# 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.

In :
p = 7
q = 19

n = p * q

In :
n

Out:
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)$

In :
phi_n = (p-1)*(q-1)

In :
phi_n

Out:
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).

In :
e = 5

import rsa

rsa.gcd(e,phi_n)

Out:
1

In :
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.

In :
d = rsa.modinv(e, phi_n)
d

Out:
65

In :
e * d

Out:
325

In :
(e*d) % phi_n

Out:
1

In :
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.

In :
c1 = 10**e % n
c1

Out:
117

In :
c2 = 11**e % n
c2

Out:
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

In :
t1 = c1**d % n
t1

Out:
10L

In :
t2 = c2**d % n
t2

Out:
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.