1

CH2- Crypto Système à Clé Secrète

Présentation d’IDEA

IDEA (International Data Encryption Algorithm)

Conçu dans les années 90 par deux chercheurs suisses (lai et massey)
IDEA est breveté aux etats-unis et dans de nombreux pays
européens;
Opère sur des blocs de 64 bits;
Utilise une clé de 128 bits .

Cet algorithme est considéré comme étant assez nettement

supérieur au DES en terme de sécurité. Sa vitesse d’exécution
reste comparable avec le DES. Ses implémentations hardware
sont simplement légèrement plus rapides.
 2

CH2- Crypto Système à Clé Secrète

Présentation d’IDEA
Le bloc d'entrée de 64 bits est divisé en 4 blocs de 16 bits A ,B,
C, et D qui deviennent les blocs d'entrée de l'algorithme.

Lors de chacun des 8 tours, trois opérations sont effectuées :

1. Un Xor (ou-exclusif); représenté par ф

16
2. Une addition Modulo 2 +1 ;représentée par : ±
16
3. Et une Multiplication modulo 2 +1; représentée par ×
 3

CH2- Crypto Système à Clé Secrète

Fonctionnement d’IDEA
B C D
A
K1 × K2 ± K3 ± K4 ×

ф ф
8 Rounds
K5 ×
±

× K6
±

ф ф
ф
ф
 4

CH2- Crypto Système à Clé Secrète

Attaque de l’IDEA

IDEA résistera encore pendant quelques dizaines d'années aux

attaques cryptanalytiques.

Aucune attaque existe contre l'IDEA.

IDEA avec 5 tours (au lieu de 8) est cassé.

 5

CH2- Crypto Système à Clé Secrète

CONCLUSION

Dans les cas où les deux interlocuteurs sont sûrs, il est

préférable d'utiliser un chiffrement symétrique.

Parmi les chiffrements symétriques, le chiffrement AES, très

récent, s'avère être le plus efficace.

Il est d'ailleurs très employé depuis son officialisation.

 6
CH2- La Sécurité

• Sûreté d'un chiffrement

• Théorie de Shannon
• Secret parfait
Théorie de RSA et mise en œuvre
• Crypto systèmesetàattaque
Factorisation clé secrète
de RSA
• Crypto systèmes à clé publique
• Hachage et schémas de signature
• Certificats, gestion de clés
• Illustration avec PGP/gnupg
 7

CH2- Crypto Système à Clé Publique

Présentation

Alice génère deux clés : la clé publique (Dorée) qu'elle envoie à Bob et la
clé privée (Normale) qu'elle conserve précieusement sans la divulguer à
quiconque.
Bob chiffre son message avec la clé publique d'Alice et lui envoie le texte
chiffré. Alice déchiffre le message grâce à sa clé privée.

Clé1 Données Chiffrées Clé1

ALICE BOB
Clé2
 8

CH2- Crypto Système à Clé Publique

Présentation

Le but de la cryptologie asymétrique est donc de construire un

« coffre à deux serrures » virtuel.

Nous allons étudier plus précisément un tel système, qui est très
fréquemment utilisé et s'impose chaque année davantage dans le
monde des communications informatiques. Il s'agit du système
RSA, dont le principe est basé sur l'utilisation d'une propriété
simple des nombres premiers.
 9

CH2- Crypto Système à Clé Publique

Théorie de RSA et mise
en œuvre
Le chiffrement RSA (nommé par les initiales de ses trois
inventeurs) a été décrit en 1977 par Ronald Rivest, Adli Shamir et
Leonard Adleman.
C’est un algorithme de cryptographie asymétrique, très utilisé
dans le commerce électronique, et plus généralement pour
échanger des données confidentielles sur internet.

Ronald Rivest Adli Shamir Leonard Adleman

L'algorithme est remarquable par sa simplicité. Il est basé sur les nombres premiers.10

CH2- Crypto Système à Clé Publique

Théorie de RSA et mise
en œuvre
L'algorithme est remarquable par sa simplicité. Il est
basé sur les Nombres Premiers & Modulo.
Pour crypter un message:
c = m^e mod n
Pour décrypter:
m = c^d mod n
m = message en clair
c = message encrypté
(e,n) constitue la clé publique
(d,n) constitue la clé privée
n est le produit de 2 nombres premiers
^ est l'opération de mise à la puissance (a^b : a puissance b)
mod est l'opération de modulo (reste de la division entière)
 11

CH2- Crypto Système à Clé Publique

Théorie de RSA et mise
en œuvre
1. La notion de nombre premier
Un nombre premier est simplement un nombre qui ne possède que
deux facteurs, 1 et lui-même.

7 est premier car aucun nombre autre que 1 et 7 ne donne un

résultat entier en divisant 7.

Deux nombres sont premiers entre eux s'ils n'ont pas d'autre facteur
que 1.
38 et 55 sont premiers entre eux, alors qu'aucun n'est premier :
38 = 2 * 19 *1 et 55 = 5 * 11 * 1
22 et 55 ne sont pas premiers entre eux, car
22 = 2 * 11 et 55 = 5 * 11
 12

CH2- Crypto Système à Clé Publique

Théorie de RSA et mise
en œuvre
2. Division et reste : le modulo

une pendule est modulo 24 : 23h +2h = 1h du matin (arrivé à 24h, le

module, on recommence !)

La division de l'école :
Valeur / diviseur = quotient & reste
13 / 10 = 1 & 3
34 / 10 = 3 & 4
Arithmétique modulaire
13 mod 10 = 3
34 mod 10 = 4
A mod B est le reste de la division entière de A par B
 13

CH2- Crypto Système à Clé Publique

Théorie de RSA et mise
en œuvre
3. Théorème de Leonhard Euler :

Lorsqu'on utilise un module comme étant le produit de deux

nombres premiers on a :

Soit n = p * q, avec p et q premiers, et quelque soit m

m( p – 1 ) ( q – 1 ) mod n = 1

Exemple :

soit p = 11 et q = 5, n = 55 et (p – 1)(q – 1) = 10 * 4 = 40
(38e40) mod 55 = 1...pas besoin de calcul !
 14

CH2- Crypto Système à Clé Publique

Théorie de RSA et mise
en œuvre
Principe de RSA
utiliser deux modules, l'un pour les clés et l'autre pour chiffrer.
pour les clés : (p – 1) (q – 1)
pour chiffrer p * q

Etapes a suivre:

1. Création des deux clés (publique et privé)

2. Envoie de la clé publique
3. Chiffrement du message avec la clé publique
4. Déchiffrement du message avec la clé privé
 15

CH2- Crypto Système à Clé Publique

Théorie de RSA et mise
en œuvre
1. Création des clés
- L'étape de création des clés est à la charge du Récepteur;
- Il n'intervient pas à chaque chiffrement car les clés peuvent être réutilisées,
la difficulté première, est que L’émetteur soit bien certain que la clé publique
qu'il détient est celle du Récepteur;
Le renouvellement des clés n'intervient que si la clé privée est compromise, ou
par précaution au bout d'un certain temps (qui peut se compter en années).
- Choisir p et q, deux nombres premiers distincts ;
- Calculer leur produit n = p*q, appelé module de chiffrement ;
- Calculer φ(n) = (p - 1)(q -1) (c'est la valeur de l’indicateur d’Euler en n) ;
- Choisir un entier naturel e premier avec φ(n) et strictement inférieur à φ(n),
appelé exposant de chiffrement ;
- Calculer l'entier naturel d, inverse de e modulo φ(n), et strictement inférieur
à φ(n), appelé exposant de déchiffrement ; d peut se calculer efficacement par
l’algorithme d’Euclide Etendu.
 16

CH2- Crypto Système à Clé Publique

Théorie de RSA
Exemple
1. on choisit deux nombres premiers p = 3, q = 11 ;
2. module de chiffrement (n = p*q ), n = 3 × 11 = 33 ;
3. φ(n) = (p - 1)(q -1) φ(n) = (3 – 1) × (11 – 1) = 2 × 10 = 20 ;
4. Exposant de Chiffrement:
e premier avec φ(n) et strictement inférieur à φ(n),
on choisit e= 3 (premier avec 20);
1. l'exposant de déchiffrement est d = 7 avec l’algorithme d’euclide
étendu (ed=3*7=21= 1+20*1 ) de = 1 (modulo φ(n)))=1mod20
2. La clé publique d'Alice est (n, e) = (33, 3), et sa clé privée est (n, d) =
(33, 7). Bob transmet un message à Alice.
3. Chiffrement de M = 4 par Bob avec la clé publique d'Alice :
c = m^e mod n 43 mod 33≡ 64 mod 33=31,
le chiffré est C = 31 que Bob transmet à Alice ;
1. Déchiffrement de C = 31 par Alice avec sa clé privée :
m = c^d mod n 317 mod 33≡ 4,
Alice retrouve le message initial M = 4.
 17

CH2- Crypto Système à Clé Publique

Théorie de RSA et mise
en œuvre

RSA peut être utilisé pour assurer :

1. la confidentialité : seul le propriétaire de la clé privée

pourra lire le message chiffré avec la clé publique
correspondante.

2. la non-altération et la non-répudiation : seul le

propriétaire de la clé privée peut signer un message (avec la
clé privée). Une signature déchiffrée avec la clé publique
prouvera donc l'authenticité du message.
 18
CH2- La Sécurité

Crypto systèmes à clé publique

Théorie de RSA et mise en œuvre

Factorisation et attaque de RSA
 19

CH2- Crypto Système à Clé Publique

Factorisation
Il faut distinguer les attaques par la force brute, qui consistent à
retrouver p et q sur base de la connaissance de n uniquement, et les
attaques sur base de la connaissance de n mais aussi de la manière
dont p et q ont été générés, du logiciel de cryptographie utilisé, d'un
ou plusieurs messages éventuellement interceptés etc.

La sécurité de l'algorithme RSA contre les attaques par la force brute

repose sur deux conjectures :

1. « casser » RSA de cette manière nécessite la factorisation du

nombre n en le produit initial des nombres p et q,

2. avec les algorithmes classiques, le temps que prend cette

factorisation croît exponentiellement avec la longueur de la clé.
 20

CH2- Crypto Système à Clé Publique

Factorisation

En mathématique la factorisation consiste à écrire une expression

algébrique (notamment une somme), un nombre, une matrice sous la
forme d'un produit. Cette transformation peut se faire suivant
différentes techniques détaillées ci-dessous.

Par définition, un anneau constitué de 3 éléments: a, b et c

ab+ac=a(b+c)

Par exemple avec des nombres entiers:

4*7+4*8=4(7+8)
3a+21=3(a+7)
 21

CH2- Crypto Système à Clé Publique

Factorisation

En Arithmétique

Le théorème fondamental de l'arithmétique indique que tout

entier naturel supérieur ou égal à deux peut être factorisé en produit
de nombres premiers.

Cette décomposition en produit de facteurs premiers pour les entiers

est la « meilleure » factorisation possible, qui permet d'effectuer
de nombreux calculs
Exemple:
a²+b²=(a+b)(a-b)
1-x(n)=(1-x)(1+x+x²+…….+x(n-1)
 22

CH2- Crypto Système à Clé Publique

Factorisation RSA

Problème RSA

étant donné un entier RSA

n = p q (p < q < 2p) on demande de retrouver la clé secrète d

Ce problème est plus difficile que celui où l’on demande de

décrypter un message chiffré donné. Ici la résolution de ce
problème permet de décrypter n’importe quel message chiffré.
 23

CH2- Crypto Système à Clé Publique

Factorisation RSA

n = p q avec p et q deux premiers distincts.

Lemme
Si l’on connaît la factorisation de n alors on casse complètement RSA,
i.e. on sait retrouver la clé privée d et donc déchiffrer n’importe quel
message chiffré.
Preuve
A partir de n = p q on peut calculer ϕ(n) =(p−1)(q−1).
a l’aide de l’algorithme d’Euclide étendue (complexité polynomiale)
on calcule facilement une relation entre e et ϕ(n ).
On retrouve alors l’inverse d de e modulo ϕ(n)
 24

CH2- Crypto Système à Clé Publique

ATTAQUES RSA
Jusqu'à présent, ce qui fait le succès du RSA est qu'il n'existe pas
d'algorithme connu de la communauté scientifique pour réaliser
une attaque force brute avec des ordinateurs classiques

On peut néanmoins présumer que RSA reste sûr si la taille de la

clé est suffisamment grande. On peut trouver la factorisation
d'une clé de taille inférieure à 256 bits en quelques minutes sur
un ordinateur individuel, en utilisant des logiciels librement
disponibles.
Pour une taille allant jusqu'à 512 bits, et depuis 1999, il faut
faire travailler conjointement plusieurs centaines d'ordinateurs.
Par sûreté, il est couramment recommandé que la taille des clés
RSA soit au moins de 2 048 bits.
 25

CH2- Crypto Système à Clé Publique

ATTAQUES RSA
Plusieurs attaques ont été proposées pour casser le chiffrement RSA

1. Attaque de Håstad l'une des premières attaques découvertes

(en 1985)

2. Attaque de Wiener (1989)

3. Attaque par chronométrage (timing attacks): Paul Kocher

a décrit en 1995 une nouvelle attaque contre RSA

4. Attaque à chiffrés choisis (Adaptive chosen ciphertext

attacks)
 26
CH2- La Sécurité

• Sûreté d'un chiffrement

• Théorie de Shannon
• Secret parfait
• Crypto systèmes à clé secrète
• Crypto systèmes à clé publique
• Hachage et schémas de signature
• Certificats, gestion de clés
• Illustration avec PGP/gnupg
 27

CH2- Hachage et schémas de signature

Fonction De Hachage
Une fonction de hachage est une fonction permettant d'obtenir un
résumé d'un texte, c.-à-d. une suite de caractères assez courte
représentant le texte qu'il résume.

Une fonction de hachage est une fonction particulière qui, à

partir d'une donnée fournie en entrée, calcule une empreinte
servant à identifier rapidement, bien qu'incomplètement, la
donnée initiale. Les fonctions de hachage sont utilisées en
informatique et en cryptographie.
 28

CH2- Crypto Système à Clé Secrète

Caractéristiques et points forts de
l'AES
La fonction de hachage doit :
 être telle qu'elle associe un et un seul résumé à un texte en clair
(cela signifie que la moindre modification du document entraine la
modification de son résumé), c.-à-d.. « sans collision ».

 être une fonction à sens unique (one-way function) afin qu'il soit
impossible de retrouver le message original à partir du résumé.

y = F(x), mais il est impossible de retrouver x à partir de y !

 29

CH2- Hachage et schémas de signature

Fonction De Hachage

Propriétés:
une fonction de hachage "H" transforme une entrée de données
d'une dimension variable "m" et donne comme résultat une sortie
de données inférieure et fixe "h" (h = H(m)).
1. l'entrée peut être de dimension variable ;
2. la sortie doit être de dimension fixe ;
3. H(m) doit être relativement facile à calculer ;
4. H(m) doit être une fonction à sens unique ;
5. H(m) doit être « sans collision ».
 30

CH2- Hachage et schémas de signature

Fonction De Hachage

Utilisation - Authentification et intégrité

Les algorithmes de hachage sont utilisés :
 dans la génération des signatures numériques, dans ce cas, le
résultat "h" est appelé "empreinte" ;
 pour la vérification si un document a été modifié (le changement
d'une partie du document change son empreinte) ;
 pour la construction du MAC, Message Authentication Code, ou
code d'authentification de message, il permet de joindre l'empreinte
du message chiffré avec une clé secrète ce qui protège contre toute
modification du message (si l'intrus modifie le message et son
empreinte, il est incapable de chiffrée celle-ci pour la remplacer dans
le message).
 31

CH2- Hachage et schémas de signature

Fonction De Hachage et Signature

Cette fonction va prendre le texte du mot de passe et le

«mouliner» pour obtenir une signature (cette signature est aussi
appelée « empreinte »).

L’ordinateur ne va pas envoyer le mot de passe au serveur, mais une

signature du mot de passe. Le serveur ne va enregistrer le mot de passe
mais enregistrera cette signature.

Lorsque l’utilisateur se connectera, le serveur ne va pas vérifier si le

mot de passe est identique, mais il va vérifier que la signature du mot
de passe saisi est bien la même que la signature du mot de passe
enregistré
 32

CH2- Hachage et schémas de signature

Fonction De Hachage et Signature