krypto3.rtf

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ą. Najprostrze z nich opierają sie 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 strunktury 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ć conajmniej 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 geometrzycznej (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ąch 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 poprzedających.

- ECB -              najprostrzy sposób szyfrowania blokowego. Każdy blok szyfrowany osobno.

              Szyfr ten nie powinien być stosowany.

- OFB -               kolejna metoda szyfrowania strumieni danych.

> Wybrane algorytmy

W tym dziale przedstawione zostaną ogólnikowo przykładowe algorytmy, stosowane zarówno w historii jak i współcześnie.

> Szyfry historyczne

> 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 najprostyszych 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 poprostu 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 urzyte 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ą naprawde losowe, tak samo jak losowy nie bedzię 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śc przepisujemi 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órzyc.

> Blowfish

Blowfish jest algorytmem powstałym w 1993 roku, mającym być bezpłatną alternatywą do, istaniejących wówaczas komercyjnych szyfrów. Jest to algorytm blokowy (operuje na 64-bitowych blokach), używjącym kluczy od 32 do 448 bitów. Dzieki specjalnej budowie, jest on szczególnie wytrzymały na ataki brute-force. Jezeli 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 Standart Szyfrowania Danych (Data Encryption Standard). Ten 56-biowy algorytm został stworzony prze IBMa, a następnie zmodyfikowany przez NSA. Jako standart amerykański, został uznany w 1977 roku. Algrotym ten nie jest do końca bezpieczny, bowiem dysponując sprzętem wartym ponad milon dolarów, można złamać wiadomość zaszyfrowaną DES'em w niecałe 35 minut. Pierwsze łamanie DES'a zajeł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ść dziłania tego szyfru polega na trundoś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 moglyby 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 kompyuterów przynosi w wielu przypadkach porzą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 pomoco pseudo-losowgo 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 pojedyńczej 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 zajeł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 szczegulnej budowie każdego języka ludzkiego, a szczególniej na częstości występowanai konkretynych 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 troche mniej skuteczna, gdyż nie ma w nim specjalnie wyrużnają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żacym sprawdzaniu jakosci algorytmów szyfrujacych.

> 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 kateogrie:

- 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.