TP de Maple : Cryprographie
c(cid:13) Dikanaina Harrivel, protégé par la GNU Free Documentation License
source disponible sur http://www.velvia.org
Le problème général de la cryptographie est le suivant : une personne, Mr X, désire assurer
la confidentialité des messages qui lui sont envoyés. Pour ce faire, il détermine deux fonctions
C (fonction de chiffrement) et D (fonction de déchiffrage).
Dans les systemes de cryptographie ”classiques”, ces deux fonctions sont tenues secretes. Au
contraire, dans les systemes a clef publique, la fonction de chiffrement est connue de tous,
seule la clef de déchiffrage est tenue secrète. Ainsi tout un chacun peut envoyer un message
a Mr X, mais personne (mis a part Mr X) ne doit être en mesure de lire ces messages.
Le principe des systemes a clef publique a été proposé initialement par Diffie et Hellman avec
les contraintes suivantes sur les fonctions C et D :
1. si M est un message, D(C(M )) = M .
2. il est très difficile, voire impossible, de déduire D connaissant C.
Vous pouvez réfléchir au moyen de signer les messages avec le systeme a clef publique.
1 Première opération : Codage d’un texte
Pour crypter un message, il faut au préalable transformer celui-ci en une suite de nombres.
En utilisant la fonction convert avec l’option bytes de Maple, écrivez deux procédures code
et decode qui transforment respectivement une chaˆıne de caractères en une suite de nombres
et une suite de nombre en une suite de caractères.
2 Le cryptage par l’algorithme du sac à dos
C’est un algorithme de cryptage a clef publique qui est dû a Merkle et Hellman. Il repose
sur la complexité algorithmique du probleme du sac a dos : un marcheur dispose d’un sac à
dos et aimerait emporter avec lui n objets de différente valeurs. Malheureusement les n objets
ne peuvent pas loger tous dans le sac à dos en même temps. Quelle est la meilleure combi-
naison d’objets pour remplir le sac a dos ? Plus formellement, le probleme général consiste,
étant donné un n–uplet (a1, a2, . . . , an) d’entiers positifs, et un nombre S positif également,
à trouver un n–uplet de nombres valant 0 ou 1 tel que S = P aixi.
Si les (ai)i n’ont pas de propriétés particulières, la recherche des (xi)i (le message codé en
binaire) demande un travail exponentiel en n (on démontre en fait que ce problème est NP-
complet). Ainsi la résolution du problème est impossible en temps raisonnable et donc on
Publicité
1Attention le problème n’admet pas forcement de solution.
2pour la multiplication
peut présumer que l’algorithme du sac à dos est bien adapté au cryptage.
Pour pouvoir utiliser cette propriété en cryptographie, il faut trouver une classe de n–uplet
(a1, . . . , an) pour lesquels on puisse résoudre facilement le problème (en ayant éventuellement
une connaissance supplémentaire tenue secrète), sinon il serait impossible de décrypter le
message codé.
2.1 Les suites super croissantes
Un n–uplet (b1, . . . , bn) sera dit super croissant si et seulement si
∀i ∈ J2, nK
bi >
i−1
X
j=1
bj.
1. écrire une procédure est super(b) qui renvoie true si la suite b est super croissante et
false sinon.
2. Dans le cas ou le n–uplet b est super croissant, le probleme du sac a dos est parti-
culierement simple a résoudre. Donnons nous un n–uplet b := [b1, . . . , bn] super crois-
sant et un entier S = Pi xibi avec xi ∈ {0, 1}. Montrez que si bn > S alors xn = 0 et
si bn ≤ S alors xn = 1. En déduire un algorithme pour déterminer les xi connaissant b
et S.
Écrire une procédure resout(S,b) qui étant donnés une suite super croissante (bi)16i6n
et un entier S ≤ P bi renvoie un entier M dont l’écriture sur n bits M = x1x2 . . . xn
avec xi ∈ {0, 1} vérifie1 S = P
n
i=1 xibi.
2.2 Cryptographie et algorithme du sac à dos
Évidemment, sous cette forme particulière (avec les suites super croissantes), l’algorithme
du sac à dos ne présente aucun intérêt pour la cryptographie (tout le monde, connaissant
la suite super croissante (bi)i est en mesure de décoder un message). L’idée de Merkle et
Publicité
Hellman consiste a tordre les bi de façon a obtenir un n–uplet qui n’est plus super crois-
sant. Pour ce faire on peut utiliser la structure d’anneau de Z/nZ. On choisit un nombre
m > P bi, et un entier w ∈ N tel que pgcd(w, m) = 1. Alors w est inversible2 dans Z/mZ.
On note u := w−1 ∈ Z/mZ, on a ainsi u · w ≡ 1 dans Z/mZ. On calcule alors le n–uplet
a = (a1, . . . , an) tel que pour tout i ∈ J1, nK,
3 La méthode RSA
ai = w · bi ∈ Z/mZ
Le n–uplet a est alors rendu public, tandis que u est gardé secret. Pour transmettre le mes-
sage S a Mr X, Mlle Y va a partir de l’écriture de S sur n bits S = xnxn−1 . . . x1 calculer la
n
somme Σ := P
i=1 xiai qu’elle va envoyer à Mr X. Si le message est intercepté par le jaloux
personnage Z, celui-ci ne pourra pas (a priori) retrouver la suite des xi a partir des Σ et du
n–uplet a car c’est un probleme de type sac a dos.
Pour décoder le message Mr X n’aura alors qu’à calculer Σ · u modulo m, il obtiendra ainsi
n
la somme P
i=1 xibi et le n–uplet b étant super croissant, il n’aura aucun mal à retrouver le
nombre S.
1. Écrire une procédure Csac(txt,a) qui étant donné un texte txt renvoie le message
codé à l’aide du n–uplet a par la méthode décrite ci-dessus. Pour obtenir l’écriture d’un
nombre en binaire vous pouvez utiliser la fonction convert de Maple.
2. Écrire une procédure Dsac(txtcod,a,u) qui à partir du message crypté par la méthode
du sac à dos txtcod, la clef publique a et la clef privée u renvoie le message décodé.
3. Vérifiez que
b = [5, 13, 21, 89, 233, 377, 987, 2584, 6765, 17711, 251516, 6548456,
65484652, 114845465], m = 463814521, w = 234203372 et u = 101 vérifient bien les
propriétés voulues. Décrypter le message suivant [648640591, 1329005307, 1162545881,
1016018455, 1116558815, 1033898626]
Cette méthode de cryptage fut présentée par Merkle et Hellman en 1978 et semblait pro-
mise à un brillant avenir. Malheureusement, en 1982, Shamir publiait un algorithme pour
Publicité
casser le cryptage, car si le probleme du sac a dos est (pour l’instant) insoluble3 dans le
cas général, le n-uplet public a n’est pas tout à fait quelconque et l’attaque est possible.
Ainsi l’algorithme du sac à dos a été abandonné au profit de la méthode RSA dont l’un des
inventeurs est justement Shamir...
Cette méthode a été inventée en 1977 par Rivest, Shamir et Adleman, d’où le nom de
la méthode. Elle est aujourd’hui extrêmement populaire et il en existe beaucoup de versions
plus ou moins raffinées, mais toutes reposent sur le même principe.
Tout d’abord on se donne deux nombres premiers distincts p et q de préférence très grands.
Considérons alors l’entier n produit de ces deux nombres premiers n := pq. Il est (pour l’ins-
tant et empiriquement) tres difficile de retrouver p et q a partir de n seul. C’est sur cette
propriété qu’est basée le procédé de cryptage RSA.
On choisit c ∈ N premier à ϕ(n) = (p − 1)(q − 1) et l’on calcule alors d := c−1 l’inverse de c
dans Z/ϕ(n)Z. Montrez que l’on a la propriété suivante
∀x ∈ Z/nZ; (xc)d ≡ x
Les entiers n et c sont rendus publics tandis que d est gardé secret. Le codage d’un nombre
M < n consiste alors a calculer Mcod := M c dans Z/nZ. Le destinataire n’aura alors qu’a
calculer (Mcod)d modulo Z/nZ à l’aide de la clef privée d pour retrouver M .
1. Écrire une procédure CRSA(M ,c, n) qui code un message M par la méthode RSA
avec les clefs publiques c et n. Utilisez de préférence &ˆ pour l’élévation à la puissance
dans Z/nZ.
2. Écrire une procédure DRSA(CM ,d) qui décode un message CM à l’aide de la clef
privée d.
3. pour les application numériques vous pourrez prendre p = 47, q = 59 et c = 157, alors
d = c−1 = 17 dans un premier temps. Montrez que l’on peut facilement casser ce code
avec Maple. Essayez avec p = 37866809061660057264219253397 et q = 260 − 173, avec
c = 101 et d = 13399813988306020923532260412972837706866401322.
On est actuellement capable de factoriser des nombres de moins de 400 bits (mais pas n’im-
porte qui). Pour être assuré (pour l’instant) de la confidentialité des échanges, il faut donc
utiliser des clefs de 512 bits ou plus ou se faire à l’idée que l’on peut être écouté.
3en temps raisonnable