Misty1

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

Misty1
Résumé
Concepteur(s) Mitsuru Matsui
Première publication 1995
Dérivé de Aucun
Chiffrement(s) basé(s) sur cet algorithme Camellia, MISTY2, KASUMI
Caractéristiques
Taille(s) du bloc 64 bits
Longueur(s) de la clé 128 bits
Structure réseau de Feistel
Nombre de tours 8 tours

Meilleure cryptanalyse

Une attaque complète avec recouvrement total de la clef en 263,9999 chiffrés choisis et en temps 279 ou en 264 chiffrés choisis et en temps 269.5 opérations[1]

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 :

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 :

S70123456 789abcdef
00:1b32335a3b1017 545b1a72736b2c6649
10:1f24136c372e3f 4a5d0f405625511c04
20:0b46200d7b3544 422b1e41144b79156f
30:0e550936740c67 53280a7e3802076029
40:1912652f303908 685f782a4c6445753d
50:594803577c4f62 3c1d215e276a704d3a
60:016d6e63187723 05267600312d7a7f61
70:50221106471652 4e713e6943345c587d


S90123456 789abcdef
000:1c30cb15319f1e30e90fb 0351810b91171eb13300902d0d3
010:0c714a03707e0eb164193 1d80a311e05502c01d1a2163118
020:14b1521d200f02b03013a 0e511113818e0630e30c81f401b
030:00109d0f81a016d1f301c 14607d0d10821ea18312d0f419e
040:1d30dd1e21281e00ec059 09101112f0260dc0b018c10f1f7
050:0e716c0b60f90d8151101 14c1030b815412b1ae01707100c
060:04705807f1a4134129084 15d19d1b21a304807c0511ca023
070:13d1a716503b0420da192 0ce0c106b09f1f112c1840fa196
080:1e116917d03118010a094 1da18613e11c0601751cf067119
090:06506809915000800717c 0b70240190de1270db0e41a9052
0a0:10909019c1c10281b3135 16a1760df1e51880c516e1de1b1
0b0:0c31df0360ee1ee0f0093 04909a1b606908112500b05e0b4
0c0:1491c717403e13b1b708e 1c60ae0100951ef04e0f21fd085
0d0:0fd0f60a016f08308a156 09b13c1071670981d01e90031fe
0e0:0bd1220890d218f012033 06a1420ed17011b0e214f158131
0f0:14705d1131 cd0791611a5 17909e1b40cc02213201a0e8004
100:1871ed1970391bf1d7027 18b0c609c0d014e06c0341f206e
110:0ca0250ba1910fe013106 02f1ad1721db0c010b1d60f51ec
120:10d0761141ab07510c1e4 15905411f04b0c41be0f70290a4
130:00e1f007704d17a08608b 0b31710bf10e10409715b160168
140:0d70bb0661ce0fc0921c5 06f01604a0a11390af0f119000a
150:1aa14317b05618d1660d4 1fb14d19419a0871f81230a71b8
160:14103c1f914002a15511a 1a11980d51261af06112e1571dc
170:07218a0aa0961150ef045 07b08d14505305f1780b202e020
180:1d503f1c91e71ac044038 0140b116b0ab0b505a1821c81d4
190:0181770640cf06d100199 13015a0051201bb1bd0e004f0d6
1a0:13f1c412a0150060ff19b 0a604308805015f1e812107317e
1b0:0bc0c20c91731891f5074 1cc1e61a819501f04100d1ba032
1c0:03d1d10800a80571b9162 1480d910506207a0211ff112108
1d0:1c00a911d1b01a60 cd0f3 05c10205b1d91441f60ad0a503a
1e0:1cb13617f0460e101e1dd 0e61371fa18508c08f0401b50be
1f0:0780000ac11015e124002 1bc0a20ea0701fc11615c04c1c2

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

  1. Bar-On et Keller 2016.
  2. Matsui 1997, Publication dans une conférence. Les premières traces sont dans un (en) rapport technique.

Annexes

Liens externes

Bibliographie

  • Portail de la cryptologie
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.