Grands nombres premiers

Cryptographie RSA

François DE M ARÇAY
Département de Mathématiques d’Orsay
Université Paris-Sud, France

1. Limitations physiques
Soit un nombre donné quelconque n > 1, représenté par exemple en base 10 comme
suite finie de chiffres appartenant à {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Le Crible d’Eratosthène est la méthode la plus simple et la plus directe pour déterminer
si un tel nombre entier n donné est un nombre premier, ou un nombre composé.

L’algorithme procède par élimination : il s’agit de supprimer de la table complète de tous

les entiers allant de 2 jusqu’à n tous les entiers qui sont multiples d’un entier inférieur à n.
À la fin il ne restera donc que les entiers qui ne sont multiples d’aucun entier, c’est-à-dire,
il ne restera plus que les nombres premiers.
On commence tout simplement par rayer tous les multiples de 2, puis tous les multiples
de 3, puis tous les multiples de 5, puis tous les multiples de 7, et ainsi de suite, jusqu’aux
multiples du dernier entier premier k tel que k 2 6 n.
1
2 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France

√
On peut en effet s’arrêter à k ≈ n, car tous les entiers non premiers ont déjà été rayés
précédemment !

Cependant, ce procédé direct est limité dans la pratique à cause du très grand nombre
d’opérations qu’il exige.

In a very real sense, there are no large numbers : Any explicit integer can be said to be
‘small’. Indeed, no matter how many digits or towers of exponents you may write down, there are
only finitely many natural numbers smaller than your candidate, and finitely many that are larger.
Though condemned always to deal with small numbers, we can at least strive to handle numbers
that are larger than those that could be handled before. Richard Crandall, Carl Pomerance

Affirmation de philosophie des mathématiques. L’ensemble complet de tous les nombres

premiers n’est pas connaissable comme totalité donnée de manière actuelle, c’est-à-dire de
manière accessible, effective, concrète, visible, « vraiment présente ». 

La raison métaphysique simplette de cette limitation est claire : l’infini actuel n’existe
pas.

Afin de mieux comprendre en quoi il y a réellement limitation, spéculons quelque peu.

Supposons par exemple que l’on rêve d’imprimer la liste complète de tous les nombres
entiers premiers qui sont inférieurs à un certain entier nombre assez grand, disons pour se
satisfaire de possèder un petit « trésor mathématique ». Va-t-on y parvenir ?

Définition 1.1. Pour x > 1 entier, on note classiquement π(x) le nombre d’entiers premiers
inférieurs à x :

π(x) := Card p ∈ P premiers avec p 6 x .



On connaît la valeur exacte de π(x) pour des x contenant une vingtaine de chiffres en
base 10.
 1. Limitations physiques 3

Prenons par exemple x = 1020 . Il se trouve qu’à notre époque, on connaît la valeur
exacte :
π 1020 = 2 220 819 602 560 918 840

≈ 2 · 1018 .
De tels nombres n’ont « qu’une vingtaine de chiffres », ils peuvent donc sembler
« petits » — mais attention aux illusions !
Question 1.2. Si on connaît la valeur exacte de π(1020 ), cela semble vouloir dire que l’on
connaît effectivement tous les nombres premiers p 6 1020 , mais cela est-il bien vrai ?
En fait, non ! Même si chacun de ces ≈ 2 · 1018 nombres pouvait être représenté par un
seul caractère d’imprimerie ou un seul bit informatique, nous affirmons qu’il serait néan-
moins totalement impossible de les voir tous, ou de les stocker tous dans des ordinateurs.
En effet, considérons par analogie le nombre record de décimales du nombre d’Archi-
mède :
π = 3, 141592653589793238462643383279502884279169399375 · · ·,
qui, depuis octobre 2011, va jusqu’à 10 000 milliards, ce qui nous fait donc :
1013
décimales, c’est-à-dire 1013 caractères d’imprimerie, ou bits sur un ordinateur, un nombre
vraiment inférieur à 2 · 1018 . Mais même ce nombre se situe à la limite du visible.
Question 1.3. Combien de livres de 500 pages comportant 40 lignes chacune avec 80 ca-
ractères seraient nécessaires pour montrer à l’humanité éclairée les 1013 décimales connues
du nombre π ?
Dans un seul livre, on peut imprimer :
500 × 80 × 40 = 1 600 000
décimales, et donc il faudrait environ :
10 000 000 000 000
= 6 250 000,
1 600 000
4 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France

livres, environ la moitié des quatorze millions de livres que possède et conserve la Biblio-
thèque Nationale de France.
Pour faire voir les ≈ 2 · 1018 nombres premiers inférieurs à 1020 , il faudrait alors au
moins :
1018−13 = 100 000
bibliothèques de cette taille de par le monde. En poussant jusqu’à 5 chiffres de plus :
Conclusion 1.4. Pour des raisons purement physiques, on ne pourra jamais « voir » tous
les nombres premiers ayant un nombre de chiffres 6 25 en base 10. 

Rien n’est logique et rien ne semble absurde comme l’océan. Cette dispersion de soi-même
est inhérente à sa souveraineté et est un des éléments de son ampleur. Victor Hugo

Ainsi dans cette immensité, se noie ma pensée : et le naufrage m’est doux dans cette mer.
Leopardi

Le paradoxe contre-paradoxal 1, c’est que les théoriciens des nombres réussissent quand
même à capturer et à manipuler quelques gros poissons nombres premiers ayant jusqu’à
100, 200, 300 chiffres ! Les mathématiques évoluent alors comme dans une mer immense
de nombres gigantesques, en connaissant très peu de nombres premiers parmi ceux qui
comportent jusqu’à des dizaines de millions de chiffres en base 10.
Question 1.5. Comment engendrer des nombres premiers qui possèdent un très grand
nombre de chiffres ?

2. Grands nombres premiers : pêche à la ligne

Fermat avait proposé, nous l’avons vu, une formule simple qui lui semblait produire des
nombres premiers de plus en plus grands. Le hic, avec ces nombres de Fermat :
n
Fn := 22 + 1,
c’est qu’ils ne sont presque jamais premiers, en tout cas, pour ce qui est de ceux que nous
connaissons actuellement.
En 1732, Euler a découvert la factorisation :
F5 = 4294967297
= 641 · 6700417.
En 1882, Landry a montré que le nombre de Fermat suivant est aussi composé :
6
F6 = 2 2 + 1
= 18446744073709551617
= 274177 · 67280421310721.
No prime Fn has ever been found beyond F4 , so Fermat’s conjecture has not proved a very
happy one. G.H. Hardy, E.M. Wright

Aux alentours de l’année 2005, l’état des connaissances concernant les nombres de Fer-
mat jusqu’à F24 est résumé au moyen du tableau suivant.

1. Ce n’est parce qu’on ne peut pas tout connaître qu’il est impossible de connaître un tout petit peu d’un
trop grand tout.
 2. Grands nombres premiers : pêche à la ligne 5

Dans ce tableau, tous les nombres explicitement écrits sont des nombres premiers, et la
lettre « P » désigne un grand facteur entier dont on a démontré qu’il est premier, tandis que
la lettre « C » désigne un très grand facteur composé, dont on ne connaît pas nécessairement
les facteurs premiers.
Néanmoins, comme les mathématiques savent produire un très grand nombre de for-
mules très compliquées, on peut toujours espérer qu’une modification de la formule de
Fermat pourrait engendrer une collection infinie de nombres premiers.

Question 2.1. Existe-t-il une formule générale simple F (k) dépendant d’un entier k > 1
dont toutes les valeurs :

F (1) = 2, F (2) = 3, F (3) = 5, F (4) = 7, F (5) = 11, ......,

décrivent exactement la suite des nombres premiers ?

Aucune telle formule magique n’est connue sur Terre, et il est très probable qu’il n’en
existe pas non plus sur les autres planètes habitées de l’Univers.
On peut alors abaisser les ambitions d’un cran.

Question 2.2. Existe-t-il une formule générale simple G (k) dépendant d’un entier k > 1
dont les valeurs contiennent au moins une infinité de nombres premiers ? (Sans demander,
toutefois, que toutes les valeurs G (1), G (2), G (3), . . ., soient des nombres premiers.)

Par exemple, la formule :

G (k) := k 2 − k + 41
ne produit que des valeurs entières premières pour :

0 6 k 6 40,
6 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France

à savoir les valeurs :

41, 41, 43, 47, 53, 61, 71, 83, 97, 113, 131,
151, 173, 197, 223, 251, 281, 313, 347, 383, 421,
461, 503, 547, 593, 641, 691, 743, 797, 853, 911,
971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601,
mais à partir de k = 41, ces nombres cessent d’être toujours premiers :
41·41, 41·43, 1847, 1933, 43·47, 2111, 2203, 2297, 2393, 47·53,
quoiqu’il y en ait toujours pas mal qui soient premiers.
Problème mathématique ouvert. Existe-t-il une infinité de nombre premiers dans la suite :

∞
k 2 + 1 k=1 ?
ou encore dans la suite :

∞
k 2 − k + 41 k=1
?

De même, on constate à la main ou sur un ordinateur que la suite :

∞
k 2 − 79 k + 1601 k=1
ne prend que des valeurs entières premières pour :
0 6 k 6 79,
mais pour k = 80 on a :
802 − 79 · 80 + 1601 = 41 · 41.
Il n’est en fait pas difficile de constater que ce phénomène est général.
Théorème 2.3. Aucun polynôme non constant à coefficients entiers :
G (x) ∈ Z[x]
ne peut prendre une suite complète de valeurs :

∞
G (k) k=K
qui sont toutes des nombres premiers pour k > K  1 assez grand.
Démonstration. Quitte à remplacer G par − G , on peut supposer que le coefficient de tête
de G est positif :
G (x) = g0 xd + · · · + gd−1 x + gd (d = deg G , g0 > 0),

de telle sorte que G (k) tend vers +∞ lorsque k → ∞.

Ainsi, en un entier k assez grand, la valeur du polynôme :
G (k) = a0 k d + · · · + ad−1 k + gd
=: `
 2. Grands nombres premiers : pêche à la ligne 7

est certainement > 2. L’astuce élémentaire, pour conclure, consiste alors à observer, grâce
la formule du binôme de Newton (exercice), que pour tout entier λ > 1 :

d
G λ ` + k = g0 λ ` + k + · · · + gd−1 λ ` + k + gd

= G (k) + multiple de `
= multiple de `
= nombre non premier,
ce qui montre que G ne prend pas de valeurs entières premières sur la suite infinie (λ ` +
k)∞
λ=1 . 
L’énoncé suivant, dont la démonstration peut faire l’objet d’un mémoire de Master 1 à
l’université, utilise de magnifiques outils d’Analyse Complexe.
Théorème 2.4. [Dirichlet] Pour tout couple d’entiers a, b > 1 premiers entre eux :
a ∧ b = 1,
la suite des valeurs :
∞
a + bk k=1
contient une infinité de nombres premiers. 
Pour formuler un énoncé plus fin, rappelons que le Théorème des nombres premiers
stipule que la fonction :
π(x) := Card 2 6 p 6 x : p ∈ P est premier


se comporte asymptotiquement comme :

x
π(x) ∼ .
log x
Théorème 2.5. [Dirichlet affiné] Pour tout couple d’entiers a, b > 1 premiers entre eux,
dans la progression arithmétique infinie :
a, a + 2 b, a + 3 b, a + 4 b, a + 5 b, ......,
le nombre de nombres qui sont premiers :
π x; a, b := Card k ∈ N avec a + bk 6 x tels que a + b k ∈ P



est asymptotiquement égal à :

1
π x; a, b ∼ π(x)
ϕ(b)
1 x
∼ ,
ϕ(b) log x
où ϕ(b) = Card {1 6 b0 6 b : b0 ∧ b = 1} est l’indicateur d’Euler. 
En tout cas, que ce soit au moyen de formules linéaires k 7−→ a k + b ou, conjec-
turalement, au moyen de formules quadratiques telles que k 7−→ k 2 + 1, même s’il elles
produisent une infinité de nombres premiers, il reste en général difficile, comme le dit l’An-
cien Testament, de séparer le bon grain de l’ivraie, à savoir il reste difficile de déterminer
si une valeur G (k) est un nombre premier ou un nombre composé.
8 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France

Mais revenons à notre Question 1.5 qui demandait comment produire de grands nombres
premiers. Il est clair qu’il vaut mieux utiliser des formules exponentielles, car les poly-
nômes croissent moins vite que les exponentielles.
Il est intéressant de comparer le destin des nombres de Fermat à celui d’une autre conjec-
ture célèbre, qui concerne les nombres premiers de la forme :
2n − 1.
Théorème 2.6. Si, pour un entier n > 2, le nombre :
an − 1
est premier, alors a = 2 et n lui-même est premier.
Démonstration. En effet, si a > 3, alors on a la factorisation :
an − 1 = (a − 1) an−1 + · · · + a + 1 .

Donc on a a = 2 nécessairement.
Ensuite, si n = k l est composé, on peut à nouveau constater (exercice) que 2k − 1 et
2 − 1 divisent 2n − 1.
l

Définition 2.7. Un nombre de Mersenne 2 est un nombre premier qui s’écrit sous la forme :
Mp := 2p − 1,
avec p lui-même entier premier.

En 1644, Mersenne affirmait que Mp est premier pour les valeurs :

p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257,
et que Mp est composé pour les 44 autres valeurs de p premier inférieures à 257.
La première erreur 3 dans la liste de Mersenne n’a été trouvée qu’en 1886, lorsque Per-
vusin et Seelhoff découvrirent que M61 est en fait premier. Par la suite, d’autres erreurs
furent trouvées, et la liste de Mersenne commença à ne plus être prise au sérieux.
En 1876, Lucas mis au point une méthode pour tester si Mp est premier, méthode qu’il
utilisa pour montrer que M127 est premier.
Entre 1876 et 1951, c’est-à-dire pendant trois-quarts de siècle, le nombre de Lucas :
2127 − 1 = 170141183460469231731687303715884105727
demeura le plus grand nombre premier connu.
2. Marin Mersenne, religieux érudit et mathématicien français du XVIIème siècle.
3. En 1732, Euler affirmait que M41 et M47 sont premiers, ce qui n’était pas vrai (et n’est toujours pas
vrai aujourd’hui).
 3. Principe de la crytographie RSA 9

En 2005, tous les nombres premiers de Mersenne connus étaient ceux qui apparaissent
dans le tableau suivant.

Les prochains sont les suivants :

M30402457 = 230402457 − 1,
M32582657 = 232582657 − 1,
M37156667 = 237156667 − 1,
M42643801 = 242643801 − 1,
M43112609 = 243112609 − 1,
M57885161 = 257885161 − 1,
ce qui veut dire que tous les Mp intercalés qui n’apparaissent pas sont composés.
Le dernier, découvert en janvier 2013 :
257885161 − 1,
est composé de plus de 17 millions de chiffres en base 10, et son écriture complète rempli-
rait une bonne dizaine de livres de 500 pages environ.
À titre de comparaison, il faut moins de 100 chiffres pour effectuer le décompte du
nombre de particules (neutrons, protons et électrons) contenues dans tout l’univers !
Après tous ces préliminaires qui se sont étendus en longueur, il est temps, maintenant,
d’entrer dans le vif du sujet.

3. Principe de la crytographie RSA

Our ability to uncover large primes and prove them prime has outstripped our ability to factor,
a situation that gives tome comfort to cryptographers. Richard Crandall, Carl Pomerance
10 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France

Le scénario est le suivant. Bernard 4 souhaite envoyer secrètement un message à sa dul-

cinée, Alice.
En effet, il est hors de question que des oreilles indiscrètes interceptent ce qui transite
dans les canaux de leur communication intime.
L’idée la plus simple, qui remonte à l’Antiquité, consiste à coder, ou à chiffrer, le mes-
sage, c’est-à-dire à le rendre illisible par toute autre tierce personne.

Le code de Cæsar — Julius, qui écrivait à Cléopâtre — permute simplement toutes les
lettres de l’alphabet :
a 7−→ d, b 7−→ e, c 7−→ f, ......, y 7−→ b, z 7−→ c.
Par exemple, Cæsar signera sa lettre enflammée par :
F dhvdu.

Malheureusement, ce cryptosystème est trivialement facile à casser : il y a seulement 26

possibilités à tester, et une fois que la correspondance pour une seule lettre a été trouvée,
toutes les autres s’ensuivent car la permutation est circulaire.
Plus astucieusement, on pourrait utiliser l’une des :
26! ≈ 4 · 1026
permutations de l’alphabet à 26 lettres. Dans un tel cryptosystème qui demeure encore
assez primitif, casser le code, cela consiste à reconstituer la permutation. Mais si l’on sait
dans quel langage le message est codé, une simple anayse de fréquence des lettres qui
apparaissent permet assez rapidement de reconstituer la totalité du message.

4. Dans la langue anglo-saxonne, Bernard est appelé Bob.

 3. Principe de la crytographie RSA 11

Exeunt, donc les codes trop antiques de Julius Cæsar et Cléôpatre, place à la science
high-tech d’Alice et de Bernard !
La seule méthode de codage dont on démontre qu’elle est entièrement sécurisée, au sens
de l’informatique théorique, est la suivante.
Soit ν > 1 le nombre de lettres du message à transmettre, par exemple, le message
« ECUREUIL» réduit pour simplifier à un seul mot. On choisit une autre séquence auxiliaire
de ν lettres produites au hasard, par exemple la séquence « DFTXMQIB ». On effectue la
correspondence la plus simple entre les 26 lettres de l’alphabet et les nombres de 0 à 25 :
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

On place le message à transmettre ainsi que son compagnon aléatoire l’un au-dessus de
l’autre :
4 2 20 17 4 20 8 11
E C U R E U I L
D F T X M Q I B
3 5 19 23 12 16 8 1

On effectue l’addition modulo 26 de leurs chiffres respectifs, et on retranscrit le résultat en

lettres :
7 7 14 15 11 16 18 12
H H O P L Q S M
ce qui est le code du message d’origine.
C’est le seul procédé de codage qui soit démontrablement incassable.
Mais il présente quelques inconvénients. Premièrement, les clés doivent avoir la même
longueur que les messages. Deuxièmement, il est préférable de ne pas ré-utiliser plusieurs
fois des parties d’une même séquence aléatoire de lettres.
Le système de cryptographie le plus répandu et qui a supplanté tous ses concurrents est
le système dit RSA — voir la Section 5 infra pour des informations historiques —, et il
est basé sur l’utilisation de grands nombres premiers, le plus complexe des mystères
mathématiques.
L’idée profonde est que la personne, Alice, qui souhaite recevoir un message secret
de Bernard (de la CIA), prépare à l’avance chez elle (à la Maison Blanche) certaines
données qui lui permettront à elle seule de comprendre les messages que Bernard aura
envoyés. Alice se prépare, en secret, à devenir la seule personne au monde qui pourra
comprendre ce que voudra lui dire Bernard !
Si on admet temporairement que le message de Bernard peut être découpé en blocs
de caractères d’imprimerie ayant des longueurs approximativement égales, chaque
morceau correspondant d’une certaine manière à un nombre, le problème reviendra
alors à envoyer secrètement une suite de nombres entiers, écrits en base 10, de tailles
approximativement égales. Dans la Section 4, nous justifierons un tel codage prélimi-
naire, qui transforme des blocs de caractères d’imprimerie en une suite de nombres
entiers.

Algorithme: Cryptographie RSA

 Un bloc du message de Bernard est représenté par un nombre m ∈ N de taille
raisonnable.
12 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France

 Alice, qui est cryptographe professionnelle, choisit dans sa collection personnelle

deux très grands nombres premiers, soient :
p et q,
comportant tous deux environ 300 chiffres en base 10. Lorsque soit p, soit q est trop
petit, le protocole a des risques d’être attaqué.
 Alice multiplie ces deux nombres, ce qui est très facile, et elle obtient le nombre :
n := p q,
qui comporte environ 600 chiffres.
 Alice rend public ce nombre n, mais elle conserve secrètement chez elle les deux pré-
cieux facteurs premiers p et q. Autrement dit, Bernard, qui fait partie du public d’Alice,
peut prendre connaissance du nombre n, par exemple sur internet, et le monde entier,
d’ailleurs, peut aussi prendre connaissance de n. L’intérêt fantastique du protocole
RSA, c’est que Bernard n’aura aucunement besoin de connaître les secrets d’Alice pour
pouvoir lui écrire sans que personne n’y comprenne rien. Autrement dit, aucun secret
ne transitera dans les canaux de communication, tel est le génie du RSA !
Le secret reste intérieur !
 Sur le plan pratique, la sécurité du protocole RSA tient au fait qu’il est démontra-
blement extrêmement difficile de factoriser, même avec un réseau d’ordinateurs su-
perpuissants, des nombres entiers à environ 600 chiffres. Donc tout le monde a beau
connaître n, personne n’est assez fort pour retrouver les deux facteurs premiers p et
q, à moins d’y passer des milliards de milliards d’années.

 Ensuite, Alice considère le groupe multiplicatif des éléments inversibles :


×
Z (p − 1)(q − 1)Z ,
et en appliquant des recherches aléatoires automatiques répétées, elle finit par trouver
un élément inversible : 
×
d ∈ Z (p − 1)(q − 1)Z ,
dont la taille soit assez grande pour que le protocole ne puisse pas être cassé.
 Alice détermine alors l’unique inverse e de d dans ce groupe, qui satisfait donc :
d e ≡ 1 mod (p − 1)(q − 1).
 Enfin, Alice rend aussi public cet inverse e, et alors, ce qu’on appelle la clé publique
d’Alice, visible par tout le monde dans le monde entier, est le couple :
(n, e),
 3. Principe de la crytographie RSA 13

que Bernard se hâte de noter sur ses ordinateurs.

 Tout est maintenant prêt pour que Bernard se décide enfin à coder puis à envoyer
son message, qui est un nombre m ∈ N, car . . . Alice est prête !
 C’est très simple : en utilisant l’Algorithme (très efficace !) d’exponentiation mo-
dulaire, Bernard prend son entier m et lui fait subir :
m 7−→ me mod n,
ce qu’il peut effectivement faire, puisqu’il connaît n et e. De la sorte, le message initial
signifiant m est remplacé par un message me mod n dans lequel un très grand désordre
numérique a été introduit.
 Bernard envoie alors à Alice ce message illisible me mod n, que le KGB n’essaie
même plus d’intercepter sur internet.
 Mais comment Alice va-t-elle réussir à déchiffer cela ?
 C’est très simple, Alice fait subir à me une nouvelle exponentiation modulaire :

d
me mod n 7−→ me mod n
= m mod n,
et la Proposition 3.1 ci-dessous stipule que Alice retrouvera bien m.

 Afin d’assurer qu’il n’y ait aucune ambiguïté dans la reconstitution de m à travers
le module n, il suffit que Bernard s’arrange à l’avance pour découper son message en
blocs codés par des entiers m qui soient tous 6 n − 1.

Proposition 3.1. Étant donné deux nombres entiers premiers p, q ∈ P, et étant donné un
élément inversible : 
×
d ∈ Z (p − 1)(q − 1)Z
d’inverse e :
1 ≡ d e mod (p − 1)(q − 1),
pour tout entier m ∈ Z, on a toujours :

d
me mod p q ≡ m mod p q.
Démonstration. Par hypothèse, il existe un entier k ∈ Z tel que :
e d = 1 + k (p − 1)(q − 1).
14 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France

Assertion 3.2. On a :
me d ≡ m mod p.
Preuve. Deux cas sont à considérer. Premièrement, lorsque p divise m, on gagne facile-
ment :
me d ≡ 0 mod p
≡ m mod p.
Deuxièmement, lorsque p ne divise pas m, d’où pgcd(p, m) = 1, le petit Théorème de
Fermat donne :
mp−1 ≡ 1 mod p,
d’où :
me d = m · mk (p−1) (q−1)
≡ m · 1 mod p
et là encore, on a gagné. 
Par symétrie, on obtient aussi :
me d ≡ m mod q.
Autrement dit, me d −m est multiple de p et est multiple de q, et comme p et q sont premiers,
c’est que me d − m doit être (exercice mental) multiple de leur produit p q, ce qui conclut.

Le système RSA est dit à clé publique, ce qui signifie que :
 ni l’algorithme de calcul ni la clé de codage ne sont cachés ;
 la connaissance de la clé publique d’Alice permet à tous ses interlocuteurs potentiels :
Bernard, Gustave, Gédéon, Prosper, Léopold, de crypter les messages qu’ils lui destinent,
mais seule Alice peut décrypter les messages qu’elle reçoit, grâce à sa clé de décodage
privée, qu’elle cache soigneusement.
Les clés publiques peuvent être publiées dans un annuaire ou sont obtenues, à la de-
mande, en contactant préalablement celui à qui l’on veut faire parvenir un message.
Ce type de système possédant une clé de décodage différente de la clé de codage (le sys-
tème est dissymétrique) présente un avantage sur les systèmes classiques (dits symétriques,
car une seule et même clé sert à la fois au codage et au décodage) : avant un échange, les
deux interlocuteurs n’ont pas besoin de se rencontrer pour convenir d’une clé secrète, qui
devra rester connue d’eux seuls, ni n’ont besoin de faire circuler — sur un réseau informa-
tique ou autre — une clé secrète, transmission qui bien sûr engendre un risque. Seule la clé
publique, insuffisante pour le décryptage, est connue préalablement aux échanges cryptés
entre les deux interlocuteurs.
Pour terminer cette section, posons-nous la :
Question 3.3. Combien de temps faudrait-il pour factoriser un entier n à 600 chiffres en
base 10 en appliquant l’algorithme naïf d’Eratosthène ?
√
Il s’agit de supprimer tous les multiples de nombres premiers p 6 10600 = 10300 . Le
nombre de nombre premiers inférieurs à 10300 est approximativement égal à :
10300
≈ 1, 5 · 10297 .
log 10300
 4. Codages préliminaires 15

Un processeur ayant une forte puissance de 10 Ghz (optimiste) fait environ 1010 opéra-
tions à la seconde.
Supposons sans sourciller qu’il y ait 1011 tels processeurs de part le monde (ce qui ferait
10 processeurs par être humain !).
On obtiendrait une puissance de calcul de 1021 opérations à la seconde.
Puisqu’il y a 60 · 60 · 24 · 365 ≈ 3 · 107 secondes dans une année, cela ferait au mieux
3 · 1028 opérations par an.
En supposant (fort abusivement !) qu’il n’y ait qu’une seule opération à effectuer par
nombre premier dans le crible d’Eratosthène, il faudrait donc un nombre d’années égal à
environ :
1.5 · 10297
≈ 5 · 10268 ,
3 · 1028
ce qui est insensé !

4. Codages préliminaires
Le texte de Bernard est certainement trop long pour être codé d’un seul tenant comme
un unique nombre m ∈ Z.
Je regrette les temps de la grande Cybèle
Qu’on disait parcourir, gigantesquement belle,
Sur un grand char d’airain, les splendides cités ;
Son double sein versait dans les immensités
Le pur ruissellement de la vie infinie,
L’Homme suçait, heureux, sa mamelle bénie,
Comme un petit enfant, jouant sur ses genoux.
Parce qu’il était fort, l’Homme était chaste et doux. Rimbaud

Il faut donc le découper en blocs de caractères d’imprimerie ayant tous une longueur
raisonnable approximativement équilibrée, par exemple ici, vers par vers :
 
Je regrette les temps de la grande Cybèle
 
Qu’on disait parcourir, gigantesquement belle,
 
Sur un grand char d’airain, les splendides cités ;
 
Son double sein versait dans les immensités
 
Le pur ruissellement de la vie infinie,
 
L’Homme suçait, heureux, sa mamelle bénie,
 
Comme un petit enfant, jouant sur ses genoux.
 
Parce qu’il était fort, l’Homme était chaste et doux. Rimbaud

Pour simplifier, nous supposerons que les caractères d’imprimerie que Bernard utilise
se réduisent aux lettres standard de l’alphabet :
a b c d e f g h i j k l m n o p q r s t u v w x y z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
16 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France

avec aussi un espace blanc :

L
26

ainsi que les lettres majuscules :

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

et nous supposerons que Bernard pré-code ces caractères de 0 à 52. Dans la vraie vie de la
poésie, on doit coder avec une centaine de caractères. Dans la vraie vie des mathématiques,
plusieurs centaines sont nécessaires.
Soit alors une portion quelconque du texte de Bernard qui comporte un nombre ν > 1
de caractères :
`0 `1 . . . `ν−1 ,
appartenant tous à cet alphabet simplifié de lettres, espace, majuscules. Le précodage asso-
cie donc à cette portion une suite de ν nombres :
m0 m1 . . . mν−1
appartenant tous à {0, 1, . . . , 52}. Mais comme les ordinateurs sont en général construits
pour afficher en base 10 les calculs qu’ils font en base 2, il faut pouvoir transcrire cela en
un certain nombre :
m ∈ N,
écrit en base 10.
L’idée la plus naturelle consiste alors à faire représenter la suite des mλ par le nombre
écrit en base 53 :
m := m0 + m1 · 531 + · · · + mν−1 · 53ν−1 ,
et l’ordinateur calculera alors automatiquement cette somme comme un certain nombre
écrit en base 10. La correspondance est bi-univoque (exercice mental), et le nombre m est
toujours majoré par :
m 6 52 + 52 · 53 + · · · + 52 · 53ν−1
= 52 1 + 53 + · · · + 53ν−1

53ν − 1
= 52
53 − 1
ν
= 53 − 1.
Rappelons enfin que pour qu’Alice retrouve l’entier m sans ambiguïté modulo n, il est
préférable que Bernard découpe son texte en blocs de caractères auxquels correspondront
des nombres :
m 6 n − 1,
ce qui revient à demander que :
53ν 6 n,
à savoir à assurer que la longueur ν des blocs de caractères d’imprimerie soit majorée par :
log n
ν 6 ,
log 53
ce que Bernard peut fort aisément faire, puisque Alice a rendu publique sa clé n ! En ré-
sumé :
 5. RSA : historique et réflexions diverses 17

Proposition 4.1. Pour pré-coder son message dans le langage de l’arithmétique des
nombres entiers, ayant pris connaissance de la clé publique n d’Alice, Bernard découpe
son texte en blocs de caractères d’imprimerie :
  0
`0 . . . `0ν 0 −1
  00
`0 . . . `00ν 00 −1
  000
`0 . . . `000
  0000
`0 . . . `0000
 
`0 . . . `ν−1 ν 000 −1 ν 0000 −1 ......
log n
de longueurs ν, ν 0 , ν 00 , . . . toutes 6 log 53
, et il associe à chacun de ces blocs des nombres
entiers :
   0   00   000   0000 
m m m m m ......

satisfaisant tous m, m0 , m00 , · · · 6 n − 1, qui seront chacun soumis au processus d’expo-

nentiation RSA. 

Dans cette approche, on découpe le message en blocs et on utilise RSA sur chaque bloc.
Dans la vraie vie, il est plus usuel d’utiliser RSA pour chiffrer une clé et d’utiliser ensuite
un chiffrement à clé privée pour faire le chiffrement réel du message. En effet, utiliser RSA
sur plusieurs blocs n’est pas sûr : on peut par exemple savoir si le même bloc est transmis
plusieurs fois.

5. RSA : historique et réflexions diverses

Le système de cryptage RSA a été inventé en 1977 par Rivest, Shamir et Adleman,
dont les initiales forment l’acronyme RSA. Ces trois auteurs avaient décidé de travailler en-
semble pour établir qu’un nouveau système de codage révolutionnaire, dénommé « système
à clé publique » que Diffie et Hellman venaient d’inventer, était une impossibilité logique,
autrement dit, que tout système de cryptage de cette nature devait présenter certaines failles.
Ils ne réussirent pas dans leur projet, mais, au contraire, ils découvrirent un nouveau sys-
tème à clé publique qui supplanta rapidement celui de Diffie et Hellman.
Rappelons que la dissymétrie fondamentale qui sous-tend le protocole, est qu’il est im-
médiatement facile de multiplier deux nombres premiers ayant un grand nombre de chiffres,
alors qu’il est extrêmement difficile de déterminer les facteurs premiers d’un grand nombre
donné. Si l’on s’y prend naïvement, il faut diviser ce nombre par beaucoup de nombres plus
petits et déterminer le reste : si celui-ci est nul, on a déterminé ainsi un diviseur. Les mathé-
maticiens ont mis au point des moyens plus rapides que les divisions successives, mais le
nombre d’opérations à effectuer reste considérable pour des nombres de taille importante.
Ainsi il est actuellement impossible de « factoriser » des nombres de plus de 300 chiffres,
même avec les ordinateurs les plus rapides et les algorithmes les plus performants.
18 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France

Insistons sur le fait que le jeu numérique élémentaire du protocole RSA est aujourd’hui
un système universel servant dans une multitude d’applications. Au cours des années, il a
devancé tous ses concurrents.

Le RSA est programmé aussi dans les systèmes d’exploitation de Microsoft, d’Apple,
de Sun. Il est intégré dans les cartes Ethernet et dans certaines cartes à puce bancaires.
Un très grand nombre d’institutions gouvernementales, universitaires ou militaires, l’uti-
lisent de façon interne. Le réseau Internet en fait un usage systématique pour assurer la
confidentialité du courrier électronique et authentifier les utilisateurs. Bref :
le protocole RSA est partout !
Sur le plan pratique, les experts recommandaient au début des années 2000 d’utiliser des
nombres n de 768 bits (232 chiffres décimaux) pour mettre en œuvre le RSA dans le cas
de données pas trop importantes, mais ils conseillaient 1 024 bits (309 chiffres décimaux)
pour un usage commercial et 2 048 bits (617 chiffres décimaux) pour avoir une garantie se
prolongeant sur une longue période de temps. Les clés de 512 bits (155 chiffres décimaux),
 5. RSA : historique et réflexions diverses 19

encore utilisées, ne devraient plus l’être, car on a réussi, en août 1999, à factoriser un
nombre n (produit de deux grands nombres premiers) de 512 bits.
La confiance dans la sécurité du RSA n’est pas due à la démonstration théorique que
ce système est sûr, car une telle démonstration n’existe pas. La confiance affichée provient
de l’échec, répété depuis plus de 30 ans, de toutes les tentatives entreprises pour casser
ce système, tentatives qui n’ont conduit qu’à la formulation de quelques recommandations
pour le choix des paramètres p, q, e, d.
Sur le plan théorique, la situation est décevante et le restera certainement longtemps.
Celui qui sait factoriser n = p q retrouve ensuite facilement d. Inversement, les mathéma-
tiques montrent que celui qui connaît n, e et d peut trouver rapidement p et q. La robustesse
du RSA apparaît donc liée à la difficulté de la factorisation. Malheureusement, il n’est pas
exclu que quelqu’un, sans réussir à obtenir d ni p ni q, puisse décrypter un message : au-
trement dit, il n’a pas été prouvé que la difficulté du RSA est équivalente à celle de la
factorisation.
Deux attaques théoriques du RSA sont donc envisageables. Celle passant par la facto-
risation : quiconque sait factoriser les nombres de la taille de n = p q sait lire comme à
livre ouvert tous les messages cryptés par le RSA. Celle contournant la factorisation, dont
personne n’a su établir qu’elle était impossible et pour laquelle, au contraire, on a pro-
posé récemment des arguments indiquant qu’elle devait être sérieusement crainte. Boneh
et Venkatesan ont en effet établi en 1998 que casser le RSA, lorsqu’il est utilisé avec des
exposants e trop petits, n’est pas équivalent à factoriser n.
—————–