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

©2020 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 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.

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.

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

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:
wykonuj kroki K02...K04
przetwarzamy kolejne znaki łańcucha s
K02:     X  ← ( a  × X  + c  ) mod m obliczamy nową liczbę pseudolosową
K03:     Jeśli ( s [ i  ] < 'A' ) ∨ ( s [ i  ] > 'Z' ),
    to następny obieg pętli K01
pomijamy znaki nie będące 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
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.

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

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:
wykonuj kroki K02...K04
przetwarzamy kolejne znaki łańcucha s
K02:     X ← ( a  × X  + c  ) mod m obliczamy nową liczbę pseudolosową
K03:     Jeśli ( s [ i  ] < 'A' ) ∨ ( s [ i  ] > 'Z' ),
    to następny obieg pętli K01
pomijamy znaki nie będące 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
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
©2020 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.