Szyfr przestawieniowy - transpozycja

fivewithfour.blogspot.com 1 dekada temu

Dzisiejszy odcinek w całości poświęcony będzie kryptologii. Kryptologia to nauka o szyfrach i metodach ich łamania. Postaram się opisać jedną z najprostszych metod szyfrowania oraz sposób na jej złamanie. Do tekstu dołączone są źródła programu szyfrującego zadany tekst metodą transpozycji oraz plik źródłowy programu łamiącego zaszyfrowany tekst.

Szyfrator

Brutal

WPROWADZENIE

Potrzeba szyfrowania informacji jest kilka młodsza od samej informacji. Sposoby na ukrycie informacji w pozornie niezrozumiałym tekście są nam znane od tysięcy lat. Jednym z nich jest metoda przestawieniowa zwana również transpozycją. Aby jasno przedstawić na czym polega ta metoda posłużę się tabelkami. Na początku należy jednak wyjaśnić podstawowe pojęcia:
- Tekst jawny – tekst, który chcemy ukryć i poddać go zaszyfrowaniu,
- Kryptogram – tekst, który jawny po zaszyfrowaniu, zwykle trudne do zrozumienia dane tekstowe,
- Algorytm szyfrujący – metoda, która posłużyła do przetworzenia tekstu jawnego na kryptogram,
- Klucz szyfrujący – informacja niezbędna dla poprawnego odszyfrowania danych znanym algorytmem, najpilniej strzeżona rzecz w kryptografii.
Metoda transpozycji polega na przestawianiu znaków w tekście jawnym w ściśle określony sposób i według zadanego klucza. Najlepiej wyjaśni to przykład:
- Tekst jawny – „Windows to bezpieczny OS ;-)”
- Klucz szyfrujący – 5
- Kryptogram (zależny od klucza szyfrującego) – „Ww iy;isbe -n ecO)dtzzS oopn”
Wyraźnie widać, iż kryptogram jest trudny do odczytania i nie łatwo jest wywnioskować sens tekstu jawnego. Metoda przestawieniowa działa tak:
1. Tekst jawny

W i n d o w s t o b e z p i e c z n y O S ; - )

Składa się z 28 znaków, które można zapisać w macierzy (wektorze)

2. Klucz szyfrujący – wybrałem liczbę 5, której działanie wystarczająco skomplikowało kryptogram – na jego podstawie trudno wyznaczyć tekst jawny.
3. Szyfrowanie metodą przestawieniową – polega na zamianie kolejności znaków w zdaniu. Wszystkie znaki kryptogramu występują w tekście jawnym tylko raz. W sumie metoda transpozycji to taki prosty algorytm mieszający. Aby przedstawić sposób tworzenia kryptogramu z tekstu jawnego z zadanym kluczem szyfrującym, posłużę się macierzami. Ilość kolumn w macierzy jest taka jak klucz szyfrujący. Na tym opiera się szyfrowanie przestawieniowe – wpisujemy tekst jawny w macierz wzdłuż wierszy macierzy, a odczytujemy kryptogram wzdłuż kolumn macierzy. Bardzo ważnym elementem jest uzupełnienie pustych miejsc w macierzy tak aby:

długość tekstu jawnego % klucz szyfrujący = 0

Jeśli brakuje kilku znaków w macierzy, najlepiej zapisać na jej końcu znaki SPACE kod 32d w ASCII, co w rezultacie dopisze niewidoczne znaki na koniec tekstu jawnego. Przed każdym szyfrowaniem należy sprawdzić czy reszta z dzielenia długości tekstu jawnego przez wartość klucza szyfrującego jest równa 0. Jest to warunek konieczny do poprawnego odszyfrowania kryptogramu.

Odczytując wiersze otrzymamy tekst jawny, a odczytując kolumny kryptogram. Kryptogram zawiera dodatkowe przerwy będące efektem uzupełnienia dwóch ostatnich pól macierzy, której wymiary to 5x6 – czyli 30 pól, a tekst jawny zawiera 28 znaków + 2 znaki SPACE na końcu tekstu.

Ww iy;isbe -n ecO)dtzzS oopn

POZIOM BEZPIECZEŃSTWA

Na pierwszy rzut oka kryptogram wydaj się być skomplikowany i trudny do deszyfracji bez znajomości klucza, którym zaszyfrowany jest tekst jawny. Najważniejszą informacją jaką posiadamy to algorytm szyfrujący i oczywiści kryptogram. To w zupełności wystarczy do rozszyfrowania kryptogramu i poznania tekstu jawnego. Opisywany przypadek ma zapoznać czytelnika z prostym szyfrowaniem, w rzeczywistości kryptoanalitycy często nie posiadają całego kryptogramu i nie wiedzą jakim algorytmem zaszyfrowany jest tekst jawny. choćby jeżeli wiedzą to nie jest to algorytm przestawieniowy w opisywanej tutaj formie. Siła opisywanego algorytmu to 1 w skali do 100. Przestrzeń możliwych kluczy teoretycznie jest nieograniczona, ale w praktyce kluczem szyfrującym mogą być liczby w zakresu:

Długość tekstu jawnego –2

Nie ma sensu stosować klucza o wartości 1 oraz klucza o wartości równej długości tekstu jawnego. W praktyce tekst jawny w ogóle nie będzie zaszyfrowany. Wyraźnie widać, iż ten algorytm nie ma „mocy”, ale jest prosty w implementacji i wystarczająco komplikuje dłuższe teksty. Dodatkową zaletą jest to, iż tworzenie kryptogramu może zacząć się z innego miejsca macierzy niż tutaj opisywany. Dla wprawnego oka łatwo będzie ustalić klucz szyfrujący, ale nie o tym będę pisał.

PRAKTYKA

Opracowując ten materiał pomyślałem, iż dobrym rozwiązaniem będzie napisanie programu szyfratora i programu łamiącego algorytm przestawieniowy. Oba programy napisałem przy pomocy DevC++, są to konsole umożliwiające poprawne przećwiczenie działania algorytmu.
Szyfrator pozwala wpisać dowolny tekst o długości do ok. 500 znaków. Podczas implementacji szyfratora udało mi się uniknąć działań na macierzach, co ułatwi zrozumienie kodu. Program składa się z jednej funkcji, kilku pętli i warunków. Pomimo pozornego chaosu, kod jest czytelny i łatwy do prześledzenia. Kod dostępny w code.5w4

#include #include #include using namespace std; int main() { char sText[500] ; // tekst jawny char sCrypt[500] ; // miejsce na kryptogram int iKey, iIndexT, iTextLenght ; // klucz, index tekstu jawnego, dlugość tekstu jawnego int iIndexC ; // index kryptogramu ofstream bdCrypt ; // wskażnik do pliku z kryptogramem for (iIndexT=0 ; iIndexT > iKey ; // pobranie kluczaa szyfrującego cout

Nie trudno stworzyć deszyfrator dla tej metody szyfrowania. Moim zadaniem było napisanie programu, który będzie na podstawie kryptogramu wyliczał tekst jawny i znajdował klucz, który posłużył do zaszyfrowania informacji. W kryptoanalizie najskuteczniejszą metodą łamania zabezpieczeń jest wypróbowanie całej przestrzeni kluczy szyfrujących – oczywiście mam tutaj na myśli algorytmy symetryczne, w których za szyfrowanie i deszyfrowanie informacji odpowiada ten sam klucz. Crakerzy znają tą metodę jako brute force, przedstawiałem ją podczas łamania nietypowego zabezpieczenia napisanego przez Lukiana. W przypadku opisywanej transpozycji przestrzeń kluczy jest niewielka – około 500 kluczy i nie ma sensu zastanawiać się nad optymalizacją algorytmu łamiącego. Należy deszyfrować kryptogram, wypróbowując wszystkie możliwe klucze, do czasu aż na ekranie pokaże się sensowny tekst, który będzie tekstem jawnym. Kod dostępny w code.5w4

#include #include using namespace std; // standardowa przestrzeń nazw void fnInsertKey(char*, int) ; // prototyp funkcji odpowiedzialnej za deszyfracje int main() { char sCrypt[500] ; // kryptogram pobrany z pliku int iCryptLenght = 0 ; // dlugość kryptogramu int iKey = 0 ; // klucz szyfrujący FILE *bdCrypt ; // wskaźnik pliku crypt.txt cout Plik źródłowy jest łatwy do odczytania. Program składa się z dwóch funkcji, głównej oraz funkcji deszyfrującej, która jest wywoływana tyle razy ile możliwych jest kluczy deszyfrujących. Na ekranie konsoli pojawiają się tylko te klucze, których wynik:

Długość kryptogramu % klucz szyfrujący = 0

Na tej podstawie, można przeprowadzić optymalizacje metody łamania kryptogramu, ponieważ jak widać, zaledwie 1/3 możliwych kluczy spełnia warunek. Dla nas nie ma to większego znaczenia, ponieważ przestrzeń kluczy jest niewielka i komputer radzi sobie dobrze ze wszystkimi możliwymi kluczami. Znak % oznacza w języku C++ resztę z dzielenia. Trudno napisać kod który mógłby rozpoznawać złamany kryptogram pod kątem jego sensowności, dlatego podawane są wszystkie możliwe rozwiązania dla podstawianych kluczy, aby użytkownik, mógł sam określić, które z rozwiązań jest tekstem jawnym. W rzeczywistości istnieją algorytmy sprawdzające logiczność rozszyfrowanego kryptogramu, robi się to po to aby ograniczyć ilość sprawdzanych kluczy, których czasami może być ogromna ilość. Nie można złamać trudnych algorytmów szyfrujących z dnia na dzień, może w przyszłości ktoś wymyśli metodę lepszą niż sprawdzenie całej przestrzeni kluczy szyfrujących. Zdecydowałem się opisać prosty algorytm szyfrujący i skuteczną metodę jego łamania. jeżeli wymyślisz szybszą i skuteczniejszą napisz.

Idź do oryginalnego materiału