Flux RSS

Nos partenaires

NCIES - Poitiers
Equipe Mathématiques

$logo math$
Caroline Pintoux

$logo math$
Hélène Arnaud

Etat de l'enquête
Généralités sur la cryptographie
1. Qu'est-ce que le cryptage ?
2. Historique de la cryptographie
Premières conclusions des mathématiciens
Le cryptage RSA
Décryptage des courriels par les mathématiciens

I. Etat de l'enquête

Divers témoignages ont fourni aux enquêteurs un suspect en la personne d'un jeune doctorant de l'Université de Poitiers. Celui-ci aurait eu une altercation avec feu le président de l'Université au sujet d'un poste de moniteur qu'il estimait mériter mais qui ne lui avait pas été accordé. Il travaillait également dans le bar où la victime aurait été vue pour la dernière fois. Ces éléments permettent de le placer en garde à vue, et une perquisition est autorisée à son domicile.

Afin de prouver la culpabilité du jeune homme et d'indentifier son (ou ses) complice(s), son ordinateur est fouillé et ses courriels sont analysés. On découvre alors toute une correspondance cryptée entre le doctorant et son directeur de thèse. Les mathématiciens sont chargés de décrypter ces emails.

II. Généralités sur la cryptographie

1. Qu'est-ce que le cryptage ?

Jamais le monde n'a eu autant d'informations à cacher, et à bien cacher: les secrets des comptes bancaires, le déclenchement des armes atomiques, tout doit être protégé. Si du temps de César, l'écriture elle-même représentait déjà une forme de cryptage, aujourd'hui l'analyse et l'élaboration de codes toujours plus perfectionnés sont parmi les problèmes de mathématiques les plus ardus.

Au fur et à mesure que les chercheurs élaborent des moyens de cryptage des données toujours plus sûrs, d'autres inventent des contre-mesures pour décrypter ces codes...

Faisons d'abord un petit point de vocabulaire, car les termes associés à la théorie des codes secrets et de la protection de l'information sont multiples et souvent sources de confusion:

Tout d'abord, la cryptologie, c'est la science du secret et elle englobe deux sous-domaines qui sont respectivement la cryptographie (l'écriture secrète, le fait de coder une information) et la cryptanalyse (le déchiffrage des écritures secrêtes, l'analyse des codes).
Nous employons souvent, et à tort, le mot cryptage qui est un anglicisme (vient de encryption), de même que le verbe associé de crypter. Il faudrait rigoureusement lui préférer le mot chiffrement ou encore codage mais là encore, ces deux choses différent.
Le chiffrement, c'est un procédé qui vise à rendre inintelligible un document à toute personne qui n'en possède pas la clef de chiffrement. Ce processus part d'une volonté de protéger des informations et d'empêcher l'accès à celles-ci à toute personne que ces données ne sont pas sensées concerner.
Le codage consiste à transformer de l'information vers un ensemble de mots chacun constitués de symboles (la compression est un codage, et tout code donné une table de conversion). La volonté de dissimuler n'est pas nécessairement là.
Les formes modernes de cryptologie reposent sur des algorithmes et des clefs.
Un algorithme est l'énoncé d'un ensemble logique d'actions, d'opérations, d'étapes qui se répètent de façon systématique pour résoudre un problème: on verra notamment le détail de l'algorithme d' Euclide.
Toute l'affaire de la cryptologie est d'élaborer des algorithmes efficaces et de les coupler à une clef de chiffrement, qui est un paramètre se présentant soit sous forme de mots, de phrases, de nombres ou de codes binaires. Dans ce dernier cas, il faut :
- que la clef soit suffisamment longue pour que toutes les combinaisons ne puissent être essayées dans un temps raisonnable: une clef de 128 bits contient ainsi 2¹²⁸ combinaisons... Tout ordinateur, si puissant soit-il, mettra un temps certain avant de trouver la bonne clef parmi toutes les possibilités.
- et qu'elle contienne une bonne dose de hasard: si on est un inconditionnel du chiffre 0 et qu'on choisit comme clef une suite de 128 zéros, il y a des chances pour que quelqu'un qui nous connaît bien la devine...

2. Historique de la cryptographie

Historiquement, on fait remonter l'invention des codes secrets à Jules César, mais il semble naturel de penser que dès que l'Homme a su écrire et donc transmettre des messages, il a cherché à préserver la confidentialité et l'intégrité de certains d'entre eux aux moyens de codes plus ou moins rudimentaires.

Pour une chronologie de l'apparition et de l'évolution de la cryptographie, suivez ce lien.

Vous pouvez aussi télécharger la version pdf de cet historique.

III. Premières conclusions des mathématiciens

Les messages sont formés d'une série de nombres conséquente. Les méthodes d'associations de chaque lettre de l'alphabet à un nombre puis des substitutions/transpositions (lettres remplacées par d'autres ou permutations des lettres) sont assez vite écartées: si c'était le cas, les nombres associés aux lettres les plus usitées dans les langues latines (que pratique le doctorant) telles le 'E' ou le 'A' apparaîtraient à une fréquence assez élevée. Une rapide étude statistique sur les messages ne montre rien de tel.

Un code par substitution polyalphabétique (chiffre de Vigenère ou chiffre de Hill) est également écarté: les enquêteurs s'appuient sur des calculs de probabilités. Les mathématiciens supposent alors qu'il s'agit d'un cryptage RSA, l'un des cryptages les plus connus, les plus faciles à implémenter, et également les plus sûrs. Le décryptage s'annonce délicat!

IV. Le cryptage RSA

1. Principe général

Les inventeurs du système RSA : de gauche à droite Adi Shamir, Don Rivest, et Len Adleman.

La méthode de chiffrement RSA (du nom de ses inventeurs: Rivest, Shamir et Adleman en 1976) reste un moyen plutôt sûr de communiquer des informations entre deux personnes. Pour faire simple, ce système de cryptage, dit à clef publique, fonctionne de la manière suivante: supposons qu'Andy veuille transmettre un message à Bernard:

Le receveur du message (Bernard) choisit deux grands nombres premiers p et q.
Il calcule leur produit m.
Il fixe un inversible modulo n=(p-1)×(q-1)(on verra plus tard ce que cela signifie), qu'on appelle e.
Il calcule l'inverse de e modulo n, qu'on appelle d.
les données m et e sont rendues publiques, mais seul Bernard connaît p, q et d.
Andy code son message sous forme d'une suite de nombres (via une méthode qu'on expliquera plus tard).
Bernard n'a plus qu'à faire une petite inversion mathématique pour pouvoir lire le message d'Andy. Mais attention, pour ce faire, il doit absolument connaître p et q!

Qu'entend-t-on par données publiques? Et bien par exemple, ces données (m et e), necessaires à la communication entre les deux individus, peuvent être transmises par texto, par mail, ou même affichées sur des panneaux publicitaires (donc interceptables par la police, par exemple...)!

Toute personne possédant la clef, c'est à dire les nombres m et e, peut coder un message et l'envoyer à Bernard, mais seul celui-ci peut le décoder, car pour décoder un tel message, il est nécessaire de connaître p et q.

Cette méthode de cryptage repose le fait qu'étant donné un nombre donné de grande taille (constitué de plus de 200 ou 300 chiffres), ici m, qu'on sait être le produit de deux nombres premiers (p et q), il est très difficile de retrouver les deux nombres en question, même avec une machine très performante.

Dans ce qui suit, nous expliquons en détail pourquoi il est si difficile de retrouver p et q, et quelles sont les mathématiques sur lesquelles repose RSA.

2. Nombres premiers et factorisation

Si on choisit deux entiers positifs, p et q et qu'on pose: m=pq, alors on dit que m se factorise en le produit p×q, ou que p et q sont des diviseurs de m. Ainsi:

6 = 2 × 3 77 = 7 × 11 et 6135640685170 = 1658974 × 3698455.

Un nombre premier est un nombre qui ne peut pas se factoriser, ou dont les seuls diviseurs sont lui-même et 1.

Tout le problème du décodage des systèmes de cryptage à clefs publiques repose sur la factorisation de grands nombres comme produits de nombres premiers, c'est à dire qu'on connaît le nombre m, qui s'écrit avec beaucoup de chiffres et qui est le produit de deux nombres premiers (m=p× q), et qu'on cherche à trouver ses facteurs p (et donc q).

Voici un nombre m obtenu comme produit de deux nombres premiers distincts:

m=27606985387162255149739023449107931668458716142620601169954803000803329

En utilisant une méthode "naïve", combien de temps faudrait-il à une machine effectuant 1.000.000=10⁶ opérations à la seconde pour trouver le premier diviseur (nombre premier) du nombre m? Et si la machine effectuait 10⁹ opérations à la seconde? et 10²⁰?

Le nombre m s'écrit avec 71 chiffres. Donc il est de l'ordre de 10⁷⁰ (on parle ici d'ordre de grandeur).

Pour trouver le premier diviseur premier de m, une méthode naïve consiste à calculer successivement m/2, m/3, m/5, m/7 ...etc... (on divise m par les nombres premiers successifs) jusqu'à obtenir un nombre entier.

Si on suppose que les deux nombres cherchés, p et q sont du même ordre (en taille), alors on peut estimer à environ 10³⁵ le nombre de divisions à effectuer avant de trouver le résultat.

Notre machine effectue 10⁶ opérations à la seconde, ce qui donne une durée de calcul de l'ordre de:

10³⁵/10⁶=10²⁹ secondes,

soit environ 3×10²¹ années !!!

Avec une machine effectuant 10⁹ (c'est à dire un milliard) opérations à la seconde, on obtient encore environ 3×10¹⁸ années; et si on utilise une machine effectuant 10²⁰ opérations par seconde, on tombe à 3×10⁷ années, ce qui fait encore beaucoup...!!

On se rend ici cruellement compte de l'égalité:

10^a/10^b=10^a-b

Actuellement, il n'existe pas de méthode efficace pour factoriser en un temps raisonnable un nombre de 200 chiffres décimaux.

En revanche, on peut facilement savoir si un nombre est premier ou pas (test de primalité). Par suite, il est relativement aisé, avec un ordinateur possédant un bon logiciel de calcul formel, de produire des nombres premiers p et q longs d'une centaine de chiffres, puis de calculer leur produit m=p×q. En repartant de m, le logiciel qui nous a donné p et q est incapable de les retrouver!

Si les codes secrets ont toujours fasciné, les systèmes de chiffrement sont aujourd'hui utilisés dans les transactions numériques (commerce électronique) ou dans nos portefeuilles (cartes à puces, pour le paiement, la santé etc...). Casser les codes de protection se ramène très fréquemment au problème suivant: étant donné un nombre, comment le brise-t-on (c'est à dire, comment le factorise-t-on) en ses parties élémentaires, les nombres premiers?

Dans le cadre des chiffrements modernes (comme le système RSA), les nombres s'écrivent avec 100 à 200 chiffres le plus courramment (généralement, c'est 155 chiffres, ou 512 chiffres binaires, ou bits). Les factoriser est un problème ardu sur lequel les mathématiciens se cassent les dents depuis des millénaires.

A l'époque où RSA a été inventé, factoriser des nombres de 512 bits relevait de la science-fiction. En 1999, l'inviolabilité des clefs de 512 bits a été limitée dans le temps: il n'a fallu que quelques mois et assez peu de ressources informatiques pour casser une telle clef.

Cependant, les systèmes d'aujourd'hui, utilisant des clefs de 768 ou 1024 bits restent hors d'atteinte.

Mais qui sait pour combien de temps...??

3. Mathématiques du cryptage RSA

On dispose d'une phrase que l'on veut coder sous forme numérique.Ceci se fait en deux étapes :

une première étape d'encodage, qui consiste à transformer la phrase à coder en un nombre, d'une manière qui n'est un secret pour personne,
le cryptage proprement dit, qui consiste en une opération mathématique sur le nombre obtenu précédemment.

∗ Pour encoder (ou numériser ) la phrase à coder, on utilise l'alphabet ASCII étendu de 256 caractères. A tout caractère est associé un nombre compris entre 0 et 255 (son code ASCII). A titre d'exemple, la lettre "a" correspond au nombre 97, de même "b" correspond à 98 et "c" correspond à 99. On peut ainsi coder tout caractère. Pour coder une phrase entière, on utilise la base 256. Par exemple

"abc" sera codé 97 × 256² + 98 × 256¹+ 99× 256⁰ = 6382179

Cet encodage peut se faire très simplement sur machine. Voici par exemple un petit programme Maple qui le permet :

TexteVersNombre:= proc(texte)	("texte" est le texte à encoder)
local S, i, n;	(les variables locales que l'on utilise)
S := convert (texte, bytes);	(S est une liste qui contient les codes ASCII de chaque caractère de texte)
n:=0 ;
for i from 1 to nops(S) do
n:= 256* n+S[i]; od;	(calcul du nombre associé à texte)
RETURN(n);
end:

L'opération d'encodage est complètement réversible (on dit qu'elle est bijective). Etant donné un nombre N, pour retrouver le texte auquel il correpond, on commence par le décomposer en base 256, ce qui permet de retrouver le code ASCII de chaque caractère qui compose le texte de départ, et ainsi de le retrouver.

Prenons par exemple N= 5395265. Comme 256²= 65536 < N et 256³= 16777216>N, N va s'écrire sous la forme N= ? × 256² + ? × 256¹ + ? × 256⁰. La division euclidienne de N par 256² donne que N= 82 × 256²+ 21313. De même, 21313= 256 × 83 + 65, de sorte que N= 82 × 256² + 83 × 256¹ + 65 × 256⁰. Or 82 correspond au caractère R, 83 correspond à S, et 65 à A. Le texte de départ était donc RSA.

Voici un programme Maple permettant de réaliser cette opération sur machine :

NombreVersTexte:= proc(N)
local S, n, i;	(les variables locales que l'on utilise)
S := convert (N, base, 256);	(S est une liste qui contient les coefficients de l'écriture de N en base 256)
n:=nops(S) ;	(la longueur de S)
S:=[seq(S[n+1-i], i=1..n]	(on renverse la liste pour l'avoir dans le bon ordre)
RETURN( convert (S, bytes));
end:

∗ Nous pouvons maintenant parler du cryptage proprement dit. Bernard veut recevoir des messages cryptés d'Andy. Il choisit pour cela deux nombres premiers p et q, et calcule les produits

m=pq et n=(p-1)(q-1).

Il choisit ensuite deux nombres e et d tels que

ed=1 + kn, pour un certain entier k

(on dit alors que ed est congru à 1 modulo n, ou que e est un inversible modulo n et d est son inverse).

Comment trouver e et d?

L'égalité ed=1+kn s'écrit ed-kn=1. On commence par choisir un nombre e premier avec n, c'est à dire n'ayant pas d'autre facteur commun avec n que 1 (on peut par exemple prendre e premier). Le théorème de Bezout assure alors l'existence d'un couple (u,v) d'entiers tels que eu+nv=1. Un fois qu'on aura ce couple, il ne restera plus qu'à prendre d=u. On pourra même, pour plus de simplicité dans les calculs, prendre pour d le reste de la division euclidienne de u par n (c'est à dire d=u mod(n)). En effet, la division euclidienne de u par n s'écrit u=nq+r, où q et r sont des entiers. En remplaçant n par son expression dans l'égalité eu+nv=1, on obtient e(nq+r)+nv=1, ce qui donne enq+er+nv=1, et donc er+n(eq+v)=1. On peut donc bien prendre d=r.

Mais comment obtient-on le couple (u,v)? Une méthode efficace consiste à écrire l'algorithme d'Euclide appliqué à e et n, puis à le remonter. Plus de détails à ce sujet? C'est ici!

Et ensuite ? Bernard va communiquer les nombres m et e à Andy (et au monde entier s'il veut!). Tout repose sur le résultat mathématique suivant (qui sera expliqué par la suite) :

Proposition : Avec les notations précédentes, les applications Me et Md, de $\mathbb{Z}$ / m $\mathbb{Z}$ dans lui même, définies respectivement par Me(x)=x^e mod(m) et Md(x)=x^d mod(m) sont réciproques l'une de l'autre.

Tout d'abord, qu'est ce que $\mathbb{Z}$ / m $\mathbb{Z}$ ? En fait, $\mathbb{Z}$ / m $\mathbb{Z}$ = { 0,1,...,m-1}. On désigne par x^e mod(m) le reste de la division euclidienne de x^e par m.

La compréhension de la démonstration de ce résultat donné de bonnes connaissances en algèbre. Le lecteur intéressé la trouvera ici.

Andy va commencer par encoder son message comme expliqué précédemment. Mais attention, pour les besoins du cryptage, il faudra que le nombre qu'il obtient soit strictement inférieur à m. Si ce n'est pas le cas, il lui faudra découper son message en plusieurs morceaux et encoder chacun de ces morceaux séparément, afin que le résultat soit une suite de nombres strictement inférieurs à m, c'est à dire une suite de nombres de $\mathbb{Z}$ / m $\mathbb{Z}$ .

Une fois le message à crypter encodé, si x est un nombre correspondant à une partie ou à la totalité du message, il est crypté par y = le reste de la division euclidienne de x^e par m=Me(x). On remarque que y∈ $\mathbb{Z}$ / m $\mathbb{Z}$ . Andy envoie alors ce nombre y à Bernard.

La proposition précédente fournit alors à Bernard une manière de ² ce message. En effet,d'après ce résultat, comme y=Me(x), alors x=Md(y), autrement dit x est le reste de la division euclidienne de y^d par m. Bernard n'a donc qu'à calculer Md(y) pour retrouver x, puis le message de départ.

Le décryptage du message nécessite donc la connaissance de d. Pour retrouver d à partir de e et m, il faut connaître n=(p-1)(q-1), donc p et q. On est donc ramené au problème de factorisation suivant : étant donné m un (grand!) nombre que l'on sait être le produit de deux nombres premiers p et q, peut-on retrouver ces deux nombres p et q? On a vu précédemment que c'est un problème extrèmement difficile. C'est ce qui rend le cryptage RSA sûr!

4. Bilan

Commençons par un résumé des étapes de cryptage et de décryptage :

Bernard choisit deux nombres premiers p et q, calcule m=pq et n=(p-1)(q-1), et trouve deux entiers e et d vérifiant ed=1 + kn, pour un certain entier k. Il rend ensuite publiques les nombres e et m.
Andy encode son message sous forme d'un ou plusieurs nombres. Chacun de ces nombres x est ensuite crypté par y= le reste de la division euclidienne de x^e par m.
Bernard décode le message d'Andy en retrouvant chaque x, qui est le reste de la division euclidienne de y^d par m.

Voici un exemple de cryptage et de décryptage, réalisé à l'aide du logiciel Maple :

`>`	TexteVersNombre :=proc(texte) local S, i, n; S:= convert(texte, bytes); n:=0; for i from 1 to nops(S) do n:=256*n+S[i]; od; RETURN(n); end:

`>`	NombreVersTexte := proc(n) local S, N, i; S:=convert(n, base, 256); N:= nops(S); S:=[seq(S[N+1-i], i=1..N)]; RETURN(convert(S, bytes)); end:

`>`	p:=nextprime (10^60); p est le premier nombre premier après 10^60

p := 1000000000000000000000000000000000000000000000000000000000007

`>`	q:= nextprime (10^80);

q := 100000000000000000000000000000000000000000000000000000000000000000000000000000129

`>`	*m:=pq;**

m :=	100000000000000000000000000000000000000000000000000000000000700000000000000000
	129000000000000000000000000000000000000000000000000000000000903

`>`	*n:=(p-1)(q-1);**

n :=	100000000000000000000000000000000000000000000000000000000000600000000000000000
	128000000000000000000000000000000000000000000000000000000000768

`>`	e:=13;

e := 13

`>`	igcdex(e, n, 'u', 'v'); fonction Maple qui va nous donner le pgcd de e et n, et surtout u et v

`>`	d:= u mod n;

d :=	69230769230769230769230769230769230769230769230769230769231184615384615384
	615473230769230769230769230769230769230769230769230769230769231301

`>`	texte := "mon fabuleux message secret";

texte := "mon fabuleux message secret"

`>`	x:= TexteVersNombre(texte); On encode le message secret

x := 45019060585550317006735125296455482198246147409361243967512012148

`>`	y:=x &^ e mod m; On le crypte

y :=	2873002213378533669341889984334465825293308994076929389583819827807592401
	6057040247190812655611621457319254327403685302127412746425031451964

`>`	decode := y &^ d mod m; On le décrypte

decode := 45019060585550317006735125296455482198246147409361243967512012148

`>`	NombreVersTexte(decode);

"mon fabuleux message secret"

On retrouve bien le message de départ!

V. Décryptage des courriels par les mathématiciens

Si le mode de cryptage utilisé par le suspect est bien RSA, la première chose à faire est de trouver a clef publique. Or on retrouve dans les messages envoyés par le doctorant un mail adressé à son directeur de thèse dans lequel sont inscrits deux nombres :

27606985387162255149739023449107931668458716142620601169954803000803329 et 5. Ces deux nombres ressemblent fortement à une clef publique. Si tel est le cas, le plus grand des deux nombres est certainement m et l'autre est e. Un fait rassure les mathématiciennes : m est un nombre relativement petit, et sera certainement factorisable en un temps raisonnable.

On lance donc le calcul sur machine pour tenter de factoriser m. Dans le même temps, les mathématiciens essayent de diviser m par un certain nombre de nombres premiers connus (les "nextprime" (10^k) pour k suffisamment grand, les nombres de Mersenne, etc...). A leur grande surprise, m se trouve être divisible par le nombre de Mersenne

p=2¹⁰⁷-1= 162259276829213363391578010288127. On trouve alors que q= 170141183460469231731687303715884105727=2¹²⁷-1 (autre nombre de Mersenne).

On calcule ainsi

n=(p-1)(q-1)= 27606985387162255149739023449107761527112996396559656119259509106409476, puis, à l'aide de Maple :

`>`	igcdex(5, n, 'u', 'v');

$1$

`>`	d:=u mod n;

$d := 22085588309729804119791218759286209221690397117247724895407607285127581$

Les enquêteurs sont maintenant en mesure de décoder la correspondance cryptée du suspect!

Remarque : Le doctorant suspect a été très imprudent dans le choix de ses nombres premiers! Le cryptage RSA est sûr à condition de bien choisir ces nombres sur lesquels tout repose. Tout d'abord le nombre m choisi par le suspect était trop petit, un ordinateur aurait pu le factoriser assez rapidement. Mais pire encore, le doctorant avait choisi des nombres premiers particuliers, ce qu'il ne faut jamais faire car ce sont les premiers à être testés!

Lien :

Laboratoire de Mathématiques et Applications

Accueil

Haut de page

NCIES - Poitiers Equipe Mathématiques

NCIES - Poitiers
Equipe Mathématiques