MISTY1

MISTY1
Résumé
Concepteur(s)	Mitsuru Matsui
Première publication	1995
Dérivé de	Aucun
Chiffrement(s) basé(s) sur cet algorithme	Aucun
Caractéristiques
Taille(s) du bloc	64 bits
Longueur(s) de la clé	128 bits
Structure	schéma de Feistel
Nombre de tours	8 tours
Meilleure cryptanalyse
modifier

MISTY1 (pour «Mitsubishi Improved Security Technology») a été créé en 1995 par Mitsuru Matsui pour Mitsubishi Electric.

MISTY1 est un algorithme de chiffrement symétrique par blocs de 64 bits avec une clé de 128 bits et un nombre variable de rondes, basé sur un schéma de Feistel. MISTY1 est conçu pour résister à la cryptanalyse différentielle et à la cryptanalyse linéaire, et pour être très rapide dans ses mises en œuvres matérielles et logicielles. Il est recommandé d'utiliser MISTY1 avec 8 rondes pour un bon compromis vitesse/sécurité.

Description de l'algorithme

L'algorithme peut être divisé en deux parties, à savoir la gestion de la clé et le chiffrement/déchiffrement à proprement parler.

Terminologie

Les opérateurs suivants sont utilisés pour décrire l'algorithme :

• l'opérateur + pour l'addition en complément à deux
• l'opérateur * pour la multiplication
• l'opérateur / pour le quotient de la division euclidienne
• l'opérateur % pour le reste de la division euclidienne
• l'opérateur & pour le et binaire
• l'opérateur | pour le ou binaire
• l'opérateur ^ pour le ou exclusif ou XOR binaire
• l'opérateur << pour le décalage d'un bit vers la gauche
• l'opérateur >> pour le décalage d'un bit vers la droite

Gestion de la clé

L'expansion de la clé est réalisé par l'algorithme suivant :

pour i = 0, ..., 7 faire
   EK[i] = K[i*2]*256 + K[i*2+1]
   pour i = 0, ..., 7 faire
      EK[i+ 8] = FI(EK[i], EK[(i+1)%8])
      EK[i+16] = EK[i+8] & 0x1ff
      EK[i+24] = EK[i+8] >> 9
   finpour
finpour

K est la clé secrète de 128 bits et chaque octet de K est noté K[i].
EK est la clé étendue et chaque élément de EK représente deux octets et est noté EK[i].
K[0 .. 15] est copié dans EK[0 .. 7] puis l'extension de la clé est produite à partir de EK[0 .. 7] en utilisant la fonction FI (décrite dans la section suivante) et est stocké dans EK[8 .. 15].

Le chiffrement

Cette partie décrit les deux fonctions utilisée pour le chiffrement : FO et FL.
La fonction FO utilise (comme l'expansion de la clé ci-dessus) la sous-routine FI. La sous-routine FI utilise deux boîtes-S (S-BOXES) à savoir S7 et S9.

La fonction FO

La fonction FO prend deux paramètres. Le premier est une entrée de 32 bits nommée FO_IN, l'autre est un index d'EK noté k. FO renvoie un buffer de 32 bits de données nommé FO_OUT (ceci est dû à sa structure de schéma de Feistel sur 64 bits).

fonction FO(FO_IN, k)

variables t0, t1 (entiers de 16 bits)
début
   t0 = FO_IN >> 16
   t1 = FO_IN & 0xffff
   t0 = t0 ^ EK[k]
   t0 = FI(t0, EK[(k+5)%8+8])
   t0 = t0 ^ t1
   t1 = t1 ^ EK[(k+2)%8]
   t1 = FI(t1, EK[(k+1)%8+8])
   t1 = t1 ^ t0
   t0 = t0 ^ EK[(k+7)%8]
   t0 = FI(t0, EK[(k+3)%8+8])
   t0 = t0 ^ t1
   t1 = t1 ^ EK[(k+4)%8]
   FO_OUT = (t1<<16) | t0
   retourner FO_OUT
fin

La fonction FI

La fonction FI prend deux paramètres. Le premier est une entrée de 16 bits nommée FO_IN, l'autre est une partie d'EK de 16 bits, à savoir FI_KEY. FI renvoie un buffer de 16 bits, FI_OUT. La fonction FI effectue une substitution d'octet non linéaire par boîte-S.

fonction FI(FI_IN, FI_KEY)

variable d9 (entier de 9 bits)
variable d7 (entier de 7 bits)
début
   d9 = FI_IN >> 7
   d7 = FI_IN & 0x7f
   d9 = S9[d9] ^ d7
   d7 = S7[d7] ^ d9
   ( d7 = d7 & 0x7f)
   d7 = d7 ^ (FI_KEY >> 9)
   d9 = d9 ^ (FI_KEY & 0x1ff)
   d9 = S9[d9] ^ d7
   FI_OUT = (d7<<9) | d9
   retourner FI_OUT
fin

Voici la description des tables S7 et S9 en notation hexadécimale :

La fonction FL

La fonction FO prend deux paramètres. Le premier est une entrée de 32 bits nommée FO_IN, l'autre est un index d'EK noté k. FO renvoie un buffer de 32 bits de données nommé FO_OUT.

fonction FL(FL_IN, k)

variables d0, d1 (entiers de 16 bits)
début
 
   d0 = FL_IN >> 16
   d1 = FL_IN & 0xffff
   si (k est pair) alors
      d1 = d1 ^ (d0 & EK[k/2])
      d0 = d0 ^ (d1 | EK[(k/2+6)%8+8])
   sinon
      d1 = d1 ^ (d0 & EK[((k-1)/2+2)%8+8])
      d0 = d0 ^ (d1 | EK[((k-1)/2+4)%8])
   finsi
   FL_OUT = (d0<<16) | d1
   retourner FL_OUT
fin

Quand l'algorithme est utilisé pour le déchiffrement, la fonction FLINV est utilisée à la place de FL.

fonction FLINV (FL_IN, k)

variables d0, d1 (entiers de 16 bits)
début
 
   d0 = FL_IN >> 16
   d1 = FL_IN & 0xffff
   si (k est pair) alors
      d0 = d0 ^ (d1 | EK[(k/2+6)%8+8])
      d1 = d1 ^ (d0 & EK[k/2])
   sinon
      d0 = d0 ^ (d1 | EK[((k-1)/2+4)%8])
      d1 = d1 ^ (d0 & EK[((k-1)/2+2)%8+8])
   finsi
   FL_OUT = (d0<<16) | d1
   retourner FL_OUT
fin

Description du chiffrement/déchiffrement

On utilise en général un chiffrement/déchiffrement en 8 rondes. Une ronde consiste en un appel à la fonction FO, les rondes paires incluent en plus un appel à FL ou FLINV. Après la ronde finale un appel à FL ou FLINV est effectué.
Voici les descriptions détaillées des rondes pour le chiffrement :

Un texte clair P de 64 bits est divisé en D0 (les 32 bits de poids fort) et D1 (les 32 bits de poids faible).

 début
  // ronde 0
  D0 = FL(D0, 0);
  D1 = FL(D1, 1);
  D1 = D1 ^ FO(D0, 0);
  // ronde 1
  D0 = D0 ^ FO(D1, 1);
  // ronde 2
  D0 = FL(D0, 2);
  D1 = FL(D1, 3);
  D1 = D1 ^ FO(D0, 2);
  // ronde 3
  D0 = D0 ^ FO(D1, 3);
  // ronde 4
  D0 = FL(D0, 4);
  D1 = FL(D1, 5);
  D1 = D1 ^ FO(D0, 4);
  // ronde 5
  D0 = D0 ^ FO(D1, 5);
  // ronde 6
  D0 = FL(D0, 6);
  D1 = FL(D1, 7);
  D1 = D1 ^ FO(D0, 6);
  // ronde 7
  D0 = D0 ^ FO(D1, 7);
  // final
  D0 = FL(D0, 8);
  D1 = FL(D1, 9);
 fin

Le texte chiffré C de 64 bits est construit à partir de D0 et D1 de la manière suivante :

  C = (D1<<32) | D0;

Lors du déchiffrement, l'ordre des rondes est inversé :

 début
  D0 = C & 0xffffffff;
  D1 = C >> 32;
  D0 = FLINV(D0, 8);
  D1 = FLINV(D1, 9);
  D0 = D0 ^ FO(D1, 7);
  D1 = D1 ^ FO(D0, 6);
  D0 = FLINV(D0, 6);
  D1 = FLINV(D1, 7);
  D0 = D0 ^ FO(D1, 5);
  D1 = D1 ^ FO(D0, 4);
  D0 = FLINV(D0, 4);
  D1 = FLINV(D1, 5);
  D0 = D0 ^ FO(D1, 3);
  D1 = D1 ^ FO(D0, 2);
  D0 = FLINV(D0, 2);
  D1 = FLINV(D1, 3);
  D0 = D0 ^ FO(D1, 1);
  D1 = D1 ^ FO(D0, 0);
  D0 = FLINV(D0, 0);
  D1 = FLINV(D1, 1);
  P = (D0<<32) | D1;
 fin

Liens externes

• (en) La RFC dont est tiré ce texte
• (fr) La traduction française de la RFC

• Portail de la cryptologie