Décryptage de fichiers chiffrés
Sujet proposé par Andreas Enge
enge@lix.polytechnique.fr
Difficulté: moyen (**)
Ce projet est accompagné d'une page de suivi, accessible depuis
http://www.enseignement.polytechnique.fr/profs/informatique/Andreas.Enge/ |
1 Le contexte
Le problème du logarithme discret est, aux côtés du problème de la
factorisation, à la base des systèmes cryptographiques à clef publique les
plus utilisés en ce moment. Par exemple, les signatures numériques DSA et le
système de chiffrement ElGamal utilisés dans OpenPGP reposent sur la
difficulté de ce problème modulo un grand nombre premier p.
Nous rappelons le petit théorème de Fermat: pour un nombre premier p et
tout entier g entre 1 et p−1, on a
gp−1 modp = 1.
De plus, il y a des entiers (appelés éléments primitifs) g
tels que toutes les puissances 1, g, g2, ..., gp−2 sont
différentes modulo p et recouvrent donc l'ensemble des entiers entre 1 et
p−1. Par exemple, pour p = 11, on peut choisir g=2 puisque les puissances
successives de 2 modulo 11 sont 1, 2, 4, 8, 16=5, 10, 20=9,
18=7, 14=3 et 6; la puissance suivante est 12=1, et le cycle se répète.
Si on se donne maintenant un autre entier h entre 1
et p−1, il existe forcément un entier x (appelé le logarithme
discret de h en base g) tel que
gx modp = h.
Vu le théorème de Fermat, cet entier est uniquement déterminé modulo p−1, et
on peut donc le prendre entre 0 et p−2.
L'ancêtre de tous les cryptosystèmes fondés sur le problème du logarithme
discret est l'échange de clef inventée par Diffie et Hellman [3],
qui permet à deux utilisateurs Alice et Bob d'obtenir une clef de
chiffrement commune. Alice choisit
un exposant a au hasard entre 0 et p−1, calcule A = ga modp et
l'envoie à Bob. Bob agit de façon symétrique en prenant un entier aléatoire b
et en envoyant B = gb modp à Alice. Maintenant, les deux peuvent obtenir
gab modp: Alice procède en calculant Ba modp, Bob calcule Ab
modp. Ils peuvent ensuite utiliser ce secret commun pour chiffrer
la communication entre eux. Éve souhaite les espionner et a installé du
matériel écoutant la ligne reliant les deux. Elle intercepte A et B.
Clairement, si elle sait calculer des logarithmes discrets modulo p, elle
retrouve a ou b et ainsi gab, et peut à partir de ce moment décrypter
la communication chiffrée.
2 L'algorithme
Un algorithme trivial pour résoudre le
problème consiste à tester toutes les valeurs successives de x jusqu'à ce
qu'on tombe sur la bonne. Clairement, cette approche n'est plus faisable
déjà pour des tailles assez modérées de p. Le but de ce projet est d'implanter
un algorithme plus rapide qui permettra d'attaquer des instances dans lesquelles
p a plusieurs dizaines de chiffres décimaux. Cet algorithme a été présenté
dans [1]. Il procède en trois étapes: dans la première phase, on crée
des relations entre quelques nombres bien choisis; dans la deuxième, on
résout un système linéaire pour trouver les logarithmes discrets de ces
nombres particuliers; dans la troisième phase, on calcule le logarithme discret
du nombre qui nous intéresse.
2.1 Trouver des relations entre petits nombres premiers
Fixons une borne B. Soit F = { p1, …, pn } l'ensemble
comprenant tous les nombres premiers ne dépassant pas B; on l'appelle la
base de facteurs. Pour des valeurs ai choisies
aléatoirement entre 1 et p−2, nous pouvons maintenant calculer
gai modp; si nous avons de la chance, cet entier se décompose en
facteurs premiers contenus dans F. Cela se teste en essayant de
diviser par les éléments de F. On obtient donc de temps en
temps une relation de la forme
Passant aux logarithmes, on obtient l'équation linéaire
dans laquelle les logarithmes des éléments de la base de facteurs sont inconnus.
L'étape suivante est de résoudre le système linéaire ainsi formé pour
justement trouver ces logarithmes particuliers.
Exemple.
Pour p = 1019, g = 3, B = 11 et donc
F = { 2, 3, 5, 7, 11 }, nous trouvons (modulo 1019):
| |
366 mod1019 = 770 = 2 ⋅ 5 ⋅ 7 ⋅ 11,
372 = 880 = 24 ⋅ 5 ⋅ 11, |
| |
390 = 660 = 22 ⋅ 3 ⋅ 5 ⋅ 11,
3108 = 495 = 32 ⋅ 5 ⋅ 11,
3128 = 539 = 72 ⋅ 11, |
| |
3134 = 616 = 23 ⋅ 7 ⋅ 11 |
2.2 Algèbre linéaire
Le système linéaire issu de la phase précédente est à résoudre modulo p−1, ce
qui découle du petit théorème de Fermat. On va procéder par élimination de
Gauß. Notons que les entiers modulo p−1 forment un anneau: on peut
additionner, soustraire et multiplier en faisant les opérations usuelles sur les
entiers et en réduisant après modulo p−1. Malheureusement, il ne s'agit pas
d'un corps, puisque tous les éléments ne sont pas inversibles: on peut inverser
un élément a précisément si a et premier avec p−1. Dans ce cas,
l'algorithme d'Euclide étendu entre a et p−1 trouve les coefficients de
Bézout s et t tels que
s a + t (p−1) = 1;
modulo p−1, on a donc bien s = a−1.
Le problème d'algèbre linéaire
peut être résolu en travaillant séparément modulo les diviseurs
premiers de p−1 et en réassemblant le résultat modulo p−1 par le théorème
des restes chinois. Dans ce projet, nous allons nous faciliter la vie et prendre
des p tels que p−1 = 2 q avec q premier (des premiers de Sophie Germain).
En plus, au lieu de choisir un élément g primitif, nous allons prendre un
élément g d'ordre q, de sorte que gq = 1 modp, et le cycle des
puissances de g a une longueur q au lieu de p−1. Ainsi, on peut faire
l'algèbre linéaire modulo q, et tout élément différent de 0 devient
inversible. Cela permet d'appliquer l'élimination de Gauß telle qu'elle est
connue pour l'algèbre linéaire sur les réels. D'abord, on met la matrice sous
forme triangulaire (sauf permutation éventuelle des lignes). On choisit un
pivot différent de 0 dans la
première colonne, et en soustrayant des multiples de la ligne correspondante de
toutes les autres lignes, on élimine toutes les entrées sauf le pivot. Puis,
on choisit un pivot dans la deuxième colonne et on élimine toutes les entrées
de la deuxième colonne sauf les deux dans les lignes de pivot sélectionnées
jusqu'ici, et ainsi de suite. On travaille en même temps sur le côté droit du
système. À la fin, on remonte le système triangulaire et trouve facilement une
solution.
Exemple.
Continuant l'exemple de la section précédente, il faut résoudre le système
linéaire
|
|
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝ |
| 1 |
1 |
1 |
1 |
| 4 |
1 |
0 |
1 |
| 2 |
1 |
0 |
1 |
| 0 |
1 |
0 |
1 |
| 0 |
0 |
2 |
1 |
| 3 |
0 |
1 |
1 |
|
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠ |
|
|
|
=
|
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝ |
|
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠ |
|
Comme premier pivot, on choisit le 1 dans la première ligne, et on élimine
les entrées en dessous dans la première colonne en soustrayant 4 fois la
première ligne de la deuxième, 2 fois la première ligne de la troisième et
3 fois la première ligne de la sixième. Cela donne
|
|
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝ |
| 1 |
1 |
1 |
1 |
| 0 |
506 |
505 |
506 |
| 0 |
508 |
507 |
508 |
| 0 |
1 |
0 |
1 |
| 0 |
0 |
2 |
1 |
| 0 |
506 |
507 |
507 |
|
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠ |
|
|
|
=
|
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝ |
|
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠ |
|
|
|
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝ |
| 1 |
1 |
1 |
1 |
| 0 |
1 |
171 |
1 |
| 0 |
0 |
169 |
0 |
| 0 |
0 |
338 |
0 |
| 0 |
0 |
2 |
1 |
| 0 |
0 |
2 |
1 |
|
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠ |
|
|
|
=
|
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝ |
|
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠ |
|
|
|
⎛
⎜
⎜
⎜
⎝ |
| 1 |
1 |
1 |
1 |
| 0 |
1 |
171 |
1 |
| 0 |
0 |
1 |
0 |
| 0 |
0 |
0 |
1 |
|
⎞
⎟
⎟
⎟
⎠ |
|
|
|
=
|
|
2.3 Calculer des logarithmes discrets
La troisième phase fait finalement intervenir le nombre h dont nous cherchons
le logarithme discret. De façon similaire à la première étape, on cherche une
relation de la forme
ce qui implique
équation dans laquelle maintenant les logpj sont connus.
Exemple.
Pour h = 101, on obtient
h g11 = 245 = 5 ⋅ 72
et donc
log101 = 2 ⋅ 223 + 424 − 11 = 350,
et en effet on vérifie aisément que 3350 mod1019 = 101.
3 Travail demandé
Écrivez un programme Dlog qui prend comme argument un nombre premier
p tel que q = p−1/2 est également premier, la base g d'ordre
q du logarithme et le nombre A dont le logarithme est cherché. Le programme
renverra le logarithme de A modulo p en base g. Par exemple:
# java Dlog 1019 3 101
350
Puis écrivez un programme DH pour cryptanalyser le système de
chiffrement dérivé de l'échange de clef à la Diffie–Hellman. Le but est
d'obtenir la clef secrète
après avoir écouté l'information échangée lors de son établissement.
Le programme prendra en argument le nombre premier p, la base g et les
deux nombres A = ga et B = gb échangés par les deux participants. Il
affiche la valeur de gab. Par exemple:
# java DH 1019 3 101 255
303
La page de suivi contient des liens vers des fichiers qui ont été chiffrés
avec gpg. Les clefs utilisées sont dérivées des échanges
Diffie–Hellman de la liste suivante. Pour décrypter le fichier
exemple3.txt.gpg, exécutez la commande
gpg -o exemple3.txt -d exemple3.txt.gpg
Le logiciel vous demandera le mot de passe, qui n'est rien d'autre que la
clef commune Diffie–Hellman, ici, 303.
Jusqu'où pouvez-vous aller?
| p |
g |
|
|
A et B |
| 103 + 19 |
|
3 |
|
|
101 |
| |
|
|
|
|
255 |
| 1010 + 259 |
|
3 |
|
|
4819601888 |
| |
|
|
|
|
4585976725 |
| 1020 + 763 |
|
3 |
|
|
91735131463472784552 |
| |
|
|
|
|
71943364482341972729 |
| 1030 + 1783 |
|
2 |
|
|
170443004030887263495503209797 |
| |
|
|
|
|
79603079654135421329725150443 |
| 1040 + 17407 |
|
2 |
|
|
7844874590252958799279234570696688991100 |
| |
|
|
|
|
7168212572107335215990016933997075374505 |
| 1050 + 4483 |
|
3 |
|
|
57729859988238372248223918064862692108319469581386 |
| |
|
|
|
|
71082576999006199136234704359201564628816601360849 |
| 1060 + 15919 |
|
2 |
|
|
915432078722549409670942815593824347180000684959197526496947 |
| |
|
|
|
|
625397773938548846252647070659717579933818502198566122612022 |
3.1 Conseils pratiques
On remarque que les phases 1 et 2 peuvent prendre beaucoup de temps, tandis que
la phase 3 est relativement rapide. Prenez donc soin de ne pas répéter les deux
premières phases chaque fois que le programme est appelé; idéalement, le
deuxième logarithme pour le même p et g prendra une fraction du temps
nécessaire pour le premier. Cela peut être obtenu en stockant des résultats
intermédiaires dans un fichier.
Le bon choix de la borne B et donc de la base des facteurs F
s'avère
délicat: si B est trop petit, alors la probabilité d'obtenir une relation est
très faible. Si B est trop grand, la taille du système linéaire croît ainsi
que le nombre de relations requis. La valeur théorique pour un temps de calcul
minimal est donnée par B ∼ Lp1/2 avec
Le temps de calcul de l'algorithme est alors de l'ordre de
Lp3/2. En pratique, il faudra expérimenter et probablement choisir de
plus petites valeurs pour B, ne serait-ce que pour faire tenir la matrice en
mémoire.
Comme on a vu dans le petit exemple, les relations qu'on obtient ont tendance
à être linéairement dépendantes. Pour pouvoir résoudre le système linéaire, il
faudra donc créer plus de relations qu'il y a d'éléments dans la base des
facteurs.
3.2 Structures de données
Pour manipuler les grands entiers dépassant les 32 ou 64 bits des machines
actuelles, Java propose la classe BigInteger, qui contient toutes les
opérations arithmétiques nécessaires pour le projet.
4 Extensions
Le sujet se prête à une multitude d'améliorations algorithmiques:
Références
- [1]
-
Leonard Adleman.
A subexponential algorithm for the discrete logarithm problem with
applications to cryptography.
In Proceedings of the 20th Annual Symposium on Foundations of
Computer Science, pages 55–60, New York, 1979. IEEE.
- [2]
-
Don Coppersmith, Andrew M. Odlyzko, and Richard Schroeppel.
Discrete logarithms in GF(p).
Algorithmica, 1:1–15, 1986.
- [3]
-
Whitfield Diffie and Martin E. Hellman.
New directions in cryptography.
IEEE Transactions on Information Theory, 22(6):644–655,
November 1976.
Ce document a été traduit de LATEX par HEVEA