Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemOpracować algorytm szyfrujący i deszyfrujący 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 |
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
LCG(3956280000,1978141,1309,Xo)
Ziarno Xo
jest w zakresie
Zasada szyfrowania jest następująca:
Odczytujemy klucz i wprowadzamy go do ziarna pseudolosowego naszego
Wynik jest kodem zaszyfrowanego znaku – umieszczamy go
K01: Dla i = 0,1,…,|s|-1: ; przetwarzamy kolejne znaki łańcucha s wykonuj kroki K02…K04 K02: X ← (a×X+c) mod m ; obliczamy nową liczbę pseudolosową K03: Jeśli (s[i] < 'A') ∨ (s[i] > 'Z'), ; pomijamy znaki nie będące to następny obieg pętli K01 ; literami od A do Z K04: s[i] ← znak(65+(kod(s[i])-65+X mod 26) mod 26) ; szyfrujemy K05: Pisz s ; wyprowadzamy szyfr K06: Zakończ ; gotowe
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program odczytuje kolejno
|
Pascal// Szyfrowanie z pseudolosowym odstępem // Data: 20.08.2008 // (C)2020 mgr Jerzy Wałaszek //----------------------------- program prg; var s : string; i : integer; X, a, m, c : qword; begin // definiujemy generator LCG m := 3956280000; a := 1978141; c := 1309; // odczytujemy klucz i wiersz znaków readln(X); readln(s); // zamieniamy małe litery na duże s := upcase(s); // szyfrujemy for i := 1 to length(s) do begin // obliczamy kolejną liczbę pseudolosową X := (a*X+c) mod m; // szyfrujemy literkę if s[i] in ['A'..'Z'] then s[i] := chr(65+(ord(s[i])-65+X mod 26) mod 26); end; // wypisujemy zaszyfrowany tekst writeln(s); writeln; end. |
// Szyfrowanie z pseudolosowym odstępem // Data: 20.08.2008 // (C)2020 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <string> using namespace std; int main() { string s; int i; unsigned long long X, a, m, c; // definiujemy generator LCG m = 3956280000ull; a = 1978141ull; c = 1309ull; // odczytujemy klucz i wiersz znaków cin >> X; cin.ignore(256,'\n'); getline(cin,s); // szyfrujemy for(i = 0; i < s.length(); i++) { // obliczamy kolejną liczbę pseudolosową X = (a*X+c)%m; // szyfrujemy literkę s[i] = toupper(s[i]); if((s[i] >= 'A') && (s[i] <= 'Z')) s[i] = 65+(s[i]-65+X%26)%26; } // wypisujemy zaszyfrowany tekst cout << s << endl << endl; return 0; } |
Basic' Szyfrowanie z pseudolosowym odstępem ' Data: 20.08.2008 ' (C)2020 mgr Jerzy Wałaszek '----------------------------- Dim As String s Dim As Integer i Dim As Ulongint X, a, m, c ' definiujemy generator LCG m = 3956280000 a = 1978141 c = 1309 ' odczytujemy klucz i wiersz znaków Input X Line Input s ' zamieniamy małe litery na duże s = Ucase (s) ' szyfrujemy For i = 1 To Len(s) ' obliczamy kolejną liczbę pseudolosową X = (a*X+c) Mod m ' szyfrujemy literkę If Mid(s,i,1) >= "A" And Mid(s,i,1) <= "Z" Then_ Mid(s,i,1) = Chr(65+(Asc(Mid(s,i,1))-65+X Mod 26) Mod 26) Next ' wypisujemy zaszyfrowany tekst Print s Print End |
Python
(dodatek)# Szyfrowanie z pseudolosowym odstępem # Data: 26.03.2024 # (C)2024 mgr Jerzy Wałaszek #----------------------------- # definiujemy generator LCG m = 3956280000 a = 1978141 c = 1309 # odczytujemy klucz i wiersz znaków X = int(input()) s = input().upper() # szyfrujemy for i in range(len(s)): # obliczamy kolejną liczbę pseudolosową X = (a * X + c) % m # szyfrujemy literkę if (s[i] >= "A") and (s[i] <= "Z"): s = s[:i]+chr(65+(ord(s[i])-65+X%26)%26)+s[i+1:] # wypisujemy zaszyfrowany tekst print(s) print() |
Wynik: |
1001 AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA WRELMD MUVJQVHPJOXUE ESVRDSNBN V SSXQ SNIRED 1002 AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA FKHGVU HHGMNMAQCVYHP PRWKILEOI U BDOP VSDUPE 1003 AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA ODKRUL MURPUNDRFSJUK AGHDNOLRN J UOFE YHOXAV |
Zwróć uwagę, iż dla różnych kluczy otrzymujemy zupełnie inne szyfry. Co więcej powtarzające się literki (tutaj A przed i za tekstem) zostają zaszyfrowane w różne znaki – to zaleta szyfru z pseudolosowym odstępem. Aby ukryć odstępy między wyrazami, które pozwalają zidentyfikować słowa, można wpisywać w ich miejsce wybraną literkę (np. X – tak postępowali operatorzy niemieckich maszyn Enigma w czasie II Wojny Światowej). Wtedy szyfr stanie się jednolitym blokiem liter.
Zasada rozszyfrowywania jest prawie identyczna jak przy szyfrowaniu. Jedyna różnica leży we wzorze obliczania kodu znaku z kodu szyfru:
ch = 65+(ch-39-X mod 26) mod 26 |
K01: Dla i = 0,1,…,|s|-1: ; przetwarzamy kolejne znaki łańcucha s wykonuj kroki K02…K04 K02: X ← (a×X+c) mod m ; obliczamy nową liczbę pseudolosową K03: Jeśli (s[i] < 'A') ∨ (s[i] > 'Z'), ; pomijamy znaki nie będące to następny obieg pętli K01 ; literami od A do Z K04: s[i] ← znak(65+(kod(s[i])-39-X mod 26) mod 26) ; rozszyfrowujemy K05: Pisz s ; wyprowadzamy tekst K06: Zakończ ; gotowe
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program odczytuje kolejno klucz
|
Pascal// Deszyfrowanie z pseudolosowym odstępem // Data: 20.08.2008 // (C)2020 mgr Jerzy Wałaszek //----------------------------- program prg; var s : string; i : integer; X, a, m, c : qword; begin // definiujemy generator LCG m := 3956280000; a := 1978141; c := 1309; // odczytujemy klucz i szyfr readln(X); readln(s); // zamieniamy małe litery na duże s := upcase(s); // deszyfrujemy for i := 1 to length(s) do begin // obliczamy kolejną liczbę pseudolosową X := (a * X + c) mod m; // deszyfrujemy literkę if s[i] in ['A'..'Z'] then s[i] := chr(65+(ord(s[i])-39-X mod 26) mod 26); end; // wypisujemy rozszyfrowany tekst writeln(s); writeln; end. |
// Deszyfrowanie z pseudolosowym odstępem // Data: 20.08.2008 // (C)2020 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <string> using namespace std; int main() { string s; int i; unsigned long long X, a, m, c; // definiujemy generator LCG m = 3956280000ull; a = 1978141ull; c = 1309ull; // odczytujemy klucz i szyfr cin >> X; cin.ignore(256,'\n'); getline(cin,s); // deszyfrujemy for(i = 0; i < s.length(); i++) { // obliczamy kolejną liczbę pseudolosową X = (a * X + c) % m; // deszyfrujemy literkę s[i] = toupper(s[i]); if((s[i] >= 'A') && (s[i] <= 'Z')) s[i] = 65+(s[i]-39-X%26)% 26; } // wypisujemy rozszyfrowany tekst cout << s << endl << endl; return 0; } |
Basic' Deszyfrowanie z pseudolosowym odstępem ' Data: 20.08.2008 ' (C)2020 mgr Jerzy Wałaszek '----------------------------- Dim As String s Dim As Integer i Dim As Ulongint X, a, m, c ' definiujemy generator LCG m = 3956280000 a = 1978141 c = 1309 ' odczytujemy klucz i szyfr Input X Line Input s ' zamieniamy małe litery na duże s = Ucase(s) ' deszyfrujemy For i = 1 To Len(s) ' obliczamy kolejną liczbę pseudolosową X = (a * X + c) Mod m ' deszyfrujemy literkę If Mid(s,i,1) >= "A" And Mid(s,i,1) <= "Z" Then_ Mid(s,i,1) = Chr(65+(Asc(Mid(s,i,1))-39-X Mod 26) Mod 26) Next ' wypisujemy rozszyfrowany tekst Print s Print End |
Python
(dodatek)# Deszyfrowanie z pseudolosowym odstępem # Data: 27.03.2024 # (C)2024 mgr Jerzy Wałaszek #----------------------------- # definiujemy generator LCG m = 3956280000 a = 1978141 c = 1309 # odczytujemy klucz i wiersz znaków X = int(input()) s = input().upper() # szyfrujemy for i in range(len(s)): # obliczamy kolejną liczbę pseudolosową X = (a * X + c) % m # szyfrujemy literkę if (s[i] >= "A") and (s[i] <= "Z"): s = s[:i]+chr(65+(ord(s[i])-39-X%26)%26)+s[i+1:] # wypisujemy zaszyfrowany tekst print(s) print() |
Wynik: |
1001 WRELMD MUVJQVHPJOXUE ESVRDSNBN V SSXQ SNIRED AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA 1002 FKHGVU HHGMNMAQCVYHP PRWKILEOI U BDOP VSDUPE AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA 1003 ODKRUL MURPUNDRFSJUK AGHDNOLRN J UOFE YHOXAV AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.