© Květuše Sýkorová
© Květuše Sýkorová
• příklad Steganografie • Matematické základy šifrování – – – – – – –
modulární aritmetika modulární inverze prvočísla faktorizace diskrétní logaritmus eliptické křivky generátory náhodných čísel
• šifrování pomocí křížů • Hebrejské šifry
• Girolamo Cardano (Gerolamo, Geronimo) – latinsky – Hieronymus Cardanus • (1501 – 1576)
– milánský matematik, fyzik, filosof, astronom a astrolog • ukrytí jedné zprávy do jiné zprávy – šablona » obdélníková nebo čtvercová mřížka s vystřiženými poli © Květuše Sýkorová
• původní doporučení – o.t. opakovat 3x » odstranění problémů s nečitelností š.t. – snadno luštitelná » velmi rychle se přestalo používat
© Květuše Sýkorová
š.t.: = ESERCIEA RODFLNAY ERGNMOAV UOANNTSV INCAAMAI RRIZUDZA PTUNKOSR HUAIOSJB E
S
E
R
C
I
E
A
R
O
D
F
L
N
A
Y
E
R
G
N M O
A
V
U
O
A
N
N
T
S
V
I
N
C
A
A
M
A
I
R
R
I
Z
U
D
Z
A
P
T
U
N
K
O
S
R
H
U
A
I
O
S
J
B
o.t.: CARDANOVAMRIZKAJ EELEGANTNIZPUSOB SIFROVANIAUTORHI ERONYMUSCARDANUS text: Cardanova mřížka je elegantní způsob šifrování. Autor: Hieronymus Cardanus
• šifrovací algoritmus používá – matematické funkce • • • • •
modulární aritmetika Malá Fermatova věta prvočíselná faktorizace diskrétní logaritmus eliptické křivky
© Květuše Sýkorová
– logické operátory • XOR • modulární + a *
– záměna pozic • transpozice • substituce
• převedení znaků textu na čísla – PC – znak = číselná hodnota • binární zápis • interní uložení ve znakové sadě – kódová tabulka, kódová schránka » Morseova abeceda
• ASCII (1B, 7bitů,128 znaků) © Květuše Sýkorová
– další: bratrů Kamenických, PC‐Latin 2, ISO‐8859‐2, Windows‐1250
• Unicode (1‐4B, 21bitů, 1 114 112 znaků, 129 abeced) – sjednocená mezinárodní znaková sada » ver. 1.0.0 (10/1991) – ver. 8.0 (06/2015) – kódování: UTF‐7, UTF‐8, UTF‐16LE/BE (UCS‐2), UTF‐32LE/BE (UCS‐4) » endianita (LE, BE)
• představují substituci (A = 65, a = 97, á = 160)
• modulární aritmetika – jako aritmetika N 1,2,3, …
•
– redukován počet použitých čísel (n) 0,1,2, … ,
•
1
– n = modul
– komutativní zákon ∗
© Květuše Sýkorová
•
∗
– asociativní zákon ∗
•
∗
∗
∗
– distributivní zákon •
∗
∗
∗
∗
∗
∗
• modulární aritmetika – přirozená čísla N • 1,2,3, … • operace + * (nelze – a /)
– celá čísla Z
© Květuše Sýkorová
• … , 1,0,1, … • operace + – * (nelze /)
– množina čísel modulo n • 0,1,2, … , 1 • operace + – * / • relace kongruence – redukce – „dvě čísla mají stejný zbytek po dělení daným číslem“
• modulární aritmetika – relace kongruence • 0,1,2, … , 1 • platí: ≡ ↔ ∃ ∈ ∗ – „a je kongruentní modulo n s b“ nebo „a je kongruentní s b modulo n“
© Květuše Sýkorová
– –
, – po dělení n dávají stejný zbytek je dělitelný n
• např. 20 ≡ 8 – 20 2 ∗ 6 8 – 20/6 3 zbytek 2 8/6 – 20 8 /6 2 zbytek 0
• dále např. 164 ≡
, 69 ≡
1 zbytek 2
, 86 ≡ 44, …
• modulární aritmetika – relace kongruence • pravidla pro počítání:
© Květuše Sýkorová
– P1: ≡ ∀ ∈ – P2: ≡ → ≡ – P3: ≡ ∪ ≡
∀ , ∈ → ≡ ∀ , , ∈
– P4:
≡
∪
≡
→
– P5:
≡
∪
≡
→
≡ ∗
≡
∀ , , , ∗
∀ , , ,
• např. 20 ≡ 8, 64 ≡ 4 400 ≡ 64 400 ≡ 4 – 123 ≡ 4
• např. 5 – 5
≡ ? ?
5 » 21
∗5 ∗5 10101
∈ ∈
• modulární aritmetika – modul n = 10 • sečtěte a odečtěte posloupnosti: – 5 1 3 0 6 a – 7 0 4 9 8
5 1 3 0 6 7 0 4 9 8 1 2 1 8 0 4
5 1 3 0 6 7 0 4 9 8 1 9 1 9 2
– modul n = 26
© Květuše Sýkorová
• sečtěte a odečtěte posloupnosti: 15 11 23 06 11 – 15 11 23 06 11 a – 17 04 14 19 23
15 11 23 06 11 17 04 14 19 23 17 04 14 19 23 01 18 17 13 12 01 06 16 12 00 08
– modul n = 2 • sečtěte a odečtěte posloupnosti: – 0 1 1 0 1 a – 1 0 1 1 1
0 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0
0 1 1 0 1 1 0 1 1 1 0 1 0 1 0
• modulární aritmetika písmen – modul n = 26 • sečtěte a odečtěte posloupnosti:
© Květuše Sýkorová
– POSTEL a – PEŘINA
A
B
C
D
E
F
G
H
I
J
K
L
M
00
01
02
03
04
05
06
07
08
09
10
11
12
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
13
14
15
16
17
18
19
20
21
22
23
24
25
• modulární inverze • předpoklad: operace je některá z operací + *
– číslo k je identický prvek pro operaci ∀ ∆ ∆
© Květuše Sýkorová
• 0 pro + • 1 pro *
– číslo m je inverzní prvek k číslu n pro operaci • (‐n) pro + • (1/n) pro * – v modulární aritmetice inverze složitější
∆
• modulární inverze – v modulární aritmetice • operace + ‐ * jednoduché řešení – výpočet provedeme v běžné aritmetice – výsledek upravíme relací kongruence
• operace / složitější řešení
© Květuše Sýkorová
– hledáme číslo m k číslu x tak, aby platilo: • jiný zápis:
∗
≡ 1
≡
– existence řešení: • •
, ,
1 → jediné řešení, obecně pro n = prvočíslo 1 → nemá řešení
© Květuše Sýkorová
n = 5 (prvočíslo) +
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3
identický prvek k = ??? inverzní prvek m = ???
© Květuše Sýkorová
n = 6 (není prvočíslo) +
0
1
2
3
4
5
0
0
1
2
3
4
5
1
1
2
3
4
5
0
2
2
3
4
5
0
1
3
3
4
5
0
1
2
4
4
5
0
1
2
3
5
5
0
1
2
3
4
identický prvek k = ??? inverzní prvek m = ???
© Květuše Sýkorová
n = 5 (prvočíslo) *
0
1
2
3
4
0
0
0
0
0
0
1
0
1
2
3
4
2
0
2
4
1
3
3
0
3
1
4
2
4
0
4
3
2
1
identický prvek k = ??? inverzní prvek m = ???
© Květuše Sýkorová
n = 6 (není prvočíslo) *
0
1
2
3
4
5
0
0
0
0
0
0
0
1
0
1
2
3
4
5
2
0
2
4
0
2
4
3
0
3
0
3
0
3
4
0
4
2
0
4
2
5
0
5
4
3
2
1
identický prvek k = ??? inverzní prvek m = ???
• prvočísla – dělitelnost ⁄ ⟺ ∃ ∈ ∗ – „a dělí b“ nebo „a je dělitelem b“ • pro každé číslo a platí: •
– je beze zbytku dělitelné dvěma děliteli (číslo 1 a číslo a) – označíme je „triviální dělitelé“
© Květuše Sýkorová
• prvočíslo: – je takové přirozené číslo p, které nemá kromě dvou různých triviálních dělitelů žádné jiné dělitele » číslo 1 tedy není prvočíslo
• složené číslo: – je celé číslo různé od 1, které není prvočíslem » tj. kromě dvou různých triviálních dělitelů má ještě další dělitele
• prvočísla – vlastnosti:
© Květuše Sýkorová
• pro každé prvočíslo p platí: ⁄ ∗ ⟹ / ∨ / • každé přirozené číslo >1 je prvočíslo nebo je rozložitelné na součin prvočísel • každé přirozené číslo se dá jednoznačně vyjádřit jako součin prvočísel (v kanonickém tvaru): ∗ ∗ ⋯∗ – –
, ,
,…, ,…,
= prvočísla = přirozená čísla
• pokud p je prvočíslo a ∈ ; 0 , pak / • ke každému celému kladnému číslu ∈ ; 0 můžeme nalézt takové prvočíslo ; 2
• Eratostenovo síto
© Květuše Sýkorová
– zjištění prvočísel – pro malá N 2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
• Euklidův algoritmus – zjištění NSD(a,b) •
/
∧
/
→
/
∗
– počet dělení nepřesáhne 5‐ti násobek počtu cifer menšího z čísel
– definice: /
• d je NSD(a,b) 1.
∧
/
2. ∃ ´
´/
∧
´/
→ ´/
– např. NSD(56,126)= © Květuše Sýkorová
– tvrzení: • dvě čísla a,b jsou nesoudělná NSD(a,b)=1
– definice: • m je NSN(a,b) 1. / / ´
∧
/
2. ∃ ´
– např. NSN(16,20)=
– platí: .
,
·
,
/ ´ ∧
/ ´ →
• rozšířený Euklidův algoritmus – algoritmus pro nalezení koeficientů Bézoutovy rovnosti ,
•
·
– kde ,
∈
·
jsou Bézoutovy koeficienty
– lze využít pro nalezení inverzního prvku 0,1,2, … ,
• pro množinu –
,∗
,
• pro p = prvočíslo je © Květuše Sýkorová
1
– a tedy 1 · » a platí: · – tj. 1 ≡
1 pro všechna x
· ≡ 0
·
» kde ∈
je inverzním prvkem k prvku x
• rozšířený Euklidův algoritmus – příklad:
© Květuše Sýkorová
• 3
≡ ?? – tj. hledáme , ∈ tak, aby 29,3 · 29 ·3 » EA: 29 9 · 3 2 → 2 1 · 29 9 · 3 – 29,3 3,2 » EA: 3 1 · 2 1 → 1 1 · 3 1 · 2 » 1 · 3 1 · 1 · 29 9 · 3 10 · 3 1 · 29 » tj. 1 10 · 3 1 · 29 – a tedy: » 1, 10 29,3 1 · 29 10 · 3 » 1 » 1 ≡ 10 · 3 » kde 1 · 29 ≡ 0
• 3
≡
10
1
• rozšířený Euklidův algoritmus – příklad: • 3
≡ ??
© Květuše Sýkorová
násobky
zbytky
koeficienty
29
1
0
3
0
1
• rozšířený Euklidův algoritmus – příklad: • 3
≡ ?? násobky
© Květuše Sýkorová
29=9.3+2
9
zbytky
koeficienty
29
1
0
3
0
1
2
1
‐9
1=9*0+1, 0=9*1+(-9)
• rozšířený Euklidův algoritmus – příklad: • 3
≡ ??
© Květuše Sýkorová
násobky
koeficienty
29
1
0
3
0
1
29=9.3+2
9
2
1
‐9
1=9*0+1, 0=9*1+(-9)
3=1.2+1
1
1
‐1
10
0=1*1+(-1), 1=1*(-9)+10
3,29
–
• 3
zbytky
≡
10
1 · 29
10 · 3
1
• rozšířený Euklidův algoritmus – příklad: • 5
≡ ??
© Květuše Sýkorová
násobky
zbytky
koeficienty
29
1
0
5
0
1
• Eulerova funkce – počet přirozených čísel < n, která jsou nesoudělná s n ∑
• φ
1
– kde NSD(a,n)=1 » φ 1 ≔1
• pro bezpečnost algoritmů důležitý odhad počtu prvočísel < n
© Květuše Sýkorová
• pokud p je prvočíslo – φ
1
• pokud p je složené číslo – φ
1
n
1
2
3
4
5
6
7
8
9
10
11
12
13
(n)
1
1
2
2
4
2
6
4
6
4
10
4
12
• Eulerova funkce
© Květuše Sýkorová
– Eulerův vztah: n
počet prvočísel < n
102
22
104
1 085
106
72 398
1014
3,1.1012
1036
1.1034
10101
4,3.1098
10170
2,6.10167
• Malá Fermatova věta – ∀ ∈
∀ ∈
;
≡
– důsledek: •
≡ 1 3
– např. 81
≡ 1
≡ 1
•
,
– pokud © Květuše Sýkorová
3 1
– využívá se pro hledání složených čísel • n je složené číslo pokud ∃ ∈ 1,2, … ,
– využívá se pro hledání inverze • a
≡
p
– např. 3
a ≡ ??
1;
≢ 1
• moderní kryptografie – utajení, autentizace, autorizace, integrita
© Květuše Sýkorová
• šifrovací algoritmy, digitální podpisy, kryptografické protokoly, časové značky, … • obtížnost řešení matematických úloh – prvočíselná faktorizace velkých čísel (IF) » RSA, Rabin‐Williams – diskrétní logaritmus (DL) » DSA, Diffie‐Hellman – eliptický diskrétní logaritmus (EC) » ECDSA, eliptické kryptosystémy
• faktorizace – rozklad čísla na součin menších čísel (faktorů) – prvočíselná faktorizace
∗
∗ ⋯∗
• faktor = prvočíslo
© Květuše Sýkorová
– rozklad na součin prvočísel
• pro každé číslo dána jednoznačně • časově velmi náročná • bezpečnost asymetrických algoritmů (RSA, …)
• diskrétní logaritmus – nalézt v celých číslech Z neznámý exponent x z rovnice: – ≡ • znalost q, x, n – snadno spočtu Y • znalost Y, n – obtížné zjistit x • nejsou známy algoritmy s rozumnou výpočetní složitostí © Květuše Sýkorová
– řešení je považováno za příliš složité
• využívá spousta kryptosystémů (El‐Gamal, DSS, …) – výpočetní složitost srovnatelná nebo i vyšší než u faktorizace
• eliptické křivky – eliptický diskrétní logaritmus • používají výpočty nad dvěma tělesy – prvočíselné těleso » výpočty mod p – binární těleso » výpočty mod 2m
© Květuše Sýkorová
• výpočty bodů eliptické křivky – » nevlastní bod v nekonečnu
• nejsou známy algoritmy se subexponenciální výpočetní složitostí – řešení je považováno za příliš složité – u speciálních typů eliptických křivek je algoritmus znám » MOV útok pro supersingulární eliptické křivky se stopou ‐1
• generování náhodných čísel • dobrý generátor – důležitý • využití: – náhodný výběr klíče z celého prostoru klíčů
– generátor náhodných čísel (RNG)
© Květuše Sýkorová
• náhodná čísla – „bílý“ šum v elektronických obvodech – kosmické záření – počet produktů rozpadu radioaktivního vzorku / časová jednotka
– generátor pseudonáhodných čísel (PRNG) • klasické (program) – nevýhoda = zacyklení po určité době » čím delší doba, tím kvalitnější
• generování náhodných čísel – generátor • nelze – odhad vygenerované hodnoty na základě předchozích • statisticky rovnoměrné rozložení generovaných čísel
– kongruenční generátory
© Květuše Sýkorová
– třída modulo, rekurzivní výpočet
• Fibonacciho aditivní generátor • Lehmerův multiplikativní generátor • Kongruenční smíšený generátor
·
·
– nejrozšířenější LCG (lineární kongr. gen.)
• kvadratický generátor · • kubický generátor · • posuvný registr se zpětnou vazbou
· ·
·
– a spousta dalších (Blum‐Blum‐Shub, Mersenne twister, …)
• substituční šifry – šifrování pomocí křížů • šifra prasečích chlívků • velký polský kříž • malý kříž
© Květuše Sýkorová
– Hebrejské šifry • ATBAŠ • ALBAM • ATBAH
• monoalfabetická substituční šifra – jednoduchá záměna O.A. za Š.A. – svobodní zednáři • počátek 18. století • uchovávání tajných záznamů
© Květuše Sýkorová
– v té době již snadno luštitelná – dnes – pobavení pro školáky a táborníky
• šifrování pomocí křížů A
B
C
J
K
L
D
E
F
M
N
O
G
H
I
P
Q
R
S T
W U
V
X
Y Z
text = Jen se zeptej ječmene, snad si na to vzpomene.
© Květuše Sýkorová
o.t. = JEN SE ZEPTEJ JECMENE SNAD SI NA TO VZPOMENE A
B
C
J
K
L
D
E
F
M
N
O
G
H
I
P
Q
R
š.t. =
S T
W U
V
X
Y Z
text = Kuře bloudí mezi poli, pípá, pípá, nožky bolí.
© Květuše Sýkorová
o.t. = KURE BLOUDI MEZI POLI PIPA PIPA NOZKY BOLI
š.t. =
A
B
C
D
E
F
G
H
CH
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
text = Pověz milý ječmínku, jak mám najít maminku?
© Květuše Sýkorová
o.t. = POVEZ MILY JECMINKU JAK MAM NAJIT MAMINKU
š.t. =
A
B
C
I
J
K
R
S
T
D
E
F
L
M
N
U
V
W
G
H CH
O
P
Q
X
Y
Z
• hebrejci – prokazatelně používali
• monoalfabetické substituční šifry – jednoduchá záměna O.A. za Š.A. • Š.A. = O.A.
© Květuše Sýkorová
– odlišný předpis 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
• postup: – znak o.t. • vzdálenost od počátku abecedy
– znak š.t.
© Květuše Sýkorová
• stejná vzdálenost od konce abecedy
A
B
C
D
E
F
G
H
I
J
K
L
M
Z
Y
X
W
V
U
T
S
R
Q
P
O
N
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
M
L
K
J
I
H
G
F
E
D
C
B
A
text = Ječmen syčí mezi vousy: „Ptej se pšenic, vzpomenou si!“
© Květuše Sýkorová
o.t. = JECMEN SYCI MEZI VOUSY PTEJ SE PSENIC VZPOMENOU SI A
B
C
D
E
F
G
H
I
J
K
L
M
Z
Y
X
W
V
U
T
S
R
Q
P
O
N
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
M
L
K
J
I
H
G
F
E
D
C
B
A
š.t. = QVXNV MHBXR NVARE LFHBK GVQHV KHVMR XEAKL NVMLF HR
• postup: – abecedu rozdělíme na dvě poloviny – znak o.t. • vzdálenost od počátku jedné poloviny abecedy
– znak š.t.
© Květuše Sýkorová
• stejná vzdálenost od počátku druhé poloviny abecedy 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
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
text = Kuře pípá u pšenic, nevědí však také nic:
© Květuše Sýkorová
o.t. = KURE PIPA U PSENIC NEVEDI VSAK TAKE NIC
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
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
š.t. = XHERC VCNHC FRAVP ARIRQ VIFNX GNXRA VP
• postup: – abecedu rozdělíme na dvě skupiny po 9 znacích – znak o.t. • vzdálenost od počátku skupiny
– znak š.t.
© Květuše Sýkorová
• stejná vzdálenost od konce skupiny A
B
C
D
E
F
G
H
I
I
H
G
F
N
D
C
B
A
J
K
L
M
N
O
P
Q
R
R
Q
P
O
E
M
L
K
J
S
T
U
V
W
X
Y
Z
Z
Y
X
W
V
U
T
S
text = "Milé kuře, je nám líto, ptej se žita, poví ti to!"
© Květuše Sýkorová
o.t. = MILE KURE JE NAM LITO PTEJ SE ZITA POVI TI TO A
B
C
D
E
F
G
H
I
I
H
G
F
N
D
C
B
A
J
K
L
M
N
O
P
Q
R
R
Q
P
O
E
M
L
K
J
S
T
U
V
W
X
Y
Z
Z
Y
X
W
V
U
T
S
š.t. = OAPNQ XJNRN EIOPA YMLYN RZNSA YILMW AYAYM
© Květuše Sýkorová
