Metody kryptoanalizy

1. Kryptoanaliza metodą anagramową.

Metoda ta wykorzystywana jest szczególnie przy łamaniu szyfrów przestawieniowych. Rozpoznanie, czy dany szyfr jest szyfrem przestawieniowym jest stosunkowo łatwe, ponieważ częstotliwość występowania znaków w tekście jawnym jest identyczna jak ich częstotliwość w tekście zaszyfrowanym.

Kryptoanaliza tą metodą polega na wykorzystaniu tablic częstości występowania digramów oraz trigramów (kombinacji dwu- i trzyliterowych). Tablice te pomagają w ustaleniu właściwej kolejności znaków w tekście szyfrowanym przestawieniowo.

2. Analiza częstości.

Metodę tą wykorzystuje się przy analizie szyfrów przestawieniowych. Analiza polega na porównaniu częstości występowania liter w tekście zaszyfrowanym z częstościami oczekiwanymi. Znając częstość występowania liter dla danego języka czy nawet tematyki, można z dużym prawdopodobieństwem przyporządkować litery z tekstu tajnego do liter z tekstu jawnego. Dużym ułatwieniem dla kryptoanalityka jest znajomość digramów i trigramów.

3. Atak brutalny.

Atak brutalny na system kryptograficzny polega na przeanalizowaniu wszystkich kombinacji klucza. Metoda ta jest bardzo czasochłonna oraz w przypadku współczesnych systemów kryptograficznych bardzo nieefektywna i zawodna.

Można to przeanalizować na przykładzie prostego szyfru Cezara lub szyfru ROT-13. W przypadku języka angielskiego przestrzeń klucza zostaje w tym wypadku ograniczona do 25 kombinacji. Analiza polega na sprawdzeniu kolejnych podstawień w alfabecie szyfrującym przesuniętym kolejno o 1 do 25 pozycji.

W przypadku prostych szyfrów, jak np. Cezara czy ROT-13analiza jest dość szybka, ponieważ sposób szyfrowania jest stały. Jeżeli jednak przeprowadzamy atak na szyfr, w którym alfabet szyfrujący jest dowolną kombinacją odwzorowań znaku alfabetu jawnego w znak alfabetu szyfrującego, ilość obliczeń i kombinacji klucza drastycznie rośnie. W takiej sytuacji mamy do sprawdzenia aż 26! kombinacji. Wprawdzie współczesne szyfrowanie opiera się na systemie binarnym, jednak liczba kombinacji w kluczu 56-bitowym równa jest 256. Jeżeli założymy, że superszybki komputer jest w stanie sprawdzić milion kluczy na sekundę to odszukanie właściwego klucza może zająć mu ok. 2000 lat.

4. Kryptoanaliza różnicowa.

Metoda ta opracowana została dla ośmiorundowej wersji algorytmu DES jednak w późniejszym czasie wykorzystywana do analizy innych szyfrów iteracyjnych, czyli takich, których działanie opiera się na wykonywanych kilkakrotnie tych samych obliczeniach (rundach). Polega ona na szyfrowaniu par tekstów jawnych z użyciem tego samego klucza. Pary te różnią się od siebie w określony sposób i są następnie analizowane w trakcie wykonywania kolejnych cykli algorytmu. Określone różnice pomiędzy tekstami jawnymi wiążą się z określonymi różnicami pomiędzy otrzymanymi szyfrogramami tworząc charakterystyki. W wyniku przejścia przez kilka cykli wyznaczają one ścieżkę pomiędzy cyklami.

Odkrycie to okazało się przełomowe, ponieważ metoda ta jako pierwsza pozwalała przełamać ośmiorundowy algorytm DES szybciej niż atakiem brutalnym. Późniejsze jednak analizy wykazały, iż właściwa, 16-rundowa wersja algorytmu DES radzi sobie z powodzeniem z tym typem kryptoanalizy.

Innym rodzajem ataku kryptoanalitycznego, zbliżonego do analizy różnicowej jest metoda powiązanych kluczy. Różnice w tym przypadku sprawdzane są między kluczami.

Kryptoanaliza.

Kryptoanaliza jest nauką oraz dziedziną badań zajmującą się metodami łamania szyfrów. Celem kryptoanalizy jest odnalezienie słabych stron systemu kryptograficznego w celu złamania szyfru lub jego obejścia. Szyfr można złamać, jeżeli na podstawie tekstu tajnego istnieje możliwość odtworzenia pierwotnego tekstu lub klucza. Odtworzenie klucza jest ponadto możliwe w przypadku posiadania obu tekstów – tajnego i jawnego.

Intencje działań kryptoanalityka mogą mieć dwa podłoża. Pierwszym są działania wrogie, mające na celu złamanie szyfru i odczytanie informacji lub odkrycie samego algorytmu szyfrowania. Drugim natomiast działaniem jest działanie przychylne, mające na celu badanie algorytmu szyfrowania oraz poznanie i usunięcie jego słabych stron, aby szyfr był możliwie jak najtrudniejszy do złamania.

Istnieje wiele typów ataków kryptoanalitycznych, jak również wiele ich klasyfikacji. Według najpowszechniej przyjętego podziału, rodzaje przełamywania szyfrów możemy podzielić następująco:

- atak bez tekstu jawnego (ze znanym szyfrogramem) – jest to sytuacja, kiedy kryptoanalityk ma do dyspozycji jedynie tekst tajny. Do odszyfrowania informacji potrzebne jest zatem określenie klucza. W tym wypadku mogą być też znane: metoda szyfrowania, język i tematyka tekstu jawnego czy słowa charakterystyczne dla tej tematyki z określonym prawdopodobieństwem wystąpienia.

- atak z tekstem jawnym – kryptoanalityk ma do dyspozycji parę tekstów: zaszyfrowany i jawny. Możliwe jest posiadanie kilku par takich tekstów.

- atak z wybranym tekstem jawnym – zaszyfrowany zostaje tekst jawny wybrany przez kryptoanalityka. W ten sposób dostępna jest para tekstów: zaszyfrowany i jawny, możliwe jest więc wyznaczenie klucza i metody szyfrowania.

- atak z wybranym tekstem tajnym – to sytuacja, w której kryptoanalitykowi udaje się uzyskać dostęp do aparatury deszyfrującej i przy jej pomocy odszyfrowanie tekstu.

Kryptografia.

Kryptografia jest nauką o układaniu systemów kryptograficznych (szyfrowaniu). W przeciwieństwie do steganografii nie ma na celu ukrycia istnienia wiadomości ale ukrycie jej znaczenia.

Najbardziej znanym w historii kryptografii podziałem szyfrów jest podział na dwie grupy: szyfry podstawieniowe oraz szyfry przestawieniowe[1].

   Szyfrem podstawieniowym nazywamy taki szyfr, w którym każdy znak w tekście szyfrowanym zostaje zastąpiony innym, umownym znakiem ale nie zmienia swojego miejsca w tekście. Takie podstawienie powoduje, iż tekst taki nie jest zrozumiały dla nikogo oprócz odbiorcy, który po odwróceniu podstawienia otrzymuje oryginalną wiadomość.

   Szyfrem przestawieniowym nazywamy szyfr, który tworzony jest poprzez przestawienie kolejności znaków w tekście szyfrowanym. Z tekstu szyfrowanego tworzony jest anagram.

Istnieją również połączenia obu typów szyfrów tworząc tzw. szyfry mieszane.

            Współczesna kryptografia nie stosuje szyfrów przestawieniowych z uwagi na pracochłonne i kłopotliwe przestawianie kolejności liter w długich tekstach. Z kolei anagramy tekstów krótkich są bardzo łatwe do odczytania. Więcej możliwości dają natomiast szyfry podstawieniowe, które możemy podzielić na:

- szyfry monoalfabetyczne – dla każdego znaku alfabetu jawnego przyporządkowany jest jeden ustalony znak alfabetu tajnego

-  szyfry homofoniczne – dla każdego znaku alfabetu jawnego przyporządkowana jest grupa znaków alfabetu tajnego

- szyfry polialfabetyczne – do szyfrowania używanych jest wiele alfabetów tajnych. Za pomocą jednego z tych alfabetów, wybranego w określony sposób, kodowany jest jeden znak z tekstu jawnego.

-  szyfry poligramowe – szyfrowane są grupy znaków. Dla każdej grupy znaków z tekstu jawnego przyporządkowana jest grupa z tekstu tajnego

            Najmniej bezpiecznymi z szyfrów podstawieniowych są szyfry monoalfabetyczne. W prosty sposób można je złamać za pomocą analizy częstości występowania znaków w tekście zaszyfrowanym i porównaniu jej do częstości występowania znaków w danym języku.

Odpowiednie jednak zastosowanie analizy częstości pozwala na złamanie również szyfrów homofonicznych, polialfabetycznych oraz poligramowych.

            Przez wiele lat rozwoju kryptografii wykorzystywano tylko takie algorytmy, w których zarówno szyfrowanie jak i deszyfrowanie odbywało się przy użyciu tego samego klucza. Pojawiał się w związku z tym problem dystrybucji klucza. Musiał on być bezpiecznie przekazywany, tak aby znany był tylko nadawcy oraz odbiorcy wiadomości. Rozwiązanie tego problemu przyniósł dopiero wiek XX, kiedy to pojawiły się szyfry, w których szyfrowanie i deszyfrowanie odbywało się przy użyciu odmiennych kluczy.

            W związku z tym pojawił się nowy podział szyfrów:

            - szyfry symetryczne – szyfrowanie i deszyfrowanie wiadomości odbywa się za pomocą tego samego klucza,

            - szyfry asymetryczne – szyfrowanie wiadomości odbywa się za pomocą klucza publicznego, zaś do odszyfrowania używany jest klucz prywatny.

            Era dynamicznego rozwoju komputerów przyczyniła się równocześnie do ogromnego postępu w dziedzinie kryptografii i zmieniła dotychczasowe metody szyfrowania. Podstawową zmianą było znaczne przyspieszenie samego procesu szyfrowania. Dotychczas używane metody oraz konstruowane maszyny szyfrujące były ogromnym ograniczeniem dla samej złożoności algorytmów szyfrujących. Przy użyciu komputera możliwa jest symulacja dowolnej maszyny szyfrującej. Skraca to znacznie czas szyfrowania, jak również sam proces konstrukcji urządzenia. Możliwa jest przy tym nawet symulacja urządzenia, którego fizyczne wykonanie byłoby niemożliwe.

Druga zasadnicza zmiana dotyczyła sposobu szyfrowania. Nastąpiło przejście z systemu szyfrowania liter i znaków na używany w systemach komputerowych system binarny. Opracowany został system przekształcania liter i znaków na ciągi zer i jedynek, znany obecnie jak kod ASCII. Po zastąpieniu ciągu znaków za pomocą kodu, proces samego szyfrowania jest identyczny jak wcześniej – przy pomocy klucza oraz algorytmu. Różnica polega natomiast na sposobie zapisywania – podstawowym elementem jest bit a nie znak.

W związku z użyciem komputerów pojawiła się kolejna, współczesna klasyfikacja szyfrów:

            - szyfry blokowe – szyfrują operując na blokach tekstu jawnego (ciągu binarnego) określonej długości,

            - szyfry strumieniowe – szyfrują pojedyńcze bity.

            Szyfry blokowe są procedurami szyfrującymi niewielkie bloki danych. Składają się one z kilkunastu prostych rund, w trakcie których wykonywane są po sobie różne proste operacje na bloku (przesunięcia, dodawanie, mnożenia itd.). Już po kilku rundach szyfr taki jest bardzo trudny do przeanalizowania.

Szyfry strumieniowe składają się z generatora ciągu kluczowego oraz elementu dodającego bity klucza do bitów tekstu jawnego. W taki sposób powstaje ciąg zaszyfrowany.  We współczesnych szyfrach najczęściej stosowane jest dodawanie modulo 2 (XOR).

---

[1] Rogowski J., Wykłady z kryptografii

Steganografia.

Steganografia to nauka o ukrywaniu informacji. Celem działań steganograficznych jest więc taki sposób przekazywania wiadomości, aby osoby postronne nie wiedziały o jej istnieniu.

Najróżniejsze techniki steganograficzne wykorzystywane były już od czasów starożytnych. Pierwsze informacje o używaniu tej techniki pochodzą z V w. p.n.e., kiedy to do pisania używane były drewniane tabliczki pokryte woskiem, na którym zapisywano tekst. Ukrywanie wiadomości odbywało się poprzez wyrycie tekstu na samej tabliczce, dopiero później pokrytej woskiem. Tak „nie zapisana” lub zapisana jakimś prostym tekstem woskowa tabliczka nie wzbudzała żadnych podejrzeń i bezpiecznie dostawała się do odbiorcy, który znając tą technikę mógł bez problemu odczytać ukrytą pod woskiem wiadomość[1].

W starożytnym Rzymie, Egipcie czy Chinach do ukrywania wiadomości stosowany był tzw. atrament sympatyczny. Wykonany był on z soków owocowych lub mleka i nie zostawiał żadnego śladu (był niewidoczny). Pomiędzy wierszami prostej, na ogół niewiele znaczącej wiadomości, wpisywana była treść tajnego przesłania. Odczytanie go było możliwe dopiero po podgrzaniu papirusu lub pergaminu.

Ciekawy sposób ukrywania wiadomości stosowany był przez armię niemiecką w czasie II wojny światowej. Informacje, które chcieli ukryć (teksty, mapy, rysunki, itd....) były układane najczęściej do formatu A4 i fotografowane. Następnie kliszę z taką fotografią pomniejszano do rozmiaru ok. mm² i przyklejano zamiast jednej z kropek w oficjalnym tekście.

W czasach współczesnych steganografia przeżywa znaczący rozwój, co jest możliwe przy wykorzystaniu niezliczonych możliwości jakie dają komputery. Powstają coraz to nowe sposoby ukrywania informacji, takie jak ukrywanie danych w plikach graficznych czy dźwiękowych. Wykorzystywane przy tym są naturalne ograniczenia ludzkich zmysłów. Pliki graficzne na przykład wykorzystują ograniczenia ludzkiego oka, którym nie możliwe jest zauważenie minimalnych różnic w odcieniach kolorów czy szarości. Informacje w plikach dźwiękowych natomiast, wykorzystują ograniczony zakres słyszalności dźwięku.

Wykorzystanie mediów potęguje jeszcze możliwości współczesnej steganografii. Dzięki internetowi, telewizji czy radiu ukrytą wiadomość można w ekspresowym tempie wysłać w dowolne miejsce na świecie. Obraz ukryty w pikselach innego obrazu, dźwięk wpleciony w inny dźwięk czy przekaz telewizyjny ukryty pomiędzy klatkami innego przekazu może w jednej chwili niezauważony dostać się do adresata, który bez problemu odczyta ukrytą wiadomość. Dodatkowo jednoczesne użycie tak zaawansowanych technik steganograficznych w połączeniu z zaawansowanymi technikami szyfrowania przesyłanych wiadomości daje potężną siłę tajnego przesyłania informacji we współczesnym świecie.

---

[1] Karbowski M., Podstawy kryptografii wydanie II

Kryptologia – nauka o ukrywaniu wiadomości.

Kryptologią nazywamy dziedzinę wiedzy poświęconą wszystkim formom tajnego zapisywania wiadomości.

W skład Kryptologii wchodzą:

- steganografia – nauka o ukrywaniu wiadomości oraz ich istnienia,

- kryptografia – nauka o ukrywaniu treści wiadomości (szyfrowaniu),

- kryptoanaliza – nauka o odczytywaniu zaszyfrowanego tekstu bez znajomości klucza.