Clés publiques

Invention récente de Diffie et Hellman [2] Turing Award 2015.

Nous nous trouvons aujourd’hui à l’aube d’une révolu-
tion en cryptographie.
Idée géniale : asymétrique ; chiffrement ̸= déchiffrement.
Chiffrement par clé de chiffrement publique.
Déchiffrement par clé de déchiffrement privée.
Cryptographie à clé publique Utile pour résoudre le problème de la distribution des clés !
Principe de Kerckhoffs (1883) d’autant plus d’actualité
La sécurité d’un chiffre ne doit pas dépendre du secret
de l’algorithme mais seulement du secret de la clé.
http://fr.wikipedia.org/wiki/Principe_de_Kerckhoffs

Quelle sécurité ? Fonction à sens unique

Repose sur la sécurité calculatoire.
Soit P et C deux ensembles et f : P → C et f (P) image de P
Signification : cryptanalyste déploie plus d’efforts de calcul par f . f est à sens unique si
pour retrouver le clair (ou la clé) à partir du chiffré que la durée 1. ∀x ∈ P, f (x) facile à calculer (temps polynomial) et
de vie du clair. 2. Trouver, pour la plupart des y ∈ f (P) un x ∈ P tel que
f (x) = y doit être difficile [3, 4, 1].
Défis pour casser des clés RSA :
Avec seulement 2., déchiffrer aussi difficile que cryptanalyser.
• de 140 chiffres (463 bits en 1999) 2000 ans mips
• de 155 chiffres (512 bits en 1999) 8000 ans mips Ajouter une notion qui permet de déchiffrer et rendre la
de 232 chiffres (768 bits en 2010) 4, 5.106 ans mips cryptanalyse difficile.
•
http://actualites.epfl.ch/presseinfo-com?id=859 → Notion de trappe.
Pour info, un i7 développe au max 318 MIPS.
 Fonction à sens unique à trappe 1er chiffre à clé publique

f : P → C à sens unique est à trappe si le calcul dans le sens

inverse est efficace en disposant d’une information secrète -la 1978 : Rivest Shamir et Adleman.
trappe- qui permet de construire g tq. g ◦ f = Id.
• cherchaient une contradiction dans le concept de clé
publique.
Facile de calculer l’image par f mais calculatoirement difficile
d’inverser f sans connaître g. • parviennent au résultat inverse et obtiennent le Turing
Award 2002 !
Construire des couples (f , g) doit être facile. http://amturing.acm.org/lectures.cfm
Publier f ne doit rien révéler sur g.

Idée : algos (2 clés) ̸=, f pour chiffrer et g pour déchiffrer.

Rivest, Shamir, Adleman (1978) Rappels mathématiques

Indicatrice d’Euler de n ∈ N : ϕ(n) : nombre d’entiers de [[1, n]]
premiers avec n. ϕ(1) = 1 et pour p premier, ϕ(p) = p − 1.
Repose sur la difficulté calculatoire de factoriser un nombre et
sur la difficulté calculatoire de décider la primalité. ϕ(n) = card{j ∈ {1, . . . , n} : gcd(j, n) = 1}
Par exemple, 1829 est-il premier ?
Calcul : décomposer n en n = p|n,p premier p³p alors,
Non : on vous donne 31 et 59, on vérifie en les multipliant que 1829 est leur produit, mais les trouver est beaucoup

plus difficile. Surtout qu’on ne connait pas a priori le nombre de facteurs premiers de 1829.
ϕ(n) = p|n,p premier (p³p − p³p −1 ) = n p|n (1 − p1 ).
Ou bien, 7919 est-il composé ? Exemple : ϕ(12) = (4 − 2)(3 − 1) = 12(1 − 12 )(1 − 13 ) = 4
Non, mais le certificat de primalité est plus «difficile» à exhiber.
Théorème (Fermat-Euler)

mφ(n) ≡ 1 mod n si gcd(m, n) = 1

 Calculer ab mod n À la main
Exponentiation modulaire (a, b, n)
d ← 1; 1773 mod 100. 73 = ï1001001ð
k
Soit ïbk , bk −1 , . . . b0 ð la représentation binaire de b = i=0 bi 2
i

172 172
i i
Pour i ← 0 jusqu’à k pas -1 faire i bi mod 100 valeur
d ← (d.d) mod n ; 0 1 17 17 mod 100 17
si bi = 1 alors d ← (d.a) mod n fsi ; 1 0 172 289 mod 100 89
renvoie d 2 0 892 7921 mod 100 21
3 1 212 441 mod 100 41
4 0 412 1681 mod 100 81
def expMod(a,b,n): 5 0 812 6561 mod 100 61
d = 1
6 1 612 3721 mod 100 21
for i in bin(b)[2:] :
d = (d*d) % n 3 6
et 1773 mod 100 = 17.172 .172 = 17.41.21 mod 100 = 37.
if i == ’1’: d = (d*a) % n
return(d)

Chiffre RSA Attaque sur les paramètres

Cycles : Fred voit c = me mod n et essaye de trouver ν t.q.
ν
1. choisir p, q premiers assez grands de l’ordre de 10100 ce ≡ c mod n ô e¿ ≡ 1 mod ϕ(n)
2. fixer n = pq et publier n ν−1
Permet de trouver m ≡ c e mod n.
3. calculer ϕ(n) = (p − 1)(q − 1) ν
En effet c ≡ c mod n ô c
e e ν −1
≡ 1 mod n et, par le
4. publier e tq gcd(e, ϕ(n)) = 1 (clé publique, encipher ) théorème d’Euler, e − 1 ≡ 0 mod ϕ(n) ô e¿ ≡ 1 mod ϕ(n).
¿

5. calculer d tq d.e ≡ 1 mod ϕ(n) (clé privée, decipher ) Comme c = me mod n et de ≡ 1 mod ϕ(n), on peut prendre
d = e¿−1 pour déchiffrer.
Chiffrer : E : M → M e mod n (M < n).
Exemple : Alice publie sa clé publique (e, n) = (17, 143), Fred
Déchiffrer : D : C → C d mod n (d est la trappe).
intercepte c = 19. Il calcule :
Implémentations : logicielles, matérielles ou mixtes. Sur des
cartes dédiées, RSA environ 1000 fois plus lent que DES. i 2 3 4
i
ce 84 28 19

Il ne lui reste plus qu’à «lire» m pour i = 3, soit 28.

 Attaque à ϕ(n) connu Crible d’Eratosthène
Connaître (n, ϕ(n)) revient à connaître la factorisation de n [3].
n = pq
En posant : et q = pn :
ϕ(n) = (p − 1)(q − 1) √
On divise n par tous les impairs entre 3 et + n,.
n Méthode efficace pour n < √ 1012 et connue depuis l’antiquité.
ϕ(n) − (p − 1) −1 = 0 ô p2 + p (ϕ(n) − n − 1) + n = 0
p Crible d’Eratosthène en O( n).

équation du second degré de solutions p et q. Pas polynomial mais pseudo polynomial ! La complexité en
Calculer ϕ(n) aussi difficile que factoriser n. temps n’est pas polynomiale en la longueur de l’entrée (log(n)).

Exemple De plus, dans le cas de RSA, le module n n’a pas de «petits»

facteurs premiers.
n = p.q = 133 et ϕ(n) = 108. ϕ(n) − (p − 1) n
p −1 =0
ô p2+ p (ϕ(n) − n − 1) + n = p2
+ p(108−133−1) + 133 =
2
0 ô p − 26.p + 133 = 0 avec
∆ = (−26)2 − (4.133) = 144 = 122 ; sol. p = 26±12
2 = {19, 7}.

Sûreté Man in the middle

Porte sur la communication des clés.
• Bob (client) demande à Alice (serveur) sa clé publique

RSA est aussi sûr que la factorisation de n est difficile. • Alice envoie eS , nS à Bob
Complexité de quelques «bons» algorithmes de factorisation : • Melchior intercepte eS , nS et envoie ses paramètres eM , nM
√ • Bob chiffre en utilisant à son insu eM , nM et envoie c
crible quadratique O(e((1+o(1))√log n log log n) )
• Melchior intercepte le message c et le déchiffre en secret
courbes elliptiques O(e((1+o(1)) 2 log p log log p) )
crible algébrique
1/3 2/3
O(e((1,92+o(1))(log n) (log log n) ) )
• Melchior rechiffre secret avec eS , nS et transmet à Alice. . .
Serveur Melchior Client
eS,nS eM,nM
(p : plus petit facteur premier de n).

Serveur
Client
eS,nS eM,nM

secreteS mod nS secreteM mod nM

Ah ! si Bob avait pu s’assurer que les données venaient d’Alice.

Objectifs des systèmes à clé publique Signatures
• confidentialité
Utilisation légale depuis le 29 février 2000, loi N. 2000-230
• authentification : garantie de l’authenticité de l’origine Art.3 :L’écrit sur support électronique a la même force probante
• identification : affirmation de son identité électronique que l’écrit sur support papier.

• intégrité : garantie qu’il n’y a pas eu de modification Signatures introduites par Diffie et Hellman [2].
But : apporter la preuve à un tiers de l’identité de l’expéditeur
• non répudiation : émission/réception message irréfutable
(ie l’authentifier) et de l’intégrité du message.
Autres mécanismes cryptographiques nécessaires :
La signature dépend de l’identité du signataire et du message.
• signature : moyen d’associer l’expéditeur à un message
Empèche deux types de fraudes :
• certificat : attestation (d’un tiers) qui confirme une identité
• la falsification du message ;
• tiers de confiance : l’autorité qui délivre les certificats
• la non-reconnaissance du message par l’expéditeur.
• estampillage : ajout de dates garantes de l’unicité du message

Cahier des charges de sig(M) Mécanisme général de signature

• algorithme de signature (privé), sig qui, pour une clé

privée SK , retourne une signature S pour un clair M ;
• facile à calculer par le signataire pour tout message M
sigSK (M) = S = {M}SK
• le destinataire doit pouvoir vérifier la signature
• un tiers doit pouvoir vérifier la signature • algorithme (public) de vérification, ver qui, à une clé
• impossible à falsifier publique PK et pour tout couple clair/signature (M, S) va
vérifier si la signature correspond bien au clair.
• on ne peut pas imiter la signature de l’expéditeur.
vrai si S = sigSK (M) ie {S}PK = M
verPK (M, S) =
faux sinon
 Signer avec RSA Envoi d’un message secret signé
Bob désire envoyer un message M signé à Alice. Ils disposent Comment Bob envoie à Alice un message secret signé ?
pour cela de leurs clés RSA respectives : Privés Publics
Privée Publique Alice DA (C) = C dA mod nA EA (M) = M eA mod nA
Alice dA n A , eA Bob DB (C) = C dB mod nB EB (M) = M eB mod nB
Bob dB nB , eB Bob envoie à Alice le message
Le procédé de signature est alors :
C = EA (DB (M))
sigSK (M) = M dB mod nB = S
Et Alice déchiffre le message de Bob en
Celui de vérification :
EB (DA (C))
verPK (M, S) = vrai ô S eB mod nB ≡ M
Pour cela, il faut que M < nB < nA .
C’est ce qu’on appelle RSAKE.

Problème du log. discret Calcul du log. discret

Problème du logarithme discret de y en base g :
Devient très difficile quand le cardinal de G croît.
Instance : g, y éléments d’un groupe multiplicatif fini G.
Algo de calcul du logarithme discret : Shanks s’applique à tout
Question : trouver x tel que g x ≡ y dans G groupe fini G. Complexité en temps O( |G| log |G|) et
ou, pour p un grand premier, g un générateur de G = Z⋆p , O( |G|) en espace.
g x ≡ y mod p et x = logg (y ) mod p − 1. Idée : construire deux listes de puissances de g :
Exemple √
Soit G = Z⋆7 un groupe. • une liste de petits pas {g i : i = 0..+√ n, − 1} avec n = |G|
√
En base g = 2, seuls 1, 2 et 4 possèdent un logarithme discret. • une liste de pas de géant y g −+ n,j : j = 0..+ n, .
En base g = 3, on obtient : Puis trouver un terme commun aux 2 listes (i0 , j0 ). Ainsi,
nombre y 1 2 3 4 5 6 √ √
g i0 = y (g −j0 + n,
) et x = i0 + j0 + n,
logarithme 6 2 1 4 5 3

Par exemple pour nombre = 1 et log = 6.

Cela signifie que log3 1 = 6, ce qu’on vérifie par 36 mod 7 = 1.
Log. discret de y = 4 dans Z7, g = 3 Exemple
√
On travaille dans Z×
113 =< 3 > d’ordre n = 112 ; n = r = 11.
On cherche le logarithme discret de y = 57 en base g = 3 :
√ Liste (non ordonnée) des petits pas, forme (exposant, valeur) :
On a r = + 7, = 3
Petits pas : Table[Mod[g i , 7], {i, 0, r - 1}]
B = {(0, 1), (1, 3), (2, 9), (3, 27), (4, 81),
{1, 3, 2} (5, 17), (6, 51), (7, 40), (8, 7), (9, 21), (10, 63)}

Liste (non ordonnée) des pas de géant, forme (exposant,

s inverse de g mod 7 : {d, {s, t}} = ExtendedGCD[g, 7]
valeur) :
Grands pas : Table[Mod[y ∗ s(r ∗j) , 7], {j, 0, r}]
L = {(0, 57), (1, 29), (2, 100), (3, 37), (4, 112), (5, 55), (6, 26),
{4, 3, 4, 3}
(7, 39), (8, 2), (9, 3), (10, 61), (11, 35)}
3 commun aux deux listes i0 = 1, j0 = 1 : x = i0 + r · j0 = 4
3 est commun aux petits pas et aux grands pas, il a été
engendré pour i0 = 1 dans la liste B et pour j0 = 9 dans la liste
L. Le logarithme discret que l’on cherchait est
x = i0 + r .j0 = 100. Vérification : on calcule g x mod 113 = 57.

Signature par El Gamal Exemple

Soit p un nombre premier pour lequel le problème du logarithme Soit p = 467 et a = 127. On a bien que gcd(a, p − 1) = 1. Soit
discret est difficile dans Z⋆p et soit α un générateur de Z⋆p . α = 2 un élément primitif de Z×
p . On calcule
Le message M ∈ Z⋆p et sa signature est constituée du couple
(M, S) ∈ Z⋆p × (Z⋆p × Z⋆p−1 ). L’ensemble des clés est β = αa mod p = 2127 mod 467 = 132
K = {(p, α, a, β) : β = αa mod p}
Si Bob veut signer le message M = 100 pour la valeur aléatoire
Privé Publics k = 213 qui vérifie bien gcd(k , p − 1) = 1, il calcule l’inverse de
a p, α, β k −1 mod p − 1 par Euclide étendu qui donne k −1 = 431 alors,

On choisit k ∈ Z⋆p−1 aléatoire et secret qui vérifie gcd(k , p − 1) = 1. γ = αk mod p = 2213 mod 467 = 29
On définit une signature comme :
et
sigK (M, k ) = (γ, δ)
δ = (M−aγ)k −1 mod (p−1) = (100−127.29).431 mod 466 = 51
pour γ = αk mod p δ/aγ + k δ ≡ M mod (p − 1)
 Vérification G. Brassard.
Cryptologie contemporaine.
Pour M, γ ∈ Z⋆p et δ ∈ Zp−1 , on définit Logique, mathématiques, informatique. Masson, 1993.

W. Diffie and M.E. Hellman.

New directions in cryptography.
vérK (M, γ, δ) = vrai ô β µ γ ¶ ≡ αM mod p IEEE Trans. on Inform. Theory, 22(6) :644–654, 1976.

N. Koblitz.

Si la signature est construite correctement, la vérification A course in number theory and cryptography.
Graduate texts in mathematics. Springer Verlag, 1987.
authentifie la signature car : A. Salomaa.
Public Key Cryptography.
EATCS monographs. Springer Verlag, 1990.
β µ γ ¶ ≡ αaµ αk ¶ mod p ≡ αM mod p

en utilisant le fait que aγ + k δ ≡ M mod (p − 1).

Exemple : On authentifie la signature de (100, 29, 51) par :

vérK (M, γ, δ) = vrai ô β µ γ ¶ ≡ αM (p) ô 13229 2951 ≡ 2100 (p) ≡ 189

qui valide la signature précédente.