Section 11.6 RSA and (Lack Of) Security
Sage note 11.6.1. A final reminder to evaluate definitions.
If you're online, don't forget to evaluate the commands in the Sage cell below so we can use words as messages instead of just numbers.
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)
Subsection 11.6.1 Beating the man in the middle
First, remember one problem with Diffie-Hellman key exchange (Section 11.4). Someone who can control your messages can actually fake them. This can't happen with public-key systems (at least not as easily). Here's why. Suppose I want to let someone verify I am who I say I am. In a public-key system, I never need to let f get known, so I encode my signature with f itself as the exponent! First, I just turn my signature into a number. I'll just use the first three letters in order to keep the encoding small enough to use small primes.xxxxxxxxxx
signature='Cri'
code=encode(signature)
print(code)
xxxxxxxxxx
p=89
q=97
n=p*q
phi=euler_phi(n)
e=71
f=mod(e,phi)^-1
secret=mod(code,n)^f
secret
xxxxxxxxxx
print(secret^e)
print(decode(secret^e))
Subsection 11.6.2 A cautionary tale
Lest you think we are now completely secure, let me warn you about one possible problem. Remember how we said above that it seems not to matter too much what e is? Well, that is sort of true, and sort of untrue. Suppose we chose to send a message using the following primes and randomly (maybe) chosen exponent e. (Notice that if gcd(e,Ο(pq))β 1, this code wouldn't have worked at all.)xxxxxxxxxx
message='hiphop'
secret=encode(message)
p=197108347
q=591324977
e=52665067560570823
n=p*q
phi=(p-1)*(q-1)
code=mod(secret,n)^e
f=mod(e,phi)^-1
print("My encoded message is %s"%secret)
print("A big product of primes bigger than that is pq=(%s)(%s)=%s"%(p,q,n))
print("(which means my secret phi(n)=phi((%s)(%s))=(%s-1)(%s-1) is %s)"%(p,q,p,q,phi))
print("And I chose exponent %s"%e)
print("The encrypted message is %s^%s congruent to %s"%(secret,e,code))
print("The inverse of %s modulo %s is %s"%(e,phi,f))
print("And the decrypted message turns out to be:")
print(''.join(decode(code^f)))
xxxxxxxxxx
trial_decrypt=code
for i in [1..25]:
trial_decrypt=trial_decrypt^e
print(''.join(decode(trial_decrypt)))
Subsection 11.6.3 The explanation
This circumstance may seem mysterious, but it really is related to mathematics we already used a number of times before. Remember that we could find an inverse for a modulo n by just taking powers of a, becausexxxxxxxxxx
g = 7 # Pick something coprime to n
print(gcd(g,phi))
i = mod(g,phi) # look at it mod phi(n)
print(i.multiplicative_order())
print(factor(i.multiplicative_order()))
xxxxxxxxxx
j=i^( 11 * 13 * 37 * 1879 * 22973) # take it to as high a power I can to reduce the order
print(j.multiplicative_order()) # make sure this is small
print(gcd(j,phi)) # check we still have the right gcd
print(j)
Subsection 11.6.4 A solution
When we found elements of big order (primitive roots, for prime modulus) in Chapter 10, we relied on having the original modulus p being prime. We did not tell the whole story, but we did do enough of what happens with other moduli to know that we should suspect that choosing n factoring as a small number of primes to powers should make it easy to find elements of big order in the group of units. (For instance, we saw that 2n had elements pretty close to being primitive roots.) And we do know something about Ο(n). Namely, since n=pq is the product of two primes, we know that Ο(n)=(pβ1)(qβ1) is also the product of two numbers. It would be too much to hope for those to be prime! After all, pβ1 and qβ1 will both be even, since p and q will be odd primes. However, it's possible to pick p and q so that pβ1=2pβ² and qβ1=2qβ², where pβ² and qβ² are both prime. In that casexxxxxxxxxx
n = 7*11
phi = euler_phi(n)
[mod(i,phi).multiplicative_order() for i in [1..phi] if gcd(i,phi)==1]
Historical remark 11.6.2. Sophie Germain.
Germain was the only female number theorist of note before the twentieth century, and is definitely an important figure. She is most well-known today for proving cases of Fermat's Last Theorem and (more importantly) developing a general strategy for attacking it for the first time. During Napoleon's invasion of various German territories, she intervened to ensure Gauss' safety, as she had corresponded with him under an assumed name for some time on this problem. Her significant work on an early problem in mathematical physics, while eventually winning an award, was largely ignored during her lifetime by the French mathematical establishment.