Chiffrement par permutation (Tranposition cipher)

soit $m \in \mathbb{Z}_{> 0},\; \EuScript{P}$= $\EuScript{C}$= $\frac{\mathbb{Z}}{26\mathbb{Z}}^{m}$

$\mid \EuScript{K} \mid\; = S_{m} = m!$

$\pi \in \EuScript{K},\; x=(x_{1},x_{2}, ..., x_{m}) \in \EuScript{P},\; y=(y_{1},y_{2}, ..., y_{m}) \in \EuScript{C}$

$E_{K}(x_{1},x_{2}, ..., x_{m}) = (x_{\pi(1)},x_{\pi(2)}, ..., x_{\pi(m)}) = (y_{1},y_{2}, ..., y_{m})$

$D_{K}(y) = (y_{\pi^{-1}(1)},y_{\pi^{-1}(2)}, ..., y_{\pi^{-1}(m)}) = x$

vérifions (1) : $D_{K}oE_{K}(x) = ((x_{\pi(1)})_{\pi^{-1}(1)}, ...) = (x_{\pi \pi^{-1}(1)}, ...) = x$

remarque : si on généralise les systèmes précédents aux alphabets sur $\mathbb{F}_2^a$ on a donc deux cas ``extrêmes'' :

• Des permutations aléatoires $\pi : \mathbb{F}_2^a \rightarrow \mathbb{F}_2^a$ qui nécessitent un traitement par petits blocs. On dit que de tels permutations apportent de la confusion (Shanon, 1948)
• Des transformations linéaires $R : \mathbb{F}_2^a \rightarrow \mathbb{F}_2^a$ données par leur matrice ($a^2$ bits) et inversibles en $O(a^3)$ opérations. Ces transformations étant performantes pour des $a$ grands, on dit qu'elles apportent de la diffusion (la transformation d'un seul bit du message clair implique des transformations pour des bits du chiffré très éloignés les uns des autres).

On a vu que ces systèmes utilisés seuls ne sont pas sûrs. Les systèmes cryptographiques modernes (DES, ...) mêlent ces deux types de transformations.