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 ssi 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.