5. Szyfry i kryptografia

5.7. Szyfry podstawieniowe

Prosty szyfr podstawieniowy (ang. simple substitution cipher) to szyfr blokowy o długości bloku 1. Niech V1 będzie ustalonym alfabetem a f : V1 V2 funkcją różnowartościową (z reguły V1 V2 ). Jeśli wiadomość jawna m m1m2 ...mr , to szyfrogram c f (m1) f (m2 )... f (mr) . Funkcja f jest tu kluczem szyfrującym a f 1 kluczem deszyfrującym.

Klasycznym przykładem takiego szyfru jest szyfr Cezara,. który będzie omówiony dokładniej w dalszym ciągu podrozdziału.

Polialfabetyczny szyfr podstawieniowy (ang. polyalphabetic substitution cipher) to szyfr blokowy o długości bloku t. Niech V1 będzie ustalonym alfabetem a fi : V1 V2 , funkcją różnowartościową dla i 1,2,..., t (z reguły V1 V2 ). Jeśli wiadomość jawna m m1m2 ...mt to szyfrogram c f1 (m1 ) f2 (m2 )... ft (mt ) . Funkcja f1 f 2 ... ft jest tu kluczem szyfrującym a f1 1 f2 1 ... ft 1 kluczem deszyfrującym.

Przykład: Rozważmy dla ustalenia uwagi 26 literowy alfabet języka angielskiego V {<i>a</i>, <i>b</i>, <i>c</i>,..., <i>z</i>} . Klasycznym szyfrem Cezara nazywamy szyfr podstawieniowy, w którym V1 V2 V i funkcją definiującą podstawienia jest permutacja : V V , gdzie

\pi = \binom{ \text {a b c d e ... y z}}{ \text {d e f g h ... b c} }

Jeśli utożsamimy litery z liczbami z pierścienia Z26 na zasadzie a ~ 0, b~1, c~2, d~3, ..., y~24, z~25 , to widać, że:

(x) x 3(mod 26)

co odpowiada braniu jako wartości permutacji  liczby – litery znajdującej się o 3 pozycje w prawo (modulo 26) w stosunku do liczby – litery argumentu.

Ogólnie rzecz biorąc, jeśli alfabet V jest n literowy, to możemy V utożsamić z Zn i zdefiniować permutację : V V wzorem:

(x) (x r)(mod n)

Kryptogram wiadomości jawnej m m1m2 m3 ...ms otrzymujemy więc jako

(m1 ) (m2 ) (m3 )... (ms )

Tak zdefiniowany szyfr, nazywamy szyfrem Cezara z przesunięciem r. Oczywiście r jest kluczem szyfrującym i deszyfrującym jednocześnie. Kluczem w szyfrze Cezara jest więc liczba naturalna ze zbioru Zn

Przykład: Załóżmy, że m jest licznością alfabetu jawnego V tzn. m cardV , np. = 26 w przypadku języka angielskiego.

Identyfikujemy:

a 1 czyli identyfikujemy kolejne litery z kolejnymi liczbami

b 2 naturalnymi ze zbioru {1,2,...,26}

...

z 26

W przypadku alfabetu polskiego liter jest trochę więcej, bo mamy ą, ć, ę, ł, ń, ś , ó, ź. Klucz k k1 k2 ...kt V t , t N powtarzamy, jeśli trzeba, okresowo.

Szyfr Vigenere`a zadajemy tak: definiujemy odwzorowane fi : V V wzorem:

fi (a) \overset{df}{=} a m ki

dla tekstu jawnego m m1m2 ...mk

c = f_{[1]_t} (m_1)f_{[2]_t}(m_2)...f_{[k]_t} (m_k)

Przykład: Okres klucza 5, klucz k = OKRES

m = ENCYKLOPEDIA TECHNIKI
k = OKRESOKRESOKRESOKRESO
                                                      
c = TYUCC ZGJWXLRYXRSENCX

Oczywiście szyfr Cezara jest szczególnym przypadkiem szyfru Vigenere`a.