On raconte que le besoin de créer des codes secrets remonte à Jules César, qui décalait de trois rangs dans l’ alphabet les lettres de ses messages. C’ est l’ encodage. Comment pourriez-vous décoder un tel message?
La cryptographie moderne, qui est l’ art d’ encoder et décoder des messages, a bénéficié d’ un regain d’ intérêt avec le transfert informatique de données, et a gardé son importance traditionnelle dans les opérations militaires. Elle utilise une clé publique, qui n’ oblige pas ses utilisateurs à partager une clé qui rendrait les messages codés susceptibles d’ être attaqués.
La théorie des nombres traditionnelle a produit quantité de méthodes de codage sécurisées, mais « sécurisée » est un terme relatif. Les méthodes modernes dépendent simplement de la capacité à multiplier deux nombres de grande taille et à retrouver ces facteurs étant donné leur produit.
Un peu d’ histoire
L’ histoire de la cryptographie a commencé il y a des milliers d’ années. Jusqu’ à il y a quelques décennies, il s’ agissait de l’ histoire de ce que l’ on pourrait appeler la cryptographie classique, c’ est-à-dire des méthodes de codage utilisant uniquement du papier et un stylo, ou peut être une aide mécanique simple.
Les premiers procédés étaient des procédés de substitution. Il s’ agit d’ une méthode de codage remplaçant les unités du message original par un code selon un système régulier; les “unités” peuvent être simplement des lettres, des paires de lettres, des triplets de lettres et ainsi de suite. Le destinataire décode le texte en procédant à la substitution inverse. Il y a de nombreux procédés de substitution. Si le procédé agit sur une lettre à la fois, on dit qu’ il s’ agit d’ un procédé de substitution simple; un procédé qui agit sur un plus grand groupe de lettre est appelé polygraphique.
Jules César aurait encodé des messages en décalant chaque lettre de trois rangs dans l’ alphabet. Par exemple, ARRIVEE VENDREDI devient DUULYHH YHQGUHGL. La substitution inverse consiste simplement à décaler les lettres de trois rangs dans l’ alphabet dans l’ autre sens. Si l’ encodage est symbolisé par 
et le décodage par 
, alors (VENDREDI) = YHQGUHGL et (YHQGUHGL) = VENDREDI. On peut écrire 
. Regrouper les lettres déguise un peu le message: écrire le message ARR IVE EVE NDR EDI, de sorte que (ARR) = DUU, et ainsi de suite.
Cette approche peut être sérieusement améliorée en utilisant le chiffre de Vigenère (modifié). Choisissez un nombre à trois chiffres, comme 427, et décalez les lettres de chaque groupe de 4 rangs, puis 2 rangs, et 7 rangs, dans l’ alphabet. On obtient (ARR IVE) = ETY MXL. Casser ce code équivaut à trouver la clé 427. Lorsque la clé est aussi longue que le message original, et est utilisée une seule fois, le code est considéré comme inviolable; dans ce cas ce procédé est appelé masque jetable.
Au début du 20ème siècle, l’ invention de machines mécaniques complexes, et électromécaniques, comme la machine Enigma, a fourni des méthodes de cryptographie plus élaborées et efficaces; et par la suite le développement de l’ informatique a permis l’ utilisation de méthodes d’ encore plus grande complexité, la plupart étant absolument inutilisables à l’ aide de papier et de stylo.
La publication de l’ article “New directions in cryptography” de Whitfield Diffie et Martin Hellman en 1976 a été le développement le plus important. Il présentait une méthode totallement nouvelle de partage des clés cryptographiques, qui s’ approchait près de la solution d’ un des problèmes fondamentaux de la cryptographie, à savoir le besoin de garder secrètes des clés partagées par un certain nombre d’ utilisateurs. L’ article a déclenché le développement quasi immédiat d’ une nouvelle classe d’ algorithmes de codage et a mené à de grandes améliorations des méthodes de factorisation des grands nombres et des tests de primalité. Ces aspects de la théorie des nombres ont été vitaux à l’ échange de clés Diffie–Hellman.
Avant de décrire la plus connues de ces approches, le système RSA, nous avons besoin de développer un résultat de théorie des nombres. Il repose sur la connaissance de la formule du binôme de Newton et de l’ arithmétique modulaire.
Preuve de la formule 
(mod 
), pour des entiers premiers distincts 
, 
ne divisant pas 
Commençons avec la formule des coefficients binomiaux:
![\[\binom pi=\frac{p!}{i!(p-i)!},\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-01284215a21085fa435fba66b50f5727_l3.png "Rendered by QuickLaTeX.com")
où, pour notre utilisation, et 
sont des entiers tels que 
. Puisque
![\[i!\binom pi= p(p-1)(p-2)\cdots(p-i+1),\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-7d5c6bdf7dc7da030c0d44f883ec4152_l3.png "Rendered by QuickLaTeX.com")
il est nécessaire que soit un diviseur de 
, car divise le membre de droite de l’ égalité mais ne divise pas 
.
Ainsi, pour des entiers 
, 
, 
, d’ après la formule du binôme,
![\[(A+B)^p=A^p+\binom p1 A^{p-1}B+\binom p2 A^{p-2}B^2+\cdots+B^p\equiv A^p+B^p \pmod p,\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-ebebee04cbaec1983c1bc6213b56e720_l3.png "Rendered by QuickLaTeX.com")
donc
![\[(A+B+C)^p=((A+B)+C)^p\equiv(A+B)^p+C^p\equiv A^p+B^p+C^p \pmod p.\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-5c58a7335114d722b7e521a74a83887f_l3.png "Rendered by QuickLaTeX.com")
De sorte que, pour des entiers, 
, 
, …, 
,
![\[(A_1+A_2+\cdots+A_t)^p\equiv A_1^p+A_2^p+\cdots+A_t^p \pmod p.\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-0a8f7478949cf890e1d2de5009aae364_l3.png "Rendered by QuickLaTeX.com")
Si on choisit 
on obtient
![\[t^p\equiv t \pmod p.\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-2364c15199d188bccaff656e278d5524_l3.png "Rendered by QuickLaTeX.com")
Puisque ne divise pas , on a
![\[t^{p-1}\equiv 1 \pmod p.\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-cbc3f0fdc317f3aa6bc5f2973c8dc6fb_l3.png "Rendered by QuickLaTeX.com")
Si maintenant on élève chaque coté de cette congruence à la puissance 
:
![\[t^{(p-1)(q-1)}\equiv 1 \pmod p.\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-39a0120e560c6ac87637e6cf18902f4c_l3.png "Rendered by QuickLaTeX.com")
De même,
![\[t^{(p-1)(q-1)}\equiv 1 \pmod q.\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-793bbd36c5e02e5551441cee0cb5b5be_l3.png "Rendered by QuickLaTeX.com")
Qui signifient, respectivement, qu’ il existe des entiers 
et 
tels que
![\[t^{(p-1)(q-1)}=1+ph, \quad t^{(p-1)(q-1)}=1+qk,\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-e0880eaf885593622b19be9311334036_l3.png "Rendered by QuickLaTeX.com")
donc 
. Alors divise (puisque et sont premiers et distincts), ou 
, pour un entier 
. Ainsi nous avons 
, ou
![\[t^{(p-1)(q-1)}\equiv1 \pmod {pq},\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-c7fb4170ee2bd859f069137ef90025f5_l3.png "Rendered by QuickLaTeX.com")
comme désiré.
Le système RSA
RSA signifie Rivest, Shamir et Adleman, qui ont présenté cette méthode en 1978. voici comment ce système fonctionne.
Pour commencer choisissez deux nombres premiers, et . Calculez 
et 
. Choisissez un entier aléatoirement entre 3 et 
, mais tel que et 
n’ aient aucun facteur premier en commun. La paire 
est la clé publique, et est donnée à chacun par l’ expéditeur du message à encoder. La clé privée , que l’ envoyeur gardera secrète, est calculée par 
(mod ), c’ est-à-dire le nombre tel que 
(mod ). Ceci est aisément réalisé avec l’ algorithme d’ Euclide.
Le message à encoder est choisi comme une portion du message original transformée en un entier 
, 
.La méthode la plus simple pour cela est de remplacer chaque lettre du message par sa position numérique dans l’ alphabet: A devient 01, B devient 02, etc. Par exemple ARR devient 011818 (ce qui nécessite 
). Traditionnellement, c’ est Bob qui encode le message et l’ envoie à Alice qui le décodera. Alice a choisi et , a calculé 
et , choisi (et a publié ), et calculé . Bob encode en calculant 
(mod ),
Cette méthode fonctionne car 
, pour un entier , et
![\[x^F=x^{(p-1)(q-1)}\equiv1 \pmod N\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-910ad2a126d46de90eb17a22bb3d621a_l3.png "Rendered by QuickLaTeX.com")
(comme démontré ci-dessus), et ainsi
![\[y^D\equiv x^{DE}=x(x^F)^k\equiv x\cdot1^k=x \pmod N.\]](https://blog.kleinproject.org/wp-content/ql-cache/quicklatex.com-ac66e5a6ad63dcce0caf65276cbbe428_l3.png "Rendered by QuickLaTeX.com")
La raison pour laquelle le système RSA est si efficace repose sur le choix des entiers premiers et (par Alice). Ceux-ci doivent être aussi grands que possible, disons environ 100 chiffres chacun. Il est facile pour Alice de calculer et et la clé privée . Mais personne ne peut calculer ou parce que factoriser pour retrouver et est particulièrement difficile. Il existe des méthodes très rapides pour calculer 
(mod ) par exemple, même si , habituellement, et sont des nombres immenses. La technique est appelée exponentiation modulaire.
Comment Alice peut-elle être sûre que le message qu’ elle a reçu provient de Bob? Le système RSA permet d’ avoir des messages signés en laissant la possibilité à Bob d’ avoir ses propres clés publique et privée. Il encode un message exactement comme décrit ci-dessus en utilisant ses propres clés (de sorte que le message soit maintenant signé), et l’ encode une seconde fois en utilisant la clé publique d’ Alice et lui envoie le résultat. A son tour elle utilise sa clé privée pour retrouver le message signé et utilise alors la clé publique de Bob pour retrouver le message original. Le principe est que le message doit forcément provenir de Bob puisque il est le seul à connaître sa clé privée.
Le Message
Le message, original, est clair.