Klasická kryptografie

© Květuše Sýkorová

• Klasická kryptografie – Substituční kryptosystémy • • • •

monoalfabetické homofonní polyalfabetické polygramové


– Transpoziční šifry • jednoduchá transpozice • transpozice s heslem • dvojitá transpozice

– Součinové šifry • ST, TS • STT, TTS

• opakování: – odesílatel: • znak O.A. nahradí znakem Š.A.

– příjemce (adresát): • znak Š.A. nahradí znakem O.A.


– použije na Š.T. invertovanou substituci

• základní typy použití substituce: – – – –

monoalfabetická homofonní polyalfabetická polygramová

– jednoduchá substituce • jednoduchá záměna

• šifrování: – každý znak O.T. se nahradí jedním znakem Š.T. podle předpisu • používá se jen jedna Š.A. pro celý O.T. • předpis náhrady je stejný pro celý O.T.


– proudová šifra • – je prosté zobrazení – celkem N! různých zobrazení »

. .

Š. .

– např. N 26 ⇒ ! ≐ 4. 10 » relativní bezpečnost proti útoku hrubou silou

• dešifrování: – nutná znalost tabulky přiřazení nebo klíč

• varianty: – afinní šifry • klíč = tabulka přiřazení, tabulka substitucí

– šifry s triviálním klíčem © Květuše Sýkorová

• klíč = posunutí

– šifry s klíčem • klíč = klíčová fráze

• luštění: – využívají se statistické metody • frekvenční analýza, analýza bigramů, trigramů, polygramů

• šifrování + dešifrování: – klíč = tabulka přiřazení, tabulka substitucí


• dodržuje se standardní postup šifrování 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

– zachovává frekvenci výskytu jednotlivých znaků

text = Obecná substituční šifra


o.t.: = OBECNA SUBSTITUCNI SIFRA A

B

C

D

E

F

G

H

I

J

K

L

M

05

12

16

23

06

21

00

07

25

15

01

13

04

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

18

22

11

08

17

20

09

02

14

24

10

19

03

číselná varianta

š.t.: = 22 12 06 16 18 05 20 02 12 20 09 25 09 02 16 18 25 20 25 21 17 05

text = zachovává frekvenci výskytu znaků


o.t. = ZACHOVAVA FREKVENCI VYSKYTU ZNAKU A

B

C

D

E

F

G

H

I

J

K

L

M

F

M

Q

X

G

V

A

I

Z

P

B

N

E

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

R

W

L

H

S

U

J

D

O

Y

K

T

C

varianta se znaky

š.t.: = CFQIW OFOFV SGBOG RQZOT UBTJD CRFBD


š.t.: = 15 06 16 04 06 18 20 19 16 25 04 06 03 25 14 22 02 20 19 11 09 06 15 20 06 11 20 06 18 25 16 14 03 11 22 04 06 18 22 02 20 25 A

B

C

D

E

F

G

H

I

J

K

L

M

05

12

16

23

06

21

00

07

25

15

01

13

04

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

18

22

11

08

17

20

09

02

14

24

10

19

03

o.t.: = JECME NSYCI MEZIV OUSYP TEJSE PSENI CVZPO MENOU SI text = Ječmen syčí mezi vousy: Ptej se pšenic, vzpomenou si!

• šifrování + dešifrování: – klíč = posunu → tzv. „posuvná šifra“ • posunutí o K znaků vpravo – cyklické posunutí v abecedě = modulo N – pouze varianta se znaky

• příklad = Caesarova šifra – K = 3


• – –

∈

je posunutí . .

Š. .

• dodržuje se standardní postup šifrování – zachovává frekvenci výskytu jednotlivých znaků

text = Caesarova šifra je tzv. omezený algoritmus o.t.: = CAESAROVA SIFRA JE TZV OMEZENY ALGORITMUS


key = 3 A

B

C

D

E

F

G

H

I

J

K

L

M

D

E

F

G

H

I

J

K

L

M

N

O

P

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

š.t.: = FDHVD URYDV LIUDM HWCYR PHCHQ BDOJR ULWPX V

š.t.: = RBYLW PWHBW ZLUPJ ULCLK PCZHR AHRLU PJ


key = 7 A

B

C

D

E

F

G

H

I

J

K

L

M

H

I

J

K

L

M

N

O

P

Q

R

S

T

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

U

V

W

X

Y

Z

A

B

C

D

E

F

G

o.t.: = KUREP IPAUP SENIC NEVED IVSAK TAKEN IC text = Kuře pípá u pšenic, nevědí však také nic.

• šifrování + dešifrování: – klíč = fráze • postup „heslem mísená standardní abeceda“


– zvolí se počáteční písmeno pro psaní hesla » dostatečně dlouhé a smysluplné heslo » vynecháme opakující se písmena – nepoužitá písmena za heslo v daném pořadí » !!! špatné heslo = zachování pořadí písmen v abecedě

• . . Š. . • dodržuje se standardní postup šifrování

– zachovává frekvenci výskytu jednotlivých znaků

text = Nepoužíváme krátká hesla. o.t.: = NEPOUZIVAME KRATKA HESLA


key = pozastavený, H A

B

C

D

E

F

G

H

I

J

K

L

M

L

M

Q

R

U

W

X

P

O

Z

A

S

T

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

V

E

N

Y

B

C

D

F

G

H

I

J

K

š.t.: = VUNEF KOGLT UABLD ALPUC SL

• šifrování + dešifrování: – klíč = špatně zvolené (krátké) heslo


key = ananas, B A

B

C

D

E

F

G

H

I

J

K

L

M

Z

A

N

S

B

C

D

E

F

G

H

I

J

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

K

L

M

O

P

Q

R

T

U

V

W

X

Y

• šifrování + dešifrování: – klíč = špatně zvolené (krátké) heslo + od začátku abecedy


key = banán, A A

B

C

D

E

F

G

H

I

J

K

L

M

B

A

N

C

D

E

F

G

H

I

J

K

L

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

M

O

P

Q

R

S

T

U

V

W

X

Y

Z

š.t.: = YZCNA KHNLN BUYCZ JDFJN LINTZ JUFDM ZJZJD


key = nepozlacený, E A

B

C

D

E

F

G

H

I

J

K

L

M

U

V

W

X

N

E

P

O

Z

L

A

C

Y

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

B

D

F

G

H

I

J

K

M

Q

R

S

T

o.t.: = MILEK UREJE NAMLI TOPTE JSEZI TAPOV ITITO text = Milé kuře, je nám líto, ptej se žita, poví ti to.

– podobá se monoalfabetické – vyhlazuje frekvenci výskytu jednotlivých znaků • frekventované znaky mají v Š.A. celou skupinu znaků

• šifrování:


– každý znak O.T. se nahradí jedním znakem Š.T. podle předpisu • frekventované znaky – vybíráme náhodně z příslušné skupiny šifrových znaků • počet znaků ve skupině odpovídá frekvenci výskytu daného znaku • používá se jen jedna Š.A. pro celý O.T. – předpis náhrady je stejný pro celý O.T.

– proudová šifra • – Š. . ≫

. .

text = Vyhlazuje frekvenci výskytu znaků. o.t.: = VYHLAZUJE FREKVENCI VYSKYTU ZNAKU


A

B

C

D

E

F

G

H

I

J

K

L

M

31

00

07

09, 29

34

28

13

04

06, 17, 24

12

16

23

05, 14, 21, 27, 30

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

18

01, 15, 25, 22

11

08

33

20

26

02

35

32

10

19

03

š.t.: = 35 19 07 13 24 03 02 34 21 31 33 05 28 35 14 18 16 29 35 19 20 28 19 26 02 03 18 17 28 02

– frekventované znaky v ČJ (monogramy): • E, O, A, I, N, S, T, R, V, U, L, Z, D, K, P, M, C, Y, H, J, B, G, F, X, W, Q • frekventované znaky na začátku slov – P, S, V, Z, N, T, O, J, K, D, A, B, M, R, U, C, I, H, E, L, F, G, W, Y, Q, X

• frekventované znaky na konci slov – E, I, A, O, U, Y, M, T, H, V, L, K, S, Z, D, N, R, C, J, B, P, G, F, W, X, Q

– bigramy: © Květuše Sýkorová

• ST, PR, SK, CH, DN, TR, …

– trigramy: • STR, PRO, UNI, OST, STA, ANI, OVA, YCH, STI, PRI, PRE, OJE, REN, IST, EHO, TER, RED, ICH, …

– polygramy: • častá slova v jazyce

• závisí na typu textu • novinové články, romány, odborné texty, …

• AJ: – frekventované znaky: • E, T, A, O, N, R, I, S, H, D, L, F, C, M, U, G, P, Y, W, B, V, K, X, J, Q, Z


– bigramy: • TH, HE, AN, IN, ER, RE, ON, ES, TI, AT, ST, EN, OR, ND, TO, NT, ED, IS, AR, …

– trigramy: • THE, ING, AND, ION, TIO, ENT, ERE, HER, ATE, VER, TER, THA, ATI, FOR, HAT, ERS, HIS, RES, ILL, ARE, …

– polygramy: • THE, OF, AND, TO, A, IN, THAT, IT, IS, I, FOR, AS, …

– šifrování mezi skupinami znaků • složitější při provádění • nutná tabulka pro šifrování

– substituční tabulka


• • • •

čím větší skupina znaků, tím větší tabulka skupina = dvojice (NxN řádků) skupina = trojice (NxNxN řádků) skupina = k‐tice (Nk řádků) – N=26 → N2=676, N3=17 576, N4=456 976, …

– Dvouznaková polygramová substituční šifra AA

AB

AC

AD

AE

AF

FW

LJ

UR

EX

MN

BC

…

– posloupnost monoalfabetických šifer • konečná, nekonečná • –

je monoalfabetická šifra

• pořadí použití


– určeno klíčem – po určité době se začne opakovat » kryptoanalýza

• příklady: – Trithemiova šifra – Gronsfeldova šifra – Vigenerova šifra » periodické heslo, autoklíč – Beaufortova šifra

– Trithemiova šifra • tabulka = „tabula recta“ – N = 26 znaků – 26 abeced » posun o K=0,1,2,..,25

• nevýhoda – opakování » 1., 27., 53., … znaky šifrovány beze změny © Květuše Sýkorová

– Gronsfeldova šifra • tabulka – N = 26 znaků – 10 abeced

• klíč – číselný

– Vigenerova šifra • 16. století francouz Blaise de Vigenére – realizace » generování ‐ Vigenerův čtverec – periodické heslo » key = abeceda, o.t. = sloupec, š.t. = průsečík – autoklíč » key = 1 znak + o.t. © Květuše Sýkorová

– Beaufortova šifra • angličan admirál sir Francis Beaufort – periodické heslo » o.t. = abeceda, key = průsečík, š.t. = sloupec – Beaufortova varianta » key = abeceda, o.t. = průsečík, š.t. = sloupec


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 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 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 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 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 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 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

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

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


I


I

J

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 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 O P Q R S T U V W X Y Z A B C D E F G H

J

K L M

I

• digrafická šifra – řecký historik Polybios

• původně: – kódový systém pro signalizaci • písmeno o.t. = číslo řady a číslo sloupce š.t.


– pomocí pochodní na velkou vzdálenost » řádek = levá ruka » sloupek = pravá ruka

• dnes: – předání celé tabulky nebo hesla • častější heslo

– Problém = 26 znaků abecedy a 25 polí tabulky • AJ = I+J, ČJ = X+Y


1

2

3

4

5

1

A

B

C

D

E

2

F

G

H

I/J

K

3

L

M

N

O

P

4

Q

R

S

T

U

5

V

W

X

Y

Z 1

2

3

4

5

1

H

E

S

L

O

2

A

B

C

D

F

3

G

I

J

K

M

4

N

P

Q

R

T

5

U

V

W

X/Y

Z

• původ: – věznice v carském Rusku • vězňové z řad anarchistů • ťukání na stěnu – nejprve řádek, poté sloupec – oddělovač = mezera


– rozšířila se po celé Evropě – upravená Polybiova tabulka • 6 x 6 • heslo – pomalá a pracná komunikace

• bigramová substituční šifra – navrhl 1854 britský vědec Charles Wheatstone • největší propagátor byl britský poslanec Lyona Playfaira – používána jako vojenská polní šifra i během 2. sv. války (občas)

• princip: – klíč = tabulka 5 x 5 © Květuše Sýkorová

• 25 písmen mezinárodní abecedy (J = I) – obecná permutace písmen

– šifrování: • t‐gramová šifra (bigram na bigram) – dvojice písmen tvoří obdélník – nahradíme dvěma písmeny, které tvoří protilehlé vrcholy tohoto obdélníku – dvojice písmen v jednom řádku – nahradíme písmeny vpravo od nich – dvojice písmen v jednom sloupci – nahradíme písmeny pod nimi

H

E

S

L

O

A

B

C

D

F

G

I/J

K

M

N

P

Q

R

T

U

V

W

X

Y

Z


text: Princeznička na bále o.t.: PR IN CE ZN IC KA NA BA LE š.t.: QT KG SB OU BK CG FG CB OS šifra: QTKGS BOUBK CGFGC BOS

• princip – permutace písmen otevřeného textu • přeházené pořadí, „přesmyčka“

• varianty: – sloupcová transpozice • o.t. zapisujeme do řádků s přesně daným počtem písmen


– š.t. čteme po sloupcích od prvního po poslední

– sloupcová transpozice s heslem • o.t. zapisujeme do řádků s přesně daným počtem písmen – š.t. čteme po sloupcích dle abecedního pořadí písmen hesla

• sloupcová transpozice – šifrování:


• sloupec = 7 znaků

1 2 3 4 5 6 7 K U R E H L

E

text = Kuře hledá žitné pole, ale to je dávno holé. A na suchá strniska vítr tiše zapíská:

D A Z

I

P O L

E A L

o.t. = KURE HLEDA ZITNE POLE ALE TO JE DAVNO HOLE A NA SUCHA STRNISKA VITR TISE ZAPISKA

T O J

E D A V

N O H O L

E

E A

N A S U C H A S

š.t. = KDPTN NSASK UAOOO ATVEA RZLJH SRIZX EIEEO UNTAX HTADL CIRPX LNLAE HSTIX EEEVA AKISX

T N E

T R N

I

A V

I

S

Z A P

E

S K

T R T I

I S

K A X X X X X

A N A K O N D A

• sloupcová transpozice s heslem – šifrování: • heslo = ANAKONDA (16258743)

V Z D Y T J S I D O M A Z A C H A L U P O U S L Y S I S V S T A


text = Vždyť jsi doma za chalupou. Slyšíš? V stáji J I K O N E D U koně dupou, kocour ve stodole vrní - a tvá máma P O U K O C O U za vraty, zob, zob, zobá bílé zrní s ostatními R V E S T O D O kuřaty. o.t. = VZDYT JSI DOMA ZA CHALUPOU SLYSIS V STAJI KONE DUPOU KOCOUR VE STODOLE VRNI A TVA MAMA ZA VRATY ZOB ZOB ZOBA BILE ZRNI S OSTATNIMI KURATY š.t. = VDAYJ PRLVV ZIOID MUIKU EVMAB ETUIH LAUUO TABBS MXSCS TDODA ZOAII YYAPS OKSRA TZZAR ZOLSI OVEAR OLSKJ AUSEC OIAZB NNTTZ OVNOT NMYOR TA

L E V R N I A T V A M A M A Z A V R A T Y Z O B Z O B Z O B A B I L E Z R N I S O S T A T N I M I K U R A T Y X

• použití: – německá armáda v průběhu první světové války • i po ní až do roku 1928

– československá vláda v exilu v Londýně v průběhu druhé světové války • ke komunikaci s domácím odbojem


– proto měl domácí odboj takové ztráty

• luštění: – popsáno ve francouzských novinách již na počátku první světové války v roce 1914 • velmi usnadněné, jsou‐li šifrovány zprávy stejné délky.

• algoritmus: – dvě hesla • např.

– 2x použít jednoduchou transpozici s heslem • první transpozice – první heslo – doplnění náhodnými znaky v posledním řádku © Květuše Sýkorová

• druhá transpozice – druhé heslo – v posledním řádku se nic nedoplňuje

• metoda vytváření šifer – navrhnul Claude Shannon • pro dobré promíchání o.t. a klíče • opakované skládání (součin) několika šifer různého typu – označení: » S = substituce, T = transpozice, L = lineární šifra

– šifra TTS, STT, … © Květuše Sýkorová

– hlavní šifry čs. vojenské zpravodajské služby za 2. sv. války (němci luštili)

• substituce (abeceda 45 znaků) – A, B, C, ... , Z, Č, Ě, Ř, Š, Ž, ., ?, ‐, /,1, 2, ..., 9, 0 » 15 den v měsíci: A=15, B=16, C=17, …, 0=14

• transpozice – heslo = daná kniha, strana (měsíc), řádek (den), zač./kon. ř. (slova+15zn.) ‐> očíslování písmen (transpozice s heslem) » zašifrovací a přešifrovací transpozice

• metoda vytváření šifer – šifra TTS, STT, … – hlavní šifry čs. vojenské zpravodajské služby za 2. sv. války

• transpozice – kniha = T.G. Masaryk: Světová revoluce 1914‐1918, vydání z r. 1925 – text básně Nadšení (32 řádků)


• TTS = zašifrovací transpozice, přešifrovací transpozice, substituce – luštění » rozdělení do dvojic – zjištěna frekvence „01“ až „45“ » jedná se pouze o posuvnou substituci » luštění do hloubky – zjištěna výsledná T, z ní odděleny obě dílčí T

• STT = substituce, zašifrovací transpozice, přešifrovací transpozice – luštění » zašifrovací T obsahuje lichý / sudý počet cifer (odlišná charakteristika výskytu jednotkových a desítkových číslic)

• metoda vytváření šifer – šifra TTS, STT, … – hlavní šifry čs. vojenské zpravodajské služby za 2. sv. války


• „Zubatka“ ST = substituce, transpozice – substituce (neuspořádané dvojice cifer) » O.A.: 49 zn. abeceda A B C Č D E Ě … . ? : ! , ‐ / 0 … 9 » mezera = 5 variant » čísla = zdvojení » po substituci zarovnat náh. ciframi do násobku 5 – transpozice » heslo = daná kniha, strana (měsíc), řádek (den), 15‐20 písmen » z hesla první 3 zn + . a poslední 3 zn + . se přidali k o.t. » očíslování písmen (transpozice s heslem)


Klasická kryptografie

Recommend Documents