# A simple implementation of the principle of RSA encryption

Inspired by a Numberphile video I made a little program that shows the principles of RSA encryption and decryption. To calculate the keys I used the explanation in this link: rsa public private key encryption explained. Fascinating what you can do in a few lines of code and how Python can handle to powering of large numbers.

One observation is that with large prime numbers encryption goes relatively fast starting with ascii code numbers that are relatively small less than 200 or so, but the decryption goes much slower as the encrypted numbers are magnitudes larger. How is this solved in practice? and how is this all working with really large primes?

'''  RSA encryption
and http://jcla1.com/blog/rsa-public-private-key-encryption-explained

some conditions:
- prime numbers must be > 1 and not equal
- prime factor must sufficiently large to accommodate the ascii numbers, let's say > 150
- so for example (2, 191) will do as well as (11, 17)
'''

class RSA():
''' methods for calculating keys, encrypt and decrypt ascii messages
'''
@staticmethod
def gcd(a, b):
while b:
a, b = b, a % b
return a

@classmethod
def encrypt(cls, message):
message_letters = [ord(letter) for letter in message]
message_encrypted = ''.join([chr(letter**cls.public_key % cls.prime_factor) for letter in message_letters])
return message_encrypted

@classmethod
def decrypt(cls, message_encrypted):
message_encrypted_letters = [ord(letter) for letter in message_encrypted]
message = ''.join([chr(letter**cls.private_key % cls.prime_factor) for letter in message_encrypted_letters])
return message

@classmethod
def calc_keys(cls, prime_1, prime_2):
cls.prime_factor = prime_1 * prime_2
totient = (prime_1 - 1) * (prime_2 - 1)

# calculate the possible public keys where gcd(public_key, totient) == 1, then select the 5th one (this is abritary, any
# of the public_keys could have been selected
# (Note above link has an error that the gcd of public_key and totient must be 1, not public_key
#  and the prime_factor as suggested in the article)
public_keys = []
for i in range(totient):
if cls.gcd(i, totient) == 1:
public_keys.append(i)
cls.public_key = public_keys

# calculate the private key based on public key and totient when (public_key * private_key - 1) % totient == 0
cls.private_key = 0
x = -1
while x != 0:
cls.private_key += 1
x = (cls.public_key * cls.private_key - 1) % totient

return (cls.prime_factor, cls.public_key, cls.private_key)

def main():
rsa = RSA()
print(rsa.calc_keys(61, 53))

message = 'hello this is my encrypted message'
encrypted_message = rsa.encrypt(message)
decrypted_message = rsa.decrypt(encrypted_message)

if message == decrypted_message:
print('Hurray!!')
print(f'message: {message}\nencrypted message: {encrypted_message}'
f'\ndecrypted message: {decrypted_message}')
else:
print('Ough, someting wrong here  ... !')

if __name__=="__main__":
main()

• Normally, you never encrypt the whole message with RSA. Usually you encrypt a randomely generated symmetric key (ex. AES), encryot the message with it and concatenate them together. – Ilkhd Aug 15 at 18:00