MISTY1

MISTY1 (for “ Mitsubishi Improved Security Technology ”) was created in 1995 by Mitsuru Matsui for Mitsubishi Electric.

MISTY1 is a symmetrical algorithm of Chiffrement per blocks of 64 bits with a key of 128 bits and a variable number of rounds, based on a Schéma of Feistel. MISTY1 is conceived to resist the Cryptanalyse differential and the linear Cryptanalyse, and to be very fast in its implemented material S and Logiciel them. It is recommended to use MISTY1 with 8 rounds for a good compromise speed/safety.

Description of the algorithm

The algorithm can be divided into two parts, namely management of the key and the Chiffrement/Déchiffrement strictly speaking.

Terminology

The operator S following are used to describe the algorithm:

the operator + for the Addition in Twos complement
the operator * for the Multiplication
the operator / for the quotient of the Euclidean Division
the operator % for the remainder of the Euclidean Division
the operator & for the binary and
the operator | for the Or binary
the operator ^ for the Or exclusive or binary XOR
the operator << for the shift of a bit towards the left
the operator >> for the shift of a bit towards the line

Management of the key

The expansion of the key is carried out by the following algorithm:

pour I = 0,…, 7 faire
EK = K*256 + K
pour I = 0,…, 7 faire
EK 8 = FI (EK, EK)
EK = EK & 0x1ff
EK = EK >> 9
finpour
finpour

K is the secret key of 128 bits and each byte of K is noted K.
EK is the wide key and each element of EK accounts for two Octet S and is noted EK.
K. 15 are copied in EK. 7 then the extension of the key is produced starting from EK. 7 by using function FI (described in the following section) and is stored in EK. 15.

Coding

This part describes both function S used for coding: FO and FL.
La FO function uses (like the expansion of the key above) sub-routine FI. Under routine FI two boxes-S (S-BOXES) with knowing uses S7 and S9.

The FO function

The FO function takes two Paramètre S. the first is a named entry of 32 bits FO_IN, the other is an index of EK noted K. FO returns a buffer of 32 bits of data named FO_OUT (this is due to its structure of diagram of Feistel on 64 bits).

fonction FO (FO_IN, K)
variables t0, T1 (entireties of 16 bits)
début
t0 = FO_IN >> 16
T1 = FO_IN & 0xffff
t0 = t0 ^ EK
t0 = FI (t0, EK)
t0 = t0 ^ t1
T1 = T1 ^ EK
T1 = FI (T1, EK)
T1 = T1 ^ t0
t0 = t0 ^ EK
t0 = FI (t0, EK)
t0 = t0 ^ t1
T1 = T1 ^ EK
FO_OUT = (t1<<16) | t0
retourner FO_OUT
fin

Function FI

Function FI takes two Paramètre S. the first is a named entry of 16 bits FO_IN, the other is part of EK of 16 bits, namely FI_KEY. FI returns a buffer of 16 bits, FI_OUT. Function FI carries out a Substitution nonlinear byte by Box-S. FONCTION FI (FI_IN, FI_KEY)
variable d9 (whole of 9 bits)
variable d7 (whole of 7 bits)
début
d9 = FI_IN >> 7
d7 = FI_IN & 0x7f
d9 = S9 ^ d7
d7 = S7 ^ d9
(d7 = d7 & 0x7f)
d7 = d7 ^ (FI_KEY >> 9)
d9 = d9 ^ (FI_KEY & 0x1ff)
d9 = S9 ^ d7
FI_OUT = (d7<<9) | d9
retourner FI_OUT
fin

Here the description of the S7 tables and Hexadecimal S9 in notation E:

Function FL

The FO function takes two parameters. The first is a named entry of 32 bits FO_IN, the other is an index of EK noted K. FO returns a buffer of 32 bits of data named FO_OUT.

fonction FL (FL_IN, K)
variables d0, d1 (whole of 16 bits)
début
d0 = FL_IN >> 16
d1 = FL_IN & 0xffff
si (K is even) alors
d1 = d1 ^ (d0 & EK)
d0 = d0 ^ (d1 | EK)
sinon
d1 = d1 ^ (d0 & EK)
d0 = d0 ^ (d1 | EK)
finsi
FL_OUT = (d0<<16) | d1
retourner FL_OUT
fin

When the algorithm is used for the deciphering, function FLINV is used in the place of FL.

fonction FLINV (FL_IN, K)
variables d0, d1 (whole of 16 bits)
début
d0 = FL_IN >> 16
d1 = FL_IN & 0xffff
si (K is even) alors
d0 = d0 ^ (d1 | EK)
d1 = d1 ^ (d0 & EK)
sinon
d0 = d0 ^ (d1 | EK)
d1 = d1 ^ (d0 & EK)
finsi
FL_OUT = (d0<<16) | d1
retourner FL_OUT
fin

Description of coding/deciphering

One in general uses a coding/deciphering in 8 rounds. A round consists of a call to the FO function, the even rounds include in more one call to FL or FLINV. After the final round a call to FL or FLINV is effectué.
Here detailed descriptions of the rounds for coding:

A clear text P of 64 bits is divided into D0 (32 bits of strong weight) and D1 (32 bits of weak weight).

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

The text quantified C of 64 bits is built starting from D0 and D1 in the following way:

C = (D1<<32) | D0;

At the time of the deciphering, the order of the rounds is reversed:

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

External bonds

the RFC from which this text
is drawn the French translation from the RFC

Random links: