Kryptograficzna

przygoda

01010 10001 11000 01111 10011
01110 00110 10001 00000 00101

01000 00010 11001 01101 00000
01111 10001 11001 11000 00110

01110 00011 00000

czyli całkiem inne szyfrowanie…

Autor:

phm. Michał Starosta HO

7 DSH „Cerber” im. gen. S.F. Sosabowskiego

Hufiec ZHP Nowy Tomyśl

[e-mail]

Spis tre

ś

ci

I.

II.

III.

IV.

V.

Czy nie zastanawiali

ś

cie si

ę

?...

Co b

ę

dzie nam potrzebne

Zaczynamy zabaw

ę

Szyfr zmieniaj

ą

cy alfabet

Szyfr Vigenere’a
Szyfr Playfair’a

Robi si

ę

powa

ż

nie;-)

ECB
CBC
CFB
Szyfr Feistella

Wytaczamy ostatni

ą

armat

ę

Szyfr afiniczny

Pomoce matematyczne
Dodawanie binarne – dodawanie inaczej
Permutacja – z czym si

ę

to je

Macierz – to bardzo proste
Modulo – czy kto

ś

mi grozi?

3
3

4
4
8

13

15
15
19
23
28

33
33

37
37
37
37
38

Czy nie zastanawialiście się?...

www.wedrownik.net

2

Czy nigdy si

ę

nie zastanawiali

ś

cie nad pewnymi brakami w rozwoju technik harcerskich? W

zasadzie wi

ę

kszo

ść

technik harcerskich mo

ż

emy rozwija

ć

w zale

ż

no

ś

ci od wieku. Wiele, ale

nie szyfry. Tak jak uczymy si

ę

ich na samym pocz

ą

tku naszej przygody harcerskiej, tak

zazwyczaj nic nowego ju

ż

pó

ź

niej nie poznajemy. Proste szyfry harcerskie nie s

ą

ż

adnym

wyzwaniem dla harcerzy starszych, nie wspominaj

ą

c o w

ę

drownikach.

Mo

ż

e pora to zmieni

ć

. Chciałbym zaproponowa

ć

mał

ą

wycieczk

ę

w krain

ę

kryptografii.

Potrzebny przy tym aparat matematyczny nie b

ę

dzie wymagaj

ą

cy – humani

ś

ci nie musz

ą

si

ę

obawia

ć

.

Do cz

ęś

ci szyfrów podam metody ich łamania. Do tej pory przy harcerskich szyfrach nie

mieli

ś

my takiej mo

ż

liwo

ś

ci, gdy

ż

znajomo

ść

rodzaju szyfru była równoznaczna z mo

ż

liwo

ś

ci

ą

jego rozszyfrowania. Do nowych szyfrów potrzebny zawsze b

ę

d

ą

jakie

ś

dodatkowe

informacje. I łamanie szyfru b

ę

dzie zazwyczaj równoznaczne z ich kre

ś

leniem.

Co będzie nam potrzebne

Pierwszy grupa nowych szyfrów jakie b

ę

d

ą

w nast

ę

pnym rozdziale zaprezentowane nie b

ę

d

ą

od nas wymagały

ż

adnych przekształce

ń

matematycznych – wystarcz

ą

odpowiednie tabele i

b

ę

dziemy mogli szyfrowa

ć

i deszyfrowa

ć

wiadomo

ś

ci.

Do szyfrów z drugiej grupy potrzebna nam b

ę

dzie tabela zapisu liter w postaci

zerojedynkowej lub mówi

ą

c inaczej binarnej. Na szcz

ęś

cie szyfry te nie b

ę

d

ą

wymagały od

nas

ż

adnych skomplikowanych oblicze

ń

. Wystarczy par

ę

prostych działa

ń

matematycznych.

Do pracy z pozostałymi szyframi przyda si

ę

nam kalkulator. My

ś

l

ę

,

ż

e nie jest to bardzo

uci

ąż

liwe wymaganie, gdy

ż

wi

ę

kszo

ść

z nas posiada telefony komórkowe z kalkulatorem w

bonusie. Tutaj potrzebne b

ę

d

ą

nam tak

ż

e pewne poj

ę

cia z matematyki wy

ż

szej – operacja

modulo (bez strachu to wbrew pozorom bardzo łatwe).
Cała teoria matematyczna zostanie umieszczona dla przejrzysto

ś

ci na ko

ń

cu poradnika – na

pocz

ą

tku mogłaby za bardzo straszy

ć

;-)

Dodam jeszcze,

ż

e przy opisach działania i łamania szyfrów nie b

ę

d

ę

rozpisywał si

ę

jaka

teoria matematyczna pozwala na takie, a nie inne działania. Nie chc

ę

aby ten poradnik był

zbyt podobny do ksi

ą

zki z matematyki. Ka

ż

da metoda b

ę

dzie krok po kroku tłumaczona na

konkretnym przykładzie – zamiast przebijania si

ę

przez teorie od razu zobaczycie jak

działaj

ą

konkretne metody.

Ciekawskich zach

ę

cam do poszperania po ksi

ąż

kach (wybór literatury jest naprawd

ę

du

ż

y,

nawet dla pocz

ą

tkuj

ą

cych), a reszt

ę

do zabawy nieskr

ę

powanej teori

ą

matematyczn

ą☺

Zaczynamy zabawę

www.wedrownik.net

3

Szyfr zmieniający alfabet

Fachowo powiedzieliby

ś

my – szyfr permutuj

ą

cy alfabet. Pierwszy szyfr i ju

ż

dziwne

matematyczne słowo;-) Ale aby nie bawi

ć

si

ę

w nadmierne tłumaczenie definicji permutacji

wystarczy przyj

ąć

,

ż

e zasada działania szyfru polega na zamianie kolejno

ś

ci liter alfabetu.

Jak to wygl

ą

da?

SZYFROWANIE – DESZYFROWANIE – ŁAMANIE SZYFRU

Aby zaszyfrowa

ć

wiadomo

ść

musimy utworzy

ć

alfabet tajny – czyli zmieni

ć

kolejno

ść

liter w

alfabecie. W praktyce wygl

ą

da to tak,

ż

e zapisujemy najpierw wszystkie litery w klasycznej

kolejno

ś

ci, a pó

ź

niej ka

ż

dej z nich przyporz

ą

dkujemy wybrana przez nas liter

ę

.

Wa

ż

ne

– nowo przyporz

ą

dkowane litery nie mog

ą

si

ę

powtarza

ć

!!!

Poni

ż

sza tabelka jest przykładem takiego nowego przyporz

ą

dkowania.

www.wedrownik.net

4

a

→

m

f

→

k

m

→

t

ś

→

y

ą

→

c

g

→

i

n

→

ó

t

→

p

b

→

g

h

→

ć

ń

→

ą

u

→

z

c

→

a

i

→

ę

o

→

s

www.wedrownik.net

5

Wadą tej metody jest to, że każdy przy odrobinie cierpliwości może złamać taki szyfr. Zaletą
zaś jest jej łatwość i możliwość zastosowania w różnych zabawach harcerskich – nawet dla
harcerzy młodszych.

Szyfr Vigenere’a

Zanim przejd

ę

do omawiania szyfru Vigenere’a przypomn

ę

szyfrowanie metod

ą

Cezara. Ten szyfr zna wi

ę

kszo

ść

harcerzy. W podanym tek

ś

cie, wybieramy jako klucz

cyfr

ę

nie wi

ę

ksz

ą

ni

ż

26 lub 32 (w zale

ż

no

ś

ci czy stosujemy angielski czy polski

alfabet). I wszystkie litery naszego tekstu przesuwamy o t

ą

warto

ść

na prawo w

alfabecie. Deszyfrowanie analogicznie z tym,

ż

e przesuwamy litery w lewo.

Ró

ż

nica pomi

ę

dzy szyfrem Cezara, a Vigenere’a jest taka,

ż

e w tym drugim

przypadku rol

ę

klucza pełni nie cyfra ale wyraz.

Aby nie musie

ć

co chwila oblicza

ć

jaka litera jest nast

ę

pn

ą

o podan

ą

ilo

ść

pozycji,

b

ę

dziemy stosowa

ć

tablic

ę

Vigenere’a.

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

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

B

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

C

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

B

D

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

E

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

D

F

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

G

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

H

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

I

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

J

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

K

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

L

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

M

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

N

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

O

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

P

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

Q

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

R

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

S

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

T

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

U

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

www.wedrownik.net

6

V

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

W

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

X

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

Y

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Z

Z

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

Wskazówka
- w przypadku tego szyfru polecam stosowanie alfabetu angielskiego, gdy

ż

dzi

ę

ki

temu mo

ż

emy u

ż

ywaj

ą

c tylko jednej tablicy, by szyfrowa

ć

teksty w wi

ę

kszo

ś

ci j

ę

zyków

- je

ś

li chcemy szyfrowa

ć

tekst z polskimi literami musimy odpowiednio rozbudowa

ć

nasz

ą

tabel

ę

Maj

ą

c ju

ż

tabelk

ę

mo

ż

emy przyst

ą

pi

ć

do nauki jak funkcjonuje ta metoda.

SZYFROWANIE – DESZYFROWANIE – ŁAMANIE SZYFRU

Jak ju

ż

zostało wspomniane, jako klucza u

ż

ywa

ć

b

ę

dziemy wyrazu, a nie jednej litery.

Gdy tekst przeznaczony do szyfrowania jest dłu

ż

szy ni

ż

nasz klucz, to musimy wyraz klucz

wpisa

ć

pod naszym tekstem jawnym tyle razy ile si

ę

zmie

ś

ci.

W poni

ż

szym przykładzie u

ż

ywamy jako klucza słowa

dom

.

www.wedrownik.net

7

h
a
r
c
e
r
z

s
z
e
d
l

p
r
z
e
z
…

d
o
m
d
o
m
d

o
m
d
o
m

d
o
m
d
o

Taki zapis oznacza,

ż

e do szyfrowania litery

h

u

ż

yjemy liter

ę

d

,

o

dla

a

,

m

dla

r

itd. Ale jak

teraz zastosowa

ć

nasz

ą

tabel

ę

? W pierwszym wierszu szukamy liter

ę

, któr

ą

chcemy

zaszyfrowa

ć

, a wi

ę

c w naszym przypadku

h

. W pierwszej kolumnie szukamy liter

ę

z klucza,

a wi

ę

c

d

. Przeci

ę

cie si

ę

wiersza i kolumny przyporz

ą

dkowuje nam zaszyfrowan

ą

liter

ę

–

k

.

www.wedrownik.net

8

A
B
C
D
E

F

G

H

I

…

A
A
B
C
D
E

F

G

H

I

…

B
B
C
D
E

F

G

H

I

J

…

C
C
D
E

F

G

H

I

J

K

…

D
D
E

F

G

H

I

J

K

L

…

E

www.wedrownik.net

9

Metoda ta jest do

ść

pracochłonna, ale po paru próbach łamanie szyfru powinno post

ę

powa

ć

do

ść

szybko. Istnieje przy niej ryzyko popełnienia pewnej ilo

ś

ci bł

ę

dów literowych lub pomyłki

podczas liczenia.

www.wedrownik.net

10

Szyfr Playfaira

B

ę

dzie to ostatni szyfr z pierwszej grupy. Niestety tutaj nie podam metody jego łamania,

gdy

ż

jest zbyt pracochłonna. Ale pomimo to jest on wart uwagi.

SZYFROWANIE – DESZYFROWANIE

Równie

ż

ten szyfr opiera si

ę

na stosowaniu odpowiedniej tabelki. Jednak aby j

ą

stworzy

ć

,

potrzebne jest nam słowo klucz . Szyfr ten powstał w oparciu o słowo

playfair

(st

ą

d ta

nazwa). Nic nie stoi jednak na przeszkodzie, aby u

ż

ywa

ć

dowolnego słowa klucza.

Ż

eby utworzy

ć

odpowiedni

ą

tabelk

ę

(5x5) wpisujemy słowo klucz z pomini

ę

ciem

powtarzaj

ą

cych si

ę

liter. Wa

ż

ne jest tak

ż

e to,

ż

e litery

i

i

j

traktujemy jako jedn

ą

. Pozostałe

wolne miejsca w tabeli uzupełniamy (w kolejno

ś

ci alfabetycznej) brakuj

ą

cymi literami.

P

L
A
Y
F

I/J
R
B
C
D

E
G
H
K
M

N
O
Q
S
T

U
V
W
X
Z

Metod

ę

t

ą

omówi

ę

na przykładzie szyfrowania słowa

konna policja

. Wiem,

ż

e lepiej brzmi

policja konna, ale na potrzeby prezentacji działania szyfru zamieniłem ogólnie przyjmowan

ą

kolejno

ść

.

Krok I.
Dzielimy nasz tekst na pary liter. Je

ś

li w parze wyst

ę

puj

ą

te same litery, to oddzielamy je

liter

ą

x

. Gdyby okazało si

ę

,

ż

e ostatnia litera nie ma pary to tak

ż

e dopisujemy do niej

x

.

www.wedrownik.net

11

ko
n

x

n
a
p
o
li
cj
a

x

Krok II.
Teraz stosujemy 3 zasady szyfrowania.

1. Je

ś

li obie litery znajduj

ą

si

ę

w tym samym wierszu, to zast

ę

pujemy je literami

stoj

ą

cymi po ich prawej stronie. Je

ś

li nasza litera tekstu jawnego jest na ko

ń

cu

wiersza, to zamiast niej wstawiamy t

ą

z samego pocz

ą

tku.

2. Je

ś

li obie litery znajduj

ą

si

ę

w tej samej kolumnie, to zast

ę

pujemy je literami

znajduj

ą

cymi si

ę

pod nimi. Je

ś

li nasza litera tekstu jawnego jest na dole kolumny, to

zamiast niej wstawiamy t

ą

z samej góry.

3.

Je

ś

li litery znajduj

ą

si

ę

w ró

ż

nych wierszach i kolumnach to zamiast nich wstawiamy

litery z tego samego wiersza, ale z kolumny drugiej litery w parze.

Stosuj

ą

c te 3 zasady otrzymamy nast

ę

puj

ą

cy szyfr.

ko
nx
n
a
p
o
li
cj
ax

⇓

gs
su
q
p
ln
pr
dr
y
w

A wi

ę

c ostatecznym efektem naszego szyfrowania jest tekst

gssuqplnprdryw

.

●●●

Deszyfrowanie jest zwykłym odwróceniem zasad 1-3. Sprawdzimy to na przykładzie
szyfru

qbbdgiuz

.

www.wedrownik.net

12

qb
bd
gi
uz

⇓

qb

– obie litery nale

żą

do jednej kolumny. Odwracaj

ą

c zasad

ę

2 przyporz

ą

dkowujemy im litery

b

ę

d

ą

ce nad nimi i otrzymujemy –

ha

bd

– obie litery nale

żą

do jednego wiersza. Odwracaj

ą

c zasad

ę

1 przyporz

ą

dkowujemy im litery

b

ę

d

ą

ce po ich lewej stronie i otrzymujemy –

rc

gi

– obie litery le

żą

w ró

ż

nych wierszach i kolumnach wi

ę

c stosuj

ą

c zasad

ę

3 uzyskamy par

ę

–

er

uz

– obie litery nale

żą

do jednego wiersza. Odwracaj

ą

c zasad

ę

1 przyporz

ą

dkowujemy im litery

b

ę

d

ą

ce po ich lewej stronie i otrzymujemy –

zx

Po pozbyciu si

ę

symboli

x

w naszych parach liter, otrzymujemy wiadomo

ść

–

harcerz

.

Zalet

ą

tej metody jest jej prostota oraz fakt,

ż

e nie potrzebujemy do niej

ż

adnych

dodatkowych pomocy ani tabelek. Potrzebn

ą

nam tabelk

ę

szyfruj

ą

c

ą

mo

ż

emy stworzy

ć

sobie sami. Wad

ą

jest niestety brak mo

ż

liwo

ś

ci łamania tego systemu – niestety wymaga to

zbyt du

ż

ej ilo

ś

ci czasu.

www.wedrownik.net

13

Robi się poważnie;-)

Szyfry dla zapisu zerojedynkowego

S

ą

to ciekawe szyfry daj

ą

ce ciekawe mo

ż

liwo

ś

ci. Co bardzo wa

ż

ne nie wymagaj

ą

ce

ż

adnych

wielkich zdolno

ś

ci matematycznych – a na tym nam przecie

ż

zale

ż

y:-) Zanim przejd

ę

do

omawiania dokładnych metod, krótkie wyja

ś

nienie jak zapisujemy wyrazy u

ż

ywaj

ą

c tylko cyfr

0 i 1. Potrzebujemy do tego tabelk

ę

przedstawiaj

ą

c

ą

przyporz

ą

dkowanie kodu

zerojedynkowego dla ka

ż

dej litery alfabetu.

Litera

Kod

Litera

Kod

Litera

Kod

a

00000

j

01001

s

10010

b

00001

k

01010

t

10011

c

00010

l

01011

u

10100

d

00011

m

01100

v

10101

e

00100

n

01101

w

10110

f

00101

o

01110

x

10111

g

00110

p

01111

y

11000

h

00111

q

10000

z

11001

i

01000

r

10001

Do pierwszych trzech szyfrów nie podam metod ich łamania. Poradnik ten ma by

ć

w ko

ń

cu

jak najmniej matematyczny. Na szcz

ęś

cie nadrobimy to przy ostatniej metodzie z tej grupy.

ECB (Elektronic Code Book)

Najprostszy z tej grupy szyfrów. Dzi

ę

ki temu jest doskonały nawet dla harcerzy młodszych.

Dobrze tez si

ę

sprawdza na grach terenowych ze wzgl

ę

du na szybko

ść

pracy z nim.

.

SZYFROWANIE – DESZYFROWANIE – ŁAMANIE SZYFRU

Działanie tej metody (tak jak i wcze

ś

niejszych) omówimy na konkretnym przykładzie. Dla

wzrokowców zał

ą

czam jeszcze schemat działania tego szyfru. Cho

ć

osobi

ś

cie s

ą

dz

ę

,

ż

e

łatwiej b

ę

dzie pracowa

ć

nam przy u

ż

yciu tabelki. Ale wszystko po kolei:-)

Schemat szyfrowania

www.wedrownik.net

14

Do zaszyfrowania wybierzemy słowo

harcerz

.

Krok I.
Zapisujemy litery w systemie zerojedynkowym.

h
a

r

c

e

r

z

00111
00000
10001
00010
00100
10001
11001

Krok II.
Teraz pora na zaszyfrowanie naszej wiadomo

ś

ci. Dokonamy tego zmieniaj

ą

c kolejno

ść

symboli w blokach tekstu (poddaj

ą

c je permutacji – wyja

ś

nienie poj

ę

cia w rozdziale V na

stronie 37)
W naszym przykładzie u

ż

yjemy nast

ę

puj

ą

cej permutacji –

(124)

. A wi

ę

c pierwszy symbol

przeniesiemy na drug

ą

pozycj

ę

, drugi na czwart

ą

, czwarty na pierwsz

ą

, a trzeci pozostanie

na swoim miejscu. Aby tego dokona

ć

musimy nasz ci

ą

g 0 i 1 podzieli

ć

na bloki o długo

ś

ci 4

elementów (ilo

ść

permutowanych elementów).

0011
1000
0010
0010
0010
0010
0100
0111
001

Krok III.
Jak wida

ć

ostatni blok jest krótszy. W takiej sytuacji brakuj

ą

ce pozycje uzupełniamy

odpowiedni

ą

ilo

ś

ci

ą

zer.

www.wedrownik.net

15

0011
1000
0010
0010
0010
0010
0100
0111
001

0

Krok IV.
W tym momencie pozostało nam tylko poddanie ka

ż

dego bloku zamianie symboli miejscami

(naszej matematycznej permutacji – wiem,

ż

e to słowo nie gryzie, ale wol

ę

go unika

ć

aby

nie straszy

ć

humanistów;-)

0011
1000
0010
0010
0010
0010
0100
0111
0010

⇓

1010
0100
0010
0010
0010
0010
0001
1011
0010

I po bólu, nasza wiadomo

ść

została wła

ś

nie zaszyfrowana:-)

Wa

ż

ne

- powy

ż

ej jest przedstawiony ostateczny wynik szyfrowania. Nie zmieniamy zapisu

zerojedynkowego w literowy, gdy

ż

podczas szyfrowania mo

ż

emy uzyska

ć

taki ci

ą

g 0 i 1,

który nie ma odpowiednika literowego

●●●

Schemat deszyfrowania

www.wedrownik.net

16

Deszyfrowanie te

ż

jest bezbolesne. Spróbujemy teraz odszyfrowa

ć

wiadomo

ść

, któr

ą

dopiero co zaszyfrowali

ś

my.

Krok I.
Musimy najpierw okre

ś

li

ć

, jak odwróci

ć

przestawienie symboli (okre

ś

li

ć

permutacj

ę

odwrotn

ą

– ponownie odsyłam do rozdziału V na stronie 37)
Dla naszej permutacji szyfruj

ą

cej (124) odwrotn

ą

jest

(142)

– odwrócona kolejno

ść

(421) z

uwzgl

ę

dnieniem zasady wpisywania zawsze najmniejszej cyfry na pocz

ą

tku – czyli pierwszy

element umie

ś

cimy na czwartej pozycji, czwarty na drugiej, drugi na pierwszej, a trzeci

ponownie pozostaje bez zmian.

Krok II.
W tym momencie mo

ż

emy ju

ż

zastosowa

ć

przekształcenie odwrotne na nasz szyfr.

1010
0100
0010
0010
0010
0010
0001
1011
0010

⇓

0011
1000
0010
0010
0010
0010
0100
0111
0010

Krok III.
Rozszyfrowan

ą

wiadomo

ść

dzielimy na bloki długo

ś

ci 5 symboli, a nadwy

ż

k

ę

odrzucamy.

www.wedrownik.net

17

00111
00000
10001
00010
00100
10001
11001

0

Krok IV.
Dokonujemy zamiany zapisu binarnego na nasz normalny alfabet.

00111
00000
10001
00010
00100
10001
11001

h
a

r

c

e

r

z

●●●

Łamanie tego szyfru jest czasochłonne, ale nieszczególnie skomplikowane. Je

ś

li znamy

długo

ść

permutacji szyfruj

ą

cej musimy okre

ś

li

ć

jej odwrotno

ść

. Sprowadza si

ę

to do

sprawdzenia wszelkich mo

ż

liwo

ś

ci – dla 3 elementów musimy sprawdzi

ć

tylko 6 układów,

dla 4 elementów ju

ż

24 układy, ale dla 5 elementów niestety a

ż

120. Z przestawieniem o

długo

ś

ci 2 nie ma najmniejszego problemu, dla (12) odwrotno

ś

ci

ą

jest (12).

Spróbujmy naszych sił na wiadomo

ś

ci zaszyfrowanej przy pomocy permutacji o długo

ś

ci 3.

001
100
111
001
011

Dla permutacji 3 elementów mamy 6 mo

ż

liwych kolejno

ś

ci –

(12)

,

(13)

,

(23)

,

(123)

,

(132)

,

oraz pozostawienie kolejno

ś

ci

bez zmian

.

Sprawd

ź

my wszystkie 6 mo

ż

liwo

ś

ci. Od razu wynik podzielimy na bloki długo

ś

ci 5 symboli i

podstawimy litery.

www.wedrownik.net

18

szyfr

001
100
111
001
011

szyfr

001
100
111
001
011

(12)

001
010
111
001
101

(13)

100
001
111
100
110

⇓

długo

ść

5

00101
01110
01101

długo

ść

5

10000
11111
00110

tekst

f

o
n

tekst

q

---

g

www.wedrownik.net

19

szyfr

001
100
111
001
011

szyfr

001
100
111
001
011

(23)

010
100
111
010
011

(123)

100
010
111
100
101

⇓

długo

ść

5

01010
01110
10011

długo

ść

5

10001
01111
00101

tekst

k

o

t

tekst

r

p

f

www.wedrownik.net

20

szyfr

001
100
111
001
011

szyfr

001
100
111
001
011

(132)

010
001
111
010
110

b.z.

001
100
111
001
011

⇓

długo

ść

5

01000
11110
10110

długo

ść

5

00110
01110
01011

tekst

i

---

w

tekst

g
o

l

Jak wida

ć

w paru przypadkach uzyskali

ś

my nawet nieistniej

ą

ce symbole. Jedyne sensowne

wyrazy to

kot

i

gol

– czyli poprawne permutacje odwrotne to

(23)

i kolejno

ść

bez zmian

.

www.wedrownik.net

21

Tak to jest z łamaniem szyfrów,

ż

e czasem dostajemy par

ę

sensownych wersji. Gdyby

ś

my

mieli dłu

ż

szy szyfr do złamania to mogliby

ś

my okre

ś

li

ć

jednoznacznie poprawn

ą

deszyfracj

ę

.

Uwaga
- metoda ta działa równie dobrze dla normalnego zapisu literowego (oszcz

ę

dzamy krok z

zamian

ą

liter na zapis z 1 i 0)

- po podzieleniu tekstu na bloki długo

ś

ci naszej permutacji uzupełniamy w razie potrzeby

ostatni blok – mo

ż

emy dowolnymi literami (tak aby nie zmieniły sensu szyfrowanego tekstu)

CBC (Cipher Block Chaining)

Pomi

ę

dzy CBC, a ECB s

ą

dwie ró

ż

nice. Poza permutacj

ą

posiadamy jeszcze klucz

pocz

ą

tkowy. Klucz ten zmienia si

ę

po ka

ż

dym zaszyfrowanym bloku – wła

ś

nie ten

zaszyfrowany blok jest nowym kluczem. Brzmi gro

ź

nie, ale na szcz

ęś

cie nie jest to tak

trudne.

SZYFROWANIE – DESZYFROWANIE

Najpierw zaprezentuj

ę

schemat tej metody.

Schemat szyfrowania

www.wedrownik.net

22

A teraz jak zwykle przykład dla zilustrowania działania szyfru. Ponownie u

ż

yjemy słowa

harcerz

. Potrzebujemy te

ż

funkcj

ę

zmieniaj

ą

ca kolejno

ść

elementów –

(13)(24)

. Elementem

nowym b

ę

dzie klucz startowy –

0101

.

Krok I.
Zapisujemy nasz tekst w postaci zerojedynkowej.

h
a

r

c

e

r

z

00111
00000
10001
00010
00100
10001
11001

Krok II.
Dzielimy tekst na bloki długo

ś

ci równej ilo

ś

ci permutowanych elementów – czyli długo

ś

ci 4 –

i ewentualnie uzupełniamy ostatni blok.

www.wedrownik.net

23

0011
1000
0010
0010
0010
0010
0100
0111
001

0

Krok III.
Tworzymy tabelk

ę

z 4 kolumnami – 1 kolumna zawiera wszystkie bloki tekstu, 2 w

pierwszym wierszu klucz startowy. Ostatnie dwie na razie pozostawimy puste

www.wedrownik.net

24

Tekst

Kluc

z

Tekst

+

Kluc

z

Szyfr

(po

perm

utacji

)

0011
0101

1000

0010

0010

0010

0010

0100

0111

0010

www.wedrownik.net

25

Metoda ta wymaga troszk

ę

wi

ę

cej pracy ni

ż

szyfr ECB. Mam jednak nadziej

ę

,

ż

e pomimo

tego jest ona interesuj

ą

ca.

Uwaga
- w tej i nast

ę

pnej metodzie istnieje ciekawy sposób ukrycia klucza. Po prostu zał

ą

czamy go

na pocz

ą

tku wiadomo

ś

ci. Adresat naszego tekstu wiedz

ą

c jaka jest jego długo

ść

wyodr

ę

bni

klucz z szyfru i przyst

ą

pi do odczytywania przesyłki.

CFB (Cipher Feedback)

CFB jest kolejnym bardziej skomplikowanym szyfrem z tej grupy. Podobnie jak dla CBC, dla
ka

ż

dego bloku tekstu dostajemy inny klucz. Jednak dokonujemy jeszcze paru dodatkowych

przekształce

ń

– prosz

ę

si

ę

nie ba

ć

, to nie b

ę

d

ą

ż

adne matematyczne przekształcenia.

SZYFROWANIE – DESZYFROWANIE

Szczególnie przy tej metodzie warto zapozna

ć

si

ę

z schematem, gdy

ż

wtedy łatwiej

zapami

ę

ta

ć

jak ona działa.

Schemat szyfrowania

W przykładzie ilustruj

ą

cym prac

ę

tego szyfru, tradycyjnie u

ż

yjemy słowa

harcerz

.

Potrzebujemy te

ż

funkcj

ę

permutuj

ą

c

ą

–

(13)

oraz klucz startowy –

1101

. Dodatkowym

parametrem jest warto

ść

przesuni

ę

cia –

1

. Co ta warto

ść

oznacza najlepiej poka

ż

e

przykład.

Krok I.
Zapisujemy nasz tekst w postaci zerojedynkowej.

www.wedrownik.net

26

h
a

r

c

e

r

z

00111
00000
10001
00010
00100
10001
11001

Krok II.
Teraz musimy ustali

ć

długo

ść

bloku tekstu. Permutacja mo

ż

e mie

ć

minimaln

ą

ilo

ść

elementów równ

ą

3, ale klucz pocz

ą

tkowy ma ich 4. Wi

ę

c wychodzi nam długo

ść

4. Tutaj

jednak wchodzi w gr

ę

warto

ść

przesuni

ę

cia i skraca nam blok tekstu – w tym przykładzie o

1.
Ostateczna długo

ść

bloków przeznaczonych do szyfrowania wynosi 3 symbole.

001
110
000
010
001
000
100
010
010
001
110
01

0

Ostatni blok uzupełnili

ś

my o brakuj

ą

cy element.

Krok III.
Tworzymy teraz nast

ę

puj

ą

c

ą

tabelk

ę

– na pocz

ą

tek wpisujemy w 3 kolumn

ą

wszystkie bloki

tekstu.

www.wedrownik.net

27

Klucz
Klucz
po
perm
utacji
Tekst
Szyfr

(klucz
+
tekst)

001

110

000

010

001

000

100

010

010

www.wedrownik.net

28

Niestety, do obu powy

ż

szych szyfrów nie podam metod łamania, gdy

ż

s

ą

zbyt

skomplikowane – zainteresowanych odsyłam do fachowej literatury (jednak zalecam wzi

ę

cie

sobie paru dni wolnego;-)

Szyfr Feistella

Ostatni z szyfrów działaj

ą

cych w systemie zerojedynkowym. I to jest jedyne podobie

ń

stwo do

powy

ż

szych szyfrów;-) Stopniem trudno

ś

ci lokuje si

ę

pomi

ę

dzy dwoma pierwszymi szyframi

z tego rozdziału. Co jednak wa

ż

niejsze, nauczymy si

ę

w prosty sposób łama

ć

t

ą

metod

ę

:-)

SZYFROWANIE – DESZYFROWANIE – ŁAMANIE SZYFRU

Metod

ę

ta przedstawi

ę

w najprostszej wersji. Je

ś

li kto

ś

b

ę

dzie chciał spróbowa

ć

sił z troch

ę

wy

ż

szym poziomem trudno

ś

ci, to wystarczy zmieni

ć

warto

ś

ci pewnych parametrów.

Na nasze potrzeby wystarcz

ą

nast

ę

puj

ą

ce zało

ż

enia – b

ę

dziemy szyfrowa

ć

bloki tekstu o

długo

ś

ci 4 symboli, ilo

ść

kroków szyfruj

ą

cych ograniczymy do 2, a stosowanym elementem

szyfruj

ą

cym b

ę

dzie macierz 2x2 (kto nie zna tego poj

ę

cia to prosz

ę

zapozna

ć

si

ę

z

rozdziałem V na stronie 37)

Uwaga
- długo

ść

bloków jakie podlegaj

ą

szyfrowaniu jest

ś

ci

ś

le zwi

ą

zana z wielko

ś

ci

ą

macierzy –

szyfrowany fragment tekstu jest zawsze dwa razy dłu

ż

szy, ni

ż

wielko

ść

macierzy (dlatego

długo

ść

4 dla macierzy 2x2, 6 dla 3x3, 8 dla 4x4 itd.)

Na potrzeby naszego przykładu zaszyfrujemy słowo

harcerz

, przy zastosowaniu

2

kroków

szyfruj

ą

cych z macierz

ą













1

0

1

1

Krok I.

www.wedrownik.net

29

Tradycyjnie zapisujemy nasz tekst w formie zerojedynkowej i dzielimy na fragmenty o
długo

ś

ci 4 elementów z ewentualnym uzupełnieniem ostatniej cz

ęś

ci.

h
a

r

c
e

r

z

00111
00000
10001
00010
00100
10001
11001

⇓

0011
1000
0010
0010
0010
0010
0100
0111
001

0

Krok II.
Tym razem działanie przedstawimy za pomoc

ą

rysunku. Najpierw zaszyfrujemy pierwszy

fragment naszego tekstu –

0011

.

Tekst dzielimy na cz

ęść

lew

ą

i praw

ą

.

Krok III.
Zaczynamy pierwszy krok szyfruj

ą

cy. Cz

ęść

praw

ą

mno

ż

ymy z nasz

ą

macierz

ą

i

przygotowujemy j

ą

do dodania do cz

ęś

ci lewej. Dodatkowo niezmienion

ą

cz

ęść

praw

ą

przepisujemy poni

ż

ej, aby móc za dwa kroki dokona

ć

zamiany.

www.wedrownik.net

30

Krok IV.
Dodajemy do siebie cz

ęść

lew

ą

i zmodyfikowan

ą

praw

ą

.

W tym momencie ko

ń

czymy pierwszy krok szyfruj

ą

cy.

Krok V.
Dokonujemy zamiany cz

ęś

ci lewej i prawej.

Krok VI.
Dla nowych cz

ęś

ci tekstu, przeprowadzamy drugi krok szyfruj

ą

cy (dokładnie jak powy

ż

ej).

Po ostatnim kroku szyfruj

ą

cym nie dokonujemy zamiany. Dlatego w naszym przypadku

drugie powtórzenie daje nam zaszyfrowany pierwszy blok tekstu.

www.wedrownik.net

31

Je

ś

li powtórzymy dla ka

ż

dego bloku tekstu kroki II – VI, to jako zaszyfrowany tekst

otrzymamy.

0010
1110
0011
0011
0011
0011
0101
0111
0011

●●●

Ta metoda jest kolejn

ą

, przy której dla rozszyfrowania podanego tajnego tekstu, musimy go

ponownie zaszyfrowa

ć

. A wi

ę

c, aby z szyfru

0010
1110
0011
0011
0011
0011
0101
0111
0011

uzyska

ć

słowo harcerz, musimy na nim zastosowa

ć

opisan

ą

powy

ż

ej metod

ę

wraz z

ko

ń

cowym podzieleniem na bloki składaj

ą

ce si

ę

z 5 elementów i eliminacj

ą

zb

ę

dnych

symboli – ale te działanie ju

ż

wielokrotnie

ć

wiczyli

ś

my.

●●●

Gdy mamy zaszyfrowan

ą

wiadomo

ść

i chcemy j

ą

rozgry

źć

, musimy okre

ś

li

ć

macierz, która

nam szyfruje pojedyncze bloki. Wiemy,

ż

e macierz ta ma 4 elementy, a jako mo

ż

liwe

warto

ś

ci tylko 0 i 1. Je

ś

li znamy jakie

ś

elementy macierzy to musimy sprawdzi

ć

wszystkie

mo

ż

liwo

ś

ci i zobaczy

ć

przy której uzyskujemy sensowne wyniki. Gdy znamy 3 elementy, to

www.wedrownik.net

32

do sprawdzenia mamy 2 macierze, gdy znamy 2 to ju

ż

4, przy 1 elemencie a

ż

8. Gdy nie

znamy

ż

adnego, to pozostaje nam przetestowa

ć

wszystkie 16 mo

ż

liwo

ś

ci.

Prób

ę

przeprowadzamy tak, jak zostało to opisane w cz

ęś

ci po

ś

wi

ę

conej szyfrowaniu.

Ciekawiej jest, gdy oprócz szyfru znamy tekst jawny pasuj

ą

cy do jednego bloku szyfru.

Dzi

ę

ki temu mo

ż

emy okre

ś

li

ć

poszukiwan

ą

macierz – gdy znamy jakiekolwiek jej elementy,

to zadanie jest dodatkowo ułatwione.
Jak si

ę

do tego zabra

ć

?

Trzeba przeanalizowa

ć

, jak wygl

ą

da proces szyfrowania (bo w tej metodzie deszyfrowanie

działa identycznie jak szyfrowanie). Zrobimy to na konkretnym przykładzie.
Dla szyfru

0110

znamy tekst jawny

0111

.

Nasza macierz ma ogóln

ą

posta

ć













d

c

b

a

.

Krok I.
Uzupełniamy schemat szyfru i elementy, które ju

ż

znamy.

Uzupełnili

ś

my od razu

ś

cie

ż

k

ę

dla prawego elementu – wszystko zgodnie z metod

ą

szyfrowania.

Krok II.
Wymna

ż

amy praw

ą

stron

ę

naszego szyfru z ogóln

ą

postaci

ą

macierzy, a nast

ę

pnie

dodajemy do lewej strony (i uzupełniamy praw

ą

stron

ę

pozycji po zamianie).

Dla przejrzysto

ś

ci u

ż

yłem pisowni z przecinkiem.

W tej chwili mo

ż

emy zacz

ąć

okre

ś

la

ć

posta

ć

naszej macierzy. Z naszego schematu wynika,

ż

e

(a, b+1) = (11)

. Daje nam to nast

ę

puj

ą

ce warto

ś

ci:

a = 1

i

b = 0

. A wi

ę

c nasza macierz

www.wedrownik.net

33

wygl

ą

da nast

ę

puj

ą

co -













d

c

0

1

.

Krok III.
Teraz wykonujemy drugie mno

ż

enie macierzy z nasz

ą

praw

ą

stron

ą

szyfru (po uprzednim

podstawieniu cyfr).

Aby okre

ś

li

ć

ostatnie elementy macierzy dokonujemy dodawania

(10) + (1+c, d)

.

Zsumowane elementy musz

ą

(na podstawie schematu) by

ć

równe elementowi

(01)

.

Ostatecznie daje nam to

(1+1+c, d) = (1, 1)

, a wi

ę

c

c = 0

,

d = 1

. Maj

ą

c wszystkie elementy

wiemy ju

ż

,

ż

e pozostałe bloki szyfru musimy podda

ć

działaniu macierzy













1

0

0

1

.

Czasem mo

ż

e trafi

ć

si

ę

nam trudniejsza sytuacja, gdy nie tak łatwo okre

ś

li

ć

jednoznacznie

elementy macierzy. Có

ż

, pozostaje nam wtedy rozpatrywa

ć

po kolei ró

ż

ne mo

ż

liwo

ś

ci i

sprawdza

ć

, które pasuj

ą

do schematu.

Metoda ta jak pokazuj

ą

przykłady mo

ż

e by

ć

troszk

ę

pracochłonna. Jednak nie ma tutaj

ż

adnej skomplikowane matematyki. Jedynie sprawdzanie pewnej liczby mo

ż

liwych

kombinacji.

Uwaga
- metoda ta sprawdza si

ę

równie

ż

, gdy zamiast macierzy, u

ż

ywamy do szyfrowania

dwuelementowego klucza
- niestety znacznie łatwiej wtedy złama

ć

t

ą

metod

ę

, gdy

ż

do wyboru mamy tylko 4 klucze

(mo

ż

na zawsze je wydłu

ż

y

ć

, ale co za tym idzie dwukrotnie zwi

ę

kszy

ć

szyfrowane lub

deszyfrowane bloki tekstu)

www.wedrownik.net

34

Wytaczamy ostatnią armatę

Ta grupa szyfrów b

ę

dzie wymagała wprowadzenia pewnej, dla wielu osób na pocz

ą

tku na

pewno niełatwej, teorii matematycznej – działania modulo (proponuj

ę

zapozna

ć

si

ę

z tre

ś

ci

ą

rozdziału V na stronie 38).

Szyfr afiniczny

Jest to mocno utrudniona wersja szyfru Cezara. Tutaj zmiana litery jest okre

ś

lona dwoma

parametrami, a nie jak w metodzie Cezara jednym.

SZYFROWANIE – DESZYFROWANIE – ŁAMANIE SZYFRU

Przy tej metodzie do

ść

cz

ę

sto pomocnym narz

ę

dziem b

ę

dzie kalkulator.

Aby zobrazowa

ć

działanie tej metody zaszyfrujemy słowo harcerz.

Krok I.
Zamieniamy litery tekstu jawnego na ich warto

ś

ci liczbowe. Jednak zaczynamy od 0 – czyli

litera a ma warto

ść

0,

ą

– 1, b - 2, itd.

www.wedrownik.net

35

h
a

r

c
e

r

z

10

0

22

3
6

22
29

Wa

ż

ne

- wa

ż

ne jest jaki alfabet stosujemy – dla angielskiego mamy 26 liter, a dla polskiego 32

- w tej metodzie szyfrowania, tak

ż

e odst

ę

p mi

ę

dzy wyrazami ma przypisana warto

ść

– dla

alfabetu angielskiego 26, a dla polskiego 32

Krok II.
Aby zaszyfrowa

ć

tekst musimy okre

ś

li

ć

funkcje szyfruj

ą

c

ą

. Jak ju

ż

wiemy b

ę

dzie ona zale

ż

e

ć

od dwóch warto

ś

ci –

a

i

b

(b

ę

dziemy je nazywa

ć

kluczem). Ogólna posta

ć

funkcji wygl

ą

da

nast

ę

puj

ą

co:

y

≡

(ax + b) mod n

a

oraz

b

s

ą

wybranymi przez nas liczbami,

n

jest ilo

ś

ci

ą

liter w alfabecie + 1,

x

warto

ś

ci

ą

liczbow

ą

szyfrowanej litery, a

y

uzyskanym w ten sposób szyfrem. W naszym przykładzie

u

ż

yjemy funkcji

y

≡

(2x + 7) mod 33

Je

ś

li zachcemy zaszyfrowa

ć

liter

ę

h, to uzyskamy poni

ż

szy wynik:

h = 10

, a wi

ę

c

y

≡

(2·10 + 7) mod 33

= 27 mod 33 =

27 = w

Gdy ka

ż

d

ą

z liter słowa harcerz tak zaszyfrujemy uzyskamy:

www.wedrownik.net

36

h
a

r

c

e

r

z

10

0

22

3
6

22
29

⇓

27

7

18
13
19
18
32

w

ę
ń

k
o

ń

●●●

Deszyfracja jest bardziej skomplikowana. Ale wszystko po kolei.

Poni

ż

szy szyfr został stworzony przy pomocy tej samej funkcji szyfruj

ą

cej:

y

≡

(2x + 7) mod 33

www.wedrownik.net

37

ę
ą
ę

d
e

ę

d
a

j

ś
ę

7
2
7
5
6
7
5
0
1
2
2
4
7

Krok I.
Aby deszyfrowa

ć

, musimy okre

ś

li

ć

funkcj

ę

odwrotn

ą

do zastosowanej.

Wa

ż

ne

- aby deszyfrowanie było mo

ż

liwe, musi by

ć

spełniony warunek NWD (a, n) = 1 (najwi

ę

kszy

wspólny dzielnik). Nie b

ę

d

ę

si

ę

rozwodził dlaczego akurat tak, gdy

ż

musiałbym straszy

ć

matematyk

ą

– zainteresowanych odsyłam do literatury fachowej.

NWD (2, 33) = 1, a wi

ę

c mo

ż

emy jednoznacznie okre

ś

li

ć

funkcje odwrotn

ą

. Jej ogólna

posta

ć

prezentuj

ę

si

ę

nast

ę

puj

ą

co:

x

≡

a’·(y - b) mod n

a’

jest w tym przypadku odwrotno

ś

ci

ą

a z wzoru na szyfrowanie. Nie jest to jednak

odwrotno

ść

, jak

ą

znamy ze szkoły. Aby okre

ś

li

ć

a’ musimy zastosowa

ć

rozszerzony

algorytm Euklidesa

.

Dla

x

≡

2’(y - 7) mod 33

całe obliczenie wygl

ą

da jak poni

ż

ej (dlaczego tak, a nie inaczej

wyja

ś

nione jest w rozdziale V na stronie 38).

33 = 16·2 + 1

⇒

1 = 33 - 16·2

A wi

ę

c odwrotno

ś

ci

ą

2

jest

-16

. Ale -16 odpowiada liczbie

17

(33-16=17) w grupie

mod 33

.

www.wedrownik.net

38

Nasza funkcja ma posta

ć

:

x

≡

17·(y - 7) mod 33

Krok II.
Nasz

ą

zaszyfrowan

ą

wiadomo

ść

poddajemy działaniu funkcji odwrotnej. Daje nam to efekt

jak poni

ż

ej.

ę
ą
ę

d
e

ę

d
a

j

ś

ę

7
2
7
5
6
7
5
0
1
2
2
4
7

⇓

www.wedrownik.net

39

0
1
4
0
3
2
1
6
0
3
2
1
3
1
9
2
5
0

a

l

a

m
a

k
o

t

a

Metoda ta wymaga wiele uwagi i ci

ą

głej

ś

wiadomo

ś

ci,

ż

e liczymy w grupie mod n (u nas w

mod 33).

●●●

Aby móc złama

ć

szyfr afiniczny nie znaj

ą

c funkcji szyfruj

ą

cej, potrzebujemy informacj

ę

o

cho

ć

by paru przyporz

ą

dkowaniach liter tekstu jawnego do liter szyfru. Gdy znamy cho

ć

2 z

nich, mo

ż

emy złama

ć

t

ą

metod

ę

kryptograficzn

ą

. Tak

ż

e w tym przypadku najlepiej łamanie

omówi

ć

na konkretnym przykładzie, bez zb

ę

dnych teoretycznych wywodów, które sił

ą

woli

byłyby zbyt techniczne.

Mamy szyfr

n

ą

ry

ą

l

i wiemy,

ż

e

n

zostało zaszyfrowane do

r

, a

d

do

y

. Dzi

ę

ki temu mo

ż

emy

stwierdzi

ć

,

ż

e

www.wedrownik.net

40

n

ą

r

y

ą

l

17

1

22
28

1

14

oraz

n

→

r

1
7

→

2
2

d

→

y

5

→

2
8

Pozwoli nam to okre

ś

li

ć

, jak

ą

funkcj

ą

zaszyfrowano tekst, a co za tym idzie wyznaczy

ć

funkcj

ę

do niej przeciwn

ą

. Gdy ju

ż

ja uzyskamy, to b

ę

dziemy mogli odszyfrowa

ć

pozostałe

litery.

Krok I.
Na podstawie drugiej tabelki utworzymy układ równa

ń

liniowych (w zapisie mod 33).

17a + b

≡

22 mod 33

5a + b

≡

28 mod 33

Jak wida

ć

na naszym przykładzie, warto

ś

ci liczbowe dla

tekstu jawnego

wpisujemy przy

a

,

a

warto

ś

ci szyfru

przy

mod

.

www.wedrownik.net

41

Krok II.
Rozwi

ą

zujemy nasze równanie liniowe (pami

ę

taj

ą

c,

ż

e liczymy w grupie mod 33).

17a + b

≡

22 mod 33

/ · (-1)

5a + b

≡

28 mod 33

⇓

-17a - b

≡

-22 mod 33

5a + b

≡

28 mod 33

⇓

-12a

≡

6 mod 33

⇓

21a

≡

6 mod 33

⇓

a = 5

Pocz

ą

tek rozwi

ą

zania powinien by

ć

zrozumiały dla wszystkich. Wa

ż

ne jest aby pami

ę

ta

ć

i

ż

-12

ma warto

ść

21

w grupie mod 33.

Wynik

a = 5

mo

ż

na uzyska

ć

jedynie poprzez systematyczne podstawianie liczb (pocz

ą

wszy

od 1) i sprawdzanie czy równanie jest prawdziwe. Wymaga to troch

ę

cierpliwo

ś

ci i najlepiej

stosowania kalkulatora (jest to du

ż

e udogodnienie).

Teraz musimy wyznaczy

ć

jeszcze parametr b.

5·5 + b

≡

28 mod 33

⇓

25 + b

≡

28 mod 33

/ - 20

⇓

b

≡

3 mod 33

⇓

b = 3

Maj

ą

c oba parametry wiemy ju

ż

,

ż

e tekst został zaszyfrowany funkcj

ą

:

y = (4x + 3) mod 33

Krok III.
Do rozszyfrowania wiadomo

ś

ci potrzebujemy, jak ju

ż

wiemy, funkcj

ę

odwrotn

ą

do tej przez

www.wedrownik.net

42

nas okre

ś

lonej. Aby okre

ś

li

ć

5’

z

x = 5’·(y

–

3) mod 33

musimy zastosowa

ć

rozszerzony algorytm Euklidesa.

33 = 6·5 + 3
5 = 3 + 2
3 = 2 + 1

⇒

1 = 3 – 2
1 = 3 – (5 –
3)
1 = 2·3 – 5
1 = 2·(33 –
6·5) – 5
1 = 2·33 –
13·5

Odwrotno

ś

ci

ą

5 jest liczba

- 13

. Jednak -13 w zapisie mod 33 ma warto

ść

20 (33 – 13 = 20).

Tak wi

ę

c uzyskujemy

a’ = 20

. Ostatecznie nasza funkcja odwrotna ma posta

ć

:

x = 20·(y

–

3) mod 33

Krok IV.
Działamy nasz

ą

funkcja odwrotn

ą

na nieznane nam litery szyfru i uzyskujemy tekst jawny:

n

ą

r

y

ą

l

17

1

22
28

1

14

⇓

www.wedrownik.net

43

16
26
17

5

26
22

m

u
n
d
u

r

W ten sposób przebili

ś

my si

ę

przez kolejn

ą

metod

ę

łamanie szyfru.

Pomoce matematyczne – proszę się nie bać, nie gryzą;-)

Dodawanie binarne - dodawanie inaczej

Brzmi strasznie, ale na szcz

ęś

cie jest prostsze ni

ż

zwykłe dodawanie, gdy

ż

mamy tylko 4

mo

ż

liwo

ś

ci:-)

Poni

ż

ej przedstawione s

ą

wszelkie mo

ż

liwe sytuacje podczas takiego dodawania.

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0

Permutacja – z czym się to je

Mówi

ą

c mo

ż

liwie prosto, permutacja to po prostu zmiana kolejno

ś

ci elementów ci

ą

gu. A

zapis ogólny podaje nam, które pozycje otrzymuj

ą

nowe przyporz

ą

dkowanie.

Przykładowo













1

4

4

3

2

2

3

1

oznacza,

ż

e pierwszy element bloku o długo

ś

ci 4 zostanie

przeniesiony na pozycj

ę

3, drugi pozostanie na pozycji 2, trzeci przesuwamy na pozycj

ę

4, a

ostatni element l

ą

duje na pocz

ą

tku bloku. Opis mo

ż

e skomplikowany, ale praktyka bardzo

prosta:-)

Inn

ą

form

ą

zapisu tej samej permutacji jest (134) – taki jest u

ż

ywany w tym poradniku. Je

ś

li

w zapisie tym brakuje jakiej

ś

cyfry, to oznacza to, i

ż

symbol na tej pozycji nie jest

przenoszony. Jest to opis krótszy a oznacza dokładnie to samo. Czasami mo

ż

emy spotka

ć

nast

ę

puj

ą

cy zapis (13)(24) – oznacza to nic innego jak to,

ż

e symbol z pozycji 1 przenosimy

na 3, z 3 na 1, a z 2 na 4 oraz z 4 na 2.
Aby okre

ś

li

ć

odwrotn

ą

permutacj

ę

odwracamy kolejno

ść

w wersji skróconej czyli otrzymamy

(431). Matematyczna konwencja przewiduje zawsze najmniejszy element na pocz

ą

tku, wi

ę

c

wersj

ą

ko

ń

cow

ą

jest (143).

Permutacje o długo

ś

ci 2 s

ą

odwrotne same do siebie. A wi

ę

c (23) jest odwrotno

ś

ci

ą

(23), a

(13)(24) jest odwrotno

ś

ci

ą

(13)(24). Proste:-)

www.wedrownik.net

44

Macierz – to bardzo proste

Nie b

ę

d

ę

si

ę

wdawał w opisywanie definicji macierzy. W tym poradniku ograniczymy si

ę

do

macierzy kwadratowych o rozmiarze 2x2. Jak taki twór wygl

ą

da?













d

c

b

a

jest ogólnym

zapisem macierzy kwadratowej – prawda,

ż

e podobne do kwadratu? A zapis 2x2 oznacza,

ż

e mamy po dwa wiersze i dwie kolumny.

Wektorem z kolei nazwiemy nast

ę

puj

ą

cy element (e, f). Jest to wektor o długo

ś

ci 2. Mno

ż

y

ć

mo

ż

emy z sob

ą

tylko wektory i macierze kwadratowe o tym samym rozmiarze, a wi

ę

c wektor

o długo

ś

ci 2 z macierz

ą

2x2.

Jak wygl

ą

da takie mno

ż

enie?

(e f)

=













⋅

d

c

b

a

(ea+fc, eb+fd)

(1 1) ·













1

1

1

0

= (1·0 + 1·1 1·1 + 1·1 ) = (0 + 1 1 + 1) = (1 0)

- jest to mno

ż

enie macierzy z uwzgl

ę

dnieniem dodawania zerojedynkowego

Modulo – czy ktoś mi grozi?

Mówi

ą

c najpro

ś

ciej jak si

ę

da, jest to reszta z dzielenia przez liczb

ę

n. W zapisie

matematycznym wygl

ą

da to nast

ę

puj

ą

co:

a

≡

b mod n

i oznacza,

ż

e a przy dzieleniu przez n, daje reszt

ę

b. Ten

ś

mieszny znaczek pomi

ę

dzy

elementami traktujcie jako zwykły znak równo

ś

ci. Mo

ż

e nie jest to w pełni poprawne

matematycznie, ale nas to nie interesuje, ma by

ć

łatwo i przyjemnie;-)

Przy takiej operacji liczba b le

ż

y w przedziale od 0 do n –1, niezale

ż

nie jak du

żą

liczb

ą

jest a.

W ramach

ć

wiczenia par

ę

przykładów:

22 mod 3 = 1
4 mod 6 = 4
25 mod 5 = 0

A co si

ę

stanie, gdy w wyniku naszych działa

ń

dostaniemy liczb

ę

negatywn

ą

? Wiemy

przecie

ż

,

ż

e nasze liczby nale

żą

do przedziału od 0 do n – 1.

-22 mod 3 = -1 mod 3 = 2 gdy

ż

3 – 1 = 2

-14 mod 33 = 19 gdy

ż

33 – 14 = 19

Na razie jest miło prosto i przyjemnie. Niestety teraz zaczn

ą

si

ę

lekkie schody. Czasami

musimy okre

ś

li

ć

odwrotno

ść

jakiej

ś

liczby w systemie modulo n. Zapis matematyczny

przedstawia si

ę

tak:

ab

≡

1 mod n

www.wedrownik.net

45

W tym przypadku a i b s

ą

do siebie odwrotne. Niestety nie s

ą

to elementy odwrotne tak, jak

si

ę

do tego przyzwyczaili

ś

my w szkole.

Do tego nie ka

ż

dy element w systemie mod n ma odwrotno

ść

. Dziwne, ale prawdziwe. Aby

móc wyznaczy

ć

taki element musi by

ć

spełniony warunek NWD(a, n) = 1.

Jak mo

ż

na je wyznaczy

ć

? Najprostsz

ą

metod

ą

jest rozszerzony algorytm Euklidesa. Jego

działanie najlepiej wytłumaczy

ć

na przykładzie.

Spróbujmy znale

źć

odwrotn

ą

liczb

ę

dla 18 w systemie mod 41

Szukamy zapisu liczby 41 przy pomocy 18 i ewentualnej reszty:

41 = 2·18 + 5

Teraz 18 przenosimy na lew

ą

stron

ę

i szukamy jej zapisu przy pomocy 5 i reszty.

18 = 3·5 + 3

Krok ten powtarzamy tak długo, a

ż

reszt

ą

b

ę

dzie liczba 1.

5 = 3 + 2
3 = 2 + 1

W ten sposób zako

ń

czyli

ś

my pierwsz

ą

cz

ęść

szukania odwrotno

ś

ci. Druga polega na

przedstawieniu 1 za pomoc

ą

18 i 41. Brzmi troch

ę

absurdalnie, ale jest to mo

ż

liwe i

poprawne matematycznie. Zaczniemy od naszego ostatniego równania – zmieniamy je tak,
aby tylko liczba 1 była po lewej stronie

1 = 3 – 2

Skorzystamy teraz z informacji, jakie s

ą

w drugim równaniu – po prostu w miejsce 2

wstawimy jej warto

ść

z drugiego równania.

1 = 3 – (5 – 3)

1 = 2·3 – 5

Wykorzystuj

ą

c równania z pierwszej cz

ęś

ci zamieniamy stopniowo liczby, a

ż

dojdziemy do

postaci z 18 i 41.

1 = 2·(18 – 3·5) – 5
1 = 2·18 – 7·5
1 = 2·18 – 7·(41 – 2·18)
1 = 16·18 – 7·41

Liczb

ą

odwrotn

ą

do 18 jest ta z, któr

ą

jest ona wymna

ż

ana w ostatniej linii naszego

równania. A wi

ę

c jest to liczba 16.

Aby sprawdzi

ć

nasz rachunek wystarczy wyliczy

ć

,

ż

e

16·18 = 288 mod 41 = 1

I to by było na tyle z matematycznych wywodów:-)

Ż

ycz

ę

miłej zabawy i całkiem nowych

wra

ż

e

ń

!

www.wedrownik.net

46