💾 Archived View for tilde.team › ~steve › blog › rsa.gmi captured on 2023-04-20 at 00:23:02. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

RSA Tutorial

Back

I spent the weekend learning a bit about RSA. After talking about GPG, TLS and IPFS I realized RSA is mentioned many times and I don't understand it thoroughly. I read about it in wikipedia and implemented it in python. There are a few points I still don't understand related to number theory and I didn't learn the proof yet. But writing the python code to encrypt and then decrypt a message gave me some understanding of how it works.

I don't understand why breaking it is "hard"; there's the naive part related to scaling which could take thousands of years to solve/factor and then there's the "hacking" part which I'm not familiar with at all, related to how an input file is convert to a number (a padding scheme), how to choose a good exponent (looks arbitrary to me, dark art), how different the seed prime numbers P, Q should be from one another and possibly more nuances.

RSA in 60 second

given a message m represented as a number, we can encrypt it using a public key n (a number) and an exponent e (another number) such that

enc = m ^ e   mod n

can not be inverted back to recover m. An individual holding the private key d (another number) can calculate

enc ^ d = m   mod n

and if the maths are right she should get the exact original message. In other words, it's a scheme to find two numbers e, d such that

(m ^ e) ^ d == m mod n

holds for every m and such that knowing e can not help you finding d.

Seed Primes

OK, let's implement it. First, one should know that if you take two big numbers a, b and exponent them a ^ b you would get another large number. Taking a modulo of the result offers us an optimization which reduces the complexity to O(log2 b) down from O(b). In python, one can use the builtin function pow(a,b,n) to calculate a ^ b mod n.

Since the numbers are always taken to be modulo n, it also means the message cannot be larger (when converted to a number) than the public key n. If that's the case, one needs to use hybrid cryptosystem (combining symmetric encryption for the large files with asymmetric encryption for the symmetric key).

We start by taking two prime numbers p, q. The public key n is their product:

p = 416340643409549923009499483672943658225449234468718458074545744166165761632775602620065965918180977670757304830003832394505937083402258963576559007722425762948575838614251669169597413298652506870099047858967861502402226213779153363701549329970522928384230456326002348479551787668160607179516281766377
q = 346102910600806706282390081096522025891264990081561722073430930053129965029570527337591651144945172371749340297815923555387823862619852785213375844961248649329605511920816304203232191954950124812520849477072541700194634917313937939653674231142444601671706373495901166534219973793176350795828518534761

n = p * q

When we say we generate a 4096 bit RSA key, it means n has 4096 bits in binary representation. I took the primes from bigprimes.org.

n has only math.log2(n) = 1990 bits because that's the biggest primes the website can generate.

Modulus

Next we calculate the Carmichael's function λ(n). Using the fact that n = p * q where p,q are primes we get

λ(n) = lcm(λ(p),λ(q)) = lcm(ϕ(p), ϕ(q)) = lcm(p-1, q-1)

where ϕ is the Eular totient function, lcm is least-common-multiple, and I used

Carmichael Function

We can calculate lcm using its relation to gcd - greatest common denominator:

lcm(a,b) = |a * b| / gcd(a,b)

We implement a trivial gcm :

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

And calculate λ(n):

lam = (p - 1) * (q - 1) // gcd(p - 1, q - 1)

Exponent

To complete the key generation step, we need to choose an exponent e. It should be a coprime with λ(n) and a popular choice is

e = 2**16 + 1
assert gcd(e, lam) == 1

What other considerations are relevant in choosing e? I don't know.

The public key is the pair (n, e).

Private Key

Next we calculate a private key d from λ(n). We don't need p, q anymore. d is the inverse of e modulo λ(n) so we need to solve

d * e = 1   mod λ(n)

It can be calculated efficiently using the extended Euclidean algorithm:

def inverse(a, n):
    t = 0; newt = 1
    r = n; newr = a

    while newr != 0:
        quot = r // newr
        t, newt = newt, t - quot * newt 
        r, newr = newr, r - quot * newr

    if r > 1:
        return "a is not invertible"
    if t < 0:
        t = t + n

    return t

This function is based on

Extended Euclidean algorithm

This part is the least understood by me. Anyway, we find the secret decryption key d:

d = inverse(e, lam)

d should be kept secret. We don't need λ(n) anymore.

Encrypting a message

Now that we have (n, e) and d we can test it. RSA works in two ways. One way is people using the public (n, e) to write a message only you (holding d) can read. The "opposite" way is you creating a small signature using d everyone holding (n, e) can verify that it must have been you who wrote the message. We'll test the former.

message = "Hi, how are you doing? 😀"

Here we convert the message to an integer. It appears there is great complexity in the way this could be done. It's called a padding scheme, and apparently, there are ways to do that that make the entire RSA vulnerable to attacks. We ignore this now and just convert the python string to it's hex representation and then to regular decimal integer.

message = message.encode().hex()
message = int(message, 16)

We now encrypt the message using the public (n, e):

encrypted = pow(message, e, n)

According to math, and by picking p, q (and hence n) large enough, one cannot inverse this to get back the original message even when knowing n and e.

Now the receiver uses her private d key:

decrypted = pow(encrypted, d, n)

And convert it back to a string:

decrypted = bytes.fromhex(hex(decrypted)[2:]).decode()

You should get exactly the same message as the input. Great success 👍

------------------------------------------------------------------------

Addendum

Pointed out by ~dzwdz two considerations for picking out e:

1. Exponentiation with modulo uses an optimization trick that reduces complexity of m ^ e mod n to O(log2 e) as mentioned; the algorithm loops over the binary represention of e; it's beneficial choosing e that has only 2 non zero binary bits, such as 3 and 2**16+1.

2. Complexity, having e not too big but also not too small: if m ^ e is smaller than n then

pow(message, e, n) = pow(message, e)

and an adversary can solve for m:

from sympy import Rational
e = 3
encrypted = pow(message, e, n)
decrypted = encrypted ** Rational(1,e)

assert decrypted == pow(encrypted, d, n)

so one can decrypt the message only with the public e. That's the reason padding is needed for short messages, given e and n.