\(\def\FF{\mathbb{F}} \def\PP{\mathbb{P}} \def\bk#1{\lvert#1\rangle} \def\abs#1{\lvert#1\rvert} \def\Enc{\mathrm{Enc}} \def\Dec{\mathrm{Dec}} \def\Sig{\mathrm{Sig}} \def\Ver{\mathrm{Ver}}\)

40 years of secret key exchange

by Luca De Feo

Rentrée des Masters Jacques Hadamard

September 8-9, 2016. Paris Saclay.

The beginnings of public key cryptography

Cryptography, helping lovers since 2000 BC

O Romeo, Romeo! wherefore art thou Romeo? Deny thy father and refuse thy name; Or, if thou wilt not, be but sworn my love, And I’ll no longer be a Capulet.

Confidentiality: Has Tybalt seen the message?

Authenticity: Is the message really from Juliet?

Integrity: Is the message exactly what Juliet meant to send?

…and: Secret sharing, homomorphic encryption, multiparty computation, plausible deniability, anonimity, proofs of knowledge, proofs of work, …

Secret key (symmetric) cryptography

Romeo and Juliet have met in the Capulet’s orchard. Upon falling in love, they have agreed on a secret key S.

It was the nightingale, and not the lark, That pierced the fearful hollow of thine ear;                           ↓ S   Lw#zdv#wkh#qljkwlqjdoh#dqg#qrw#wkh#odun# Wkdw#slhufhg#wkh#ihduixo#kroorz#ri#wklqh#hdu                           ↓ S-1   It was the nightingale and not the lark That pierced the fearful hollow of thine ear

The birth of public key (asymmetric) cryptography

The modern day Romeo and Juliet have only met on Tinder. They want to share their most intimate secrets in a confidential way, but the Internet is fraught with pirates, hackers, governments, and tech-savvy Italian moms wanting to spy on their messages.

Can Romeo and Juliet establish a common secret by chatting on a public channel without having ever met before in person?

1976: New directions in cryptography

Our modern day Romeo and Juliet: W. Diffie and M. Hellman

We stand today on the brink of a revolution in cryptography. The development of cheap digital hardware has freed it from the design limitations of mechanical computing and brought the cost of high grade cryptographic devices down to where they can be used in such commercial applications as remote cash dispensers and computer terminals. In turn, such applications create a need for new types of cryptographic systems which minimize the necessity of secure key distribution channels and supply the equivalent of a written signature. At the same time, theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science.

The Diffie-Hellman key exchange protocol (abstract version)

Let \(G\) be a finite cyclic group, noted multiplicatively, generated by an element \(g∈G\).

Romeo   Juliet
Picks \(0<a<N\) at random;   Picks \(0<b<N\) at random;
Computes \(A = g^a\);   Computes \(B = g^b\);
  \(—A→\)  
  \(←B—\)  
Computes \(S = B^a = g^{ba}\)   Computes \(S = A^b = g^{ab}\)

Ok, \(S\) is a common something. But is it a secret?

Lady Capulet is spying on Romeo and Juliet’s conversation:

How can she recover \(S\)?

Let’s see an example with \(G=ℤ/Nℤ\).

Hard problems

Let \(G\) be a cyclic group of order \(N\).

Discrete logarithm

Let \(g,A∈G\), the discrete logarithm \(\log_g A\) is the unique integer \(0≤a<N\) such that \(g^a=A\).

Discrete logarithm problem (DLP)
Given \(g,A∈G\), find \(\log_g A\).
Computational Diffie-Hellman problem (CDH)
Given \(g,A,B∈G\), find \(S\) such that \(S = A^{\log_g B} = B^{\log_g A} = g^{(\log_g A)(\log_g B)}\).

Security reductions

Obviously: CDH → DLP (if you can solve DLP, you can solve CDH);

Conjectured: DLP → CDH.

Computational security

We cannot hope discrete logarithm to be unsolvable for any group. But we can hope it to take VERY LOOONG to solve.

Cost of secret generation

Square-and-multiply exponentiation algorithm:

\[a ↦ g^a = (\underbrace{g^{⎣a/2⎦}}_{\text{recursive call}})^2 · g^{a\bmod 2}\]
  • \(⎡\log_2 N⎤\) recursive calls;
  • one or two group operations at each call.

Total cost: \(O(\log N)\) group operations.

We say that DLP (or CDH) is hard in \(G\) if no algorithm solves it in polynomial time in \(\log N\).

And if you know a little about complexity theory:

… But we can still conjecture that DLP is hard for some groups…

The classical Diffie-Helman protocol

Let \(q\) be a prime, the modular integers \(ℤ/qℤ\) form a finite field, also written \(\FF_q\).

Denote by \(\FF_q^*\) the multiplicative group of units of \(\FF_q\).

That is all elements of \(\FF_q\), except \(0\), with group operation given by multiplication.

If \(q-1\) has a large prime factor, the DLP in \(\FF_q^*\) seems to be hard!

An example.

Capulet in the middle

It is easy to prove that if CDH is hard, then the Diffie-Hellman key exchange is secure against passive adversaries.

However, if Lady Capulet can intercept messages on Tinder and manipulate them…

Romeo   Lady Capulet   Juliet
Picks \(0<a<N\) at random;   Picks \(0<c<N\) at random;   Picks \(0<b<N\) at random;
Computes \(A = g^a\);   Computes \(C = g^c\);   Computes \(B = g^b\);
  \(—A→\)   \(—C→\)  
  \(←C—\)   \(←B—\)  
Computes \(S = C^a = g^{ca}\)   Computes \(S = A^c = g^{ac}\)    
    Computes \(S' = B^c = g^{bc}\)   Computes \(S' = C^b = g^{cb}\)
  \(⇐S⇒\)   \(⇐S'⇒\)  

Public key encryption

Instead of an ephemeral key, Juliet has a long term secret key anyone can use to send her private message.

Public key encryption system

Key pair
A pair \((K_p, K_s)\) (public key, secret key),
\(K_p\) is publicly known (published on Juliet’s Tinder profile).
Encryption algorithm \(\Enc(K_p, m)\)
Inputs: public key \(K_p\) and a message \(m\);
Output: a cyphertext \(c\).
Decryption algorithm \(\Dec(K_s, m)\)
Inputs: secret key \(K_s\) and a cyphertext \(c=\Enc(K_p, m)\);
Output: the message \(m\).

Security properties:

First ever encryption protocol: RSA (Rivest, Shamir, Adleman 1977)

From Diffie-Hellman to PK encryption: the El Gamal protocol (1985)

Parameters
Keys

Encryption

Input: Public key \(K_p\), a message \(m∈\FF_q^*\);

  1. Pick random \(0≤b<q-1\);
  2. Compute \(c_1 = g^b\);
  3. Compute \(s = (K_p)^b\) (shared secret);
  4. Compute \(c_2 = m·s\);

Output: The cyphertext \((c_1, c_2)\).

Decryption

Input: Secret key \(a\), a cyphertext \((c_1,c_2)∈\FF_q^* × \FF_q^*\);

  1. Compute \(s = c_1^a\) (shared secret);
  2. Compute \(m = c_2 · s^{-1}\);

Output: The message \(m\).

CDH hard ⇒ El Gamal is secure

Signatures

But how does Juliet know that the message is really from Romeo?

Public key signature system

Key pair
A pair \((K_p, K_s)\) (public key, secret key),
\(K_p\) is publicly known (published on Romeo’s Tinder profile).
Signature algorithm \(\Sig(K_s, m)\)
Inputs: secret key \(K_s\) and a message \(m\);
Output: a signature \(s\).
Verification algorithm \(\Ver(K_p, m, s)\)
Inputs: public key \(K_p\), a message \(m\), a signature \(s\);
Output: OK if \(s = \Sig(K_s, m)\), FAIL otherwise.

Security property:

Signatures are hard:

Schnorr signatures

Parameters
Keys

Signature

Input: Secret key \(a\), a message \(m∈\{0,1\}^*\);

  1. Pick random \(0≤b<q-1\);
  2. Compute \(r = g^b\);
  3. Compute \(e = H(m \| r)\);
  4. Compute \(s = b - a·e\);

Output: The signature \((s, e)\).

Verification

Input: Public key \(K_p\), a message \(m\), a signature \((s, e)\);

  1. Compute \(r = (K_p)^e · g^s\);
  2. Compute \(e' = H(m \| r)\);

Output: OK if \(e = e'\), FAIL otherwise.

Final remarks

Modern day key exchange

Generic attacks on DLP

Let \(G\) be a cyclic group of order \(N\), let \(g\) be a generator.

DLP: Given \(h = g^a\), find \(a\).

Baby-step/giant-step, Pollard Rho

Idea: look for collisions of the form

\[g^x = h^y,\]

then \(a = x/y \mod N\).

Pohlig-Hellman

Suppose \(N = p_1·p_2 \cdots p_n\), by the Chinese remainder theorem

\[G ≃ ℤ/Nℤ = ℤ/p_1ℤ × ℤ/p_2ℤ × \cdots x ℤ/p_nℤ,\]

Complexity: \(O(\sqrt{p})\), where \(p\) is the largest factor of \(N\).

Sub-exponential algorithms for finite fields

\[L_N(α,c) = \exp(c\log(N)^α · \log\log(N)^{1-α})\]
Index calculus

Smooth element

We say that an integer is \(B\)-smooth if it is the product of primes \(<B\).

General index calculus

Input: \(g,h∈\FF_q^*\), Output: \(\log_g(h)\).

  1. Choose a smoothness basis \(\mathcal{B} = \{x\;\vert\; x<B\}\);
  2. Choose a field generator \(b∈B\);

  3. Compute the discrete logs base \(b\) of all elements of \(\mathcal{B}\):

    • Collect enough relations of the form

      \[\prod (b_i)^{e_i} = 1;\]

    • Put them in a matrix, use linear algebra to find each discrete log;

  4. Rewrite \(g\) and \(h\) as products of elements of \(\mathcal{B}\);

Output: \(\log_g(h)\).

Index calculs variants

Secrity levels

It is usually assumed that unfeasible amounts of computation start at \(\sim 2^{80}\) elementary operations.

For good measure

Security level Ideal DLP over \(\FF_p\) Elliptic curve DLP NSA recommendation
80 160 1024 160  
96 192 1536 192  
112 224 2048 224  
128 256 3072 256 SECRET
192 384 7680 384 TOP SECRET
256 512 15360 512  

Key lenghts (in bits) for given security level.

Elliptic curves

Projective space

Let \(k\) be a field, the projective space \(\PP^2(k)\) is the set of all lines in \(k^3\) passing through the origin.

Equivalently, it is the set of triples

\[(X:Y:Z) ≠ (0:0:0),\]

up to the equivalence relation

\[(X:Y:Z) \sim (λX:λY:λZ).\]

Elliptic curves

An elliptic curve over a field \(k\) (of characteristic \(>3\)) is the set of projective solutions of an equation

\[E \;:\; Y^2Z = X^3 + aXZ^2 + bZ^3,\]

with \(a,b\in k\), with a distinguished point (the point at infinity \((0:1:0)\)).

Group law

The chord and tangent law

Let’s work out some examples

Hasse’s theorem

Theorem

Let \(E/k\) be an elliptic curve defined over a finite field \(k\), then the number \(\#E(k)\) of rational points of \(E\) is bounded by

\[\abs{\#E(k) - q + 1} ≤ 2\sqrt{q}.\]
Bonus
ECDLP

Key exchange in a post-quantum world

History of computers

  Computer science Physics
1642 Blaise Pascal’s mechanical calculator  
1687   Isaac Newton’s Philosophiæ Naturalis Principia Mathematica
1821   André Ampère’s theory of electrodynamics
1822 Charles Babbage’s difference engine  
1837 Charles Babbage’s analytical engine  
1842 Ada Lovelace writes the first computer program  
1854   Lord Kelvin’s On the Dynamical Theory of Heat
1871   Maxwell’s and Clausius statistical thermodynamics
1873   James C. Maxwell’s Treatise on Electricity and Magneitsm
1900   Max Planck’s black body radiation law
1905   Albert Einstein’s special relativity
1911   Niels Bohr’s atomic model
1912   Henri Poincaré Sur la théorie des quanta
1916   Albert Einstein’s general relativity
1926   Erwin Schrödinger’s equation.
1927   Werner Heisenberg’s uncertainity principle
1935   Einstein-Podolsky-Rosen quantum entanglement (spooky action at a distance)
1939 Konrad Zuse’s electromechanical computers  
1943 Max Newman’s Colossus  
1946 ENIAC  
1947 Transistors  
1952 Integrated circuits  
1964   John S. Bell’s inequalties
1980   Quantum computing (Yuri Manin, Richard Feynman, …)
1994   Peter Shor’s factoring algorithm
2??? First quantum computer  

Quantum computing

Classical computers
Quantum computers

Quantum cats

Qubit

Mathematically
Phisically

Entanglement

Two or more qubits can become entangled, also called a superposition state.

Mathematically

Spooky action at a distance (EPR)

  • Entanglement can be carried over long distances;
  • Tested experimentally over hundreds of km;
  • …very hard to maintain for a long time even locally, though.

Quantum circuits

Quantum gates
Quantum circuits

The most dangerous quantum circuit ever

Quantum Fourier transform (QFT)

Peter Shor’s period-finding algorithm

RSA is dead. Diffie-Hellman is dead

Or is it?

Post-quantum cryptography

Slides at http://defeo.lu/talks/yacc-27-09-12.pdf

References

  1. W. Diffie, M. Hellman, New Directions in Cryptography. IEEE transactions on Information Theory, 1976.

  2. R.L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems Communications of the ACM, 1978.

  3. T. El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms. Advances in cryptology, 1984.

  4. C.P. Schnorr, Efficient signature generation by smart cards. Journal of cryptology, 1991.

  5. A. Joux, Algorithmic cryptanalysis. CRC Press, 2009.

  6. R. Barbulescu, P. Gaudry, A. Joux, E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. EuroCrypt, 2014.

  7. S. Galbraith, Mathematics of Public Key Cryptography. Cambridge University Press, 2012.

  8. M.A. Nielsen, I.L. Chuang, Quantum Computation and Quantum Information. 10th Anniversary Edition. Cambridge University Press, 2011.

  9. A. Rostovtsev, A. Stolbunov, Public-Key Cryptosystem Based on Isogenies. IACR Cryptology ePrint Archive, 2006.

  10. D. Jao, L. De Feo, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies International Workshop on Post-Quantum Cryptography, 2011.

  11. L. De Feo, D. Jao, J. Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Journal of Mathematical Cryptology, 2014.

Fork me on GitHub