Date post: | 03-Jan-2016 |
Category: |
Documents |
Upload: | darryl-burns |
View: | 46 times |
Download: | 0 times |
Teorie čísel
• Prvočíslo
• Eulerova funkce φ(n)
• První hodnoty funkce φ: 1,1,2,2,4,2,6,3,6,4
• Pro a, b nesoudělná φ(ab)= φ(a). φ(b)
• P prvočíslo: φ(p)=p-1
Vlastnosti prvočísel
• Binomický koeficient (p nad i) mod p = 0, pro i=1..p-1
• (a+b)p mod p=ap+bp
• Pro c menší než p je cpmod p = c, cp-1mod p = 1
• N je součin dvou prvočísel p,q. φ(N)=(p-1)(q-1), c φ(N) mod N = 1
• Malá Fermatova věta
Distribuce klíčů D-H *1976
Whitfield Diffie *1944 Martin Hellban *1945
Massachusetts Institute of Technology (Boston)
Protokol SSL
Metoda Diffie Hellman
• Použiji jednosměrnou funkci f(x)=px mod q p,q jsou velká prvočísla.
• Uživatel A zvolí tajný klíč t, uživatel B tajný klíč s.
• Uživatel A spočítá f(t) = pt mod q = α a pošle• Uživatel B spočítá f(s) = ps mod q = β a pošle
Metoda Diffie Hellman
• A spočítá βt mod q = pst mod q = K.
• B spočítá αs mod q = pts mod q = K.
• K se použije jako klíč pro jednorázovou šifru (např. DES)
RSA šifra *1977
• Ronald Rivest *1947
Adi Shamir *1952
Leonard Adelman *1945
University of Southern California, Los Angeles
Protokol PGP
RSA šifra
• Dvě prvočísla p,q
• Šifrovací modul N=p.q
• Dešifrovací exponent t nesoudělný s N
• Φ(N)=(p-1).(q-1)
• s je řešení kongurence s.t mod Φ(N)=1
• Veřejný klíč: N,s
• Tajný klíč: p,q, Φ(N), t
RSA šifra
• Šifrovací zobrazení y=xs mod N
• Dešifrovací zobrazení x=yt mod N
• xst mod N = xkΦ(N)+1 mod N = 1k.x mod N = x
Příklad
• p=7, q=13
• N=91, Φ(N)=6.12=72
• t=7
• s.7 mod 72 = 1, s=31
• Veřejný klíč s=31, N=91, y=x31mod 91
• Tajný klíč t=7, p=7, q=13, Φ(N)=72, x=y7 mod 91
Příklad
• x=24• y= x31mod 91= 2431mod 91 =
(2416mod 91). (248mod 91). (244mod 91). (242mod 91). (241mod 91) = 24.30.81.9.81mod 91= 42515280 mod 91 = 80
• x = 807 mod 91= (801 mod 91). (802 mod 91). (804 mod 91) = 80.30.81 mod 91 = 24
Elektronický podpis
• X=yt mod N, y =xs mod A
• y=yst mod N = y
Jak vybrat prvočísla p, q
• Prvočísel je nekonečně mnoho
• Počet prvočísel menších než n: π(n)≈n/ln(n)
• Počet 100místných prvočísel: π(10100)- π(1099) ≈4,3*1097
• ln(10100) ≈ 230, každé 230 číslo je prvočíslo
Algoritmus pro hledání prvočísla
• Zvol náhodné číslo n
• Otestuj, jestli je prvočíslo
• Pokud ne, polož n:=n+1
Test prvočíselnosti
• Vyzkoušet všechny dělitele – nereálné
• Malá Fermatova věta, pro c<p, p prvočíslo platí: cp-1 mod p = 1
• Obrácené tvrzení neplatí
• Čísla, která splňují cp-1 mod p = 1 pro každé c a nejsou prvočísla, Carmichaelova čísla, nejmenší 561=3*11*17