Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 27-03-2018 23:18:14

Moon
Membre
Inscription : 12-03-2018
Messages : 4

Rechercher Exhaustive DES

Bonjour,
Je voudrais faire une sorte de recherche exhaustive sur le DES en résolvant le système de 8 équations suivant:

.P-1(L16⊕L*16)1-4=[ S1(E(R15)⊕K16)⊕(S1(E(R*15)⊕K16)];
...............................................................................................;
...............................................................................................;
...............................................................................................;
...............................................................................................;
.P-1(L16⊕L*16)29-32=[ S8(E(R15)⊕K16)⊕(S8(E(R*15)⊕K16)];

La seule inconnue ici est K16; l'utilisation de ce système est sensé réduire K16 à 216 clés possibles. Seulement je ne comprend pas comment je pourrais faire une recherche exhaustive en 216. Quelqu'un aurait une idée?

Merci d'avance.

Hors ligne

#2 30-03-2018 14:55:43

Rossignol
Membre
Inscription : 19-06-2015
Messages : 141

Re : Rechercher Exhaustive DES

Bonjour,

Je ne trouve pas les mêmes équations que vous. Peut-être n'ai-je rien compris !
Le DES est un chiffre de Feistel à 16 tours.

Le bloc de 64 bits à chiffrer, après la permutation initiale, est coupé en deux moitiés de 32 bits $L_0$ et $R_0$.
Le round $n$ est défini par :

$L_{n} = R_{n-1}$ 
$R_{n} = L_{n-1}\oplus f(R_{n-1}, K_{n})$

pour $n = 1... 16$
(J'utilise les notations du standard)

Au seizième et dernier tour, on a

$L_{16} = R_{15}$ 
$R_{16} = L_{15}\oplus f(R_{15}, K_{16})$

Par des procédés inavouables, on provoque une faute sur $R_{15}$ qui devient $R^*_{15}$ ($L_{15}$ ne change pas). 
On a donc

$L^*_{16} = R^*_{15}$ 
$R^*_{16} = L_{15}\oplus f(R^*_{15}, K_{16})$

En formant la différence, on élimine $L_{15}$.

$R_{16}\oplus R^*_{16}= L_{15}\oplus f(R_{15}, K_{16})\oplus L_{15}\oplus f(R^*_{15}, K_{16})
= f(R_{15}, K_{16})\oplus f(R^*_{15}, K_{16})$

Pour le DES la fonction $f$ est définie par

$f(X, K) = P(S(E(X)\oplus K))$

où $P$ est une permutation (32 bits --> 32 bits), $S$ une substitution (48 bits --> 32 bits) et $E$ une "permutation-extension" (32 bits --> 48 bits).

On a donc

$R_{16}\oplus R^*_{16}= P(S(E(R_{15})\oplus K_{16})) \oplus P(S(E(R^*_{15})\oplus K_{16}))$

$P$ est une permutation donc linéaire:

$R_{16}\oplus R^*_{16}= P(S(E(R_{15})\oplus K_{16}) \oplus S(E(R^*_{15})\oplus K_{16}))$

d'où

$P^{-1}(R_{16}\oplus R^*_{16}) = S(E(R_{15})\oplus K_{16}) \oplus S(E(R^*_{15})\oplus K_{16})$

La substitution $S$ est composée de 8 Sbox $S_1$, $S_2$, ... $S_8$ en parallèle chacune de 6 bits --> 4 bits.

On obtient les 8 équations :

$P^{-1}(R_{16}\oplus R_{16}^{*})_{1-4} = S_1((E(R_{15})\oplus K_{16})_{1-6})\oplus S_1((E(R^*_{15})\oplus K_{16})_{1-6})$

$P^{-1}(R_{16}\oplus R_{16}^{*})_{5-8} = S_2((E(R_{15})\oplus K_{16})_{7-12})\oplus S_2((E(R^*_{15})\oplus K_{16})_{7-12})$

...

$P^{-1}(R_{16}\oplus R_{16}^{*})_{29-32} = S_8((E(R_{15})\oplus K_{16})_{43-48})\oplus S_8((E(R^*_{15})\oplus K_{16})_{43-48})$

Prenons la première équation. Puisque $\oplus$ est une opération bit à bit, on a

$(E(R_{15})\oplus K_{16})_{1-6} = (E(R^*_{15}))_{1-6} \oplus (K_{16})_{1-6}$ 
$(E(R^*_{15})\oplus K_{16})_{1-6} = (E(R^*_{15}))_{1-6} \oplus (K_{16})_{1-6}$

$P^{-1}(R_{16}\oplus R_{16}^{*})_{1-4} = S_1((E(R_{15}))_{1-6} \oplus (K_{16})_{1-6}) \oplus S_1((E(R^*_{15}))_{1-6} \oplus (K_{16})_{1-6})$

Donc l'égalité n'est à vérifier que sur les six bits de 1 à 6 de $K_{16}$, les autres bits n'interviennent pas.

Une attaque par force brute ne coute pas cher ($2^6$ cas). Mais par contre, elle vous donnera en moyenne 4 solutions (indétermination due au fait que l'ensemble de départ a $2^6$ éléments et l'ensemble d'arrivée seulement $2^4$ éléments).

En faisant la même opération sur les sept autres équations, on obtient par concaténations (en moyenne) $4^8 = 2^{16}$ clés putatives pour $K_{16}$. À comparer aux $2^{48}$ possibilités, le gain est appréciable.

On suppose, naturellement, que $R^*_{15}\neq R_{15}$, sinon le système d'équations est totalement indéterminé : on a $2^6$ solutions par Sbox dont $(2^6)^8 = 2^{48}$ clés putatives et on ne gagne rien.

En recommençant l'expérience avec des valeurs différentes de $R^*_{15}$ et en faisant l'intersection des ensembles de solutions obtenues on doit obtenir moins de $2^{16}$ clés putatives pour $K_{16}$.
Dans quelle proportion ? Il faudrait expérimenter.

@+

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante ?40 - 28
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums