Cryptographie

Jean-Marc Alliot*

*
e-mail : alliot@recherche.enac.fr

Chapter 1  Éléments mathématiques

La plupart des systèmes de cryptographie à clef publique sont basés sur des techniques mathématiques, qu'elles soient arithmétiques, algébriques ou analytiques.

L'outil indispensable à connaître est la théorie des corps quotients de Z, que nous allons rapidement présenter.

1.1  Définitions élémentaire

Définition 1  [Groupe]   Un groupe est un couple (G,+) où + est une loi de composition interne sur G, associative, possédant un élément neutre, et telle que tout élément de G admet un symétrique pour cette loi. Si + est commutative, le groupe est dit commutatif, ou abélien.
S'il n'y a pas d'ambiguïté sur la loi, on parlera parfois simplement du groupe G. Le couple (Z,+) composé de l'ensemble des entiers relatifs et de l'addition usuelle est un groupe abélien.
Définition 2  [Sous-groupe]   Soit le groupe (G,+). On dit que (S,+) est un sous-groupe de G si S est une partie de G stable pour + et S est un groupe pour la loi + induite par G sur S.
Les entiers pairs 2Z munis de l'addition sont un sous groupe de (Z,+).
Définition 3  [Anneau]   Un anneau est un triplet (A,+,.) où la loi + (dite "additive") est une loi de groupe abélien sur A et la loi . (dite "multiplicative") est une loi de composition interne, associative, et distributive par rapport à l'addition. Si la multiplication est commutative, l'anneau est dit commutatif, et si elle possède un élément neutre, l'anneau est dit unitaire.
Là encore, s'il n'y a pas d'ambiguïté sur les lois, on parlera parfois simplement de l'anneau A. Le triplet (Z,+,.) composé de l'ensemble des entiers relatifs, de l'addition et de la multiplication usuelles est un anneau commutatif unitaire.
Définition 4  [Corps]   Un corps est un anneau unitaire (K,+,.) tel que (K-{0},.) (où 0 est l'élément neutre de l'addition) est un groupe.
Tout élément non nul de K est donc inversible dans K. Des exemples classiques de corps sont (R,+,.) (ensemble des nombres réels) et (Q,+,.) (ensemble des nombres rationnels).
Définition 5  [Idéal d'un anneau commutatif A]   I est un idéal de A si et seulement si I est un sous-groupe additif de A et pour tout élément x de A et tout élément y de I, x.y Î I.
Les idéaux de l'anneau Z sont les sous-groupes nZ (ensemble des multiples de n) avec n ³ 0.
Définition 6  [Relation sur un ensemble E]   Une relation R sur un ensemble E est un couple (E,G) ou G est une partie du produit cartésien E× E, appelée graphe de la relation. On dit que a est en relation avec b, et l'on note a   R  b, si et seulement si (a,b) Î G.
En pratique, une relation est plutôt définie par une propriété, que par la donnée extensive du graphe.
Définition 7  [Relation d'équivalence]   R est une relation d'équivalence sur l'ensemble E si et seulement si R est réflexive (pour tout x de E, on a x   R  x), symétrique (si x   R  y alors y   R  x) et transitive (si x   R  y et y   R  z alors x   R  z).
Un exemple simple de relation d'équivalence est, par exemple, la relation définie par ``x   R  y si x a le même nombre de chiffres en base 10 que y''.
Définition 8  [Classe d'équivalence]   Soit R une relation d'équivalence sur E. La classe d'équivalence d'un élément x de E est le sous-ensemble des éléments de E en relation avec x suivant R.
On dit que deux éléments x et y d'une même classe d'équivalence sont équivalents suivant R. Notons également que l'ensemble des classes d'équivalence suivant R forme une partition de E1.
Définition 9  [Ensemble quotient de E par R]   Soit R une relation d'équivalence sur E. L'ensemble des classes d'équivalence de E suivant R est appelé ensemble quotient de E par R, et il est noté E/ R.

Définition 10  [Classes à gauche, classes à droite]   Soit (G,+) un groupe, H un sous-groupe de G et a un élément de G. Alors les ensembles
aH={a+h | hÎ H} et Ha={h+a | hÎ H}
sont appelées respectivement classe à gauche et classe à droite de a suivant H.
Les éléments de aH (resp. Ha) sont les classes d'équivalence de a pour la relation d'équivalence définie par : x R y si et seulement si (y-x) Î H (resp. (x-y) Î H).

Pour deux éléments a et b de G, les ensembles aH et bH sont soit confondus, soit disjoints (a et b sont soit dans la même classe d'équivalence, soit dans des classes d'équivalence différentes) et les ensembles de la forme aH, pour a variant sur tout G, forment une partition de G (toujours en raison des propriétés de la relation d'équivalence).
Théorème 1  [Théorème de Lagrange]   Soit G groupe fini et H un sous groupe de G. Alors le cardinal2 de H divise le cardinal de G.
Nous savons déjà que les classes d'équivalence de la relation : x R y si et seulement si (y-x) Î H, forment une partition de G. Remarquons maintenant que l'application qui à x associe a+x definit une bijection de H sur aH. Donc le cardinal de aH est exactement le cardinal de H, et ce pour tout a de G. Donc chaque classe d'équivalence de R a exactement le même cardinal, qui est aussi celui de H. Donc le cardinal de H divise le cardinal de G.
Définition 11  [Congruence]   Une congruence R sur un ensemble E, muni d'une loi de composition interne +, est une relation d'équivalence sur E, compatible avec la loi de composition interne + : soit x   R  y et z   R  w alors (x+z)   R  (y+w).

1.2  Éléments d'arithmétique

Théorème 2  [Division euclidienne]   Soit deux entiers naturels a et b avec a>b. Il existe un couple unique d'entiers naturel q et r (avec 0£ r<b) vérifiant a=bq+r.
q est appelé le quotient de la division euclidienne de a par b et r le reste. La démonstration est triviale.
Définition 12  [Diviseur]   On dit qu'un entier b divise un entier a>b (et on note a|b) si et seulement si le reste de la division euclidienne de a par b est égal à 0. On dit aussi que a est un multiple de b.

Définition 13  [Nombre premier]   Un nombre p est dit premier si et seulement si il n'a que deux diviseurs positifs : 1 et lui-même.

Théorème 3  [Théorème fondamental de l'arithmétique]   Tout entier naturel n peut s'écrire de façon unique en un produit de nombre premiers, appelé décomposition en facteurs premiers de n.
Une assertion équivalente au théorème fondamental consiste à dire que si un nombre premier p divise ab alors p divise a ou p divise b. Un nombre premier est, quant à lui, dit irréductible3.
Définition 14  [Plus grand diviseur commun (pgcd)]   Le plus grand diviseur commun de deux entiers a et b, noté pgcd(a,b) est le plus grand entier d divisant à la fois a et b.
Une définition équivalente du pgcd consiste à dire qu'il s'agit du seul entier divisant a et b et divisible par tous les autres entiers divisant à la fois a et b. Il est aisé de trouver le pgcd de deux nombres lorsque l'on connaît leurs décompositions en facteurs premiers : il suffit de prendre le produit des entiers premiers apparaissant dans les deux décompositions avec l'exposant minimal. Il est malheureusement rare de connaître dans le cas général la décomposition en facteurs premiers d'un nombre quelconque (la sécurité de nombreux systèmes cryptographiques comme le RSA repose précisément sur la difficulté qu'il y a à décomposer un nombre en facteurs premiers). Il existe pourtant une méthode rapide permettant de trouver le pgcd de deux nombres.
Théorème 4  [Algorithme d'Euclide]   Soit deux entiers a et b (b<a). On définit la suite rn suivante :
rn-1= qn rn + rn+1    avec   0£ rn+1 < rn
avec r0=a et r1=b. Alors, il existe n0 tel que rn0+1=0 et rn0 est le pgcd de a et b.
Démonstration : La suite rn est strictement décroissante et minorée par 0, puisqu'il s'agit de la définition même de la division euclidienne. Donc il existe nécessairement n0 tel que rn0+1=0. Montrons maintenant que rn0 est le pgcd de a et b. Pour cela, utilisons la seconde définition du pgcd, c'est à dire qu'il s'agit du seul entier divisant a et b et divisible par tous les autres entiers divisant simultanément a et b.

Vérifions tout d'abord que rn0 divise a et b. On a rn0-1 = qn0 rn0+0. Donc rn0 divise rn0-1 Mais s'il divise rn0-1 il divise aussi rn0-2 puisque rn0-2 = qn0-1 rn0-1+rn0, etc. Par récurrence, on démontre ainsi aisément que rn0 divise tous les rn et donc divise a et b.

Réciproquement, considérons un nombre c qui divise a et b. c divise donc r0 et r1 par définition. Mais alors, il divise également r2 puisque r0 = q1 r1+r2, etc. Par récurrence, on démontre donc qu'il divise tous les rn et donc qu'il divise rn0.

L'algorithme d'Euclide permet d'établir aisément le théorème suivant.
Théorème 5  [Identité de Bezout]   Soit a et b deux nombres tels que pgcd(a,b)=d. Il existe alors deux entiers relatifs u et v tels que au+bv=d.
Démonstration : récrivons les relations ci-dessus :
rn0 = rn0-2 - qn0-1 rn0-1     (1)
··· = ···     (2)
rn-1 = rn-3 - qn-2 rn-2     (3)
··· = ···     (4)
r3 = r1 - q2 r2     (5)
r2 = r0 - q1 r1     (6)
On voit donc que r2 peut s'écrire comme une combinaison linéaire de r0 et r1 (c'est à dire de a et b). r3 peut donc s'écrire comme une combinaison linéaire de a et b en remplaçant r2 par son expression en a et b. On peut ainsi vérifier par récurrence que tous les rn peuvent s'écrire sous la forme d'une combinaison linéaire de a et b, et ce résultat est donc également valable pour le pgcd rn0.
Définition 15  [Relation de congruence pour les entiers relatifs]   Soit a et b deux entiers relatifs. Soit p un entier naturel fixé. On dit que a et b sont congrus modulo p si et seulement si a-b est un multiple de p. On note alors :
a º b     [ p ]

Il est aisé de vérifier que la relation définie ci dessus est une relation d'équivalence (réflexive, symétrique et transitive).
Définition 16  [Ensemble quotient]   On note Z / p Z l'ensemble des classes d'équivalence de la relation de congruence modulo p et      la fonction qui à chaque élément a de Z associe sa classe d'équivalence a dans Z / p Z.
Notons que Z / p Z contient exactement p éléments qui sont représentés par les éléments canoniques 0,1,···,p-1.
Définition 17  [Arithmétique de Z / p Z]   On étend l'arithmétique de Z à Z / p Z en définissant les fonctions + et × de la façon suivante :
a   +   b = a+b
a   ×   b = a × b
Pour que cette définition ait un sens, il faut vérifier que les opérations définies ci-dessus sont bien indépendantes du représentant choisi dans la classe d'équivalence. Cela est rendu évident par les formules : (pa+b)+(pc+d)=p(a+b)+(c+d) et (pa+b)(pc+d)=p(pac+cb+ad)+bd.
Théorème 6   Z / p Z muni des opérations + et × est un anneau. La fonction est un morphisme surjectif d'anneau.
On abandonne généralement la notation pour les opérateurs et les classes d'équivalence de Z /p Z, et on les note simplement +, × et 0··· p-1, notation que nous adopterons dans la suite.
Exemple 1   Posons p=5. Les élément de Z / 5 Z sont 0, 1, 2, 3 et 4. 0 est bien évidemment élément neutre pour l'addition et 1 élément neutre pour la multiplication. L'inverse (pour l'addition) de 2 est 3 ( 2+3=5 º 0     [ 5 ]), celui de 4 est 1.

Théorème 7  [Inversibilité dans Z / p Z]   Un élément a de Z / p Z est inversible si et seulement si a et p sont premiers entre eux.

Démonstration : si a et p sont premiers entre eux, alors il existe u et v tels que au+pv=1. Modulo p, cette relation devient au º 1     [ p ]. u est donc l'inverse de a dans Z / p Z.

Réciproquement, si a et p ne sont pas premiers entre eux alors il existe trois nombres q, r, s avec 1<q<p et 1<s<p tels que qr=a et qs=p (q est le pgcd de a et p). On en déduit qrs=qsr=pr=as qui devient modulo p : as º 0     [ p ]. Donc a est un diviseur de zéro dans Z / p Z et n'admet donc pas d'inverse4.
Théorème 8  [Corps Z/p Z]   Z/ p Z est un corps si et seulement si p est premier.
Démonstration : si p est premier, alors tout nombre compris strictement entre 1 et p est premier avec p, donc tout nombre de Z /p Z est inversible. Réciproquement, si p n'est pas premier, il admet au moins un diviseur compris strictement entre 1 et p, qui ne sera donc pas inversible.
Théorème 9  [Théorème chinois]   Soit le système de s congruences suivant :
x º a1     [m1]
x º a2     [m2]
··· º ···
x º as     [ms]
et " i,j,    j¹ i,  pgcd(mi,mj)=1. Alors il existe une solution x0 commune à toutes les congruences ci dessus et toute autre solution est congruente à x0 modulo M=m1 m2 ··· ms.
Démonstration : posons Mi = M/mi, alors pgcd(Mi,mi)=1. Donc d'après l'identité de Bezout, il existe Ni tel que Mi Ni º 1     [ mi ]. Posons x0=åi ai Mi Ni. Alors pour tout j : x0 º aj     [ mj ]. Supposons maintenant que nous ayons une deuxième solution x1 de notre système. Posons x=x0-x1. x est congru à 0 modulo chacun des mi, et donc également congru à 0 module M. Donc x0 et x1 sont congrus modulo M.
Définition 18  [Fonction indicatrice d'Euler]   Soit n un entier naturel. On appelle fonction indicatrice d'Euler, et on note j(n) le nombre d'entiers naturels strictement positifs premiers avec n et strictement inférieurs à n.
On remarque que pour p premier, j(p)=p-1 ; d'autre part, j(pa)= pa-pa-1, puisque les nombres premiers avec pa et inférieurs à pa sont tous les nombres inférieurs à pa moins les multiples de p (et il y en a pa-1).

Nous allons maintenant donner une formule générale permettant de calculer j(n) connaissant la décomposition en facteurs premiers de n. Avant cela, nous aurons besoin du lemme suivant.
Lemme 1   La fonction j est multiplicative pour les nombres premiers entre eux : si pgcd(p,q)=1 alors j(pq)=j(p) j(q)
Démonstration : nous devons compter les nombres i compris entre 0 et pq-1 qui sont premiers avec pq. Or, d'après le théorème chinois, un nombre i n'aura pas de facteur commun avec pq si et seulement si le nombre i1 º i     [ p ] n'a aucun facteur commun avec p et le nombre i2 º i     [ q ] n'a pas de facteur commun avec q. On a donc grâce au théorème chinois une bijection entre les couples (i1,i2) tels que i1 est premier avec p et i2 est premier avec q, et les nombre i tel que i est premier avec pq. Or, nous avons j(p)× j(q) couples de ce type, donc j(pq)=j(p) j(q)

De façon générale :
Théorème 10   Soit n un entier naturel avec n=Õ1£ i£ k piei où les (pi,ei) sont la décompositions en facteurs premiers de n. Alors :
j(n)=
 
Õ
1£ i£ k
(pi-1) piei-1
Démonstration : j étant multiplicative, il suffit d'utiliser la formule j(pa)= pa-pa-1=pa-1(p-1) pour p premier.
Théorème 11   Soit a et n deux nombres premiers entre eux et x1, x2,··· xk les nombres (xi)i=1j(n) premiers avec n et inférieurs à n. Alors l'ensemble des (a xi)i=1j(n) dans Z/n Z est égal à l'ensemble des (xi)i=1j(n).
Démonstration : Tout d'abord remarquons que si xi et a sont premiers avec n alors a xi est premier avec n. Maintenant, supposons qu'il existe deux nombre i et j distincts tels que a xi º a xj     [ n ]. Cela implique que a(xi-xj) º 0     [ n ]. Mais a étant premier avec n, il est inversible et donc on a xi-xj º 0     [ n ]. Donc xi º xj     [ n ], ce qui est contraire à l'hypothèse.
Théorème 12  [Généralisation d'Euler]   Soit a et n deux nombres premiers entre eux. Alors aj(n) º 1     [ n ]
L'ensemble des (xi)i=1j(n) premiers avec n et inférieurs à n et l'ensemble des (a xi mod n)i=1j(n) étant les mêmes, on a
j(n)
Õ
i=1
xi º
j(n)
Õ
i=1
a xi º aj(n)
j(n)
Õ
i=1
xi     [n]
Donc aj(n) º 1     [ n ]

Ce théorème est appelé généralisation d'Euler, car il généralise le petit théorème de Fermat qui dit que si n est premier, alors pour tout a<n, an-1 º 1     [ n ].

On peut également remarquer une propriété utile liée au théorème d'Euler : si l'on souhaite calculer ar modulo n, alors on peut réduire r en s avec sº r  [j(n)] et ar º as   [n]

1.3  Résidus quadratiques

Définition 19  [Résidu quadratique]   Soit aÎ Z/nZ. a est appelé résidu quadratique modulo n ou carré modulo n si et seulement si il existe bÎ Z/nZ tel que b2 º a   [n]

Théorème 13  [Racines carrés dans le corps Z/nZ]   Soit n>2 premier. Alors si a est un résidu quadratique dans Z/nZ différent de 0, a a exactement deux racines carrées.
La démonstration est élémentaire. Soit b et c, deux racines de a quelconques et non nécessairement distinctes. Nous avons alors b2 º c2    [n]. Donc b2-c2 º 0     [ n ], ou encore (b-c)(b+c) º 0     [ n ]. n étant premier, Z/nZ est un corps. On a donc soit b=c, soit b=n-c. a admet donc bien exactement deux racines carrées distinctes, l'une inférieure ou égale à n-1/2 et l'autre strictement supérieure.
Théorème 14  [Nombre de résidus quadratiques]   Soit n>2 premier. Alors il y a exactement n-1/2 résidus quadratiques différents de 0 dans Z/nZ.
Le résultat découle directement du théorème précédent. L'ensemble des résidus quadratiques est simplement obtenu en calculant le carré de tous les nombres de 1 à n-1/2.
Définition 20  [Symbole de Legendre]   Soit n>2 premier et a un entier quelconque. On définit le symbole de Legendre (a/n) par :

Théorème 15  
(
a
n
) º a(n-1)/2     [ n ]

1
Démonstration élémentaire laissée à la diligence du lecteur.
2
On appelle aussi parfois le cardinal d'un groupe, l'ordre de ce groupe.
3
Ces définitions, valables pour l'arithmétique des entiers naturels ou relatifs, devient fausse pour l'arithmétique des nombres algébriques, comme par exemple les nombres de la forme a+b10, pour lesquels l'irréductibilité n'est pas équivalente à la primalité.
4
S'il en admettait un, que nous noterions a -1, on aurait (comme as=0) : a -1 a s = 0, soit s=0 dans Z / p Z, ce qui est contredit l'hypothèse 1<s<p dans Z.

Chapter 2  Cryptage à clef publique

2.1  Introduction

Le cryptage traditionnel repose sur l'existence d'une clef privée, commune à l'émetteur et au récepteur du message, qui doit rester secrète pour garantir la confidentialité de la transaction. Cela pose le problème du transport de cette clef (comment la faire parvenir de façon sûre à quelqu'un se trouvant à l'étranger), mais aussi du maintien de sa confidentialité sur le long terme. Dans le cryptage traditionnel, la connaissance de l'algorithme de cryptage et de ses paramètres permet de construire l'algorithme de décryptage.

Dans le cryptage à clef publique, la clef de cryptage est au contraire diffusée largement, même par des canaux absolument non sûrs. Simplement, la connaissance de l'algorithme de cryptage et sa clef ne permet pas de reconstituer l'algorithme de décryptage.

Nous allons maintenant examiner quelques exemples de cryptage à clef publique.

2.2  L'algorithme Merkle-Hellman

L'algorithme Merkle-Hellman [MH78] est historiquement le premier algorithme montrant le fonctionnement d'un système à clef publique. Il appartient à la famille des algorithmes de cryptage de type ``sac à dos'' (ou knapsack en anglais).

Le problème du sac à dos est un problème classique en théorie de la complexité. On sait qu'une instance générale du problème est NP-complète. La formulation du problème du sac à dos est simple : un randonneur possède un sac à dos pouvant contenir x kgs, et il dispose d'un ensemble I d'objets, chacun pesant un poids xi. Il souhaite savoir s'il existe un sous ensemble de J, tel que la somme des poids des éléments de J soit exactement x. Mathématiquement :
xÎ N, I={x1,x2,···,xi,···,xn},    trouver    J    tel que :  
 
å
iÎ J
xi = x

Remarquons tout d'abord que, s'il est possible de montrer que le problème du sac à dos est NP-complet dans le cas général, il existe des instances extrêmement faciles à résoudre, ce sont celles faisant intervenir les séquences super-croissantes :
Définition 21  [Séquence super-croissante]   Soit une suite un et la série associée Sn=åi=1n un. On dit que un est super-croissante si l'on a :
" n,   un+1> Sn
Notons tout de suite que les bases de numérations sont toutes des exemples de séquence super-croissante (1+2<4, 1+2+4<8, etc).

Il est clair que le problème du sac à dos est trivial lorsque l'on utilise une séquence super-croissante. Il est tout aussi clair qu'il n'a pas toujours de solution. Ainsi, si l'on choisit la base 2 comme séquence super-croissante, tout nombre pourra se décomposer sur cette base au sens du problème du sac à dos. Il n'en va pas de même si l'on choisit la base 10 (par exemple, 13=8+4+1 se décompose aisément sur la séquence {1,2,4,8}, alors que le même nombre ne peut pas se décomposer sur la séquence {1,10}).

L'idée de Merkle-Hellman est de transformer un problème du sac à dos trivial basé sur une séquence super-croissante en problème du sac dos général, qui devient alors NP-complet, donc ``insoluble''. Nous allons tout d'abord présenter une version simplifiée de l'algorithme Merkle-Hellman.
Algorithme 1  [Génération de la clef pour l'algorithme Merkle-Hellman]   L'algorithme se décompose de la façon suivante :
  1. Choisir une séquence super-croissante {a1,a2,···,an} et un nombre N avec N>a1+a2+···+an
  2. Choisir un nombre A<N tel que pgcd(A,N)=1
  3. Calculer les bi º A ai     [ N ]
La clef publique est ({b1,b2,···,bn}) et la clef privée (N,A,{a1,a2,···,an}).

Il suffit maintenant pour l'émetteur de récupérer la clef publique ({b1,b2,···,bn}), qui peut être transmise par n'importe quel canal, même non sûr, puis d'appliquer l'algorithme de cryptage suivant :
Algorithme 2  [Cryptage par l'algorithme de Merkle-Hellman]   Soit un message binaire composée de la suite de chiffre d1d2 ··· dn, avec di=0 ou di=1. Alors, le message crypté est :
c =
n
å
i=1
di bi
où les bi sont la clef publique calculée par l'algorithme précédent.
Supposons maintenant qu'un individu mal intentionné tente de décrypter le message c. Il est en possession de la séquence I={b1,b2,···,bn} et du nombre c. Il lui faut donc résoudre un problème de sac à dos, puisqu'il lui faut trouver le sous ensemble J de I tel que åjÎ J bj=c. Or ce problème de sac à dos n'a a priori aucune structure particulière, puisque la séquence bi n'est pas super-croissante après l'application de la multiplication par A et du modulo N. Ce problème est donc a priori NP-complet.

En revanche, si nous sommes en possession de la clef privée, le décryptage est élémentaire :
Algorithme 3  [Décryptage par l'algorithme de Merkle-Hellman]   Soit le message cryptée c. Soit m º A-1c     [ N ]. Calculons les nombres binaires di' tel que m=åi=1n di' ai. Alors di=di', où les di représentent les chiffres du message initial.
L'algorithme de décryptage de Merkle-Hellman consiste à résoudre un problème de sac à dos, mais cette fois ci sur une instance super-croissante. On peut aisément vérifier que l'algorithme de décryptage est correct en raison de la propriété suivante :
m º A-1c º A-1
n
å
i=1
di bi º
n
å
i=1
di (A-1 b1) º
n
å
i=1
di ai     [N]

Nous allons maintenant développer un exemple pour bien montrer le fonctionnement de l'algorithme Merkle-Hellman. Nous allons choisir des nombres artificiellement petits, sachant bien entendu qu'il faudrait normalement choisir des nombres plus grands de plusieurs ordres de magnitude.
Exemple 2  [Application de l'algorithme de Merkle-Hellman]   Nous allons prendre n=8, et comme suite : {a1,a2,···,a8}={3,7,15,31,63,151,317,673}. Nous choisissons N=1511 et A=643. Nous calculons alors la séquence : {b1,b2,···,b8}={418,1479,579,290,1223,389,1357,593}, et aussi 643-1=47   [1511].

La seule information diffusée est la liste des bi. Supposons maintenant que nous ayons à coder le message 10011010. Il suffit de calculer puis de transmettre c=418+290+1223+1357=3288.

Pour décrypter le message, nous calculons m=A-1 c   [N]=47 × 3288   [1511]=414. Il nous suffit alors de résoudre le problème du sac à dos avec la séquence super-croissante ai et x=414=317+63+31+3, soit 10011010. Nous retrouvons bien le message initial.

L'algorithme de Merkle-Hellman est aujourd'hui complètement abandonné. Même avec diverses améliorations (permutation sur les éléments de la base, algorithme itéré, etc), il n'est pas sûr et l'on a trouvé des algorithmes capables de le ``casser'' en un temps polynomial. Le premier exemple d'un tel algorithme est dû à Shamir en 1982 (publié seulement en 1984 [Sha84]).

Notons enfin qu'il n'existe qu'un seul système de cryptage sûr basé sur le principe du ``sac à dos''. Il s'agit de l'algorithme de Chor-Rivest. Son principal inconvénient est la taille des clefs (de l'ordre de 50000 bits).

2.3  L'algorithme RSA (Rivest-Shamir-Adleman)

L'algorithme RSA est actuellement le cryptosystème le plus employé. Inventé en 1977, il est basé sur l'impossibilité, tout au moins à ce jour, de factoriser rapidement de grands nombres composites.
Algorithme 4  [Génération d'une clef pour l'algorithme RSA]   La construction d'une clef pour l'algorithme RSA se fait en trois étapes :
  1. Générer deux grands nombres premiers p et q et calculer n=pq et f=(p-1)(q-1)
  2. Trouver un entier e tel que 1 < e < f et pgcd(e,f)=1
  3. Calculer d=e-1   [f].
La clef publique diffusée est (n,e) et la clef privée est d.
Notons que la connaissance de n et e ne permet pas de reconstituer d. Il faudrait pour cela être capable de factoriser n, ce qui est impossible dès que l'on choisit p et q suffisamment grands.
Algorithme 5  [Cryptage par l'algorithme RSA]   Le message m à transmettre doit appartenir à l'intervalle [0,n-1]. On calcule alors :
cº me   [n]
c est le message crypté à transmettre.

Algorithme 6  [Décryptage par l'algorithme RSA]   Soit c le message crypté. Il suffit de calculer :
mº cd   [n]

Démonstration : il nous faut montrer que cd º (me)d º med   [n] est également congru à m modulo n. Nous savons que dº e-1   [f], donc $ k,   ed=1+kf. Donc med º m1+kf º m (mf)k   [n]. Le théorème d'Euler permet d'écrire : mf º 1 [n]. Donc med º m   [n].

Nous allons maintenant montrer un exemple d'utilisation de l'algorithme RSA. Les paramètres sont là aussi pris artificiellement petits.
Exemple 3   On choisit p=313 et q=547. Donc n=p q=171211 et f=170352. On choisit e=83 et l'on trouve d=108779. Supposons que nous souhaitions coder le message m=123456. On trouve alors c º me º 12345683 º 49619   [n]. Pour retrouver le message initial, il suffit de calculer mº cd º 49619108779 º 123456   [n].

References

[MH78]
R.C. Merkle and M.E. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE transactions on information theory, 24:525--530, 1978.

[Sha84]
R. Shamir. A polynomial time algorithm for breaking the merkle-hellman cryptosystem. IEEE transactions on information theory, 30:699--704, 1984.


This document was translated from LATEX by HEVEA.