Bill Buchanan - The Bluffers Guide to Discrete Logarithms

Preface We should all have a magic switch that pushes aside our worries and replaces them with something that takes our woes away. So, when I’ve had a long and tiring day, and there are things buzzing in my head — I don’t count sheep, I ponder the wonder of discrete logarithms, and in the magical ways they have solved our many online security. It relaxes me and pushes out all of those academic stresses. This academic year, we were so lucky to speak to some of the people who properly built the foundations of our online security. This included Marty Hellman (co-inventor of the Diffie-Hellman method), Tahir ElGamal (inventor of the ElGamal encryption method), and Neal Koblitz (co-inventor of Elliptic Curve Cryptography — ECC). In this article, I will trace the roots of this security, and outline how discrete logs paved the way for the rise of ECC. So, if we go back to school, you will remember that: g^x . g^y is equal to: g^{x+y} and that: {g^x}^y is: g^{x.y} That’s the beauty of logarithms. Introduction Our online world is secured with discrete logs. While we have moved away from discrete logs for key exchange (Diffie-Hellman), encryption (ElGamal) and digital signatures (DSA), at the core of the security of elliptic curves is the Elliptic Curve Discrete Logarithm Problem (ECDLP): Can we find n such that Q = nP? and where P and Q are points on an elliptic curve, and where we have a finite field defined by a prime number. The curve itself can be the form of: y²=x³+ax+b (mod p) The (mod p) part defines a finite field, and which basically constrains the values of x and y to between 0 and p-1. But, I’d like to look back at a time before elliptic curves and see where we started with this: the discrete log. Basically, discrete logs built the security of the Internet, and without them, we would have struggled to advance from a digital world that used physical cables and padlocks to secure itself.