SEAL (kryptografický algoritmus)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. března 2014; kontroly vyžadují 9 úprav .

SEAL ( S oftware - optimized Encryption Algorithm , softwarově optimalizovaný šifrovací algoritmus) je algoritmus symetrického proudového šifrování dat optimalizovaný pro softwarovou implementaci.

Vyvinutý v IBM v roce 1993 Philem Rogawayem a Donem Coppersmithem . _ _ Algoritmus je optimalizován a doporučen pro 32bitové procesory . K provozu vyžaduje několik kilobajtů vyrovnávací paměti a osm 32bitových registrů . Rychlost šifrování je přibližně 4 strojové cykly na bajt textu. Pro kódování a dekódování se používá 160bitový klíč . Aby se předešlo nežádoucí ztrátě rychlosti v důsledku pomalých operací zpracování klíčů , SEAL na něm předem provede několik transformací, což vede ke třem tabulkám určité velikosti. Místo samotného klíče se tyto tabulky používají přímo k šifrování a dešifrování textu.

Algoritmus je považován za velmi spolehlivý, velmi rychlý [1] a od prosince 1993 je chráněn patentem USA č. 5454039 [2] .

Historie

V roce 1991 Ralph C. Merkle popsal nákladovou efektivitu softwarových šifer . Podle jeho názoru nejúčinnější z nich byly Khufu , FEAL a RC4 . Stále se zvyšující potřeby zákazníků po spolehlivé kryptografii však vyžadovaly hledání nových a zdokonalování starých řešení.

V létě 1992 byl zahájen vývoj první verze nového softwarově optimalizovaného algoritmu SEAL 1.0 . Hlavní myšlenky a princip fungování vývojáři převzali z blokové šifry Ralph Merkle ( ang. Ralph C. Merkle ) Khufu , která se jim v té době zdála nejdokonalejší. Rozhodli se dosáhnout nejlepších vlastností projektu (hlavně rychlosti) a zúžili rozsah zařízení , na kterých je jeho realizace možná. Volba byla učiněna ve prospěch 32bitových strojů s alespoň osmi obecnými registry a mezipamětí o velikosti alespoň 8 KB . V březnu 1993 bylo rozhodnuto vytvořit blokovou šifru , ale struktura z rodiny pseudonáhodných funkcí vyvinutá do října téhož roku fungovala rychleji, což vedlo vývojáře k streamování šifrování .

Tato struktura se skládala ze čtyř registrů , z nichž každý měnil svého „souseda“ v závislosti na tabulce získané z klíče . Po řadě takových úprav se hodnoty registru přidají do sekvence klíčů, která s každou iterací roste, dokud nedosáhne určité délky.

Při vývoji byla téměř veškerá pozornost věnována vnitřní smyčce algoritmu , protože procedura inicializace registru a způsob generování tabulek z klíče měly malý vliv na jeho bezpečnost. Ve své finální podobě se projekt SEAL 1.0 objevil až v prosinci 1993 .

V roce 1996 Helen Handschuh a Henri Gilbert SEAL 1.0 a na samotný SEAL 1.0. Potřebovali texty, každé čtyři 32bitová slova, aby našli závislost pseudonáhodné funkce na klíči . V důsledku toho byla provedena některá vylepšení a změny v dalších verzích algoritmu SEAL 3.0 a SEAL 2.0 . Například ve verzi 1.0 končila každá iterace s klávesovou sekvencí úpravou pouze dvou registrů a ve verzi 3.0 byly upraveny všechny čtyři. SEAL 3.0 a SEAL 2.0 také používaly algoritmus SHA-1 ( Secure Hash Algorithm-1 ) ke generování tabulek namísto původního SHA , díky čemuž byly odolnější vůči kryptoanalýze . $2^{30}$

Popis

Při popisu algoritmu se používají následující operace a zápisy:

čísla hexadecimální číselné soustavy začínají znaky "0x" a v záznamu používají kromě desetinných číslic i znaky "a" , "b" , "c" , "d" , "e" a "f" , která označují desetinná čísla od 10 do 15 ;
pod výrazem Yt je třeba rozumět cyklický posun registru Y doprava o t bitů ; $\ggg$
pod výrazem Yt je třeba rozumět cyklický posun registru Y doleva o t bitů ; $\já budu$
operace X Y znamená bitové logické násobení ( anglicky AND ) registrů X a Y ; $\A$
operace X Y znamená bitové logické sčítání ( anglicky OR ) registrů X a Y ; $\lor$
operace X Y znamená bitové sčítání modulo 2 ( anglicky XOR ) registry X a Y ; $\oplus$
pod X Y je třeba rozumět zřetězení ( anglicky concatenation ) registrů X a Y ; $\lVert$
výraz lichý (X) označuje logickou funkci argumentu X , která se vyhodnotí jako PRAVDA ( angl. TRUE ) pouze v případě, že X je sudé číslo .

Vytváření šifrovacích tabulek z klíče

Aby se předešlo ztrátě rychlosti šifrování při pomalých operacích, používá algoritmus tři tabulky: R , S a T . Tyto tabulky jsou vypočteny pomocí procedury z algoritmu SHA-1 a závisí pouze na klíči . Plnění těchto tabulek lze popsat pomocí funkce G , která vrací 160bitovou hodnotu ze 160bitového řetězce a 32bitového čísla . $A$ $i$ $G_{a}(i)$

Zavádíme následující funkce a proměnné v závislosti na indexu : $t$

nainstalovat a _ $0\leq t\leq 19$ $K_{t}={\mbox{0x}}5a827999$ $f_{t}(B,C,D)=(B\A C)\lor (B\A D);$
nainstalovat a _ $20\leq t\leq 39$ $K_{t}={\mbox{0x}}6ed9eba1$ $f_{t}(B,C,D)=B\oplus C\oplus D;$
nainstalovat a _ $40\leq t\leq 59$ $K_{t}={\mbox{0x}}8f1bbcdc$ $f_{t}(B,C,D)=(B\A C)\lor (B\A D)\lor (C\A D);$
nainstalovat a _ $60\leq t\leq 79$ $K_{t}={\mbox{0x}}ca62c1d6$ $f_{t}(B,C,D)=B\oplus C\oplus D.$

160bitový řetězec je pak rozdělen do pěti 32bitových slov, takže $A$ $a=H_{0}\lVert H_{1}\lVert H_{2}\lVert H_{3}\lVert H_{4}.$

Je také vytvořeno šestnáct 32bitových slov $W_{0}=i,~~W_{1}=W_{2}=...=W_{15}=0^{32}.$

Poté se provedou konečné výpočty:

${\mbox{For}}~t=16~{\mbox{to}}~79~{\mbox{do}}~W_{t}=(W_{t-3}\oplus W_{t -8}\oplus W_{t-14}\oplus W_{t-16})\lll 1;$
$A=H_{0};~B=H_{1};~C=H_{2};~D=H_{3};~E=H_{4};$
${\mbox{For}}~t=0~{\mbox{to}}~79~{\mbox{do}}$ ${\mbox{TEMP}}=A\lll 5+f_{t}(B,C,D)+E+W_{t}+K_{t};$ $E=D;~D=C;~C=B\lll 30;~B=A;~A=TEMP;$
$H_{0}=H_{0}+A;~H_{1}=H_{1}+B;~H_{2}=H_{2}+C;~H_{3}=H_{3 }+D;H_{4}=H_{4}+E;$
$G_{a}(i)=H_{0}\lVert H_{1}\lVert H_{2}\lVert H_{3}\lVert H_{4}.$

Představujeme funkci where for ${\displaystyle \Gamma _{a}(i)=H_{i~mod~5}^{i))$ $H_{0}^{5j}\lVert H_{1}^{5j+1}\lVert H_{2}^{5j+2}\lVert H_{3}^{5j+3}\lVert H_ {4}^{5j+4}=G_{a}(j)$ $j={\mathcal {b}}i/5{\mathcal {c}}.$

Pak tabulky:

$T[i]=\Gamma _{a}(i),~~0\leq i<512;$

$S[j]=\Gamma _{a}({\mbox{0x}}1000+j),~~0\leq j<256;$

$R[k]=\Gamma _{a}({\mbox{0x}}2000+k),~~0\leq k<256.$

Dále se klíč v algoritmu nepoužívá. $A$

Inicializace servisních registrů

Před generováním pseudonáhodné funkce je třeba připravit čtyři 32bitové servisní registry ( , , a ) a čtyři 32bitová slova ( , , a ). Jejich hodnoty jsou určeny z tabulek a , 32bitového čísla a nějakého čísla v následujícím postupu. $A$ $B$ $C$ $D$ $n_{1}$ $n_{2}$ ${\displaystyle n_{3))$ $n_{4}$ $R$ $T$ $n$ $l$

${\mbox{procedure}}~{\mbox{Initialize}}~(n,l,A,B,C,D,n_{1},n_{2},n_{3},n_{4 })$

A\leftarrow n\oplus R[4l];

B\leftarrow (n\ggg 8)\oplus R[4l+1];

C\leftarrow (n\ggg 16)\oplus R[4l+2];

D\leftarrow (n\ggg 24)\oplus R[4l+3];

${\mbox{for}}~j\leftarrow 1~{\mbox{to}}~2~{\mbox{do}}$

P\leftarrow A\And {\mbox{0x}}7fc;~~B\leftarrow B+T[P/4];~~A\leftarrow A\ggg 9;

P\leftarrow B\And {\mbox{0x}}7fc;~~C\leftarrow C+T[P/4];~~B\leftarrow B\ggg 9;

P\leftarrow C\And {\mbox{0x}}7fc;~~D\leftarrow D+T[P/4];~~C\leftarrow C\ggg 9;

P\leftarrow D\And {\mbox{0x}}7fc;~~A\leftarrow A+T[P/4];~~D\leftarrow D\ggg 9;

$(n_{1},n_{2},n_{3},n_{4})\leftarrow (D,B,A,C);$

P\leftarrow A\And {\mbox{0x}}7fc;~~B\leftarrow B+T[P/4];~~A\leftarrow A\ggg 9;

P\leftarrow B\And {\mbox{0x}}7fc;~~C\leftarrow C+T[P/4];~~B\leftarrow B\ggg 9;

P\leftarrow C\And {\mbox{0x}}7fc;~~D\leftarrow D+T[P/4];~~C\leftarrow C\ggg 9;

P\leftarrow D\And {\mbox{0x}}7fc;~~A\leftarrow A+T[P/4];~~D\leftarrow D\ggg 9;

Vytvoření pseudonáhodné funkce

Pro šifrování textu je potřeba vytvořit pseudonáhodnou funkci.

${\mbox{function}}~{\mbox{SEAL}}~(a,n,L)$

$y=0^{L};$

${\mbox{for}}~l\leftarrow 0~{\mbox{to}}~\infty ~{\mbox{do}}$

${\mbox{Initialize}}~(n,l,A,B,C,D,n_{1},n_{2},n_{3},n_{4});$

${\mbox{for}}~i\leftarrow 1~{\mbox{to}}~64~{\mbox{do}}$

$P\leftarrow A\And {\mbox{0x}}7fc;~~B\leftarrow B+T[P/4];~~A\leftarrow A\ggg 9;~~B\leftarrow B\oplus A;$

$Q\leftarrow B\And {\mbox{0x}}7fc;~~C\leftarrow C\oplus T[Q/4];~~B\leftarrow B\ggg 9;~~C\leftarrow C+ B ;$

$P\leftarrow (P+C)\And {\mbox{0x}}7fc;~~D\leftarrow D+T[P/4];~~C\leftarrow C\ggg 9;~~D\ šipka doleva D\oplus C;$

$Q\leftarrow (Q+D)\And {\mbox{0x}}7fc;~~A\leftarrow A\oplus T[Q/4];~~D\leftarrow D\ggg 9;~~A \leftarrow A+D;$

$P\leftarrow (P+A)\And {\mbox{0x}}7fc;~~B\leftarrow B\oplus T[P/4];~~A\leftarrow A\ggg 9;$

$Q\leftarrow (Q+B)\And {\mbox{0x}}7fc;~~C\leftarrow C+T[Q/4];~~B\leftarrow B\ggg 9;$

$P\leftarrow (P+C)\And {\mbox{0x}}7fc;~~D\leftarrow D\oplus T[P/4];~~C\leftarrow C\ggg 9;$

$Q\leftarrow (Q+D)\And {\mbox{0x}}7fc;~~A\leftarrow A+T[Q/4];~~D\leftarrow D\ggg 9;$

$y\leftarrow y~\lVert ~B+S[4i-4]~\lVert ~C\oplus S[4i-3]~\lVert ~D+S[4i-2]~\lVert ~A\ plus S[4i-1];$

${\mbox{if}}~|y|\geq L~{\mbox{then}}~{\mbox{return}}~~y_{0}y_{1}...y_{L- jeden};$

${\mbox{if}}~odd(i)~{\mbox{then}}~(A,B,C,D)\leftarrow (A+n_{1},B+n_{2}, C\oplus n_{1},D\oplus n_{2});$

${\mbox{else}}~(A,B,C,D)\leftarrow (A+n_{3},B+n_{4},C\oplus n_{3},D\oplus n_{ čtyři});$

Proces šifrování se skládá z velkého počtu iterací , z nichž každá končí vygenerováním pseudonáhodné funkce . Počet prošlých iterací ukazuje počítadlo l . Všechny jsou rozděleny do několika fází s podobnými operacemi. V každé fázi je horních 9 bitů jednoho z registrů ( A , B , C nebo D ) použito jako ukazatel , kterým se vybírá hodnota z tabulky T. Tato hodnota se přičte aritmeticky nebo bitově modulo 2 (XOR) s dalším registrem (opět jedním z A , B , C nebo D ). První vybraný registr se poté otočí doprava o 9 pozic. Dále se buď upraví hodnota druhého registru sčítáním nebo XOR s obsahem prvního (již posunutým) a provede se přechod do dalšího stupně, nebo se tento přechod provede ihned. Po 8 takových kolech se hodnoty A , B , C a D sečtou (aritmeticky nebo XORed ) s určitými slovy z tabulky S a přidají se k posloupnosti kláves y . Posledním krokem iterace je přidání dalších 32bitových hodnot ( n1 , n2 nebo n3 , n4 ) do registrů . Navíc výběr konkrétní hodnoty závisí na paritě čísla této iterace .

Vlastnosti a praktické použití

Při vývoji tohoto algoritmu byla hlavní pozornost věnována následujícím vlastnostem a nápadům:

použití velké (asi 2 kB ) tabulky T získané z velkého 160bitového klíče ;
střídání aritmetických operací (sčítání a bitové XOR );
použití vnitřního stavu systému, který se explicitně neobjevuje v datovém toku (hodnoty n1 , n2 , n3 a n4 , které mění registry na konci každé iterace );
použití operací, které se od sebe liší v závislosti na fázi iterace a jejím počtu.

Šifra SEAL vyžaduje asi čtyři strojové cykly k zašifrování a dešifrování každého bajtu textu . Běží rychlostí přibližně 58 Mb/s na 32bitovém 50 MHz procesoru a je jednou z nejrychlejších šifer na trhu .

Poznámky

↑ P.Rogaway , D.Coppersmith . Softwarově optimalizovaný šifrovací algoritmus . — 1998.
↑ Patent USA 5 454 039 „Softwarově efektivní pseudonáhodná funkce a její použití pro šifrování“

Zdroje

Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M .: Triumf, 2002. - S. 446-448. — 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
P.Rogaway , D.Coppersmith . Softwarově optimalizovaný šifrovací algoritmus . — 1998.
Helen Handshuh , H. Gilbert -Kryptoanalýza šifrovacího algoritmu SEAL. — 1997. $X^{2}$

Odkazy

Patent USA 5 675 652 „Počítačově čitelné zařízení implementující softwarově efektivní šifrování pseudonáhodné funkce“
Neoficiální implementace algoritmu SEAL 3.0 v C Archivováno 5. března 2016 na Wayback Machine
Neoficiální implementace algoritmu SEAL 3.0 v Delphi Archivováno 4. března 2016 na Wayback Machine

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) nafukovací ryba Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher