2017-03-13.sagews

Math 152 - Intro to Mathematical Software

2017-03-13

Kiran Kedlaya; University of California, San Diego

adapted from lectures by William Stein, University of Washington

Guest lecturer (and worksheet author): Kartik Venkatram

** Lecture 26: Public key cryptography and number theory, part 1 **

Announcements:

• Kiran will be monitoring the chat room this hour.

• No sections today.

• Additional guest lecture Wednesday: Alina Bucur

• Office hours this week:

  • Zonglin: Thursday, March 16, 3:30-5:30 in APM 5748.

  • Kiran: Friday, March 17, 11-12 in APM 7202.

  • Peter: Friday, March 17, 12-1 and 3-4 in APM 6132.

• Homework due Friday, 8pm. Peer grading due Sunday, 8pm.

• No final exam!

• Please do your course evaluation (CAPE)! Evaluations close Monday, March 20 at 8am.

# Let's make the field of integers modulo 23. For historical reasons, it is called a "Galois field"
p = 23
F = GF(p)
print F

print "13+17 = ", F(13)+F(17)
print "13*17 = ", F(13)*F(17)

Finite Field of size 23 13+17 = 7 13*17 = 14

print ?, ?

File: 
Docstring :

a = F(13)
b = 5
c = a^b
print a, "^", b, "=", c
print "log_", a, c, "=", c.log(a) 

13 ^ 5 = 4 log_ 13 4 = 5

m = euler_phi(p)
print "phi(p) =", m
print "powers of 5:", [F(5)^a for a in range(2*m)]
print "powers of 2:", [F(2)^a for a in range(2*m)]

phi(p) = 22 powers of 5: [1, 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14, 1, 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14] powers of 2: [1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12]

e = randint(1, 11)
c = F(2)^e
%timeit c.log(F(2))

p = 3408871799
F2 = GF(p)
e = randint(1, (p-1)/2)
c = F2(2)^e
%timeit c.log(F2(2))

625 loops, best of 3: 98.2 µs per loop 5 loops, best of 3: 137 ms per loop

%latex
\noindent Though this doesn't look so bad, it is still 1000x worse...practical implementations of Diffie-Hellman use 1000 bit primes (or larger), for which discrete logarithms are believed to be extremely difficult.

\section*{Diffie-Hellman}
Next, let's use our machinery to construct a Diffie-Hellman key exchange protocol: here are the steps.
\begin{enumerate}
\item Alice and Bob (publicly) agree on a large prime $p$, modulo which all computations will take place, and a generator $g$ of $GF(p)$.
\item Alice chooses a secret, random integer $a$ between $0$ and $p-1$, while Bob chooses a secret random integer $b$ in the same range.
\item Alice (publicly) transmits $A=g^a\mod p$ to Bob, while Bob (publicly) transmits $B=g^b\mod p$ to Alice.
\item Alice and Bob both compute $g^{ab}\mod p = B^a\mod p = A^b\mod p$, and use that value as their shared secret.
\end{enumerate}
Now, if Eve wants to find their shared secret, she has to be able to compute $g^{ab}$ only knowing $g$, $g^a$, and $g^b$. This is called the \emph{Diffie-Hellman problem}, and is believed to be as hard as computing discrete logarithms in general.

You should have all the tools to make this yourself: please fill in the outline below.

# Public stuff
p = random_prime(2^64)
Fp = GF(p)
g = Fp.multiplicative_generator()

# Alice's private and public keys
a = ?
A = ?

# Bob's private and public keys
b = ?
B = ?

# Alice computes the shared secret
K_alice = ?

# Bob computes the shared secret
K_bob = ?

# Finally, check that they are the same
K_alice == K_bob

%latex
\noindent And that's it! Alice and Bob have a shared secret, which they can use to send messages.

\section*{Attacking Diffie-Hellman}

We're going to consider two attacks on Diffie-Hellman key exchange: the first is a \emph{brute force} attack on the system, while the second is an attack which works if $p$ is a \emph{weak Diffie-Hellman prime}. In both cases, we're actually going to attack the discrete logarithm problem directly. That is, given $g^a$ for some unknown $a$, find $a$

The simplest brute force attack, of course, is simply \emph{exhaustion}. That is, just try every value until we find a hit. Let's try this on a particularly small example.

p = previous_prime(2^20)
Fp = GF(p)
g = Fp.multiplicative_generator()

# Alice's public key, based on an "unknown" random number
A = g^(randint(2, p-1))

# Now let's find it
def exhaust(g, A):
    for a in range(2, g.multiplicative_order()):
        if g^a == A:
            return a

%time
print A, g^exhaust(g,A)

425438 425438 CPU time: 0.18 s, Wall time: 0.19 s

%latex
\noindent Try the above with a larger prime, say one with 20 bits. Hint: you can get a random n-bit prime by doing {\tt random\_prime($2^n$)}. How much harder is it?

There are better brute-force attacks which use memory to reduce the amount of computation required. We will talk about one particular one, called \emph{baby-step giant-step}, which works as follows:
\begin{enumerate}
\item Compute $m=\lfloor\sqrt{p-1}\rfloor$
\item For $e=0,\ldots,m-1$, compute and store $g^e\mod p$ along with the index $e$.
\item For $f=0,\ldots,m-1$, compute $A*g^{-fm}\mod p$, and check if it's in the list above. If it is, stop, and output the pair $(e,f)$.
\end{enumerate}
If the above produces an output, we know that $g^e \equiv g^{a-fm}\mod p$, i.e. $e \equiv a-fm\mod p-1$, i.e. $a \equiv e+fm\mod p-1$. Moreover, since we can always write $a<p-1$ as $e+fm$ for $e,f < m$, this algorithm should always output.

Now, let's try it out.

p=4294967291 # a 32-bit prime
Fp = GF(p)
g = Fp.multiplicative_generator()

# Construct random public key as before
A = g^randint(0,p-1)

def bsgs(g, A):
    # Step 1
    m = floor(sqrt(g.multiplicative_order()))
    # Step 2
    small_g_powers = {g^e:e for e in range(m)}
    # Step 3
    gpow = A
    mult = g^(-m)
    for f in range(m):
        if gpow in small_g_powers:
            return small_g_powers[gpow]+f*m
        gpow *= mult

%time
print A, g^bsgs(g, A)

3059695168 3059695168 CPU time: 0.21 s, Wall time: 0.20 s

%latex
\noindent Note that we were able to break a 32-bit problem faster than the exhaustive approach broke a 20-bit problem. Try going a little higher, say a 40-bit prime.

Finally, let's look at one attack involving a potential weakness of the prime $p$, namely that $p-1$ has smaller factors. Assume $p-1 = q_1*q_2$ for $q_1, q_2$ relatively prime factors of size $\approx \sqrt{p}$. Since $x^{p-1}\mod p = 1$ for any $x$, $(x^{q_1})^{q_2}\mod p = 1$ for any $x$. That is, if we only look at elements with are $q_1$-powers of something, they have order $q_2$. An analogous thing happens if we switch $q_1$ and $q_2$. 

We use this to recover $a\mod q_1$ and $a\mod q_2$, from which we can use the Chinese Remainder Theorem (which you learned earlier) to recover $a$.
\begin{enumerate}
\item Find the discrete logarithm of $A^{q_1}$ with respect to $g^{q_1}$ using one of the algorithms above, i.e. $a_2$ such that $g^{a_2*q_1} = A^{q_1}$. This implies that $a_2*q_1 \equiv a*q_1\mod q-1$, i.e. $a_2\equiv a\mod q_2$.
\item Find the discrete logarithm of $A^{q_2}$ with respect to $g^{q_2}$ using one of the algorithms above, i.e. $a_1$ such that $g^{a_1*q_2} = A^{q_2}$. This implies that $a_1*q_2 \equiv a*q_2\mod q-1$, i.e. $a_1\equiv a\mod q_1$.
\item Compute $a = CRT(a_1, a_2, q_1, q_2)$.
\end{enumerate}

# Let's find a particularly nice p of the appropriate form
q_1 = previous_prime(2**32)
for q_2 in range(2**32-1000, 2**32):
    p = q_1*q_2+1
    if is_prime(p): break
print "p = ", p
print "p-1 = ", factor(p-1)

p = 18446739937656050359 p-1 = 2 * 3^2 * 13^2 * 1411889 * 4294967291

Fp = GF(p)
g = Fp.multiplicative_generator()

# Make Alice's public key as usual
A = g^(randint(1,p-1))

def crt_attack(g, A, q_1, q_2):
    a_2 = bsgs(g^q_1, A^q_1)
    a_1 = bsgs(g^q_2, A^q_2)
    return crt(a_1, a_2, q_1, q_2)

%time
print A, g^crt_attack(g, A, q_1, q_2)

4541974040081333206 4541974040081333206 CPU time: 0.54 s, Wall time: 0.53 s

%latex
\noindent Now, it turns out that the Chinese remainder theorem actually works with any number of relatively prime moduli, i.e. we can work with all the factors of $p-1$ independently. In particular, no matter how large $p$ is, if $p-1$ can be factored into small values, we can use this technique to quickly attack the discrete logarithm problem modulo $p$.