5
\$\begingroup\$

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?

Comments, suggestions welcome.

'''  RSA encryption
     inspired on: https://www.youtube.com/watch?v=M7kEpw1tn50
     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[4]

        # 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()
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Ilkhd Aug 15 at 18:00
1
\$\begingroup\$

1) Real implementation of RSA use the Chinese Remainder Theorem, which greatly improves the performance.

2) The big performance difference between encryption and decryption is a normal thing for RSA. It comes from the fact, that the performance of the modular exponentiation used depends on the number of 1 bits in the exponent. If you either chose the public exponent to be very small (like you are doing in your code, which is insecure btw) or large but with a lot of zeroes in its binary representation (usually e=655537=100...001 is used) public key operations (=encryption) will be fast. The private exponent can not be controlled and will have ~1/2 of its bit set to one, making the decryption a lot slower.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.