Math details of public key cryptography

This article is an annex explaining the mathematical details of public key cryptography. I’ll recommend you read also the main article first: Quantum will not kill the crypto star.

Diffie-Hellman ?‍?

Back in 1978 Whitfield Diffie and Martin Hellman came to find a secure way for Alice and Bob to agree on a secret key. It works this way:

Alice and Bob agree (without the need to make it over a secure channel) on a large prime p and a base number, also known as generator, g<p.

Alice creates her key pair by choosing some random number a<p and calculating

A becomes Alice’s public key. a becomes Alice’s private key.

Note that all operations are done mod p. This means “modulo p”. The modulo operation gives as result the remainder of dividing a number by another. For instance,

7 mod 7 = 0 (7 divides 7 with no remainder)
8 mod 7 = 1 (8 divided by 7 has a remainder of 1)
9 mod 7 = 2 (9 divided by 7 has a remainder of 2)

You use the modulo operation when converting hours in 24h format to pm format: 20:00 = 20 mod 12 = 8pm

Bob creates his key pair by choosing some random number b < p and calculating

B becomes Bob’s public key. b becomes Bob’s private key

Alice publicly sends A to Bob and Bob sends B to Alice.
Alice calculates their shared secret as

Bob calculates their shared secret as

since

and

we have that

From here they can securely derive a secret key from S.

Why is this secure? ?

Eve only knows A and B, but to find S she would need to calculate a or b. However, anyone (including Alice and Bob) would need to execute a discrete logarithm operation in order to get any private key but their own, because

Calculating the discrete logarithm is a hard problem when the numbers involved are large.

Diffie-Hellman is key agreement protocol based on the discrete logarithm problem.

RSA ?

Building on the idea of public key, Ron Rivest, Adi Shamir and Len Adleman where able to find a mechanism that would allow both encryption and signature, as explained before. It goes like this:

Key Creation ?

Alice creates a key pair by choosing two large primes p, q and multiplies them to obtain the RSA modulus, n.

Alice randomly chooses a number d < (p-1)(q-1), that is relatively prime with (p-1)(q-1), that is: the only common factor between d and (p-1)(q-1) is 1.
She calculates e as the inverse of d modulo (p-1)(q-1). So we have that,

This election will make that

(You can find a demonstration in Chapter VI of the original RSA paper)
So x can be recovered from its exponentiation to the power of e or d since

and

Alice publishes (e,n) as her public key while retaining (d,n) as her private key.

Encryption ⛓

Say Bob wants to send a private message M to Alice while Eve is eavesdropping on their communication channel.

Bob encrypts M using Alice’s public key (e,n) to obtain a cyphertext C

Bob sends C to Alice
Alice decrypts C by exponentiating it to the power of her private key, d

Signature ?

Say Alice wants to sign a message M.

Alice encrypts M using her private key to obtain a cyphertext S

Alice sends (M,S) to Bob. She could encrypt it before using Bob’s public key if she wanted the conversation to remain private, but we’ll skip that.
Bob decrypts S using Alice’s public key to obtain M’

Bob verifies that M’=M. That encryption could only be made by Alice using her private key.

Somebody might argue that there is no need for Alice to provide M since whatever is M’ it can be accepted as a cyphertext prepared by Alice if it is anything that makes sense.

However, I’m skipping here a few details… All this math is complex and consumes processor time. Also, encrypting messages larger than n requires some kind of cleartext splitting. In practical implementations, what Alice encrypts is a hash of her message and what Bob verifies is that the decrypted hash is equal to the hash of the cleartext provided by Alice.

I just didn’t want to introduce hashing in the explanation to simplify the process as much as possible. If you know what a hash is, you’ll probably get the idea. Otherwise, think of a hash like a fixed bit size fingerprint of a message.

Why is this secure? ?

Eve or anyone listening to the conversation would have a long and hard time to get d, Alice’s secret exponent. Their best option is to calculate d from (e,n), but the only easy way known to do that is with

So the problem is to factor ? to obtain ? y ?. Remember that ? = ??.

As explained before this is also a hard problem when the numbers are large.

RSA is a public key cryptosystem based on the factoring problem.

Elliptic curve ➰

Elliptic Curve cryptography provides methods for encryption and signature based on the discrete logarithm problem in finite fields defined by an elliptic curve, typically 256 bit long.

Elliptic curve form

A 256bit elliptic curve signing cryptosystem provides roughly the same level of security than RSA4096 and is much faster to sign and roughly as fast for signature verification.

Elliptic curve is very frequently used for signing as it is much more efficient than RSA. It is used, for instance in Bitcoin and Ethereum.

Detailed math of elliptic curve cryptography is out of the scope of this article. Just remember that this is based in the discrete logarithm problem and, hence, it can be attacked using Shor’s algorithm.

Shor’s algorithm ?

The main idea behind Shor’s algorithm is that the discrete number fields used for RSA and discrete log-based cryptosystems have a periodic behavior. So, if you can find the period associated with the key you are trying to crack you can easily (and classically) calculate the key.

Calculating periods of periodic functions is a different way to say calculating the frequencies associated to a signal. And we have the mathematical tools to do that: The Fourier transform (FT). You can think of the Fourier transform as if it was the screen of a sound equalizer, showing bar graphs indicating the frequencies our sound system is playing.

Calculating the periods associated to a large cryptographic key is also a complex task, but we have an efficient quantum algorithm to do so: The Quantum Fourier Transform (QFT).

Factoring version ?

So, let’s assume we have a quantum computer that can run the QFT for us. Only the QFT part requires a quantum computer. The rest can be done classically.

We want to factor a large RSA modulus:

Choose an arbitrary number a<N

Run QFT to get the period ω of

If you get an odd number for ω, choose another a, as you’ll have to calculate ω/2 later.

Because ω is the period of f(x), we know that

So,

Now, remember that mod N means the reminder after dividing by N. This means that

That is,

Multiple of N

is a multiple of N.

We can now get that as the factor of two terms:

This means that:

are multiples of the factors of k or N. So, let’s get the greatest common divisor between one of them, for instance the (-1) and N. Calculating the GCD of large numbers is a task that can be executed efficiently on classic computers using Euclid’s algorithm.

After calculating the GCD you can get either the solution (one of the prime factors of N) or a non-solution (trivial (1 or N) or you may have chosen a factor of k).

The chances of getting caught in an issue (odd ω or non-solution) while running the algorithm are 37.5%. So, you may need to run it a small number of times before getting the solution, but you should get a solution easily.

Discrete logarithm version ?

As before, let’s assume we have a quantum computer that can run the QFT for us. Only the QFT part requires a quantum computer. The rest can be done classically.

Before we enter, we’ll need some help from Euler here: