Public cryptography Blockchain

Math details of public key cryptography

25/08/20 9 min. read

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:

  1. 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.
  1. Alice creates her key pair by choosing some random number a<p  and calculating
  1. A becomes Alice’s public key and a becomes Alice’s private key.
    Note that all operations are done . This means “modulo ”. 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

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

becomes Bob’s public key and b becomes Bob’s private key

  1. Alice publicly sends to Bob and Bob sends to Alice
  2. 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 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 🧬

  1. Alice creates a key pair by choosing two large primes p ,q and multiplies them to obtain the RSA modulus, .
  1. 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.
  2. 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 or since

and

  1. 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 to Alice while Eve is eavesdropping on their communication channel.

  1. Bob encrypts M using Alice’s public key (e,n) to obtain a cyphertext C
  1. Bob sends C to Alice
  2. Alice decrypts C by exponentiating it to the power of her private key, d

Signature 🖋

Say Alice wants to sign a message M.

  1. Alice encrypts M using her private key to obtain a cyphertext S
  1. 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.
  2. Bob decrypts S using Alice’s public key to obtain M’
  1. 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 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 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

Multiple of N

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

This means that:

are multiples of the factors of k o N. So, let’s get the greatest common divisor between one of them. 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 (ω 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:

Set of integers mod p, excluding 0
The Euler phi function (number of elements in Z*p that are coprimers with p)

So, p is prime, because all numbers smaller than p, {1,2,…,p-1}, are coprimers with p.

Euler’s theorem states that for a y n being coprimes:

In other words:

Now, remember the components of Diffie-Hellman, which we’ll use in this example:

  • Y is the public key,
  • g is the generator and is known,
  • x is the private key we’ll try to recover,
  • p is the prime number used to define Z*p and is known.

We are ready to go with Shor.

Run QFT to get the periods ω y ω´of:

So that,

That means that,

Hence

Let´s replace Y considering that:

That would be:

Now, rememnber Euler’s theorem:

So,

and finally…

So, once you get the two periods of

you just need a division to recover the private key👍.

Thanks to María José Ruiz Félez for the illustrations! 🙌

jaime gomez

Jaime Gómez García

Santander Global Tech

Architecture and IT & Telecom Infrastructure expert. I learn about the Internet, networks and applied cryptography every day since the mid 90’s.

 

Other posts