Täiustatud krüpteerimisstandard

Täiustatud krüpteerimisstandard (lühend AES; inglise keeles Advanced Encryption Standard) on 2001. aastal Ameerika Ühendriikide Riikliku Standardite ja Tehnoloogia Instituudi (National Institute of Standards and Tehnology ehk NIST) defineeritud krüpteerimisstandard, mis kasutab ühte võtit nii krüpteerimiseks kui ka dekrüpteerimiseks. Standardis kasutatakse algoritmi Rijndael.

Rijndaeli autorid on belglastest arvutitehnikud Vincent Rijmen ja Joan Daemen.

Täiustatud krüpteerimisstandardi puhul töötleb Rijndaeli algoritm 128-bitiseid andmeplokke 128-, 192- või 256-bitise võtmega. Teisi Rijndaeli algoritmi ploki-või võtmesuuruseid AES ei luba. Andmeplokkide ja võtmete bitid on jaotatud baitideks. Seega koosneb 128-bitine andmeplokk või võti 16-st, 192-bitine võti 24-st ja 256-bitine võti 32-st baidist. Kui krüpteeritavad andmed on suuremad kui üks 16-baidine andmeplokk, siis ülejäänud andmed mahutatakse järgmistesse 16-baidistesse plokkidesse. Võib ka juhtuda, et krüpteeritav info on väiksem kui 128 bitti. Sellisel juhul täidetakse tühjad kohad nullidega.

AESi valimine

1997. aasta 2. jaanuaril kuulutas NIST välja AES konkursi täiustatud krüpteerimisalgoritmi leidmiseks. NISTi eesmärgiks oli kirjeldada salastamata krüpteerimisalgoritm, mis oleks võimeline kaitsma riikliku tähtsusega andmeid. Tööde esitamise tähtajaks oli konkursile laekunud 15 nõuetele vastavat algoritmi. Võitja valimisel arvestati krüpteerimisalgoritmi turvalisust, maksumust ja loogika olemust. Pärast mitut testimis- ja valimisvooru valiti kõige sobivamaks algoritmiks kahe belglasest arvutitehniku välja töötatud Rijndael.

Konkursi ajakava

2. jaanuaril 1997 kuulutas NIST välja AES konkursi täiustatud krüpteerimisalgoritmi leidmiseks.
15. aprillil 1997 toimus arutelu, mille käigus vaadati üle AESi nõuded, kriteeriumid ning kandidaatide vastuvõtutingimused.
12. septembril 1997 väljastati NISTi poolt kutse algoritmide esitamiseks.
15. juuni 1998 kuulutati välja 15 kriteeriumitele vastavat algoritmi.
22–23. märtsil 1999 vaadati üle kandidaatidele tehtud analüüside tulemused.
9. augustil 1999 kuulutati välja 5 finalisti.
13–14. aprillil 2000 kaitsesid viis finalisti oma algoritme.
2. oktoobril 2000 teatati konkursi võitja.
26. novembril 2001 avaldati FIPS-197.

Konkursi hindamiskriteeriumid

Turvalisus (kõige tähtsam hindamiskriteerium):
- algoritmi turvalisus võrrelduna teiste kandideerivate algoritmidega;
- kui suurel määral on algoritmi väljundandmetes eristamatu sisendisse saadetud juhuslik permutatsioon;
- algoritmi matemaatiline usaldatavus;
- valimisprotsessi käigus avalikkuse poolt välja toodud tegurid.
Maksumus:
- nõuded litsentsile (algoritm peab olema kõigile kättesaadav);
- arvutuslik efektiivsus;
- nõudmised mälule.
Algoritm ja selle rakendamise karakteristika:
- paindlikkus;
- ühilduvus riist- ja tarkvaraga;
- lihtsus.

Kandidaatide tabel

Algoritm	Staatus	Autorid
Rijndael	Võitja	Vincent Rijmen, Joan Daemen
MARS	Finalist	Carolynn Burwick, Don Coppersmith, Edward D'Avignon, Rosario Gennaro, Shai Halevi, Charanjit Jutla, Stephen M. Matyas, Luke O'Connor, Mohammad Peyravian, David Safford, Nevenko Zunic
RC6	Finalist	Ron Rivest, Matt Robshaw, Ray Sidney, Yiqun Lisa Yin
Serpent	Finalist	Ross Anderson, Eli Biham, Lars Knudsen
Twofish	Finalist	Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson
CAST-256	Kandidaat	Carlisle Adams, Stafford Tavares, Howard Heys, Michael Wiener
CRYPTON	Kandidaat	Chae Hoon Lim
DEAL	Kandidaat	Lars Knudsen
DFC	Kandidaat	Henri Gilbert, Marc Girault, Philippe Hoogvorst, Fabrice Noilhan, Thomas Pornin, Guillaume Poupard, Jacques Stern, Serge Vaudenay
E2	Kandidaat	Masayuki Kanda, Shiho Moriai, Kazumaro Aoki, Hiroki Ueda, Miyako Ohkubo, Youichi Takashima, Kazuo Ohta, Tsutomu Matsumoto
FROG	Kandidaat	Dianelos Georgoudis, Damian Leroux, Billy Simón Chaves
HPC	Kandidaat	Richard Schroeppel
LOKI97	Kandidaat	Lawrence Brown, Josef Pieprzyk, Jennifer Seberry
MAGENTA	Kandidaat	Michael Jacobson Jr., Klaus Huber
SAFER+	Kandidaat	James Massey, Gurgen Khachatrian, Melsik Kuregian

AESi turvalisus

Täiustatud krüpteerimisalgoritm töötab kas 128-, 192- või 256-bitise võtmega. 128-bitise võtme puhul on erinevate võimalike võtmekombinatsioonide arv $2^{128}$ . Selline võtmepikkus tähendab, et jõumeetodil 128-bitise võtme leidmiseks kuluv aeg, kasutades kahendarvudel töötavat superarvutit, on võrreldav kogu teadaoleva universumi eksisteerimise ajaga. Kui kasutada võtmeid pikkusega 192 või 256 bitti on ka kõikvõimalike võtmekombinatsioonide arv vastavalt $2^{192}$ või $2^{256}$ .

AESi kasutusvaldkonnad

Täiustatud krüpteerimisstandardit võib kasutada tarkvaras, püsivaras, riistvaras ja nende erinevates kombinatsioonides. Tavainimene, kes teadlikult krüptograafiaga ei tegele, puutub AESiga kokku nii WPA2 ruuteri, kuid ka erinevate programmide nagu 7-zip ja WinZip, kasutamisel.

AES algoritmi kirjeldus

Krüpteerimiseks ja dekrüpteerimiseks kopeeritakse sisendandmed olekumassiivi. Edasi rakendatakse olekumassiivile korduvalt nelja erinevat andmemuundamise tehnikat: baidi asendamine, rea nihutamine, veergude segamine, vooruvõtme lisamine. Krüpteerimise ja dekrüpteerimise puhul kasutatakse samu tehnikaid, kuid vastupidistes järjestustes. Andmemuundamise tehnikate rakendamise täpne tsüklite arv sõltub krüpteerimisvõtme pikkusest. 128-bitise võtme puhul läbitakse tsüklit 10, 192-bitise võtme puhul 12 ja 256-bitise võtme puhul 14 korda. Igaks järgnevaks tsükliks muudab Rijandaeli algoritm eelnevas tsüklis kasutatud vooruvõtit. Seda kutsutakse ka võtme laiendamiseks.

AESi etappide järjestus 128-bitise võtmega krüpteerimisel ja dekrüpteerimisel

16-baidise võtme puhul läbitakse neljast andmemuundamise tehnikast koosnevat tsüklit 9 korda. Enne esimest tsüklit XORitakse esialgne andmeplokk algoritmi poolt muutmata võtmega. Kümnendal korral jäetakse välja veergude segamise samm, kuna vastasel juhul ei oleks võimalik algseid andmeid dekrüpteerimisel kätte saada. Dekrüpteerimisel läbitakse tsükleid tagurpidises järjestuses. Seega on 16-baidise võtme puhul läbitavate tsüklite arv nii krüpteerimisel kui dekrüpteerimisel 10.

Järjestus krüpteerimisel:

Tsükli number	Vooruvõtme lisamine	Baidi asendamine	Rea nihutamine	Veergude segamine
0	Toimub esimesena	Ei toimu	Ei toimu	Ei toimu
1–9	Toimub neljandana	Toimub esimesena	Toimub teisena	Toimub kolmandana
10	Toimub kolmandana	Toimub esimesena	Toimub teisena	Ei toimu

Järjestus dekrüpteerimisel:

Tsükli number	Vooruvõtme lisamine	Baidi asendamine	Rea nihutamine	Veergude segamine
0	Toimub esimesena	Ei toimu	Ei toimu	Ei toimu
1–9	Toimub kolmandana	Toimub teisena	Toimub esimesena	Toimub neljandana
10	Toimub kolmandana	Toimub teisena	Toimub esimesena	Ei toimu

AESi etappide järjestus 192-bitise võtmega krüpteerimisel ja dekrüpteerimisel

24-baidise võtme kasutamine erineb 16-baidise võtmega krüpteerimisest ja dekrüpteerimisest tsüklite arvu poolest. Tsükleid läbitakse 12 korda nii krüpteerimisel kui dekrüpteerimisel.

Järjestus krüpteerimisel:

Tsükli number	Vooruvõtme lisamine	Baidi asendamine	Rea nihutamine	Veergude segamine
0	Toimub esimesena	Ei toimu	Ei toimu	Ei toimu
1–11	Toimub neljandana	Toimub esimesena	Toimub teisena	Toimub kolmandana
12	Toimub kolmandana	Toimub esimesena	Toimub teisena	Ei toimu

Järjestus dekrüpteerimisel:

Tsükli number	Vooruvõtme lisamine	Baidi asendamine	Rea nihutamine	Veergude segamine
0	Toimub esimesena	Ei toimu	Ei toimu	Ei toimu
1–11	Toimub kolmandana	Toimub teisena	Toimub esimesena	Toimub neljandana
12	Toimub kolmandana	Toimub teisena	Toimub esimesena	Ei toimu

AESi etappide järjestus 256-bitise võtmega krüpteerimisel ja dekrüpteerimisel

32-baidise võtme kasutamine erineb 16-baidise ja 24-baidise võtmega krüpteerimisest ja dekrüpteerimisest tsüklite arvu poolest. 256-bitise võtmega krüpteerimisel ja dekrüpteerimisel on läbitavaid tsükleid 14.

Järjestus krüpteerimisel:

Tsükli number	Vooruvõtme lisamine	Baidi asendamine	Rea nihutamine	Veergude segamine
0	Toimub esimesena	Ei toimu	Ei toimu	Ei toimu
1–13	Toimub neljandana	Toimub esimesena	Toimub teisena	Toimub kolmandana
14	Toimub kolmandana	Toimub esimesena	Toimub teisena	Ei toimu

Järjestus dekrüpteerimisel:

Tsükli number	Vooruvõtme lisamine	Baidi asendamine	Rea nihutamine	Veergude segamine
0	Toimub esimesena	Ei toimu	Ei toimu	Ei toimu
1–13	Toimub kolmandana	Toimub teisena	Toimub esimesena	Toimub neljandana
14	Toimub kolmandana	Toimub teisena	Toimub esimesena	Ei toimu

Võtme laiendamine

Krüpteerimistsükli esimesel läbimisel kasutatakse muutmata krüpteerimisvõtit. Igas järgnevas tsüklis kasutatakse esialgsest võtmest saadud muudetud võtmeversiooni ehk vooruvõtit. Vooruvõtmeid võib nimetada ka esialgse võtme laiendusteks. Uue vooruvõtme saamiseks tuleb eelmise tsükli võtit muuta, kasutades asendus- ja rotatsioonimeetodeid ning ringkonstanti.

Baidi asendamine

Lähteandmete arusaadavuse vähendamiseks asendatakse olekumaatriksi baidid asendusmaatriksist (S-box) võetud baitidega. S-box on AESi puhul 16x16 tabel, mis sisaldab asendusbaite kõigile kahekohalistele kuueteistkümnendsüsteemi arvudele. Ühekohalist kuueteistkümnendsüsteemi arvu on võimalik edastada nelja biti ehk poole baidiga. Andmete esitus kuueteistkümnendsüsteemis muudab kirjapildi lühemaks ning teeb info inimsilmale loetavamaks.

Rea nihutamine

Rea nihutamise etapis nihutatakse neljarealise olekumaatriksi viimast kolme rida. Rea elementide edasiliigutamiste arv sõltub selle rea paiknemiskohast maatriksis. Maatriksist välja lükatud arv paigutatakse nihkest tekkinud tühjale kohale. Teist rida liigutatakse ühe, kolmandat kahe ja neljandat kolme koha võrra. Esimest rida ei liigutata. Krüpteerimise käigus toimub nihe vasakule.

Veergude segamine

Veergude segamine on AESi puhul matemaatiliselt kõige keerulisem protsess. Lihtsustamiseks kasutatakse selles etapis kahte otsingutabelit, mille abil on võimalik kiiremini leida vajaminevate korrutiste tulemusi.

Vooruvõtme lisamine

Vooruvõti lisatakse olekumaatriksile lihtsa bitwise XOR tehtega. Tehet teostatakse veergudena. Iga olekumaatriksi veerg XORitakse vastava võtmemaatriksi veeruga.

Viited

↑ "AES Information". AES Crypt. Vaadatud 20.09.2014. ^{[alaline kõdulink]}
1 2 3 4 5 6 7 "AES" (PDF). NIST. Originaali (PDF) arhiivikoopia seisuga 7.04.2015. Vaadatud 20.09.2014.
↑ "U.S. Selects a New Encryption Technique". NYTimes. Vaadatud 20.09.2014.
1 2 3 4 5 6 7 8 9 10 11 "Advanced Encryption Standard by Example" (PDF). Adam Berent. Originaali (PDF) arhiivikoopia seisuga 27.03.2014. Vaadatud 4.10.2014.
1 2 3 4 "AES: the Advanced Encryption Standard". Cryptographic competitions. Vaadatud 4.10.2014.
↑ "TENTATIVE TIMELINE OF THE DEVELOPMENT OF NEW HASH FUNCTIONS". nist. Originaali arhiivikoopia seisuga 4.06.2009. Vaadatud 5.10.2014.
↑ "AES encryption is cracked". theinquirer. Originaali arhiivikoopia seisuga 5.10.2014. Vaadatud 4.10.2014.
↑ "How secure is AES against brute force attacks?". eetimes. Vaadatud 4.10.2014.
↑ "7z Format". 7zip. Vaadatud 4.10.2014.
↑ "AES Encryption Information: Encryption Specification AE-1 and AE-2". WINZIP. Vaadatud 4.10.2014.
↑ [www.speedguide.net/faq/wpa2-tkip-or-aes-encryption-331 "WPA2 TKIP or AES encryption ?"]. speedguide. Vaadatud 4.10.2014. {{cite web}}: kontrolli parameetri |url= väärtust (juhend)
↑ "Biclique Cryptanalysis of the Full AES" (PDF). Andrey Bogdanov, Dmitry Khovratovich, Christian Rechberger. Originaali (PDF) arhiivikoopia seisuga 6.03.2016. Vaadatud 21.09.2014.
↑ "Round Constant in AES". ansbro. Originaali arhiivikoopia seisuga 6.10.2014. Vaadatud 4.10.2014.
1 2 "s-box". samiam. Vaadatud 21.09.2014.
↑ "Hexadecimal Numbers". electronics-tutorials. Vaadatud 21.09.2014.
↑ "Binary and hexadecimal conversions". computerhope. Vaadatud 21.09.2014.

[AESCrypt-1] "AES Information". AES Crypt. Vaadatud 20.09.2014. ^{[alaline kõdulink]}

[NIST-2] 1 2 3 4 5 6 7 "AES" (PDF). NIST. Originaali (PDF) arhiivikoopia seisuga 7.04.2015. Vaadatud 20.09.2014.

[NYTimes-3] "U.S. Selects a New Encryption Technique". NYTimes. Vaadatud 20.09.2014.

[AESexample-4] 1 2 3 4 5 6 7 8 9 10 11 "Advanced Encryption Standard by Example" (PDF). Adam Berent. Originaali (PDF) arhiivikoopia seisuga 27.03.2014. Vaadatud 4.10.2014.

[voistlus-5] 1 2 3 4 "AES: the Advanced Encryption Standard". Cryptographic competitions. Vaadatud 4.10.2014.

[voistlus2-6] "TENTATIVE TIMELINE OF THE DEVELOPMENT OF NEW HASH FUNCTIONS". nist. Originaali arhiivikoopia seisuga 4.06.2009. Vaadatud 5.10.2014.

[cracked-7] "AES encryption is cracked". theinquirer. Originaali arhiivikoopia seisuga 5.10.2014. Vaadatud 4.10.2014.

[bruteforce-8] "How secure is AES against brute force attacks?". eetimes. Vaadatud 4.10.2014.

[7zip-9] "7z Format". 7zip. Vaadatud 4.10.2014.

[winzip-10] "AES Encryption Information: Encryption Specification AE-1 and AE-2". WINZIP. Vaadatud 4.10.2014.

[vs-11] [www.speedguide.net/faq/wpa2-tkip-or-aes-encryption-331 "WPA2 TKIP or AES encryption ?"]. speedguide. Vaadatud 4.10.2014. {{cite web}}: kontrolli parameetri |url= väärtust (juhend)

[fullAES-12] "Biclique Cryptanalysis of the Full AES" (PDF). Andrey Bogdanov, Dmitry Khovratovich, Christian Rechberger. Originaali (PDF) arhiivikoopia seisuga 6.03.2016. Vaadatud 21.09.2014.

[ansbro-13] "Round Constant in AES". ansbro. Originaali arhiivikoopia seisuga 6.10.2014. Vaadatud 4.10.2014.

[samiam-14] 1 2 "s-box". samiam. Vaadatud 21.09.2014.

[hex-15] "Hexadecimal Numbers". electronics-tutorials. Vaadatud 21.09.2014.

[hex2-16] "Binary and hexadecimal conversions". computerhope. Vaadatud 21.09.2014.