Šifrová ochrana informací věk počítačů PS5-2

Bezpečnost informací – BI Ing. Jindřich Kodl, CSc.

Šifrová ochrana informací – věk počítačů PS5-2

VŠFS; Aplikovaná informatika; SW systémy – 2005/2006

1

Osnova

• • •

•

šifrová ochrana využívající výpočetní techniku – např. Feistelova šifra; symetrické a asymetrické šifry; základní symetrické šifrovací algoritmy; – algoritmus DES; – algoritmus AES; – odolnost soudobých symetrických šifrovacích algoritmů; základní asymetrické šifrovací algoritmy; – algoritmus RSA; – algoritmy na bázi eliptických křivek; – odolnost soudobých asymetrických šifrovacích algoritmů; – elektronický podpis;


2

Literatura

• Menezes A.J. a kol.: Handbook of Applied Cryptography,CRC Press, 1997 (dostupné i na Internetu)

Doporučená • Přibyl J.: Informační bezpečnost a utajování zpráv,ČVUT, 2004 • Přibyl J., Kodl J.: Ochrana dat v informatice, ČVUT, 1998 VŠFS; Aplikovaná informatika; SW systémy – 2005/2006

3

Asymetrické šifry • • • • •

Diffie - Hellman - algoritmus pro výměnu klíče (session key) - založen na obtížnosti výpočtu diskrétních logaritmů. ECC (Eliptic Curve Cryptography) - algoritmus založen na principu eliptických křivek - použití pro šifrování i výměnu klíčů - podstatně kratší klíče (5 - 10 x) oproti např. RSA RSA - autoři Rivest, Shamir, Adleman – použití pro šifrování i výměnu klíčů ElGamal – algoritmus založen na obtížnosti výpočtu diskrétních logaritmů použití pro šifrování i výměnu klíčů DSS (Digital Signature standard) FIPS PUB 186 - použití výhradně pro digitální podpis (spolu s jednocestným algoritmem SHA) - založen na obtížnosti výpočtu diskrétních logaritmů (obdobně jako Diffie - Hellman a ElGamal) - neprolomitelná délka klíče 1024 b


4

Asymetrické šifry – oblasti využití Kryptosystémy s veřejným klíčem lze obecně s výhodou využít ve třech základních směrech: • • •

šifrování dat; autentizace – elektronický podpis; ochrana přenášených tajných klíčů pro symetrické šifry.

Některé z algoritmů umožňují aplikaci ve všech uvedených směrech, jiné jsou speciálně navrženy buď pro jednu nebo dvě z těchto aplikací. VŠFS; Aplikovaná informatika; SW systémy – 2005/2006

5

Diffie-Hellman systém – systém dohodnutí klíče Systém uveden v článku „New directions in cryptography“ v IEEE Transactions on IT 1976 Popis základní metody – založena na složitosti výpočtu diskrétního logaritmu • Uživatelé se dohodnou na parametrech p a g; p je velké prvočíslo a g je prvočíslo a leží v intervalu 1,(p-1). Tyto parametry mohou být zveřejněny. • Dále se dohodnou na jednosměrné funkci kx = f(x) = gx mod(p)


6

Diffie-Hellman systém – dohodnutí klíče Uživatel A: zvolí si (vygeneruje) tajné číslo a vypočte ka = ga mod(p) odešle ka uživateli B

Uživatel B: zvolí si (vygeneruje) tajné číslo b vypočte kb = gb mod(p) odešle kb uživateli A

Nyní (ka)b = (kb)a = gab mod(p) = gba mod(p) = K; kde K je dohodnutý klíč VŠFS; Aplikovaná informatika; SW systémy – 2005/2006

7

Diffie-Hellman systém – dohodnutí klíče Klíč K může být použit jako klíč pro symetrickou šifru, nebo se z něj klíč pro symetrickou šifru odvodí. Klíče ka a kb jsou veřejné klíče – důležitý bezpečnostní aspekt = zajištění autentičnosti těchto klíčů Klasický D – H systém se používá pro distribuci klíčů. Existuje řada modifikací, které zvyšují bezpečnost systému, umožňují použití systému pro šifrování resp. elektronický podpis VŠFS; Aplikovaná informatika; SW systémy – 2005/2006

8

Algoritmus RSA Základ algoritmu RSA je postaven na zveřejnění modulo m = p * q, ale jeho dělitele p a q budeme držet v tajnosti. Veřejný klíč je dvojice celých kladných čísel (e,n) a privátní klíč je (d). Zašifrování datové zprávy = rozdělení na bloky o velikosti 0 až n-1. K zašifrování využijeme operaci umocňování, tj.: y = xe (mod n)

kde e je šifrovací klíč.

Při dešifrování se využije stejného matematického vztahu x = yd (mod n)

kde d je privátní tajný klíč.

Nutno nalézt takovou hodnotu d, která ve vztahu k e zajistí, že dešifrování je inverzní funkcí k šifrování. To znamená, že x = yd = xde (mod n) pro všechny hodnoty x VŠFS; Aplikovaná informatika; SW systémy – 2005/2006

9

Algoritmus RSA - Příklad Postup výpočtu dešifrovacího klíče d, pro zvolená prvočísla p a q, aby bylo n = 91. Hodnota zvoleného šifrovacího klíče je 29. Jsou zvolena prvočísla p = 7 a q = 13 a odtud dostaneme n = p*q = 7*13 = 91 Generování klíčů Výběr p, q

p a q jsou prvočísla

Nyní je nutné zvolit šifrovací klíč tak, aby byl nesoudělný s Φ(n) = (p – 1)(q – 1) = 6 x 12 = 72

Výpočet n = p * q Výběr celého čísla e

gcd ( e, Φ(n)) = 1; 1< d < Φ(n)

Výpočet d

d * e = 1 modulo Φ(n)

Veřejný klíč

(e,n)

Tajný klíč

d

Zvolili jsme číslo 29. Pomocí Euklidova algoritmu lze dokázat, že toto číslo není dělitelné s 91 nebo 72 a může být použito jako platný šifrovací klíč. 91 = (3) * 29 + 4 29 = (7) * 4 + 1 největší společný dělitel je roven 1 72 = (2) * 29 + 14 29 = (2) * 14 + 1 největší společný dělitel je roven 1 Odpovídající dešifrovací klíč 5 * 29 = 1 (mod 72) (tj. 145 = 144 +1) což znamená, že dešifrovací klíč d je roven 5.


10

Algoritmy na bázi eliptických křivek • pojem eliptická křivka (Elliptic Curve) = množina bodů (x,y) splňující rovnici F (x,y)=0; • pro prvočíselná tělesa má tvar: y2 ≡ x3 + ax + b (mod p), p prvočíslo • pro binární tělesa má tvar: y2 + xy ≡ x3 + ax2 + b (mod 2m), • EC kryptosystémy = varianty známých systémů s veřejným klíčem (např. DSA => ECDSA, D-H => ECC DH) místo s čísly se pracuje s body eliptické křivky


11

Algoritmy na bázi eliptických křivek • definují se základní operace s body křivky, kdy množina bodů křivky tvoří grupu; operace s body křivky jsou definované jako operace s čísly • výhoda - kratší klíče (cca řádově) než u standardních systémů při ekvivalentní úrovni bezpečnosti • bezpečnost těchto systémů závisí na obtížnosti řešitelnosti úlohy diskrétního logaritmu v grupách vytvořených na eliptických křivkách • základní problémy při nasazení = vyřešení otázek výpočetního charakteru – algoritmy pro sčítání bodů, násobení bodů křivky apod. VŠFS; Aplikovaná informatika; SW systémy – 2005/2006

12

Algoritmy na bázi eliptických křivek Operace sčítání bodů eliptické křivky


13

Algoritmy na bázi eliptických křivek Diffie Hellman kryptosystém dohodnutý klíč

ECC -systém na bázi eliptických křivek dohodnutý klíč


14

El Gamal algoritmus • Stejný princip jako systém D-H • využití pro digitální podpis i pro šifrování • bezpečnost spočívá ve složitosti výpočtu diskrétního logaritmu v konečném tělese Vygenerování páru klíčů • zvolí se prvočíslo p a dvě náhodná čísla g a x kde 1< x< p – 1 • vypočte se y = gx (mod p) • veřejný klíč - čísla p,g,y • tajný klíč číslo x


15

El Gamal algoritmus Šifrování zprávy zašifrování zprávy • zvolí se náhodné číslo k tak, aby nemělo žádné společné součinitele s (p – 1) • vypočte se: a = gk (mod p) b = yk M (mod p) • pár a,b tvoří šifrový text ( pozn. ŠT = 2 OT) dešifrování zprávy • vypočte se M = b / ax (mod p) neboť ( ax = gkx (mod p) a b / ax ≡ yk M / ax ≡ gkx M / gkx ≡ M (mod p) ) VŠFS; Aplikovaná informatika; SW systémy – 2005/2006

16

El Gamal algoritmus Digitální podpis • zvolí se náhodné číslo k tak, aby nemělo žádné společné součinitele s (p – 1) • vypočte se: a = gk (mod p) b takové, že M = (xa + kb) (mod p - 1) • podpis představuje pár a a b; náhodné číslo k musí být tajné • ověření podpisu = ověření platnosti ya ab (mod p) = gM (mod p) _____________________________ Každý podpis nebo šifrování vyžaduje nové k


17

Algoritmus DSA (Digital Signature Algorithm) • 1991 – publikována U.S. norma DSS (Digital Signature Standard) • DSA – varianta El Gamal schématu pro podpisy Vygenerování páru klíčů • zvolí se p = L-bitové prvočíslo kdy p = qz + 1 a L = 1024 • zvolí se q – 160-bitový prvočinitel čísla p - 1 • vypočte se g kde g = h(p-1)/q (mod p) > 1 a 1 < h < p-1 • vybere se x libovolné číslo 0 < x < q • vypočte se y = gx (mod p) • • •

parametry p, q, g jsou veřejné a mohou být společné pro celý systém, y = veřejný klíč x = tajný (privátní) klíč


18

Algoritmus DSA (Digital Signature Algorithm) Digitální podpis • vygenerování náhodného čísla k kde 1 < k < q • vypočte se r = (gk (mod p)) mod q • vypočte se vzorek zprávy pomocí hash funkce SHA-1 h = SHA-1(M) • vypočte se s = (k-1 (h + xr)) mod q parametry r,s tvoří podpis zprávy M • ověření podpisu

vypočte se

w = s-1 (mod q) u1 = (h * w) (mod q) u2 = (r * w) (mod q) v = ((gu1 * yu2 )(mod p)) (mod q)

platí – li v = r podpis je ověřen VŠFS; Aplikovaná informatika; SW systémy – 2005/2006

19

Odolnost kryptosystémů s veřejným klíčem Bezpečnost soudobých asymetrických kryptosystémů se opírá o výpočetní složitost matematických metod: • RSA - faktorizace velkých čísel • DSA – výpočet diskrétního logaritmu obdobně u kryptosystémů na bázi eliptických křivek – výpočetní složitost se odvíjí od základního schématu (místo práce s čísly se pracuje s body křivky) Největší rizika • chyby a zjednodušení při implementaci matematického modelu do systému; • nedostatečná aktualizace zvolených parametrů algoritmu (úprava požadované délky klíčů v závislosti na rozvoji analytických metod) ____________________ využití kvantových počítačů je v současnosti stále v teoretické rovině.


20

Šifrování zprávy vs. elektronický podpis 1

Šifrování zprávy

Šifrování a podepsání zprávy

2 Příklad rozdílu mezi procesem podpisu a šifrování (zdroj: Public Key Cryptography Author:Marcus Erber Date:November 2004)


Podepsání zprávy

21

Šifrová ochrana informací věk počítačů PS5-2

Recommend Documents