NTIC A Modular Exponentiation Cipher

Section 11.3 A Modular Exponentiation Cipher

To prepare for discussion of a famous public-key system, we will first discuss a (symmetric) system that leads to it. This system needs yet another invertible number theory procedure, one that we have used enough to be quite comfortable with.

🔗

That procedure is modular exponentiation as cipher. Recall that we have methods to solve modular exponential congruences (such as using primitive roots). That gives us tools sufficient to implement these subtle techniques.

🔗

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
 
1
def encode(s): # Input must be in quotes!
2
    s = str(s).upper()
3
    return sum((ord(s[i])-64)*26^i for i in range(len(s)))
4
5
def decode(n):
6
    n = Integer(n)
7
    list = []
8
    while n != 0:
9
        if n%26==0:
10
            list.append(chr(64+26))
11
            n -= 1
12
        else:
13
            list.append(chr(n%26+64))
14
        n //=26
15
    return ''.join(list)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

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 number

p,

and some legitimate exponent

e

that won’t mess things up too badly. (Also, suppose our secret is still that math is cool.)

🔗

What do I mean by ‘won’t mess things up too badly?’ Recall from Subsection 10.5.1 that when we solved

x^{3} \equiv 5 (mod 17) as 3^{3 i} \equiv 3^{5} (mod 17)

🔗

we ended up in the world of

ϕ (17) = 16

and solved

3 i \equiv 5 (mod 16) .

🔗

This required a solution

i

to exist, which wouldn’t happen for all possible choices of numbers in a congruence!

🔗

In order to keep using these ideas easily, we will pick an exponent coprime to

ϕ (p) .

🔗

Now, here is the algorithm (see also Algorithm 11.3.3). I just take my message (as a number) and raise it to the

e

power modulo

p .

It’s as simple as that!

🔗

In the cell below, we pick a convenient

e

and

p .


    
        
xxxxxxxxxx
 
1
p=29 # a prime number
2
e=9 # a number coprime to euler_phi(p)=p-1=28
3
message='MathIsCool'
4
secret=[encode(letter) for letter in message]
5
code=[mod(x,p)^e for x in secret]
6
print(code)
7
print(''.join([decode(m) for m in code]))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Here I picked

p = 29

since it’s close to

26,

and more or less arbitrarily picked an exponent

e = 9

(though it does have to be coprime to

28 = ϕ (29)

🔗

Note the steps. I first had to encode “MathIsCool” to numbers. Then I exponentiated each number in the coded version, modulo 29. To be precise, I sent each number

a \mapsto a^{9} (mod 29) .

🔗

Remark 11.3.2.

🔗

Notice that decoding the secret message code is not so useful anymore! (What would we do with the number

28

as an output, for instance?) So we usually just stick with the numbers.

🔗

Leaving aside for the moment that the letter A will now have the unfortunate property that it always stays 1, and hence basically unencrypted (this is because we are doing a toy example), how on earth would we ever decrypt this? Do we have a way to invert

a^{9} (mod 29)

🔗

in any way?

🔗

Naturally, we do! We will use exponentiation again to do so. We just need something that solves

{(a^{9})}^{f} \equiv a (mod 29),

🔗

or more concisely

a^{9 f} \equiv a^{1} (mod 29) .

🔗

(We can think of

f

as a power that inverts the original power

9 .

🔗

From our discussion in Section 10.5, solving this congruence is tantamount to solving

9 f \equiv 1 (mod 28)

🔗

and we know we can find this. In the cell below, we do it computationally, but you could do this one ‘by hand’.


    
        
xxxxxxxxxx
 
1
f=mod(e,p-1)^-1 # the multiplicative inverse mod p-1 (!) to our encryption power
2
print(f)
3
print(''.join([decode(x^f) for x in code]))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

This method of encryption is known as the Diffie-Hellman method (named after its originators, who proposed it in the mid-70’s); see Historical remark 11.4.1 and Historical remark 11.3.5.

🔗

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 exponent

e

that was coprime to

ϕ (p) = p - 1 .


    
        
xxxxxxxxxx
 
1
message='heymathiscooleverybody'
2
secret=encode(message)
3
secret

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

For convenience, I’ll just take the next prime bigger than my message.


    
        
xxxxxxxxxx
 
1
p=next_prime(secret)
2
print(p)
3
print(factor(p-1))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Next, I pick an exponent. Not every exponent will work! Beforehand I factored

p - 1

so I could find something coprime to it.


    
        
xxxxxxxxxx
 
1
e=10103 # a number coprime to p-1
2
code=mod(secret,p)^e
3
code

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

The encrypted message is now just one number. Now we need the decryption key. Luckily, that’s just as easy as taking an inverse modulo

p - 1 :


    
        
xxxxxxxxxx
 
1
f=mod(e,p-1)^-1
2
print(f)
3
print(''.join(decode(code^f)))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Here is one more extended Sage example; why not try your own message? Here, the interesting point is that I allow Sage to pick a prime for me using next_prime(). (If it fails, try changing e to something coprime to

p - 1 .

)


    
        
xxxxxxxxxx
 
1
message='mathisreallycoolanditshouldntbeasecret'
2
secret=encode(message)
3
p=next_prime((secret)^5)
4
e=677 # hopefully coprime to p-1
5
code=mod(secret,p)^e
6
f=mod(e,p-1)^-1
7
pretty_print(html("My encoded message is $%s$"%secret))
8
pretty_print(html("A big prime bigger than that is $%s$"%p))
9
pretty_print(html("And I chose exponent $%s$"%e))
10
pretty_print(html("The encrypted message is $%s$"%code))
11
pretty_print(html("The inverse of $%s$ is $%s$"%(e,f)))
12
pretty_print(html("And the decrypted message turns out to be:"))
13
print(''.join(decode(code^f)))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

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 $x .$
Pick a prime $p$ (presumably greater than $x$ ).
Pick an exponent $e$ such that $gcd (e, p - 1) = 1 .$
Encrypt to a secret message by taking

$m = x^{e} (mod p) .$

🔗

Here are the steps for decryption.

Find an inverse modulo $p - 1$ to $e,$ and call it $f .$
Decrypt (if you want) by taking

$m^{f} \equiv x (mod p)$
Celebrate in your opponent’s destruction.

Proof.

Why does this work? First, note that our condition on

f

is equivalent to

e f \equiv 1 (mod p - 1) .

Then we can simply compute that

m^{f} \equiv {(x^{e})}^{f} \equiv x^{e f} \equiv x^{1} \equiv x (mod p)

which verifies that we get the original message back.

🔗

Feel free to use the following Sage cells to see what happens with your own short messages.


    
        
xxxxxxxxxx
 
1
@interact
2
def _(message='mathiscool',e=677):
3
    secret=encode(message)
4
    p=next_prime(100*(secret))
5
    if gcd(e,p-1) != 1:
6
        pretty_print(html("Looks like $%s$ isn't coprime to the prime! Try another one."%e))
7
    else:
8
        code=mod(secret,p)^e
9
        try:
10
            f=mod(e,p-1)^-1
11
        except:
12
            pretty_print(html("Looks like $%s$ is not coprime to the prime we chose, $%s$"%(e,p)))
13
        pretty_print(html("My encoded message is $%s$"%secret))
14
        pretty_print(html("A big prime bigger than that is $%s$"%p))
15
        pretty_print(html("And I chose exponent $%s$"%e))
16
        pretty_print(html("The encrypted message is $%s$"%code))
17
        pretty_print(html("The inverse of $%s$ is $%s$"%(e,f)))
18
        pretty_print(html("And the decrypted message turns out to be:"))
19
        print(''.join(decode(code^f)))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Or you can choose a prime on your own.


    
        
xxxxxxxxxx
 
1
@interact
2
def _(message='hi',p=991,e=677):
3
    secret=encode(message)
4
    if is_prime(p) and gcd(p,e)==1 and p>secret:
5
        e=677 # hopefully coprime to p-1
6
        code=mod(secret,p)^e
7
        try:
8
            f=mod(e,p-1)^-1
9
        except:
10
            pretty_print(html("Looks like $%s$ is not coprime to the prime we chose, $%s$"%(e,p)))
11
        pretty_print(html("My encoded message is $%s$"%secret))
12
        pretty_print(html("A big prime bigger than that is $%s$"%p))
13
        pretty_print(html("And I chose exponent $%s$"%e))
14
        pretty_print(html("The encrypted message is $%s$"%code))
15
        pretty_print(html("The inverse of $%s$ is $%s$"%(e,f)))
16
        pretty_print(html("And the decrypted message turns out to be:"))
17
        print(''.join(decode(code^f)))
18
    elif not is_prime(p):
19
        pretty_print(html("Pick a prime $p$!"))
20
    elif p <= secret:
21
        pretty_print(html("Make sure your prime is bigger than your secret, $%s$"%secret))
22
    else:
23
        pretty_print(html("Make sure that $gcd(p,e)=1$!"))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

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
 
1
next_prime(11058)

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

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 mod

n

live in the world of congruences mod

ϕ (n),

as long as they are numbers coprime to

ϕ (n) .

That’s why

gcd (e, p - 1) = 1

is important.

🔗

Here’s an example of how not choosing your exponent wisely can go wrong.


    
        
xxxxxxxxxx
 
1
message='hi' # needs to be in quotes
2
secret=encode(message)
3
p=991 # needs to be bigger than secret
4
e=2 # NOT coprime to p-1
5
code=mod(secret,p)^e
6
code

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

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.

🔗

Assuming you followed along, so far, so good; it got encrypted. But what happens when we try to decrypt?


    
        
xxxxxxxxxx
 
1
f=mod(e,p-1)^-1
2
message,secret,code,decode(code^f) # prints all the steps

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

You should have gotten an error (in fact, a 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.

Prev Top Next