Szyfrowanie tekstów - szyfr z pseudolosowym odstępem

Szyfr Cezara posiada kilka wad, które uniemożliwiają praktyczne zastosowanie. Po pierwsze wystarczy odkryć wartość przesunięcia kodów (oryginalnie wynosi ono 3, lecz można je zmieniać w zakresie od 1 do 25), aby rozszyfrować całą wiadomość. W tym celu należy przeprowadzić 25 prób, co dla współczesnych komputerów nie stanowi żadnego problemu.

 

Przesunięcie kodów Szyfr
0 ALA MA KOTA
 + 1 BMB NB LPUB
 + 2 CNC OC MQVC
 + 3 DOD PD NRWD
 + 4 EPE QE OSXE
 + 5 FQF RF PTYF

 

Po drugie, z uwagi na stałe przesunięcie kodów, te same znaki są zawsze szyfrowane tak samo. Jeśli na przykład zaszyfrujemy AAAAAAAAAA, to otrzymamy ciąg DDDDDDDDDD.

Aby znacząco utrudnić rozszyfrowanie wiadomości zaprojektujemy szyfr, w którym przesunięcie kodów będzie się zmieniało w zakresie od 0 do 25 w trakcie szyfrowania znaków. Do tego celu potrzebna nam jest możliwość generacji tych samych ciągów liczbowych przy szyfrowaniu oraz rozszyfrowywaniu. Wykorzystamy generator pseudolosowy LCG, który startując od określonego ziarna tworzy zawsze te same ciągi liczb pseudolosowych. Kluczem szyfrującym będą parametry generatora oraz wartość ziarna pseudolosowego. Parametry generatora: moduł m, mnożnik a oraz przyrost c zostaną na stałe zdefiniowane w programie (możesz je zmienić, wtedy zmianie ulegnie sposób szyfrowania). Użytkownik będzie jedynie podawał wartość ziarna pseudolosowego Xo.

 

Projekt generatora LCG

Im większy zakres generowanych liczb pseudolosowych, tym dłuższy okres powtarzania tworzonego ciągu. W efekcie trudniejsze jest złamanie szyfru. Kryptologia potrafi bez większych problemów łamać szyfry oparte na prostych generatorach pseudolosowych z uwagi na ich właściwości, dlatego nie są one stosowane w praktycznych systemach szyfrowania - użyty generator musi być kryptologicznie bezpieczny. My się tym nie będziemy przejmowali, ponieważ nasz projekt jest czysto dydaktyczny.

 

Wybieramy zakres od 0 do Xmax = 3956279999.

Moduł m jest równy Xmax + 1 = 3956280000

Czynniki pierwsze modułu m = 3956280000 = 2 × 2 × 2 × 2 × 2 × 2 × 3 × 5 × 5 × 5 × 5 × 32969

Przyrost c = 7 × 11 × 17 = 1309

Mnożnik a - 1 = 2 × 2 × 3 × 5 × 32969 = 1978140, stąd a = 1978141.

Podsumowując otrzymujemy następujący generator LCG:

LCG(3956280000,1978141,1309,Xo)

Ziarno Xo jest w zakresie od 0 do Xmax, czyli od 0 do 3956279999. Liczba ta będzie naszym kluczem szyfrującym.

 

Szyfrowanie

Zasada szyfrowania jest następująca:

 

Odczytujemy klucz i wprowadzamy go do ziarna pseudolosowego naszego generatora LCG. Na podstawie tego klucza generator LCG będzie tworzył ściśle określony ciąg liczb pseudolosowych. Odczytujemy następnie łańcuch s, który ma zostać zaszyfrowany. Zamieniamy wszystkie litery z małych na duże (nasz algorytm szyfruje tylko duże znaki). Przetwarzamy kolejne znaki tego łańcucha. Dla każdego znaku generujemy liczbę pseudolosową X. Teraz sprawdzamy, czy przetwarzany znak łańcucha s jest dużą literą od A do Z. Jeśli tak, to obliczamy jego kod ch i przekształcamy go zgodnie ze wzorem:

 

Niech c jest kodem szyfrowanej litery od A do Z. Litera A ma kod ASCII równy 65, litera Z ma kod 90.

1. Sprowadzamy kod c do zakresu od 0 do 25:

        cc - 65

2. Dodajemy pseudolosowe przesunięcie:

        cc - 65 + X mod 26

3. Wykonujemy operację modulo 26, aby wartość wyrażenia sprowadzić do zakresu od 0 do 25

        c ← (c - 65 + X mod 26) mod 26

4. Wracamy z powrotem do kodów ASCII

        c ← 65 + (c - 65+ X mod 26) mod 26

 

Wynik jest kodem zaszyfrowanego znaku - umieszczamy go w łańcuchu s na miejscu przetwarzanego znaku i kontynuujemy te same operacje aż do przetworzenia wszystkich znaków w s. Na końcu łańcuch s zwracamy jako wynik szyfrowania.

 

Algorytm szyfrowania z pseudolosowym odstępem

Wejście

Klucz X
Parametry generatora LCG: m, a i c
Tablica znakowa s[ ]

Wyjście:

Zaszyfrowany łańcuch s

Zmienne pomocnicze:
i  -  indeks
Lista kroków:
Krok 1: i ← 0 ; rozpoczynamy szyfrowanie od pierwszego znaku w tablicy
Krok 2: Jeśli s[i] = 0, zakończ ; sprawdzamy koniec tekstu
Krok 3: Jeśli s[i] < "A' lub s[i] > 'Z', to idź do kroku 6 ; sprawdzamy, czy szyfrowany znak jest dużą literą
Krok 4: X ← (a × X + c) mod m ; obliczamy liczbę pseudolosową
Krok 5: s[i] ← 65 + (s[i] - 65 + X mod 26) mod 26) ; szyfrujemy znak
Krok 6: ii + 1 ; przechodzimy do następnego znaku w tablicy
Krok 7: Idź do kroku 2  

 

Szyfrowanie kodem o pseudolosowym odstępie
(C)2011 mgr Jerzy Wałaszek


Klucz 0 ... 3956279999 :


.

 

Deszyfrowanie

Zasada rozszyfrowywania jest prawie identyczna jak przy szyfrowaniu. Jedyna różnica leży we wzorze obliczania kodu znaku z kodu szyfru:

 

Niech c będzie kodem rozszyfrowywanej litery od A do Z.

1. Sprowadzamy kod do zakresu od 0 do 25:

        cc - 65

2. Odejmujemy pseudolosowe przesunięcie, dodając moduł 26 i przesunięcie:

        cc - 65 + 26 + X mod 26

3. Wykonujemy operację modulo:

        c ← (c - 39 + X mod 26) mod 26

4. Wracamy z powrotem do kodów ASCII

        c ← 65 + (c - 39 + X mod 26) mod 26

 

Algorytm deszyfrowania z pseudolosowym odstępem

Wejście

Klucz X
Parametry generatora LCG: m, a i c
Tablica z zaszyfrowanym tekstem s[ ]

Wyjście:

Rozszyfrowany łańcuch s

Zmienne pomocnicze:
i  -  indeks
Lista kroków:
Krok 1: i ← 0 ; rozpoczynamy szyfrowanie od pierwszego znaku w tablicy
Krok 2: Jeśli s[i] = 0, zakończ ; sprawdzamy koniec tekstu
Krok 3: Jeśli s[i] < "A' lub s[i] > 'Z', to idź do kroku 6 ; sprawdzamy, czy szyfrowany znak jest dużą literą
Krok 4: X ← (a × X + c) mod m ; obliczamy liczbę pseudolosową
Krok 5: s[i] ← 65 + (s[i] - 39 - X mod 26) mod 26 ; rozszyfrujemy znak
Krok 6: ii + 1 ; przechodzimy do następnego znaku w tablicy
Krok 7: Idź do kroku 2  

 

Deszyfrowanie kodu o pseudolosowym odstępie
(C)2011 mgr Jerzy Wałaszek


Klucz 0 ... 3956279999 :


.

 

Program odczytuje najpierw rodzaj pracy. 0 oznacza szyfrowanie, 1 oznacza rozszyfrowywanie. Następnie czytany jest klucz X oraz tekst.

 

// Szyfrowanie z pseudolosowym odstępem
// (C)2011 I LO w Tarnowie
//--------------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned long long X,a,c,m;
    int w,i;
    char s[1024];

    m = 3956280000UL;    // parametry generatora LCG
    a = 1978141;
    c = 1309;

    cin >> w;            // rodzaj pracy

    cin >> X;            // klucz

    cin.ignore(256,'\n');

    cin.getline(s,1024); // tekst lub szyfr

    for(i = 0; s[i]; i++)
    {
        if(s[i] >= 'A' && s[i] <= 'Z')
        {
            X = (a * X + c) % m;
            if(w) s[i] = 65 + (s[i] - 39 - X % 26) % 26;
            else  s[i] = 65 + (s[i] - 65 + X % 26) % 26;
        }
    }

    cout << s << endl;

    return 0;
}

0
123
ATAK W NOCY OD STRONY RZEKI
YQSR S QGHI BT VLIUGM UJJQF

1
123
YQSR S QGHI BT VLIUGM UJJQF
ATAK W NOCY OD STRONY RZEKI

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.