Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

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
I LO w Tarnowie

Szyfrowanie z pseudolosowym odstępem

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Opracować 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.

Przesunięcie 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. Sposób projektowania generatora LCG opisaliśmy w rozdziale o liczbach pseudolosowych.

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.


Na początek:  podrozdziału   strony 

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:

ch = 65+(ch-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:

X : klucz; X ∈ N.
m, a, c : parametry generatora LCG; m, a, c ∈ N.
s : łańcuch tekstowy.

Wyjście:

Zaszyfrowany łańcuch s.

Elementy pomocnicze:

i : indeks; i ∈ N.
kod(x) : zwraca kod litery x.
znak(x) : zamienia kod x na odpowiadający mu znak ASCII.

Lista kroków:

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

Przykładowe programy

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 X oraz łańcuch s, który szyfruje kodem o pseudolosowym odstępie i wypisuje wynik. Parametry generatora LCG są zdefiniowane wewnątrz programu. Zakres kluczy wynosi od 0 do 3956279999.
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.
C++
// 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 ASCII – 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.

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

Klucz 0 … 3956279999 :

.


Na początek:  podrozdziału   strony 

Deszyfrowanie

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

Algorytm deszyfrowania z pseudolosowym odstępem

Wejście:

X : klucz; X ∈ N.
m, a, c : parametry generatora LCG; m, a, c ∈ N.
s : zaszyfrowany łańcuch tekstowy.

Wyjście:

Rozszyfrowany łańcuch s.

Elementy pomocnicze:

i : indeks; i ∈ N.
kod(x) : zwraca kod litery x.
znak(x) : zamienia kod x na odpowiadający mu znak ASCII.

Lista kroków:

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

Przykładowe programy

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 X oraz łańcuch s, który rozszyfrowuje kodem o pseudolosowym odstępie i wypisuje wynik. Parametry generatora LCG są zdefiniowane wewnątrz programu. Zakres kluczy wynosi od 0 do 3956279999.
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.
C++
// 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

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

Klucz 0 … 3956279999 :

.


Na początek:  podrozdziału   strony 
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: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.