Introduction¶
We will work out a small example of RSA encryption, generating a public/private keypair and sending a simple message.
The example is based on the tutorials on doctrina.org:
http://doctrina.org/How-RSA-Works-With-Examples.html
We use code from a toy RSA implementation by Alex Roper:
https://github.com/calmofthestorm/toys/blob/master/rsa/rsa.py
Key Generation¶
Key generation is complex, we pick two "large" primes, p and q.
p = 7
q = 19
n = p * q
n
133
With this small example, we can encrypt numbers smaller than 133, which would allow us to send messages consisting of the 127 lower ASCII (7-bit ASCII) characters.
Now we compute $\phi$, the totient of n. In our case we can use the factorization of n into p and q to quickly compute the totient. The security of RSA depends in great part on it being dificult to factor n. Our example is way too simple.
$\phi(n) = \phi(p) \cdot \phi(q) = (p-1)(q-1)$
phi_n = (p-1)*(q-1)
phi_n
108
Public key¶
We're ready to pick a public key. Choose a prime e in the range [3,phi(n)), such that gcd(e,phi(n)) = 1. We chose 5, which is too small for the real world, but useful for this example. We import the rsa.py module for some usefull functions (like gcd).
e = 5
import rsa
rsa.gcd(e,phi_n)
1
public_key = (e, n)
The private key is computed as the mutiplicative inverse of e in the integers mod phi(n). I'll use an auxilliary function in rsa.py to compute the inverse, but we can check it using regular math.
d = rsa.modinv(e, phi_n)
d
65
e * d
325
(e*d) % phi_n
1
private_key = (d, n)
Encryption¶
Now we're ready to encrypt and decrypt information. We want to securely transmit someone's birthday, which is October 11. Recall that our n is 133, so we can work with numbers smaller than that. Let's send the birthday as a sequence of two numbers, the first is 10, the second 11.
To encrypt a message m for a person, we can use the public key (e), and compute the ciphertext c as m^e mod n = c.
c1 = 10**e % n
c1
117
c2 = 11**e % n
c2
121
The encrypted message is then 117, 121, which can be transmitted over any channel.
Decrypting¶
To decrypt, we perform the same procedure, but use the private key (d) to compute the plaintext t from the ciphertext.
c^d mod n = t
t1 = c1**d % n
t1
10L
t2 = c2**d % n
t2
11L
Conclusion¶
RSA isn't magic, although sometimes it seems like it. We can use simple arithmetic like multiplication, division and remainders to compute ciphertext and plaintext. The magic is in the algorithm.
Now go read the linked resources to find out more. Especially why RSA works.