Szyfr przestawieniowy - transpozycja

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 niewiele 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, zazwyczaj 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ć, że 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. Nawet jeśli 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ć, że ten algorytm nie ma „mocy”, ale jest prosty w implementacji i wystarczająco komplikuje dłuższe teksty. Dodatkową zaletą jest to, że 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, że 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 < iostream >
#include < stdlib.h >
#include < fstream >

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 < 500 ; iIndexT++) // zapisanie tablicy z tekstem jawnym w celu
        sText[iIndexT] = 0 ; // późniejszego ustalenia warunku na 0

    cout << "\t---------------------------------------" << endl ;
    cout << "\tDlugosc wpisanego tekstu < 500 znakow" << endl ;
    cout << "\tKlucz < dlugosc tekstu jawnego" << endl ;
    cout << "\tKlucz szyfrujacy musi byc liczba calkowita" << endl ;
    cout << "\tProgram nie obsluguje polskich znakow dialektycznych" << endl ;
    cout << "\t---------------------------------------" << endl ;
    cout << "\n\nWpisz tekst ktory chcesz zaszyfrowac:" << endl ;

    gets(sText) ; // pobranie tekstu jawnego

    cout << "\nKlucz szyfrujacy:\t" ;
    cin >> iKey ; // pobranie kluczaa szyfrującego
    cout << "\nTekst jawny:\t\t" << sText << endl ;
    int iTextLenthTemp = strlen(sText) ; // dlugość teksu przed ewentualnym rozszerzeniem
    cout << "Dlugosc tekstu:\t\t" << iTextLenthTemp << " znakow" ;

    if ((strlen(sText) % iKey) != 0) // ważna procedura w tej metodzie szyfrowania
        { // odpowiedzialna za dodanie znaków spacji (32)
        int iAdd = (strlen(sText) % iKey) ; // na koniec tekstu jawnego w celu
        int iAddText = iKey - iAdd ; // spełnienia warunku 
        char sAddText[iAddText] ; // (długość tekstu jawnego % klucz szyfrujący = 0)
        for (int i=0 ; i < iAddText ; i++) // w innym przypadku nie bedzie możliwości deszyfracji
            sText[iTextLenthTemp++] = 32 ; // kryptogramu
        }  

    iIndexT = 0 ; // ustawinie tekstu jawnego na pierwszy znak
    iIndexC = 0 ; // ustawienie tablicy z kryptogramem na pierwszy znak

    for (int i=0 ; i < iKey ; i++) // pętla szyfrująca, a raczej przestawiająca
        { // znaki w tekście jawnym odpowiedzialna również 
        iIndexT = i ; // za zapisanie zaszyfrowanego tekstu w zmiennej sCrypt
        while (sText[iIndexT] != 0)
            {
            sCrypt[iIndexC++] = sText[iIndexT] ;
            iIndexT += iKey ;
            }
        }

    iTextLenght = strlen(sText) ; // pobranie długości tekstu jawnego po rozszerzeniu
    sCrypt[iTextLenght] = 0 ; // zapis 0 na koncu kryptogramu - na wszelki wypadek

    cout << "\n\nKryptogram:\t\t" << sCrypt ;  
    cout << "\nDlugosc kryptogramu:\t" << strlen(sCrypt) << " znakow" << endl ;

    bdCrypt.open("crypt.txt", ios::out) ;
    if (bdCrypt.fail())
        cout << "ERROR:\tNie mozna otworzyc pliku !!!" << endl ;
    else
        {  
        bdCrypt << sCrypt ;
        cout << "\n\nKoniec programu - kryptogram zapisany w pliku crypt.txt" << endl << endl ;
        bdCrypt.close() ;
        }  

    system("PAUSE") ;

    return 0 ;
    }

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 < iostream >
#include < stdlib.h >

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 << "\t-----------------------------------" << endl ;
     cout << "\tMetoda brute force dla transpozycji" << endl ;
     cout << "\tWymagany plik crypt.txt" << endl ;
     cout << "\tProgram nie obsluguje polskich znakow dialektycznych" << endl ;
     cout << "\t-----------------------------------" << endl ;

     for (int i=0 ; i < 500 ; i++)    // czyszczenie miejsca na kryptogram
         sCrypt[i] = 0 ;   

     if ((bdCrypt = fopen("crypt.txt", "r")) == NULL)    // otwarcie pliku crypt.txt
         cout << "ERROR:\tNie mozna otworzyc pliku !!!" << endl ;
     else
         {
         fgets(sCrypt, 500, bdCrypt) ;        // pobranie kryptogram z pliku
         fclose(bdCrypt) ;                    // zamknięcie pliku
         }

     iCryptLenght = strlen(sCrypt) ;  // pobranie długość kryptogramu
     cout << "\nKryptogram:\t\t" << sCrypt << endl ;
     cout << "Dlugosc kryptogramu:\t" << iCryptLenght << endl << endl ;
     cout << "\nSprawdz ktory z odszyfrowanych tekstow jest poprawny:" << endl << endl ;
     for (int j=0 ; j < iCryptLenght ; j++)    // pętla o iteracji dlugość kryptogramu
         fnInsertKey(sCrypt, ++iKey) ;      // podstawianie kolejnych kluczy
     system("PAUSE");
     return 0;
     }

void fnInsertKey(char sCryptTmp[500], int iKey)  // funkcja deszyfrująca 
     {
     char sText[500] ;   // miejsce na rozszyfrowany text
     int iIndexC = 0 ;   // index kryptogramu
     int iIndexT = 0 ;   // index rozszyfrowanego textu
     int iKeyTemp = 0 ;  // właściwy klucz deszyfrujący

     for (int i=0 ; i<500 ; i++)    // czyszczenie miejsca na rozszyfrowany text
         sText[i] = 0 ;

     for (int i=0 ; i < iKey ; i++)    // przejście do kolejnych kolumn w macierzy
         {
         iIndexC = i ;
         while(sCryptTmp[iIndexC] != 0)     // warunek końca tekstu
             {
             sText[iIndexT++] = sCryptTmp[iIndexC] ; // wstawianie kolejnych znaków
             iIndexC += iKey ;
             }
         } 
     if ((strlen(sText) % iKey) == 0)   // nie pokazuje kluczy które nie są liczbami całkowitymi
         {
         iKeyTemp = strlen(sText) / iKey ; 
         cout << "klucz:\t" << iKeyTemp << "\todszyfrowany tekst:\t" << sText << endl ;
         }   

     return ;
     }

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śli wymyślisz szybszą i skuteczniejszą napisz.