A simple implementation of the principle of RSA encryption

Question

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()

Answer 1

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.

Answer 2

Programming:

1. You can see that OpenSSL uses Chinese Remainder Theorem (CRT) for RSA modular exponentiation. CRT gives you approximately 4x speed up.
2. There is nothing wrong with a small public key exponent e as long as a proper padding applied. Except 2, when public exponent is 2, you will have Rabin-Cryptosystem. See security section;
3. The commons public keys are {3, 5, 17, 257 or 65537}. This helps to reduce the number of multiplications. This is considered helpful if you consider client's low power devices.
4. The modular exponentiation should be performed modular version of repeated squaring method. Or you can use pow function of python which already has fast modular multiplication. In your case, firstly the power is calculated this means that the number becomes bigger and bigger and therefore slow.

Security:

1. RSA is a trapdoor function and should never be used without a proper padding.
2. For Encryption you can use PKCS#1.5 padding scheme or better use Optimal Asymmetric Encryption Scheme (OAEP).
3. For signatures you can use Probabilistic Signature Scheme (RSA-PSS).
4. Normally RSA is not used for encryption. It is used for signatures.
5. Usually, we prefer hybrid cryptosystem in that public key algorithms are used for key exchange/establishment then a symmetric algorithm is used.
6. There is once useful case is where RSA encryption is used, RSA-KEM where it is used to establish key for symmetric algorithms
7. Never use small private exponent, this is insecure.