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 tours, basé sur un réseau 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 œuvre matérielles et logicielles. Il est recommandé d'utiliser Misty1 avec huit tours 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, etc., 7 faire
EK[i] = K[i*2]*256 K[i*2 1]
finpour pour i = 0, etc., 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
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 FI_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 FL prend deux paramètres. Le premier est une entrée de 32 bits nommée FL_IN, l'autre est un index d'EK noté k. FL renvoie un buffer de 32 bits de données nommé FL_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 tours. Un tour consiste en un appel à la fonction FO, les tours paires incluent en plus un appel à FL ou FLINV. Après le tour final un appel à FL ou FLINV est effectué.
Voici les descriptions détaillées des tours 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
// tour 0
D0 = FL(D0, 0);
D1 = FL(D1, 1);
D1 = D1 ^ FO(D0, 0);
// tour 1
D0 = D0 ^ FO(D1, 1);
// tour 2
D0 = FL(D0, 2);
D1 = FL(D1, 3);
D1 = D1 ^ FO(D0, 2);
// tour 3
D0 = D0 ^ FO(D1, 3);
// tour 4
D0 = FL(D0, 4);
D1 = FL(D1, 5);
D1 = D1 ^ FO(D0, 4);
// tour 5
D0 = D0 ^ FO(D1, 5);
// tour 6
D0 = FL(D0, 6);
D1 = FL(D1, 7);
D1 = D1 ^ FO(D0, 6);
// tour 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 tours 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
Notes et références
Annexes
Liens externes
- (en) La RFC dont est tiré ce texte
- (fr) La traduction française de la RFC
Bibliographie
- [Bar-On et Keller 2016] (en) Achiya Bar-On et Nathan Keller, « A 2⁷⁰ Attack on the Full Misty1 », Crypto, (DOI 10.1007/978-3-662-53018-4_16, lire en ligne).
- [Matsui 1997] (en) Mitsuru Matsui, « New block encryption algorithm MISTY », Fast Software Encryption (FSE), (DOI 10.1007/BFb0052334).
- Portail de la cryptologie
