Úvod RSA Aplikace, související témata RSA. Ing. Štěpán Sem Festival Fantazie, Štěpán Sem

Úvod RSA Aplikace, související témata

RSA Ing. Štěpán Sem <[email protected]>

Festival Fantazie, 2013

Štěpán Sem

RSA


Štěpán Sem

RSA


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


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



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



Historie zabezpečení

kštice hůl Caesarova šifra Vernamova šifra veřejný vs. tajný algoritmus

Štěpán Sem

RSA



Matematický kontext

Z, N, N0 103 ≈ 210 = 1024

Štěpán Sem

RSA



Obtížné problémy

Štěpán Sem

RSA



Obtížné problémy – Trávníkář

Štěpán Sem

RSA



Obtížné problémy 2

Štěpán Sem

RSA



Obtížné problémy 2 – První kontakt

Štěpán Sem

RSA



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



Součet podmnožiny

Součet podmnožiny 3x1 + 5x2 + 7x3 + 2x4 = 9 ~x = (0; 0; 1; 1)

Štěpán Sem

RSA



Problém faktorizace

prvočíselný rozklad 60 = 22 · 3 · 5 m = p·q p, q =? p, q prvočísla

Štěpán Sem

RSA



Modulární algebra

programátorské % (Google kalkulačka) 3 · 7 mod 10 ≡ (3 · 7) % 10 ≡ 1

Štěpán Sem

RSA



Modulární algebra

Štěpán Sem

RSA



Problém diskrétního logaritmu

M = gx

mod n

x =?

Štěpán Sem

RSA



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



Kryptosystém

Obrázek : (A)symetrický kryptosystém [PDK]

Štěpán Sem

RSA



(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


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



RSA

Štěpán Sem

RSA



RSA

(x i )j i ·j

mod m = x

mod (p − 1)(q − 1) = 1 i, j ∈ N

Štěpán Sem

RSA



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



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



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



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



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



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



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



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



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)



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



Leonhard Euler

Leonhard Euler 1707-1783 švýcarský matematik, fyzik

Štěpán Sem

RSA



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



(Malá) Fermatova věta

Star Trek: TNG Hotel Royale

(Velká) Fermatova věta (1993, Andrew Wiles)

Štěpán Sem

RSA



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


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


Elektronický podpis

Ilustrativní podepisovací mechanismus (x j )i

mod m = x

i h(M)j

Štěpán Sem

mod m = h(M)

RSA


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


Literatura

[PDK] LEDA 2006 témata kódování šifrování digitalizace komprese teorie informace

Štěpán Sem

RSA


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


Literatura – volně související, zájmová

Triton 2011 „policejní město“ RSA, GPG TOR další bezpečností mechanismy

Štěpán Sem

RSA


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


Obrázky, fotografie

Star Trek Nová generace, 2x12 (Hotel Royale) První kontakt

Trávníkář

Štěpán Sem

RSA

Úvod RSA Aplikace, související témata RSA. Ing. Štěpán Sem Festival Fantazie, Štěpán Sem

Recommend Documents