Notepad

Diffie-Hellman Key Exchange

Written by Dominik Joe Pantůček on 2019-03-21

diffie-hellman

Before Cryptoucan™, there were just elliptic curves stored in your computer. And before elliptic curves, there were exponential groups over finite fields. Read on to learn some history here.

During the last year, you have read a lot about our new cryptographic token Cryptoucan™[1] here and about the underlying cryptographic primitives based on algebra of points on elliptic curves[2] over finite fields[3]. But why did we choose such complex basis for building a cryptographic product? If we look at the Diffie-Hellman key exchange that is also used for implementing encryption in OpenPGP[4] standard or for initializing TLS[5] connection when you connect to HTTPS[6] website, it is rather simple - yet secure. In order to really appreciate, why the elliptic curve version is really needed, we must understand how the original Diffie-Hellman[7] key exchange works.

First thing we need to define is the prime finite field[8] $\mathrm{GF}(p)$. In layman's terms, finite field consists of natural numbers from $0$ to $p-1$ and if $p$ is prime number, the resulting prime finite field has certain interesting and very useful properties. To study these properties we have to define a few operations over the finite field.

All operations are defined using the $\mathrm{mod}$ (modulo) operation which calculates  the remainder of integer division. For example: $7\mod 4=3\quad\land\quad 7\div 4=1\quad\land\quad 7=1\cdot 4+3$ Now for the actual operations - we only need addition and multiplication. In an finite field $\mathrm{GF}(p)$ the addition and multiplication are defined as: $a+b:\quad a+b\mod p$ $a\cdot b:\quad a\cdot b\mod p$ With multiplication defined it is possible to define exponentiation and with exponentiation a group structure (like the one on elliptic curves[9]) emerges. As you might recall, this means we have commutativity and discrete logarithm problem. With these two, a key exchange protocol can be easily defined. Given Alice's secret number $a$ and Bob's secret number $b$, they can come up with shared secret, nobody can easily retrieve due to the following equality: $(g^a)^b=(g^b)^a$ So far everything looks good. The problem is that only some numbers from the finite field are encountered by exponentiation. Take $p=23$ and $g=3$ for example: $3^0\mod 23=1$ $3^1\mod 23=3$ $3^2\mod 23=9$ $3^3\mod 23=4$ $3^4\mod 23=12$ $3^5\mod 23=13$ $3^6\mod 23=16$ $3^7\mod 23=2$ $3^8\mod 23=6$ $3^9\mod 23=18$ $3^{10}\mod 23=8$ $3^{11}\mod 23=1$ As you can see, although we used finite field of size 23, only 11 numbers are used for the group operation and the rest is unused.

With elliptic curves, the situation is much better because if you are working with elliptic curve over a finite field $\mathrm{GF}(p)$ the number of elements used for the group operation is - with the right coefficients used - about $p$. Therefore with the same size of the finite field, we can get much bigger security parameter with elliptic curves than with just plain exponentiation of numbers.

 

Hope you liked a small venture into the history of cryptography and did not get scared by the math presented and see you next week with some Cryptoucan™ news again.

References

  1. https://trustica.cz/en/2019/02/21/cryptoucan-usage-first-look/

  2. https://trustica.cz/en/2018/02/22/introduction-to-elliptic-curves/

  3. https://trustica.cz/en/2018/03/01/elliptic-curves-over-finite-fields/

  4. https://trustica.cz/en/2018/08/30/securing-email/

  5. Wikipedia contributors. (2019, March 20). Transport Layer Security. In Wikipedia, The Free Encyclopedia. Retrieved 18:04, March 21, 2019, from https://en.wikipedia.org/w/index.php?title=Transport_Layer_Security&oldid=888677929

  6. Wikipedia contributors. (2019, March 17). HTTPS. In Wikipedia, The Free Encyclopedia. Retrieved 18:04, March 21, 2019, from https://en.wikipedia.org/w/index.php?title=HTTPS&oldid=888246701

  7. Wikipedia contributors. (2019, March 15). Diffie–Hellman key exchange. In Wikipedia, The Free Encyclopedia. Retrieved 18:05, March 21, 2019, from https://en.wikipedia.org/w/index.php?title=Diffie%E2%80%93Hellman_key_exchange&oldid=887932218

  8. Wikipedia contributors. (2019, March 11). Finite field. In Wikipedia, The Free Encyclopedia. Retrieved 18:05, March 21, 2019, from https://en.wikipedia.org/w/index.php?title=Finite_field&oldid=887219603

  9. https://trustica.cz/en/2018/04/19/elliptic-curves-scalar-multiplication2/