LOTFree 3

Dossier Cryptographie : Partie 1

Comme son nom l'indique, cet article aura pour thème la cryptographie. J'ai mis partie 1 car il y aura peut-être une suite dans lotfree#4 (ya des chances ;-).
Certains passeront directement à l'article suivant rien qu'à la vue du mot cryptographie, pourtant c'est un domaine très vaste et qui est utilisé de façon automatique aujourd'hui. C'est bien simple, on crypte tout : vos cookies, vos transactions et même votre quatrième chaine de tv.
La cryptographie tient plus du domaine des mathématiques que de l'informatique pourtant sans l'informatique la cryptographie serait rien : imaginez décoder une page entière sans utiliser un prog qui fait le travail à votre place, ça peut prendre des heures.
La cryptographie peut vous être utile si vous avez peur que quelqu'un intercepte vos données, ou lise vos mails. (au cas où l'admin de votre bahut ne vous tient pas dans son cœur ;-)
Aujourd'hui je vais vous faire découvrir (ou pas) la méthode de Vigenere (le carre de Vigenere) mais on va aussi voir ses dérivés (plus évolués). Mais vous allez voir c'est très facile.

Vigenere est une des méthodes de cryptographie utilisant une clé que seul le destinataire et l'envoyeur du message doivent connaitre. Ils n'utilisent pas tous ce système qui semble pourtant naturel (si vous avez lu l'article qui suit vous savez déjà que la base64 n'a pas de clé).
Bon on a donc une clé et un message a crypter. On agit lettre par lettre (avec la première lettre de la clé et la première lettre de la phrase à crypter on obtient la première lettre de la phrase cryptée et ainsi de suite). L'algorithme utilisé est une addition basée sur l'alphabet. Chaque lettre a une valeur, c'est à dire que A vaut 0, B vaut 1, C vaut 2 ... Z vaut 25.

Ainsi A+A=0+0=0=A. Comme A vaut 0 tout lettre crypté avec A vaudra elle même. Un autre exemple : S+B = 18 + 1 = 19=T.
Dernier exemple : Y + K = 24+10=34. On est sorti del'aphabet (on s'arrête à 25) alors on revient au début.
On fait 34 divisé par 26 ça y va 1 fois il reste 8 soit la lettre I. (on a fait un tour de boucle : 25 est Z, donc 26 est A, en gros 26 vaut 0).
On utilise donc le reste de la division entière (division euclidienne) aussi appelé modulo (ici on fait un modulo 26).

De façon plus simple on peut utiliser le carré de Vigenere. Il suffit de prendre l'intersection de deux lettres pour obtenir la lettre cryptée. Ici on voit bien que l'intersection de Y et K donne I.

K (key) A B C D E F G H I J K L M N O P Q R S T U V W X Y Z  (plaintext)
------- ---------------------------------------------------       P
  A     A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
  B     B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
  C     C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
  D     D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
  E     E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
  F     F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
  G     G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
  H     H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
  I     I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
  J     J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
  K     K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
  L     L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
  M     M N O P Q R S T U V W X Y Z A B C D E F G H I J K L  ciphertext
  N     N O P Q R S T U V W X Y Z A B C D E F G H I J K L M      C
  O     O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
  P     P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
  Q     Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
  R     R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
  S     S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
  T     T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
  U     U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
  V     V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
  W     W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
  X     X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
  Y     Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
  Z     Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Souvent la cle est un mot, dans tous les cas elle est souvent plus petite que la phrase à crypter. Alors pour crypter la phrase Vigenere a eu l'idée de répéter la clé plusieurs fois.
Si la clé est lotfree et la phrase à crypter est "la cryptographie c'est cool", on aura :

Clé     : L O T F R E E L O T F R E E L O T F R E E L O
Phrase  : L A C R Y P T O G R A P H I E C E S T C O O L
Résultat: W O V W P T X Z U K F G L M P Q X X K G S Z Z

Et pour déchiffrer c'est pas plus difficile : on reprend l'exemple du Y et du K. On regarde dans la ligne (ou la colonne) de la lettre K et on cherche la lettre I dans cette ligne. On remonte... On est dans la colonne des Y, c'est bon. Peut importe que vous prenez les lignes ou les colonnes.
Il y a plus simple pour crypter/decrypter avec cette méthode, c'est en utilisant les blocs :

Clé     : L O T F R E E
Phrase  : L A C R Y P T     Résultat : W O V W P T X
          O G R A P H I                Z U K F G L M
          E C E S T C O                P Q X X K G S
          O L                          Z Z

Maintenant, la méthode Variant : seul le carré change, il faut par contre respecter les colonnes et les lignes :

K (key) A B C D E F G H I J K L M N O P Q R S T U V W X Y Z  (plaintext)
------- ---------------------------------------------------       P
  A     A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
  Z     B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
  Y     C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
  X     D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
  W     E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
  V     F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
  U     G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
  T     H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
  S     I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
  R     J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
  Q     K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
  P     L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
  O     M N O P Q R S T U V W X Y Z A B C D E F G H I J K L  ciphertext
  N     N O P Q R S T U V W X Y Z A B C D E F G H I J K L M       C
  M     O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
  L     P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
  K     Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
  J     R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
  I     S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
  H     T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
  G     U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
  F     V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
  E     W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
  D     X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
  C     Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
  B     Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Donc ici si la clé est K et que l'on veut crypter Y on obtient O. Pour décrypter on a K comme clé et O comme résultat. On cherche O sur la ligne de K, on remonte, on tombe sur Y.

Je vous présente aussi la méthode Beaufort :

K (key) A B C D E F G H I J K L M N O P Q R S T U V W X Y Z  (plaintext)
------- ---------------------------------------------------       P
  Z    Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
  Y    Y X W V U T S R Q P O N M L K J I H G F E D C B A Z
  X    X W V U T S R Q P O N M L K J I H G F E D C B A Z Y
  W    W V U T S R Q P O N M L K J I H G F E D C B A Z Y X
  V    V U T S R Q P O N M L K J I H G F E D C B A Z Y X W
  U    U T S R Q P O N M L K J I H G F E D C B A Z Y X W V
  T    T S R Q P O N M L K J I H G F E D C B A Z Y X W V U
  S    S R Q P O N M L K J I H G F E D C B A Z Y X W V U T
  R    R Q P O N M L K J I H G F E D C B A Z Y X W V U T S
  Q    Q P O N M L K J I H G F E D C B A Z Y X W V U T S R
  P    P O N M L K J I H G F E D C B A Z Y X W V U T S R Q
  O    O N M L K J I H G F E D C B A Z Y X W V U T S R Q P
  N    N M L K J I H G F E D C B A Z Y X W V U T S R Q P 0  ciphertext
  M    M L K J I H G F E D C B A Z Y X W V U T S R Q P 0 N       C
  L    L K J I H G F E D C B A Z Y X W V U T S R Q P 0 N M
  K    K J I H G F E D C B A Z Y X W V U T S R Q P 0 N M L
  J    J I H G F E D C B A Z Y X W V U T S R Q P 0 N M L K
  I    I H G F E D C B A Z Y X W V U T S R Q P 0 N M L K J
  H    H G F E D C B A Z Y X W V U T S R Q P 0 N M L K J I
  G    G F E D C B A Z Y X W V U T S R Q P 0 N M L K J I H
  F    F E D C B A Z Y X W V U T S R Q P 0 N M L K J I H G
  E    E D C B A Z Y X W V U T S R Q P 0 N M L K J I H G F
  D    D C B A Z Y X W V U T S R Q P 0 N M L K J I H G F E
  C    C B A Z Y X W V U T S R Q P 0 N M L K J I H G F E D
  B    B A Z Y X W V U T S R Q P 0 N M L K J I H G F E D C
  A    A Z Y X W V U T S R Q P 0 N M L K J I H G F E D C B

Voilà, pas de commentaires.

Il y a aussi la façon de découper la phrase qui entre en jeu, par exemple la méthode slidefair consiste a découper par paire de lettres. Exemple :

Key = DIGRAPH

Phrase : the Slidefair can be used with Vigenere, Variant or Beaufort.

K = |  D  I  G  R  A  P  H
-------------------------------
P = | th es li de fa ir ca         C = | EW KM CR NU AF CX TJ
    | nb eu se dw it hv ig             | YQ MM YY FU TI GW ZP
    | en er ev ar ia nt or             | KH JM PK BS AI EC KV
    | be au fo rt                      | CF MI IL CI

C: EW KM CR NU AF CX TJ YQ MM YY FU TI GW ZP
   KH JM PK BS AI EC KV CF MI IL CI

La méthode Interrupted key utilise un découpage par mots. Bref il y a pas mal de possibilitées : toutes les x lettres, tous les x mots, les x syllabes, ou en alternant 1 lettre / 2 lettres...

La méthode dérivée que je trouve la mieux est la Autokey, que je vous ai gardé pour la fin. Elle consiste à utiliser la phrase à crypter comme clé. Mais il y a toujours une vrai clé. On a vu qu'avec Vigenere on répétait la clé jusqu'à ce que le cryptage soit terminé. Ici la clé est la concaténation (l'accrochage) d'elle même avec la phrase à crypter. Voici un exemple :

Phrase :  The autokey can be used with Vigenere, Variant or Beaufort.
Clé : PRIMER

Clé      : P R I M E R T H E A U T O K E Y C A N B E U S E D W I T H V I G E N E R E V A R I A N T O R B E
Phrase   : t h e a u t o k e y c a n b e u s e d w i t h v i g e n e r e v a r i a n t o r b e a u f o r t
Résultat : I Y M M Y K H R I Y W T B L I S U E Q X M N Z Z L C M G L M M B E E M R R O O I J E N N T F S X

Pour l'encryption il n'y a pas de problèmes, en revanche pour décrypter on découvre la clé en même temps que la phrase. Le problème c'est que si on se trompe une fois après tout le reste est faux. Mais cette méthode est plus intéressante.

Histoire de vous gater je vous ai codé un petit prog en Pascal (parce qu'en C++ la gestion des chaines de caractères c pas super facile) qui utilise la méthode autokey. Il crypte et décrypte ce que vous entrez au clavier. Si vous savez programmer vous pouvez l'améliorer pour la lecture de fichier... Voici la source :

program crypto;
var key,phrase,res : string;
    choix,cpt : integer;

procedure touppercase(var mot:string);
   var i:integer;
   begin
   for i:=1 to length(mot) do
   if (mot[i]>='a') and (mot[i]<='z') then ord(mot[i]):=ord(mot[i])-32;
   end;

function inint(var c:char):boolean;
   begin
   if (c>='A') and (c<='Z') then
   inint:=true
   else inint:=false;
   end;

begin {debut du main}
   choix:=0;
   res:='';
   writeln('Choisissez le mode de fonctionnement :');
   while ((choix<1) or (choix>2)) do
   begin
   writeln('1->Cryptage');
   writeln('2->Decryptage');
   write('?');
   readln(choix);
   end;
   writeln('Entrez la cle : ');
   readln(key);
   writeln('Entrez la phrase : ');
   readln(phrase);
   touppercase(key);
   touppercase(phrase);

if choix=1 then
   begin
   key:=key+phrase;
     for cpt:=1 to length(phrase) do
     begin
     if ( inint(key[cpt]) and inint(phrase[cpt]) ) then
       begin
       res := res + chr( (((ord(key[cpt]) mod 65) + (ord(phrase[cpt]) mod 65)) mod    26) + 65)
       end
     else res:=res+phrase[cpt];
     end;
   writeln('--Resultat du cryptage--');
   writeln(res);
 end
 else
   begin
     for cpt:=1 to length(phrase) do
     begin
     if ( inint(key[cpt]) and inint(phrase[cpt]) ) then
       begin
       choix:=(ord(phrase[cpt]) mod 65) - (ord(key[cpt]) mod 65);
       if choix<0 then choix:=choix+26;
       res := res + chr(choix+65);
       end
     else res:=res+phrase[cpt];
     key:=key+res[cpt];
     end;
   writeln('--Resultat du decryptage--');
   writeln(res);
   end;
 write('Appuyez sur entree pour quitter');
 readln;
 end.

Le prog est joint avec le mag, c'est crypto.exe, pas de valeurs a passer comme argument, ya un menu etc... J'espère que cet article vous aura plus.