84
Science de la sécurité du système d’information
Deuxième partie
n, C et e étant connus. Encore une fois, dans le monde des réels, la solution est triviale : M =
e
√
C. Mais dans le monde modulaire la solution est M =
e
√
C mod n,
et il n’y a pas d’algorithme rapide connu pour la calculer, même pour de petites
valeurs de e. Ainsi, trouver la racine cubique modulo n d’un nombre y est un
problème qui n’est toujours pas résolu.
En fait la seule attaque possible (outre la recherche de failles de réalisation du
logiciel) consisterait à trouver p et q par recherche des facteurs de n, ce que
l’on appelle la factorisation du nombre n. La factorisation permettrait de calculer
z = φ(n) = (p − 1)(q − 1). Le nombre secret d est tel que e.d ≡ 1 mod z. d est
un nombre du même ordre de grandeur que z, soit un nombre de mille chiffres
binaires. Ce calcul serait réalisable, mais l’obstacle est que la factorisation n’est pas
un problème résolu, et qu’il est donc impossible, dans le cas général, de calculer p,
q et z.
Les réalisations industrielles ont longtemps utilisé, et utilisent parfois encore
e = 3. De nos jours e = 2 16 + 1 = 65 537 est populaire. Avec un tel choix, d
est du même ordre de grandeur que n, soit d ≈ 2 1024 . L’élévation à une puissance
de cet ordre peut être réalisée efficacement par des algorithmes de type « élévation au carré et multiplication » (square and multiply), qui prennent moins d’une
seconde dans une carte à puce.
POUR EN SAVOIR PLUS
Le lecteur trouvera des explications mathématiques supplémentaires dans l’ouvrage de
Cormen, Leiserson et Rivest (le R de RSA) [35] ou dans celui de Menezes, van Oorschot
et Vanstone [79], ou encore, de façon plus abordable, dans ceux de Gilles Dubertret [43]
ou d’Albert Ducrocq et André Warusfel [44]. Au demeurant, il est stupéfiant de constater
que les découvertes prodigieuses de Diffie, Hellman, Merkle, Rivest, Shamir et Adleman
reposent sur des bases mathématiques déjà entièrement établies par Leonhard Euler
(1707–1783), sinon par Pierre de Fermat (1601–1665), et que, hormis Donald Knuth
dans les années 1960, personne n’y avait pensé avant. Et si personne n’y avait pensé, c’est
qu’avant l’invention de l’informatique moderne les méthodes cryptographiques dont nous
venons de donner un bref exposé étaient non seulement irréalisables, mais impensables.
Science de la sécurité du système d’information
Deuxième partie
n, C et e étant connus. Encore une fois, dans le monde des réels, la solution est triviale : M =
e
√
C. Mais dans le monde modulaire la solution est M =
e
√
C mod n,
et il n’y a pas d’algorithme rapide connu pour la calculer, même pour de petites
valeurs de e. Ainsi, trouver la racine cubique modulo n d’un nombre y est un
problème qui n’est toujours pas résolu.
En fait la seule attaque possible (outre la recherche de failles de réalisation du
logiciel) consisterait à trouver p et q par recherche des facteurs de n, ce que
l’on appelle la factorisation du nombre n. La factorisation permettrait de calculer
z = φ(n) = (p − 1)(q − 1). Le nombre secret d est tel que e.d ≡ 1 mod z. d est
un nombre du même ordre de grandeur que z, soit un nombre de mille chiffres
binaires. Ce calcul serait réalisable, mais l’obstacle est que la factorisation n’est pas
un problème résolu, et qu’il est donc impossible, dans le cas général, de calculer p,
q et z.
Les réalisations industrielles ont longtemps utilisé, et utilisent parfois encore
e = 3. De nos jours e = 2 16 + 1 = 65 537 est populaire. Avec un tel choix, d
est du même ordre de grandeur que n, soit d ≈ 2 1024 . L’élévation à une puissance
de cet ordre peut être réalisée efficacement par des algorithmes de type « élévation au carré et multiplication » (square and multiply), qui prennent moins d’une
seconde dans une carte à puce.
POUR EN SAVOIR PLUS
Le lecteur trouvera des explications mathématiques supplémentaires dans l’ouvrage de
Cormen, Leiserson et Rivest (le R de RSA) [35] ou dans celui de Menezes, van Oorschot
et Vanstone [79], ou encore, de façon plus abordable, dans ceux de Gilles Dubertret [43]
ou d’Albert Ducrocq et André Warusfel [44]. Au demeurant, il est stupéfiant de constater
que les découvertes prodigieuses de Diffie, Hellman, Merkle, Rivest, Shamir et Adleman
reposent sur des bases mathématiques déjà entièrement établies par Leonhard Euler
(1707–1783), sinon par Pierre de Fermat (1601–1665), et que, hormis Donald Knuth
dans les années 1960, personne n’y avait pensé avant. Et si personne n’y avait pensé, c’est
qu’avant l’invention de l’informatique moderne les méthodes cryptographiques dont nous
venons de donner un bref exposé étaient non seulement irréalisables, mais impensables.