Advanced Encryption Standard (AES) je specifikacija za šifrovanje podataka usvojena 2001. godine od strane Nacionalnog instituta za standarde i tehnologiju SAD-a (National Institute of Standards and Technology). Konkurs za izbor algoritma je trajao od 1997. do 2000. godine kada je izabran Rijndael algoritam. Rijndael je blokovski algoritam za šifrovanje podataka pomoću simetričnog ključa. Veličina bloka i ključa su promenljivi. Ona može biti bilo koji broj bitova od 128 do 256 koji je deljiv sa 32. Za AES su izabrane varijante Rijndael algoritma kod kojih je veličina bloka i ključa 128, 192 ili 256 bitova.

Uvod

AES je blokovski algoritam za šifrovanje što znači da jedan poziv algoritma šifruje jedan blok. U slučaju AES-128 šifruje se 16 bajtova odjednom. To znači da za podatak od 16MB bi trebalo da izvršimo algoritam milion puta. Očigledno je da vreme izvršavanja linearno raste sa povećanjem veličine podataka. Ali možemo uočiti da je svako šifrovanje nekog bloka nezavisno od ostalih pa se šifrovanje lako može paralelizovati. Višenitna implementacija ovog algoritma bi donela neko ubrzanje u zavisnosti od broja jezgara procesora. Još veće ubrzanje bi postigli implementacijom algoritma za grafičke procesore koji danas imaju i više od 1000 jezgara.

Napravićemo implementaciju AES-128 algoritma za CPU, a zatim je podesiti za rad na Nvidia CUDA platformi i uporediti njihove performanse za različite veličine ulaznih podataka.

Opis algoritma

AES-128 algoritam radi sa ulaznim podacima (dužine 16 bajtova) kao sa matricom dimenzija 4×4 koja se naziva stanjem. To stanje prolazi kroz 10 rundi u kojima se na njega primenjuju 4 različite transformacije. To su SubBytes, ShiftRows, MixColumns i AddRoundKey.

• SubBytes – Svaki element stanja zamenjuje sa odgovarajućom vrednošću iz S-box tabele u odnosu na trenutnu vrednost elementa. S-box je unapred izračunata tabela koju čuvamo kao konstantan niz od 256 bajtova.

• ShiftRows – Ciklično rotira poslednje tri vrste matrice stanja. Drugu vrstu za jedan, treću za dva i četvrtu za tri elementa u levo.

• MixColumns – Transformiše svaku kolonu matrice stanja množeći je sa jednom predefinisanom matricom. (Ne koristi se obično množenje matrica. Objašnjenje)

• AddRoundKey – Svakom elementu stanja dodaje odgovarajući element ključa trenutne runde koristeći operaciju XOR.

KeyExpansion

Za svaku rundu, u AddRoundKey transformaciji, se koristi poseban ključ. Koristeći ulazni ključ, na osnovu Rijndael key schedule algoritma, se izvode ostalih 10 ključeva. (AES Key schedule)

Tok algoritma

Pre izvršavanja AES algoritma je potrebno da se razvije ključ pomoću KeyExpansion operacije. Zatim algoritam teče na sledeći način:

• U inicijalnom koraku se izvrši AddRoundKey operacija.

• Zatim se izvršava 10 rundi koje se sastoje iz operacija SubBytes, ShiftRows, MixColumns i AddRoundKey.

• U finalnoj rundi se izvrše operacije SubBytes, ShiftRows i AddRoundKey.

Implementacija algoritma i performanse

Implementaciju algoritma u programskom jeziku C možete naći u ovom Github repozitorijumu. Repozitorijum se sastoji iz sledećih fajlova:

• aes.c – CPU implementacija AES-128 algoritma.

• aes.cu – GPU implementacija AES-128 algoritma.

• keygen.c – Program koji stvara ključ dužine 16 bajtova.

• payload.c – Program koji stvara podatke određene dužine. Kao argument prima prirodan broj n i stvara fajl dužine 2^n.

• measure.sh – Bash skripta koja generiše ključ i podatke različitih dužina, meri vreme izvršavanja CPU i GPU implementacije i rezultate čuva u obliku CSV fajla.

Dobijene podatke o vremenu izvršavanja smo iskoristili kako bi uporedili performanse obe implementacije. Kao što vidimo na grafiku ispod, za podatke veličine manje od 2^20, odnosno 1MB, vreme izvršavanja je veoma slično. Za te podatke ne možemo dovoljno precizno izračunati vreme izvršavanja. Ali razlika je očigledna za podatke veće od 1MB. Sa eksponencijalnim rastom veličine podatka se i vreme izvršavanja eksponencijalno povećava i kod CPU i kod GPU implementacije. Ako uporedimo vremena izvršavanja videćemo da je GPU implementacija oko 50 puta brža od CPU implementacije.

Za pokretanje CUDA programa je potrebna Nvidia grafička kartica. Ovi rezultati su dobijeni na kartici Nvidia GeForce GTX 960.

Režim šifrovanja kod blokovskih algoritama

Postoje različiti režimi šifrovanja kod blokovskih algoritama. Za potrebe ove demonstracije smo koristili Electronic Code Book (ECB) režim. Kod njega se svaki blok podataka nezavisno šifruje što omogućava da se algoritam lako paralelizuje. Ali mana ovog režima je to što dva bloka sa istim sadržajem će da izgledaju isto i kada su šifrovani. Na slici ispod vidimo sliku koja je šifrovana ECB režimom. Slika ne izgleda isto posle šifrovanja ali ipak možemo da uočimo šta se nalazilo na slici pre šifrovanja.

Ovaj problem može da se reši korišćenjem Cipher-Block Chaining (CBC) režimom koji za šifrovanje svakog bloka koristi rezultat šifrovanja prethodnog bloka. Na slici ispod vidimo šifrovanje iste slike ali CBC režimom. Mana ovog režima je to što zbog njega algoritam ne može da se paralelizuje.

Zaključak

U ovom članku smo se upoznali sa jednim od najpoznatijih algoritama za šifrovanje podataka i dva različita režima šifrovanja kod blokovskih algoritama. Ovom temom se još možemo pozabaviti istraživanjem drugih režima šifrovanja koji su sigurniji i pogodni za paralelizaciju. Takođe, shvatili smo pravu moć grafičkih procesora u oblasti paralelizacije i intenzivne obrade podataka.

Izvori i korisni linkovi

• https://developer.nvidia.com/gpugems/gpugems3/part-vi-gpu-computing/chapter-36-aes-encryption-and-decryption-gpu
• https://en.wikipedia.org/wiki/Advanced_Encryption_Standard
• https://en.wikipedia.org/wiki/AES_key_schedule
• https://github.com/backey/aes-performance
• https://github.com/kokke/tiny-AES-c/blob/master/aes.c
• AES Rijndael Cipher explained
• Learn CUDA in an Afternoon
• CUDA basics

Autor: Andrej Ilić

Student informatike, zainteresovan za upoznavanje novih tehnologija.

Linkedin | Github