Concepteur(s) | Mitsuru Matsui |
---|---|
Première publication | 1995 |
Dérivé de | Aucun |
Chiffrement(s) basé(s) sur cet algorithme | Camellia, MISTY2, KASUMI |
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 (pour «Mitsubishi Improved Security Technology») a été créé en 1995 par Mitsuru Matsui pour Mitsubishi Electric[2].
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é.
L'algorithme peut être divisé en deux parties, à savoir la gestion de la clé et le chiffrement/déchiffrement à proprement parler.
Les opérateurs suivants sont utilisés pour décrire l'algorithme :
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].
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 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 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 :
S7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
00: | 1b | 32 | 33 | 5a | 3b | 10 | 17 | 54 | 5b | 1a | 72 | 73 | 6b | 2c | 66 | 49 |
10: | 1f | 24 | 13 | 6c | 37 | 2e | 3f | 4a | 5d | 0f | 40 | 56 | 25 | 51 | 1c | 04 |
20: | 0b | 46 | 20 | 0d | 7b | 35 | 44 | 42 | 2b | 1e | 41 | 14 | 4b | 79 | 15 | 6f |
30: | 0e | 55 | 09 | 36 | 74 | 0c | 67 | 53 | 28 | 0a | 7e | 38 | 02 | 07 | 60 | 29 |
40: | 19 | 12 | 65 | 2f | 30 | 39 | 08 | 68 | 5f | 78 | 2a | 4c | 64 | 45 | 75 | 3d |
50: | 59 | 48 | 03 | 57 | 7c | 4f | 62 | 3c | 1d | 21 | 5e | 27 | 6a | 70 | 4d | 3a |
60: | 01 | 6d | 6e | 63 | 18 | 77 | 23 | 05 | 26 | 76 | 00 | 31 | 2d | 7a | 7f | 61 |
70: | 50 | 22 | 11 | 06 | 47 | 16 | 52 | 4e | 71 | 3e | 69 | 43 | 34 | 5c | 58 | 7d |
S9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
000: | 1c3 | 0cb | 153 | 19f | 1e3 | 0e9 | 0fb | 035 | 181 | 0b9 | 117 | 1eb | 133 | 009 | 02d | 0d3 |
010: | 0c7 | 14a | 037 | 07e | 0eb | 164 | 193 | 1d8 | 0a3 | 11e | 055 | 02c | 01d | 1a2 | 163 | 118 |
020: | 14b | 152 | 1d2 | 00f | 02b | 030 | 13a | 0e5 | 111 | 138 | 18e | 063 | 0e3 | 0c8 | 1f4 | 01b |
030: | 001 | 09d | 0f8 | 1a0 | 16d | 1f3 | 01c | 146 | 07d | 0d1 | 082 | 1ea | 183 | 12d | 0f4 | 19e |
040: | 1d3 | 0dd | 1e2 | 128 | 1e0 | 0ec | 059 | 091 | 011 | 12f | 026 | 0dc | 0b0 | 18c | 10f | 1f7 |
050: | 0e7 | 16c | 0b6 | 0f9 | 0d8 | 151 | 101 | 14c | 103 | 0b8 | 154 | 12b | 1ae | 017 | 071 | 00c |
060: | 047 | 058 | 07f | 1a4 | 134 | 129 | 084 | 15d | 19d | 1b2 | 1a3 | 048 | 07c | 051 | 1ca | 023 |
070: | 13d | 1a7 | 165 | 03b | 042 | 0da | 192 | 0ce | 0c1 | 06b | 09f | 1f1 | 12c | 184 | 0fa | 196 |
080: | 1e1 | 169 | 17d | 031 | 180 | 10a | 094 | 1da | 186 | 13e | 11c | 060 | 175 | 1cf | 067 | 119 |
090: | 065 | 068 | 099 | 150 | 008 | 007 | 17c | 0b7 | 024 | 019 | 0de | 127 | 0db | 0e4 | 1a9 | 052 |
0a0: | 109 | 090 | 19c | 1c1 | 028 | 1b3 | 135 | 16a | 176 | 0df | 1e5 | 188 | 0c5 | 16e | 1de | 1b1 |
0b0: | 0c3 | 1df | 036 | 0ee | 1ee | 0f0 | 093 | 049 | 09a | 1b6 | 069 | 081 | 125 | 00b | 05e | 0b4 |
0c0: | 149 | 1c7 | 174 | 03e | 13b | 1b7 | 08e | 1c6 | 0ae | 010 | 095 | 1ef | 04e | 0f2 | 1fd | 085 |
0d0: | 0fd | 0f6 | 0a0 | 16f | 083 | 08a | 156 | 09b | 13c | 107 | 167 | 098 | 1d0 | 1e9 | 003 | 1fe |
0e0: | 0bd | 122 | 089 | 0d2 | 18f | 012 | 033 | 06a | 142 | 0ed | 170 | 11b | 0e2 | 14f | 158 | 131 |
0f0: | 147 | 05d | 113 | 1 cd | 079 | 161 | 1a5 | 179 | 09e | 1b4 | 0cc | 022 | 132 | 01a | 0e8 | 004 |
100: | 187 | 1ed | 197 | 039 | 1bf | 1d7 | 027 | 18b | 0c6 | 09c | 0d0 | 14e | 06c | 034 | 1f2 | 06e |
110: | 0ca | 025 | 0ba | 191 | 0fe | 013 | 106 | 02f | 1ad | 172 | 1db | 0c0 | 10b | 1d6 | 0f5 | 1ec |
120: | 10d | 076 | 114 | 1ab | 075 | 10c | 1e4 | 159 | 054 | 11f | 04b | 0c4 | 1be | 0f7 | 029 | 0a4 |
130: | 00e | 1f0 | 077 | 04d | 17a | 086 | 08b | 0b3 | 171 | 0bf | 10e | 104 | 097 | 15b | 160 | 168 |
140: | 0d7 | 0bb | 066 | 1ce | 0fc | 092 | 1c5 | 06f | 016 | 04a | 0a1 | 139 | 0af | 0f1 | 190 | 00a |
150: | 1aa | 143 | 17b | 056 | 18d | 166 | 0d4 | 1fb | 14d | 194 | 19a | 087 | 1f8 | 123 | 0a7 | 1b8 |
160: | 141 | 03c | 1f9 | 140 | 02a | 155 | 11a | 1a1 | 198 | 0d5 | 126 | 1af | 061 | 12e | 157 | 1dc |
170: | 072 | 18a | 0aa | 096 | 115 | 0ef | 045 | 07b | 08d | 145 | 053 | 05f | 178 | 0b2 | 02e | 020 |
180: | 1d5 | 03f | 1c9 | 1e7 | 1ac | 044 | 038 | 014 | 0b1 | 16b | 0ab | 0b5 | 05a | 182 | 1c8 | 1d4 |
190: | 018 | 177 | 064 | 0cf | 06d | 100 | 199 | 130 | 15a | 005 | 120 | 1bb | 1bd | 0e0 | 04f | 0d6 |
1a0: | 13f | 1c4 | 12a | 015 | 006 | 0ff | 19b | 0a6 | 043 | 088 | 050 | 15f | 1e8 | 121 | 073 | 17e |
1b0: | 0bc | 0c2 | 0c9 | 173 | 189 | 1f5 | 074 | 1cc | 1e6 | 1a8 | 195 | 01f | 041 | 00d | 1ba | 032 |
1c0: | 03d | 1d1 | 080 | 0a8 | 057 | 1b9 | 162 | 148 | 0d9 | 105 | 062 | 07a | 021 | 1ff | 112 | 108 |
1d0: | 1c0 | 0a9 | 11d | 1b0 | 1a6 | 0 cd | 0f3 | 05c | 102 | 05b | 1d9 | 144 | 1f6 | 0ad | 0a5 | 03a |
1e0: | 1cb | 136 | 17f | 046 | 0e1 | 01e | 1dd | 0e6 | 137 | 1fa | 185 | 08c | 08f | 040 | 1b5 | 0be |
1f0: | 078 | 000 | 0ac | 110 | 15e | 124 | 002 | 1bc | 0a2 | 0ea | 070 | 1fc | 116 | 15c | 04c | 1c2 |
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
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