Discussion :

[moone]

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

.P-1(L₁₆⊕L*₁₆)_1-4=[ S1(E(R₁₅)⊕K₁₆)⊕(S1(E(R*₁₅)⊕K₁₆)];
...............................................................................................;
...............................................................................................;
...............................................................................................;
...............................................................................................;
.P-1(L₁₆⊕L*₁₆)_29-32=[ S8(E(R₁₅)⊕K₁₆)⊕(S8(E(R*₁₅)⊕K₁₆)];

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

Merci d'avance.

[Flodelarab]

Bonjour

1) Tu n'as défini aucun des objets mathématiques que tu utilises.

2) "Recherche exhaustive" veut dire "force brutale" ? Ben vas-y. Fais tous les cas possibles.

3) Qu'as-tu fais jusqu'à maintenant ? ("rien" n'est pas une bonne réponse)

[moone]

Bonjour,
Je n'ai pas trouver de manière pour faciliter la résolution du système alors j'ai décidé de le faire en testant tous les cas.
Je le fais en C, et j'utilise plusieurs méthodes pour calculer différents éléments.
.D'abord je crée K16 en le remplissant aléatoirement de 0 et de 1.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
char *RemplirK( char *L){
    for(int i=0;i<48;i++)
        {
           int  r =  rand()%2;
          L[i]=r;
        }
        return L;
}

.Ensuite je calcule :[ S1(E(R15)⊕K16)⊕(S1(E(R*15)⊕K16)] par la méthode suivante

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
char *CalculS1( char *K, char *R15, char *R15fo){
      char *E;
      char *E1;
      char *xoK;
      char *xoK1;
      char *S;
      char *s;
      char *s1;
      char *S1;
      char *Xof;
      E=permute(R15,expansion_table,48);//correspond à E(R15)
      E1=permute(R15fo, expansion_table,48);//correspond à E(R*15)
      xoK=Xor1(E,K);//correspond à E(R15)+K16
      xoK1=Xor1(E1,K);//correspond à E(R*15)+K16
      S=Blocks5Bits(xoK,S_1,48,32);//correspond à S1(E(R15)+K16)
      S1=Blocks5Bits(xoK1,S_1,48,32);//correspond à S1(E(R*15)+K16)
      s=Reduction4(S);//j'extrai les 4 premier bits
      s1=Reduction4(S1);//j'extrai les 4 premier bits
      Xof= Xor1(s,s1);//correspond à S1(E(R15)+K16)+(S1(E(R*15)+K16)
      return Xof;
 
 }

Une fois que j'aurais tout calculé, je teste si les blocs trouvés sont égaux aux différents blocs P-1(L16⊕L*16).
Je ne sais pas si c'est la bonne manière de la faire parce que je n'ai pas l'impression qu'utiliser le système rende la recherche de K16(48 bits) plus rapide qu'avec un brute force qui chiffrerai avec une clé de 48 bits pour ensuite comparer.

[dinobogan]

Ta demande n'est pas du tout claire.
D'après ce que j'ai compris dans ton code, tu cherches à faire une recherche par force brute sur une combinaison de 2^48 en les testant 2^16 fois.
L'exercice est intéressant mais tu ne trouveras jamais le résultat : pas assez de puissance de calculs. Je ne parle pas de ton ordinateur, entendons-nous bien. Je parle de tous les processeurs de la planète qui ne seraient pas suffisant pour trouver la solution en un temps humain raisonnable !

Maintenant, sur l'implémentation, tu ne devrais pas coder les bits sur des char. Utilise plutôt des entiers (sur 64 bits) pour travailler avec des bits. Ton code sera bien plus rapide. Selon le processeur et le compilateur que tu utilises, il y a aussi les fonctions "intrinsic" pour manipuler ces entiers et effectuer des opérations ultra-rapides car cablées directement sur le processeur. Toujours selon ton processeur, il est très probable que tes calculs soit utilisable via des instructions vectorielles (SSE, VMX, ...). Mais ici encore, pas de magie : si tu te débrouilles bien, ton code sera beaucoup plus rapide mais le nombre de combinaisons à effectuer sera toujours trop grand pour trouver une solution.

[moone]

Bonjour,

Je m'étais trompé en fait, il me fallait prendre chaque égalité séparément et chercher K₁₆ en le divisant en bloc de 6 bits, et là j'obtiens K₁₆ avec une complexité de 2¹⁶.

Merci