NTIC RSA Public Key

Section 11.5 RSA Public Key

Sage note 11.5.1. We keep reminding you.

Remember, this cell contains the command used to make numbers from letters (and vice versa), so always evaluate the cell before doing any en/decoding.

xxxxxxxxxx
 
def encode(s): # Input must be in quotes!
    s = str(s).upper()
    return sum((ord(s[i])-64)*26^i for i in range(len(s)))
​
def decode(n):
    n = Integer(n)
    list = []
    while n != 0:
        if n%26==0:
            list.append(chr(64+26))
            n -= 1
        else:
            list.append(chr(n%26+64))
        n //=26
    return ''.join(list)

🔗

In order to deal with some of the issues of symmetric systems, we will now introduce the most famous public-key system. Recall that this means we have an encryption key that is easy for anybody at all to use, but is very difficult to undo unless you know the secret. (Sometimes this is called a trapdoor system, because it's easy to fall in but it's hard to get back out unless you know where the secret passageway is!)

🔗

Historical remark 11.5.2. Who is RSA?

The formal name for the system in this section is “Rivest, Shamir, Adleman” or RSA, for Ron Rivest, Adi Shamir, and Leonard Adleman, who developed it in the late 1970s. The acronym continues to be the name of the security company they cofounded. Like the Diffie-Hellman protocol, the British intelligence unit GCHQ also developed it in earlier (then-classified) documents.

🔗

Subsection 11.5.1 The background

🔗

The idea behind RSA is to make Diffie-Hellman, which relies only upon Theorem 7.5.3 and primes, into a system which involves Euler's Theorem (9.2.5). We want to do so, but not so heavily as to make the computation too expensive. (With the advent of mobile devices, it turns out that this has once again become a big issue, so much so that even RSA or similar methods are being replaced with more sophisticated ones involving curves like those coming from the Mordell equation (recall Section 15.3), known as elliptic curves. See [E.4.19] for an excellent full introduction to this at about the level of this text, which could help in answering Exercise 25.9.10; a more targeted approach is in [E.2.10, Chapter 18.6].

🔗

It turns out that the easiest way to keep computation easy while sticking with exponentiation is to choose as a modulus a large integer

$n$ with only two prime factors, instead of one large prime

$p$ as we did before. For instance:

xxxxxxxxxx
 
p=89
q=97
n=p*q
print("Multiply the primes %s and %s to get our modulus %s"%(p,q,n))

🔗

Exponents here live in the world of

$\phi(n)\text{.}$ We can easily compute this using Fact 9.5.2 (so that

$\phi(n)=(p-1)(q-1)$ ). So the computations are going to be easy for us, assuming we know

$p$ and

$q\text{.}$

🔗

But they will not be so easy to compute without that knowledge, for which we need to have the prime decomposition of

$n\text{.}$ In particular, for reasonably large

$n\text{,}$ that means

$\phi(n)$ is essentially secret to anyone who isn't tough enough to factor

$n\text{.}$

🔗

Remark 11.5.3.

At least that's what people currently believe; if it isn't true, we are in deep trouble security-wise, as we will see later.

🔗

As an example, in the early 1600s, Fermat believed

$2^{32}+1$ was prime. It took until 1732 and the genius of Euler to factor

$2^{32}+1$ as follows¹, which shows the one hundred sixteenth prime is the smaller of two factors.

Weil points out in [E.5.8, II.IV] that Fermat had the tools to do this (see the discussion at the end of Subsection 7.5.2), but apparently just completely neglected to use them, so convinced was he of his correctness.

xxxxxxxxxx
 
2^32+1,factor(2^32+1),nth_prime(116)

🔗

Hence

$n=2^{32}+1$ wouldn't have been a bad

$n$ to choose in the early 1700s, since it would take a lot of trial and error to get to the one hundred sixteenth prime!

🔗

Subsection 11.5.2 The practice of RSA

🔗

That's the preliminaries. From now on, we do exactly the same thing as before, choosing an

$e$ coprime to

$\phi(n)\text{,}$ etc. This time, though, instead of keeping

$e$ secret, we let anybody know it (along with

$n\text{,}$ which we have to let people know anyway).

🔗

Example 11.5.4.

With the same primes, let's choose $e=71\text{,}$ because that is coprime to $\phi(89\cdot 97)=\phi(89)\phi(97)=88\cdot 96=8448\text{.}$

xxxxxxxxxx
 
p=89
q=97
n=p*q
phi=euler_phi(n)
e=71
print("Multiply the primes %s and %s to get our modulus %s"%(p,q,n))
print("Are e=%s and phi(%s)=%s coprime?"%(e,n,phi))
print(gcd(e,phi)==1)

We compute an inverse mod $\phi(n)$ just as before, which will be (as before) our decryption key. Since we are able to compute $\phi(n)\text{,}$ it isn't hard to get an inverse for $e\text{.}$ If you only knew $n\text{,}$ though, it would be very hard to do this (for reasonably large $n$ ); or at least, it is supposed to be hard to compute $\phi(n)$ without factoring $n\text{,}$ though it has yet to proven.

xxxxxxxxxx
 
f=mod(e,phi)^-1;f

Now, just like with Diffie-Hellman, I raise my message (number) to the power $e$ to encrypt, and raise to the power $f$ to decrypt an encrypted message. Here are all the steps together!

xxxxxxxxxx
 
@interact
def _(message='hi',p=89,q=97,e=71):
    secret=encode(message)
    n = p*q
    phi = (p-1)*(q-1)
    if gcd(n,e)==1 and n>secret:
        code=mod(secret,n)^e
        try:
            f=mod(e,phi)^-1
            pretty_print(html("My encoded message is $%s$"%secret))
            pretty_print(html(r"A big product of primes bigger than that is $pq=%s\cdot%s=%s$"%(p,q,n)))
            pretty_print(html(r"(which means my secret $\phi(n)=\phi(%s\cdot %s)=(%s-1)(%s-1)$ is $%s$)"%(p,q,p,q,phi)))
            pretty_print(html("And I chose exponent $%s$"%e))
            pretty_print(html(r"The encrypted message is $%s^{%s}\equiv%s$"%(secret,e,code)))
            pretty_print(html("The inverse of $%s$ modulo $%s$ is $%s$"%(e,phi,f)))
            pretty_print(html("And the decrypted message turns out to be:"))
            print(''.join(decode(code^f)))
        except:
            pretty_print(html(r"Looks like $%s$ is not coprime to $\phi(%s)=%s$"%(e,n,phi)))
    elif gcd(phi,e)!=1:
        pretty_print(html(r"Make sure that $gcd(\phi(n),e)=1$!"))
    elif n <= secret:
        pretty_print(html("My encoded message is $%s$"%secret))
        pretty_print(html(r"Make sure that $pq=%s\cdot %s=%s$ is bigger than your secret"%(p,q,n)))

🔗

Subsection 11.5.3 Why RSA works

🔗

Now we have an encryption method where anyone can encrypt. The modulus

$n$ (not written as

$pq$ ) and

$e$ are both published, and anyone who wants to send a message of length

$n$ or less just exponentiates. You just have to be sure that

$\phi(n)$ and

$e$ are coprime for it to be defined properly.

🔗

Algorithm 11.5.5. RSA encryption algorithm.

In order to encrypt a message $x$ via RSA with public key $(n,e)\text{,}$ you do

$\begin{equation*} x^e\text{ (mod }n)\text{.} \end{equation*}$

In order for the owner of the key to decrypt a message $m\text{,}$ they do

$\begin{equation*} m^{e^{-1}}=m^f\text{ (mod }n) \end{equation*}$

for any $f$ solving $ef\equiv 1\text{ (mod }\phi(n))\text{.}$

🔗

Proof.

Assume the original message was $x$ and that this is coprime to $n\text{.}$ Since

\begin{equation*} ef\equiv 1\text{ (mod }\phi(n)) \end{equation*}

we have $ef=k\phi(n)+1$ for some integer $k\text{.}$ Hence by Euler's Theorem we have

\begin{equation*} \left(x^e\right)^f=x^{ef}=x^{k\phi(n)+1}=\left(x^{\phi(n)}\right)^k x^1\equiv 1^k x\equiv x\text{ (mod }n)\text{.} \end{equation*}

So it all works out, we recover the original message.

Interestingly, because $n=pq$ is a product of different primes, we don't actually need the coprime hypothesis for the message, which is nice not to have to check. Suppose $p\mid x$ but $\gcd(q,x)=1\text{,}$ for example. Then modulo $p$ we have $\left(x^e\right)^f\equiv x$ because both are zero, while modulo $q$ we do a bit more computation to see

\begin{equation*} \left(x^e\right)^f = x^{k\phi(n)+1} = x^{k\phi(p)\phi(q)+1}\equiv\left(x^{\phi(q)}\right)^{k\phi(p)} x^1\equiv x\text{.} \end{equation*}

By (essentially) the Fundamental Theorem of Arithmetic that suffices to show they are equivalent modulo $n=pq$ as well. (If $pq\mid x\text{,}$ then $x\equiv 0$ so things aren't very interesting.)

🔗

And if someone nefarious were to try to decrypt this, they would need access to

$f$ somehow, or something equivalent to it mathematically. That would mean solving

$\begin{equation*} ef\equiv 1\text{ (mod }\phi(n)) \end{equation*}$

🔗

for

$f$ without actually knowing what

$\phi(n)$ is!

🔗

Naturally, that is pretty easy to compute in the cases above. But in real life?

xxxxxxxxxx
 
p=next_prime(randrange(2^50))
q=next_prime(randrange(2^50))
n=p*q # needs to be bigger than secret
print("The first part of my key, %s, is the product of my secret primes"%n)

🔗

The

$n$ in the cell above is the product of two primes – but would you like to try to compute

$\phi(n)$ by hand? Without knowing the actual primes, it could be very difficult to figure out

$\phi(n)\text{,}$ which you probably need to get

$f\text{.}$

🔗

Realistic examples have much larger primes than this, say 100 digits. But let's see what would happen next in a ‘real’ example.

xxxxxxxxxx
 
message='mathiscool' # needs to be in quotes
secret=encode(message) # needs to be less than n
print("My message is %s numerically"%secret)

🔗

Hopefully the randomness of the

$p$ and

$q$ I picked didn't keep

$n$ from being greater than the numerical value of the message.

🔗

Now we pick the other piece of our key,

$e\text{.}$ Believe it or not, it doesn't really seem to matter (though no one has proved this) what

$e$ is. Documentation for a widely used RSA implementation says this:

-F4|-3: The public exponent to use, either 65537 or 3. The default is 65537.

🔗

The documentation used to also recommend

$17\text{,}$ which I figure is easier to use than

$65537$ but less obvious than

$3\text{.}$ Let's check that it's coprime to the modulus of the key.

xxxxxxxxxx
 
phi=euler_phi(n)
e=17 # needs to be coprime to phi
print("And I can check whether e=17 is coprime to phi(%s)"%n)
print(gcd(phi,e)==1)

🔗

If you get False above (I did once in a while during testing), then just pick a different

$e\text{.}$ (Only evaluate the following cell if you have to!)

xxxxxxxxxx
 
e=65537 # needs to be coprime to phi
print("Second try - is e=65537 coprime to phi(%s)?"%n)
print(gcd(phi,e)==1)

🔗

Once we have our key, away we go!

xxxxxxxxxx
 
code=mod(secret,n)^e
print("My encoded message is %s"%secret)
print("A big product of primes bigger than that is n=%s"%n)
print("And I chose exponent %s"%e)
print("The encrypted message is %s^%s congruent to %s"%(secret,e,code))

🔗

Crack that! Who knows what

$\phi(n)$ is?

🔗

But if I know it, I can calculate the inverse of

$e\text{:}$

xxxxxxxxxx
 
f=mod(e,phi)^-1
print("My original primes were %s and %s"%(p,q))
print("So phi(n) = (%s-1)(%s-1) = %s"%(p,q,phi))
print("Which makes f = %s"%f)
print("And the decrypted message turns out to be:")
print(''.join(decode(code^f)))