Úvod RSA Aplikace, související témata
RSA Ing. Štěpán Sem <
[email protected]>
Festival Fantazie, 2013
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Osnova
1
Úvod Základní pojmy Obtížnost Kryptografie
2
RSA Základní princip Matematické souvislosti Historie
3
Aplikace, související témata
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Vymezení pojmů
kódování přizpůsobení zařízení / kanálu morseovka ASCII (Latin2) „Unicode“
šifrování utajení obsahu sdělení Enigma
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Kódování textu
Latin2 Latin210 Latin22 Latin216 „LatinN“
M 77 01001101 48
A 65 01000001 41
E 69 01000101 45
L 76 01001100 4C
Štěpán Sem
S 83 01010011 53
RSA
T 84 01010100 54
R 82 01010010 52
Ö 214 11010110 D6 !
M 77 01001101 48
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Historie zabezpečení
kštice hůl Caesarova šifra Vernamova šifra veřejný vs. tajný algoritmus
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Matematický kontext
Z, N, N0 103 ≈ 210 = 1024
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Obtížné problémy
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Obtížné problémy – Trávníkář
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Obtížné problémy 2
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Obtížné problémy 2 – První kontakt
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Obtížné problémy – součet podmnožiny P vs. NP důkaz místo slibů? Problémy milénia, CMI (1 mil. $)
N k vs k N ,. . . ,N! Součet podmnožiny x1 w1 + x2 w2 + · · · + xN wN = K N
∑ xi wi = K
i=1
∃? xi ∈ {0; 1} Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Součet podmnožiny
Součet podmnožiny 3x1 + 5x2 + 7x3 + 2x4 = 9 ~x = (0; 0; 1; 1)
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Problém faktorizace
prvočíselný rozklad 60 = 22 · 3 · 5 m = p·q p, q =? p, q prvočísla
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Modulární algebra
programátorské % (Google kalkulačka) 3 · 7 mod 10 ≡ (3 · 7) % 10 ≡ 1
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Modulární algebra
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Problém diskrétního logaritmu
M = gx
mod n
x =?
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
John Forbes Nash, Jr. John Forbes Nash, Jr. b 1928 1994 Nobelova cena (ekonomie) návrh kryptosystému založeného na obtížně řešitelném problému dopis NSA (1955) utajen do 2011
A Beautiful Mind
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
Kryptosystém
Obrázek : (A)symetrický kryptosystém [PDK]
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní pojmy Obtížnost Kryptografie
(A)symetrická kryptografie symetrická kryptografie K1 = K2
asymetrická kryptografie (kryptografie s veřejným klíčem) K1 6= K2 bezpečnější pomalejší (cca 1000×)
kombinování asymetricky vyměnit klíče data šifrovat symetricky
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
RSA
Ron Rivest, Adi Shamir, Leonard Adleman (1977) Clifford Cocks (1973, odtajněno 1997) problém faktorizace (ϕ(m)) Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
RSA
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
RSA
(x i )j i ·j
mod m = x
mod (p − 1)(q − 1) = 1 i, j ∈ N
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Konstrukce RSA kryptosystému
velká prvočísla p, q, p 6= q ≈300 cifer (1000 bitů)
modul m = pq „zlikvidovat“ p, q volba klíčů veřejného (i) soukromého (j)
zveřejnění m, i
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Prvočísla do 1000 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Eulerova funkce ϕ(m) : počet čísel < m nesoudělných s m ϕ(mn) = ϕ(m)ϕ(n) m, n nesoudělná ϕ(p k ) = p k − p k−1 = p k−1 (p − 1) p prvočíslo počet čísel 5 p k soudělných s p k (násobkem) n · p 5 pk n 5 p k−1
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Eulerova funkce
Výpočet hodnot p, q různá prvočísla ϕ(p) = p − 1 ϕ(p k ) = (p − 1)p k−1 ϕ(p · q) = (p − 1)(q − 1)
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Eulerova věta Eulerova věta mod m = 1
aϕ(m) a, m ∈ N; nesoudělná
1·
ϕ(n)
ϕ(n)
ϕ(n)
∏ xi ≡
∏ axi ≡ aϕ(n)
∏ xi
1
1
axj ≡ axk
mod n
1
mod n ⇒ j = k
1 ≡ aϕ(n)
Štěpán Sem
mod n
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Volba klíčů i nesoudělné s ϕ(m)! j = i ϕ(ϕ(m))−1
mod ϕ(m)
Důkaz. aϕ(m)
mod m = 1
aϕ(ϕ(m)) mod ϕ(m) = i · i ϕ(ϕ(m)−1
Štěpán Sem
mod ϕ(m) = i · j
RSA
mod ϕ(m) = 1
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Ilustrativní kryptosystém osmibitové šifrování p = 17, q = 19 m = 17 · 19 = 323 = 256 ϕ(17 · 19) = (17 − 1) · (19 − 1) = 288 ϕ(ϕ(m)) = ϕ(25 · 32 ) = (1 · 24 ) · (2 · 31 ) = 96 i =7 j = i 96−1 Štěpán Sem
mod 288 = 247 RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Ukázka šifrování
ASCII ASCIIi=7
M 77 5
A 65 65
E 69 45
L 76 256
Štěpán Sem
S 83 155
RSA
T 84 0
R 82 64
O 79 79
M 77 5
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Slabiny nešifrovné zprávy 0, 1 x 2 mod (p · q) = x x1 = (p q−2 mod q) · p x2 = (q p−2 mod p) · q
σ = (1 + d (i − 1, p − 1)) · (1 + d (i − 1, q − 1)) σ 59 Ilustrativní kryptosystém x1 = (1717 mod 19) · 17 = 9 · 17 = 153 x2 = (1915 mod 17) · 19 = 9 · 19 = 171 σ = (1 + d (6, 16)) · (1 + d (6, 18)) = (1 + 2) · (1 + 6) = 21 Štěpán Sem
RSA
(OK) (OK) (KO)
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Důkaz RSA
i · j = k · ϕ(m) + 1 (x i )j = x ij = x k·ϕ(m)+1 x ϕ(m) x k·ϕ(m) x k·ϕ(m)+1
mod m = 1
mod m = 1k
mod m = 1
mod m = x k·ϕ(m) · x
Štěpán Sem
RSA
mod m
mod m = x
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Leonhard Euler
Leonhard Euler 1707-1783 švýcarský matematik, fyzik
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Malá Fermatova věta
Malá Fermatova věta bp−1
mod p = 1
b ∈ N, p prvočíslo; nesoudělná
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
(Malá) Fermatova věta
Star Trek: TNG Hotel Royale
(Velká) Fermatova věta (1993, Andrew Wiles)
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Základní princip Matematické souvislosti Historie
Pierre de Fermat
Pierre de Fermat 1601(1607?)-1665 francozský právník, soudce matematik „amatér“ xn + yn = zn
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Použití (RSA)
komunikace (PGP, GPG) end to end instant messaging Jabber, Pidgin (ICQ?)
elektronická pošta (Thunderbird)
elektronické bankovnictví elektronický podpis
zabezpečené prohlížení webu
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Elektronický podpis
Ilustrativní podepisovací mechanismus (x j )i
mod m = x
i h(M)j
Štěpán Sem
mod m = h(M)
RSA
Úvod RSA Aplikace, související témata
Pro samostatné studium – nástroje Faktorizace menších čísel http://laman.webz.cz/rozklad.php?num=288 Aritmetika velkých čísel https://defuse.ca/big-number-calculator.htm Největší společný dělitel http://gcd.awardspace.com/ Modulární násobení, umocňování velkých čísel http://www.cs.virginia.edu/cs200/lectures/notes36.html Převod do binární, hexadecimální soustavy http://easycalculation.com/decimal-converter.php Modulární aritmetika velkých čísel: http://web.math.princeton.edu/math_alive/Crypto/Lab2/ ModCalculator.html Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Literatura
[PDK] LEDA 2006 témata kódování šifrování digitalizace komprese teorie informace
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Literatura – volně související, zájmová
Academia 2003 (1998) základní myšlenky 140 stran A5 čistého textu
pro naprosté laiky
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Literatura – volně související, zájmová
Triton 2011 „policejní město“ RSA, GPG TOR další bezpečností mechanismy
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Obrázky, fotografie Rivset, Shamir, Adleman http://www.cs.virginia.edu/cs200/lectures/notes36.html Leonhard Euler https://en.wikipedia.org/wiki/File:Leonhard_Euler.jpg John Forbes Nash, Jr. http://www.freeinfosociety.com/media.php?id=1198 RSA tričko http://www.cs.virginia.edu/cs200/lectures/notes36.html Informační znak http://www.clker.com/cliparts/M/c/F/a/M/8/info-signmd.png
Štěpán Sem
RSA
Úvod RSA Aplikace, související témata
Obrázky, fotografie
Star Trek Nová generace, 2x12 (Hotel Royale) První kontakt
Trávníkář
Štěpán Sem
RSA