Cloud Crypto Tool – Algorytm SDES – Simplified Data Encryption Standard

Na pierwszy ogień zaimplementujemy jakiś prosty algorytm szyfrujący, obrazujący podstawy szyfrowania danych. Jednym z najlepszych szyfrów, o niezbyt dużym stopniu skomplikowania, jest algorytm SDES (Simplified Data Encryption Standard). Został on zaprojektowany tylko i wyłącznie do celów edukacyjnych, nigdy nie powinien być wykorzystywany w żadnym komercyjnym systemie kryptograficznym. Spis wszystkich permutacji, niezbędnych w procesie szyfrowania oraz generowania podkluczy, jak i kod samego algorytmu szyfrującego, znajdziesz na moim repozytorium.

Wspomniany algorytm został opracowany w 1996 roku przez Edwarda Schaefera jako uproszczona wersja standardu DES. Szyfr ten nigdy nie znalazł żadnego praktycznego zastosowania. Opracowano go jako wstęp, ułatwiający dokładne zrozumienie, do zaproponowanego wcześniej standardu DES. SDES operuje na 8-bitowych porcjach tekstu jawnego posługując się przy tym 10-bitowym kluczem szyfrującym. Wynikiem procesu szyfrowania jest 8-bitowy fragment szyfrogramu. SDES jest algorytmem symetrycznym, ten sam klucz wykorzystywany jest do szyfrowania i deszyfrowania informacji. Długość klucza szyfrującego określana jest jako słabość w bezpieczeństwie tego szyfru. 10-bitowy klucz oznacza, że mamy do dyspozycji tylko 2^{10} = 1024 możliwych kluczy szyfrujących. Tak mała pula podatna jest nawet na najprostszy atak siłowy (brute-force).

Generowanie podkluczy

Na samym początku algorytmu, na podstawie zadanego klucza szyfrującego, generowane są dwa 8-bitowe podklucze K_1 oraz K_2 – wykorzystywane w każdej z dwóch rund algorytmu. Klucz główny zostaje przekazany do permutacji P10, zadaniem której jest poprzestawianie bitów klucza według z góry określonej tabeli przestawień. Następnie wygenerowany ciąg zostaje przedzielony na dwie równe części. Każda z nich zostaje poddana operacji cyklicznego przesunięcia o jedną pozycję w lewo (Shift) – każdy najbardziej znaczący bit MSB (Most Significant Bit), pierwszy po lewej stronie, zostanie przesunięty na pozycję najmniej znaczącego bitu LSB (Least Significant Bit), czyli maksymalnie na prawo. Często bite te określa się mianem najstarszego oraz najmłodszego bitu. Przesunięte 5-bitowe połówki zostają skonkatenowane ze sobą w jeden 10-bitowy ciąg, który następnie zostaje przekazany do permutacji P8. W ten sposób uzyskaliśmy pierwszy z podkluczy K_1.

Proces generowania podkluczy algorytmu SDES
Proces generowania podkluczy algorytmu SDES

W celu wygenerowania drugiego podklucza K_2 po jednokrotnym przesunięciu podciągów wykonuje się dodatkowe przesunięcie – tym razem o dwie pozycje. Nowy wygenerowane podciągi, również konkatenowane są ze sobą w jeden blok danych, który następnie przekazywany do permutacji P8. Proces generowania podkluczy został zrealizowany w następujący sposób:

Permutacje i przesunięcia

Wspomniana już kilkukrotnie operacja permutacji została zrealizowana za pomocą poniższego kodu:

Na pierwszy rzut oka kod może wydawać się nieco „egzotyczny” – z tego co zauważyłem, operacje bitowe nie są zbyt często wykorzystywane przez programistów, może się mylę 🙂 Iterujemy po każdej wartości znajdującej się w tabeli permutacji. Wartość 0 od samego początku przesuwana jest o jedną pozycję w lewo – na razie nie ma to większego znaczenia, zostawmy to w spokoju. Następnie odejmujemy pierwszą wartość z tabeli od największej możliwej wartości permutacji. Przez operację logicznego mnożenia wyciągana jest wartość najmłodszego bitu, na podstawie którego dokonujemy przesunięcia permutowanego ciągu w prawo – maksymalnie możliwe jest przesunięcie o tylko jedną pozycję. Na sam koniec przesunięta wartość poddawana jest logicznej sumie, dzięki czemu zapisywany jest wynik z iteracji. W kolejnej turze wracamy do przesunięcia w lewo, co pozwala nam zapamiętać otrzymany bit, a następnie rozważany jest kolejny fragment permutacji i tak aż do wyczerpania. Oczywiście można by to zrealizować na tablicach i bawić się w podmienianie indeksów, aczkolwiek operacje bitowe są dużo szybsze.

Co do samych przesunięć cyklicznych:

Kopia najbardziej znaczącego bitu zapisywana jest do zmiennej pomocniczej, a następnie wspomniany bit usuwany jest z podciągu. Teraz całość przesuwana jest o jedną pozycję w lewo, a najstarszy bit ląduje na pozycji najmniej znaczącego bitu.

Szyfrowanie

Proces szyfrowania składa się z pięciu podstawowych elementów. Przekazany blok tekstu jawnego przekazywany jest do permutacji początkowej IP. Wygenerowany ciąg, wraz z pierwszym podkluczem K_1, zostaje przekazany do funkcji rundy f_k, odpowiadającej za wszystkie przekształcenia i permutacje. Wygenerowany fragment zostaje następnie przemieszany za pomocą funkcji SW (Swap) zamieniającej miejscami lewą część z prawą – można to sprowadzić do przesunięcia cyklicznego o cztery pozycje w lewo. Tak wymieszany ciąg wpada do drugiej rundy algorytmu. Po raz kolejny wykorzystywana jest funkcja rundy, tym razem z podkluczem K_2. Na sam koniec, wygenerowany ciąg zostaje przerzucony przez permutację odwrotną IP^{-1}. W ten sposób powstaje 8-bitowy fragment szyfrogramu.

Funkcja rundy algorytmu SDES

Wewnątrz funkcji f_k blok danych zostaje podzielony na dwie równe części, lewą oraz prawą. W tym momencie wprowadza się pojęcie dodatkowej funkcji pomocniczej F, realizującej przekształcenia prawej części bloku oraz podklucza. Lewa część bloku xor’owaną jest wartością funkcji F. Rundę algorytmu kończy operacja konkatenacji wygenerowanego ciągu z prawą częścią bloku: f_k(L, R) = (L \oplus F(R, K_i), R).

Funkcja pomocnicza

Wewnątrz funkcji pomocniczej, prawa część zostaje przekazana do permutacji rozszerzającej E, zwiększając rozmiar ciągu z 4 do 8 bitów – każdy z bitów powielany jest względem pewnej, z góry ustalonej tabeli. Dzięki rozszerzeniu ciągu może zostać on podany operacji alternatywy wykluczającej, potocznie zwanej xor’owaniem, z podkluczem. Po raz kolejny dokonujemy przecięcia bloku na dwie 4 bitowe części, które zostają przekazane do tzw. S-Bloków. Zadaniem tych macierzy jest nieliniowa dekompresja danych wejściowych – z 4 do 2 bitów. Wyjścia S-Bloków konkatenuje się ze sobą, a następnie przekazuje do permutacji P4.

Może jeszcze słówko na temat tego w jaki sposób wybierane są indeksy dla S-Bloków. Pierwszy i czwarty bit przekazanego do S-bloku ciągu wejściowego odpowiada za numer wiersza macierzy, natomiast drugi i trzeci za numer kolumny. Na podstawie tych wartości obliczany jest indeks macierzy, z której zostanie wyciągnięta wartość S-Bloku:

Deszyfrowanie

Proces deszyfrowania wygląda niemal identycznie jak proces szyfrowania. Różni się jedynie kolejnością podania podkluczy. W pierwszej rundzie algorytmu wykorzystywany jest podklucz K_2, natomiast w drugiej rundzie podklucz K_1. Reszta przekształceń pozostaje taka sama.

Ok, myślę, że na początek  byłoby tego, żeby nikogo za bardzo kryptografią nie przerazić 🙂 Polecam każdemu zaimplementowanie swojego własnego algorytmu SDES, w razie problemów można podejrzeć kod na GitHub’ie.  Następnym razem przejdziemy do oryginalnego DES’a.