Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Techniques de cryptographie
Azzouzi Hamza –25614
2021/2022
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Introduction
Figure –
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Table de matière
1 Introduction et Notations
2 Premières techniques de cryptographie
3 Crypatge asymétrique et RSA
4 Problème du Logarithme Discret
5 Test de Primalités
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Quelques notations
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Méthode César
Elle consiste à créer un chiffrage de 3 lettres
Figure – L’alphabet dans le chiffrage de César
Exemple
SALUT → VDOYX
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Au delà de la méthode César
On peut faire correspondre chaque lettre à une autre (26!
possibilités)
Technique facile à déchiffrer( fréquence des lettres )
Figure – fréquence des lettres en français
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
La méthode XOR
Le principe du XOR (ou exclusif) est le suivant : Pour x,y ∈ {0, 1}2
0 si x=y
x ⊕y = : ll
1 sinon
On peut alors crypter un message en utilisant comme clé un
nombre de bits.
Ck (m) = k ⊕ m
Dk (c) = k ⊕ c
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Exemple de la méthode XOR
En prenant k = 1011 et m = 1010
Message chiffré :
Ck (m) = 1011 ⊕ 1010 = [0 ⊕ 1] [0 ⊕ 1] [1 ⊕ 1] [1 ⊕ 0] = 0001
Message déchiffré :
Dk (c) = 0001 ⊕ 1011 = 1010
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Principe du cryptage asymétrique
Figure – clé publique et privée
Figure – chiffrage et déchiffrage
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Fonction indicatrice d’Euler
∀p ∈ N∗ , p est premier ssi ϕ (p) = p − 1
si p et q sont deux entiers premiers entre eux alors :
ϕ(pq) = ϕ(p)ϕ(q)
on peut montrer que pour n ∈ N fixé :
∀x ∈ (Z/nZ)∗ , x ϕ(n) ≡ 1 [n]
Figure – La fonction indicatrice d’Euler
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Principe de La RSA
La fonction indicatrice d’Euler est la base de la cryptographie par la
méthode de RSA dont le principe est le suivant :
On choisit un grand nombre n = pq(où p et q sont deux
grands nombres premiers), et un nombre r
L’application de chiffrement est :
c = C (m) = mr mod n
L’application de déchiffrement est :
D(m) = c s mod n
De sorte que : rs ≡ 1 [ϕ(n)]
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Principe de la RSA
Le calcul des fonctions E et D se fait rapidement si on connaît
r et s grâce à l’algorithme des calcul rapides des puissances.
Le nombre s n’est connu que par le propriétaire.
La RSA permet de signer le message puisque le nombre s
caractérise la personne qui a chiffrée le message.
Figure – Principe de La RSA
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Exemple d’utilisation de RSA
On utilise p = 157 q = 167 r = 5
On trouve alors que n = 26219 , ϕ(n) = 25896 et s = 20717
Je chiffrerai "SALUT"
On commence par transformer notre message en code ASCII
Figure – code ASCII
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Exemple d’utilisation de RSA
Lettre S A L U T
mr mod n 835 modn 655 modn 765 modn 855 modn 845 modn
Message chiffré 2959 21218 16981 11755 5391
Ainsi le message envoyé serait "02959 21218 16981 05391".
Pour déchiffrer :
Message chiffré 2959 21218 16981 11755 5391
c r mod n 295920717 212820717 1698120717 1175520717 539120717
Message déchiffré 83 65 76 85 84
On retrouve alors le message envoyé.
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Sécurité du RSA
L’algorithme
√ le plus rapide pour factoriser un nombre se fait en
ln(n) ln(ln(n))
O(e )
On suppose que l’ordinateur prend environ une microseconde à
chaque opération
Longueur Nb d’opérations Durée
75 9.0.1012 74 années
.
200 1.2 .1023 3.8 .109 années
500 1.3 .1039 4.2 .1025 années
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Problème du Logarithme Discret
Proposition
Soit p un nombre [Link] a les propositions suivantes :
F∗p est cyclique
il existe g ∈ F∗p tq ord(g ) = p − 1. g est alors appelé racine
primitive de l’unité.
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Définition
Soit p un nombre premier et soit g une racine primitive de l’unité.
Pour tout y ∈ F∗p il existe x tq g x = y mod p.
On dit alors que x est le logarithme discret de y modulo p et
on note x = logg (y )
Exemple :
On prend ici n = 11 et g = 2
n 1 2 3 4 5 6 7 8 9 10
log2 (n) 0 1 8 2 4 9 7 3 6 5
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Cryptosystème d’ElGamal
Choix de la clé privée et publique
Bob choisit un grand nombre premier p, tel que le problème du
logarithme discret est difficile à résoudre dans F∗p . Il choisit g
une racine primitive dans F∗p
Bob choisit un nombre d tel que 0 < d < p − 1 et calcule
b = g d mod p
Bob alors publie le triplet (p,g,b) qui représentera la clé
publique. La clé privée étant le nombre d choisi.
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Cryptosystème d’ElGamal
Cryptage du message
Supposons qu’Alice veuille envoyer un message M à Bob.
Elle commence par choisir un nombre k tq 0 < k < p − 1
Elle calcule alors r = g k et t = b k M mod p
Alice envoie le couple (r,t) à Bob
Décryptage du message
Pour décrypter le message Bob doit calculer
tr −d = (b k M)(g −kd ) = (g kd M)(g −kd ) = M (mod p)
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Sécurité des cryptosystèmes
L’algorithme pour résoudre √le problème
√ du logarithme discret
1/2+o(1) ln(n) ln(ln(n))
le plus rapide se fait O(e ).
On suppose que l’ordinateur effectue chaque opération en une
microseconde
Longueur du nombre Nb d’opérations Durée
100 3.9x106 3 secondes
200 9.9x109 2.5 heures
500 1.3x1017 3170 années
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Test de Primalités
Test de Fermat
Un nombre n n’est pas premier ssi ∃a ∈ (Z/nZ)∗ , an−1 6≡ 1[n]
Démonstration.
Le sens directe est la contraposée du théorème de Fermat.
L’autre sens découle du fait que si an−1 ≡ 1[n] alors a est premier
avec n
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Test de primalités
Test de Miller Rabin
Notons n − 1 = 2s t où t est un nombre impair
si n n’est pas premier alors il existe a ∈ (Z/nZ)∗ tq at 6≡ 1[n]
i
ou a2 t 6≡ −1[n] avec 0<i<s
un tel entier est appelé un témoin de Miller
Lemme
Si n est un entier composé au moins 3 quarts des nombres entre 2
et n-2 sont des témoins de Miller.
En utilisant ce lemme on peut alors écrire le test probabiliste de
Miller.
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Test de primalité
Test probabiliste de Miller-Rabin
1 On choisit un nombre t qui représentera le nombre de test à
effectuer
2 on choisit aléatoirement un nombre entre 2 et n − 2
3 si a n’est pas un témoin de Miller on réitère l’opération
4 Si après t test le test n’est pas terminé on retourne "n est
premier avec une probabilité supérieure à 1 − 41t "
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Comparaison entre les deux tests
Figure – Comparaison entre les deux méthodes
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Test de Lucas-Lehmer
Théorème
Un nombre p ∈ N est premier ssi il existe a ∈ F∗p d’ordre p-1
Définition
Un nombre de Mersenne est un terme de la suite Mn = 2n − 1
Théorème
s0 = 4
Soit la suite (sn )n∈N définie par récurrence :
sn+1 = (sn )2 − 2
Soit p un nombre premier impaire. Mp est premier ssi Mp |sp−2
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Test de Lucas-Lehmer
Description du test
1 choisir un entier naturel p qui est premier et impair
2 Calculer le nombre de Mersenne Mp
3 Calculer sp−2
4 Evaluer le reste de la division euclidienne de sp−2 par Mp . S’il
vaut 0 alors Mp est un nombre premier
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Merci pour votre attention
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Algorithmes
Figure –
Azzouzi Hamza –25614 Techniques de cryptographie
Introduction et Notations
Premières techniques de cryptographie
Crypatge asymétrique et RSA
Problème du Logarithme Discret
Test de Primalités
Algorithmes
Azzouzi Hamza –25614
Figure Techniques
– de cryptographie