Generating RSA Keys in Python

Posted: 2024-05-31
Tags: Python, RSA

• Actionable Takeaways
• The RSA Algorithm
• Python’s PyCryptodome Module
• Key Generation
• (En|De)crypting with the Key
• Python’s gmpy Module

Actionable Takeaways

from Crypto.PublicKey import RSA

key = RSA.generate(2048)

print("PUBLIC KEY:")
print("N =", key.n)
print("E =", key.e)

print("PRIVATE KEY:")
print("D =", key.d)

The RSA Algorithm¹

The RSA algorithm relies on the fact that for sufficiently large \(n\), \(e\), and \(d\) it can be shown that for all integers \(m\) such that \(0 \leq m < n\) the values of \((m^e)^d\) and \(m\) are congurent modulo \(n\). Written as an equation:

Here \(m\) is the message, \(e\) the encryption key, and \(d\) the decryption key. The value of \(n\) is found by multiplying two large primes together.

The public key is \(n\) and \(e\), which can be freely distributed.

The private key is \(d\), which must remain secret.

It is also critical that the two prime numbers used to generate \(n\) remain secret, since with them the value of \(d\) can be easilt calculated.

NOTE: The values of \(e\) and \(d\) can be swapped. This is because \((x^m)^n = x^{(mn)}\) and \(mn = nm\). Generally, the smaller of the two values is used for \(e\) and the larger for \(d\).

Python’s PyCryptodome Module

Installed with the command pip install PyCryptodome at the command line (or with !pip install PyCryptodome in a Jupyter notebook).

Provides the class Crypto.PublicKey.RSA.RsaKey² with a generate() function and reports to values of n, e, d, etc.

from Crypto.PublicKey import RSA

print(RSA.generate(2048)) 

Python conveniently has builtin support for big integers.

Key Generation

First, \(n\) is found by selecting two prime numbers \(p\) and \(q\), where \(n = pq\).

In practice, \(e\) is always taken to be \(65,537\), and the value of \(d = e^{-1} (\operatorname{mod}n)\), in Python: d = pow(e, -1, n).

Theoretically, the value of \(e\) is chosen by using either Euler’s or Carmichael’s totient functions. However, using \(65,537\) is considered secure and makes calculating the encrypted value faster because \(65,537 = 2^{16} + 1\).

(En|De)crypting with the Key

Using the RSA key is easy with Crypto.Cipher.PKCS1_OAEP³:

from Crypto.Cipher import PKCS1_OAEP

cipher = PKCS1_OAEP.new(key)

ciphertext = cipher.encrypt(b"this is a test")

print(cipher.decrypt(ciphertext))

It is possible (although not advised, due to attacks against improperly padded messages) to just do the math directly:

# convert string to binary string to integer
message = int(''.join(bin(ord(c))[2:].zfill(7) for c in "test"), 2)

# encrypt
encrypted = pow(message, key.e, key.n)

# decrypt
decrypted = pow(encrypted, key.d, key.n)

# convert int to binary string to string
''.join([chr(int(bin(decrypted)[i+2:i+9], 2)) for i in range(0, len(bin(decrypted)[2:]), 7)])

The construct (a ** b) % c is extremely slow compared to pow(a, b, c).

Python’s gmpy Module⁴

Python’s builtin support for big integers can be slow for certain operations (e.g. int to string conversion⁵).

The gmpy module provides improved performance.

Not strictly necessary, but possibly useful if performance slowdowns are seen.