Cryptographie à clef publique

Cécile Schryve - Laurent Gajny

24 mai 2010

1
Table des matières
1 Clef secrète, clef publique 3
1.1 Cryptographie à clef secrète . . . . . . . . . . . . . . . . . . . 3
1.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Quelques exemples . . . . . . . . . . . . . . . . . . . . 5
1.2 Cryptographie à clef publique . . . . . . . . . . . . . . . . . . 6
1.3 Clef publique contre Clef privée . . . . . . . . . . . . . . . . . 7

2 Eléments d’Algèbre 9
2.1 Le petit théorème de Fermat . . . . . . . . . . . . . . . . . . . 9
2.2 Le groupe multiplicatif . . . . . . . . . . . . . . . . . . . . . . 10
2.3 La fonction ϕ d’Euler . . . . . . . . . . . . . . . . . . . . . . . 10

3 Diffie-Hellman et RSA 11
3.1 Echange de clef Diffie-Hellman . . . . . . . . . . . . . . . . . . 11
3.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.2 Outils mathématiques et algorithmes . . . . . . . . . . 12
3.2 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.1 Avantages et inconvénients du cryptosystème . . . . . 16
3.2.2 Le protocole RSA . . . . . . . . . . . . . . . . . . . . . 16
3.2.3 Le théorème du RSA . . . . . . . . . . . . . . . . . . . 17
3.2.4 La signature dans RSA . . . . . . . . . . . . . . . . . . 18

4 Tests de primalité 18
4.1 Un premier test basé sur le petit théorème de Fermat . . . . . 19
4.2 Test de Solovay-Strassen . . . . . . . . . . . . . . . . . . . . . 21
4.3 Test de Miller-Rabin . . . . . . . . . . . . . . . . . . . . . . . 23

5 Programmation 26
5.1 Tests de primalité . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 Le protocole RSA . . . . . . . . . . . . . . . . . . . . . . . . . 29

2
 Depuis longtemps, les hommes ont eu le souci de pouvoir se commu-
niquer des données de manière confidentielle, que ce soit pour s’échanger
des messages personnels aussi bien que des messages militaires. Pour cela,
les hommes ont inventé la cryptologie. Elle existe depuis l’Antiquité mais
pendant longtemps, elle fut considérée comme de l’art et c’est à partir du
XVIIIème siècle qu’elle devint réellement une science. Dans notre exposé,
nous allons nous pencher plus particulièrement sur une partie de la cryp-
tologie : la cryptographie. Elle fait donc partie, avec la cryptanalyse, de la
cryptologie, qui est la science englobant le chiffrement et le déchiffrement de
messages codés, messages codés que l’on appelle également cryptogrammes.
Plus précisément, la cryptographie est la discipline de la cryptologie qui a
pour objectif d’assurer la sécurité lors de la transmission de messages. Par
sécurité, nous entendons la confidentialité mais également l’authenticité de
l’expéditeur et du destinataire. Pour se faire, les cryptogrammes utilisent
des clefs pour chiffrer les messages. La cryptographie traditionnelle est donc
une science traitant de la transmission confidentielle de données et étudiant
les différentes méthodes permettant la transmission de messages sous forme
déguisée tel que seul le destinataire soit capable de les lire. Même si nous
avons des applications concrètes de la cryptographie, il ne faut pas oublier
qu’il y a un aspect mathématique qui se cache derrière tout ça. De plus, nous
pouvons dire que l’évolution de la cryptographie est liée à l’évolution des
mathématiques mais aussi de l’informatique car c’est grâce à l’informatique
qu’elle connu un essor important. De nos jours, la cryptographie peut être
utilisée dans les domaines militaire, commercial mais aussi pour la protection
de la vie privée.

1 Clef secrète, clef publique

1.1 Cryptographie à clef secrète
1.1.1 Principe
La cryptographie à clef secrète est utilisée depuis bien longtemps. Elle per-
met à deux personnes possédant un secret commun de communiquer confi-
dentiellement. En effet, on a le problème suivant : Alice veut envoyer un
message à Bob (par la suite, Alice et Bob pourront être représentés par A
et B) mais ne veut pas que les autres soient au courant. Pour cela, elle va
d’abord se mettre d’accord avec Bob sur un secret commun qui va leur per-
mettre de chiffrer et de déchiffrer les messages. Maintenant, nous allons vous
présenter la procédure :

3
Figure 1 – Modélisation d’une communication confidentielle entre A et B
en présence de O.

– Alice va donc écrire son message en clair puis le chiffrer grâce au secret
commun.
– Ensuite, Alice va envoyer son message à Bob et il pourra le déchiffrer
facilement car il est le seul à connaı̂tre le secret, hormis Alice.

Le secret commun d’Alice et Bob s’appelle la clef, que l’on note en général
K, et on s’aperçoit que si une troisième personne Oscar (représenté par O
dans la suite) ne possède pas K alors elle ne peut pas déchiffrer le message.

Grâce au schéma ci-après, nous pouvons voir qu’Oscar ne peut pas déchiffrer
le message s’il ne possède pas la clef mais il pourrait très bien essayer un cer-
tain nombre de possibilités et par chance, tomber rapidement sur la solution.
Alice et Bob ne peuvent donc pas choisir n’importe comment leur clé. Ce-
pendant, s’ils font attention aux différents principes suivants :
– La sécurité repose sur le secret de la clef et non sur le secret de l’algo-
rithme.
– Le déchiffrement sans la clef doit être impossible (en temps raison-
nable).
– Trouver la clef à partir du clair et du chiffré est impossible (en temps
raisonnable).
Alors théoriquement, Oscar ne pourra pas casser le système. Les principes
énoncés font partis des principes de Kerckhoffs.

4
1.1.2 Quelques exemples
Le chiffrement de Jules César
Le chiffrement par décalage est aussi appelé chiffrement de Jules César
car il a été considéré comme le créateur de cette méthode. En effet, même si
on a retrouvé des traces de messages chiffrés grâce à une clef qui décale les
lettres chez les Grecs, on sait que Jules César n’a eu aucun contact avec ces
messages et on peut considérer qu’il a réinventé le fait de chiffrer les messages.
Pour son époque, ce fut révolutionnaire car jamais personne n’y avait pensé,
et surtout, si le message était intercepté, il était illisible pour les ennemis.
D’ailleurs, on retrouve dans des écrits de personnes de l’époque que César
écrivait des messages incompréhensibles en n’alternant pas nécessairement les
voyelles et les consonnes comme ils le connaissaient pour faire des phrases.
César a donc surpris, innové et mis au point une stratégie militaire que ses
ennemis ne pouvaient pas contrer car ils ne connaissaient pas le moyen de
déchiffrer et ils ne connaissaient donc pas la clef. Mais en quoi consiste ce
chiffrement plus précisément ?

Ce chiffrement consiste donc à décaler les lettres d’un certain nombre de

rangs. Pour cela, il faut écrire l’alphabet et chaque lettre sera remplacé par
la lettre que l’on obtient lorsque l’on se décale du nombre de lettres voulues
vers la droite. Mais regardons le sur des exemples :
– JULES CESAR deviendra OZQJX HJXFW si on décale de 5 rangs
c’est-à-dire si on remplace A par F , E par J, . . .
– ALEA JACTA EST sera remplacé par DOHD MDFWD HVW si on
décale de 3 rangs, si on remplace A par D, B par E,. . . , Z par C.
La clef secrète, que connaı̂t donc César et son interlocuteur, est donc F ou
alors 5, qui correspond au nombre de lettres à passer avant d’arriver à celle
souhaitée pour le premier cas et pour le deuxième, la clé sera D ou 3.

Pour chiffrer son message, César va donc tout d’abord l’écrire en clair,
c’est-à-dire en latin. Puis, pour le chiffrer, il va décaler les lettres en utili-
sant la clé secrète (qui lui indique donc le nombre de rang ou la lettre qui
remplace A), César, lui, décale les lettres vers la droite mais lorsque le des-
tinataire reçoit le message, pour le déchiffrer, il doit décaler les lettres, du
même nombre de rang, mais vers la gauche. Ainsi, il va découvrir le message
en clair émis par César.
Cela peut se faire avec n’importe quelle lettre puisque lorsque l’on arrive à
la lettre Z, on repart au début, c’est-à-dire à A. Selon l’histoire, Jules César
utilisait principalement la clef de chiffrement 3, ou encore D.

5
 On se rend compte qu’avec nos moyens actuels il serait très facile de le
déchiffrer mais pour l’époque c’était incompréhensible. Cependant, cela n’a
pas empêché ce système de se développer puisqu’il existe plusieurs variantes,
avec des chiffres par exemple, ce système s’appelle aussi le chiffrement par
substitution. Ce système nous montre cependant la limite d’un chiffrement à
clef secrète.

Le chiffrement par substitution

On considérera ici l’exemple le plus basique qui soit.

A B C ... Z
01 02 03 ... 26

Voici des citations de Jules César que nous allons coder avec cette clé de
chiffrement :
VENI VIDI VICI −→ 220514092209040922090309
TU QUOQUE MI FILI −→ 2021172115172105130906091209
ALEA JACTA EST −→ 011205011001032001051920

Pour déchiffrer les messages, il suffit de regrouper les chiffres 2 par 2 et d’uti-
liser la clef pour leur attribuer la lettre correspondante. Une fois finie, le texte
clair apparaı̂t et le message est déchiffré.

On peut se rendre que ces systèmes sont peu résistants. En effet, pour
rendre la tâche du cryptanaliste difficile, il est important de concevoir des
systèmes tels que le texte chiffré ait un aspect aléatoire sinon il serait trop
simple à déchiffrer. Pour cette raison, ainsi que pour le problème de la confi-
dentialité dans l’échange de données, une cryptographie à clé publique, ou
cryptographie asymétrique a vu le jour.

1.2 Cryptographie à clef publique

Etant donné que la cryptographie à clef secrète était peu résistante , la
cryptographie moderne a évolué pour devenir ce qu’on appelle maintenant la
cryptographie à clé publique ou asymétrique. Cependant, cette cryptographie
est apparue très tardivement, en 1976 avec Diffie et Hellman, c’est donc une
science très récente. La cryptographie à clef publique repose sur la notion de
fonction à sens unique dont nous allons donner la définition.

6
Définition 1. Une fonction f : E → F est dite à sens unique si :
– Il est possible de calculer simplement f (x) à partir de n’importe quel
x
– Pour la plupart des y ∈ f (E) , il n’est pas possible de trouver un x tel
que f (x) = y, sauf en faisant un nombre prohibitif d’opérations ou en
ayant une chance sur laquelle il est déraisonnable de compter.

En réalité, on peut donc dire que les fonctions à sens unique sont des fonc-
tions qu’il est difficile d’inverser, voire même impossible sauf si on connaı̂t la
clef privée. Il faut cependant préciser qu’il faut prendre E suffisamment grand
pour empêcher ou rendre dérisoire une recherche exhaustive parmi tous les
antécédents possibles.

1.3 Clef publique contre Clef privée

La clef secrète a longtemps été utilisée mais un dilemme s’est toujours
posé : pour établir un canal sûr, on utilise la cryptographie mais la crypto-
graphie à clef privée nécessite un canal sûr. La clef publique, elle, répond à
ce dilemme. En effet, lorsque l’on utilise une clef asymétrique, nous n’avons
plus besoin d’avoir un canal sûr pour s’échanger des données puisqu’il y en a
certaines qui sont publiques. De plus, l’expéditeur et le destinataire n’ont pas
besoin des mêmes clefs pour chiffrer et déchiffrer les messages et ne doivent
donc pas s’échanger la clef. En contrepartie, tout le challenge consiste à s’as-
surer que la clef publique que l’on possède est bien celle de la personne à
qui on veut envoyer un message ou de qui on veut recevoir un message, mais
nous en reparlerons un peu plus tard.

La cryptographie asymétrique répond donc à un besoin majeur de la

cryptographie symétrique cependant c’est le mécanisme symétrique qui est
le moins coûteux en temps de calcul. En effet, pour les codes symétriques, les
clefs sont beaucoup plus petites et le chiffrement ainsi que le déchiffrement
sont donc beaucoup plus rapides,ils travaillent de 100 à 1000 fois plus vite,
ce qui n’est pas négligeable.

Les systèmes actuels, utilisant la cryptographie, sont donc formés ainsi :

ils utilisent la cryptographie asymétrique seulement au début, c’est-à-dire
pour s’échanger les clefs, qui, elles, seront secrètes, puis ensuite, ces clefs
secrètes prendront le relais. Parmi les systèmes actuels, il y a par exemple
Internet ou encore les cartes bancaires.

7
Figure 2 – Attaque de l’homme du milieu lors d’une conversation entre
Alice et Bob

Le dernier inconvénient que l’on pourrait encore présenter pour le chif-

frement à clef publique a déjà été effleuré au dessus, il s’agit du problème
d’authentification. En effet, avec un chiffrement à clef publique, comment
savoir si le message que l’on envoie arrive à la personne souhaitée et que
le message que l’on reçoit provient de la bonne personne. Pour cela, des
mécanismes d’authentification ont été créés. Comme exemple d’interception
des messages lors d’un échange utilisant une clef publique, il y a l’attaque
de l’homme du milieu. Supposons qu’Alice et Bob communiquent sur un ca-
nal non sur grâce à une clé publique, cette attaque consiste alors à placer un
homme au ”milieu” du canal (Oscar), c’est-à-dire qu’il va pouvoir intercepter
les données entre Alice et Bob. Le but n’est pas de déchiffrer ce qu’ils vont
s’envoyer mais d’intercepter les informations qu’ils s’échangent par rapport à
leur clef et de transmettre à l’un et à l’autre des données erronées. En réalité,
lorsque Alice va envoyer des informations à Bob, l’homme du milieu va l’in-
tercepter et renvoyer son information à lui et vice versa lorsque c’est Bob qui
transmet des informations à Alice. De ce fait, lorsqu’Alice et Bob commu-
niquent, ils croient se parler l’un à l’autre mais en réalité ils communiquent
tous les deux avec la tierce personne que l’on nomme l’homme du milieu à
juste titre. Contrairement au premier schéma, nous pouvons nous apercevoir
que l’homme du milieu n’a pas besoin de la clef pour gêner la transmission
entre Alice et Bob. Le but n’est donc pas de déchiffrer les messages mais de
les intercepter pour les modifier.

Pour éviter ce genre d’attaque, nous pouvons intégrer dans les mes-
sages codés un mécanisme d’authentification permettant de garantir la pro-
venance du message chiffré. Pour être sûr de l’expéditeur, on parle de si-

8
gnature électronique et pour être sûr du destinataire, on parle de certificat
électronique.

Avant de voir plus en détails des exemples de cryptosystèmes à clef pu-

blique, il nous faut rappeler quelques résultats d’algèbre qui sont à la base
de nos futurs exemples.

2 Eléments d’Algèbre
Ce qui fait sans doute le charme des cryptosystèmes dont on parlera
plus tard, est l’apparente simplicité des éléments mathématiques auxquels ils
font appel. Nous travaillerons toujours dans un ensemble du type Z/nZ. On
supposera acquis les deux théorèmes fondamentaux suivants.
Théorème 1 (Théorème de Gauss). Soient (a, b, c) ∈ Z3 .

a|bc
⇒ a|c
a∧b=1
Théorème 2 (Théorème de Bezout). Soient (a, b) ∈ Z2 .
a ∧ b = 1 ⇔ ∃(u, v) ∈ Z2 : au + bv = 1

2.1 Le petit théorème de Fermat

Théorème 3 (Petit théorème de Fermat). Soit p un nombre premier et a
un entier naturel premier avec p alors :
ap−1 ≡ 1 (mod p) (1)
Démonstration. Supposons dans un premier temps que p divise l’un des
termes de la suite a, 2a, . . . , (p−1)a disons le terme ka. Comme a et p sont pre-
miers entre eux, par le théorème de Gauss p divise k. Ceci est absurde puisque
1 < k < p. Donc p ne divise aucun nombre de la suite a, 2a, . . . , (p − 1)a.

On montre maintenant que les restes des divisions de a, 2a, . . . , (p − 1)a par p
sont tous différents. En effet, supposons qu’on ait un reste identique pour ka
et k 0 a avec k > k 0 , ceci impliquerait que p divise (k − k 0 )a et c’est impossible
par le point précédent. Donc à l’ordre des facteurs près, les restes des divisions
de a, 2a, . . . , (p − 1)a par p est 1, 2, . . . , p − 1.

⇒ a × 2a × · · · × (p − 1)a ≡ 1 × 2 × · · · × (p − 1) (mod p)
⇒ ap−1 ≡ 1 (mod p)

9
On peut alors prouver un corollaire très utile.

Corollaire 1. Soit p un nombre premier et a un entier quelconque alors

ap ≡ a (mod p)

Démonstration. – Si a ∧ p = 1, par le théorème 1, ap−1 ≡ 1 (mod p).

– Sinon, comme p est premier, a ∧ p = p et alors a ≡ 0 (mod p)
Dans les 2 cas, a(ap−1 − 1) ≡ 0 (mod p) d’où la conclusion.

2.2 Le groupe multiplicatif

Définition 2. Soit n ∈ N. On appelle groupe multiplicatif et on note (Z/nZ)×
l’ensemble des éléments inversibles de Z/nZ.

On peut caractériser les éléments de ce groupe, la proposition suivante bien

connue nous le permet.

Proposition 1.

(Z/nZ)× = {m ∈ Z/nZ : m ∧ n = 1}

Démonstration.
m ∈ (Z/nZ)× ⇔ ∃m0 ∈ Z/nZ : mm0 ≡ 1 (mod n)
⇔ ∃k ∈ Z : mm0 + kn = 1
⇔ m ∧ n = 1 par le théorème de Bezout

Ce résultat sera particulièrement utile dans le protocole RSA.

2.3 La fonction ϕ d’Euler

Définition 3. On appelle fonction ϕ d’Euler ou indicatrice d’Euler la fonc-
tion qui à un entier n associe le nombre d’entiers a premiers à n vérifiant
1 ≤ a ≤ n.

La fonction ϕ permet donc d’évaluer le cardinal du groupe multiplicatif

(Z/nZ)× . Pour un nombre premier p, ϕ(p) = p − 1.
On va énoncer un résultat primordial dans le protocole RSA.

10
Proposition 2. Soient p et q deux nombres premiers distincts alors :
varphi(pq) = (p − 1)(q − 1)
Démonstration. ϕ(pq) est par définition le nombre d’entiers a : 1 ≤ a ≤ pq
premiers à pq. Ces entiers a sont les multiples de p et q. Or, il y a p multiples
de q dans l’ensemble {1, . . . , pq} et également q multiples de p. Dans ce
dénombrement, on a compté deux fois le terme pq. D’où finalement :
ϕ(pq) = pq − (p + q − 1) = (p − 1)(q − 1)

3 Diffie-Hellman et RSA
3.1 Echange de clef Diffie-Hellman
3.1.1 Principe
L’analogie avec le coffre fort
Le principe est assez simple. Alice (A) et Bob (B) veulent se commu-
niquer un message confidentiellement. Pour cela, Alice va choisir un coffre
fort pour lequel elle possède la clef et l’envoie à Bob tout en le laissant ou-
vert. Bob va y mettre le message, le refermer et le renvoyer à Alice. Ainsi
Alice recevra le coffre fort qu’elle pourra ouvrir puisqu’elle possède la clé
mais toutes les personnes intermédiaires ayant transporté le coffre n’auront
pas pu intercepter le message. Dans cet exemple, nous voyons bien pourquoi
ces systèmes sont également appelés des systèmes asymétriques. En effet, on
remarque que Alice et Bob n’ont pas besoin des mêmes informations tous les
deux pour pouvoir s’échanger des messages codés.

Leur but est donc de trouver S qui leur servira de clé pour un chiffrement
traditionnel sans transmettre d’informations sur le canal qui pourraient per-
mettre à des pirates de deviner S.

Nous obtenons donc le protocole suivant :

– Alice et Bob se mettent d’accord publiquement sur un très grand nombre
premier p et sur une racine primitive modulo p que l’on nommera α.
– Alice choisit un nombre a tel que a < p mais qu’elle garde secret et elle
transmet à Bob αa (mod p).
– Bob choisit un nombre b < p qu’il garde secret aussi et transmet à Alice
αb (mod p).

11
 – Leur secret commun sera donc αab (mod p). A va donc accéder à S en
élevant alphab à la puissance a et B , en élevant αa à la puissance b.

3.1.2 Outils mathématiques et algorithmes

Le protocole de Diffie-Hellman utilise comme fonction à sens unique l’ex-
ponentiation modulaire qui est impossible du point de vue computationnel à
inverser pour des nombres très grands. Cependant, il repose aussi sur d’autres
aspects mathématiques comme le choix du groupe. En effet, c’est le groupe
F∗p qui est utilisé et il a pour propriété d’être commutatif, ce qui est impor-
tant ici puisque cela nous permet de dire que αab = αba , ce qui fait que A
et B obtienne la même clef secrète. Il faut donc que le groupe de départ soit
bien choisi et que les nombres utilisés suffisamment grands pour éviter une
attaque par recherche exhaustive. Aujourd’hui, si on a un nombre premier p
de l’ordre de 300 chiffres et si a et b sont de l’ordre de 100 chiffres, alors il
est quasiment impossible à casser.

Exponentiation modulaire et logarithme discret

Comme son nom l’indique, l’exponentiation modulaire permet de calcu-
ler un nombre élevé à une certaine puissance et réduit modulo un autre
nombre. Il est inconcevable pour des grands nombres de calculer dans un
premier temps ce nombre à la puissance voulue, puis le réduire modulo un
autre grand nombre. Ceci serait très coûteux en temps de calcul et en espace
mémoire. Il existe des algorithmes nous permettant d’éviter ces problèmes de
coût, un algorithme sera décrit ultérieurement. L’inverse de l’exponentiation
modulaire est appelée logarithme discret.

Le problème du logarithme discret est le suivant : il est facile de calculer

b assez rapidement mais si on nous donne bx = y, avec x inconnue, comment
x

pouvons nous calculer x = logb y ? Résoudre le problème du logarithme discret

s’avère très difficile dans un groupe fini.

Exemple : (avec de petits nombres)

On pose G = (Z/19Z)∗ , b = 2, y = 7.On veut trouver x tel que 7 = 2x car
cela correspond au logarithme discret de 7 en base 2 (si b, y ∈ G avec y une
puissance de b, alors le logarithme discret de y en base b est x tel que bx = y).
La réponse est x = 6 car : 26 = 64 = 19 × 3 + 7. Comme on travaille sur
(Z/19Z)∗ , on regarde le reste de la division par 19 qui correspond, dans notre
cas, à 7 qui est ce que l’on recherchait.

12
 Nous pouvons donc trouver le logarithme discret lorsque nous travaillons
sur (Z/qZ)∗ et que la condition suivante est respectée : tous les nombres pre-
miers qui divisent q − 1 sont petits. Avec ces conditions, il y a un algorithme
pour trouver le logarithme discret d’un élément y ∈ (Z/qZ)∗ avec la base b.
Pour simplifier, nous supposerons que b est un générateur de (Z/qZ)∗ . Nous
devons cet algorithme à Silver, Pohlig et Hellman.

Première étape :

Tout d’abord, il faut calculer les racines pièmes de l’unité pour chaque p
premier divisant q − 1. Notons ces racines de la manière suivante :

rp,j = bj(q−1)/p) pour j = 0, . . . , p − 1

Avec les rp,j , nous pouvons écrire une sorte de table qui va nous permettre de
calculer le logarithme discret de n’importe quel y ∈ (Z/qZ)∗ . Il faut rappeler
que l’objectif est le suivant : trouver x, 0 ≤ x ≤ q − 1 tel que bx = y.

On sait que si q −1 = p pα est la factorisation en nombres premiers de q −1,

Q
alors il suffit de trouver x (mod pα ) pour chaque p divisant q − 1. Ensuite,
on peut appliquer le théorème des restes chinois pour trouver x et conclure.

Deuxième étape :

Maintenant, on va fixer un nombre premier p divisant q − 1 et on va montrer

comment déterminer x (mod pα ). On suppose que :

x ≡ x0 + x1 p + x2 p2 + · · · + xα−1 pα−1 (mod pα ) avec 0 ≤ xi < p

Pour trouver x0 , on calcule y (q−1)/p , on obtient ainsi une puissance pième de

1 car y q−1 = 1. En effet , comme b est un générateur de (Z/qZ)∗ :

bq = b ⇒ bq−1 = 1
⇒ b(q−1)x = 1

Comme bx = y , on obtient donc y q−1 = 1. Il s’en suit que y (q−1)/p =

bx(q−1)/p = bx0 (q−1)/p . En effet, si on remplace x par la formule donnée au
début, on obtient :

13
 α−1 )(q−1)/p
bx(q−1)/p = b(x0 +x1 p+···+xα−1 p
α−2 (q−1)
= bx0 (q−1)/p bx1 (q−1) bx2 p(q−1) . . . bxα−1 p
= bx0 (q−1)/p
= rp,x0
= (b(q−1)/p )x0
= y (q−1)/p
Troisième étape :

Finalement, on compare y (q−1)/p avec la table des {rp,j } pour j compris

entre 0 et p (strictement plus petit que p), puis lorsque l’on a trouvé la va-
leur correspondant à y (q−1)/p dans la table, on prend x0 égal à la valeur de j
pour laquelle y (q−1)/p = rp,j . On trouve cette valeur grâce à la table que nous
avons pu construire au début en calculant les racines pièmes . Nous avons donc
trouver la valeur de x0 , il nous reste à trouver les valeurs de tous les xi .

Maintenant, il faut réitérer les étapes pour tous les xi .

Pour trouver x1 , on va pratiquer de la même manière sauf que l’on rem-

place y par y1 avec :
y1 = y/bx0 = bx /bx0 = bx−x0 .
De ce fait, y1 a pour logarithme discret x − x0 , comme x0 est maintenant
connu, on va calculer x1 avec la formule x − x0 ≡ x1 p + x2 p2 + · · · + xα−1 pα−1
2
(mod pα ). On a y (q−1)/p = 1 et on va calculer y (q−1)/p :
2 2
y (q−1)/p = b(x−x0 )(q−1)/p
2 +···+x α−1 )(q−1)/p2
= b(x1 p+x2 p α−1 p

α−3 (q−1)
= bx1 (q−1)/p bx2 (q−1) bx3 p(q−1) . . . bxα−1 p
= bx1 (q−1)/p
= rp,x1
(q−1)/p2
Par la suite, on va donc comparer y1 avec les valeurs de la table des
(q−1)/p2
rp,j et x1 sera égal à la valeur de j pour laquelle y1 = rp,j . On procède
de la même manière pour trouver x2 , x3 , . . . , xα−1 . Travaillons au rang i :
y
Pour tout i = 1, . . . , p − 1, on pose : yi = x0 +x1 p+···+x i−1 p
i−1 . D’où :
b
x−x0 −x1 p−x2 p2 −···−xi−1 pi−1
yi = b

14
Et y a pour logarithme discret :

x − x0 − x1 p − x2 p2 − · · · − xi−1 pi−1 ≡ xi pi + · · · + xα−1 pα−1 (mod pα )

De ce fait, on calcule :
(q−1)/pi+1 2 −···−x i−1 )(q−1)/pi+1)
yi = b(x−x0 −x1 p−x2 p i−1 p

i α−1 )(q−1)/pi+1
= b(xi p +···+xα−1) p
= bxi (q−1)p bxi+1 (q−1) bxi+2 p(q−1) . . .
= bxi (q−1)p
= rp,xi

Comme auparavant, on regarde dans la table à quelle valeur correspond

(q−1)/pi+1 (q−1)/pi+1
yi et on pose xi égal à la valeur de j pour laquelle yi = rp,j .

Dernière étape :

Lorsque l’on a effectué cela jusqu’au rang p − 1, on obtient donc x

(mod pα ). Après avoir fait cela pour chaque p divisant q − 1, nous obtenons
un système de la forme :

x ≡ α1 (mod p1 )
x ≡ α2 (mod p2 ) avec ∀i 6= j, pi ∧ pj = 1
..
.
x ≡ αr (mod pr )

Or le théorème des restes chinois nous dit que pour un tel système, il existe
une solution répondant à toutes les congruences et elle est unique modulo P
avec P = p1 p2 . . . pr . De ce fait, nous pouvons conclure et trouver ainsi x.

Conclusion : Nous pouvons nous rendre compte que cet algorithme fonctionne
bien quand tous les diviseurs premiers de q − 1 sont petits, mais il est clair
(q−1)/pi+1
que le calcul de la table des rp,j et la comparaison des yi avec cette
table est beaucoup plus longue si q − 1 est divisible par un nombre premier
beaucoup plus grand, de l’ordre de 20 chiffres minimum. C’est pour cela que
les chiffres utilisés lors d’échanges de messages utilisant une clef publique et
en particulier les nombres premiers sont très grands et que cette technique a
besoin de plus de temps qu’un système à clef privée.

15
3.2 RSA
Le système de cryptage RSA a été inventé en 1977 par Ron Rivest, Adi
Shamir et Len Adleman. C’est un essayant de démontrer que l’idée de système
à clef publique introduit par Diffie et Hellman était une incohérence que les
trois auteurs, devant leur échec, découvrirent ce système qui devint rapide-
ment une référence. Encore aujourd’hui le cryptosytème RSA est partout,
dans les cartes à puces de cartes bancaires, dans les messageries . . .

3.2.1 Avantages et inconvénients du cryptosystème

L’inconvénient majeur de RSA est le temps de calcul plus long que chez
les algorithmes à une seule clef. En effet, dans ce cryptosytème la clef de
codage est différente de la clef de décodage, c’est un système ”asymétrique”.

L’atout majeur de RSA est sa sécurité. Celle-ci repose sur la facilité, pour
les deux personnes voulant échanger des messages, de créer un grand nombre
à partir du produit de deux grands nombres premiers (par des algorithmes
probabilistes) et sur l’immense difficulté pour un intercepteur malveillant de
retrouver la factorisation en deux nombres premiers pour le grand nombre
ainsi généré et donc casser le système.

Le cryptosystème RSA est basé sur des résultats mathématiques très

simples, connus depuis le XVIIIème siècle. Enfin, un atout propre aux crypto-
systèmes à clef publique est de ne pas avoir besoin d’un canal sécurisé pour
échanger une clef.

3.2.2 Le protocole RSA

Nous appellerons dans cette partie Alice l’émetteur du message et Bob la
destinataire.
– Bob génère deux grands nombres premiers p et q par des algorithmes
probabilistes. Il calcule n = pq. Il détermine un entier e tel que e ∧
ϕ(n) = 1 (on rappelle que ϕ(n) = ϕ(pq) = (p − 1)(q − 1)). Bob en
profite pour déterminer d tel que :
ed ≡ 1 (mod ϕ(n))
.
– Bob envoie (n, e) à Alice, ce sera sa clef de codage (publique). (n, d)
sera la clef de décodage de Bob (secrète).
– Alice code son message chiffré M en calculant via l’exponentiation mo-
dulaire : M e (mod n) et elle envoie son résultat C à Bob.

16
 – Bob décode le message en calculant C d (mod n)

En effectuant ce dernier calcul, Bob retombera bien sur le message initial.

Ceci est garanti par le résultat suivant communément appelé théorème du
RSA.

3.2.3 Le théorème du RSA

Théorème 4 (Le théorème du RSA). Soient p et q deux nombres premiers
, on pose n = pq. Si le nombre e est un entier premier avec le nombre
ϕ(n) = (p − 1)(q − 1) alors il existe un entier d positif tel que ed ≡ 1
(mod ϕ(n)) et pour cet entier d et un entier A quelconque on a :
Aed ≡ A (mod n)

Démonstration. On sait que e ∧ (p − 1)(q − 1) = 1. Ceci implique que e est

inversible dans Z/(p−1)(q−1)Z. D’où l’existence et même l’unicité d’un tel d.

Posons B ≡ Ae (mod n). On a alors B d ≡ Aed (mod n).

ed ≡ 1 (mod (p − 1)(q − 1)) ⇒ ∃k : ed = k(p − 1)(q − 1) + 1
D’où :
Aed = Ak(p−1)(q−1)+1
= (Ap )(q−1)k A1−(q−1)k
Or, on sait par le corollaire 1 page 10 que Ap ≡ A (mod p).
Aed ≡ A(q−1)k+1−(q−1)k (mod p)
≡ A (mod p)
De même,
Aed ≡ A (mod q)
0 0
On en déduit alors qu’il existe l et l tel que Aed = lp + A = l q + A et
0 00
donc lp = l q. Cette dernière quantité s’écrit également l pq pour un certain
00
l car p et q sont des nombres premiers. Ainsi Aed ≡ A (mod pq)
On a donc pour le moment décrit et justifié la méthode RSA, Alice et Bob
peuvent donc s’échanger des messages de manière sure grâce à ce protocole,
mais un problème se pose imaginons que Oscar intercepte la clef publique que
Bob envoie à Alice, il peut alors très bien crypter un message en se faisant
passer pour Alice. Il est donc indispensable d’avoir une façon de savoir si la
personne qui nous envoie un message est bel et bien celle dont on attend le
message.

17
3.2.4 La signature dans RSA
Il parait raisonnable de penser qu’Alice et Bob auront plusieurs messages
à s’échanger. Désormais, on considérera donc qu’Alice et Bob possèdent cha-
cun une clef privée et une clef publique. Autrement dit avec les notations
précédentes, la clef privée de Bob est (n, d), la clef publique associée destinée
à Alice est (n, e). De son côté, Alice a procédé de la même manière que Bob
pour créer le triplet (n0 , e0 , d0 ) où n0 = p0 × q 0 est le produit de deux nombres
premiers, e0 ∧ ϕ(n0 ) = 1 et e0 d0 ≡ 1 (mod ϕ(n0 )). Sa clef privée est (n0 , d0 ) et
la clef publique destinée à Bob est (n0 , e0 ). Pour résumer :

Alice Bob
Clef publique (n, e) (n0 , e0 )
Clef privée (n0 , d0 ) (n, d)

Pour signer son message, Alice crypte sa signature M grâce à sa clef privée
(n0 , d0 ), elle obtient M 0 , puis elle crypte M 0 grâce à la clef publique (n, e),
elle obtient M 00 et elle l’envoie avec son message à Bob.

Bob décrypte M 00 grâce à sa clef privée (n, d), par le théorème du RSA,
il tombe sur M 0 , puis il utilise sa clef publique (n0 , e0 ) pour retomber sur M
toujours en vertu du même théorème.

Ainsi par un procédé très simple et qui n’utilise rien de plus que le pro-
tocole en lui même, Alice est certaine que le message qu’elle reçoit vient de
Bob.

4 Tests de primalité
Pour faire fonctionner un algorithme de cryptage/décryptage type RSA,
on a besoin de grands nombres premiers. Des nombres premiers trop petits
représenteraient un danger pour la sécurité du système.
Théorème 5 (Théorème des nombres premiers). Le nombre de nombres
premiers inférieurs ou égaux à x noté π(x) vérifie
x
π(x) ∼
ln x
Ce théorème nous donne le nombre moyen de tirages qu’il faut effectuer
pour avoir un nombre premier. Si p est choisi au hasard, la probabilité qu’il
soit premier est ln1p .

18
Il faut donc utiliser des algorithmes ”probabilistes” pour un tester si le
nombre tiré est non premier ou probablement premier. Ces algorithmes ne
nous procurerons pas la certitude intégrale que p est premier. Si p passe le
test on dira qu’il est premier avec forte probabilité.

On pourra se proposer de tester des nombres impairs à la structure bien

particulière comme par exemple les nombres de Mersenne.

Définition 4. Un nombre de Mersenne est un nombre du type 2n − 1 où

n∈N

Pour tester la primalité, on a besoin d’un critère de primalité. Si le nombre

à tester n0 passe ce critère avec succès dans un cas particulier, il est peut-être
premier. Si n0 passe avec succès le critère dans tous les cas, il est premier
avec forte probabilité. Sinon il est composé.

En général, trouver une factorisation pour montrer qu’un nombre est

composé est très gourmand en temps de calcul. Le premier test auquel on
pourrait penser serait à partir de n0 à tester, de prendre m 6= 1 au hasard et
tester si m divise n0 . Si ce n’est pas le cas, on choisit un autre m et ainsi de
suite. Evidemment, ceci est laborieux pour de grands nombres !

4.1 Un premier test basé sur le petit théorème de Fer-

mat
Définition 5. Soit n est un entier impair composé et b un entier tel que b
soit premier avec n. Si bn−1 ≡ 1 (mod n) alors n est appelé pseudo-premier

Par exemple, 91 est un pseudo-premier dans la base 3.

Proposition 3. Soit n un entier impair composé.

1. Les propositions suivantes sont équivalentes :
– n est pseudo-premier dans la base b où b ∧ n = 1
– Ord(b) dans (Z/nZ)∗ divise n − 1
2. Si n est premier dans les bases b1 et b2 alors il l’est dans les bases b1 b2
et b1 b−1
2
3. Si n échoue à ce test pour b ∈ (Z/nZ)∗ alors n échoue aussi pour au
moins la moitié des bases b ∈ (Z/nZ)∗ possibles.

Démonstration. 1. La première proposition est une évidence.

19
 2. On a :
b1n−1 ≡ 1 (mod n)
b2n−1 ≡ 1 (mod n)
⇒ bn−1
1 bn−1
2 ≡1 (mod n) ⇒ (b1 b2 )n−1 ≡ 1 (mod n)
Donc n est pseudo-premier dans la base b1 b2

De plus :
bn−1
2 ≡1 (mod n) ⇒ (bn−1
2 )−1 dans (Z/nZ)∗
Ainsi :
bn−1
1 ×1 ≡ 1 (mod 1) ⇒ b1n−1 ×(b2n−1 )−1 ≡ 1 (mod n) ⇒ (b1 b−1
2 )
n−1
≡1 (mod n)

Donc n est pseudo-premier dans la base b1 b−1 2

3. Soient b1 , . . . , bs toutes les bases pour lesquelles n est pseudo-premier.
Soit b une base pour laquelle b n’est pas pseudo-premier. Si n est
pseudo-premier pour chaque bbi alors par la proposition précédente
(bbi )b−1
i = b est une base pour laquelle n est pseudo premier. Contra-
diction.
Ainsi, pour bb1 , . . . , bbs , n échoue au test.
Donc pour b choisi au hasard, il y a au moins 50% de chance d’échec.

Description du test : (donnée n)

– Choix aléatoire de b : 0 < b < n.
– Calcul de d = b ∧ n par l’algorithme d’Euclide.
– On distingue 2 cas :
– Si d > 1, n n’est pas premier.
– Si d = 1, calcul de bn−1 (mod n) par l’algorithme d’exponentiation
modulaire. Si on a 1 alors n passe le test et on passe à un autre b.
Sinon n est composé.

Si on applique ce test k fois et que n passe le test avec succès dans tous
les cas, alors n est probablement premier. Par la proposition 3, la probabilité
que n soit composé malgré tout est d’au plus 21k .
Définition 6. Un nombre de Carmichaël est un entier composé n tel que
∀b ∈ (Z/nZ)∗ :
bn−1 ≡ 1 (mod n)
Ces nombres particuliers révèlent une faille dans notre méthode.

20
4.2 Test de Solovay-Strassen
Afin de comprendre ce test, nous devons définir certaines notions telles
que résidu quadratique, symbole de Legendre et de Jacobi.

Définition 7. – Soit p ∈ N un nombre premier, n 6= 2 et x ∈ N tel que

1 ≤ x ≤ p − 1. On dit que x est un résidu quadratique modulo p si la
congruence y 2 ≡ x (mod p) a une solution y ∈ Z/pZ.
– Soit a un entier et p > 2 un nombre premier. On définit le symbole de
Legendre comme suit :

 b   0 si p divise a
= 1 si a est un résidu quadratique modulo p
n
−1 sinon


– Soit a un entier, et soit n un entier positif impair. Soit n = pα1 1 , . . . , pαr r

la décomposition en facteurs premiers de n. On définit le symbole de
Jacobi ( na ) comme le produit des symboles de Legendre pour les facteurs
premiers de n :  a   a  α1  a  αr
= ...
n p1 pr
Le test est inspiré de la proposition suivante.

Proposition 4. Si n est premier alors pour tout entier b ;

n−1
b
b 2 ≡ (mod n) (2)
n
Ici bien sur, les symboles de Jacobi et de Legendre coincident.
Démonstration. – Si n divise b, d’une part ( nb ) = 0, d’autre part n divise
n−1 n−1
b 2 et donc b 2 ≡ 0 (mod n). La congruence est donc vrai dans ce
cas.
– Si n ne divise pas b, on applique le petit théorème de Fermat :

bn−1 ≡ 1 (mod n)
n−1
⇒b 2 ≡ ±1 (mod n)

Soit g un générateur de (Z/nZ)∗ , pour un certain j on a b = g j .

Si j est pair, il existe i tel que j = 2i, et alors b = g 2i = (g i )2 , donc b
est résidu quadratique modulo n, il s’en suit ( nb ) = 1.

21
 Réciproquement, si b est un résidu quadratique modulo n, il existe a
tel que a2 = b, ainsi si b = g j et a = g i , on a j = 2i, d’où j est pair.
n−1 j
D’autre part, b 2 = (g 2 )p−1
≡ 1 (mod n) si et seulement si j/2 ∈ N par Fermat
≡ 1 (mod n) si et seulement si j est pair

Ceci conclut la preuve.

Grâce à cette proposition, on peut définir une notion de pseudo-premier

propre à ce test.
Définition 8. Soit n est un entier composé impair, soit b tel que b ∧ n = 1
tel que (2) soit vérifiée alors on dit que n est un pseudo-premier d’Euler dans
la base b.

Description du test : (donnée n)

– Choisir b tel que 0 < b < n
n−1
– Calculer b 2 (mod n) et ( nb ) (mod n)
– Si il n’y a pas égalité, n est composé, et on s’arrête.
– Si il y a égalité, n passe le test, et on choisit un autre b.

Si au bout de k itérations, l’égalité est vérifiée à chaque fois, alors n est

probablement premier. Si on teste tous les b possibles, et que l’égalité reste
vraie, alors n est premier avec forte probabilité. On peut s’intéresser main-
tenant à la fiabilité du test.

Proposition 5. Si n est un entier composé impair alors n est un pseudo-

premier d’Euler pour au plus 50% des bases b possibles.
Démonstration. On construit dans un premier temps une base b telle que (2)
ne soit pas satisfaite. Supposons qu’il existe p premier tel que p2 divise n,
on choisit b = 1 + n/p alors ( nb ) = 1 mais la partie gauche de (2) n’est pas
congrue à 1 (mod n) comme p ne divise pas (n−1)/2. Supposons maintenant
que n est le produit de nombres premiers distincts avec p l’un d’entre eux.
On choisit s un non-résidu quadratique modulo p et soit b : 1 ≤ b < n
satisfaisant aux congruences :

b ≡ s (mod p)
b ≡ 1 (mod n/p)

22
Un tel b est trouvé par le théorème des restes chinois. Alors ( nb ) = −1 mais,
b(n−1)/2 ≡ 1 (mod n/p) et b(n−1)/2 6= −1 (mod n)
On a alors construit une base b telle que (2) n’est pas satisfaite. Soient bi :
1 ≤ i ≤ t tous les entiers vérifiant (2), avec toujours la condition ∀i, bi ∧n = 1.
Posons ui = bbi (mod n). Ils sont tous distincts et vérifient ui ∧ n = 1. Si
l’un des ui satisfaisait (2), on aurait :
 b  b 
(n−1)/2 i
b(n−1)/2 bi ≡ (mod n)
n n
Comme les bi vérifient (2), on en déduit :
b
(n−1)/2
b ≡ (mod n)
n
Ceci est faux par construction de b. Ainsi aucun des ui ne vérifie (2) et alors
il y a au moins autant de bases qui ne vérifient pas la relation qu’il y en a
pour lesquelles la relation est satisfaite.

Grâce à cette proposition, on prouve que pour k itérations, la probabilité

que n passe le test tout en étant composé est d’au plus 21k . Ce test est donc
aussi fiable que le précédent, nous allons maintenant voir un dernier test plus
raffiné.

4.3 Test de Miller-Rabin

L’idée du critère découle de la conclusion du petit théorème de Fermat. Si
on extrait successivement les racines carrées de chaque côté, si n est premier
alors la première classe autre que 1 qu’on peut avoir est -1 car ±1 sont les
seules racines carrées de 1 modulo un nombre premier.
En pratique, on extrait pas des racines carrées mais on fait l’inverse, après
avoir compilé bt (mod n) où t impair est tel que n − 1 = 2s t, on élèvera
successivement au carré.

Comme dans les tests précédents, on définit une notion de pseudo-premier.

Définition 9. Soit n un entier positif, composé et impair. On pose n−1 = 2s t
avec t impair. Soit b ∈ (Z/nZ)∗ . Si n et b vérifient :
 t
 b ≡ 1 (mod n)
ou (3)
2r t
∃r : 0 ≤ r < s tel que b ≡ −1 (mod n)


alors s est appelé pseudo-premier fort.

23
Description du test : (donnée n)
– Mettre n − 1 sous la forme 2s t où t est impair.
– Choisir au hasard b tel que 0 < b < n.
– Calculer bt (mod n)
– Si on obtient 1 ou −1, n passe le test avec succès et on passe à un autre
choix de b.
– Sinon, élever au carré successivement jusqu’à obtenir −1 (s itérations
au maximum)
– Si ceci se produit, n passe le test avec succès et on passe à un autre
b.
– Sinon, n est composé.

Il est légitime de se demander si ce test est meilleur que les tests précédents.
Nous avons un tel résultat, mais avant cela nous devons énoncer 3 lemmes 1 .

Lemme 1. Si n est pseudo-premier fort dans la base b alors n est un pseudo-

premier d’Euler et par suite n est pseudo-premier

Lemme 2. Soit d = k ∧ m, alors il existe exactement d éléments dans le

groupe {g, g 2 , . . . , g m = 1} qui vérifient xk = 1.
0
Lemme 3. Soit p un nombre premier ≥ 3, on pose p − 1 = 2s t0 où t0 impair.
r
Le nombre de x ∈ (Z/pZ)∗ qui vérifient x2 t ≡ −1 (mod p) (où t est impair)
est égal à 0 si r ≥ s0 et égal à 2r (t ∧ t0 ) si r < s0 .

Proposition 6. Si n est un entier composé impair alors il est pseudo-premier

fort dans la base b pour au plus 25% des b tels que 0 < b < n.

Démonstration. On distinguera 3 cas.

1. Supposons qu’il existe p premier tel que p2 divise n. On pose n−1 = 2s t
avec t impair.
Supposons que n soit pseudo-premier dans la base b, alors bn−1 ≡ 1
(mod n).
Dans ce cas, bn−1 ≡ 1 (mod p2 ).
Notons que (Z/p2 Z)∗ est un groupe cyclique. Autrement dit, ∃g tel que
(Z/p2 Z)∗ = {g, g 2 , . . . , g p(p−1) = 1}
D’après le lemme 2, bn−1 ≡ 1 (mod p2 ) arrive exactement d fois où
d = n − 1 ∧ p(p − 1).
On sait que p divise n donc p ne divise pas n − 1 et alors p ne divise
pas d. Donc le d maximal envisageable est p − 1.
1. Les démonstrations sont données dans A course in number theory and cryptography
de Niel Koblitz

24
 Donc la probabilité que bn−1 ≡ 1 (mod p2 ) se produise sera inférieure
à pp−1 1 1 1
2 −1 = p+1 et p+1 ≤ 4 .

En particulier par le lemme 1, le résultat est vrai pour les pseudo-

premiers forts.
2. Supposons que n = pq où p et q sont des nombres des premiers.
0 00
Posons p − 1 = 2s t0 et q − 1 = 2s t00 , et s0 ≤ s00 . Sous ces conditions,
n est pseudo-premier fort dans la base b si l’une des deux propriétés
suivantes est vérifiée :

– bt ≡ 1 (mod p) et bt ≡ 1 (mod q)
r r
– ∃r : 0 ≤ r < s tel que : b2 t ≡ −1 (mod p) et b2 t ≡ −1 (mod q)
Par le lemme 2, le nombre de possibilités pour la première proposition
est (t ∧ t0 )(t ∧ t00 ) < t0 t00 . Par le lemme 3, le nombre de possibilités pour
la seconde proposition est 2r (t ∧ t0 ) × 2r (t ∧ t00 ) < 4r t0 t00 .
0 00
Comme n − 1 > φ(n) = (p − 1)(q − 1) = 2s +s t0 t00 , voici un majorant
de la proportion des b pour lesquelles n est un pseudo-premier fort :
0 0
t0 t00 + t0 t00 + 4t0 t00 + · · · + 4s −1 t0 t00 −s0 −s00 4s − 1
M= = 2 × (1 + )
2s0 +s00 t0 t00 4−1
0
−s0 −s00 4s − 1
=2 × (1 + )
3
Si s00 > s0 ,
0
2 4s
−2s0 −1 0 2 1
M ≤2 ×( + ) = 2−2s −1 × +
3 3 3 6
−3 2 1 1
≤2 ×( + )=
3 6 4
Si s” = s0 , on prouve que l’une des 2 inégalités t ∧ t0 ≤ t0 et t ∧ t00 ≤ t00
doit être stricte. En effet, supposons t0 divise t et t00 divise t, on a
n − 1 = 2s t ≡ 0 (mod t0 ) mais :

n − 1 = pq − 1
= (p − 1)(q − 1) + (q − 1)
≡ q − 1 (mod t0 )
0
On en déduit alors que t0 divise q − 1 = 2s t00 et alors t0 divise t00 . De
même t00 divise t0 . Ceci implique t0 = t00 et alors p = q, contradiction.

25
 Supposons par exemple que t ∧ t0 < t0 , comme on travaille sur des
nombres impairs, on réécrit cette condition ainsi : t ∧ t0 ≤ 31 t0 et dans
ce cas :
0
1 t0 t00 + t0 t00 + 4t0 t00 + · · · + 4s −1 t0 t00
M=
3 2s0 +s00 t0 t00
0
1 0 2 4s 1 1 1 1
= 2−2s ( + )≤ + = <
3 3 3 18 9 6 4
Ceci conclut la preuve pour le cas 2.

3. On suppose enfin que n se décompose en un nombre quelconque de

nombres premiers : n = p1 p2 . . . pk pour k ≥ 3. On décompose les fac-
teurs premiers comme précédemment pj − 1 = 2sj tj où tj est impair.
On va appliquer la même méthode que dans le cas 2.

Quitte à réordonner les termes on peut supposer ∀j ≤ k : s1 ≤ sj . On

peut, en utilisant ce qui a été fait auparavant déterminer un majorant
de la proportion des bases b possibles pour lesquelles n est un pseudo-
premier fort :

2ks1 − 1 k
−ks1 2 − 2 2ks1 k
−ks1 2 − 2 1
2−s1 −s2 −···−sk (1 + k
) ≤ 2 ( k
+ k
) = 2 k
+ k
2 −1 2 −1 2 −1 2 −1 2 −1
k 1−k
2 −2 1 2−2
≤ 2−k k + k = k = 21−k
2 −1 2 −1 2 −1
1
≤
4

Cette proposition assure que si on teste avec succès k fois un nombre grâce
à ce test, la probabilité qu’il soit pseudo-premier fort est d’au plus 1/4k . Ceci
en fait un test plus fiable que les 2 tests précédents.

5 Programmation
Il est évident que l’intérêt de la cryptographie n’est pas théorique, on se
propose donc de mettre en application certains protocoles énoncé sous scilab.

26
5.1 Tests de primalité
On va tester dans cette partie des nombres de Mersenne qu’on génère
aisément ainsi :

function[M]=mersenne(n)
format(25) ;
M = 2n − 1 ;
endfunction ;

Test basé sur le petit théorème de Fermat

L’algorithme pour le premier test que nous avons étudié et pour une
itération est le suivant :

function[P1]=test1(n,b)
temp=0 ;
P1=0 ;
d=euclide(b,n) ;
if d > 1 then ;
P1=0 ; end ;
if d==1 then ;
temp=expmod(b,n-1,n) ; end ;
if temp==1 then ;
P1=1 ; end ;
endfunction ;

Et pour k itérations :

function[P]=testprim(n,k)
P=0
Vect=int((n-1)*rand(1,k)+ones(1,k)) ;
VectP=zeros(1,k) ;
for i=1 :k ;
VectP(i)=test1(n,Vect(i)) ;
end ;
if norm(VectP,1)==k then ;
P=1 ; end ;
endfunction ;

27
 Ce programme nous permet de vérifier la primalité de nombres tels que
mersenne(7) = 127 et mersenne(19) = 524287 qu’on utilisera par la suite,
mais les nombres de Carmichaël mettent en échec ce test, on va donc coder
un test plus sur.

Test de Miller-Rabin
function[Res]=millerrabin(n,p)
s = 1;
P = zeros(p, 1) ;
Res = 0;
while int((n − 1)/2s ) == (n − 1)/2s
s = s + 1 ; end
s=s−1
t = (n − 1)/2s
for i = 1 : p
b = int(((n − 2) ∗ rand(1) + 1)) ;
a = expmod(b, t, n)
if a == 1 then ;
P (i) = 1 ; end ;
if a == n − 1 then ;
P (i) = 1 ; end ;
if a < n − 1 and a > 1 then ;
iter = 0
while expmod(a, 2, n) < n − 1 and iter < s − 1 ;
a = expmod(a, 2, n)
iter = iter + 1
end ;
if iter < s − 1 then ;
P (i) = 1
end ;
end ;
end ;
if norm(P, 1) == length(P ) then ;
Res = 1
end ;
endfunction

28
5.2 Le protocole RSA
Nous avons tout d’abord besoin de l’algorithme d’Euclide.

function[pgcd]=euclide(a,b)
r=modulo(a,b)
while r>0
a=b ;
b=r ;
r=modulo(a,b) ;
end
pgcd=b
endfunction

Le protocole repose sur l’algorithme d’exponentiation modulaire, dont on

donne une version par la méthode binaire. Un premier programme nous per-
met de déterminer la puissance de 2 maximale dans un nombre.

function[p]=binaire1(n)
temp = n
i=0
while 2i ≥ temp
i=i+1
end
p=i−1
endfunction

Voici maintenant un programme qui convertit un nombre en version binaire.

function[p]=binaire(n)
j=1
temp=n
while temp > 0 ;
[P (j)] = binaire1(temp) ; temp = temp − 2P (j) ; j = j + 1 ;
end ;
p = zeros(1, P (1) + 1);
f ori = 1 : length(P );
p(P (i) + 1) = 1 ; end ;
endfunction

function[C]=expmod(M,e,N)

29
C=M
E = binaire(e)
k = length(E)
for i = k − 1 : −1 : 1
C=modulo(C*C,N)
if E(i)==1 then ;
C=modulo(C*M,N)
end ;
end ;
endfunction ;

Il nous faut également un algorithme permettant de calculer l’inverse mo-

dulaire d’un nombre. C’est une variante de l’algorithme d’Euclide étendu 2 .

function[c]=inversemod(n,b)
c=0
b0 = b
n0 = n
t0 = 0
t=1
q = int(n0/b0)
r = n0 − q ∗ b0
while r > 0
temp = t0 − q ∗ t
if temp ≥ 0 then temp=modulo(temp,n) ; end
if temp < 0 then temp=n-modulo(-temp,n) ; end
t0 = t
t = temp
n0 = b0
b0 = r
q = int(n0/b0)
r = n0 − q ∗ b0
end ;
c=modulo(t,n)
endfunction

Désormais, nous somme en mesure de démarrer la procédure. Admet-

tons que Bob ait déterminé p et q. Il détermine l’exposant e premier avec
2. L’algorithme non modifié provient de Cryptography : Theory and practice de Douglas
R. Stinson

30
(p − 1)(q − 1) grâce à l’algorithme suivant :

function[e]=detexpo(p,q)
e=int(((p-1)*(q-1)-3)*rand(1)+2) ;
while euclide(e, (p − 1) ∗ (q − 1)) > 1 ;
e=e+1 ;
end ;
endfunction

Alice, lorsqu’elle a reçu la clef publique peut coder son message grâce à
l’exponentiation modulaire. Elle utilisera le code ASCII pour transcrire les
lettres en chiffres. On récupéra un vecteur de taille le nombre de caractère du
message. On ”accolera” alors les termes de ce vecteur 2 par 2 afin de créer
un nouveau vecteur dont les composantes sont d’au plus 6 décimales, et c’est
à ces composantes qu’on appliquera l’exponentiation modulaire.

function[M2]=cryptRSA(M1,e,n)
format(25)
temp=ascii(M1)
if length(temp)/2 > int(length(temp)/2) then ;
temp=[temp,0]
end ;
temp2=matrix(temp,2,length(temp)/2)’
temp3 = temp2(:, 2) + temp2(:, 1) ∗ 103
for i=1 :length(temp3)
M2(i)=expmod(temp3(i),e,n)
end ;
endfunction

Bob calcule l’inverse de d via l’inversion modulaire et décrypte avec l’ex-

ponentiation modulaire.

function[M]=decryptRSA(p,q,e,M2)
d=inversemod((p-1)*(q-1),e) ;
for i=1 :length(M2)
M3(i)=expmod(M2(i),d,p*q) ;
end ;
M 4 = int(M 3/103 )
M 5 = M 3 − M 4 ∗ 103
M6=[M4,M5]
M=[]

31
for i=1 :size(M6,1)
M=[M,M6(i, :)]
end ;
M=ascii(M)
endfunction ;

Exemple
Supposons que Alice veuille faire découvrir à Bob Demain dès l’aube... de
Victor Hugo. Voici les deux premiers vers :
Demain, dès l’aube, à l’heure où blanchit la campagne,
Je partirai. Vois-tu,je sais que tu m’attends
Bob de son côté a choisi p = 27 − 1 = 127 et q = 219 − 1 = 524287 ainsi
n = pq = 66584449 et le e déterminé aléatoirement est cette fois 13960129.
Alice donne ce test au programme de cryptage sous la forme :

”demaindeslaubealheureoublanchitlacampagnejepartiraivoistujesaisquetumattends”

Voici un extrait de ce que reçoit Bob :(il reçoit en fait un vecteur à 38 com-
posantes.)

16308603
55846476
10957829
16308603
62983730

Grâce au programme de décryptage, Bob retombe bien sur le message

d’Alice.
La fonction tic() ;. . . ; toc() nous permet d’évaluer le temps de calcul. Le
cryptage prend aux alentours de 2 secondes, et le décryptage est lui dans
ce cas très rapide soit environ 0,2 seconde. Ceci peut paraı̂tre assez rapide,
mais il faut se rendre compte qu’on a pris un n très petit par rapport aux n
généralement choisis.

32
Conclusion
La cryptographie à clef publique et particulièrement RSA ont encore de
beaux jours devant eux. Malgré les attaques de plus en plus subtiles et les
records de factorisation de plus en plus impressionnants, la sécurité de RSA
n’est toujours pas remise en question et il est raisonnable de penser que si
une attaque mettait à défaut le cryptosystème, elle resterait secrète encore
de longues années ! Cependant, il ne faut pas croire que RSA est considéré
comme le cryptosystème ultime, on a cru un temps que les cryptosystèmes
basés sur le bien connu problème du sac à dos remplaceraient très vite RSA.
Aujourd’hui, ils ont tous (à l’exception d’OTU 3 ) été cassés. Pourquoi donc
cela n’arriverait-il jamais pour RSA ? L’utilisation des courbes elliptiques
semble être l’avenir proche de la cryptographie à clef publique. Pour casser
un tel système, il faudrait résoudre le problème du logarithme discret sur une
courbe elliptique ! Dans un avenir plus lointain, beaucoup s’accorde à dire que
la cryptographie mathématique sera mise en échec par des ordinateurs quan-
tiques qui sont encore aujourd’hui pure science-fiction. Alors la cryptographie
devra évoluer et reposera sur des principes de physique fondamentale.

Bibliographie

– Neal Koblitz. A course in number theory and cryptography

– Gilles Zemor. Cours de Cryptographie

– Douglas R. Stinson. Cryptography : Theory and Practice

– Arto Salomaa. Public-Key Cryptography

– Jean-Guillaume Dumas, Jean-Louis Roch, Eric Tannier, Sébastien Va-

rette. Théorie des codes : Compression, cryptage, correction

3. Okamoto, Tanaka, Uchiyama

33