# Introduction à la Cryptographie

5 sèances de cours magistraux
7 TP/TD
Contrôle continu
Contrôle écrit sèance 6 + projet

## Définitions

Définition **cryptographie** : communication confidentielle sur un canal susceptible d'être écouté. On parle de cryptosystème ou de schéma de chiffrement
Définition **cryptanalyse** : art de décrypter en analysant l'information sans en être le destinataire ou l'auteur

## Objectifs

Objectifs de la cryptographie :
**Confidentialité** - accès autorisé seulement au personne voulu
**Authentification** - vérifier l'identité des personnes ou des machines lors de la communication
**Intégrité** - les données ne sont pas altérer

## Les attaques

* Attaque passive - attaque consistant à écouter sans modifier en se cachant
* attaque active - attaque consistant à modifier les données en s'introduisant dans des équipements

## Terminologie et cryptographie sysmétrique ou à clé secrète

1. A et B - utilisateurs
2. Clé sysmétrique K possédé par A et B
3. Message M de A chiffré à l'aide de K et envoie le chiffré C à B
4. B déchiffre C à l'aide de K et de C

K peut être par exemple un K=3 avec un décalage de 3 lettres dans l'alphabet, on parle alors de décalage

Ces méthodes de chiffrement sont cassable par brute force via ordinateur ou par comparaison des fréquences d'apparition des lettres dans la langue française

## Historique

* En 1586 proposé par Blaise de Vigènere pour la cour de Henri III
-Substitution polyalphabétique qui as résisté jusqu'en 1900
* Chiffrement par One-Time Pad
-Chiffrer par addition d'une clef aussi longue que le texte et aléatoire
nécessite obligatoirement la clé de chiffrement / PREMIER CHIFFREMENT SYSMETRIQUE
* Enigma inventé par Scherbius à la fin de la 1ère guerre mondiale
-substitution polyalphabétique avec des clés de très grande taille généré par une machine électromécaniques utilisant des rotors
*MDR elle a essayé d'expliquer le fonctionnement d'enigma et personne a compris, regarde sur Internet*

## Dernier cours - 22/11/19

Fonction RSA et factorisation

Définition,= : soit e un nombre entier e <= N? On définit **f(x)= x^e (mod N)**

N = objet ayant 1024 bits

Complexité pour calculer x^e (mod N) :
Par force brute : essayer x=1, x=2, opérations au degré N -> fonction à sens unique

Possibilité de l'inversé par factorisation de N par théorème :

Soit N = p . q. Alors tout entier a premier avec N, a^kp(n)+1 = a (mod N)

Exemple :

N= 3 . 11, d
(p) (q)
vent (n) =(p-1) * (q-1)
donc vent(N) = 20

f(x) = x^e avec e= 7
x^7 = 29 (mod 33)
(p*q))

NIQUE SA MERE ELLE S EST GOURE
pute

3*7
21 mod 20 = 1

## TD - 4

### Exercice 1 :
(Échange de clé Diffie-Hellman) Le protocole d'échange de clé proposé en 1976 par Diffie et
Hellman permet d'échanger un secret (typiquement la clé secrète d'un algorithme symétrique, comme AES).
Génération des clés publiques
1. Soit p un nombre premier et g tel que (g, p) = 1.
2. p et g sont les clé publiques.
Déroulement du protocole
1. Alice choisit sa clé secrète, un nombre entier a.
2. Bob choisit sa clé secrète b.
3. Alice calcule A = g
a
(mod p) et l'envoie à Bob.
4. Bob calcule B = g
b
(mod p) et l'envoie à Alice.
5. Après réception de B, Alice calcule K = Ba
(mod p).
6. Après réception de A, Bob calcule K = Ab
(mod p).
Questions:
a) Supposons que p = 7, g = 3, a = 2 et b = 9. Calculez le secret échangé.
b) En travaillant en trinôme (Alice, Bob, Charlie) vous simulerez l'échange de clé Difie-Hellman. Dans
un premier temps, vous choissirez de commun accord les paramètres publiques p et g. On suppose
que Charlie intercepte toutes les messages échangés entre Alice et Bob. Au premier tour, il décide s'il
remplace les messages envoyés par Alice et Bob par ceux obtenus à partir de sa propre clé, ou bien il
redirige les messages sans les modifier. À la fin du protocole, chaque participant rend publique la clé
calculée. Vous en déduirez ainsi si Charlie a triché ou pas.

### Excerice 2 :
Exercice 2. (Attaques par canaux cachés) Soit n un entier. On considère d un exposant secret (RSA, Diffie-Hellman) de k bits, dont l'écriture binaire est d = dk−12 k−1 +dk−22
k−2 +...+d12+d0 (avec dk−1 = 1).
Nous rappelons que la fonction f, définie par f(x) = x
d mod n, est implémentée dans une carte à puce
de la manière suivante (dite "square-and-multiply") :
Require: x, d, n
Ensure: y = x^d mod n
y := x
for i = k − 2 down to 0 do
y := y
2 mod n
if di = 1 then y := y × x mod n
end for
Return y
Questions:
1. On se place maintenant dans l'hypothèse suivante : l'attaquant est capable de détecter (par exemple par observation des courbes de consommation électrique) que la carte éfféctue une multiplication ou
un carré. Montrer qu'il peut alors retrouver la valeur de l'exposant secret d, dans le cas de l'algorithme
square-and-multiply.

## TD5 -
### Exercice 1
(Chiffrer avant signer avec RSA) Alice et Bob veulent s'échanger des messages en utilisant le
module RSA N 11 17. Dans un premier temps, ils publient leurs clés publiques RSA respectives: la clé d'Alice eA = 3 la clé de Bob eB = 9
1. Alice calcule le chiffre du message m = 5 et l'envoie à Bob. Calculer ce chiffré (par l'algorithme square and multiply). Calculer la clé secrète de Bob et expliquer comment Bob déchiffre le message (pas besoin de détailler le calcul pour déchiffrer).
* Alice
ea . da = 1 (mod phi(N))
alice calcule c-m^eb et l'envoie à Bob.
c = 5^9 (mod 187)
y <- 5
y <- 5^2 (mod 187) = 25
y <- 25^2 (mod 187 = 625 mod 187) = 64
y <- 64^2x5 mod 187 = 87
* Bob
db la clée secréte de bob -> eb . db = 1 (mod phi(N))
Bob reçoit x = 97 et pour dechifrer calcule
c^db = (m^eb)^db = m
Phi(N) = 160
g db = 1 (mod 160)
2. Cette fois ci Alice veut chiffrer le message et le signer ensuite, pour prouver à Bob que le message vient d'elle. De ce fait, elle enverra à Bob le couple (co), où o 125 est sa signature RSA pour Montrer (en détaillant le calcul) comment Bob vérifie la signature.

N=11.17 Ca=3, Cb=9 m=5 σ(N)=160

( c, σ=125)

c= message clair
c=97 (mod 187)
Pour calculer σ d'Alice, on fait σ=c^da = 97^da

Pour vérifier la signature de bob, on calcule σ^e.a =?= 97

125^3 =?= 97 ( mod (87))

## Siganture numérique

Avoir un protocole/algorythme permettant de redonner les propiétés d'une signature réel. Elle doit être authentique, infalsifiable et vérifiable.
En informatique on utilise des certificats.

Dernier cours, le mot certificat est prononcé.Fonctionnement identique à RSA

SPANISH INQUISITION

because no one expect Spanish inquisition

Algoryhtme de signature :

clé publique du signataire (N,e), clé secrète d

Signature : (m,σ = m^d (mod N))

Vérifiaction : σ^e = m (mod N)