Kryptografia

KRYPTOGRAFIA

Rodzaje algorytmów
  Ludzie wymyślili wiele sposobów szyfrownia danych. Większość z nich posiada pewne cechy, pozwalające na pogrupowanie tworzących je algorytmów według sposobu ich działania. Różnią się one między sobą bezpieczeństwem, szybkością działania i niezawodnością. Najprostsze z nich opierają się na podstawowych działaniach matematycznych i geometrii, podczas gdy te bardziej skomplikowane wykorzystują układy logiczne oraz zaawansowane funkcje i przekształcenia. Główny podział algorytmów według sposobu ich działania został przedstawiony poniżej:

> Szyfry monoalfabetyczne
Algorytmy tego typu charakteryzują się tym, że jako regułę zastępowania znaków wykorzystują wybraną modyfikację (permutację) alfabetu. Oznacza to, że każdy znak, po zakodowaniu przyjmuje wartość innego z góry ustalonego znaku. Dla 26 znakowego alfabetu, liczba możliwych kombinacji wynosi 26!, czyli 403291461126605635584000000. Szyfry tego typu nie są bezpieczne, ponieważ są podatne m.in. na statystyczne metody łamania szyfru. Do tej grupy szyfrów należy większość stosowanych w przeszłości (np. Cezara).

> Szyfry wieloliterowe
  Jest to ulepszona wersja algorytmu monoalfabetycznego, polegająca na tym, że w celu utrudnienia odczytu struktury tekstu, powtarzające się znaki są szyfrowane. Szyfry tego typu są dalej podatne na statystyczne metody łamania szyfru. Przykładem jest algorytm Playfair. Szyfr ten nie zapewnia obecnie bezpieczeństwa.

> Szyfry polialfabetyczne
Szyfry tego rodzaju, polegają na tym, że kolejne znaki informacji szyfrowane są przy użyciu innej reguły podstawienia monoalfabetycznego, w zależności od miejsca położenia. Kluczem do szyfrowania i odszyfrowania wiadomości jest kombinacja znaków dowolnej długości. Ponieważ znaki nie są kodowane "z góry", statystyczne metody łamania szyfru są w tym momencie ograniczone. Na takiej zasadzie działał szyfr Vigenere'a. Użycie tego algorytmu nie daje bezpieczeństwa.

> Szyfry symetryczne
Do tej grupy szyfrów należą wszystkie te, które do szyfrowania i deszyfrowania wiadomości używają tego samego klucza. Bezpieczeństwo jakie daje ten rodzaj algorytmów zależy od długości użytego klucza i odporności na inne ataki niż atak bezpośredni. Kryptografia symetryczna wykorzystywana jest tylko do szyfrowania. Bardziej zaawansowane funkcje taki jak uwierzytelniania, czy podpisy cyfrowe możliwe są tylko przy zastosowaniu kryptografii asymetrycznej. Przykłady: Blowfish, DES.

> Szyfry asymetryczne
  Szyfry asymetryczne, od szyfrów symetrycznych, różnią się tym, że do szyfrowania i deszyfrowania danych potrzeba użyć co najmniej dwóch różnych kluczy. Powiększa to znacznie ilość zastosowań takiego systemu kryptograficznego. Żadnego z kluczy stosowanych w tych algorytmach nie da się odtworzyć na podstawie innego. W użyciu przy podpisach cyfrowych, metoda ta, daje pewność, że dana wiadomość została podpisana przez posiadacza klucza prywatnego, a przy szyfrowaniu ,że informacja zakodowana kluczem publicznym zostanie odczytana tylko przez właściciela klucza prywatnego. Jak same nazwy wskazują, klucz prywatny jest w posiadaniu tylko i wyłącznie jednej osoby, podczas gdy klucz publiczny jest dostępny dla każdego. Algorytmy asymetryczne wykorzystują operacje, które łatwo przeprowadzi w jedną stronę natomiast dużo trudniej w drugą. Przykładami takich operacji są:
- mnożenie i faktoryzacja, wykorzystane w RSA;
- potęgowanie modulo i logarytm dyskretny, użyte w DSA.

> Szyfry przestawieniowe
  Cechą wszystkich algorytmów należących do tej grupy jest to, że w szyfrogramie występują te same znaki, co w wiadomości przed zaszyfrowaniem, ale w innej kolejności. Często do przestawienia liter używa się w nich figury geometrycznej (Macierze). Szyfry tego typu dają stosunkowo bardzo małe bezpieczeństwo.

> Szyfry podstawieniowe
Każdemu znakowi zakodowanemu tym algorytmem zostaje przyporządkowany inny znak w szyfrogramie. Na tej zasadzie opierał się np. szyfr Vigenere'a. Z powodu znikomego bezpieczeństwa ten rodzaj algorytmów przestał być stosowany.

> Szyfry przesuwające
  Działanie tych algorytmów, będących zarazem szyframi podstawieniowymi, opiera się na przesunięciu znaku o n pozycji w kryptogramie. Z powodu swojej prostoty systemy takie nie zapewniają użytkownikowi żadnego bezpieczeństwa. Przykłady: ROT13, szyfr Cezara.

> Ograniczone
Ta kateogria grupuje wszystkie algorytmy, których skuteczność oparta jest tylko na utajnieniu sposobu ich działania. Odkrycie jednego algorytmu daje w takim wypadku możliwość odkodowania wszystkich innych. Takie szyfry interesujące są aktualnie jedynie z powodu swojego historycznego znaczenia.

> Strumieniowe / Blokowe
Algorytmy blokowe różnią się tym od strumieniowych, że operacje przeprowadzają na całych blokach (fragmentach informacji), a nie kolejnych znakach (lub bitach). Bloki mogą być różnej wielkości (np. 16, 64, 128, 1024) ,przy czym im większa wielkość tym szyfr jest bardziej bezpieczny. Po podzieleniu informacji na bloki odpowiedniej wielkości należy wybrać sposób szyfrowania:
- CBC - tryb tego kodowania polega na szyfrowaniu kolejnych bloków
  algorytmem XOR z poprzednim blokiem. 
- CBF - za pomocą tego trybu można wykorzystać do szyfrowania 
 strumienia danych. Działanie podobne jak wyżej.
- CRT - tym trybem także można zaszyfrować strumień danych
 jednak wyróżnia się on tym, że aby odszyfrować jeden blok
   danych nie potrzeba odszyfrowywać wszystkich go poprzedzających.
 - ECB - najprostszy sposób szyfrowania blokowego. Każdy blok szyfrowany osobno.
  Szyfr ten nie powinien być stosowany.
- OFB - kolejna metoda szyfrowania strumieni danych.


Algorytmy szyfrowania

> Szyfr Cezara
Szyfr monoalfabetyczny, przesuwający, symetryczny, ograniczony.
Szyfr Cezara jest jednym z najstarszych sposobów szyfrowania wiadomości jaki znamy. Używał go Juliusz Cezar w korespondencji z Cyceronem. Polegał on na tym, że zamiast każdej litery pisał literę znajdującą się 3 miejsca dalej. Przy użyciu alfabetu łacińskiego wyglądało by to następująco:

klucz:
ABCDEFGHIJKLMNOPRSTUWXYZ
DEFGHIJKLMNOPRSTUWXYZABC

przykład:
przed: ALAMAKOTA
po: DODPDNSXA

  Szyfr ten jest jednym z najprostszych do złamania, gdyż jego klucz ma ilość możliwości równą ilości liter w użytym alfabecie. Wzór definiujący ten algorytm to:

D = (A + klucz) mod 26
A = (D - klucz) mod 26

gdzie "D" jest zaszyfrowanym znakiem, "A" znakiem przed zakodowaniem, a "mod" resztą z dzielenia.

Wariantem szyfru cezara jest ROT13 i ROT47, gdzie przesunięcie znaków wynosi odpowiednio 13 i 47 pozycji.

> Szyfr Cardano
  Jest to po prostu szyfr monoalfabetyczny, podstawieniowy, symetryczny. 

klucz:
ABCDEFGHIJKLMNOPRSTUWXYZ
WERTYUIOPASDFGHJKLZXCBNM

przykład:
przed: ALAMAKOTA
  po: WDWFWSHZW

W = f1(A)
A = f2(W)

> Szyfr Vigenere'a
Przykład szyfru polialfabetycznego, symetrycznego, podstawieniowego. 
Kolejne znaki informacji szyfrowane są przez kolejne znaki klucza. Gdy długość klucza jest mniejsza od długości wiadomości ( a tak jest w większości przypadków ), kolejne znaki klucza pobierane są od początku.

> AtBash
AtBash jest szyfrem polialfabetycznym, podstawieniowym, symetrycznym.
Jego działanie polega na zamianie kolejnych liter na litery leżące po drugiej stronie alfabetu i oddalone od końca o tyle samo co znak źródłowy od początku alfabetu. Szyfr jest tak prosty, że nie gwarantuje żadnego bezpieczeństwa

> XOR
Kolejny algorytm podstawieniowy, symetryczny.
Chociaż XOR (zwany też alternatywą wykluczającą lub binarnym sumowaniem) stanowi sam w sobie algorytm szyfrujący, to częściej stosowany jest jako element innego bardziej skomplikowanego szyfru, gdyż sam nie gwarantuje wystarczającego bezpieczeństwa. Wyjątkiem jest wersja XOR’a, One Time-Pad, gdzie spełnionych jest kilka ważnych warunków. XOR w swojej czystej postaci działa następująco:

0 XOR 0 = 0
1 XOR 1 = 0
0 XOR 1 = 1
1 XOR 0 = 1

Aby zaszyfrować informacje należy wpierw zamienić tekst na informację binarną, a następnie kolejne bity poddać operacji XOR razem z kolejnymi bitami hasła. 

Przykład: 
Szyfrowanie:
Tekst jawny: 0100 1010
Hasło: 0100 1000 
Szyfrogram: 0000 0010

Deszyfrowanie:
Szyfrogram: 0000 0010
Hasło: 0100 1000

M XOR K = C
C XOR K = M

Zaszyfrowana wiadomość binarna jest następnie zamieniana z powrotem na tekstową. Aby odszyfrować wiadomość należy powtórzyć całą informację.

> One Time-Pad
  Najważniejszą cechą tego algorytmu szyfrującego jest to, że jest on jedynym bezwarunkowo bezpiecznym szyfrem jaki stworzył człowiek. Zostało to matematycznie udowodnione w 1949 przez prof. Shannon'a. Wynalazcą tego szyfru jest Gilbert Vernam. Został on wykorzystany między innymi do szyfrowania połączenia Białego Domu z Moskwą. Algorytm ten jest niczym innym jak XOR'em lub szyfrem Vigenere'a, tyle że hasło użyte do szyfrowania/deszyfrowania wiadomości musi spełnić 3 warunki:

• musi być jedno razowe

• jego długość musi być równa lub większa od długości szyfrowanej wiadomości
• musi być losowe

Efektem spełnienia tych warunków, jest brak możliwości przeprowadzenia kryptoanalizy wiadomości zaszyfrowanej tym algorytmem. W przypadku próby odgadnięcia treści wiadomości, napastnik natrafi na wiele znaczących słów, ale nie będzie w stanie odkryć które z nich są treścią wiadomości.

  Najtrudniejszym do spełnienia warunkiem, jest warunek trzeci. Wbrew pozorom "losowe" ciągi znaków, takie jakie generuje komputer w oparci o aktualny stan procesora, lub czas systemowy, nie są naprawdę losowe, tak samo jak losowy nie będzie ciąg znaków powstały w skutek stykania w klawiaturę. Istnieją jednak generatory pseudo-losowych ciągów, takie jak BBS czy Schamira. 

> Macierz (kwadrat)
  Ten sposób szyfrowania opiera się na geometrii. Aby zaszyfrować wiadomość przepisujemy jej kolejne znaki do kolejnych macierzy ustawionych np. w kwadrat. Następnie spisujemy znaki lecz kolumnami, nie wierszami. Aby odszyfrować informacje trzeba cały proces powtórzyć.

> Blowfish
  Blowfish jest algorytmem powstałym w 1993 roku, mającym być bezpłatną alternatywą do, istniejących wówczas komercyjnych szyfrów. Jest to algorytm blokowy (operuje na 64-bitowych blokach), używającym kluczy od 32 do 448 bitów. Dzięki specjalnej budowie, jest on szczególnie wytrzymały na ataki brute-force. Jeżeli koszt ataku bezpośredniego dla typowych algorytmów wynosi 2^k * B ( gdzie k to długość klucza, a B koszt zakodowania bloku ) to dla Blowfisha wynosi on 2 ^ (k + 9) * B. 

> DES
  Z angielskiego Standard Szyfrowania Danych (Data Encryption Standard). Ten 56-bitowy algorytm został stworzony prze IBMa, a następnie zmodyfikowany przez NSA. Jako standard amerykański, został uznany w 1977 roku. Algorytm ten nie jest do końca bezpieczny, bowiem dysponując sprzętem wartym ponad milion dolarów, można złamać wiadomość zaszyfrowaną DES'em w niecałe 35 minut. Pierwsze łamanie DES'a zajęło 39 dni, później w 1998 roku już tylko 3 dni.

> RSA
  Pierwszy i zarazem najpopularniejszy system kryptografii asymetrycznej. Utworzony został przez 3 matematyków Revest'a, Shamir'a i Adleman'a, skąd pochodzi nazwa algorytmu. Skuteczność działania tego szyfru polega na trudności jaką sprawia faktoryzacja dużych liczb. RSA wykorzystywany jest m.in. do podpisów cyfrowych. Do maja 2004 roku udały się ataki na klucze o długości do 600 bitów. Zagrożeniem dla RSA mogłyby stać się komputery kwantowe, które mogłyby wykonać algorytm faktoryzacji (Shora) dużo szybciej niż 'tradycyjne' komputery.

> MD5
Jest to tak zwany algorytm haszujący. Celem jego działania, jest utworzenie 128 bitowego skrótu z wiadomości. Jednak najważniejsze jest to by nie dało się utworzyć dwóch identycznych skrótów z dwóch różnych wiadomości. W trakcie tworzenia skrótu, algorytm wykorzystuje odpowiednie funkcje haszujące. Algorytm MD5 (Massage-Digest 5) został opracowany w 1991 roku. Na początku 2004 roku znaleziono poważne wady w tym algorytmie.

Bezpieczeństwo szyfrów

Metody łamania szyfrów

> Metoda Brutalna (Bezpośrednia, brute-force, metoda czołgowa)
  Jest to chyba najbardziej prymitywna metoda łamania szyfrów. Polega ona na sprawdzaniu wszystkich możliwych kluczy, aż do rozkodowania wiadomości. Mimo swojej prostoty, w połączeniu z olbrzymią mocą obliczeniową wielu współpracujących komputerów przynosi w wielu przypadkach pożądane efekty. Ataki bezpośrednie możemy przeprowadzać względem zarówno szyfrów symetrycznych jak i asymetrycznych. Wyjątkowo przydatna jest znajomość par tekstu jawnego i zakodowanego szyfrogramu lub fragmentu szyfrogramu. Algorytm brute-force jest tym bardziej wydajny im bardziej ograniczony jest zbiór możliwych kluczy. Dobry klucz powinien być wygenerowany przy pomocy pseudo-losowego algorytmu i zawierać oprócz liter(małych i dużych), cyfry i znaki specjalne. Nie trzeba wspominać o tym, że prawidłowy klucz NIE MOŻE być słowem występującym w słowniku. Czas łamania szyfru zależy też od złożoności klucza:
  Jeżeli przyjmiemy ,że k to długość klucza a T to czas wykonywania pojedynczej operacji to maksymalny czas łamania szyfru możemy określić wzorem:

2^k * T

Większość klucz zostaje znalezionych w połowie czasu więc czas ten w większości przypadków wynosi:

2^(k-1) * T

Tak więc czas łamania 32-bitowego szyfru na komputerze zdolnym wykonać 100000 operacji na sekundę wyniesie:

2^(31) * 10^(-6) * s ~ 36 minut

48-bitowy szyfr, przy użyciu 1000 takich komputerów zostanie złamany w:

2^(47) * 10^(-3) * 10^(-6) * s ~ 39 godzin

  Łamanie 56-bitowego szyfru zajęło by przy użyciu tego samego sprzętu:

2^(55) * 10^(-3) * 10^(-6) * s ~ 416 dni

Natomiast 128-bitowy szyfr, mając do dyspozycji 1000 razy więce komputerów (1 000 000) został by złamany po:

2^(127) * 10^(-6) * 10^(-9) * s ~11 000 000 000 000 000 lat, czyli 500 tysięcy czasów życia wszechświata.

> Metody Statystyczne
  Bardziej wyszukaną grupą metod łamania szyfrów są metody statystyczne. Opierają się one na szczególnej budowie każdego języka ludzkiego, a szczególniej na częstości występowania konkretnych liter. Okazuje się niektóre litery występują zdecydowanie częściej, a inne rzadziej. W języku angielskim wygląda to następująco: E (13%), T(9%), A, O, I, N, R. W języku polskim metoda ta będzie trochę mniej skuteczna, gdyż nie ma w nim specjalnie wyróżniających się liter. Pierwsze jest A i I (po 9%) a dalej O i E (około 7,5 %). Na ataki z tej grupy podatne są szczególnie szyfry podstawieniowe. Kryptoanaliza statystyczna jest obecnie podstawowym narzędziem służącym sprawdzaniu jakości algorytmów szyfrujących.

> Występowanie par lub trójek
Wariant metody statystycznej.
  
> Test Kasiskiego i indeks koincydencji

> Łamanie z szyfrogramem
> Łamanie ze znanym szyfrem i tekstem jawnym
> Łamanie z wybranym tekstem jawnym
> Łamanie z adaptacyjnie wybranym tekstem jawnym
> Łamanie z wybranym szyfrogramem
> Łamanie z wybranym kluczem
> Łamanie z wykorzystaniem czasu wykonywania

> Kategorie łamania szyfrów
  Niejaki Lars Knudens podzielił łamanie szyfrów na kategorie:
- całkowite złamanie szyfru - znalezienie właściwego klucza do odszyfrowania wiadomości.
- ogólne wnioskowanie - znalezienie alternatywnego algorytmu nie wymagającego znajomości klucza.
- lokalne wnioskowanie - odszyfrowanie wiadomości bez znajomości klucza.
- częściowe wnioskowanie - znalezienie drobnych informacji o kluczu i tekście jawnym.
 
> Szyfry obliczeniowo bezpieczne
Są to szyfry odporne na ataki bruteforce. Posiadają tak wielką liczbę kombinacji, że praktycznie ni możliwe jest ich złamanie tym sposobem.

> Szyfry bezwarunkowo bezpieczne
Są to szyfry, w których przypadku, przechwycenie dowolnej liczby szyfrogramów, nie daje możliwości określić tekstu jawnego.