Définition d’un système cryptographique

[figure: Alice; chiffrement; générateur de clés; x; y; k; Oscar; canal sur; déchiffrement; Bob]

Le tuple (P, C, K, E, D) est un système cryptographique si :

P: Ensemble des textes clairs ;
K: Ensemble des clés ;
C: Ensemble des textes chiffrés ;
E: Ensemble des règles de chiffrement pour

les clés de K;

D: Ensemble des règles de déchiffrement

pour les clés de K;

Et : ∀k ∈ K, ∃e_{k} ∈ E, ∃d_{k} ∈ D, ∀x ∈ P,

d_{k}(e_{k}(x)) = x.

La cryptanalyse

principe de Kerckhoff : Oscar connait le système cryptographique utilisé.

but : Déterminer la clé utilisée.

Les attaques :

- Texte chiffré connu : Oscar ne connait que la chaine du message chiffré.

- Texte clair connu : Oscar dispose d’un texte clair et du texte chiffré correspondant.

- Texte clair choisi : Oscar a accès à une machine chiffrante.

- Texte chiffré choisi : Oscar a temporairement accès à une machine déchiffante.

Typologie des systèmes

Clé privée/clé publique :

- clé privée : la totalité de la clé est communiqué en secret (Chiffrement par substitution, de Hill, de Vigénère, le DES,...) ;

- clé publique : une partie de la clé est communiquée en secret tandis que l’autre est communiquée en publique (RSA, chiffrement de Rabin,...).

Chiffrement par bloc/en chaine :

- par bloc : la clé ne varie pas au cours du chiffrement ;

- en chaine : la clé varie au cours du chiffrement.

Monoalphabétique/polyalphabétique :

- monoalphabétique : pour un caractère clair, un caractère chiffré ;

- polyalphabétique : pour un caractère clair, plusieurs caractères chiffrés ;

Système idempotent ou non

Chiffrement en chaine

Le tuple (P, C, K, L, F, E, D) est un système cryptographique en chaine si :

P: Ensemble des textes clairs ;
K: Ensemble des clés ;
C: Ensemble des textes chiffrés ;
L: Alphabet de séquence de clés ;
F : (f_{1}, f_{2}, …) générateur de séquence :

∀i ≤ 1, f_{i} : K ∗ P^{i−1} → L;

E: Ensemble des règles de chiffrement pour

les clés de L;

D: Ensemble des règles de déchiffrement

pour les clés de L;

Et : ∀z ∈ L, ∃e_{z} ∈ E, ∃d_{z} ∈ D, ∀x ∈ P,

d_{z}(e_{z}(x)) = x. Si la séquence ne dépend que de la clé : système synchrone. Si ∀i ≥ 1, z_{i} = z_{i+d} : système périodique. rem.: Si ∀i ≥ 1, z_{i} = K: chiffrement par bloc.

Système cryptographique produit

Principe : combiner les systèmes cryptographiques. but : augmenté la sécurité des systèmes. Soient S_{1} = (P, P, K_{1}, E_{1}, D_{1}) et S_{2} = (P, P, K_{2}, E_{2}, D_{2}) deux systèmes cryptographiques. Le système S = (P, P, K_{1}∗ K_{2}, E, D) défini par

∀k = (k_{1}, k_{2}) ∈ K_{1} ∗ K_{2}, ∀x, y ∈ P

e_{(k_{1},k_{2})}(x) = e_{k_{2}}(e_{k_{1}}(x)),
d_{(k_{1},k_{2})}(y) = d_{k_{1}}(d_{k_{2}}(y))

est le système produit (noté S_{1} ∗ S_{2}). S^{n} est le système cryptographique itéré. Un système S est idempotent si S^{2} = S.

Notions d’arithmétique modulaire

a mod m est le reste de la division entière de a par m (0 ≤ a mod m ≤ m − 1). a ≡ b(mod m) si m divise (b − a). lem.: a ≡ b(mod m) ssi a mod m = b mod m. Exemple : 143 mod 5? −18 mod 7? pgcd est le plus grand commun diviseur.

\begin{matrix}ℤ_{m} = \{0, …, m − 1\} \\ x op_{m} y : x op y mod m avec op ∈ \{+, −, ∗\} \end{matrix}

La fonction indicatrice d’Euler ϕ(m) est définie par le nombre d’entiers de ℤ_{m} qui sont premiers avec m.

Soit a ∈ ℤ_{m}, a^{−1} ∈ ℤ_{m} est l’inverse de a si a∗_{m}a^{−1} ≡ a^{−1} ∗_{m} a ≡ 1(mod m).

Th.: Un nombre a admet un inverse dans ℤ_{m} si et seulement si pgcd(a, m) = 1 (i.e. a et m sont premiers entre-eux).

Algo. d’Euclide : Le plus grand commun diviseur de deux nombres b et a (b > a) est donné par la définition récursive suivante :

pgcd(a, b) = \{ \begin{matrix}a si b mod a = 0 \\ pgcd(b mod a, a) sinon \end{matrix}

Algo. d’Euclide étendu : L’inverse de x dans ℤ_{m} si il existe est x_{m}^{−1} = inverse(x, m, 0, 1, m) avec :

inverse(u, v, t, t′, m) t′ si v mod u = 0 et u = 1 ⊥ si v mod u = 0 et u ≠ 1 inverse(v mod u, u, t′, (t − (v div u) ∗ t′) mod m, m)

Notions de probabilité

Notation : X un espace d’événements, X une distribution de probabilités sur X et P r_{X} (x) la probabilité d’un événement x suivant X.

Soient X et Y deux ensembles d’événements différents. La probabilité mutuelle P r_{(X ,Y)}(x, y) : probabilité que x et y soient réalisés simultanément. La probabilité conditionnelle P r_{X} (x|y) : probabilité de x sachant que y est réalisé.

P r(x, y)_{(X ,Y)} = P r_{X} (x|y)P r_{Y}(y)

Th.: (Théorème de Bayes) Si P r_{Y}(y) > 0 alors

P r_{X} (x|y) = \frac{P r_{X} (x)P r_{Y}(y|x)}{P r_{Y}(y)}

cor.: Deux distributions X et Y sont indépendantes si et seulement si

P r_{X} (x|y) = P r_{X} (x), ∀x ∈ X , ∀y ∈ Y

Probabilité et cryptographie

C(k) = {e_{k}(x), x ∈ P}

Probabilité d’avoir un texte chiffré y:

P r_{C}(y) = Σ_{k/y∈C(k)}P r_{K}(k)P r_{P}(d_{k}(y))

Probabilité d’avoir un texte chiffré y sachant que le texte clair est x:

P r_{C}(y|x) = Σ_{k/x∈d_{k}(y)}P r_{K}(k)

Probabilité d’avoir un texte clair x sachant que le texte chiffré est y:

P r_{P}(x|y) = \frac{P r_{P}(x)P r_{C}(y|x)}{P r_{C}(y)}

Un système cryptographique assure une confidentialité parfaite si

∀x ∈ P, ∀y ∈ C, P r_{P}(x|y) = P r_{P}(x)

Probabilité et cryptographie (suite)

Th.: Soit le système cryptographique S = {P, C, K, E, D}, |P|=|C|=|K|. S assure une confidentialité parfaite si et seulement si ∀k ∈ K, P r_{K}(k) = \frac{1}{|K|} et ∀x ∈ P, ∀y ∈ C, ∃!k ∈ K/e_{k}(x) = y.

Exemple : Soient P = \{a, b\} avec P r_{P}(a) = \frac{1}{4} et P r_{P}(b) = \frac{3}{4} ; K = \{k_{1}, k_{2}, k_{3}\} et P r_{K}(k_{1}) = \frac{1}{2}, P r_{K}(k_{2}) = \frac{1}{4}, P r_{K}(k_{3}) = \frac{1}{4} ; C = \{1, 2, 3, 4\}.

\begin{matrix}e_{k}(x) & k_{1} & k_{2} & k_{3} \\ a & 1 & 2 & 3 \\ b & 2 & 3 & 4 \end{matrix}

Calculer ∀x ∈ P, ∀y ∈ C, P r(x|y)?

Chiffrement par substitution

Algo. de chiffrement par substitution :

P = C = ℤ, K = {π/π permutation sur ℤ}, ∀π ∈ K, x, y ∈ ℤ, (π^{−1} ∘ π = π ∘ π^{−1} = id), e_{π}(x) = π(x), d_{π}(y) = π^{−1}(y).

Propriétés : par bloc, monoalphabétique, à clé privée, idempotent et |K|= 26! > 4 ∗ 10^{26} . Attaque : fréquence des lettres. Exemple : Déchiffrement de

\begin{aligned}y = & RUZV F SMLXCMZV QF DHUJLF \\ & UCAHV Y F UCV HV BF ZSMXZSHV \end{aligned}

par la substitution :

\begin{matrix}a & b & c & d & e & f & g & h & i & j & k & l & m \\ X & N & Y & A & H & P & O & G & Z & Q & W & B & T \\ n & o & p & q & r & s & t & u & v & w & x & y & z \\ S & F & L & R & C & V & M & U & E & K & J & D & I \end{matrix}

Chiffrement par substitution (suite)

lem.: Le système de chiffrement par substitution offre une confidentialité parfaite. Algo. de chiffrement affine : P = C = K = {(a, b) ∈ ℤ ∗ ℤ/pgcd(a, 26) = 1}, ∀k = (a, b) ∈ K, x, y ∈ ℤ, e_{k}(x) = ax + b mod 26, d_{k}(y) = a^{−1}(y − b) mod 26. Attaque : recherche exhaustive de la clé (|K|= 26 ∗ ϕ(26) = 312). Chiffrement par décalage : a = 1. Exemple : Déchiffrement par décalage (b = 11) :

\begin{aligned}y = & ZSNZXMT P Y OP XLCT Y DN \\ & ZXMT P Y OP NLAT ELT Y P D \end{aligned}

Chiffrement de Hill

Algo. de chiffrement de Hill :

P = C = (ℤ)^{m},

K = {matrices m ∗ m inversibles dans ℤ}, ∀K ∈ K, x, y ∈ (ℤ)^{m}, e_{K}(x) = xK, d_{K}(y) = yK^{−1}

Remarque : une matrice de ℤ_{m} est inversible si pgcd(det K, m) = 1. Propriétés : par bloc, polyalphabétique, idempotent et à clé privée. Exemple : Chiffrer puis déchiffrer x = et avec

K = ( \begin{matrix}11 & 8 \\ 3 & 7 \end{matrix} ), K^{−1} = ( \begin{matrix}7 & 18 \\ 23 & 11 \end{matrix} )

Chiffrement de Hill (suite)

Chiffrement par permutation : K = {π/π permutation sur ℤ_{m}}, ∀π ∈ K, x = x_{1} … x_{m}, y = y_{1} … y_{m} ∈ ℤ^{m}, (π^{−1} ∘ π = π ∘ π^{−1} = id), e_{π}(x) = x_{π(1)} … x_{π(m)}, d_{π}(y) = y_{π^{−}1(1)} … y_{π^{−1}(m)}.

K_{π} = (k_{ij})/k_{ij} = \{ \begin{matrix}1 & si i = π(j) \\ 0 & sinon \end{matrix}

Chiffrement de Vigénère (XV I^{ème}) et de

Vernam (1917)

Algo. de chiffrement de Vigénère :

P = C = K = (ℤ)^{m}, ∀K, x, y ∈ (ℤ)^{m}, K = k_{1} … k_{m}, x = x_{1} … x_{m}, y = y_{1} … y_{m}, e_{K}(x) = (x_{1} +_{26} k_{1}) … (x_{m} +_{26} k_{m}) ( mod m), d_{K}(y) = (y_{1} −_{26} k_{1}) … (y_{m} −_{26} k_{m}) ( mod m).

Propriétés : en chaine périodique de période m, polyalphabétique, à clé privée, idempotent et |K|= 26^{m}.

Algo. de chiffrement de Vernam :

\begin{matrix}P = C = K = (ℤ_{2})^{m}, \\ ∀x, y, k ∈ (ℤ_{2})^{m}, e_{k}(x) = x ⊕ k, d_{k}(y) = y ⊕ k, \end{matrix}

lem.: Les systèmes de chiffrement de Vigénère et de Vernam offrent une confidentialité parfaite.

Standard de Chiffrement de Données : DES

DES : Data Encryption Standard

- 1973 : appel d’offre du National Bureau of Standards ;

- 1975 : publication du DES (modification de LUCIFER d’IBM) ;

- 1977 : adoption comme standard.

- révisé tous les 5 ans.

- fin probable : 1998

Algorithme du DES L’algorithme du DES prend en entrée un texte clair de 64 bits, une clé de 64 bits (dont les bits terminaux de chaques octets sont des bits de parité pour le contrôle des erreurs) et calcule un texte crypté sur 64 bits.

Algorithme général du DES

DES(x : texte 64bits, K : clé 64bits) : 64bits L_{0}R_{0} = IP (x), (|L_{0}|=|R_{0}|= 32) Pour i = 1 à 16 L_{i} = R_{i−1} R_{i} = L_{i−1} ⊕ f(R_{i−1}, T_{i}(K)) finPour résultat IP^{−1}(R_{16} L_{16} )

f(r : 32bits, k : 48bits) : 32bits B = Exp(r) ⊕ k = B_{1} … B_{8}, (|B_{i}|= 6) Pour i = 1 à 8 B_{i} = b_{1} … b_{6} C_{i} = S_{i}(b_{1}b_{6}, b_{2}b_{3}b_{4}b_{5}) finPour résultat P (C_{1} … C_{8})

Diversification de la clé

Principe : la clé subit une permutation, une série de rotations circulaires “par partie” puis une permutation inverse.

Algo. de diversification de la clé Les fonctions LS_{j}, 1 ≤ j ≤ 16 sont des rotations circulaires vers la gauche d’un bit pour les indices 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14 et 15, et de deux bits pour les indices 1, 2, 9 et 16.

T_{i}(k : 64bits) : 48bits k′ = ote bits de parite(k) C_{0}D_{0} = P C−1(k′), (|C_{0}|=|D_{0}|= 28) Pour j = 1 à i C_{j} = LS_{j}(C_{j−1}) D_{j} = LS_{j}(D_{j−1}) finPour résultat P C−2(C_{i}, D_{i})

rem.: Les fonctions de permutation T_{i}(K), 1 ≤ i ≤ 16 sont calculables à l’avance.

Modes d’utilisation du DES

ECB (electronic codebook mode) : mode courant ;

IV : une valeur initiale arbitraire.

CBC (cipher block chaining mode) :

CBC(x_{1}, x_{2}, …: 64bits) bloc initial y_{0} = IV Tantqu’il y a des blocs de texte clair x_{i} y_{i} = DES(y_{i−1} ⊕ x_{i}) finTantque

CBC^{−1}(y_{1}, y_{2}, …: 64bits) bloc initial y_{0} = IV Tantqu’il y a des blocs de texte chiffré y_{i} x_{i} = y_{i−1} ⊕ DES^{−1}(y_{i}) finTantque

Modes d’utilisation du DES (suite)

OFB (output feedback mode) : Chiffrement en chaîne synchrone

OF B = (x_{1}, x_{2}, …: 64bits) bloc initial z_{0} = IV Tantqu’il y a des blocs de texte clair x_{i} z_{i} = DES(z_{i−1}) y_{i} = z_{i} ⊕ x_{i} finTantque

OF B^{−1}(y_{1}, y_{2}, …: 64bits) bloc initial z_{0} = IV Tantqu’il y a des blocs de texte chiffré y_{i} z_{i} = DES(z_{i−1}) x_{i} = z_{i} ⊕ y_{i} finTantque

Modes d’utilisation du DES (suite)

CFB (cipher feedback mode) :

CF B = (x_{1}, x_{2}, …: 64bits) initial bloc y_{0} = IV Tantqu’il y a des blocs de texte clair x_{i} z_{i} = DES(y_{i−1}) y_{i} = z_{i} ⊕ x_{i} finTantque

CF B^{−1}(y_{1}, y_{2}, …: 64bits) bloc initial y_{0} = IV Tantqu’il y a des blocs de texte chiffré y_{i} z_{i} = DES(y_{i−1}) x_{i} = z_{i} ⊕ y_{i} finTantque

Systèmes à clés publiques

Pr.: Rendre impossible la construction de la clé de déchiffrement à partir de la clé de chiffrement.

- clé publique de chiffrement,

- clé privé de déchiffrement.

Rivest, Shamir et Adleman :(1977) factorisation des grands nombres ; Rabin : factorisation des grands nombres ; Merkle-Hellman : problème du sac-à-dos ; McEliece : théorie algébrique des codes ; ElGamal : logarithme discret dans un corps fini ; Chor-Rivest : problème du sac-à-dos.

Le système RSA

Construction du système par Bob :

- Choix de 2 grands nombres premiers p et q;

- calcul de n = pq et de ϕ(n) = (p − 1)(q − 1) ;

- choix d’un b tel que pgcd(b, ϕ(n)) = 1 ;

- calcule de a = b^{−1} mod ϕ(n) ;

- publication de b et n.

Chiffrement de x par Alice : e_{K}(x) = x^{b} mod n

Déchiffrement de y = e_{K}(x) par Bob : d_{K}(y) = y^{a} mod n

Clé : (n, p, q, a, b)

- clés publiques : n et b,

- clés privées : p, q et a.

Le système RSA

Algo. square − and − multiply pour le calcul de y dans y = x^{c} mod n = sm(x, c, n, |c|, 1) avec |c|= l le nombre de bits de la représentation binare de c et bin(c, i) le i^{ème} bit de c.

sm(x, c, n, l, z)

z si l = 0

sm(x, c, n, l − 1, (z2 ∗ x mod n)) si bin(c, l) = 1 sm(x, c, n, l − 1, z2) sinon

sachant que z2 = z^{2} mod n.

Exemple : p = 101, q = 113, x = 9726.