Cryptographie

Réalisé par : Pr. EN-NAIMANI Zakariae

École nationale des sciences appliquées d'Oujda

21 décembre 2021

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

 Chapitre 3 : Cryptographie à
clef publique

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Système à clef publique

Le système de la cryptographie classique que l'on a étudié

jusqu'ici, Alice et Bob choisissent secrètement une clef K ∈ K
qui dénit des règles de chirement E et de déchirement D .
Dans ces systèmes à clef privée, la publication E rend les
système peu sûr.
Un défaut des systèmes à clef privée est qu'ils nécessitent la
communication préalable de la clef K entre Alice et Bob par
un canal sûr avant la transmission du message chiré.
Pratiquement, cela peut s'avérer dicile à réaliser.
Par exemple, si Alice et Bob vivent à des endroits éloignés et
s'ils décident de communiquer par courrier électronique, ils
n'ont raisonnablement pas accès à un canal sûr.

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Système à clef publique

L'objectif des systèmes à clef publique est de rendre la règle

D ∈ D impossible à retrouver à partir de E ∈ E.

La règle de chirement E peut être publiée dans un répertoire

(d'où le nom de système à clef publique).
L'avantage du système à clef publique est qu'Alice (ou toute
autre personne) peut envoyer un message à Bob chiré par E
sans communication privée préalable.
Bob est la seule personne capable de déchirer ce texte en
utilisant sa règle secrète D .
L'idée de système à clef publique, qui date de 1976, est due à Die
et Hellman. La première réalisation d'un système à clef publique fut
publiée en 1977 par Rivest, Shamir et Adleman : c'est le
chirement RSA.

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Fonctions à sens unique

Conceptuellement, on peut voir un système à clef publique

comme une fonction à sens unique.
La règle de chirement de Bob E doit être facile à appliquer.
On vient juste d'observer que l'inversion de cette fonction
(c'est-à-dire le décryptage) doit être dicile pour autre
personne que Bob.
La propriété d'être dicile à inverser s'énonce en disant que la
fonction est à sens unique. On souhaite donc que E soit une
fonction (injective) à sens unique.
Les fonctions à sens unique jouent un rôle central en
cryptographie. Elles sont importantes pour construire des
systèmes à clef publique.

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Fonctions à sens unique

Voici un exemple de fonction supposé à sens unique.

Supposons que n soit le produit de deux grands nombres
premiers p et q, et soit b un entier naturel supérieur à 2. On
dénit
f : Zn −→ Zn
par
f (x) = x b mod n
Pour certaines valeurs de b, ceci en fait la fonction de
chirement de RSA.

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Algorithme d'Euclide

Soient n  2 et Zn .
Un entier b ∈ Zn est inversible si, et seulement si
pgcd(b, n) = 1.
Le nombre d'entiers positifs strictement inférieurs à n et
premiers avec n est φ(n).
L'ensemble des résidus modulo n qui sont premiers avec n est
noté Z∗n .
On sait donc que tout b ∈ Zn admet un inverse b−1 , mais on
n'a pas encore de procédé ecace pour le calculer.
L'algorithme d'Euclide étendu le permet.

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

L'algorithme d'Euclide

L'algorithme d'Euclide consiste à eectuer la suite de divisions

suivante :
Algorithme :
Soient deux entiers r0 et r1 , avec r0  r1 .
r0 = q1 r1 + r2 avec 0 ≺ r2 ≺ r1
r1 = q2 r2 + r3 avec 0 ≺ r3 ≺ r2
.....
rm−2 = qm−1 rm−1 + rm avec 0 ≺ rm ≺ rm−1
rm−1 = qm rm .
On a pgcd(r0 , r1 ) = pgcd(r1 , r2 ) = .... = pgcd(rm−1 , rm ) = rm

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

L'algorithme d'Euclide étendu
Puisque l'algorithme d'Euclide calcule le plus grand diviseur
commun, il peut être utilisé pour déterminer si un entier positif
b ≺ n est inversible modulo n. En prenant r0 = n et r1 = b . Il ne
calcule cependant pas l'inverse lorsqu'il existe. Dénissons
maintenant la suite t0 , t1 , ..., tm suivant la relation de récurrence
(où les qj sont dénis ci-dessus) :
Algorithme :
t0 = 0
t1 = 1
tj = tj−2 − qj−1 tj−1 mod r0 si j  2.
On a le résultat suivant :
Résultats :
Pour 0  j  m, on a rj ≡ tj r1 mod r0 .
Si l'on a pgcd(r0 , r1 ) = 1 alors tm = r1−1 mod r0 .
Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie
Algorithme d'Euclide

Exemple :
L'algorithme d'Euclide étendu donne :
7−1 mod 26 = 15.
28−1 mod 75 = 67.

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Chirement RSA
Ce système utilise l'arithmétique de Zn , où n est le produit de deux
nombres premiers impairs distincts p et q . On calcule
φ(n) = (p − 1)(q − 1).
RSA
Soit n = pq où p et q sont premiers. Soit P = C = Zn . On dénit
K = {(n, p, q, a, b) : n = pq, p, q; ab ≡ 1 mod (φ(n))}

Pour K = (n, p, q, a, b), on dénit

E (M) = M b mod n

et
D(C ) = C a mod n
Avec M, C ∈ Zn . Les valeurs n et b sont publiques, et les valeurs p,
q, et a sont secrètes.
Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie
Chirement RSA

Exemple :
Supposons que Bob choisisse p=7 et q=5.
Il prend b = 7.
Si Alice souhaite transmettre le message 2 à Bob. elle calcule
E (2).
Bob veut déchirer le message reçu. Il calcule D(C ).

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

 Chirement d'El Gamal

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Calcul du logarithme discret

On suppose que p est un nombre premier et que α est une

racine primitive modulo p .
Le problème du logarithme discret peut s'énoncer ainsi :
Étant donné un β ∈ Z∗p , trouver l'unique exposant a,
0  a  p − 2 tel que αa ≡ β mod (p).
Par un pré-calcul de toutes les valeurs αa possible et le
stockage de la table triée des couples (a, αa mod p) suivant
leur second membre, on peut résoudre ce problème.
Le premier algorithme non trivial que l'on décrit est un
compromis espace-temps dù à Shanks.

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Calcul du logarithme discret

Algorithme de Shanks
√
Soit m = d p − 1e.
Calculer αmj mod p , 0  j  m − 1.
Trier les m couples (j, αmj mod p) suivant leur second
membre dans la liste L1 .
Calculer βα−i mod p , 0  i  m − 1.
Trier les m couples (i, βα−i mod p) suivant leur second
membre dans la liste L2 .
Chercher les couples (j, y ) ∈ L1 et (i, y ) ∈ L2 (de même
second membre).
Dénir logα β = mj + i mod (p − 1).

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Algorithme de Shanks

Exemple 1 :
Supposons p = 11. On cherche log3 9.
On a donc α = 3, β = 9.

Exemple 2 :
Supposons p = 809. On cherche log3 525.
√
On a donc α = 3, β = 525 et m = d 808e = 29.

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Chirement d'El Gamal
Soit p un nombre premier tel que le problème du logarithme discret
dans Zp soit dicile, et soit α ∈ Z∗p un élément primitif.

Soit P = Z∗p , C = Z∗p × Z∗p . On dénit :

K = {(p, α, a, β) : β ≡ αa mod (p)}

Les valeurs p, α et β sont publiques, et a est secret.

Pour K = (p, α, a, β),et pour un k ∈ Zp−1 aléatoire (secret),
on dénit
E (M, k) = (C1 , C2 )
Où C1 = αk mod p et C2 = Mβ k mod p
Pour C1 , C2 ∈ Z∗p , on dénit :

D(C1 , C2 ) = C2 (C1a )−1 mod p

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Chirement d'El Gamal

Exemple 1 :
Supposons p = 11, α = 3, a = 2 et β = 9.
Supposons qu'Alice souhaite transmettre le message M = 2 à
Bob.
Pour commencer, elle choisit au hasard k, disons k = 6. Elle
calcule E (M, k).
Bob veut déchirer le message reçu. Il calcule D(C1 , C2 ).

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Chirement d'El Gamal

Exemple :
Supposons p = 2579, α = 2, a = 765, calculer
β = 2765 mod 2579

Supposons qu'Alice souhaite transmettre le message

M = 1299 à Bob.
Pour commencer, elle choisit au hasard k, disons k = 853. Elle
calcule E (M, k).
Bob veut déchirer le message reçu. Il calcule D(C1 , C2 ).

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

 Signature

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Procédé de signature

on étudie les procédés de signature, que l'on appelle également

signatures électroniques
Ce procédé doit être coller au message.
Le procédé de signature est composé d'un algorithme de
signature et d'un algorithme de vérication.
Bob signe un message M suivant l'algorithme (secret) de
signature sig.
Le résultat sig (M) peut ensuite être vérié par un algorithme
publique de vérication ver.
Pour tout couple (M, C ), l'algorithme de vérication fournit
une réponse "vrai" ou "faux" suivant que C est une
authentique signature de M ou non.

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Procédé de signature
Voici une dénition plus formelle d'un procédé de signature.
Dénition
Un système cryptographique est un quintuplet (P, A, K, S, V)
satisfaisant :
1 P est un ensemble ni de messages.

2 A est un ensemble ni de signatures.

3 K est un ensemble ni de clefs possibles.

4 Pour tout K ∈ K, il y a une fonction de signature sigK ∈ S et

une fonction de vérication verK ∈ V. Les fonctions
sigK : P −→ A et verK : P × A −→ {vrai, faux} vérient, pour
tout message M ∈ P et chaque signature C ∈ A
Si C = sigK (M) alors verK (M, C ) = vrai
Si C 6= sigK (M) alors verK (M, C ) = faux
Pour chaque K ∈ K, les fonctions sigK et verK doivent être calculables en

temps polynomial. Et que verK doit être publique, et sigK doit être secrète.

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Combinaison chirement et signature

On peut combiner la signature et le chirement de cette manière.

Supposons qu'Alice souhaite envoyer un message signé et
chiré à Bob.
Pour un texte clair M donné, Alice calcule la signature
C1 = sigAlice (M) et chire M et C1 en utilisant la clef
publique de Bob par KpB , en obtenant C2 = EpB (M, C1 ).
Le texte chiré C2 est transmis à Bob.
A la réception, Bob déchire C2 l'aide de sa clef secrète par
DprB et obtient (M, C1 ).
Il vérie alors la signature C1 d' Alice à l'aide de sa clef
publique par verAlice (M, C1 ).

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie

Signature RSA
Le premier procédé de signature est le système à clef publique RSA
en mode de signature.
Signature RSA
Soit n = pq où p et q sont premiers. Soit P = A = Zn . On dénit
K = {(n, p, q, a, b) : n = pq, p, q; ab ≡ 1 mod (φ(n))}

Pour K = (n, p, q, a, b), on dénit

sigK (M) = M a mod n

et
verK (M, C ) = vrai ≡ M = C b mod n
Avec M, C ∈ Zn . Les valeurs n et b sont publiques, et les valeurs p,
q, et a sont secrètes.
Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie
 Questions ?

Réalisé par : Pr. EN-NAIMANI Zakariae Cryptographie