Diffie-Hellman - a way to create a shared secret

The Diffie-Hellman key exchange was the first ever public-key cryptosystem. We will try it out on a elliptic curve here (note: it can also be used directly in $\mathbb{F}_p^* = \{1,\ldots, p-1\}$ , as you will learn in Sandor's course).

Public key cryptography involves three ``people'':

• Person 1 - traditionally named Alice
• Person 2 - traditionally named Bob
• Person 3 - traditionally called The Adversary

1. Break up into groups of (at least) 3. Choose at least person to be Alice¹, at least one to be Bob², and one to be the Adversary. Each person should have a computer terminal open to their SIMUW SAGE notebook. Open a common SAGE worksheet that all three of you can see and use to post messages (by refreshing the page). I'll explain how to do this.

2. In this exercise Alice and Bob will agree on a secret key by sending message in full view of everybody else. Of course, what they do at there computers gets kept secret - only the messages are public (in particular, Adversary should not look at the crypto worksheets of Alice and Bob).

3. Alice: Choose a random prime $p$ and create a random elliptic curve modulo $p$ , then choose a random point on this elliptic curve.

   sage: load cong.sage # defines random_elliptic_curve command
   sage: E = random_elliptic_curve(next_prime(randrange(1000)))
   sage: print E
   Elliptic Curve defined by y^2  = x^3 + 508*x + 42 over Finite Field of size 577
   

   sage: P = E.random_element()
   sage: P
   (386 : 331 : 1)
   

   Finally, Alice has to tell everybody the random elliptic curve and the random point in such a way that Bob can define it on his computer. In the above example, just report that the prime is $47$ , that the curve is EllipticCurve([36,3]), and the point is $(5,4)$ .

4. Bob: Choose a random integer $b$ (up to about $p$ in size) and compute $bP$ and tell everyone.

   sage: b = randrange(1000); b
   549
   

   sage: b*P
   (472 : 340 : 1)
   

   Announce $(83,362)$ to the world. But keep b secret.

5. Alice: Do the same thing as Bob, but with your own integer $a$ .

   sage: a = randrange(1000); a
   779
   
   sage: a*P
   (54 : 426 : 1)
   

6. Now for the key exchange. At this point everybody should know $E$ , $P$ , $aP$ and $bP$ . Only Alice knows $a$ and only Bob knows $b$ . Alice computes $a(bP)$ and Bob computes $b(aP)$ . The Adversary, not knowing $a$ or $b$ , sits there frustrated. Meanwhile Alice and Bob have agreed on a shared secret.

   sage: b*(a*P)
   (260 : 99 : 1)
   
   sage: a*(b*P)
   (260 : 99 : 1)
   

7. Nonetheless, since the numbers are so small, the adversary can figure out $a$ . E.g.,

   Q = P
   aP = E([54, 426])
   for n in range(1,1000):
       if Q == aP:
           print n
           break
       else: 
          Q = Q + P
   

   NOTE: There are better methods than the above simplistic brute force approach. But even the better methods aren't very good.

8. Go through each of the above steps, but with a much larger prime $p$ , e.g., with 40 digits (basically just change all the $1000$ 's above to $10^{40}$ 's). Note that it isn't noticeably slower. The only difference is that the Adversary's job is much harder.

Once you have a shared secret, you can use it to encrypt a message in various ways, many very complicated. A very simple way is to simply add (modulo $10$ each digit of the shared secret key to the digits of your ``message'' (which we encode as a number).