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)
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 integerxxxxxxxxxx
p=89
q=97
n=p*q
print("Multiply the primes %s and %s to get our modulus %s"%(p,q,n))
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.
xxxxxxxxxx
2^32+1,factor(2^32+1),nth_prime(116)
Subsection 11.5.2 The practice of RSA
That's the preliminaries. From now on, we do exactly the same thing as before, choosing anExample 11.5.4.
With the same primes, let's choose
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
xxxxxxxxxx
f=mod(e,phi)^-1;f
Now, just like with Diffie-Hellman, I raise my message (number) to the power
xxxxxxxxxx
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 modulusAlgorithm 11.5.5. RSA encryption algorithm.
In order to encrypt a message
In order for the owner of the key to decrypt a message
for any
Proof.
Assume the original message was \(x\) and that this is coprime to \(n\text{.}\) Since
we have \(ef=k\phi(n)+1\) for some integer \(k\text{.}\) Hence by Euler's Theorem we have
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
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.)
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)
xxxxxxxxxx
message='mathiscool' # needs to be in quotes
secret=encode(message) # needs to be less than n
print("My message is %s numerically"%secret)
The documentation used to also recommend
-F4|-3
: The public exponent to use, either 65537 or 3. The default is 65537.
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)
False
above (I did once in a while during testing), then just pick a different 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)
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))
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)))