Rozdział 5. Szyfrowanie i deszyfrowanie danych - implementacja wybranego algorytmu na procesor Cell/B.E.
Prowadzący zajęcia projektowe: Rafał Petryniak (strona domowa zajęć projektowych).
Spis treści
Szyfr – rodzaj parametryzowanego kodu stosowanego w celu utajnienia wiadomości tak, by była ona niemożliwa (lub praktycznie niemożliwa) do odczytania przez każdego, kto nie posiada odpowiedniego klucza.
Wiadomość przed zaszyfrowaniem nazywa się tekstem jawnym (plaintext), a wiadomość zaszyfrowaną – szyfrogramem (ciphertext) lub tekstem zaszyfrowanym.
Metody szyfrowania możemy podzielić na 3 grupy:
szyfry asymetryczne
symetryczne szyfry blokowe
symetryczne szyfry strumieniowe
W szyfrowaniu asymetrycznym występują 2 klucze – klucz publiczny służący do szyfrowania, oraz klucz prywatny służący do deszyfrowania. Ponieważ nie ma potrzeby rozpowszechniania klucza prywatnego, bardzo małe są szanse, że wpadnie on w niepowołane ręce. Szyfry asymetryczne opierają się na istnieniu pewnych trudnych do odwrócenia problemów. Na przykład o wiele łatwiej jest pomnożyć przez siebie 2 duże liczby, niż rozłożyć dużą liczbę na czynniki (opiera się na tym system RSA). Drugim popularnym systemem jest ElGamal, opierający się na trudności logarytmu dyskretnego. Typowe rozmiary kluczy są wielkości 1024-2048 bitów dla np. RSA lub ok. 512 bitów dla kryptografii na krzywych eliptycznych. W przypadku RSA złamane zostały klucze rozmiarów do ok. 500 bitów.
Szyfry blokowe to procedury, które szyfrują niewielkie bloki danych (znacznie mniejsze od typowej wiadomości), współcześnie jest to najczęściej 128 bitów (AES), choć do niedawna przeważały 64-bitowe bloki (DES, 3DES, Blowfish, IDEA). Klucze są znacznie mniejsze, mają zwykle od 128 do 256 bitów, przy czym wartości mniejsze od 80 (DES – 56) są uważane za niewystarczające. Typowy szyfr blokowy składa się z kilkunastu dość prostych rund przekształcających blok. Operacje używane w tych szyfrach są zwykle proste, ale pochodzą z "różnych światów", np. używa się dodawania, XOR, przesunięć cyklicznych, różnego typu S-BOXów, mnożenia modulo liczb pierwszych itd. Już kilka rund takich operacji zupełnie zaburza jakikolwiek porządek i jest bardzo trudne do analizowania. Ponieważ szyfr blokowy szyfruje jedynie niewielką ilość informacji, używane są różne tryby szyfrowania, które umożliwiają szyfrowanie większych wiadomości.
Szyfry strumieniowe szyfrują każdy znak tekstu jawnego osobno, generując znak strumienia szyfrującego i przekształcając go na przykład z użyciem funkcji XOR ze znakiem danych, w związku z czym nie jest konieczne oczekiwanie na cały blok danych, jak w przypadku szyfrów blokowych. Najpopularniejszym współczesnym szyfrem strumieniowym jest RC4. Inne popularne szyfry strumieniowe to A5/1 i A5/2 stosowane w telefonii komórkowej. Do szyfrów strumieniowych należą też historyczne szyfry polialfabetyczne i monoalfabetyczne.
W naszym projekcie najpierw zastosowaliśmy algorytm szyfrujący 3-Way. Po implementacji sekwencyjnej, podczas pracy nad implementacją zrównolegloną okazało się z podowdu odmiennej architektury procesora Cell algorytm 3-Way nie moze być przez nas stosowany(problem pojawił się w związku z przesunięciami bitowymi i bardzo rygorystycznymi wymogami algorytmu odnośnie typów zmiennych), ponieważ pliki zaszyfrowane po deszyfracji nie przyjmują pierwotnych wartości. Dlatego zastosowaliśmy algorytm XOR.
3-Way jest szyfrem blokowym zaprojektowanym przez Joan Daemen. Został on zaprojektowany tak, aby był efektywny w realizacji sprzętowej. Zarówno bloki, jak i klucze są 96-bitowe.
Algorytm można dość łatwo opisać. Zaszyfrowanie bloku x z tekstu jawnego jest wykonywane według następującego algorytmu:
For i=0 to n-1 x=xXORKn x=theta(x) x=pi-1(x) x=gamma(x) x=pi-2(x) x=x+Kn x=theta(x) End
Poszczególne funkcje są zdefiniowane następująco:
theta(x) jest liniową funkcją podstawieniową – zestawem przesunięć cyklicznych i sumowań modulo 2.
pi-1(x) i pi-1(x) to proste permutacje.
gamma (x) jest nieliniową funkcją podstawieniową; sposób jej działania jest źródłem nazwy algorytmu: funkcja ta definiuje równoległe operacje podstawiania na 3-bitowych blokach wejściowych.
Deszyfrowanie jest podobne do szyfrowania, ale należy odwrócić kolejność bitów wejściowych i wyjściowych.
Operacja ta jest częścią składową wielu rozbudowanych algorytmów kryptograficznych jak np. DES (Data Encryption Standard). Operacja ta sama w sobie stanowi również prosty algorytm szyfrowania, który nie zapewnia jednak większego bezpieczeństwa. Jednak przy spełnieniu kilku bardzo ważnych warunków może stanowić, mimo swej prostoty, algorytm
Opis metody:
Oprócz tej nazwy możemy spotkać się z takimi nazwami jak alternatywa wykluczająca lub binarne sumowanie mod 2. W matematyce oznaczana jest często przez symbol krzyżyk w kółeczku.
Operacja ta wygląda następująco:
0 XOR 0 = 0 1 XOR 1 = 0 0 XOR 1 = 1 0 XOR 0 = 0 1 XOR 0 = 1
Należy pamiętać, że w wyniku podwójnego wykonania operacji XOR otrzymamy tekst jawny.
Zatem:
M XOR K = C C XOR K = M
Czyli:
(M XOR K) XOR K = M
W wyniku tego mamy tylko jedną procedurę, zarówno do szyfrowania jak i do deszyfrowania.
Poniżej został umieszczone fragmenty kodu algorytmu 3-way, oraz wyynik szyfrowania przykładowych danych. Aby skompilować program w systemie linux trzeba utworzyć plik, w którym umieszczamy kod programu i zapisujemy go jako 3way.cpp (Nazwa moze być dowolna). Następnie w konsoli przechodzimy do katalogu gdzie znajduje się plik i komplijemy go komendą:
gcc 3way.cpp -o 3way
W ten sposób utworzyliśmy plik wykonywalny "3way" który możemy uruchomić po przez wpisanie nazwy pliku w lini komend i nacisnięcie enter.
Procedura zmieniająca kolejność bitów:
void mu(word32 *a)
{
int i;
word32 b[3];
b[0]=b[1]=b[2]=0;
for (i=0; i <32; i++)
{
b[0]<<=1;
b[1]<<=1;
b[2]<<=1;
if(a[0]&1) b[2] |=1;
if(a[1]&1) b[1] |=1;
if(a[2]&1) b[0] |=1;
a[0]>>=1;
a[1]>>=1;
a[2]>>=1;
}
a[0]=b[0];
a[1]=b[1];
a[2]=b[2];
}Procedura gamma:
void gamma(word32 *a)
{
word32 b[3];
b[0]=a[0]^(a[1]|(~a[2]));
b[1]=a[1]^(a[2]|(~a[0]));
b[2]=a[2]^(a[0]|(~a[1]));
a[0]=b[0];
a[1]=b[1];
a[2]=b[2];
}Procedura theta:
void theta(word32 *a)
{
word32 b[3];
b[0]=a[0] ^ (a[0]>>16) ^ (a[1]<<16) ^ (a[1]>>16) ^ (a[2]<<16) ^
(a[1]>>16) ^ (a[2]<<16) ^ (a[2]>>16) ^ (a[0]<<16) ^
(a[2]>>16) ^ (a[0]<<16) ^ (a[2]>>16) ^ (a[0]<<16) ;
b[1]=a[1] ^ (a[1]>>16) ^ (a[2]<<16) ^ (a[2]>>16) ^ (a[1]<<16) ^
(a[2]>>16) ^ (a[0]<<16) ^ (a[0]>>16) ^ (a[1]<<16) ^
(a[2]>>16) ^ (a[1]<<16) ^ (a[0]>>16) ^ (a[1]<<16) ;
b[2]=a[2] ^ (a[2]>>16) ^ (a[0]<<16) ^ (a[0]>>16) ^ (a[1]<<16) ^
(a[0]>>16) ^ (a[1]<<16) ^ (a[1]>>16) ^ (a[2]<<16) ^
(a[1]>>16) ^ (a[2]<<16) ^ (a[1]>>16) ^ (a[2]<<16) ;
a[0]=b[0];
a[1]=b[1];
a[2]=b[2];
}Procedura szyfrowania:
void encrypt(twy_ctx *c, word32 *a)
{
char i;
for(i=0;i<NMBR;i++)
{
a[0]^=c->k[0]^(c->ercon[i]<<16);
a[1]^=c->k[1];
a[2]^=c->k[2]^c->ercon[i];
rho(a);
}
a[0]^=c->k[0]^(c->ercon[NMBR]<<16);
a[1]^=c->k[1];
a[2]=c->k[2]^c->ercon[NMBR];
}Procedura deszyfracji:
void decrypt(twy_ctx *c, word32 *a)
{
char i;
mu(a);
for(i=0; i<NMBR; i++)
{
a[0]^=c->ki[0]^(c->drcon[i]<<16);
a[1]^=c->ki[1];
a[2]^=c->ki[2]^c->drcon[i];
rho(a);
}
a[0]^=c->ki[0]^(c->drcon[NMBR]<<16);
a[1]^=c->ki[1];
a[2]^=c->ki[2]^c->drcon[NMBR];
theta(a);
mu(a);
}Za bazę wykorzystaliśmy kod stworzony przez nas przy implemntacji sekwencyjnej algorytmu 3-Way, różnica polega na użyciu procedury szyfrowania XOR.
Program korzysta z dwóch plików tekstowych. Jest to plik z danymi do zaszyfrowania (input.txt) oraz plik z kluczem szyfrującym (key.txt). Po zaszyfrowaniu pliki są umieszczane w trzecim pliku tekstowym (output.txt).
Kod algorytmu XOR:
void xorproc(word32* array, word32 *klucz, int size)
{
int n=0;
while(n<size)
{
array[n]=array[n]^klucz[n%10];
n++;
};
return;
}*array - wskaźnik do tablicy zawierajaca dane do zaszyfrowania
*klucz - wskaźnik do tablicy zawierajacy klucz do szyfrowania
size - wielkość tablicy
Program który stworzyliśmy wykorzystuje procesor główny konsoli PlayStation 3 wraz z jej procesorami specjalizowanymi. Dzięki rozdzieleniu pracy pomiędzy poszczególne procesory, które wykonują swoją prace równolegle w czasie, program jest znacznie wydajniejszy od swojej wersji sekwencyjnej, szczególnie w przypadku bardzo dużych ilości danych do zaszyfrowania.
Nasz program przy użyciu głównego procesora rozdziela dane do zaszyfrowania na równe co do wielkości paczki, które są następnie wysyłane na poszczególne procesory specjalizowane.
Aby zoptymalizować program i w pełni wykorzystać możlwiości jakie daje nam procesor Cell dane które przesyłamy do poszczegónych wektorów sa w postaci zwektoryzowanej, co znacznie przyspiesz wykonaywanie na nich wszelkich operacji
Zmodyfikowany kod algorytmu szyfrującego(jest on oczywiście umieszczony we fragmecie programu który będzie wykonywany na poszczególnych procesorach specjalistycznych SPE):
void xorproc(word32* array, word32* klucz, int size)
{
int i;
vector unsigned int *dane = (vector unsigned int*)(array);
vector unsigned int *key = (vector unsigned int*)(klucz);
for (i = 0; i < (size / 4); i++)
{
dane[i] = dane[i]^key[i%3];
}
} Ważnym elementem programu jest przygotowywanie w procesorze głównym odpowiednich paczek danych do wysłania ich na pozostałe procesory.
while (fgets(bufor, BUFSIZ, fp) != NULL)
{
a[licznik]=atoi(bufor); //konwersja char do unsigned int ...
licznik++;
}Aby uruchomić program należy przejść do odpowiedniego folderu (single_buffer) i następnie wywołać komendę:
./single_buffer file/input.txt file/output.txt
wyjaśnienie znaczenia poszczególnych fragmentów komendy
./single buffer - to uruchomienie programu o nazwie single_buffer
file/input.txt - to scieżka do pliku z danymi, które mają być zaszyfrowane (plik txt w folderze file)
file/output - to ścieżka do pliku w którym zostaną umieszczone zaszyfrowane dane
Oczywiście nazwy plików ss dowolne, warunkiem jest tylko istnienie pliku wejściowego w podanej lokazlizacji.
Aby wykonać deszyfrację pliku należy podac w miejsce pliku wejściowego scieżkę do pliku zaszyfrowanego.
Należy pamiętać o posiadaniu odpowiedniego pliku z kluczem. Im dłuższe liczby w kluczu tym plik zaszyfrowany będzie dłuzszy. należy pamiętać, że ilość liczb w kluczu powinna być wielokrotnością liczby cztery. Jest to wymagane przy algorytmie szyfrującym. W przypadku zmiany ilości liczb nalezy pamiętać że:
Y = 4 * x
gdzie:
Y - to ilość liczb w kluczu
x - to liczba całkowita która jest wykorzystywana przy wyborze liczby z klucza w algorytmie XOR (w naszym przypadku to 3)
Zrównoleglenie algorytmów takich jak szyfrowanie i deszyfrowanie (wymagających wielu obliczeń na dużej ilości danych) znacznie usprawnia szybkość ich wykonywania. Mankamentem mogącym jednak wystąpić przy implementacji standartowych kodów szyfrujących są różnice w architekturze między procesorami CELL i standartowymi x86. Jednakże przy zachowaniu zasad obowiązujących na procesorze Cell (np. trzeba pamiętać, że przy wektoryzacji typu int należy utworzyć wektor unsigned int lub signed int ponieważ typu int procesor Cell nie obsługuje przy wektorach) możliwe jest przekształcenie programu sekwencyjnego na równoległy, dzięki czemu nasz program zostanie zoptymalizowany i jego wydajność (szczególnie przy dużych ilościach danych) znacznie wzrośnie.