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 letxxxxxxxxxx
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 whatxxxxxxxxxx
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 forxxxxxxxxxx
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 modulusxxxxxxxxxx
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.