ENIG AU : 2017-2018

Le chiffrement par clé publique

1. Introduction
Dans le cas des systèmes asymétriques, chaque personne possède 2 clés distinctes (une privée,
une publique) avec impossibilité de déduire la clé privée à partir de la clé publique. De ce fait,
il est possible de distribuer librement cette dernière.

Figure 1: Chiffrement à clé publique

On peut classer l’utilisation des algorithmes à clé publique en 3 catégories :

– Chiffrement/déchiffrement : cela fournit le secret. L’expéditeur chiffre avec la clé publique
du destinataire et ce dernier déchiffre avec sa clé privée.
– Signatures numériques : cela fournit l’authentification (traité en détail dans le chapitre
suivant). L’expéditeur signe avec sa clé privée et le dentinaire vérifie la signature avec la clé
publique de l’expéditeur.
– Échange de clés (ou des clefs de session) par exemple Diffie-Hellman.
Quelques algorithmes conviennent pour tous les usages, d’autres sont spécifiques à l’un
d’eux.

2. RSA : Rivest - Shamir - Adleman

Crée en 1978, il est basé sur le calcul exponentiel. Sa sécurité repose sur la fonction
unidirectionnelle suivante : le calcul du produit de 2 nombres premiers est aisé. La
factorisation d’un nombre en ses deux facteurs premiers est beaucoup plus complexe.

Il s’agit du système le plus connu et le plus largement répandu, basé sur l’élévation à une
puissance dans un champ fini sur des nombres entiers modulo un nombre premier. Il emploie
de grands nombres entiers (par exemple représentés sur 1024 bits).

Ce cryptosystème utilise deux clés e et d, interchangeables. Le chiffrement se fait selon

C = Me mod n

1
ENIG AU : 2017-2018

et le déchiffrement par M = Cd mod n.

La sécurité repose sur le coût nécessaire pour factoriser de grands nombres. Le nombre de
factorisation prend environ O(elog n log(log n)) opérations ce qui demande un temps de calcul trop
important pour les machines actuelles, dans un cadre privé. On l’utilise pour la confidentialité,
l’authentification, ou encore une combinaison des 2.

2.1 Principes
On possède une paire de clés, l’une publique (e,n) et une privée (d,n). La première étape
revient à choisir n. Il doit s’agir d’une valeur assez élevée, produit de 2 nombres premiers très
grands p et q. En pratique, si p et q ont 100 chiffres décimaux, n possèdera 200 chiffres. Selon
le niveau de sécurité souhaité, la taille de n peut varier : 512 bits, 768, 1024 ou 2048.

Ensuite, on choisira un très grand entier e, relativement premier à Φ(n) = (p-1)*(q-1).

La clé publique sera formée par (e, n). On choisira ensuite un d tel que

e * d ≡ 1 mod (Φ(n)).

La clé privée sera donnée par (d, n).

Dernière phase : on jette p et q. Le cryptanalyste devant retrouver ces valeurs, il faut les
détruire pour éviter les fuites.

Justification de l’inversibilité

Par les théorèmes d’Euler et de Fermat, on sait que

aΦ(n). ≡ 1 mod n

et aΦ(n).mod 1 = 1 où (a,n)=1.

Dans le RSA, on a n = p * q. De plus, Φ(n) donne le nombre d’entiers positifs plus petits que
n et relativement premiers à n (si p est premier, Φ(p) = p − 1). Si n = p * q, avec p et q
premiers, il vient Φ (n) = Φ (p) * Φ (q) = (p − 1) * (q − 1)

De par la façon de choisir e et d,

e * d ≡ 1 mod Φ(n) = k * Φ(n) + 1

pour un certain k.

De plus, par définition et propriétés des opérations modulo n, on a :

Dk(Ek(M)) = ((M)e mod n)d mod n = (Me)d mod n = Me*d mod n

Et donc :

Me*d = Mk*Φ(n)+1 = Mk*Φ(n).M mod n = 1.M mod n = M mod n

2
ENIG AU : 2017-2018

2.2 Résumé
1. Génération de 2 nombres premiers p et q

2. Calcul de n = p*q

3. Déterminer e tel que 3 < e < Φ(n) et (e, Φ(n)) = 1

4. Calculer d tel que e * d ≡ 1 mod Φ(n)

5. Clé publique : (e,n)

6. Clé privée : (d,n)

7. p et q doivent rester secrets, voir supprimés

8. C = Me mod n et M = Cd mod n

Exemple : (source : [Link]

Chiffrement :

• Prenons p=5 et q=11 donc n=pq=55 et (p-1)(q-1)=40

• Prenons e=7, on s’assure (Euclide) que e est premier avec 40

• On détermine alors l’inverse mod (p-1)(q-1) (Euclide étendu)

• La clé publique vaut (e=7, n=55), la clé privée vaut d=23, les nombres p=5 et q=11
sont détruits

• Soit à coder un fragment de message représenté par la valeur m=2, le calcul de c est
simplement
c=27 mod 55 = 128 mod 55 = 18

Déchiffrement :

le destinataire calcule de cd mod n=1823 mod 55 (on utilise ici l’exponentiation rapide qui
permet de ne manipuler que des nombres relativement petits alors que 1823 est de l’ordre de
1029)

NB : 232=10111

181 mod 55 = 18 1 18
182 mod 55 = 324 mod 55 = 49 1 18*49 mod 55=2
184 mod 55 = 492 mod 55 = 2401 mod 55 = 36 1 2*36 mod 55=17
188 mod 55 = 362 mod 55 = 1296 mod 55 = 31 0 17
1816 mod 55 = 312 mod 55 = 961 mod 55 = 26 1 17*26 mod 55=2
1823 mod 55 = 2

3
ENIG AU : 2017-2018

2.3 Exercice
Nous avons la clé publique RSA (e = 17, n =33) et aussi le codage de l'alphabet suivant :

Répondre aux questions suivantes en donnant les étapes de calcul à faire :

1) Chiffrez le mot « edith »

2) Calculez la clé de déchiffrement d
3) Déchiffrez « ml.z »

2.4 Sécurité
Il existe trois approches pour attaquer le RSA :

– recherche par force brute de la clé (impossible étant donné la taille des données),

– attaques mathématiques (difficulté de calculer Φ(n), de factorisation du module n)

- factoriser n=p*q et par conséquent trouver Φ(n) et puis d,

- déterminer Φ(n) directement et trouver d,
- trouver d directement.

– attaques de synchronisation (sur le fonctionnement du déchiffrement), il s’agit d’exploiter

les variations de temps pris pour effectuer certaines opérations (par exemple la multiplication
par un petit ou un grand nombre)
- La menace quantique (encore théorique)

2.5 Conseils d’utilisation du RSA

Pour garantir une bonne sécurité, il faut respecter certains règles telles que :
– Ne jamais utiliser de valeur n trop petite,
– N’utiliser que des clés fortes (p-1 et q-1 ont un grand facteur premier),
– Ne pas chiffrer de blocs trop courts,
– Ne pas utiliser de n communs à plusieurs clés,
– Si (d,n) est compromise ne plus utiliser n.

4
ENIG AU : 2017-2018

3. El Gamal
C’est un algorithme à clef publique présent à la base de la norme U.S. de signature
électronique. Il fut inventé par Taher ElGamal en 1984. Il est basé sur la difficulté de calculer
des logarithmes discrets.

Le problème du logarithme discret (DLP) consiste à retrouver un entier λ tel que

h = gλ mod p.

3.1 Principe du chiffrement

Soit un entier premier p très grand et p − 1 doit avoir un grand facteur premier. On produit :

– une clé privée s, telle que s ∈ (1...p − 2),

– une clé publique reposant sur l’entier p, un entier a premier avec p, et l’entier P tel que

P = as mod p

Le nombre a est pris tel que a ∈ (0...p − 1) et ∀ k ∈ (1...p − 2) :

ak ≠1 mod p

Soit un message M, avec M < p. On détermine un nombre aléatoire k qui n’est connu que de
celui qui chiffre et différent à chaque message. On calcule alors

C1 = ak mod p

C2 = [Link] mod p

On obtient alors le message chiffré C = (C1,C2). Le message chiffré est alors deux fois plus
long que le message original.

3.2 Principe du déchiffrement

A la réception, on calcule R1 = (C1)s mod p

= ask mod p

= Pk mod p

Le destinataire possède la clé privée (s). Ayant Pk, on divise C2 par cette valeur :

DK(C) = C2/(R1)

= [Link] mod p/Pk mod p

=M

Pk est donc considéré comme un masque appliqué sous forme multiplicative à M.

5
ENIG AU : 2017-2018

Pour décrypter le message, il faudra soit trouver directement un masque jetable, soit trouver la
clé privée s, solution de P = as mod p (et donc trouver le logarithme discret).

Exemple :

Soient p = 2579, a = 2, s = 765. Il vient

– Clé privée Sk = (765)

– Clé publique Pk = (2579, 2, 949) car 2765 mod 2579 = 949 = P

Pour chiffrer M = 1299, on choisit k = 853. Il vient

C1 = 2853 mod 2579 = 435

C2 = 1299 * 949853 mod 2579 = 2396

On peut effectivement vérifier que 2396/(435765) mod 2579 = 1299.

3.3 Efficacité et sécurité

El Gamal est 2 fois plus lent que le RSA. L’inconvénient majeur reste la taille des données
chiffrées qui représente 2 fois celle des données en clair. La recherche de la clé privée (s) à
partir de la clé publique est équivalente au problème du logarithme discret.

4. La cryptographie basée sur les courbes elliptiques

Il s’agit d’un concept proposé en 1985 par deux chercheurs Miller et Klobitz, de façon
totalement indépendante. Ce type de cryptographie, toujours basé sur le modèle asymétrique
permet aussi bien de chiffrer que de signer. On utilise souvent l’abréviation ECC, pour
Elliptic Curve Cryptography. Les clés utilisées sont plus courtes pour une sécurité égale ou
supérieure.

D’une manière générale, sur R, les courbes elliptiques seront considérées comme l’ensemble
des couples (x,y) tels que

y2 = x3 + ax + b

dont le discriminant

-16(4a3 + 27b2) est non nul.

Pour la dessiner, pour a et b fixés, on calcule y tel que

y = ±√ + +

La figure 2 présente deux exemples de courbes elliptiques sur R

6
ENIG AU : 2017-2018

Figure 2: Deux exemples de EC

4.1 Définition géométrique

Soit une opération (l’addition, +) pour l’ensemble E(a, b) tel que a et b répondent à la
condition du discriminant.

Si 3 points sur une EC sont alignés, leur somme vaut O (point à l’infini).

1. O est l’identité pour l’addition : O = −O.

2. Pour n’importe quel point P + O = P.

3. L’opposé d’un point P(x, y) est P(x,−y)

4. Pour additionner 2 points P et Q, on trace la droite les reliant. Cela nous donne un point
d’intersection R. On définit l’addition telle que P + Q = −R. En conséquence, on définit P + Q
comme étant l’opposé de ce point R.

4.2 Les EC sur Zp

Dans Zp ou corps de Galois, Les variables et coefficients prennent des valeurs dans
l’ensemble [0, p − 1] pour un certain nombre premier p, et où toutes les opérations sont
calculées modulo p. L’équation devient

y2 mod p = (x3 + ax + b) mod p

Cette équation est par exemple satisfaite pour a = 1, b = 1, x = 9, y = 7 et p = 23.

72 mod 23 = (93 + 9 + 1) mod 23

49 mod 23 = 739 mod 23

3=3

On note Ep(a, b) l’ensemble des couples d’entiers (x, y) qui satisfont cette équation. On parle
de groupe elliptique.

7
ENIG AU : 2017-2018

Exemple : Soient p = 23 et la courbe elliptique y2 = x3 + x + 1. On est donc dans E23(1, 1).

Comme nous travaillons dans Z23, les couples (x, y) répondant à l’équation sont donnés à la
figure 3.

Figure 3: points (x, y) de E23(1,1)

4.3 L’addition
Posons P1(x1, y1), P2(x2, y2), P3(x3, y3).

Par convention O(I,I), I comme Infini. On a: (admis)

1) -P1(x1, -y1)

2) Si x1 ≠ I, x2 ≠ I et P1 = -P2 alors x3 = I et y3 = I.

3) Si x1 ≠ I, x2 ≠ I et P1 ≠ P2 alors en posant

m = (y2 - y1) / (x2 - x1),

x3 = m2 - x1 - x2

et y3 = m.(x1 - x3) - y1.

4) Si x1 ≠ I, x2 ≠ I et P1 = P2 alors en posant

m = (3.x12 + a) / (2.y1) puis utiliser les mêmes formules qu'en 3).

5) Le reste est évident.

TD : vérifiez que (0,1) + (1,7) = (12,19) et (1,7) +(1,7) = (7,11)

4.4Calcul de k*P
Pour calculer le résultat de l’addition d’un point avec lui-même: le point k. P

Q = k. P = P + P + … + P (k-1 fois)

Nous utilisons La version de square and multiply dans le cas d’une courbe elliptique
8
ENIG AU : 2017-2018

calculer Q = 77.P

On écrit 77 en binaire : 77 = (1001101)2.

Ensuite si le bit traité est 0, on double le point et si le bit traité est 1 on double le point
et on rajoute au résultat P :

P→ 2.P → 4.P → 9.P → 19.P → 38.P → 77.P

1 0 0 1 1 0 1

4.5 Utilisation des courbes elliptiques dans la cryptographie

Pour utiliser les courbes elliptiques en cryptographie, il faut trouver un problème difficile (tel
que la factorisation d’un produit en ses facteurs premiers dans le cas du RSA).

Considérons l’équation Q = kP

où Q, P ∈ Ep(a, b) et k < p.

Il est facile de calculer Q connaissant k et P, mais il est difficile de déterminer k

si on connait Q et P. Il s’agit du problème du logarithme discret pour les courbes
elliptiques ECDLP.
Dans une utilisation réelle, le k est très grand, rendant l’attaque par force brute inutilisable
(rappelons qu’a priori, l’attaque par force brute est toujours possible).

4.5.1 L’utilisation de l’ECC

• Dans les standards :

– ANSI Public Key Cryptography for the Financial Services Industry

• X9.62-1998 — The Elliptic Curve Digital Signature Algorithm

(ECDSA)

• X9.63-1999 — Key Agreement and Key Transport Using Elliptic

Curve Cryptography (ECIES etc.)

– NIST — Digital Signature Standard FIPS 186-2 (revision 2000)

– IEEE P1363a — Standard Specifications for Public Key Cryptography

– Standards for Efficient Cryptography Group (Certicom)

• Digital stamps

• OpenSSL

• Digital Rights Management (Windows Media Player 7.0)

9
ENIG AU : 2017-2018

4.5.2 ECC pour l’échange de clés symétriques

On présente tout d’abord l’algorithme d’échange des clés de Diffie- Helman (figure 4).
p un nombre premier et g un générateur de Zp (gk ≠ 1 mod p)

Figure 4: Diffie Hellman

Dans les courbes elliptiques, le générateur g est remplacé par un point P de Ep(r,s) et
l’exposant par la multiplication k fois. (voir figure 5)

Figure 5 : ECDH

Ce protocole est vulnérable à « l'attaque de l'homme du milieu », qui implique un attaquant

capable de lire et de modifier tous les messages échangés entre Alice et Bob.

10
ENIG AU : 2017-2018

4.5.3 ECC pour chiffrer des données

Il faudra ici encoder le texte clair m comme un point Pm de coordonnées x et y. C’est ce point
qui sera chiffré. Il faut ici aussi rendre publique un point G et un groupe elliptique Eq(a, b).
Les utilisateurs doivent également choisir une clé privée et générer la clé publique
correspondante. B possède une clé privé nB et une clé publique PB / PB = nB*G

Pour chiffrer le message, A détermine aléatoirement un nombre entier positif k et produit Cm

comme un couple de points tel que

Cm = {kG, Pm + kPB}

On remarquera l’utilisation de la clé publique de B. Pour déchiffrer, B devra multiplier le

premier point par sa clé privée, et soustraire le résultat au second point reçu :

Pm + kPB − nB(kG) = Pm + k(nBG) − nB(kG) = Pm

4.6 Exercice
Alice et Bob se mettent d’accord sur une courbe elliptique Ep(a,b) définie dans le corps GF(p)
avec p premier et vont utiliser le protocole de Menezes-Vanstone décrit dans ce cadre:

ALICE BOB

Alice choisit un point P de E

Elle choisit un secret S et calcule

le point Q = S.P

Elle rend publique les points P et Q

Bob veut envoyer le message M(x,y) à Alice,

il choisit k

1) calcule U= k.P
2) calcule le point (c,d) = k.Q
3) calcule v = c.x (modulo p)
4) calcule w = d.y (modulo p)
<------------------------------------(U,v,w)

1) calcule S.U = (c,d)

2) calcule Inv(c).v = x
3) calcule Inv(d).w = y
Alice retrouve M(x,y)

11
ENIG AU : 2017-2018

Questions :

Alice utilise la courbe elliptique E : Y2=X3 + 2X – 1 définie dans le corps GF(7) (c-a-d p = 7)

Alice choisit P(2,2) et S = 5

1) Donner les points de la courbe E autre que le point Infini,

2) Calculer Q.
3) Bob veut envoyer M(4,2) (c-a-d x = 4 et y = 2) à Alice, il choisit k = 3
Calculer les paramètres U, v et w

4) Dans un autre cas, calculer le point M’(x,y) sachant que Alice reçoit les paramètres
suivant : U = (1,3), v = 2 et w = 3 (question indépendante de la question 3)

4.7 Sécurité de l’ECC

Si on compare la sécurité du RSA à l’ECC, en se basant sur des techniques de cryptanalyse
relativement récentes, on obtient les longueurs minimales, en bits, du tableau suivant.

Crypto symétrique ECC RSA/DSA

56 112 512
80 160 1024
112 224 2048
128 256 3072
192 384 7680
256 512 15360

5. Comparaisons
Asymétrique(RSA) Asymétrique(ECC)
Avan- - Cryptosystème largement - Taille de clé inférieure pour une sécurité égale
tages répandu - La taille des clés croit moins vite que le RSA si
- Nombreuses études au sujet on souhaite une meilleure sécurité
de sa sécurité - Utilisation pour systèmes embarqués
- Calculs moins lourds que l’exponentiation
- Utilisation mémoire moindre
- Cryptanalyse par algorithme exponentiel
Inconvé - Opérations de - Complexe
-nients dé/chiffrement très inégales - Peu de développement sur des systèmes
en termes de temps de calcul à grande échelle (mais tend à changer)
- Cryptanalyse par algorithme - Travaux d’optimisation essentiellement destinés
sous exponentiel aux systèmes mobiles

12
ENIG AU : 2017-2018

Symétrique Asymétrique
Avantages - Cryptosystème largement - Distributions des clés facilitées : pas
répandu d’authentification
- Facilité d’implantation sur - Permet de signer des messages
hardware facilement
- Taille de clé mémorisable: 128 - Nombre de clés à distribuer est réduit
bits ( 16 caractères) par rapport aux clés symétriques
Inconvénients - Nombre de clés à gérer - Taille des clés
- Distribution des clés - Vitesse de chiffrement
(authentification,
confidentialité)
- Certaines propriétés ([Link].
signatures) sont difficiles à
réaliser

Les figures 6, 7 et 8 représentent les recommandations des tailles des clés minimale pour une
utilisation sure d’un système symétrique et asymétrique qui sont données par le site
[Link]

Figure 6: French Network and Information Security Agency (ANSSI) 2014

Figure 7: National Security Agency NSA -USA 2016

Figure 8: German federal office for information security, BSI 2017

13