Szyfry przestawieniowe

Szyfry przestawieniowe zmieniają porządek znaków według pewnego schematu (tradycyjnie za pomocą pewnej figury). Szyfrowanie tekstu odbywa się w dwóch krokach:

zapis odczyt

Tekst jawny * figura * tekst zaszyfrowany

W pierwszy m kroku tekst jawny wpisuje się do figury w sposób określony pewną „ścieżką zapisu”. W drugim kroku tekst zaszyfrowany tekst zaszyfrowany odczytuje się z figury zgodnie z pewną „ścieżką odczytu”. Klucz składa się z figury oraz ścieżek zapisu i odczytu. W szyfrach macierzowych figurą geometryczną jest macierz dwuwymiarowa. Przy tzw. przestawieniu kolumnowym tekst jawny zapisuje się do macierzy wierszami. Tekst zaszyfrowany powstaje przez odczyt kolumnami w określonym porządku. Kluczem szyfru jest rozmiar macierzy i liczby wskazujące kolejność odczytu kolumn.

Przykład:

Tekst jawny KRYPTOANALIZA zaszyfrowano szyfrem macierzowym z kluczem [3 x 5, 4,2,5,1,3] i otrzymano:

tekst zaszyfrowany: PARAZTLKOIYNA

W szyfrze płotowym litery tekstu jawnego zapisuje się w taki sposób, aby utworzyć kształt przypominający wierzchołek płotu zbudowanego ze sztachet. Tekst zaszyfrowany otrzymuje się odczytując kolejne wiersze tak utworzonej konstrukcji. Kluczem szyfrowania jest tzw. wysokość płotu.

Przykład: Tekst jawny MARYSIA NIE ZALICZYŁA ĆWICZEŃ, wysokość płotu 4

M

A

L

A

E

A

I

N

A

I

Ł

Ć

Z

Ń

R

S

I

Z

C

Y

W

C

Y

E

Z

I

Tekst zaszyfrowany: MALAE AINAIŁĆZŃ RSIZCYWC YEZI

W szyfrach przestawieniowych z kluczem permutacyjnym zamieniana jest kolejność znaków tekstu jawnego przy zastosowaniu stałego okresu d. Niech Z_d będzie zbiorem liczb całkowitych od 1 do d, zaś f: Z_d * Z_d będzie permutacją na zbiorze Z_d. Kluczem szyfru permutacyjnego jest para K = (d, f). Kolejne bloki d znaków są szyfrowane przez dokonanie permutacji znaków zgodnie z f. Tekst jawny M=m₁ ... m_d m_d+1 ... jest szyfrowany jako E_K(M)=m_f(1) ... m_f(d) m_d+f(1) ... . W procesie deszyfrowania stosuje się permutację odwrotną.

Przykład: Niech d=4, zaś f jest permutacją (kluczem) o wartości (2431), tj. f(1)=4, f(2)=1, f(3)=3, f(4)=2. Wówczas tekst jawny M = KRYP TOAN ALIZ A zostanie zaszyfrowany jako: RPYK ONAT LZIA A.

Szyfry podstawieniowe

W szyfrach podstawieniowych bity, znaki lub bloki znaków są zastępowane ich ustalonymi zamiennikami. W prostym szyfrze podstawieniowym każdą literę tekstu zastępuje się literą otrzymaną w wyniku przesunięcia litery źródłowej o k pozycji alfabetu, przy czym alfabet tworzy cykl zamknięty, tzn. po Z następuje A. Kluczem szyfru jest k. Szyfr ten nosi nazwę szyfru Cezara.

Przykład: Niech klucz k = 3 oraz

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

Tekst jawny: GALAPAGOS, tekst zaszyfrowany: JDODSDJRV

Istnieją 4 typy szyfrów podstawieniowych:

• Monoalfabetyczne,

• Homofoniczne,

• Wieloalfabetyczne,

• Poligramowe.

Szyfry monoalfabetyczne zmieniają każdy znak uporządkowanego alfabetu jawnego A na odpowiedni znak uporządkowanego alfabetu szyfru C. Zazwyczaj C powstaje przez prostą zmianę kolejności znaków w alfabecie A.

Niech A={a₀, ..., a_n-1} wówczas C={f(a₀), ..., f(a_n-1)}, gdzie f: A * C jest wzajemnie jednoznacznym odwzorowaniem każdego znaku z A na znak w C. Kluczem jest alfabet C lub (równoważnie) funkcja f.

Przykład:

Szyfr monoalfabetyczny z kluczem AKTORKA (eliminujemy powtarzające się litery):

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

K

T

O

R

B

C

D

E

F

G

H

I

J

L

M

N

P

Q

S

U

V

W

X

Y

Z

Tekst jawny: KRYPTOANALIZA, tekst zaszyfrowany: GPYMSLAJAHEZA

W przykładzie użyto tzw. alfabetu mieszanego według klucz. Oznacza to, iż alfabet szyfru powstał z liter słowa kluczowego (z którego najpierw należy wyeliminować powtórzenia) oraz z pozostałych liter alfabetu.

Szyfry oparte na alfabetach przesuniętych przesuwają litery alfabetu w prawo o k pozycji, modulo wielkość alfabetu:

f(a) = (a+k) mod n,

gdzie:
a - szyfrowany znak (numer jego pozycji w alfabecie - numeracja od 0 ze względu na operację modulo),

k - przesunięcie, n - rozmiar alfabetu. Przykładem szyfru tego typu jest szyfr Cezara.

Bardziej złożone przekształcenia alfabetu jawnego oparte są na mnożeniach: f(a)=(a*k)mod n, przy czym k i n są liczbami względnie pierwszymi (tj. ich największy wspólny podzielnik wynosi 1). Jeśli n i k nie są liczbami względnie pierwszymi, to wielu literom tekstu jawnego będzie odpowiadała ta sama litera tekstu zaszyfrowanego i nie wszystkie litery będą występować w alfabecie szyfru.

Szyfry homofoniczne odwzorowują każdy znak a alfabetu jawnego na zestaw elementów f(a) tekstu zaszyfrowanego (elementy te zwane są homofonami). Odwzorowanie tekstu jawnego na zaszyfrowany można określić jako funkcję: f: A * 2^C. Znak c_i podstawiany w miejsce litery jawnej m_i jest losowo wybierany ze zbioru homofonów f(m_i).

Przykład:

Litery jawne	Homofony
0	05, 87, 63
1	71, 59, 29,
2	23, 60, 94
3	40, 78, 56
4	18, 03, 42,
5	19, 24, 75
6	52, 12, 37
7	34, 36, 81
8	26, 45, 13
9	67, 91, 08

Tekst jawny: 1 0 2 4 0 2, tekst zaszyfrowany: 71 87 94 18 05 60

Szyfry homofoniczne wyższych stopni. Dla większości szyfrów prawdziwe jest twierdzenie, że gdy posiadamy wystarczająco dużą ilość tekstu zaszyfrowanego C, to teoretycznie możliwe jest złamanie tego szyfru. Wynika t o z faktu, że istnieje tylko jeden klucz K, którego użycie do deszyfrowania daje w wyniku zrozumiały tekst jawny, podczas gdy inne klucze dają w wyniku jedynie bezsensowny ciąg liter. Możliwe jest jednak stworzenie szyfrów homofonicznych wyższego stopnia takich, że kryptogram można zdeszyfrować na więcej niż 1 sensowny tekst jawny, jeżeli zastosuje się różne klucze deszyfrowania.

Aby skonstruować szyfr homofoniczny drugiego stopnia (tj. taki, w którym każdemu tekstowi tajnemu odpowiadają dwa teksty jawne) należy wpisać do macierzy K o wymiarach n xn liczby od 1 do n² (w sposób losowy). Wiersze i kolumny macierzy odpowiadają znakom alfabetu jawnego. Dla każdego znaku a*A, wiersz macierzy K tworzy jeden zbiór homofonów f₁(a), zaś kolumna - drugi zbiór f₂(a). Stąd zestaw wierszy odpowiada jednemu kluczowi, a kolumn - drugiemu. Właściwy tekst jawny M szyfrujemy wraz z tekstem fałszywym X, tworząc kryptogram C w taki sposób, że c_i = K[m_i, x_i] dla i =1, 2, ... Każdy element c_i można zdeszyfrować uzyskując m_i lub x_i.

Przykład: Niech A = {A, K, Ł, W}. Tworzymy macierz 4 x 4 (bo card(A) = 4) i wpisujemy do niej losowo liczby od 1 do 16.

	A	K	Ł	W
A	10	14	7	4
K	8	6	2	13
Ł	12	1	16	9
W	3	11	15	5

Właściwy tekst jawny ŁAWKA szyfrujemy razem z fałszywym KAWAŁ następująco:

M = ŁAWKA

X = KAWAŁ

C = 1 10 5 8 7

Szyfry wieloalfabetyczne. Ponieważ w szyfrach monoalfabetycznych stosuje się jedno odwzorowanie tekstu jawnego na tekst zaszyfrowany, kryptogram zachowuje rozkład częstości występowania znaków tekstu jawnego. Szyfr homofoniczny ukrywa ten rozkład dzięki przypisaniu danej literze tekstu jawnego jednego z wielu symboli szyfrowych. Natomiast szyfr wieloalfabetyczny ukrywa rozkład częstotliwości przez użycie wielu podstawień.

W większości szyfry wieloalfabetyczne są okresowymi szyframi podstawieniowymi o okresie d. Mamy d alfabetów szyfrowych C₁, C₂, ..., C_d. Niech f_i: A * C_i stanowi odwzorowanie alfabetu tekstu jawnego A w i-ty alfabet szyfru C_i dla 1 <= i <=d. Tekst jawny M = m₁ ... m_d m_d+1 ... m_2d ... szyfruje się podstawiając sekwencję odwzorowań f₁, ..., f_d dla każdych d znaków: E_K(M) = f₁(m₁), ... f_d(m_d) f₁(m_d+1) ... f_d(m_2d) ... W szczególnym przypadku, gdy d = 1 szyfr staje się monoalfabetyczny, co odpowiada podstawieniu prostemu.

Szyfr Vigenere'a jest popularnym szyfrem podstawieniowym opartym na alfabetach przesuniętych. Klucz szyfru K tworzy sekwencja liter K = k₁ ... k_d, przy czym k_i daje liczbę przesunięć w i-tym alfabecie, tj. f_i(a) = (a+k_i) mod n.

Przykład: Tekst jawny LOKOMOTYWA zaszyfrujemy szyfrem Vigenere'a z kluczem LIST.

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

M = LOKO MOTY WA

K = LI S T L I S T L I

E_K(M) = WWCH XWLR H I

Ogólnie (pozycja (m_i)+pozycja (k_i)) mod n

Dużym ułatwieniem przy szyfrowaniu i deszyfrowaniu tekstu jest tablica Vigenere'a. Dla litery tekstu jawnego a i litery klucza k literą kryptogramu c jest znak z kolumny a wiersza k. Mając zaś literę kryptogramu c, odczytujemy literę tekstu jawnego a jako kolumnę zawierającą c w wierszu k.

Szyfry podstawieniowe poligramowe (Szyfr Playfaira). Szyfr Playfaira jest bigramowym szyfrem podstawieniowym, którego kluczem jest macierz o wymiarach 5 x 5 zawierająca wszystkie (oprócz J) litery alfabetu.

H	A	R	P	S
I	C	O	D	B
E	F	G	K	L
M	N	Q	T	U
V	W	X	Y	Z

Każdą parę liter teksu jawnego m₁ i m₂ szyfruje się według następujących reguł:

1. Jeśli m₁ i m₂ znajduje się w tym samym wierszu, to c₁i c₂ są znakami z prawej strony m₁ i m₂, przy czym pierwszą kolumnę traktuje się jako położoną na prawo od ostatniej

2. Jeśli m₁ i m₂ znajdują się w tej samej kolumnie, to c₁ i c₂ są znakami położonymi poniżej, przy czym pierwszy wiersz traktuje się jako leżący pod ostatnim

3. Jeśli m₁ i m₂ są w różnych wierszach i kolumnach, to c₁ i c₂ są brane z przeciwległych rogów prostokąta wyznaczonego przez m₁ i m₂, przy czym c₁ pochodzi z wiersza zawierającego m₁, c₂ zaś - z wiersza zawierającego m₂

4. Jeśli m₁=m₂, to do tekstu jawnego między te litery wstawia się nieznaczącą literę (np. X) co eliminuje powtórzenia

5. Jeśli tekst jawny ma nieparzystą liczbę znaków, to na końcu tekstu jawnego dopisuje się nieznaczącą literę.

Przykład:

Szyfrujemy słowo KRYPTOANALIZA. Ponieważ tekst jawny zawiera nieparzystą liczbę liter dopisujemy do niego nic nie znaczącą literę (np. X) KR YP TO AN AL IZ AX.

H	A	R	P	S
I	C	O	D	B
E	F	G	K	L
M	N	Q	T	U
V	W	X	Y	Z

Tekst zaszyfrowany:

GP PD QD CW SF BV RW

WYKŁAD - Kryptografia (szyfry przestawieniowe)

5

---