Cryptographie : Algorithmes

          La plupart des algorithmes présentés jusqu'ici sont assez simple, même s'ils permettent d'obtenir un cryptage complexe et sûr en les combinant. Voici donc quelques autres algorithmes un peu plus complexes, basés sur des règles mathématiques plus complexes.

       A) Un cryptosystème sans clé

          Supposons qu'Alice et Bob veuillent communiquer. Ils choisissent P un nombre premier très grand, public. Le message sera chiffré par blocs, assimilés à des nombres M, plus petits que P.

• Alice choisit a, plus petit que P et premier avec P-1, Bob choisit b de la même manière.
• Alice envoie à Bob C tel que : C = M^a [mod P]
• Bob renvoie à Alice D tel que : D = C^b [mod P]
• Alice calcule a' tel que a.a' = 1 [mod P] et envoie à Bob E tel que : E = D^a'[mod P]
• Bob calcule b' tel que b.b' = 1 [mod P] et obtient alors :
  M = E^b'[mod P]

E^b' = D^a'.b' = C^a'.b.b' = C^a'= M^a.a' = M [mod P]

       B) Cryptosystème à clé publique (Diffie-Helmann)

          Soit un groupe de N utilisateurs. Voici un protocole à clé publique pour leur permettre de communiquer sans avoir à échanger leurs clés.

• Choix d'un nombre premier P assez grand et de a une racine primitive¹ de P
• Chaque utilisateur U_i choisit une clé privée X_i comprise entre 1 et P-1, et publie Y_i tel que :
  Y_i = a^Xi [mod P]
• Lorsque U_i veut communiquer à U_j le message M, il lui envoie le message crypté (a^Xj, Y_i^Xi.M) qui constituent le message chiffré (C₁, C₂)
• U_i déchiffre alors C₁^Xi = a^Xj.Xi = Y_i^Xj = K

et donc : M = C₂.K^-1

       C) Algorithme du "sac à dos"

          Soit une suite (a_i) supercroissante, c'est-à-dire que chaque terme de la suite est strictement supérieur à la somme de tous les précédents. Soit N un entier, somme de plusieurs a_i. On peut facilement décomposer N pour obtenir la liste des a_i correspondants, puisque la suite est supercroissante. Si (b_i) est un vecteur de bits, c'est à dire une suite de bits du type (01001011010...), de longueur finie, on codera le message M sous forme binaire : M = (b_i) par C = S b_i.a_i. En retrouvant les a_i, on reconstitue donc M facilement.
          Pour compliquer un peu cet algorithme, on choisit m supérieur à la somme de tous les a_i, ainsi que u premier avec m et v inverse de u modulo m, tous secrets, et publie (c_i) avec c_i = u.a_i [m].

• M = (b_i) avec (b_i) un vecteur de bits, c'est-à-dire que b_i = 0 ou 1
• C = S c_i.b_i est le message crypté
• Pour déchiffrer, il suffit de calculer D = v.C [m] = vS c_i.b_i [m]= S a_i.b_i
  Il est alors possible de décomposer D en termes de (a_i) : on en déduit alors la suite (b_i), qui correspond à M.

       D) Calcul matriciel

          Ici, le message est assimilé à une matrice colonne M, de dimension n. La clé est une matrice carrée K d'ordre n inversible. On peut alors écrire le message chiffré sous forme d'une matrice colonne C :

C = K.M

D = K^-1.C = K^-1.K.M = M

Copyright © BLANC David - 2000