Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

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.

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

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 X_max  = 3956279999.

Moduł m  jest równy X_max  + 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,X_o)

Ziarno X_o  jest w zakresie od 0 do X_max, 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:

        c  ← c  - 65

2. Dodajemy pseudolosowe przesunięcie:

        c  ← c  - 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:

Lista kroków:

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:

        c  ← c  - 65

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

        c  ← c  - 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:

Lista kroków:

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;
}

---

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

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

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe