\documentclass{beamer}
%\documentclass[ignorenonframetext,handout]{beamer}
%\usepackage{pgfpages}
%\pgfpagesuselayout{2 on 1}[a4paper,border shrink=5mm]

\usetheme{JuanLesPins}
\usepackage[french]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{bortzmeyer-utils}

\title{Cryptographie post-quantique}
\author{Stéphane Bortzmeyer\\\texttt{stephane+pses@bortzmeyer.org}}
\date{Pas Sage en Seine, 29 juin 2018}

%\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex} 
%\setlength{\parskip}{15pt} 
\setlength{\parskip}{15pt plus 10pt minus 10pt} 

\begin{document}

\expandafter\def\expandafter\insertshorttitle\expandafter{%
       \insertshorttitle\hfill%
       \insertframenumber\,/\,\inserttotalframenumber}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{L'orateur}
  \begin{overlayarea}{\textwidth}{.6\textheight}
    \begin{itemize}
    \item<2->Ne connait rien en crypto.
    \item<3->Et pas grand'chose en quantique.
    \item<4->Ce qui en fait la personne idéale pour se mettre à la
      place de la majorité des gens qui vont devoir décider s'ils
      jettent RSA, ECDSA et EdDSA…
     \end{itemize}
  \end{overlayarea}  
\end{frame}

\begin{frame}
  \frametitle{Crypto classique}
    \begin{overlayarea}{\textwidth}{.6\textheight}
      \begin{itemize}
      \item<2->Toute la sécurité de l'Internet en dépend.
      \item<3->Si on casse RSA, on n'a plus de sécurité.
      \item<4->RSA repose sur le problème de la décomposition en
        facteurs premiers.
       \item<5->ECDSA et EdDSA (les courbes elliptiques) reposent sur
         le problème du logarithme discret.
       \item<6->Ne pas oublier les algorithmes de chiffrement
         symétriques (AES) et ceux de condensation (SHA).
      \end{itemize}
  \end{overlayarea}  
\end{frame}

\begin{frame}
  \frametitle{Quantique}
  \begin{overlayarea}{\textwidth}{.6\textheight}
    \begin{itemize}
      \item<2->Branche de la physique qui traite de phénomènes en
        général limités aux trucs très petits.
      \item<3->D'habitude, peu de manifestation dans le monde
        « macroscopique »\only<3>{ (mais il y en a, comme le laser)}.
      \item<4->Des prédictions hautement non-intuitives \emph{mais très bien
        vérifiées}.
      \item<5->« Si vous croyez comprendre la quantique, c'est que
        vous ne comprenez pas la quantique. »\only<5>{ (Richard
          Feynman)} « \foreign{If quantum physics sounds challenging to
            you, you are not alone.} »\only<5>{ (documentation du
            calculateur quantique d'IBM)}.
    \end{itemize}
   \end{overlayarea} 
\end{frame}

\begin{frame}
  \frametitle{La quantique amusante}
 \begin{overlayarea}{\textwidth}{.6\textheight}
   \begin{itemize}
   \item<2->Le qubit, équivalent quantique du bit.
   \item<3->0, 1 ou peut-être un peu des deux\only<3>{ (superposition)}, tant qu'on ne mesure
     pas\only<3>{ (chat de Schrödinger)}.\only<3>{ Si vous voyez 0 écrit |0>,
     c'est un qubit. a|0⟩+b|1⟩ est une superposition.}
   \item<4->Impossibilité du clonage, vous ne pouvez pas copier
     des qubits sans les mesurer\only<4>{ (et donc les réduire à des
       bits classiques)}. % No-cloning theorem
    \item<5->Intrication, dans certains cas, des qubits ont leur sort
      lié : la mesure de l'un réduit l'autre à un
      bit.\only<5>{ « Individuellement aléatoires, mais corrélés
        entre eux »} % Entanglement
    \item<6->Décohérence, quand ça cesse d'être quantique.  % Et voilà
                                % pourquoi on ne croise pas de chats
                                % de Schrödinger dans la rue.
    \item<7->Fort potentiel de pipeautage, commercial ou New Age pseudo-écolo. % Le
      % forum où un type disait que les banques avaient déjà des
      % liaisons quantiques… Ou les délires de Vandana
      % Shiva. Cf. Sokal et Bricmont « Impostures intellectuelles »
      % https://fr.wikipedia.org/wiki/Mysticisme_quantique Ou, plus
      % business, les lobbies qui cherchent du financement
      % http://qurope.eu/
      \end{itemize}
   \end{overlayarea} 
\end{frame}
    
\begin{frame}
  \frametitle{Ordinateur quantique}
  \begin{overlayarea}{\textwidth}{.6\textheight}
    \begin{itemize}
      \item<2->Un ordinateur qui utilise des concepts purement
        quantiques.
      \item<3->Première (?) idée par Richard Feynman en 1982.
      \item<4->Ce n'est pas un ordinateur général.
      \item<5->Le concept est un tel succès que certaines boîtes
        annoncent avoir des ordinateurs quantiques… qui n'en sont pas.
       \end{itemize}
   \end{overlayarea} 
\end{frame}

\begin{frame}
  \frametitle{Calculateur théorique}
  \begin{overlayarea}{\textwidth}{.6\textheight}
    \begin{itemize}
      \item<2->Ada Lovelace avait écrit des tas de programmes… pour un
        ordinateur qui n'existait pas\only<2>{ (et qui n'a jamais été
          construit)}.
      \item<3->En 1994, Shor met au point le premier
        programme utile pour un ordinateur quantique… qui n'existait pas.
      \item<4->L'algorithme de Shor permet de décomposer un nombre
        en ses facteurs premiers (et donc de casser RSA).
      \item<5->Depuis, des ordinateurs quantiques expérimentaux ont été réalisés.  
      \item<6->Le plus grand nombre décomposé par cet algorithme est
        21. % Combien de qubits, déjà ? % Avec d'autres algos, on fait
            % mieux
            % https://phys.org/news/2012-04-largest-factored-quantum-algorithm.html
      \item<7->Difficile de prévoir le rythme des progrès\only<7>{
        (pas de loi de Moore)}.  
    \end{itemize}
  \end{overlayarea}
\end{frame}

\begin{frame}
  \frametitle{Petit détour : la QKD}
\begin{overlayarea}{\textwidth}{.6\textheight}
  \begin{itemize}
  \item<2->Distribution quantique de clés.\only<2>{ (Branche de la
    cryptographie quantique.)}
   \item<3->Si un espion copie la clé, cela se voit\only<3>{
     (contrairement au numérique classique). Conséquence de
     l'intrication. « Sécurité physique et non plus algorithmique »}.
   \item<4->Permet de distribuer des clés de manière sûre.
   \item<5->\emph{Absolument rien à voir avec le calcul quantique}\only<5>{,
     et donc avec la crypto post-quantique}.
   \item<6->Le soi-disant « Internet quantique » chinois, ou le pipeau
     de Schrödinger.\only<6>{ « \foreign{allows perfectly secure,
         unhackable communication} » (Équivalent européen
       \foreign{Quantum Internet Alliance}.)} % https://motherboard.vice.com/en_us/article/xwg53k/china-is-another-step-closer-to-building-a-quantum-internet
                                              % C'est bien, la Chine,
                                              % on peut fantasmer et
                                              % raconter n'importe
                                              % quoi.
                                              % http://quantum-internet.team/
     % https://labs.ripe.net/Members/becha/introduction-to-the-quantum-internet
     % Entre autres, un ensemble de liens point-à-points ne fait pas
     % un Internet.
   \item<7->Pourquoi la QKD n'a guère d'intérêt\only<7>{ : pas
     d'authentification et, de toute façon, elle ne sécurise que le
     maillon déjà le plus solide}. % http://www.bortzmeyer.org/communication-quantique.html http://www.revue-banque.fr/management-fonctions-supports/article/cryptographie-quantique-vers-des-transmissions-num
   \end{itemize}
  \end{overlayarea}
\end{frame}

\begin{frame}
  \frametitle{Prévoir le futur}
  \begin{overlayarea}{\textwidth}{.6\textheight}
  C'est bien joli, mais comment construire un qubit ? Et N
  qubits ?\only<1>{ « \foreign{The question of when a large-scale
      quantum computer will be built is a complicated one} » (NIST)} % Actuellement,
  % c'est entre 20 et 80 qubits. https://quantumcomputingreport.com/scorecards/qubit-count/ 
  \begin{itemize}
      \item<2->Si on a un ordinateur quantique sérieux, on peut casser
        RSA, ECDSA et EdDSA\only<2>{ (\foreign{cryptapocalypse} ?)} et
        ébranler certains algorithmes symétriques.
      \item<3->Les ordinateurs quantiques existants et connus
        publiquement sont des prototypes.\only<3>{La décohérence est
          un problème sérieux.}
      \item<4->Quand est-ce que Dell nous vendra un ordinateur
        quantique ?
      \item<5->Rappel : on est plus proche de la recherche
        fondamentale que de l'ingéniérie. Difficile de prévoir les
        progrès.\only<5>{ « \foreign{Breakthrough might be imminent,
            but then again it might not.} »} % Kenny Paterson https://www.ietf.org/proceedings/99/slides/slides-99-saag-post-quantum-cryptography-00.pdf
                                % Se rappeler de la supraconductivité
                                % haute-température.
    \end{itemize}
  \end{overlayarea}
\end{frame}

\begin{frame}
  \frametitle{Écoutons ceux qui savent}
   \begin{overlayarea}{\textwidth}{.6\textheight}
     \begin{itemize}
     \item<2->En août 2015, la NSA publiait un communiqué\only<2>{
       (retiré de leur site Web depuis)} disant en substance :
       \item<3->« Si vous n'avez pas encore migré de RSA vers les
         courbes elliptiques, ce n'est pas la peine : les ordinateurs
         quantiques arriveront avant. »
       \item<4->Curieusement, certaines personnes ne font pas
         confiance à la NSA. % Ils savent, mais disent-ils la vérité ?
       \item<5->« \foreign{A Riddle Wrapped in an Enigma} » disait un
         des nombreux articles d'exégèse. % https://eprint.iacr.org/2015/1018
         \end{itemize}
  \end{overlayarea}
\end{frame}

\begin{frame}[fragile]
  \frametitle{L'algorithme de Shor en action}
  \begin{block}
    {Comme je n'ai pas d'ordinateur quantique, j'ai utilisé un
      émulateur}
    {
\begin{info}
% ./shor 42
N = 42, 31 qubits required
Random seed: 41
Measured 1024 (0.500000), fractional approximation is 1/2.
Possible period is 2.
Unable to determine factors, try again.

% ./shor 42
N = 42, 31 qubits required
Random seed: 37
Measured 682 (0.333008), fractional approximation is 345/1036.
Possible period is 1036.
42 = 2 * 21  
\end{info}
    }
  \end{block}
  % Notez le caractère probabiliste, et le fait qu'il ne décompose pas
  % jusqu'au bout. Faut recommencer :
% ./shor 21
% N = 21, 26 qubits required
% Random seed: 10
% Measured 256 (0.500000), fractional approximation is 1/2.
% Possible period is 2.
% 21 = 3 * 7

% Explication de l'algo en https://quantumexperience.ng.bluemix.net/qx/tutorial?sectionId=full-user-guide&page=004-Quantum_Algorithms~2F110-Shor%27s_algorithm
\end{frame}

\begin{frame}
  \frametitle{Émulateurs de calculateurs quantiques}
  Pour jouer en attendant.
  \begin{overlayarea}{\textwidth}{.6\textheight}
    \begin{itemize}
      \item<2->libquantum \url{http://www.libquantum.de/}.\only<2>{ Inclus un
        exemple Grover et Shor (ci-dessus).}
       % Grover (grover.c dans le source : pas génial car l'oracle est
       % en dur.  https://en.wikipedia.org/wiki/Grover%27s_algorithm
       % Permet d'inverser un hash, par exemple, en cherchant dans une
       % table
       % (implicite). https://quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/004-Quantum_Algorithms/070-Grover's_Algorithm.html
      \item<3->Quintuple \url{https://www.github.com/corbett/QuantumComputing} % Paquetage
        % Debian  python3-quintuple
      \item<4->\only<4>{Vous vous souvenez des fermes de compilation de
        SourceForge ? }Vous pouvez accéder à un vrai ordinateur
        quantique
        \url{https://quantumexperience.ng.bluemix.net/qx/experience}\only<4>{
          (cinq qubits)}. % Bonne doc
                          % https://quantumexperience.ng.bluemix.net/qx/tutorial?sectionId=beginners-guide&page=introduction
                          % (débutants)
                          % https://quantumexperience.ng.bluemix.net/qx/tutorial?sectionId=full-user-guide&page=introduction
                          % (complet).  Permet de programmer
                          % graphiquement ou en code, le code est
                          % produit par l'interface graphique, et peut
                          % tourner sur Quintuple. Les portes
                          % https://en.wikipedia.org/wiki/Quantum_logic_gate#Commonly_used_gates
                          % Utilisable via une bibliothèque
                          % https://github.com/QISKit/qiskit-core
   \item<5->Déjà beaucoup de questions sur StackOverflow.
    \end{itemize}
  \end{overlayarea}
\end{frame}

\begin{frame}
  \frametitle{Qu'est-ce qu'un algorithme post-quantique}
   \begin{overlayarea}{\textwidth}{.6\textheight}
     \begin{itemize}
     \item<2->Un algorithme de chiffrement pour lequel on ne connait
       pas \emph{actuellement} d'algorithme quantique de cassage.
     \item<3->Ce n'est pas une propriété intrinsèque : on découvrira
       peut-être un tel algo plus tard.
     \item<4->Exemples : McEliece (théorie des codes), réseaux
       euclidiens (\foreign{lattice}). % https://fr.wikipedia.org/wiki/Cryptosyst%C3%A8me_de_McEliece
        % https://en.wikipedia.org/wiki/Post-quantum_cryptography
     \item<5->Souvent des clés très longues.
     \item<6->Peu testés au feu.  
     \end{itemize}
  \end{overlayarea}
\end{frame}

\begin{frame}
  \frametitle{État du logiciel post-quantique}
   \begin{overlayarea}{\textwidth}{.6\textheight}
     \begin{itemize}
     \item<2->Rien dans OpenSSL ou GnuTLS\only<2>{ (version git)}.
               % Testé dans leurs git en 2018-06-24. Un fork OpenSSL avec du PQ
               % https://github.com/vscrypto/openssl-ringlwe (RLWE, remplace DH).
     \item<3->codecrypt \url{http://e-x-a.org/codecrypt} % Paquetage
       % Debian codecrypt
     \item<4->libbqcrypto \url{https://libpqcrypto.org/}
     \item<5->libPQP \url{https://github.com/grocid/libPQP}
       (expérimental)
     \item<6-> liboqs \url{https://openquantumsafe.org/} % OQS
       % consists of two main lines of work: liboqs, an open source C
       % library for quantum-resistant cryptographic algorithms, and
       % prototype integrations into protocols and applications,
       % including the widely used OpenSSL library.
     \item<7->Et bien d'autres\only<7>{ (par exemple les soumissions
       au NIST pour leur projet post-quantique)}.
      \end{itemize}
  \end{overlayarea}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Exemple Codecrypt}
\foreign{McEliece trapdoor running on quasi-dyadic Goppa codes}
  \begin{info}   
% ccr -g help
available algorithms: ([S]ig., [E]nc., sym. [C]ipher, [H]ash)
...
 E	MCEQCMDPC128FO-CUBE256-ARCFOUR
 E	MCEQCMDPC128FO-CUBE256-CHACHA20
 E	MCEQCMDPC128FO-CUBE256-XSYND
...

% ccr -g    MCEQCMDPC128FO-CUBE256-CHACHA20 --name pq1
Seeding done, generating the key...

% ccr -k
pubkey	MCEQCMDPC128FO-CUBE256-CHACHA20	@4d8b428e05...	pq1

% ccr -e --name pq1 --in /etc/motd --out motd.encrypted

% ccr -d --in motd.encrypted
\end{info}
\end{frame}

\begin{frame}
  \frametitle{Normes}
   \begin{overlayarea}{\textwidth}{.6\textheight}
     \begin{itemize}
     \item<2->Rien de normalisé à l'heure actuelle.\only<2>{ C'est une
       sérieuse limite pour les réseaux (pensez à TLS).}
     \item<3->NIST et autres : rien de concret pour l'instant, mais un
       projet est en cours.\only<3>{ Pas mal de soumissions dont
         Classic McEliece, NewHope…. Pas de résultat attendu avant des
         années.} % https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization
                                      % https://csrc.nist.gov/projects/post-quantum-cryptography
                                      % https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions
                                      % NewHope est membre de la
                                      % famille RLWE
                                      % https://en.wikipedia.org/wiki/Ring_learning_with_errors
                                      % un truc à réseau euclidien
     \item<4->IETF : commencez par le brouillon qui pose le problème,
       \computer{draft-hoffman-c2pq}.\only<4>{ Certains trichent en appelant
       post-quantiques des mécanismes à clé secrète pré-partagée
       \computer{draft-ietf-ipsecme-qr-ikev2}.} Également le groupe de
       recherche QIRG
       sur la QKD. % https://www.irtf.org/mailman/listinfo/qirg
     \end{itemize}
  \end{overlayarea}
\end{frame}

\begin{frame}
  \frametitle{Conclusion}
  \begin{overlayarea}{\textwidth}{.6\textheight}
    \begin{itemize}
    \item<2->La situation reste confuse et peu prédictible.
    \item<3->On ne sait pas tout\only<3>{ (la NSA a un ordinateur
      quantique installé par les extra-terrestres dans la zone 51)}.
    \item<4->Cela ressemble aux problèmes où on invoque le principe de
      précaution : décider en situation d'incertitude.
    \item<5->Mon pari : il n'y a pas urgence à se précipiter vers la
      crypto post-quantique.
    \item<6->Il faut poursuivre les recherches\only<6>{ (implémenter,
      tester et normaliser des algorithmes post-quantiques)}. % (Directeur)
      % Comment ?... S'il faut poursuivre les recherches ?... Mais
      % naturellement ! cela va de soi !... Pourquoi cette
      % question ?...  \ (Ingénieur) - Parce que, dans ce cas,
      % monsieur le directeur, il faudrait songer à installer de
      % nouveaux laboratoires...
  \item<7->Il y a une probabilité non nulle de m'être totalement trompé ici.
  \end{itemize}
  \end{overlayarea}
\end{frame}

\end{document}
