Algorytmy i Struktury Danych - Szyfrowanie z pseudolosowym odstępem

SPIS TREŚCI

Tematy pomocnicze

Podrozdziały

Projekt generatora LCG
Szyfrowanie
Deszyfrowanie

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

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.

Na początek: podrozdziału strony

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.

Zmienne 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 – 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.

Na początek: podrozdziału strony

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.

Zmienne 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

Na początek: podrozdziału strony

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.

Szyfrowanie z pseudolosowym odstępem

Problem

Projekt generatora LCG

Szyfrowanie

Algorytm szyfrowania z pseudolosowym odstępem

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Deszyfrowanie

Algorytm deszyfrowania z pseudolosowym odstępem

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy