Section 11.3 A Modular Exponentiation Cipher
Sage note 11.3.1. Another reminder to evaluate definitions.
Don't forget to evaluate the commands 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.3.1 The Diffie-Hellman method
In the cell below, we will pick a few numbers relevant to this method. To use it, we will need a prime numberxxxxxxxxxx
p=29 # a prime number
e=9 # a number coprime to euler_phi(p)=p-1=28
message='MathIsCool'
secret=[encode(letter) for letter in message]
code=[mod(x,p)^e for x in secret]
print(code)
print(''.join([decode(m) for m in code]))
Remark 11.3.2.
Notice that decoding the secret message code is not so useful anymore! (What would we do with the number
xxxxxxxxxx
f=mod(e,p-1)^-1 # the multiplicative inverse mod p-1 (!) to our encryption power
print(f)
print(''.join([decode(x^f) for x in code]))
Subsection 11.3.2 A bigger example
Now we will do a more real example of this. Notice how important it was that we chose an initial exponentxxxxxxxxxx
message='heymathiscooleverybody'
secret=encode(message)
secret
xxxxxxxxxx
p=next_prime(secret)
print(p)
print(factor(p-1))
xxxxxxxxxx
e=10103 # a number coprime to p-1
code=mod(secret,p)^e
code
xxxxxxxxxx
f=mod(e,p-1)^-1
print(f)
print(''.join(decode(code^f)))
next_prime()
. (If it fails, try changing e
to something coprime to xxxxxxxxxx
message='mathisreallycoolanditshouldntbeasecret'
secret=encode(message)
p=next_prime((secret)^5)
e=677 # hopefully coprime to p-1
code=mod(secret,p)^e
f=mod(e,p-1)^-1
pretty_print(html("My encoded message is $%s$"%secret))
pretty_print(html("A big prime bigger than that is $%s$"%p))
pretty_print(html("And I chose exponent $%s$"%e))
pretty_print(html("The encrypted message is $%s$"%code))
pretty_print(html("The inverse of $%s$ is $%s$"%(e,f)))
pretty_print(html("And the decrypted message turns out to be:"))
print(''.join(decode(code^f)))
Subsection 11.3.3 Recap
Here is the formal explanation of our first awesome encryption scheme.Algorithm 11.3.3. Diffie-Hellman Encryption.
To encrypt using this method, do the following.
Turn your message into a number
Pick a prime
(presumably greater than ).Pick an exponent
such that-
Encrypt to a secret message by taking
Here are the steps for decryption.
Find an inverse modulo
to and call it-
Decrypt (if you want) by taking
Celebrate in your opponent's destruction.
Proof.
Why does this work? First, note that our condition on \(f\) is equivalent to
Then we can simply compute that
which verifies that we get the original message back.
xxxxxxxxxx
def _(message='mathiscool',e=677):
secret=encode(message)
p=next_prime(100*(secret))
if gcd(e,p-1) != 1:
pretty_print(html("Looks like $%s$ isn't coprime to the prime! Try another one."%e))
else:
code=mod(secret,p)^e
try:
f=mod(e,p-1)^-1
except:
pretty_print(html("Looks like $%s$ is not coprime to the prime we chose, $%s$"%(e,p)))
pretty_print(html("My encoded message is $%s$"%secret))
pretty_print(html("A big prime bigger than that is $%s$"%p))
pretty_print(html("And I chose exponent $%s$"%e))
pretty_print(html("The encrypted message is $%s$"%code))
pretty_print(html("The inverse of $%s$ is $%s$"%(e,f)))
pretty_print(html("And the decrypted message turns out to be:"))
print(''.join(decode(code^f)))
xxxxxxxxxx
def _(message='hi',p=991,e=677):
secret=encode(message)
if is_prime(p) and gcd(p,e)==1 and p>secret:
e=677 # hopefully coprime to p-1
code=mod(secret,p)^e
try:
f=mod(e,p-1)^-1
except:
pretty_print(html("Looks like $%s$ is not coprime to the prime we chose, $%s$"%(e,p)))
pretty_print(html("My encoded message is $%s$"%secret))
pretty_print(html("A big prime bigger than that is $%s$"%p))
pretty_print(html("And I chose exponent $%s$"%e))
pretty_print(html("The encrypted message is $%s$"%code))
pretty_print(html("The inverse of $%s$ is $%s$"%(e,f)))
pretty_print(html("And the decrypted message turns out to be:"))
print(''.join(decode(code^f)))
elif not is_prime(p):
pretty_print(html("Pick a prime $p$!"))
elif p <= secret:
pretty_print(html("Make sure your prime is bigger than your secret, $%s$"%secret))
else:
pretty_print(html("Make sure that $gcd(p,e)=1$!"))
Sage note 11.3.4. Compute what you need.
Remember, you can always compute anything you need. For instance, if you for some reason didn't pick a big enough prime, you can use the following command to find one.
xxxxxxxxxx
next_prime(11058)
Historical remark 11.3.5. Diffie and Hellman.
In 2015, Whitfield Diffie and Martin Hellman won the Turing Award for their contribution, the highest award in computer science.
Subsection 11.3.4 A brief warning
Remember, the key that makes it all work (thanks to Fermat's Little Theorem/Euler's Theorem) is that exponents of congruences modxxxxxxxxxx
message='hi' # needs to be in quotes
secret=encode(message)
p=991 # needs to be bigger than secret
e=2 # NOT coprime to p-1
code=mod(secret,p)^e
code
Sage note 11.3.6. Change values right in the code.
Some Sage cells have little text boxes or sliders for interacting. But you can use any of them to change the values we are playing with; try changing the variable message
in the preceding cell to encode your own secret.
xxxxxxxxxx
f=mod(e,p-1)^-1
message,secret,code,decode(code^f) # prints all the steps
ZeroDivisionError
, which should sound relevant). It turns out not even to be possible to go backwards. Be warned that you must know the mathematics to use cryptography wisely.