The Bluffers Guide to Discrete Logarithms, And How They Protected and Changed Our World
The Bluffers Guide to Discrete Logarithms, And How They Protected and Changed Our World
Strap yourself in, we are going to go on a wonderful journey of discovery.
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.
Diffie-Hellman (DH) key exchange
One of the highlights of my academic year was the opportunity to chat with Marty Hellman — the co-inventor of the Diffie-Hellman key exchange method. In 1976, he and Whit Diffie wrote one of the greatest research papers ever in Computer Science:
And, when they said it was a new direction, it was basically the start of proper online security. Up to that point, we had been using symmetric key encryption to secure things. While the DES method was crumbling a little with its smallish key size (only 56 bits), its main problem was that the encryption key used had to be passed from the sender (Bob) to the receiver (Alice). This meant that Bob and Alice needs the same encryption key to secure the data. But, how could we pass it, especially when Eve was listening to everything that they sent? How do we know if Eve has a copy of the key? The answer was beautiful, and was based on the wonders of discrete logarithms:
With discrete logs, we start with the base of the logarithms (g) — or the generator value. Both Bob and Alice (and Eve) know g, and there’s nothing secret about it. We also need to finite field in order to limit our values, as the values of g^x are going to get very large as we increase our value of x. The (mod p) operation comes to our rescue and allows for the mathematical operations to still act in the way we would expect.
With the DH method, Bob creates a random value (b) and Alice also creates a random value (a). Next Bob computes B=g^b (mod p) and sends it to Alice. Alice computes A=g^a(mod p) and sends this to Bob. Bob raises the value of A to the power of b and takes (mod p), and Alice raises B to the power of a and takes (mod p). In the end, they will have the same shared value: g^{ab} (mod p). This can then be used to derive an encryption key that they can use for a secure tunnel. Overall, p is the large prime number, and also known as the shared modulus between Bob and Alice.
And, so, here is the method defined in the minimum number of Sharpies possible:
And, their beauty here:
Now encryption
The RSA encryption method followed the invention of the DH key exchange method, and for the first time — in 1997 — we had the opportunity to encrypt with Alice’s public key, and then decrypt with her private key:
With public key encryption (PKE), Alice generates a key pair: a public key and a private key. If Bob wants to send her a secret message, he takes the message (M) and encrypts it with her public key (pk), to create a cipher (C). Alice decrypts this with her private key (sk).
But, how can we trust Alice’s public key surely? Surely Eve could pass a fake version of the key to Bob? Well, this is where Trent comes in, and verifies that Alice’s public key is correct.
But, RSA is not a discrete logarithm problem, as it uses the message value M to the power of a public exponent. For a discrete log approach to public key encryption, we turn to Tahir ElGamal. In 1985 he published this paper [here]:
It was a true classic and has been referenced over 11,400 times. Within the paper, Tahir outlined encryption methods and a digital signature method. His ‘base’ was to take John Napier’s logarithm and make them discrete. This discrete element meant that we only dealt with positive integer values and where we worked within a finite field. This field was defined by a prime number (p).
Initially, Alice creates her public key by selecting a g value and a prime number (p) and then selecting a private key (x). She then computes Y which is:
Y=g^x (mod p)
Her public key is (Y,g,p) and he will send this to Bob. Bob then creates a message (M) and selects a random value (k). He then computes a and b:
a=g^k (mod p)
b=y^k.M (mod p)
Bob then receives these (a and b), and then uses his private key (x) to decrypt the values and discover the message:
M=b/{a^x} (mod p)
Again, here is the ElGamal method defined using Sharpies:
And if you are interested, here are more details on ElGamal encryption:
https://asecuritysite.com/elgamal/
It’s all about Kravitz
And, so, we now have a basic tool kit of an encryption method and a key exchange method. What about digitally signing things?
The Digital Signature Algorithm (DSA) is a standard defined in Federal Information Processing Standard (as FIPS 186) for digital signatures and is based on discrete logarithms. It was outlined by NIST in 1991, and proposed within the Digital Signature Standard (DSS). This was then standardized with FIPS 186 in 1994, and FIPS 186–4 in 2013. Within FIPS 186–5, it is defined that DSA should not be used for the generation of signatures but can be used for signature verification. Although DSA has a patent (Patent 5,231,668 by David W. Kravitz, who had previously worked for the NSA), NIST published the standard as royalty-free:
So, what does a digital signature look like? Well, it often has an r value and an s value: (r,s). So, let’s look at the DSA (Digital Signature Algorithm) signature. For this, Figure 1 shows an outline of the setup of the DSA signature, and where Bob uses his private key (sk) to sign a hash of a message, and Alice proves with his public key (pk,g,p,q). We also use a random nonce value (k) for the signature, and we must take care that we do not reuse the value.
As with most public key signing methods, in DSA, we take a hash of a message — H(M) — and then apply a private key to create a signature (r,s). This is done by creating a random value (k) to produce the signature. The signature is then verified using the associated public key. This then verifies the creator of the signature and that the message has not been changed.
Initially, Bob creates two prime numbers (p and q) and generates a generator value of g. Next, he generates his secret key (x) and then computes his public key:
To create a signature for a message (M), he creates a random value (k) and then computes two values for the signature:
When Alice receives this signature, she takes Bob’s public key (p,q,g,Y) and the message and computes:
She then checks that v is equal to r. If so, the signature checks out. This works because:
DSA method using discrete logarithms is implemented here:
Conclusions
And, so, those are the foundations that laid the security of the Internet. Some governments and law enforcement agencies of the world may wish that these methods had never seen the light of day. But, they have allowed us to thrive, and avoid spying eyes and an untrusted Internet. So, trust Napier’s logs to secure your digital world.
Come up, though, is the greatest threat to the security and trust of the Internet: Quantum Computers … but that’s more for sleepness nights than for getting to sleep.
So, off to have a snooze, and dream about some logarithms. Zzzz.