Podstawy kryptografii i szyfrowania
Autorzy: Adam Tanaś i Adrian Sternal
Kryptografia zajmuje się utajnianiem wiadomości. Jest to sposób szyfrowania tekstu, mający na celu zabezpieczenie zawartości dokumentu, a nie faktu jego istnienia.
Terminologia:
Tekst jawny jest wiadomością w formie łatwej do odczytania.
Kryptogram (szyfrogram) to zaszyfrowana postać wiadomości czytelnej
Kryptoanaliza zajmuje się łamaniem szyfrów, czyli próbą odczytania zaszyfrowanej wiadomości bez użycia kluczy rozszyfrujących.
Klucz szyfrowania to ciąg danych za pomocą którego tekst jawny zostaje zamieniony w kryptogram. Klucz ten (lub sposób) jest ustalany przez adresata w fazie szyfrowania .
Klucz rozszyfrujący służy do zamienienia kryptogramu na postać czytelną przy użyciu algorytmów deszyfrowania.
Szyfrowanie metodą podstawiania
Jest to najprostszy sposób utajania wiadomości. Metoda ta polega na przestawieniu znaków alfabetu o kilka pozycji. Po osiągnięciu ostatniego znaku alfabetu następuje zapętlenie i podstawiony zostaje pierwszy znak alfabetu.
Można to wyrazić za pomocą wzoru f(y)=y+∆, gdzie ∆ oznacza liczbę przesunięć. Jeśli przyjmiemy, że w alfabecie znajduje się 26 znaków (od A do Z) to każdej literze przypisywana jest odpowiednia wartość, np. A=1, B=2,…,Z=26. Należy wtedy przyjąć, że ∆ jest zakresem liczb od 1 do 26.
Przykładem takiego szyfru może być szyfr Juliusza Cezara, który używał tej techniki do komunikowania się z przyjaciółmi. Klucz szyfrowania używany przez Cezara polegał na przesunięciu znaków alfabetu o 3 miejsca. Posługując się naszym wzorem szyfr ten będzie przyjmował wartość f(y)=y+3.
Np. „Veni vidi vici” (tekst jawny), f(y)=yhgl ylgl ylfl (kryptogram)
Szyfrowanie przestawne
Kolejną metodą szyfrowania jest przestawianie znaków w wiadomości jawnej. Jest to tzw. Wymieszanie znaków tekstu czytelnego, które zazwyczaj jest losowe. Takie szyfrowanie zalecane jest przy niedużych wiadomościach (rys. 1)
Rys.1
Niekiedy przestawienie nie jest losowe, przykładem mogą być np. figury geometryczne. Najłatwiejszą figurą transpozycji jest kwadrat lub prostokąt. Wtedy przed oczami ukazuje się nam macierz prostokątna.
Szyfr Vigenere’a
Jest zaliczany do grupy polialfabetycznych szyfrów podstawieniowych. Działanie oparte jest na tablicy przedstawionej poniżej.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Jak widać powyżej, algorytm ten można przyrównać do szyfru Cezara. Pierwszy wiersz tablicy zapisany jest normalnie. W drugim następuje już przesunięcie o jeden znak. W trzecim wierszu o dwa znaki itd.
Przy wykonywaniu szyfrowania tekstu potrzebować będziemy słowa-klucza. Jest ono tajne i dzięki niemu będziemy wiedzieć z którego wiersza, czy kolumny mamy skorzystać. Należy również pamiętać, aby przy szyfrowaniu tekstu nie używać spacji.
Zastosujmy ten szyfr w praktyce.
Np. Zastosujmy ten szyfr w praktyce
Słowo-klucz: praktyce
Zastosujmy ten szyfr w praktyce
Praktycepr akt ycepr a ktycepra
Każda litera szyfrogramu odpowiada literze z tabeli znajdującej się na przecięciu wiersza, wyznaczanego przez literę tekstu jawnego i kolumny wyznaczanej przez literę słowa kluczowego.
Idąc tym tropem Z i P daje O, A i R daje R itd.
Po wykonaniu wszystkich kroków otrzymujemy wiadomość szyfrowaną:
Orsdhqwnbp tog qbcui w zkymxnte
Szyfr płotkowy
Metoda ta polega na zapisaniu wiadomości w rzędach. Kluczem jest tutaj ilość rzędów. Kolejne znaki są zapisywane na zmianę przypominając „schody”.
Np.
Tekst jawny: Płotkowy
Klucz: ”3” – ilość rzędów
|
P |
|
|
|
K |
|
|
|
|
|
Ł |
|
T |
|
O |
|
Y |
|
|
|
O |
|
|
|
W |
|
Tekst zaszyfrowany: Pkłtoyow
Szyfrowanie symetryczne
W algorytmach symetrycznych zwanych także "algorytmami z kluczem tajnym", klucze szyfrujący oraz deszyfrujący są identyczne(albo można prosto wyprowadzić jeden z drugiego). Algorytmy te, potrzebują dogadania się co do klucza, pomiędzy nadawcą i odbiorcą, przed rozpoczęciem wysyłania przez nich informacji. Klucz ten zależy utrzymać w dyskrecji, ponieważ to właśnie od jego tajności zależy bezpieczeństwo systemu. Upublicznienie klucza jest jednoznaczne z sytuacją, w której każdy będzie potrafił szyfrować i deszyfrować informacje. Algorytmy symetryczne zostały w szczególności zaplanowany pod względem szybkości działania oraz dużej kwoty możliwych kluczy. Algorytmy z kluczem utajnionym możemy rozdzielić na dwa najważniejsze typy, to jest algorytmy strumieniowe, które szyfrują pojedyncze bity, nadają się całkiem dobrze do kodowania na bieżąco kanałów informacyjnych. Szyfr strumieniowy złożony jest z generatora ciągu kluczowego i elementu dodającego (dla przykładu zabieg XOR) kolejne bity klucza do kolejnych bitów tekstu jawnego skutkiem, czego jest ciąg bitów stanowiący kryptogram; oraz algorytmy blokowe, które szyfrują całe bloki bitów. Klasyczne wielkości szyfrowanych na raz partycji danych to 64 bity i 128 bitów. Jeśli blok jest dłuższy, tym większe jest rozproszenie, a tym samym ciężej wyszukać zależności pomiędzy tekstem jawnym, a szyfrem, będącymi podstawą deszyfrowania. Możliwe jest także wykorzystywanie algorytmów blokowych, jak strumieniowych, za pomocą trybów CFB i OFB.
Przykładem algorytmu symetrycznego jest Data Encryption System w skrócie DES, opracowany w latach 70-tych XX wieku przez firmę IBM.
Jednak już od kilku lat uznaje się, że ze względu na niedużą długość klucza(56 bitów, duża podatność na atak siłowy) nie jest w stanie zapewnić bezpieczeństwa na wysokim poziomie. Korzysta on z tak zwanej sieci Feistela, która umożliwia na szyfrowanie i deszyfrowanie wiadomości za pomocą tego samego algorytmu, pomimo, że funkcja f jest nie odwracalna. Sieć Feistela tworzy z tekstu jawnego szyfrogram, a z szyfrogramu tworzy tekst jawny. Poprzez taką metodę budowanie algorytmów szyfrujących zauważalnie się uprościło z racji, że nie musiano już się troszczyć o odwracalność funkcji f. Przykładowy schemat działania sieci Feistela został przedstawiony poniżej:
Rys.2
Polega to na tym, że tekst jawny dzielony jest na dwa te same bloki Li oraz Ri. Funkcja f jest właściwym algorytmem szyfrującym -otrzymywany z niej jest szyfrogram, a i to numer kolejnej rundy – oznacza to, że wynik jest ponownie kodowany i razy, dzięki czemu poprawiona zostaje jakość szyfrowania. Z racji wspomnianej wcześniej słabości klucza, DES został z biegiem czasu wyparty przez swoje własne modyfikacje jak chociażby 3DES, który opiera się na zakodowaniu informacji dzięki DES potrójnie: informacja kodowana jest pierwszym kluczem, dalej dekodowana jest drugim kluczem, i kodowana trzecim kluczem.
3DES korzysta z tych samych rozmiarów bloków oraz trybów, co DES. 3DES dzięki trzykrotnemu szyfrowaniu ma 168 bitów jednakże realna siła klucza 3DES jest równa 112 bitom z powodu podatności na atak typu Meetin-the-Middle.
Kolejnym przykładem niech będzie IDEA, którego pełne brzmienie to International Data Encryption Algorithm. Jest to symetryczny szyfr blokowy zawierający 128-bitowy klucz, pracujący na 64-bitowych blokach informacji, został opracowany w 1991 roku. Wykorzystuje on 3 rodzaje operacji na 16-bitowych liczbach. Są nimi:XOR, dodawanie modulo 2^16 oraz mnożenie modulo 2^16+1 (liczba pierwsza), a 0 jest traktowane jako 2^16. IDEA był wykorzystywany w początkowych wariantach PGP i jest udostępniony, jako nieobowiązkowy algorytm w Open PGP. Co ciekawe nigdy nie został złamany.
Czas na Advanced Encryption Standard w skrócie AES znany także, jako Rijndeal to symetryczny szyfr blokowy następca algorytmu DES. Daje możliwość użycia kluczy o długościach 128 bitów, 192 bitów oraz 256 bitów oraz działa na blokach danych o długości 128 bitów, chociaż pierwotna specyfikacja Rijndael akceptowała także bloki o rozmiarze 192 bitów oraz 256 bitów. AES wykonuje 10 rund kodujących wykorzystując klucz długości 128 bitów, 12 wykorzystując klucz długości 192 bitów lub 14 z wykorzystaniem klucza długości 256 bitów, które składają się z następujących czynności: substytucji wstępnej, permutacji macierzowej oraz modyfikacji z użyciem klucza. Dzięki niekonwencjonalnej budowie funkcji podstawieniowej algorytm został "zaszczepiony" przed ofensywą kryptoanalizy różnicowej oraz liniowej.
Następny symetryczny szyfr blokowy, Serpent zaprojektowany przez Larsa Knudsena, Eliego Bihama oraz Rossa Andersona. Serpent jest powolniejszy od Rijndae-lu, lecz bezpieczniejszy. Działa na blokach 128,192, oraz 256 bitowych, posługuje się 32 rundami, podczas których ma miejsce przekształcenie przez XOR względem klucza rundy, zastosowanie funkcji mieszającej o rozmiarze 128 bitów oraz użycie trzydziestu dwóch 4 bitowych S-box'ów. Algorytm zauważalnie uzyskuje na prędkości przez wykorzystanie w S-box'ach jedynie funkcji boolowskich. Każdy z cztery bitów wynikowych tych S-box'ów jest przedstawiany w charakterze funkcji boolowskiej czterech bitów wejściowych. Na dodatek w 32-bitowych procesorach istnieje możliwość przetwarzania transformacjina wszystkich trzydziestu dwóch S-box’ach , dlatego że każdy jeden bit wynikowy przedstawia(mimo że pracująca na rozbieżnych danych wejściowych) identyczna funkcja.
Algorytm Blowfish, powszechny szczególnie w produktach open source, zaprojektowany przez Bruce'a Schneiera w 1994 r. .Klucz podstawowy posiada długość do 448 bitów, a blok danych rozmiar 64 bitów. W algorytmie znajduje się 16 iteracji używających 18 kluczy pomocniczych, które ustalane są za każdym razem przed szyfrowaniem i deszyfrowaniem oraz 4 S-bloki 256 bitowe o wartościach uzależnionych od klucza podstawowego, danych oraz liczby Pi. Dekodowanie jest zabiegiem jednakowym z szyfrowaniem - tylko kolejność kluczy pomocniczych zostaje odwrotna.
SAFER jest algorytmem blokowym zaprojektowanym przez Jamesa L. Masseya. Powszechne są warianty: SAFER-K64 z kluczem 64 bitowym, który dotyczy 6 rund lub SAFER-K128 z kluczem 128 bitów - do 12 rund.
Algorytmy z grupy CAST, CAST określa projekt użyty w rodzinie zbliżonych do DES algorytmów kryptograficznych o różnych długościach kluczy i bloków. Najpopularniejszy to szyfr CAST-128 zaprezentowany w 1997 roku.
RC2 / RC4 / RC5 / RC6 to algorytmy zaprojektowane przez Ronalda Rivesta będącego twórcą firmy RSA Data Security. Są one wysoce efektywne mniej więcej 10 razy wydajniejsze od DES o różnej długości klucza nawet do 2048 bitów. RC2, RC5 oraz RC6 są szyframi blokowymi, a RC4 to szyfrem strumieniowym.
Szyfrowanie asymetryczne
Sprawa szyfrowania asymetrycznego polega na wyodrębnieniu dwóch kluczy o różnych rolach, mianowicie: klucza prywatnego oraz klucza publicznego. I tak "idąc dalej", załóżmy, że odbiorca posiada parę kluczy, to jest: prywatny klucz tudzież publiczny klucz. Klucz prywatny jest z założenia tajny i wiadomy wyłącznie właścicielowi. Natomiast, publiczny klucz może być powszechnie znany. Więc by przekazać zaszyfrowaną wiadomości do odbiorcy należy zaszyfrować wiadomość czytelną jego kluczem publicznym. Jej odszyfrowanie możliwe jest tylko za pomocą klucza prywatnego, odpowiadającego użytemu poprzednio kluczowi publicznemu.
Ważny jest fakt, iż znajomość klucza publicznego nie jest wystarczająca do zachwiania poufności szyfrogramu otrzymanego przy zastosowaniu tegoż klucza. Zatem szyfrowanie asymetryczne świetnie nadaje się do zapewnienia poufności oraz autentyczności. Aczkolwiek minusem jest to, iż jest ono o wiele wolniejsze od symetrycznego i w zastosowaniu społecznym rzadko kiedy szyfruje się w całości informacje dzięki za jego pomocą, w zamian po prostu szyfruje się jedynie klucz danego szyfru symetrycznego
Przykładem algorytmu asymetrycznego jest niewątpliwie RSA, który to został zaprezentowany w 1978 roku przez Ronalda Rivesta, Adi Shamira, oraz Leonarda Adlemana, jak nie trudno zauważyć nazwę tworzą pierwsze litery nazwisk(Rivest-Shamir-Adleman). Polega on na kłopocie faktoryzacji dużych liczb, znalezienie szybkiej metody faktoryzacji doprowadziłoby do jego złamania.
Nie znaleziono jednak w literaturze dowodu na to, że RSA nie jest możliwe do rozszyfrowania w inną drogą. W celu wygenerowania klucza RSA losowane są 2 duże liczby pierwsze p oraz q, tudzież liczba względnie pierwsza e, równa: e=(p-1)(q-1).
Liczby względnie pierwsze to liczby całkowite, które w rozkładzie na czynniki pierwsze nie posiadają takich samych dzielników poza jedynką.
Potem liczona jest liczba d: d=e^-1 mod (p-1)(q-1). Z racji, iż e jest liczbą względnie pierwszą, posiada odwrotność, którą można wyliczyć w miarę szybko dzięki zastosowaniu rozszerzonego algorytmu Euklidesa. Wyliczana jest także liczba n: n=p*q.
Kluczem publicznym jest dwoje liczb (e,n), a kluczem prywatnym jest dwoje liczb (d,n). Algorytm RSA zakłada destrukcję liczb pi q. Aby zaszyfrować przekaz, trzeba podnieść reprezentującą go liczbę (wartość bitową) do potęgi e, a następnie dokonać dzielenia modulo n. Zabieg ten możemy zapisać w postaci wzoru:
C=P^e mod n - gdzie P to tekst jawny informacji, a C to szyfrogram. By móc odszyfrować szyfrogram, trzeba podnieść zaszyfrowany przekaz do potęgi d– zgodnie z twierdzeniem Eulera : C^d = P^ed = P mod n.
Złamanie informacji bez znajomości djest w praktyce trudne obliczeniowo. Póki co nie ma łatwego obliczeniowo sposobu odtworzenia liczby dz ebez faktoryzacji n na p i q. Także ElGamal(ELG) opublikowany w 1985 roku jest "algorytmem kryptografii asymetrycznej opartymna trudności problemu logarytmu dyskretnego w ciele liczb całkowitych przy dzieleniu modulo przez dużą liczbę pierwszą". Generowanie klucza zachodzi następująco:
· wybierana jest jakakolwiek liczba pierwsza p, oraz jakikolwiek generator a podgrupy
multiplikatywnej (czyli taki składnik, którego rząd jest równy p) oraz jakiekolwiek k, które spełnia warunek 1<k<p
· później obliczane jest b takie, że: b=a^k
Funkcję klucza publicznego spełniają liczby (p,a,b), a funkcję klucza prywatnego, k. By zaszyfrować informacje dzięki ElGamal reprezentację liczbową informacji P ukazuje się jako składową grupy [1<P<p-1],potem wybierana jest liczba y należąca do zbioru {2,(p-1)}, po czym następuje obliczenie c1i c2 według niżej pokazanych wzorów:
c1=a^y
c2=Pb^y
Dwoje liczb (c1,c2) jest szyfrogramem informacji. By odszyfrować informacje, potrzeba wpierw obliczyć liczbę d według wzoru: d=c1^k, potem można już obliczyć tekst znany P, jako P=c2/d.
Jeśli rząd grupy multiplikatywnej (p) nie jest iloczynem dużych liczb pierwszych, to istniejew tym przypadku efektywny sposób obliczania wykładnika tzw. "redukcja Pohliga-Hellmana".Na chwilę obecną nie ma „generalnego" sposobu relatywnie szybkiego wyliczania logarytmu dyskretnego, co za tym idzie nie ma możliwości obliczenia k dzięki a i c1.
Zastosowanie kryptografii w życiu codziennym
Algorytmów szyfrowania używa się w podpisie cyfrowym, przez co możliwe jest uwiarygodnienie nadawcy, dzięki czemu odbiorca jest przekonany, że nikt nie próbuje go oszukać podszywając się pod nadawcę. A nadawca nie jest w stanie zanegować faktu, że to nie on jest autorem przesłanej informacji. Ogółem kryptografia asymetryczna jest wykorzystywana wszędzie gdzie do przesyłu wiadomości używa się powszechnie dostępnych kanałów chociażby Internetu, a także w sytuacji, gdy osoby zainteresowane z jakiś przyczyn nie są w stanie w niezagrożony sposób ustalić szyfru symetrycznego. RSA jest również odpowiedzialny za bezpieczeństwo systemów bankowy, czy rozpowszechniania broni jądrowej. Inne algorytmy RC2 / RC4 / RC5 / RC6 są masowo używane w Apple Open Collaboration Enviromnent, Lotus Notes, protokołach SSL i S-HTTP, Oracle, oraz sieciach bezprzewodowych i komórkowych. Kryptografie widać również w ochronie praw autorskich do utworów muzyczny, gier, filmów itp. w cyfrowej postaci, która odbywa się za pomocą cyfrowych znaków wodnych; lub oznaczaniu przesyłek tak, by osoby niepowołane nie miały pojęcia, co w przesyłce się znajduje. Także w telewizji satelitarnej, serwisach społecznościowych, systemach operacyjnych, internetowych komunikatorach, protokołach TLS, SLL, ochronie danych osobowych przed wykradzeniem lub fałszerstwem (kliniki, przychodnie, biblioteki, monitoring) itp. Także wojsko korzysta z algorytmów szyfrujących, ambasady, mafie, wspomniane banki, terroryści, sekty, agencje rządowe, sprzedawcy, artyści i tak by można jeszcze długo, długo wymieniać gdyż kryptografia jest wszechobecna często my sami zapatrzeni w nasze codzienne sprawy nie mamy tej świadomości jak istotną rolę odgrywa w naszym społeczeństwie.
„Praca wykonana w ramach zajęć z Narzędzi Informatyki, rok akad. 2015/16”
Bibliografia:
Buchmann J. A. „Wprowadzenie do kryptografii”, PWN, 2006 rok
Stinson D. R. „Kryptografia w teorii i praktyce”, WNT, 2005 rok
Bruce Schneier „Kryptografia dla praktyków”, WNT, 2002 rok
http://www.b-skrzypczyk.republika.pl