Systèmes modernes à clé publique
3. Le cryptage RSA (2)
Généralités
Stéganographie
Cryptanalyse
Littérature
Transpositions
Subs. monoα
Subs. polyα 1 - 2
One-time pad
DES 1 - 2
Clef publique
Knapsack
Diffie-Hellman
RSA 1 - 2
problème
crible quadratique
exemple
combinaison de congruences
exemple
Grands noms
Références
RSA et factorisation
Le secret du RSA, nous l'avons dit, est très lié à la difficulté de factoriser efficacement de grands entiers. Ayant écarté les algorithmes naïfs, par quelles méthodes contemporaines le RSA peut-il être mis en péril ?Le problème
Étant donné un entier n, on cherche à le factoriser.Supposons qu'il existe x et x' tels que x2 ≡ x'2 (mod. n) et x ≢ ±x' (mod. n). Alors x2 − x'2 = (x−x')(x+x') ≡ 0 (mod. n), donc n∧(x−x') et n∧(x+x') sont en facteur dans n.
Le problème devient la détermination de x et x' pour un coût de calcul raisonnable...
Il est intéressant de rappeler que dès 1919, E. Carissan avait réalisé une machine électromécanique automatisant partiellement ce type de recherche !
Crible quadratique
- on se donne un entier x1, puis on forme y1 = x12 mod. n
- puis pour un autre entier x2, on calcule de même y2 = x22 mod. n
- et ainsi de suite. Ces calculs étant rapides, on peut essayer de très nombreux xi
exemple
Soit n = 119- x1 = 16 donne y1 = 162 − 2×119 = 18 ;
- x2 = 11 donne y2 = 112 − 1×119 = 2
On en déduit (16×11)2 ≡ 62 (mod. n). Donc 119 | (16×11)2 − 62 = (176−6)(176+6) = 170×182. Par conséquent, des facteurs de n sont
- 119∧170 = 17 ;
- 119∧182 = 7
Tout ceci ne semble guère systématique -- il ne paraît même pas acquis que le processus converge. Détaillons davantage.
Généralisation : combinaison de congruences
On se donne a priori k (petits) facteurs premiers p1, ..., pk.Comme précédemment, pour plusieurs choix d'entiers xi, on effectue une tabulation des
| yi = xi2 mod. n. |
Toutefois, on ne sélectionne chaque xi que si yi se décompose uniquement en fonction de p1, ..., pk [1].
On construit ensuite la matrice M = (mi,j) ∈ ℳp,k(𝔽2) définie par
| mi,j = vpj(yi) mod. 2 |
(exposant de pj modulo 2 dans la factorisation de yi).
On recherche alors des relations de dépendance linéaire à coefficients dans ℕ* entre les lignes de M, du type :
| α1L1 + ... + αpLp = 0𝔽2k |
alors :
| y1α1 × ... × ypαp est un carré modulo n |
... mais c'est également, par définition, le carré de x1α1 × ... × xpαp -- on peut donc amorcer ainsi la factorisation.
Cette recherche des combinaisons peut être conduite en appliquant à M une méthode de type pivot.
exemple
n = 24163481 ; {pi} = {2, 3, 5, 11, 13, 17}| xi |
yi = xi2 mod. n |
factorisation |
| 6982 |
421362 |
2×36×172 |
| 9832 |
14300 |
22×52×11×13 |
| 10118 |
5720000 |
26×54×11×13 |
| 10162 |
6612320 |
25×5×11×13×172 |
| 13964 |
1685448 |
23×36×172 |
| 14813 |
1953640 |
23×5×132×172 |
| 14847 |
2962080 |
25×32×5×112×17 |
| 15073 |
9724000 |
25×53×11×13×17 |
| 15293 |
14877720 |
23×32×5×11×13×172 |
La matrice M est donc :
|
⎛ |
1̅ | 0̅ |
0̅ | 0̅ | 0̅ | 0̅ |
⎞ |
|
⎜ |
0̅ | 0̅ | 0̅ | 1̅ | 1̅ | 0̅ |
⎟ |
|
⎜ |
0̅ | 0̅ | 0̅ | 1̅ | 1̅ | 0̅ |
⎟ |
|
⎜ |
1̅ | 0̅ | 1̅ | 1̅ | 1̅ | 0̅ |
⎟ |
|
⎜ |
1̅ | 0̅ | 0̅ | 0̅ | 0̅ | 0̅ |
⎟ |
|
⎜ |
1̅ | 0̅ | 1̅ | 0̅ | 0̅ | 0̅ |
⎟ |
|
⎜ |
1̅ | 0̅ | 1̅ | 0̅ | 0̅ | 1̅ |
⎟ |
|
⎜ |
1̅ | 0̅ | 1̅ | 1̅ | 1̅ | 1̅ |
⎟ |
|
⎝ |
1̅ | 0̅ | 1̅ | 1̅ | 1̅ | 0̅ |
⎠ |
et on peut voir [2] que L2 + L3 = 0𝔽2k, ce qui correspond à
(9832×10118)2 ≡ (24×53×11×13)2 mod. n.
Ceci qui nous conduit à poser x = 9832×10118 ≡ 2826252 mod. n et x' = 24×53×11×13 ≡ 286000 mod. n, puis- n∧(x−x') = 24163481∧2540252 = 4441 ;
- n∧(x+x') = 24163481∧3112252 = 5441,
Analyse et perspectives
Quelle est l'efficacité de cet algorithme ? En l'optimisant correctement, on estime que le temps de calcul est borné par exp(d1/3+ε) (où d = log(n). Pour des valeurs typiques de d ∈ [300, 1024], le temps de calcul T est voisin de exp(6d1/3).Plus précisément, T = exp([(64/9+o(1))ln(n)(ln(ln(n))2]1/3) -- une estimation qui repose sur des arguments heuristiques.
Cela fait des méthodes à base de crible la plus sérieuse source d'attaque sur le RSA à l'heure actuelle.
Un challenge de factorisation était organisé jusqu'en 2007 [3] par la société RSA Labs. Le dernier record en date est "RSA-768" (768 bits, soit 232 chiffres décimaux) le 12/12/2009. Le traitement équivalait à 2000 ans de calcul d'un ordinateur simple. RSA Labs recommande au moins 200 chiffres pour un cryptage estimé sûr jusqu'en 2030 au moins, voire bien au-delà dans le cas d'un cryptage sur 2048 bits -- sauf percée mathématique.
Notes
[1] Il n'y a rien là de paradoxal. Ce n'est pas une factorisation générale, puisqu'il n'y a qu'un nombre limité de facteurs à tester. Un xi qui ne convient pas est rejeté très rapidement.[2] entre autres combinaisons, que nous vous laissons découvrir
[3] Elle ne l'estime plus nécessaire maintenant.