public key, private key

cryptography maths
By Pierre Feilles Published on Last update on

Here's an excellent video:

  • that gives clearly and simply the intuition of how public key - private key cryptography works using painting colors,
  • and then explains how this can be implemented for computers.


Outline of its explanations:

colors

How could Alice and Bob agree on a secret color without Eve finding it out ?

We assume:

  • it's easy to mix two colors together to make a third color.
  • given a mix of two colors and one of those two colors, it's hard to reverse it to get the other original color.

This is a one-way fonction.

alice bob eve

  • 1 : puc: public color. Alice and Bob agree publicly on a starting color. So Eve gets it too.
  • 2 : Alice randomly selects a private color: Ac, and mixes it with the public color: mix(puc, Ac). Bob randomly selects an private color: Bc, and mixes it with the public color: mix(puc, Bc).
  • 3 : Alice sends mix(puc, Ac) to Bob. Bob sends mix(puc, Bc) to Alice. These exchanges are intercepted by Eve.
  • 4 : Alice does: mix(Ac, mix(puc, Bc)). Bob does mix(Bc, mix(puc, Ac)). Assuming the mixing color operation is associative, they now both share the following color: mix(puc, Ac, Bc).

Eve cannot perform this last operation. Knowing only puc and mix(puc, Ac), she cannot reverse the mixing operation and extract Ac, Alice's private key. Same for Bc, Bob's private key.

maths

This idea can be applied to the exchange of numbers by computers: how could Alice and Bob agree on a secret random number without Eve finding it out ?

We need a one-way function similar to color mixing.

  • Given two positive numbers, a (the dividend) and n (the divisor), a modulo n (abbreviated as a mod n) is the remainder of the euclidean division of a by n. If \(\mathbf{a = q \times n + r}\), euclidian division, we note \(\mathbf{a = r \mod n}\) or \(\mathbf{a mod n = r }\)

  • Let \(\mathbf{p}\) be a prime number, e.g. : \(\mathbf{p=17}\). The number \(\mathbf{g=3}\), for example, is a primitive root of \(\mathbf{17}\) : which means that we have the following property: \(3^x = 0,...,16 \mod{17}\) in such a way that for \(x\) randomly varying, \(0,...,16\) are equally likely as an output of this operation. (Algebra: \(g\) is a generator of the finite field : \( <g> = \mathbb{F}_p $, where : $\mathbb{F}_p= \mathbb{Z}/p\mathbb{Z}\) )

  • one-way fonction: \(\mathbf{x \mapsto 3^x \pmod{17}}\)

    • $ 3^{29} \pmod{17} = 12 $ easy
    • $ 12 = 3^? \pmod{17} $ hard, discrete logarithm problem.

Let's draw the same diagram as the one illustrating the color exchanges:

alice bob eve maths

  • 1 : Alice and Bob agree publicly on a couple \(\mathbf{(g=3, p=17)}\). This is the public key. Eve gets it too.
  • 2 : Alice selects a private random number (private key), e.g. \(\mathbf{15}\), and computes: \(\mathbf{3^{15} \pmod{17} = 6}\). Bob selects a private random number, e.g. \(\mathbf{13}\), and computes: \(\mathbf{3^{13} \pmod{17} = 12}\).
  • 3 : Alice sends \(\mathbf{6}\) to Bob. Bob sends \(\mathbf{12}\) to Alice. These exchanges are intercepted by Eve.
  • 4 : Alice computes: \(\mathbf{12^{15} \pmod{17} = 10}\). Bob computes: \(\mathbf{6^{13} \pmod{17} = 10}\). They now both share a number, \(\mathbf{10}\), that Eve can't compute, even though she could intercept all messages.

This works because:

  • on Alice's side: \(12^{15} \pmod{17} = {(3^{13} \pmod{17})}^{15} \pmod{17} = {(3^{13})}^{15} \pmod{17}\)
  • on Bob's side: \(6^{13} \pmod{17} = {(3^{15} \pmod{17})}^{13} \pmod{17} = {(3^{15})}^{13} \pmod{17}\)
  • and : \(\mathbf{ {(3^{15})}^{13} = 3^{15 \times 13} = {(3^{13})}^{15} }\)
  • Exactly like we had : mix(Ac, mix(puc, Bc)) = mix(Bc, mix(puc, Ac)) = mix(puc, Ac, Bc) in the illustration with painting colors.

Eve cannot perform this last operation:

  • to compute Alice's private key she'd have to solve: \(\mathbf{3^{?} \pmod{17} = 6}\)
  • or to compute Bob's private key she'd have to solve: \(\mathbf{3^{?} \pmod{17} = 12}\)

Both are instances of the same discrete logarithm problem, namely calculating the inverse function of the initial one-way function \(\mathbf{x \mapsto 3^x \pmod{17}}\). Eve can't do it just like knowing only puc and mix(puc, Ac), she could not inverse the mixing operation and extract Ac, Alice's private key, or similarly could not extract Bc, Bob's private key.

biblio

Comments

comments powered by Disqus