MISTY1

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 8. september 2017; checks kræver 5 redigeringer .

MISTY1
Skaber	Mitsuru Matsui, Tetsuya Ichikawa, Jun Sorimachi, Toshio Tokita, Atsuhiro Yamagishi
Oprettet	1995 _
offentliggjort	1996 [ 1 ]
Nøglestørrelse	128 bit
Blokstørrelse	64 bit
Antal runder	4×n (anbefalet 8)
Type	Feistel netværk

MISTY1 (eller MISTY-1 ) er en blokkrypteringsalgoritme skabt på basis af "nested" Feistel-netværk i 1995 af kryptologen Mitsuru Matsui sammen med en gruppe specialister for Mitsubishi Electric . MISTY er en forkortelse af Mitsubishi Improved Security Technology, samt initialerne for skaberne af algoritmen: Tetsuya Ichikawa, Jun Sorimachi, Toshio Tokita og Atsuhiro Yamagishi deltog også i udviklingen af algoritmen [2 ] . Algoritmen blev udviklet i 1995, men blev licenseret og offentliggjort i 1996.

MISTY1 er et Feistel-netværk med et variabelt antal runder (anbefalet 8, men det kan være et hvilket som helst multiplum af 4). Algoritmen arbejder med 64-bit blokke og bruger en 128-bit nøgle. Chifferen blev vinderen blandt algoritmer, der krypterer 64-bit blokke ved den europæiske NESSIE konkurrence [3] [4] . Som et resultat af analysen af algoritmen udført inden for rammerne af denne konkurrence og før den, konkluderede eksperterne, at denne algoritme ikke har nogen alvorlige sårbarheder (de bemærkede specifikt, at det er strukturen af algoritmen med indlejrede Feistel-netværk, der komplicerer kryptoanalysen betydeligt). Lignende undersøgelser blev udført inden for rammerne af CRYPTREC-projektet om valg af kryptografiske algoritmer til e-forvaltningen i Japan. Projekteksperterne satte stor pris på MISTY1-algoritmen og konkluderede, at den har en høj margin for kryptografisk styrke, algoritmen har en høj krypteringshastighed og er meget effektiv til hardwareimplementering.

MISTY1 patenteret algoritme. Den oprindelige ejer af patentet, Mitsubishi Electric, har dog meddelt, at den vil give licens på brugen gratis. [5]

Algoritmestruktur

MISTY er udviklet som et kryptosystem, der i praksis kan bruges af en lang række applikationssystemer, for eksempel: software til at arbejde med smart cards eller i hurtige ATM-netværk. Derfor er MISTY1-algoritmen baseret på følgende tre principper:

Højt niveau af krypteringssikkerhed;
Hurtig eksekverbarhed på alle processorer på tidspunktet for oprettelse af algoritmen;
Hastigheden af hardwaren baseret på denne algoritme.

For at opfylde disse krav blev følgende krypteringsmetoder brugt i MISTY1-algoritmen:

logiske operationer. AND-, OR- og XOR-operationerne er de mest almindelige elementer i chifferalgoritmer. Selvom de ikke kan forventes at være meget sikre, er disse operationer hurtige og effektive i enhver hardware og er let implementeret i software.
Aritmetiske operationer. Kryptering med hardware introducerer forsinkelser og øger den tid, det tager at kryptere og overføre data. Krypteringstiden for operationer såsom addition, subtraktion og nogle gange multiplikation, for softwareorienterede cipherer, er dog helt i overensstemmelse med det foreslåede sikkerhedsniveau.
Skiftedrift. En hyppigt brugt operation i kryptosystemer, da den er billig og nem at implementere i hardware. Det er værd at bemærke, at softwareimplementeringen af skiftoperationen, for eksempel 32-bit ord, kan udføres ret langsomt på processorer med en lavere kapacitet.
Permutationstabeller. Sådanne operationer er krævende for hastigheden af hukommelsesadgang, hvilket bør tages i betragtning ved implementering af algoritmen i software. Hardwaren skal til gengæld optimeres til denne chiffer for at opfylde de forventede tidsbegrænsninger på behandling og transmission af information.

MISTY1-algoritmen har en meget usædvanlig struktur - den er baseret på "indlejrede" Feistel-netværk. Først opdeles en 64-bit krypteret datablok i to 32-bit underblokke, hvorefter der udføres r runder af følgende transformationer [6] :

Hver underblok behandles af FL-operationen (operationerne er beskrevet nedenfor). Dette trin udføres kun i ulige runder.
FO-operationen udføres på den underblok, der behandles.
Resultatet af disse operationer overlejres af en bitvis XOR-operation på den rå underblok.
Underblokke ombyttes. Efter den sidste runde behandles begge underblokke igen af FL-operationen.

Det anbefalede antal algoritmerunder er 8, men antallet af algoritmerunder kan også være alt større end 8 og et multiplum af fire.

Operation FL

FL-operationen er ret enkel. Underblokken, der behandles af den, er opdelt i to 16-bit fragmenter, hvorpå følgende handlinger udføres:

$R'=R\oplus (L\&KL_{{{\text{i,j,1)))))$

$L'=L\oplus (R'|KL_{{{\text{i,j,2))))))$

hvor:

L og R er inputværdierne for henholdsvis venstre og højre fragmenter;

L' og R' er udgangsværdier;

$KL_{{{\text{i,j,1))))$ og er fragmenter af den j-te undernøgle i den i-te runde for FL-funktionen (nøgleudvidelsesproceduren er beskrevet i detaljer nedenfor); $KL_{{{\text{i,j,2))))$

& og | - bitvise logiske operationer henholdsvis "og" og "eller".

Operation FO

FO-funktionen er mere interessant, fordi den er det indlejrede Feistel-netværk. I lighed med de foregående opdeler funktionen inputværdien i to 16-bit fragmenter, hvorefter 3 runder af følgende handlinger udføres:

XOR-operationen overlejrer det runde nøglefragment på det venstre fragment , hvor k er det runde tal for FO-funktionen. $KO_{{{\text{i,k))))$
Det venstre fragment behandles af FI-operationen.
Det venstre fragment er XORed med værdien af det højre fragment.
Fragmenter er byttet om.

Efter den tredje runde af FO-operationen overlejres et ekstra nøglefragment på det venstre fragment af XOR-operationen . $KO_{{{\text{i,4}}}}$

Operation FI

FI er også et Feistel-netværk, det vil sige, at dette allerede er det tredje niveau af rede. I modsætning til Feistel-netværkene på de to øverste niveauer er dette netværk ubalanceret: det behandlede 16-bit fragment er opdelt i to dele: 9-bit venstre og 7-bit højre. Derefter udføres 3 runder, som består af følgende:

Venstre side "køres" gennem udskiftningstabellen. 9-bit-delen (i runde 1 og 3) behandles af tabel S9, og 7-bit-delen (i runde 2) behandles af tabel S7. Tabeldataene er beskrevet nedenfor.
XOR-operationen overlejrer den aktuelle værdi af højre side på venstre side. I dette tilfælde, hvis der er en 7-bit del til højre, er den polstret med nuller til venstre, og to bits fjernes fra venstre for 9-bit delen.
I anden runde overlejrer XOR-operationen det runde nøglefragment på venstre side og fragmentet på højre side . I andre runder udføres disse handlinger ikke. $KI_{{{\tekst{i,k,1))))$ $KI_{{{\tekst{i,k,2))))$
Venstre og højre side er byttet om.

For klarhedens skyld er en 9-bit datastrøm fremhævet med fede linjer i figuren.

Tabel S7 og S9 i MISTY1-algoritmen kan implementeres både ved hjælp af beregninger og direkte af tabeller, der er gemt i krypteringsenhedens ikke-flygtige hukommelse. Ved implementering af algoritmen skal muligheden for at bruge tabeller vælges afhængigt af krypteringsenhedens ressourcer.

Nøgleudvidelse

Opgaven med nøgleudvidelsesproceduren er at danne følgende sæt nøglefragmenter, der bruges (til 8 runder af algoritmen):

20 nøglefragmenter ( ), som hver har en størrelse på 16 bit; $KL_{{{\text{i,j,m))))$ ${\text{i}}=1,3,5,7,9;1\leqslant {\text{j}}\leqslant 2;1\leqslant {\text{m}}\leqslant 2$
32 16-bit fragmenter ( ); $KO_{{{\text{i,k))))$ $1\leqslant {\text{i}}\leqslant 2;1\leqslant {\text{k}}\leqslant 4$
24 7-bit fragmenter (når , det vil sige i 4. runde af FO-funktionen, udføres FI-operationen ikke); $KI_{{{\tekst{i,k,1))))$ ${\text{k}}=4$
24 9-bit fragmenter . $KI_{{{\tekst{i,k,2))))$

Nøgleudvidelsesproceduren beregner således 1216 bit nøgleinformation fra 128-bit krypteringsnøglen i MISTY1-algoritmen. Denne beregning udføres som følger:

1. En 128-bit nøgle er opdelt i 8 fragmenter på hver 16 bit. $K_{{{\text{1}}}}...K_{{{\text{8}}}}$

2. Værdier dannes : Resultatet af at behandle værdien af FI-funktionen bruges som en nøgle (det vil sige, at sættet af nødvendige 7- og 9-bit fragmenter) bruger værdien (i det følgende, hvis indekset n for nøglefragmentet overstiger 8, og i stedet for det, indeks n-8). $K'_{{{\text{1}}}}...K'_{{{\text{8}}}}$ $K'_{{{\text{n))))$ $K_{{{\tekst{n))))$ $K'_{{{\text{n+1))))$

3. De nødvendige fragmenter af den udvidede nøgle "samles", efterhånden som transformationerne udføres fra arrays og i henhold til tabellerne nedenfor. $K_{{{\text{1}}}}...K_{{{\text{8}}}}$ $K'_{{{\text{1}}}}...K'_{{{\text{8}}}}$

Formål	$KO_{{{\text{i,1))))$	$KO_{{{\text{i,2))))$	$KO_{{{\text{i,3}}}}$	$KO_{{{\text{i,4}}}}$	$KI_{{{\text{i,1))))$	$KI_{{{\text{i,2))))$	$KI_{{{\text{i,3}}}}$
Fragment	$K_{{{\tekst{i))))$	$K_{{{\text{i+2))))$	$K_{{{\text{i+7))))$	$K_{{{\text{i+4))))$	$K'_{{{\text{i+5}}}}$	$K'_{{{\text{i+1))))$	$K'_{{{\text{i+3))))$

Formål	$KL_{{{\text{i,1,1))))$	$KL_{{{\text{i,2,1))))$	$KL_{{{\text{i,1,2))))$	$KL_{{{\text{i,2,2))))$
Fragment	$K_{{{\text{(i+1)/2))))$	$K'_{{{\text{(i+1)2+2))))$	$K'_{{{\text{(i+1)2+6))))$	$K_{{{\text{(i+1)/2+4))))$

4. Et 16-bit fragment er opdelt i et 7-bit fragment og et 9 -bit fragment . $KI_{{{\text{i,k))))$ $KI_{{{\tekst{i,k,1))))$ $KI_{{{\tekst{i,k,2))))$

Dekryptering

Dekryptering udføres ved at udføre de samme handlinger som for kryptering, men med følgende ændringer:

de udvidede nøglefragmenter bruges i omvendt rækkefølge,
i stedet for operationen FL bruges operationen omvendt til den (lad os betegne det FLI).

Skemaet for dekrypteringsproceduren er vist i figuren:

Operation FLI

FLI-operationen er defineret som følger:

$L'=L\oplus (R\&KL_{{{\text{i,j,2))))))$

$R'=R\oplus (L'|KL_{{{\text{i,j,1))))))$

Sikkerhed

MISTY1 blev udviklet baseret på teorien om "sikret sikkerhed" mod differentiel og lineær kryptoanalyse. Denne algoritme blev designet til at modstå forskellige kryptoangreb kendt på tidspunktet for oprettelsen.

Siden offentliggørelsen af misty er der blevet udført mange undersøgelser for at evaluere dets sikkerhedsniveau. Nogle af resultaterne fra forskning i tåget med færre runder er vist nedenfor.

Højordens differentiel krypteringsanalyse anvendes effektivt til lavgrads blokcifre. Misty indeholder 2 opslagstabeller S7 og S9, begge med lille annonce, henholdsvis 3 og 2. Derfor er en hel del artikler afsat til den differentielle kryptoanalyse af mysti. Det bedste resultat blev opnået for 5-niveaus algoritmen uden FL-funktioner. Det er dog tilstedeværelsen af FL-funktioner og wide-bit AND/OR-operationer i dem, der gør det meget vanskeligt at bruge højordens differentiel kryptoanalyse.

Umulig differentialanalyse gælder også for en blokskrifttype med samme undernøgleværdi i hver runde (eller hver n. runde). Og da MISTY1 har et ret simpelt nøgleudvidelsessystem, er det helt naturligt at overveje anvendeligheden af dette angreb på denne algoritme. Det bedste resultat for et sådant angreb blev også opnået, når man betragtede algoritmen uden FL-funktioner.

Chifferen blev vinderen blandt algoritmer, der krypterer 64-bit blokke ved den europæiske NESSIE konkurrence (2000-2003). Som et resultat af analysen af algoritmen udført inden for rammerne af denne konkurrence og før den, konkluderede eksperterne, at denne algoritme ikke har nogen alvorlige sårbarheder (de bemærkede specifikt, at det er strukturen af algoritmen med indlejrede Feistel-netværk, der komplicerer kryptoanalysen betydeligt).

Lignende undersøgelser blev udført inden for rammerne af CRYPTREC- projektet om valg af kryptografiske algoritmer til e-forvaltningen i Japan. Projekteksperterne satte stor pris på MISTY1-algoritmen og konkluderede, at den har en høj margin for kryptografisk styrke, algoritmen har en høj krypteringshastighed og er meget effektiv til hardwareimplementering.

Applikationer og ændringer

Der er en modifikation af denne algoritme - MISTY2 . Det har dog ikke vundet stor popularitet på grund af det lave niveau af kryptografisk styrke.

Også en modifikation af MISTY1, KASUMI- algoritmen, blev udbredt i 2000 og blev W-CDMA mobilkrypteringsstandarden.

Se også

Noter

↑ Mitsuru Matsui. "Blokkrypteringsalgoritme MISTY." Teknisk rapport fra IEICE ISEC96-11 (1996-07). (På japansk).
↑ アーカイブされたコピー(utilgængeligt link) . Hentet 23. marts 2005. Arkiveret fra originalen 22. marts 2005. (ubestemt)
↑ Arkiveret kopi . Hentet 3. maj 2009. Arkiveret fra originalen 13. oktober 2016. (ubestemt)
↑ NESSIE-konkurrence og MISTY1-algoritmen . Hentet 3. maj 2009. Arkiveret fra originalen 30. januar 2011. (ubestemt)
↑ IETF-udkast til TLS MISTY1 01 . Hentet 25. november 2011. Arkiveret fra originalen 30. marts 2012. (ubestemt)
↑ http://web.eecs.utk.edu/~dunigan/cs594-cns96/misty1spec.pdf

Litteratur

MITY1-specifikation [1]
MISTY1 Understøttende dokument [2]
3,36. Algoritmer MISTY1 og MISTY2 fra bogen “Encryption Algorithms. Særlig opslagsbog, Sergey Panasenko, 2009, ISBN 978-5-9775-0319-8

NESSIE (engelsk) . — NESSIES officielle hjemmeside.
Licenserklæring (engelsk) (downlink) . — MISTY1 Licenserklæring. Arkiveret fra originalen den 30. marts 2012.

Links

RFC 2994
Mitsubishi - Om MISTY
MISTY1 patenterklæring fra Mitsubishi
John Savards beskrivelse af MISTY
SCANs indlæg på MISTY1
CRYPTREC Rapport 2002; Rapport om evaluering af kryptografisk teknik (FY 2002)" - Detaljeret beskrivelse af algoritmen (link ikke tilgængelig) (eng.)
Vol.100/december 2002 Mitsubishi Electric ADVANCE
Understøttende dokument for MISTY1
Bloker chiffere: Sikkerhedsbeviser, krypteringsanalyse, design og fejlangreb (downlink )
Alex Biryukov. Blok-cifere og stream-cifre: The State of the Art

Symmetriske kryptosystemer
Stream-cifre	A3 A5 A8 Decim F-FCSR Korn HC-256 KCipher-2 MICKEY MUGI GEDD Phelix RC4 Kanin FORSEGLE SNE SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistel netværk	GOST 28147-89 (Magma) blæsefisk Camellia CAST-128 CAST-256 CIFERUNIKORN-A CIFERUNIKORN-E CLEFIA Cobra DEL DES DESX DFC E2 ENRUPT FEAL HPC IDE KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NyDES NDS RC5 RC6 FRØ Simon Sinople skipjack SM4 Speck TE XTEA XXTEA Raiden RTEA Triple DES To fisk
SP netværk	Græshoppe 3 vejs ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bælte CRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer til stede Regnbue SIKRERE HAJ FIRKANT Slange tre fisk
Andet	FRØ NUSH REDOC SC2000 SHACAL CS-Cipher