Discussion :

[Celelibi]

Bonjour,

Je suis en train de coder un programme pour brutforcer un algorithme de cryptage maison.

Mon problème est pour la génération de la liste des mots. J'ai pensé à réutiliser un algo que j'avais trouvé il y a quelques temps, il se base sur la transformation d'un entier vers la base l où l est le nombre de caractères qui peuvent apparaitre dans le mot.

Voici mon algo actuel qui transforme un entier en mot :

Code :

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

1
2
3
4
5
6
7
8
9
10
idmot <- 123456 // l'id du mot
tablist <- "abcdef....."
 
// Début de la génération du mot
myid <- idmot
mot <- ""
tant que myid != 0
  mot <- mot + tablist[myid % tablist.length] // On rajoute un caractère
  myid <- myid/tablist.length // Division entière
fin tant que

tablist contient la liste des caractères, idmot contient l'id du mot à générer.
Et bien entendu tablist[ i ] représente le i-ème caractère de tablist en commençant à 0, tablist.length représente le nombre de caractères de tablist, et le % représente l'opérateur modulo.

Ça à l'aire bien au premier coup d'oeil, mais le problème c'est que le dernier caractère de mot ne sera jamais un "a" (le premier caractère de tablist).
Exactement de la même façon que quand on écrit un nombre, on n'a jamais de "0" au début.
Mais dans mon cas j'aurais besoin que "aaaa" soit généré aussi.


Avez-vous une idée pour que les mots qui finissent par un ou plusieurs "a" soient aussi générés ?

Merci d'avance.

[PRomu@ld]

Je suis en train de coder un programme pour brutforcer un algorithme de cryptage maison.

Décris plus en détail ce que tu cherches à faire.

Mon problème est pour la génération de la liste des mots.

Tu pourquoi veux tu générer une liste de mot ? Est-ce du cryptage ou du décriptage ?

Si je pars du principe que tu veux faire du décriptage, je te conseille de faire du décryptage sur un nombre n de caractère, c'est plus simple et potentiellement bouclable.


En gros, comme ça en vrac je pense à une fonction qui re renvoie le prochain mot généré à partir du précédent, ça fonctionne sur le principe du compteur.

Voilà ce que ça peux donner. (pseudo Ada)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
-- fonction qui renvoie le prochain mot.
function GetNext(s_in : string) return string is
     s : string(1..s_in'length) := s_in;
begin
     for i in reverse 1..s'length loop
          s(i) := GetNextCarac( s(i) );
          if( s(i) != tab_carac'first ) then
               break;
          end if;
     end for;
     return s;
end;

Il te reste GetNextCarac(), elle te renvoie le prochain caractère juste après le caractère que tu donnes (dans la liste des caractères que tu veux utiliser pour décrypter.

Ce n'est qu'une solution parmi d'autres, tu peux aussi utiliser des définitions récursives.

[Celelibi]

En fait j'ai une chaine cryptée par cet algo, et je cherche à retrouver le mot qui est à l'origine de cette chaine. Et étant donné que cet algo n'est pas renversable (il est à base de sha1) ni simplifiable, le seul moyen de retrouver le texte d'origine est la recherche exhaustive sur le texte d'entré.

Le problème avec la méthode qui à partir d'un mot, donne le suivant est que ça me semble un peu long avec pas mal de tests. C'est pourquoi j'avais opté pour la solution qui à partir d'un entier, donne le mot associé.

Donc en fait j'ai fait comme ça (code en Ada aussi ) :

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
function idtomot (id: integer; len : integer) return string is
  myid : integer := id;
  ret : string(1..len);
begin
  for i in reverse 1..len loop
    ret(i) := tablist(myid%tablist'length);
    myid := myid/tablist'length;
  end loop;
end idtomot;
 
max := 1;
for len in 1..10 loop
  max := max * tablist'length;
  for id in 1..max loop
    mon_mot := idtomot(id, len); 
  end loop;
end loop;

Pour passer d'un mot au suivant ça me fait :
- 2*len affectations
- len modulo
- len divisions
(- et une incrémentation qui est réalisé à l'exterieur de la fonction)

avec ton code ça fait :
- len affectations
- 2*len tests (un dans ta boucle et un par appel à GetNextCarac pour savoir si il faut revenir au premier caractère)

j'aurais tendance à dire que ton algorithme est plus rapide, mais pour récupérer le prochain caractère il faudra parcourir toute la liste de caractères utilisés. Donc on rajoute len*tab_carac'length tests.


Il me semble que réaliser un test est plus rapide qu'une opération arithémtique. Mais étant donné que ton algo réalise plus de tests je ne sais pas le quel serait le plus rapide.


J'aurais tendance à penser qu'ils sont aussi rapide l'un que l'autre, mais je demande quand même une confirmation.

[PRomu@ld]

j'aurais tendance à dire que ton algorithme est plus rapide, mais pour récupérer le prochain caractère il faudra parcourir toute la liste de caractères utilisés. Donc on rajoute len*tab_carac'length tests.

Pour récupérer le prochain caractère, tu n'a pas forcément besoin de faire des tests, admettons que tu stoques ton tableau avec les caractères sous forme de liste et que tu utilise un itérateur, tu n'a qu'une affectation et un test à faire (test que tu as déjà compté dans tes calculs..

Ca reste de l'optimisation locale, mais on ne peut peut être pas faire beaucoup plus avec cet algo.