Bankovní institut výsoká škola Praha Katedra informatiky a kvantitativních metod
Aplikace eliptických křivek v kryptografii Diplomová práce
Autor:
Bc.Elvira Djemileva ITM
Vedoucí práce:
Ing. Vladimír Beneš , Ph.D.
Praha
duben 2014 1
Prohlášení: Prohlašuji, že jsem diplomovou práci zpracovala samostatně a v seznamu uvedla veškerou použitou literaturu. Svým podpisem stvrzuji, že odevzdaná elektronická podoba práce je identická s její tištěnou verzí, a jsem seznámena se skutečností, že se práce bude archivovat v knihovně BIVŠ a dále bude zpřístupněna třetím osobám prostřednictvím interní databáze elektronických vysokoškolských prací.
V Praze, dne
Elvira Djemileva
Poděkování: Chtěla bych poděkovat Ing. Martinovi Záčkovi, Ph.D. za pomoc s vypracováním matematické části, a Ing. Vladimírovi Benešovi, Ph. D. za neustálou pomoc během psaní diplomové práce.
Anotace Diplomová práce se zabývá kryptografií nad eliptickými křivkami. Práce obsahuje podstatnou matematickou část, vysvetluje principy kryptografie eliptických křivek, popisuje algoritmy a eliptické kryptosystémy. Takže práce uvádí příklady nejmoderrnější kryptografie. Klíčová slova Principy eliptické kryptografie, kryptosystémy založené na eliptických křivkách, eliptické kryptosystémy
veřejného
klíče,
kryptografie
moderní
doby,
postkvantová,
biometrická
a termodynamická kryptografie.
Annotation This Thesis deals with Elliptic Curve Cryptography. The work includes a substantial mathematical part, explains the principles of ECC, describes the algorithms and elliptic cryptosystems. Also the Thesis provides the examples of modern cryptography
Key Words Principes of Elliptic Curve Cryptography. Elliptic Curve Cryptosystems, Public Key Elliptic Curve Cryptosystems. Modern cryptography, Post Quantum, Biometric and Thermodynamic Cryptography.
1 Obsah 1 Základní pojmy ................................................................................................................ 9
2
3
1.1
Celá čísla ........................................................................................................................ 9
1.2
Grupy ............................................................................................................................ 11
1.3
Prstence......................................................................................................................... 13
1.4
Mapování ...................................................................................................................... 14
1.5
Pole ............................................................................................................................... 14
1.6
Konečné pole ................................................................................................................ 16
Úvod do eliptických kryptosystémů veřejného klíče ................................................ 18 2.1
Kryptografie na bázi eliptických křivek(ECC)............................................................. 18
2.2
Problém diskrétního logaritmu ..................................................................................... 19
2.3
Bod násobení ................................................................................................................ 19
2.4
Skupina eliptických křivek ........................................................................................... 20
2.5
Diffie-Hellman(D-H) protokol distribuce klíčů ........................................................... 23
Eliptické kryptosystémy veřejného klíče .................................................................. 26 3.1
Srovnání s ostatními kryptosystémy veřejného klíče ................................................... 28
3.2
Otázky související s implementací ............................................................................... 28
3.3
Skupinové operace eliptických křivek nad ....................................................... 29
3.4 3.5
4
Skupinové operace eliptických křivek nad .................................................... 29
Kryptosystémy řešené jako konečné automaty ............................................................ 31
Eliptické kryptosystémy podle Neala Koblitze ........................................................ 33 4.1
Úvod ............................................................................................................................. 33
4.1.1. Eliptické křivky ...................................................................................................33
4.1.2. Vnořený otevřený text .........................................................................................35 4.1.3. Kryptosystémy .....................................................................................................36 4.1.4. Příklady................................................................................................................38 4.1.5. Primitivní body ....................................................................................................39 4.1.6. Nehladké cyklické podgrupy ...............................................................................41
5
6
Algoritmy veřejného klíče ........................................................................................ 42 5.1
Úvod ............................................................................................................................. 42
5.2
Bezpečnost algoritmu veřejného klíče.......................................................................... 42
5.3
Zavazadlový algoritmus ............................................................................................... 43
5.4
Superrostoucí zavazadlo ............................................................................................... 44
5.5
Vytvoření veřejného klíče z klíče soukromého ............................................................ 46
5.6
Šifrování ....................................................................................................................... 46
5.7
Dešifrování ................................................................................................................... 47
5.8
Praktické realizace ........................................................................................................ 47
5.9
Bezpečnost zavazadlového algoritmu .......................................................................... 47
5.10
RSA .............................................................................................................................. 48
5.11
El Gamalův systém ....................................................................................................... 51
5.12
El Gamalův podpis ....................................................................................................... 51
5.13
El Gamalovo šifrování .................................................................................................. 52
Standartizace ............................................................................................................. 54 6.1
IEEE P1363 .................................................................................................................. 54
6.1.1
Tradiční kryptografie veřejného klíče (IEEE Std 1363-2000 and 1363a-2004) .54
6.1.2
Schémata klíčové dohody ....................................................................................54
6.1.3
Podpisová schémata.............................................................................................55
6.1.4
Schémy kodování ................................................................................................55
6.1.5
Mřížkova Kryptografie veřejného klíče (IEEE Std 1363.1-2008) ......................55
6.1.6
Kryptografie veřejného klíče na bázi hesel .........................................................56
6.2
7
8
Aktualizované standardy pro eliptické křivky .............................................................. 56
6.2.1
Abstrakt ...............................................................................................................56
6.2.2
Úvod ....................................................................................................................57
6.2.3
Navrhované znění ................................................................................................57
6.2.4
Indikátor zabezpečení ..........................................................................................58
Kryptosystémy založené na eliptických křivkách .................................................... 60 7.1
LUC systém .................................................................................................................. 60
7.2
ECDH - Diffie-Hellman Eliptická Křivka .................................................................... 62
7.3
ECDSA - Algoritmus Digitálního Podpisu Eliprické Křivky ...................................... 62
7.3.1
Generování podpisů .............................................................................................63
7.3.2
Ověření podpisu...................................................................................................63
7.4
ECIES Integrovaná šifrovací schéma ........................................................................... 63
7.5
DLIES ........................................................................................................................... 65
7.5.1
Pro zefektivnění ...................................................................................................65
7.5.2
Závěr ....................................................................................................................66
Nové směry v kryptografii ........................................................................................ 67 8.1
Biometrická kryptografie.............................................................................................. 67
8.1.1
Problematické utajovaní ......................................................................................67
8.1.2
Biometrické uzamčení klíče ................................................................................68
8.1.3
Měření dynamiky stisku kláves ...........................................................................69
8.1.4
Model BioPKI .....................................................................................................70
8.1.5
Termodynamická kryptografie ............................................................................71
Závěr .................................................................................................................................. 74
Jaká je pravděpodobnost prolomení šifry? .......................................................................... 1 Permutace ................................................................................................................................... 1 Bez opakováni.................................................................................................................... 2 S opakovánim .................................................................................................................... 2 Hypergeometrické rozdělení....................................................................................................... 2 Hádání klíče Hypergeometrické rozdělení......................................................................... 4 Jaká je pravděpodobnost, že při třech pokusech klíč není v žadném? ............................... 4 Jaká je pravděpodobnost, že klíč se objeví aspoň v jednem? ............................................ 4 Jaká je pravděpodobnost, že odhadneme z jedného, druhého, nebo třetího pokusu? ........ 5
1 Základní pojmy Dříve než začneme diskutovat o eliptických křivkách a kryptosystémech veřejného klíče, prozkoumáme některé základy teorie čísel, lineární algebry, kryptografie atd., které podporují myšlenky následujících kapitol.
1.1 Celá čísla Skupina všech celých čísel bude označena jako Z. N znamená množinu všech kladných celých čísel. Pro konečnou skupinu A, počet prvků je označován # A. Relace ekvivalence na množině A, je taková binární relace, že pro každé x, y, z ϵ A. 1.
x~x
[reflexivita]
2.
když x ~ y pak y ~ x
[symetrie]
3.
když x ~ y a y ~ z to x ~ z
[transitivita]
Nechť ~ je relace ekvivalence na množině A. Pak P = {[a] | a ϵ A}, kde [a]= {b ϵ A} je rozděleníA, které 1.
pro každé S ϵ P, S ≠ ø
2.
když S, T ϵ P, pakS= T nebo S ⋂ T = ø
3.
U
Prvkům S ϵ P se říká třída rovnocennosti rozdělení P. Teorém 1.1.1 (Euklidův algoritmus rozdělení) Pro a, b ϵ Z, b ≠ 0 kde existuje jednoznačně určené q, r ϵ Z, jako například: , 0 ||
(1)
Jestli r = 0, řekneme, že b je dělitelem a, a označíme ho jako b|a. Jinak píšeme b a. Pro , ... ϵ
Z , jestliže b| (i = 1, . . . , k), pak b nazveme společný dělitel , ... . Největší společný dělitel 9
, ... vždy existuje. Je označen jako gcd ( , ... ). Prvkům a, b ϵ Z se říkáme nesoudělné
prvky, jestli máme jenom a* gcd(a,b) = 1.
Teorém 1.1.2 Jestli a, b ϵ Z, se nerovnají nule, pak d = gcd(a,b) je nejmenším prvkem skupiny všech kladných celých čísel ve tvaru ax+bx (x, y ϵ Z). Důkaz: Necht’ С = {c ϵ N | c = ax +by, x, y ϵ Z}. C ≠ ø, protože když a ≠ 0, -a ϵ C. Necht‘ !
(2)
je nejmenším prvkem C. Je třeba ukázat, že d = e. Jestli a = eq+r, 0 ≤ r<e, pak " 1 " "! .
(3)
Když r ≠ 0, to bude C a bylo by to v rozporu s naší volbou e. Tedy, e|a. Podobně, e|b, takže máme e
≤ d. Na druhé straně, poněvadž ! a d|a, d|b, z toho vychází, že d|e. Proto, d ≤ e. Tím
pádem, d = e.
Závěr 1.1.3 Existuje x, y ϵ Z které uspokojuje: ! %
(4)
jestli a jenom jestli d|c, kde d = gcd(a,b). Důkaz: Jestli a = ed, b = fd, z toho je jasné d|c. Na druhé straně, když d|c, necht’ kd = c. Protože zde
existuje , ! ϵ ' takové, jako:
! (
(5)
pak ) )! )( %
(6)
Pro , , * ϵ ' definujeme jako:
≡ *,(* jestli a jenom jestli *| " . Můžeme snadno vidět, že pro pevné m, to je vztah rovnocennosti na Z. V důsledku toho Z je
rozděleno do tříd rovnocennosti: '- ./0| ∈ '2, kde /0 . ∈ ' | ≡ *,( *2. Každá 10
třída rovnocennosti /0 je často představována jejím prvkem. Například, můžeme napsat '- .0, 1, 2, … , * " 12.
1.2 Grupy Definice 3.1. Grupou (5, ∘) nazýváme množinu 5 (tzv. nosič) spolu s binární operací ∘na množině 5, která splňuje následující axiomy: I) II) III) IV)
∀, ∈5, ∘∈5
∀, , %∈5, (∘) ∘% = ∘ (∘%) ∃e ∈5, ∀∈5, ∘ e = e ∘ =
∀∈5, ∃9∈5, ∘9 = 9∘ = e
Asociativita Existence neutrálního prvku Existence inverzního prvku
Platí-li navíc následující axiom, hovoříme o grupě abelovské. V)
∀, ∈5, ∘ = ∘
Komutativita
Poznámka 1.2.1.Dále: · Pokud pro (5,∘) platí pouze axiomy I) a II), nazývá se taková algebraická struktura pologrupa. · Pokud pro (5, ∘) platí pouze axiomy I), II) a III), označujeme takovou algebraickou strukturu jako monoid.
· Pokud operace (∘) představuje sčítání (+), hovoříme o aditivní grupě, neutrální prvek označujeme jako 0 (nulový prvek) a inverzní prvek značíme jako −a (opačný prvek). · Pokud operace (∘) představuje násobení (·), hovoříme o multiplikativní grupě, neutrální prvek označujeme jako 1 (jednotkový prvek) a inverzní prvek značíme jako : .
· Grupa (G, ∘) je konečná, jestliže počet prvků |G| je konečný. |G| je nazýván řádem grupy.
· Umocňování v grupě budeme definovat jako opakovanou aplikaci grupové operace (∘), např. ; = a ∘ a ∘ a.
11
Příklad Množina celých čísel < spolu s operací sčítání (+) tvoří abelovskou grupu. Množina <= s
operací sčítání modulo n tvoří grupu řádu n. Množina <= s operací násobení modulo n netvoří grupu, protože inverzní prvek neexistuje ke všem prvkům z <= .
Nechť n = 6. Tabulky v Tab. 1.1. představují postupně výsledky operace sčítání modulo 6, dále násobení modulo 6 a v poslední tabulce vidíme opačný a inverzní prvek (pokud existuje) pro prvky
ze <> . Aditivní opačný prvek k prvku a je −a | a + (−a) ≡ 0 (mod 6) a existuje pro každé a ∈ <> , např. 2 + 4 ≡ 0 (mod 6).
Multiplikativní inverzní prvek k prvku a je : | ·: ≡ 1 (mod n). Takovýto inverzní prvek
existuje tehdy a jen tehdy když N s D(a, n) = 1. Např. 5·5 ≡ 1 (mod 6), ale ke 2 inverzní prvek neexistuje. Definice 1.2.1. Nechť (G, ∘) je grupa, (H, ∘ ) je podgrupa grupy (G, ∘), jestliže je (H, ∘) grupa a H⊆G. Tab. 1.1. Operace (+), (·) a opačný a inverzní prvek v <> +
0
1
2
3
4
5
·
0
1
2
3
4
5
a
(- a)
a
0
0
1
2
3
4
5
0
0
0
0
0
0
0
0
0
-
1
1
2
3
4
5
0
1
0
1
2
3
4
5
1
5
1
2
2
3
4
5
0
1
2
0
2
4
0
2
4
2
4
-
3
3
4
5
0
1
2
3
0
3
0
3
0
3
3
3
-
4
4
5
0
1
2
3
4
0
4
2
0
4
2
4
2
-
5
5
0
1
2
3
4
5
0
5
4
3
2
1
5
1
5
Zdroj: vlastní úprava
Definice 1.2.2.Grupa (G, ∘) je cyklická, jestliže existuje prvek a ∈ G takový, že pro každé b ∈ G existuje celé číslo i takové, že b = . Takový prvek a se nazývá generátor grupy G. 12
Definice 1.2.3.Nechť (G, ∘ je grupa a a ∈ G. Řád prvku a je definován jako nejmenší kladné celé
číslo t takové, že = 1, pokud takové t existuje. Pokud takové číslo neexistuje, je řád prvku a
definován jako ∞. Poznámka 1.2.2.Platí: · Jestliže (G, ∘) je grupa a a ∈ G, potom množina všech mocnin prvku a tvoří cyklickou podgrupu grupy (G, ∘), kterou nazýváme podgrupa generovaná prvkem a a značíme ‹a›.
· Nechť (G, ∘) je grupa a a ∈ G je prvek řádu t. Potom |‹a›|, počet prvků podgrupy generované
prvkem a, je roven t.
· Každá podgrupa cyklické grupy (G, ∘) je také cyklická. Jestliže je cyklická grupa řádu n, potom
pro každý kladný dělitel d čísla n grupa (G, ∘) obsahuje právě jednu podgrupu řádu d.
Věta 1.2.1 (Lagrange). (G, ∘) a H její podgrupa, potom |H| dělí |G|. Proto jestliže a ∈ G, řád prvku a dělí |G|.
Nyní nechť binární operace (∘) představuje konkrétní operaci násobení (použijeme symbol*). Definice 1.1.4. Multiaplikativní grupa množiny <= je <∗= = {a∈<= | NSD(a, n) = 1}.Jestliže n je
prvočíslo, pak <∗= = {a | 1 ≤ a ≤ n - 1}. Poznámka 1.1.3.Dále:
· Nechť a ∈ <∗= . Řád prvku a je nejmenší kladné celé číslo t takové, že A ≡ 1 (mod n)
· Nechť a ∈ <∗= . Jestliže je řád prvku a roven φ(n), nazýváme jej generátorem (někdy také
primitivním prvkem) grupy <∗= . Pokud má grupa <∗= generátor, potom je to grupa cyklická.
1.3 Prstence Prstenec je skupina R spolu se dvěma binárními operacemi + a * (resp. sčítání a násobení) definována na R takto, že jsou splněny následující podmínky: ‹R, +› je abelova grupa 13
a · (b · c) = (a · b) · c pro každé , , % ∈ B [asociativita·]
a · (b + c) = a · b + a · ca (a + b) · c = a · c + b · c pro každé , , % ∈ B [distributivita· nad +]
Prstenec, který je násobením * je komutativní, a říká se mu komutativní prstenec. Takový prvek e
v prstenci R jako e *a = a *e = a, pro každé ∈ B je jednotkový prvek nebo multiplikativní
identita, a představeno 1. Když R má jednotkový prvek, říká se mu bud´ jednotkový prstenec, nebo prstenec s jednotkovým prvkem.
1.4 Mapování Necht´ a
jsou binární operace na množině respektive B a mapování C ∶ → F zachovává
operaci na , jestli pro každé , ∈ máme: f(ab) =f(a) f(b)
(7)
Necht´A a B jsou dvě grupy (neboli dva prstence). Operaci G ∶ → F říkáme homomorfismus A na
B, jestli h zachovává skupinovou operaci (neboli prstencovou operaci + a ·) na A. Homomorfismus h
je monomorfismem jestli h je jedna ku jedné (například jestli H , z toho vychází, že G H G. Prvku h říkáme mapa na B, jestli {G| ∈ 2 F. Monomorfismu na B říkáme
izomorfismus. Když máme izomorfismus A na B, říkáme, že A a B jsou izomorfní, a píšeme ≃ F.
1.5 Pole Pole F je komutativní prstenec s jednotným prvkem H 0, takový jako J ∗ . K J | H 02 je
multiplikativní skupinou.
Věta 1.5.1. Prstenec 'L je polem, jestli p je prvočíslem. Důkaz: Vzhledem k , ∈ ' připomeňme fakt, že:
p je prvočíslo ↔ p | ab znamená p | a nebo p | b
14
Jestli 'L je pole, označením 'L tvoří multiplikativní skupinu. Jestli p znamenat, že ∈ 'L ∗a že : existuje. Takže jestli p|ab a p
p je prvočíslo.
a, pak a ≢ 0 mod p. To bude
a pak N|: . Tím pádem,
A naopak, předpokládáme, že p je prvočíslo. Je to dostatečné pro to, aby ukázat, že 'L ∗ je
multiplikativní skupina, takže jenom potřebujeme ukázat, že každé ∈ 'L ∗ má svou multiaplikativní inverzi. Pro , ∈ 'L ∗ a ∈ 'L ∗,
jestli ≡ *,( N pak ≡ *,( N → " ≡ *,( N
protože N| " → N| nebo N| " a takže ∈ 'L ∗ znamená N . To ukazuje, že 'L . | ∈ 'L 2 'L . Tím pádem, každé ∈ 'L ∗ má multiplikativní inverzi.
Necht´ F je pole. Podmnožina K od F je také polem pod operacemi F (s omezením na K) se říká podpole F. V tomto případě, F se nazývá rozšířené pole od K. Jestli O H J, to K je řádné podpole
F. Poli se říká prvočíslo, pokud ono neobsahuje řádné podpole.
Pro každé pole F, průsečík J každých podpolí F nemá řádné podpole a J ⋍ Q( = pole všech racionálních čísel) nebo J ⋍ 'L kde p je prvočíslo
Poli F se říká, že má nulovou charakteristiku, jestli v J ⋍ Q , F má Q jako podpole. Říká, že pole
F má charakteristiku p pokud J ⋍ 'L .
Konečné pole je pole, které obsahuje jen konečný počet prvků. Každé konečné pole má prvočíslo
jako svou charakteristiku. V poli F s prvočíselnou charakteristikou p, pro každé ∈ J,
(8)
15
Necht´F je rozšíření pole od pole F.F = K(α), jestli F je nejmenší rozšíření pole (takže, průsečík všech rozšířených polí) K, které obsahují α. Jestli F je konečné pole charakteristiky p, to
multiaplikativní skupina F* = F\ {0} je cyklická a J 'L α, kde α je generátorem skupiny F.
Tím pádem α je primitivním prvkem F.
1.6 Konečné pole Pole má konečný počet prvků označených jako JS nebo GF(q), kde q je počet prvků. Tvrzení: Necht´F je konečné rozšíření stupně n nad konečným polem K. Jestli K má q prvků, to F má = elementů.
Důkaz Vlastně, necht´{α , … , α= } je základem pro F jako vektorový prostor nad K. Pak každé T ∈ J je jednoznačně zastoupené ve tvaru T % U ⋯ %= U=
(9)
kde % ∈ O 9 1, … , W . Protože každé % může být jakýmkoliv q prvkem od K, celkový počet
pro tuto kombinaci je = .
Důsledek:Jestli F je konečným polem charakteristiky p, to F má přesně N= prvků pro celé číslo n.
Tím pádem, každé konečné pole je rozšířením konečného stupně pole izomorfního k 'L , kde p je charakteristikou F.
Věta 1.6.1.Konečné pole J JLX je rozšířením pole 'L stupně n a každý prvek JLX je kořenem
polynomického L - x nad 'L . X
Důkaz:Charakteristikou JLX má být p. Množina J J \ .02 tvoří multiplikativní skupinu řádu
N= " 1 pod množením pole. Pro U ∈F*, řád U v této skupině dělí řád F*, N= " 1. Tím pádem, pro
každé U ∈F*, máme U L
X :
, takže U L U. Protože L " má většínu N= kořenů, JLX se skládá
ze všech kořenů L nad 'L . X
X
X
Příklad:Vidíme, že pole JZ[ obsahuje JZ (nebo 'Z ). Pokud napíšeme operaci sčítání v JZ[ jako
sčítání vektorů a napíšeme to jako produkt k nebo v (k,v ∈ JZ[ ) jako skalární produkt kv který patří 16
) ∈ JZ a \ ∈ JZ[ , pak JZ[ může být vnímán jako vektorový prostor nad JZ s rozměrem nad r.
Kromě toho, necht´d označuje dimenzi vektorového prostoru. Korespondence jedna-ku-jedné může
být nakreslená mezi prvky (vektory) tohoto d-dimenzionálního vektorového prostoru prvků na JZ .
Takže, musíme mít 2] prvků na tomto vektorovém prostoru. Protože d = r, JZ[ je vektorový prostor dimenzi
r.
Necht´JS^ je rozšířením JS . Dva prvky U, T ∈ JS^ jsou konjugované nad JS , jestli α a β jsou kořeny stejného nesnižitelného polynomu stupně m nad JS .U, U S , U S , … , U S _
konjugáty U ∈ JS^ s ohledem na JS .
Necht´JS^
je
rozšířené
{. U, U S , U S , … , U S _
^` a
pole
JS .
Základu
JS ^
(vektorový
prostor
^` a
nad
říká se jim JS )
formy
}, skládajícímu se ze vhodných U ∈ JS^ a jejich konjugátů s ohledem na JS
se říká normální základ JS^ nad JS . Pro každé rozšíření pole na konečný stupeň konečného
existuje normální základ.
17
2 Úvod do eliptických kryptosystémů veřejného klíče Eliptické křivky byly studovány matematiky přes více než století.Velmi bohatá teorie byla rozvinuta kolem nich, a postupně byla základem nového vývoje v matematice, nejpozorůhodnějším byl důkaz Fermatova teorému. Pokud jde o kryptografii zůčastněné, eliptické křivky jsou používány pro faktoring a prvočíselné prokázání. Eliptické kryptosystémy veřejného klíče (elliptic curves public-key cryptosystems) (ECPKC) byly navrženy nezávisle Victorem Millerem a Nealem Koblitzem v polovině osmdesátých let. Tito pracovníci neobjevili nový kryptografický algoritmus s eliptickými křivkami nad konečnými tělesy, ale pouze implementovali stávající algoritmy veřejného klíče, jako například Diffie-Hellmanův, pomocí eliptických křivek. Jak u všech kryptosystémů, obzvláště u kryptosystémů veřejného klíče, to trválo roky veřejného hodnocení dřív než byl stanoven dostatečný stupeň důvěry. Vypadá to tak, že ECPKSs dosáhl této úrovně. V polovině devadesátých let vznikají první komerční implementace, jako toolkity, ale takže real-world aplikace, jako zabezpečení e-mailů, čipové karty, atd.
2.1 Kryptografie na bázi eliptických křivek(ECC) Kryptografie na bázi eliptických křivek, neboli anglicky ECC (Elliptic Curve Cryptography) je kryptografií veřejného klíče. V kryptografii veřejného klíče každý uživatel nebo stroj se účastní komunikace, a obvykle má pár klíčů, veřejný a soukromý, a skupinu operací spojených s klíčem pro kryptografické operace. Pouze konkrétní uživatel ví soukromý klíč, kdýž veřejný klíč je znám všem účastníkům komunikace. Některé algoritmy veřejného klíče můžou vyžadovat předdefinované konstanty, aby byly známé pro každé zařízení které se zůčastní komunikace. “Domenové parametry” v ECC jsou příkladem podobných konstant. Kryptografie veřejného klíče, na rozdíl od kryptografie soukromého klíče, nevyžádá sdílený tajný klíč mezi komunikujícími, ale je mnohem pomalejší než kryptografie soukromého klíče. Matematické operace v ECC jsou definovány nad eliptickou křivkou ! Z ; , kde
4; 27 Z H 0. Každá hodnota a a b dává různou eliptickou křivku. Vše body (x, y), které splňují výše uvedenou rovnici a bod nekonečnosti, leží na eliptické křivce. Veřejný klíč je bodem na křivce,
a tajný klíč je náhodné číslo. Veřejný klíč se získává vynásobením soukromého klíče generátorem
18
bodů G na křivce. Generátor bodů G, a parametry křivky a a b, spolu s několika dalšími konstanty představuje domenový parametr ECC. Největší výhodou ECC je malá velikost klíče. 160-bitový klíč v ECC je stejně bezpečný jako 1024bitový klíč v RSA.
2.2 Problém diskrétního logaritmu Bezpečnost ECC závisí na složitosti Problému Diskrétního Logaritmu eliptické křivky. Necht’ P a Q
jsou body na eliptické křivce tak, že Q , kde k je skalární. Pokud P a Q je výpočetně nemožné získat k, pokud k je dostatečně velké. k je diskrétním logaritmem Q na bázi P.
Proto se hlavní operace zapojeny do ECC je bod násobení*, například násobení skalární k s jakýmkoliv bodem P na křivce, pro získaní jiného bodu Q na křivce. Příklad: Pokud a je libovolné celé číslo nesoudělné n a d je primitivním kořenem n, to existuje mezi čísla 0, 1, 2, … φW " 1, kde fW je Eulerová funkce, přesně jedno číslo µ takové jako: ≡ dg mod W.
(9)
Pak číslu µse říká diskrétní logaritmus a vzhledem k bázi d modulo n a je označena: k indn mod W.
(10)
Název „diskrétní logaritmus“ se používá v kryptografii nejčastěji, nebo se používá název „zobecněný multiplikativní řád“. V číselné teorii se často používán název „index“. Například, číslo 7 je kladným primitivním kořenem W 41 (ve skutečnosti, skupina primitivních kořenů 41 je dána
6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35), a když 15 ≡ 7; mod 41, číslo 15 má multiplikativní řád 3 s ohledem na bázi 7 (modulo 41) (Nagell 1951, p.112).
2.3 Bod násobení V bodě násobení bod P na eliptické křivce je vynásoben skalárním k za použitím rovnici eliptické křivky pro získání jiného bodů Q na stejné eliptické křivce, například kp = Q. Bodů násobení lze dosáhnout dvěma základními operacemi na eliptické křivce
19
•
Bod přidání, přidáním dvou bodů J a K pro získání jiného bodů L L,, například L = J + K.
•
Bod zdvojnásobení, přidáním bodů J pro získání jiného bodů L,, například L = 2J.
Příklad: Necht’ P je bod na eliptické křivce, k je skalár vynásobený bodem P pro získání jiného Příklad: bodu Q na křivce, například najít Q = kP. kP Když k = 23, kP = 23.
.
Tudíž bod násobení využívá bod přidání a bod zdvojnásobe zdvojnásobení ní opakovaně pro získání výsledků. Existují další efektivní metody pro bod násobení, například “Nepřilehlá forma” (Non (Non-adjacent adjacent form, neboli NAF), a wNAF(windowed NAF). Příklad bodů násobení jako srovnání ECDSA s ostatními podpisovými algoritmy bude také uuveden v následující následující kapitole.
2.4 Skupina eliptických křivek Eliptická křivka je množinou řešení rovnice: (11) Rovnice podobného druhu může být studována v různých matematických struktur strukturách, ch, jako prstencová struktura, nebo struktura pole. Pro naše účely budeme uvažovat pouze eliptické křivky nad poli. Tedy, koeficienty
jsou prvky pole, a podíváme se na všechny dvojici ((x,y), ), které splňují
rovnici , s x a y v poli. Obr.1 znazorňuje příklad eliptické křivky nad polem re Obr.1.a reálných lných čísel
. Tento graf může být získán
tím, že vyplní hodnoty pro x, a řešením kvadratické rovnicí v y.. V tomto konkrétním případě graf se skládá ze dvou samostatných částí, ale není tomu tak vždy. To ukazuje, že mn množina ožina řešení eliptické křivky má některé zajímavé vlastnosti. Zejména, může skupinová operace být zakotvena v této sadě, a tímto způsobem získáme skupinu, která nám umožňuje dělat šifrování, jak vidíme v § 3. Skupina je matematická struktura skládající se ze množiny prvků G,, se skupinovou operací ◊ definované na prvky množiny. Abychom to mohly považov považovaatt za skupinu, operace ◊ musí splňovat splňovat 20
následující vlastnosti:
-uzavření: pro všechny x, z v G, x ◊ y musí být v G; -asociativita: pro všechny x, y a z v G, musíme mít (x ◊ y) ◊ z= x ◊ (y ◊ z); -identita: existuje takové e v G, jako x◊e = e◊x = x pro všechny x; - inverze: pro všechny x existuje takové y, jako x◊y = y◊x = e Vpravo (on top of that), máme abelovskou vlastnost: abelová: pro všechny x, y, v G, máme x◊y = y◊x, v tomto případě říkáme, že grupa je abelová. Je možné převest soubor bodů na eliptické křivce do grupy? Odpoved’ je kladná, ale jak bychom měli definovat operaci na bodech křivky, s vlastností uvedenou výše? Tohoto cíle lze dosáhnout takto: vybrat dva body na křivce, označit jako p a pZ , a konstruovat čáru přes tyto dva body. V
obecném případě, bude tento řádek vždy mít třetí bod průsečíku s křivkou. Ted’ vememe ten třetí bod a zkonstruujeme svislou čáru přes druhý bod průsečiku této svislé čáry s křivkou definovanou
sumou p a pZ . Jestli p a pZ se rovnají, čára, kterou jsme zkonstruovali na počátku je tangentou křivky, která je zase přesně jiným bodem průsečiku s křivkou. Toto skupinové pravidlo je
znázorněno na Obr.1a. Poznámka na skupině je abelovská; aditivní notace je často používána pro skupinové pravidlo abelové grupy. Důležitá otázka, která stále potřebuje odpověd’ je = co je identitou grupy. Například v Obr.1a., jaký
bod máme přidat ke p; abychom získali jako součet? Můžeme pouze najít odpověd’ na tuto otázku
jestli extra nevlastní bod O je přidán ke křivce, která leží nekonečně daleko na svislé ose.
21
Obr.1.a.Příklad eliptické křivky nad polem reálných čísel, a demonstrace skupinové operace
Zdroj: Rektorys Karel a spolupracovníci,Přehled užité matematiky
Bod O je identitou skupiny eliptické křivky. Ted’ si mužeme uvědomit že tahle operace je řádně definovanou operací skupiny, ačkoliv některé z požádavků (např. asociativita), jsou daleko od triviálního důkazu. Pro kryptografické aplikace není moc praktické konstruovat výsledek skupinové operace grafickým způsobem. Nicméně, je možné najít blízkou formulu, která představuje souřadnice ( , ! ) součtu p , dvou bodů p a pZ jako funkce jejich souřadnic ( , ! ) a ( Z , !Z ). Pro případ reálných čísel, rovnice křivky může být zjednodušeno na formu:
22
! Z ; .
(12)
Vzorce skupinové operace jsou: q " " Z ;
(13)
! q " " ! ; s_ :sa
t_ :ta
q =r;t _ vw a
Zsa
)(!ž p H pZ
)(!ž p pZ
(14)
x
(15)
Tyto rovnice jsou platné za výjimkou triviálních případů, kdy p nebo pZ se rovná bodu nekonečna,
nebo v případě -p , která má souřadnice ( , "! ), se rovná pZ . Nevýhodou použití reálných čísel
pro kryptografii je, že je velmi těžké uložit přesně v paměti počítače, a předpovědět, kolik místa budeme pro ně potřebovat. Ten problém můžeme vyřešit použitím koněčného tělesa, tzn. takového tělesa které má koněčný počet prvků. Protože počet prvků je konečný, můžeme najít unikátní zastoupení pro každý z nich, což nám umožňuje ukládat a zpracovávat prvky ovladatelným
způsobem. Číslo prvků koněčného tělesa (též Galoisovo těleso) je vždy kladný primární výkon N= ; odpovídající pole je označene GF(N= ). Dva zvláštní případy jsou populární pro použití v ECPKC:
pole formy GF(p)(nebo n 1), a pole formy GF(2= ), nebo p 2. Koněčná tělesa je těžko reprezentovat grafickým způsobem, a proto se musíme spoléhat na vzorce pro skupinové operace. Pro GF(p) vzorce jsou stejné jako pro realná čísla; pro GF(2= ) jsou mírně odlišné.
2.5 Diffie-Hellman(D-H) protokol distribuce klíčů Diffie-Hellman (D-H) protokol distribuce klíču je kryptografický protokol, pomocí kterého lze vytvořit mezi komunikujícími stranami šifrované spojení, přes nezabezpečený kanál, a to bez předchozího
dohodnutí
šifrovacího
klíče.
Výsledkem
tohoto
protokolu
je
vytvoření symetrického šifrovacího klíče, který může být následně použit pro šifrovaní zbytku komunikace. Výhodou je, že případný útočník odposlouchávající komunikaci tento klíč nezachytí klíč je zkonstruován všemi účastníky komunikace a nikdy není poslán v otevřené formě. Nevýhodou tohoto
protokolu
je
bezbrannost
protiútoku 23
“Man
in
the
middle”,
protože
neumožňuje autentizaci účastníků. Nebudeme-li kombinovat tento protokol s jinými metodami, je tedy vhodný pouze tam, kde útočník nemůže aktivně zasahovat do komunikace. Počet účastníků však není omezen. Problém distribuce klíčů se stal klíčovým problémem symetrického šifrování a základním úkolem moderní kryptografie. Bez jeho vyřešení nebylo možné používat symetrické šifrovací algoritmy v počítačové komunikaci. Hledáním způsobu,
jak provést bezpečnou výměnu klíče otevřenou
cestou, se zabývali vědci Whitfield Diffie a Martin Hellman. Této dvojici se po několikaletém snažení podařilo řešení najít. Jejich algoritmus opět vychází z principu modulární aritmetiky. Předpokládejme, že dvě strany A a B se chtějí výměnit otevřenou cestou klíč, který jim umožní šifrovat a dešifrovat následnou komunikaci. Nejdříve se výmění veřejnou informaci, s jejiž pomocí vygenerují stejný symetrický klíč. Následující popis objasňuje podstatu algoritmu Diffie-Hellman: •
odesílatel a příjemce se dohodnou na dvou veřejných parametrech M a N; Mje prvočíslo a N
•
odesílatel generuje náhodné privátní číslo x a vypočítá veřejnou hodnotu | z t *,( {,
(generator) a platí z {, kterou odešle příjemci,
•
příjemce generuje náhodné privátní číslo y a vypočítá veřejnou hodnotu p z s *,( {, kterou odešle odesílateli,
• • •
odesilatel obdrží od příjemce hodnotu P, ze které výpočte klíčO}~ pt *,( {,
příjemce obdrží od odesilatele hodnotu O, ze které vypočte klíč O~} |s *,( {,
protože platí O}~ O~} O, mohou další komunikaci odesilatel a příjemce šifrovat tímto klíčem.
Příklad: Příjemce se s odesílatelem dohodli na veřejných hodnotach N = 5, M = 563. Odesílatel generuje
náhodné
číslo
9
jako
své
soukromé
číslo
x
a
vypočíta
hodnotu
z t *,( { 5 *,( 563 78 . Podobně postupuje i příjemce. Náhodně si zvolí např. 14 jako své
soukromé číslo y a vyčíslí stejně jako odesílatel hodnotu z t *,({ 5 *,( 563 534.
Vypočtené hodnoty 78 a 534 si komunikující strany vymění a pomocí svých soukromých hodnot vypočtou shodný klíč"534 *,( 563 117, 78 *,( 563 117.
Výše uvedený princip má jeden nedostatek. Vyžaduje aktivní účast obou stran, která např. v poštovní komunikaci není možná. Z úvah spojených se vznikem výše popsaného algoritmu však 24
vytvořil W. Diffie také koncepci asymetrické kryptografie opírající se o veřejný a soukromý klíč. Vlastní algoritmus však vznikl v roce 1977. Vytvořili jej trojice vědců Ronald Rivest, Adi Shamir a Leonard Adleman a nazvala jej RSA.
25
3 Eliptické kryptosystémy veřejného klíče Hodně kryptosystému veřejného klíče jsou založeny na problému diskrétního logaritmu (DLP) ve skupině. Dále budou uvedeny několik příkladů libovolných skupin, a pak omezíme pozornost na eliptické křivky. DLP ve skupině G, ◊může být definována takto: necht‘ x a y jsou prvky G, a y byl získán opakovaným použitím skupinové operaci x, jako y = x ◊ x ◊ ... ◊ x, kde počet n podmínek na pravé straně rovnice je neznámý. Mimo jiné bereme na vědomí, že y = x. Pak DLP spočívá v nalezení n, když víme jenom x a y, a vlastnosti skupiny. Složitost vyřešení DLP záleží na vlastnostech skupiny G. Ve skupině obecně, bez dodatečných vlastností, které umožňují "zkratky" (shortcuts), DLP je obtížný problém, v tom smyslu, že složitost nejznámějších algoritmů je přibližně rovna odmocnině velikosti skupiny. Nicméně, řada zajímajících skupin má další strukturu, která umožní použití vyšších algoritmů, takže tyto skupiny méně vhodné (ale ne však zbytečné) pro kryptografii. Diffie-Hellman protokol distribuce klíčů je příkladem toho jak kryptosystém veřejného klíče může být konstruovan na základě DLP ve skupině (Obr.1.b). Tradičně strany v protokolu se nazývají Alice a Bob. Obr.1.b. Diffie-Hellman protokol distribuce klíčů Alice Zvolí a, vypočte dw
Bob
dw
zvolí b, vypočte d
d vypočte d ª= dw O
vypočte dw ᵇ Zdroj: vlastní úprava
26
= dw O
Situace(Setup) Alice a Bob se dohodli na společné skupině G a společném skupinovém elementu g. Poté Alice zvolí tajné číslo a, které slouží jako tajný klíč, a Bob zvolí tajný klíč b. Komunikace Alice vypočítí dw a posílá to Bobovi veřejným kanálem; Bob posílá Alice d .I když
dw a d jsou úzce souvisí s a a b., spolehlivost DLP zajišťuje, že tajný klíč nemůže být výpočítán
z nich v praktické situaci. Proto dw a d můžou sloužit jako veřejné klíče, odpovídající příslušným
soukromým klíčům Alice a Boba.
Závěrečný krok Alice přijímá veřejný klíč Boba a vypočítád ª
=
dw ; Bob vypočítá dw ᵇ
=
dw . Jak můžeme vidět, Alice a Bob získali stejný výsledek, a ten výsledek nemůže být vypočítán
protivníkem, který zná jenom veřejné klíče. Proto Alice a Bob se dohodli na sdílení tajného klíče.
Uvědomme si, že je třeba příjmout opatření pro zabezpečení tohoto protokolu proti pasivním a aktivním útokam. Jejich popis by zabral moc času a mohl by být dalším tématem k diplomové práci, proto tady jim nebudeme věnovat. Mimo jíné uvědomte se, že spolehlivost DLP nezaručuje
bezpečnost Diffie-Hellman protokolu: výpočet dw z dw a d může být snadňeji než výpočet a z dw nebo b z d .
Doted’ nemáme určené konkrétní skupiny, ve kterých pracujeme. Zajímavými kandidáty jsou skupiny, kde DLP je těžko vyřešit. Příklady skupin, které byly používány zhruba 20 let jsou
multiplikativní skupiny konečného tělesa, zejména
podpisy, ElGamalové šifrování a DSA, kde p obvykle má z bezpečnostních důvodů alespoň 1024 bitů. V polovině osmdesátych let Victor Miller a Neal Koblitz nezávisle navrhly k použití skupiny eliptických křivek nad koněčným tělesem, pro kryptografii veřejného klíče. Nebyli známe žadné zkrátky pro řešení eliptické křivky DLP (ECDLP) rychleji než v době úměrné odmocnině z velikosti skupiny, a až doted’ je to ještě ten případ, s výjimkou několika degenerovaných tříd křivek. Všechny kryptosystémy na bázi DLP mužou být převédeny do eliptických křivek, takže máme ECDSA, EC Diffie-Hellman, EC ELGamal encryption, a tak dále. Některé drobné technické úpravy 27
jsou nezbytné k přizpůsobení k prostředí eliptických křivek, ale základní principy jsou stejné jako u ostatních DLP systémů.
3.1 Srovnání s ostatními kryptosystémy veřejného klíče Jak lze porovnat eliptické kryptosystémy veřejného klíče s ostatními populárními systémy jako
jejich protějšky založené na grupě
Velice důležitým postřehem je to, že dobré známé algoritmy pro CPLP mají složitost proporcionální odmocnině velikosti skupiny, zatímco DLP v
subexponenciální čás. To znamemá, že pro jistou úroveň bezpečnosti, velikost parametrů může být podstatně menší. Je těžké získat přesné bezpečnostní odhady pro ES, ale odborníci v oboru odhadují, že skupina eliptických křivek o velikosti 175-bitů je ekvivalentní RSA s 1024-bitovém modulem nebo systémem založeným na 1024-bit prime. Menší velikost bloku má významné důsledky prostředků potřebných k implementaci ECPKC. Například, mnohem méně čipovaný prostor je potřebný pro procesor eliptické křivky, než na RSA procesor. V aplikacích, kde šířka pásma je otázkou, můžou eliptické křivky také nabídnout výhodu. V protokolu dohody eliptických křivek podpis je jenom 340 bitů dlouhý, na rozdíl od 1024 bitů RSA podpisu. Uvědomte se, nicméně DSA podpisy jsou jenom 320 bitů dlouhé a že je možné snižovat provozní zatížení při skladování RSA podpisu obnovením části zprávy od podpisu. Skupinové operace ES jsou složitější, než základní operací jiných systémů, jako jsou RSA, a proto menší velikost bloku se neprojeví proporcionálně výkonnosti čísel.
3.2 Otázky související s implementací V této sekci budou probrány některé aspekty implementaci softwaru pro CPKC. Časově náročné operace v ECPKC je násobení bodu na křivku celým číslem, tj. opakované operace skupiny, které také říkají C umocňování, protože je podobná umocňování jiných systémů na bázi diskrétního logaritmu. Implementace je opakované operace skupiny, která se skládá ze dvou úrovní hierarchie: skupiny obslužné úrovně, a úrovně výpočtu bodového násobení pomocí jedné skupiny operací. Dále bude diskutováno o obou úrovních ve samostatních odstavcích.
28
Takže, podle kap. 2., jsme viděli že v kryptografii eliptické křivky nad dva druhů polí
použivané: 5JN nebo 5J2= . Dále bude diskutováno o skupinové činnosti obou polí v samostatných odstavcích.
3.3 Skupinové operace eliptických křivek nad Vzorce pro skupinové operace eliptických křivek nad 5JN byly uvedeny v kap. 2. Z nich vychází,
že skupinové operace můžou být vypočtény na základě několika polních operací, jako je sčítání,
odčítání, násobení a inverze. Pole 5JN je obvykle představeno celými čísly modulů p, a tedy i operace pole jsou modulární operace potřebné v dalších veřejných klíčových kryptosystémach jako například RSA a DSA. Proto části softwarové knihovny pro poslední můžou být znovu použité pro eliptické křivky nad 5JN.
Inverzní operace zaslouží zvláštní pozornost. Ve většině kryptosystémů veřejného klíče, modulární inverze není tak důležitá, ale v ECPKC se ukázalo, že hlavní překážkou je, pokud skupina operace se provádí přímým způsobem. Naštěstí, je možné snížit počet inverzí představením bodů v projektivních polohách. Tabulka 1.1.2 dává typické časování pro pole operací a skupinových operací pro případ 5JN.
3.4 Skupinové operace eliptických křivek nad
Rovnice a vzorce eliptických křivek pro koněčná tělesa 5J2= se mírně liší. Rovnice křivky může
být zjednodušená do:
! Z ! ; Z , a přidáné vzorce jsou: qZ q Z , ! q ! , s q
s_ vsa )(!ž p H pZ t_ vta x =r s a )(!ž p pZ t
(16) (17) (18)
(19)
a
Na rozdíl od 5JN, počet různých reprezentací obvykle používá pro elementy pole 5J2= .
Nejjednodušší reprezentace je ve standardním základu, kde prvky jsou binární polynomy stupně 29
menší než n, a výpočty jsou prováděny modulem ireducibilního binárního polynomů stupně označeného přesně n. Další zastoupení jsou založeny na optimálních běžných podkladech. V tomto případě
jsou
prvky
{T Z , T Z , T Z , … , TZ
a
_
X` a
reprezentovány
jako
lineární
kombinace
prvků
množiny
}, kde T je vhodně zvolený prvek pole. Třetí představení, nebo tower field
representace, představuje elementy jako polynomy nad polem 5J2 , kde r je dělitelem n.
Tabulka 1.2 uvádí typické časování pro oblast operací pole a skupinových operací pro 5J2=
pomocí standardního základu.
Tab 1.2. Časování pro operace pole nad 5JN a 5J2= . Standartní základ se používá pro
poslední. Velikost pole je zhruba 191 bitů pro oba dva. Všechno časování je dano v µs. 5JN
5J2=
násobení
7.8
39
srovnání
7.6
2.6
inverze
180
126
IS doplnění
103
215
IS double
76
220
přidání
1.6
0.6
Zdroj: State of the Art in Applied Cryptography
Jakmile máme k dispozici algoritmy pro skupinové operace, podíváme se na metodu, která vypočítá bodové násobení za použitím tak malé skupiny operaci, jak je to možné. To odpovídá problému výpočtu umocňování pomocí násobení, rovněž i v jiných kryptosystémech jako například RSA nebo DSA. S algoritmy pro bodové násobení, je možné začít budováni různých systémů veřejného klíče. Tab 1.1.3. porovnává vykonnost podpisových schémat na základě eliptických křivek k ostatním podpisovým schématům. Tab 1.3Srovnání ECDSA s ostatními podpisovými algoritmy. Pro EC, velikost pole je kolem 191 bitů. Modulo pro RSA a DSA je dlouhé 1024 bitů; veřejný exponent RSA je 3. Vše je v milisekundách, pokud není ukázano jinak. čás v ms
5JN 30
5J2= RSA
DSA
generování klíčů znak ověřování bod násobení obecně
5.5 6.3 26 21.1
11.7 11.3 60 56
1s 43.3 0.65
7 7 28.3
Zdroj: State of the Art in Applied Cryptography
3.5 Kryptosystémy řešené jako konečné automaty Čínský kryptograf Tao Renji vyvinul algoritmus veřejného klíče na principu konečného automatu. Tak jak je obtižné faktorizovat součin dvou velkých prvočísel, tak je obtížné provést rozklad dvou složených konečných automatů. Zvlášt’ obtížné je to tehdy, když jeden nebo oba automaty jsou nelineární. Většina výzkumných práci v této oblasti se uskutečnila v osmdesatých letech a výsledky byly publikovány v činštině. Renji začíná publikovat v angličtině. Hlavním výsledkem jeho práce bylo poznání, že určité nelineární automaty (kvasilineární automaty) mají snadno realizovatelné inverze tehdy a jen tehdy, když jejich maticová struktura má určité stupňovité řazení. Tato vlastnost se ztrácí po spojení s jiným automatem (dokonce i s lineárním). V algoritmu veřejného klíče je tajným klíčem invertovatelný kvasilineární automat s lineárním automatem a odpovidající veřejný klíč se dá odvodit vynásobením obou automatů člen po členu. Data se zašifrují přenosem veřejným automatem a dešifrují přenosem inverzemi jeho komponent (v některých případech musí být tyto komponenty uvedené do vhodného počatečního stávu). Toto uspořádaní může sloužít jak pro šifrování, tak pro digitální podpis. Chování těchto systémů lze shrnout podobně jako u systému Mc.Eliceova výrokem: pracují mnohem rychlejí než RSA, ale vyžadují delší klíče. Klíč o delce 1792 bitů zajiš'tuje stejnou bezpečnost jako 512-bitový RSA a klíč o delce 4152 bitů bezpečnost jako 1027-bitový RSA. V prvním případě systém při použití 33 MHz mikroprocesoru 80486 šifruje data rychlostí 20.869 bytů/seca dešifruje data rychlostí 17.117 bytů/sec. Renji popsal tři algoritmy. První FAPKCO, sloužící především pro ilustraci, je systémem jednoduchým, který využívá lineární komponenty. Dva seriózní systémy FAPKC1 a FAPKC2
31
využívají každý po jedné lineární a jedné nelineární komponentě. FAPKC2 je mnohem složitější a byl vyvinut pro podporu operace k určení identity. Přes obtížnost této problematiky bylo v Čině na tomto poli vykonáno poměrně mnoho prácí, z literatury publikované v čínštině je zřejmé, že je tomuto problému věnována značná pozornost.
32
4 Eliptické kryptosystémy podle Neala Koblitze Abstrakt. V této práci budou probírány analogicky na bázi eliptických křivek nad konečnými poli kryptosystém veřejného klíče, které jsou multiplikativní skupinou konečného pole. Této eliptické kryptosystémy můžou být víc bezpečnými, protože analog problému diskrétního logaritmu na eliptických křivkách je pravděpodobně složitější než klasický problém diskretního logaritmu,
obzvlášt’ nad 5J2= . Dále bude diskutována otázka primitivních bodů na eliptické křivce modulo
p, a představen teorém na nehladkosti (nonsmoothnes) řádu cyklické podgrupy generované globálním bodem.
4.1 Úvod První kryptosystémy veřejného klíče používající teorii čísel byly založeny na stejné struktuře jako u multiplikativní skupiny (Z/N Z)* nebo multiplikatvní skupině konečného pole GF(q), N= .
Následující konstrukce analogových systém na bázi Abelové grupy spolu s H.W. Lenstrovým uspěchem v použití eliptických křivek v celočíselné faktorizaci, dělá přírozeným prozkoumaní možností kryptografii veřejného klíče na bazi struktury skupiny bodu eliptické křivky nad velkým konečným polem. Nejdřív stručně vzpomeneme na fakty potřebné pro této eliptické křivky. Pak budou popsané analogové systémy eliptických křivek, jako Massey Omura a ElGamal. Dále jsou představený několik konkrétních příkladů, probrana otázka primitivních bodů, a vše je uzavřeno teorémem týkajícím se pravděpodobností toho že řáda cyklické podskupiny je nehladká.
4.1.1. Eliptické křivky
Eliptická křivka definovaná nad polem K s charakteristiky H 2 nebo 3, je skupinou řešení , ! ∈ O Z k rovnici:
! Z ; , , ∈ O
(20)
(kde kubická pravá strana nemá žádné vicenásobné kořeny). Přesněji, je to skupına řešení spolu s “bodem nekonečností” (s homogenními koordinaty (0, 1, 0); jestli K jsou realná čísla, to odpovídá
vertikálnímu směru, který je tečnou k zblížuje jako → ∞). Začneme se složitějšího obecného vzorce pro který může být snadno snížen ke (20) lineárními změnami proměnných, všude kde 33
znak O H 2, 3. Pokud znak K = 2 – důležitým případem v možných aplikacích, tento obecný vzorec může být snížen o lineární změnu proměnných formou:
! Z % ! (! ; , , , %, ( ∈ O.
(21)
Body na tvoří skupinu s elementem identity bodu v nekonečnu. Zápor bodu p ∈ je druhým
bodem na který má stejné x-sořadnice jako P. Necht’ p , ! a pZ Z , !Z nejsou body
nekonečnosti a nejsou navzájem záporné. Jestli K jsou realná čísla, máme jednoduchý geometrický
popis. Necht’ p; ; , !; který je jejich součtem: nakreslíme čáru přes p a pZ (tečná ke křivce na p pokud p pZ ), a necht’p; je záporem třetího bodu průsečíku p pZ . Navíc, jsou tu algebraické
vzorce, které mohou být jednoduše derivovany s této geometrické procedury a můžou být aplikovány nad jakémkoli poli K. Totíž, pokud má rovnici (21), pak ; " " Z Z %,
!; "% ;
(22)
kde r
s_ : sa
t_ : ta
, pokud p H pZ ;
;ta_ vw: sa
Zsa v ta v]
, pokud p pZ .
x
(23)
Zejména, pokud je dano rovnici (20), to obsahuje % ( 0 v (22) – (23), a tým pádem, vzorce začínají vypadát jednodušeji.
Pomocí těchto vzorců lze vypočítat násobek mP na daném bodě P ve stejný úsek čásu jako to trvá exponenciaci - , pomocí analogické procedury, tzn. Prostřednictvím O(log m) zdvojení a doplňků,
například 11p p 2p 22p . Alternativně se dá použít rekurzivní vzorce, které představují
souřádnice 2*p a 2* 1p pokud jde o ty* p.
Necht’ O 5J, N= je konečným polem, pak body tvoří konečnou Abelovou grupu. Do
jisté míry se této skupina je podobná multiplikativní skupině 5J ∗ pole K. Například Hasse
dokazal, že řád skupiny | | se rovná 1 " , kde 2√, a má stejný asymptotický
rozměr jako |5J ∗| " 1. Vlastně, lze získat 5J ∗ z výše uvedené konstrukci pravidly
sčítaní na , pokud necháme „degenerovat“ necháním kubického kořene na pravé straně, 34
získáme dvojitý kořen; pak, pokud dva zešikmení jednotného čísla jsou v 5J, z toho vychází
že je to skupina nejednotných čísel (například x-souřádnice nemají dvojitý kořen) tvoří skupinu izomorfickou k 5J ∗.
Ale na rozdíl od 5J ∗, která je cyklickou skupinou, Abelová grupa pro O 5J take může
být bud’ cyklická nebo je součínem dvou cyklických skupin. V práxi pro “náhodnou” eliptickou křivku táto skupina je obvyklé také cyklická, anebo může být napsána jako součín s jedním cyklickým faktorem, který je menší než ostatní, například je „skoro“ cyklická. Vrátíme k této otázce po uvedení příkladu.
4.1.2. Vnořený otevřený text
Necht’ je eliptická křivka definovanána dO 5J, kde N= je velká. Předpokládáme
že máme metodu vnoření otevřených textů v E, což je lehce implementovat a dekodovat. Příklady
podobných metod: (1) Necht’ p je libovolné (např.2) a W 2W′je sudé. Předpokládáme, že naše otevřené texty jsou celá čísla m, 0 * N= , ve tváru * * * N ⋯ *= : N= : , 0 * N; a
necht’ , … , = : je vhodný vektorový prostor bázi se 5JN= nad 5JN. Nastavíme
* * * ⋯ *= : = : , a necht’ !* ∈ 5JN= je jedno ze dvou
řešení kvadratické rovnice (1) nebo (2) definující body na E. Dáme p- *, !* ∈ .
Takové řešení !* musí existovat, ale nejefektivňejší algoritmy pro řešení kvadratických
rovnic nad konečnými poli jsou pravděpodobnostní (za výjimkou je metoda R.Schoofa pro nalezení kvadratických kořenů modulo p za použitím eliptických křivek).
(2) Necht’ W 1, N ≡ 3 mod4,a E je dána Eq. (1). Předpokladejme, že naše otevřené texty jsou celá čísla m, 0 *
L
:
. Zkusíme přídat tří čísla k m, dokud nedosahneme x,
1000* 1000* 1 N, takové, že C ; je kvadratem v5JN. Pak
def p- , C Lv/ je bodem na E; protože tady je nepatrná pravděpodobnost, že C bude nekvadratická pro všechny 1000* 1000* 1. 35
(3) Necht’ N 2, W ≡ 4 mod 6, a necht’ , … , =:
prostoruGF2= nad GF2, a necht’ E je představená rovnicí:
je vhodný bazis vektorového
: ! Z ! ; .
(24)
Předpokladejme, že otevřené texty jsou v rozsahu * 2=: , * * * 2 ⋯
*=: 2=: , * ∈ .0, 12, a pokusíme se nastavit
! * ⋯ *=: =: *=: =: ⋯ *=: =: ∈ GF2= s proměnlivé
*=: , … , =: ∈ .0, 12; pokud ! Z ! je kostkou v GF2= , pak bod p- , ! je na E pro ! Z !Z
X vZ/
. To nám dává pravděpodobnostní vnoření skupiny {m} otevřených textu na
E.
4.1.3. Kryptosystémy
Kryptosystémy na bázi 5J mohou být přeloženy na systémy použivající skupinu E, kde E je
eliptická křivka definována nad 5J. Dále to bude představeno popisem dvou eliptických kryptosystémů pro předávání informací.
Analog eliptické křivky Massey-Omura systém. Necht’ N= je velká,at’ E je eliptickou křivkou definovanou nad 5J,a necht’ z " ||.q a E
jsou pevně stanovené a veřejné známé, jako je N. Takže máme veřejně známé vnoření * → p-
otevřených textů jako body E. Předpokládáme, že uživatel A přeje poslat uživateli B zprávu m.
Vybírá náhodné celé číslo c splňující 0 % z a největší společný dělitel%, z 1, předává
%p- . Dál, B vybírá náhodné celé číslo d se stejnými vlastnostmi, a předává (%p- k A. Poté A
předáva %´(%p- (p- zpátky k B, kde %′% ≡ 1(mod N). Nakonec B vypočítává ( (p- p- , kde ( ( ≡ 1 (mod N).
Analog eliptické křivky El-Gamal systém. Předpokládáme stejné nastavení jako v (1), mimo toho že ted’ není nutné vědet N. (Není to žádné
velké teoretická ůspora, protože R.Schoof vynalezl algoritmus pro výpočet N v |¡,d bitových
operací, ale může to být velkou praktickou výhodou se tomu vyhýbat).
36
Dále zapíšeme 5 ∈ jako pevný a veřejné známý bod. Příjemce B vybírá a náhodně a vydává a
jako tajné. Pro předání zprávy m k B, uživatel A vybírá náhodné celé číslo k a posílá dvojici bodů
)5, p- )5. Pro přečtení zprávy, B násobí první bod ve dvojicí jeho tajným a, zatím odčítá výsledek od druhého bodu dvojici.
Poznámka. Jak ElGamalove, tak Massey a Omurove konstrukce jsou v podstatě příklady originálního Diffieho-Hellmanova protokola výměny klíčů. V kontextu eliptické křivky, posledně uvedené zahrnuje v každém uživateli A vybírajícím celé číslo c a tvořicím cP veřejným; dva
uživatele A a B mají klíč (%p %(p, kde d je tajným klíčem B. Massey-Omura funguje stejným způsobem, mimo toho že uživatel B čeká dokud A zveřejní %p a dělá (%p (radějí než (p) známýmA. El-Gamalův systém používá stejnou konstrukci s dodatečným prvkem, který mapa p → p Q
používá jako „zobecněnou Vernamovou šifru“.
Rozluštění eliptických kryptosystému, bud’ Massey-Omura anebo El-Gamal, vyžádá řešení analoga na bázi eliptických křivek problému diskrétního logaritmu: Problém Diskrétního Logaritmu na bázi Eliptických Křivek. Máme eliptickou křivku E definovanou nad GF(q) a dva body p, Q ∈ , najdeme celé číslo x takové jako Q p, pokud podobné x existuje.
Je pravděpodobné, že tento problém je víc nepoddajný než klasický problém diskrétního logaritmu. Nejpevnější známé techniky ve druhém případě nevypadájí přílsš využitelné pro analog eliptické křivky. Zejména, eliptické křivky mohou být nejvíc vhodné pro použití nad 5J2= , protože, jak
vysvětluje Odlyzko, diskrétní logaritmy v 5J2= jsou relativně lehce vypočitatelné vybráné n je
docela velké. Je pravděpodobně, že analogické systémy použivající eliptické křivky nad 5J2=
budou bezpečné významně menšími hodnotami n.
Nicméně, aby zabránit lehkému řešení problému diskrétního logaritmu za použitím technik, které se
aplikuji do jakékoliv konečné Abelovy grupy (která zabírá přiblížně √ operací, kde r je největší
prvočíslo dělící pořádí skupiny), je důležité vybrat E a q takové, že z || je dělitelné velkým
prvočíslem (bude níže uvedeno v příkladech). Všimnete si, že je to přesný opak těžšího Lenstrová faktoringového algoritmu, kde je třeba hledat eliptické křivky s N„hladkým“ číslem. 37
4.1.4. Příklady
V ElGamalovem eliptickém kryptosystému, když máme N= , vybíráme E a G náhodně.
Například, necht’ d! ! Z jestli N ¢ 2 a d! ! Z ! jestli N 2. Pak vybereme náhodné
prvky , !, ∈ 5J2= ,a nastavíme d! " ; " . Pak 5 , ! je bodem na eliptické křivce s rovnicí (1) nebo (2) (s % 0, ( 1). (Diskriminant rovnice má být nenulový, ale to je
prakticky jisté, jestli a a b jsou náhodné prvky velkého konečného pole).
Dříve než začnéme používat vybráné E a G, je nutné zkontrolovat, že řád G v E není hladké celé číslo; pokud produkt poměrně hladkých prvočísel bere bod G k identitě (bod nekonečnosti), musí být proveden další náhodný výběr. Necht’ E je dána rovnicí ! Z ! ; nad 5J2= , W ≡ 4 mod 6, jak je výše uvedeno. Jak ukázáno výše, máme jednoduché, pravděpodobnostní vnoření * → p- otevřených textů v E. Této E je také vhodné pro jiné přičiny.
Vzorce pro zdvojnásobení bodu jsou zvláště jednoduché: 2p , ! 1 pro p , !,
(25)
jak to vidíme, zaměnou Z , % 0, ( 1 v 22 23 a použitím rovnici (24), křivka může být zjednodušena do !; "1 " ! Z " .
Navíc, máme jednoduchou formulu pro N pro tento případ: Z
z || 2= 1 " 2"2_ ¥"2_ " 1¦ . X
X
(26)
Tak, máme cílem zajistit, že N je dělitelná větším prvočíslem, a můžeme proto například vybrat n takové, že
=
≡ 1 mod 3 dává Mersennové číslo s velkým faktorem, jako Mersennové prvočíslo
(například n = 508).
Táto křivka může být použita pro Massey-Omura systém, nebo, poté co vybereme náhodně bod G (za použitím popsané výše techniky pro vnoření textu v E), pro ElGamalův systém. (22) Necht’ E je dána rovnicí: !Z ! ; "
(27) 38
nad GF(p), p je velké prvočíslo, a dáme 5 0, 0. Pokud známe, že rovníce E je rovnicí nad polem
racionalních čísel, pak 5 0, 0 je bodem nekonečného řádu, který násobí vše racionální body E.
Neznamená to, že po redukci modulo p, G generuje vše body E nad GF(p); ve skutečnosti, poslední skupina nemusí být nutné cyklická. Avšak, je pravděpodobně, že G skoro vždycky generuje větší
část §¨L . Nyní probereme to detailnější.
4.1.5. Primitivní body V eliptických kryptosystémech výše uvedeného typu, obvykle to nefunguje s celou skupinou E, ale
spíše s cyklickými podgrupy: skupiny 〈p- 〉v Massey-Omura systému a skupinu 〈G〉v ElGamalovem systému. Pro skupiny 〈p- 〉a 〈G〉 je žádoucí, aby byli velké, například jejich index E musí být malý.
Přesněji, řád těchto cyklických podgrup musí být nehladkým, to znamená, musí být dělitelným větším číslem, abychom zabráníli jednoduchému řešení problemu diskrétního logaritmu v nich. V našich příkladech, G je také “náhodný” bod vybráný poté jak jsme specifikovaly q (v výše uvedených příkladech (20)-(21)), anebo globální bod (příklad (22)), jako například pevný bod nekonečného řádu eliptické křivky « definované nad racionalními čísly, kde bude dále zredukován mod p, poté co jsme vybereme velké p a rozhodneme dále pracovat s §¨L mod N. V obou
případech je vhodné položit otázku: Jaká je pravděpodobnost (p se mění s pevným G, nebo p a
“náhodné‘ G oba mění) že G generuje E mod p? Nebo, pokud nemůžeme spolehat na to, že to se děje dost často, můžeme se zeptat: Jaká je pravděpodobnost pokud | mod N | je dělitelný velkým
prvočíslem l, že |〈G mod p〉| bude také dělitelná I?
První otázkou je analog eliptické křivky primitivného kořenového problému pro GF(p) jak to bylo
považováno E.Artinem. Necht’ H 0, ¬1 je pevné celé číslo, které nemá tvár ¬ = pro jakekoliv
W ¢ 1. Artin prvním pozoroval, pokud použijeme Chebotarevu větu hustoty na to abychom to ukázali, že pro jakélkoliv prvočíslo l, pravděpodobnost, že l dělé index a v GF(p)*, například ¡|N " 1a L:/ ≡ 1 mod ¡, se rovná
. Artin předpokládal, že této události jsou nezávislé
:
pro různé l, pak v tomto případě máme pravděpodobnost toho, že a je generátorem, například žádné prvočíslo l dělí index a v GF(p)*, a se rovná: ∏¯°±²číµ¶· 1 "
:
39
0.3729 ….
(28)
Později býlo pozorovano, že události nejsou nutné nezávisle, a pro určité a musí být modifikovano několik faktorů v (28). Například, číslo, které má největší pravděpodobnost toho, že je generátorem "3, kde táto pravděpodobnost je získána vymázaním ¡ 3 podmínky v (28). Zejména, protože -3 je kvadratické, a tudíž není generátorem pokaždé když N ≡ mod 3, z toho vyplývá, že -3 je generátorem GF(p)* pro 89,7% každého N ≡ mod 3. Upravená Artinova domněnka byla
představená C.Hooleyem , a může být provedena pokud je předpokládana zobecněná Riemannová hypoteza(GRH), V případě eliptické křivky, analog Artinové doměnky býl představen Langem a Trotterem. Necht’ E
je pevná eliptická křivka definována nad Z s diskriminantou ∆, a necht’ N , NZ , … je rostoucím pořadí prvočísel, za výjimkou prvočísel dělicích ∆. Necht’G je primitivním bodem nekonečného řádu na E,
který není ve tváru W5´ pro jakékoliv W ¢ 1. Říká se, že G je primitivní pro p pouze v případě, že G mod p generuje E mod p. Necht’CW je poměrem prvních n prvočísel, pro které G je primitivní: CW C,§ W |.¹ W |5 je primitivní proN 2|.
=
(29)
Pak Lang a Trotter se dohadli, že CW blíží se nenulovému limitu, a popsali jak tento limit určit. V případě třech eliptických křivek:
: ! Z ! ; " , F: ! Z ! ; Z , ¼: ! Z ! ! ; " Z
(30)
lim= → ¾ CW ∏1 "
(31)
s bodem 5 0, 0, domýšleli si následující hodnotu: ¿ ::
_ :_ :
À 0,440.
Táto hypotéza předpokládá, že události l|/ mod N: 〈5 mod N〉0| jsou nezávisle pro různé l. V případě eliptických křivek s komplexním násobením, nachylnejší verze Lang-Trotterove hypotézy (kde zanedbávají prvočísla p, které nerozdělují v poli komplexního násobení), bylo dokázáno Gupta a Murty za předpokládem GRH. Serre, také za předpokládem GRH, dokázal analogický výsledek o otázce cyklického opakování E mod p: Podíl p, pro který E mod p je cyklickou skupinou blíží nenulové konstantě. Lang a Trotter otestováli jejich hypotézu v případech (30) (a 5 0,0) pro prvních 200 prvočísel. Výsledky nebyli tak blizko k odhadované hodnotě 88 prvočísel pro které 5 je primitivní, takže poté 40
byly zahozený prvních 20
, a spočitána hodnota zbylých 180. V intervalu
,
dohoda s odhadovánou proporci byla docela dobrá. Poté Trotter rozšířil této výpočty do prvních 2000 prvočísel, čim získ získal al přesvědčivější statistické ev evidence idence podporující domněnku o eliptických křivkách ((30).
4.1.6. Nehladké cyklické podgrupy
Druhá otázka o indexu 〈
〉 v
je je náchylnější: Pokud jsme zajištili zajištili, že
nehladké a víme víme, že je dělitelné větším prvočíslem l,, to jaká je pravděpodobnost, pravděpodobnost že |〈 také dělitelné l?? Pokud
o pravděpodobno pravděpodobnosti, že l dělí index 〈
podmiňovací pravděpodobnost pravděpodobnost, že
je
〉| je
, což není pravděpodobné pro velké l,, je to ekvivalentně otázce 〉 v v
. Jinak řečeno, pro pevné E, G a l,, jaká je vzhledem k tomu, že
? V
návaznosti na tvrzení ((28)) a za použitím Chebotarevy věty hustoty (density theorem), a výsledku Serre a Bashmakov pro křivky bez komplexního násobení, máme následující odpověd’. Věta 4.1.1:Necht’ 4.1.1:Necht’G je pevný bod nekonečného řádu na eliptické křivce E diskriminanty ∆ která kter je definována nad Z a nemá komplexní násobení. Pak, pro vše ale koněčně mnoho prvočísel l,
(32) V závěru, extra
pojem vzníká z možností, možností že
podstata těchto dohadů, i kdýž
vzrůstá s p,, index
. Nakonec, bereme na vědomí vědomí, že o průměru ne.
Tedy, pro extremálně velké p,, podskupina generována G se očekává jako docela ““slu slušná”” (například nehladká) jako E samo o sobě.
41
5 Algoritmy veřejného klíče 5.1 Úvod Na nápad řešit kryptosystém pomocí veřejného klíče přišli první Whitfield Diffie s Martinem Hellmanem a nezávisle na nich i Ralph Merkle. Přínosem pro kryptografii byla představa, že klíče mohou existovat v párech – jeden šifrovací klíč a jeden dešifrovací klíč – a že není možné jeden klíč odvodit z druhého. Diffie s Hellmanem poprvé zveřejnili svoji myšlenku na Národní počitačové konferenci v roce 1977. O několik měsiců později ji publikovali článkem “Nové směry v kryptografii”. Vzhledem ke zdlouhavosti publikačního procesu se prvý Merklův příspevek k této problematice objevil až v roce 1978. Od roku 1976 bylo navrženo velké množství kryptografických algoritmů s veřejným klíčem. Mnohé z nich nejsou bezpečné. Z těch, které lze ještě považovat za bezpečné, jsou ale mnohé nepraktické. Bud´mají příliš dlouhý klíč nebo zašifrovaný text je mnohem delší než text otevřený. Jen malo algoritmů splňuje podmínku bezpečnosti a praktičnosti. Tyto algoritmy jsou většinou založeny na některém z obtížných problémů popsaných v kapitole „Matematické základy kryptologie“. Z těch bezpečných i praktických algoritmů veřejného klíče se některé hodí jen pro distribuci klíčů. Jiné jsou vhodné pro šifrování (a po rozšíření i pro distribuci klíčů). Další zase jen pro digitální podpis. Jen tři algoritmy se dobře osvědčily pro šifrování a zároveň i pro digitální podpis: RSA, El Gamalův a Rabinův. Všechny tyto algoritmy jsou ale pomalé. Šifrují a dešifrují data mnohem pomaleji než algoritmy symetrické; pro šifrování velkých objemů dat se z těchto důvodů zpravidla nehodí. Hybridní kryptosystémy věci urychlují: Pro zašifrování zprávy se použije symetrický algoritmus s náhodným relačním klíčem a pro zašifrování relačního klíče algoritmus veřejného klíče (nesymetrický algoritmus).
5.2 Bezpečnost algoritmu veřejného klíče 42
Kryptoanalytik si může pro zašifrování zvolit jakoukoliv zprávu, protože má přístup k veřejnému
klíči. To znamená, že kryptoanalytik, který má k dispozici ¼ p může odhadovat hodnotu P a
výsledky svých odhadů jednoduše ověřovat. Tento problém je třeba brát vážně tehdy, když počet možných otevřených textů je tak malý, že umožňuje luštění metodou totálních zkoušek. Nicméně dá se překonat tak, že se zprávy vyplní posloupností náhodných bitů. Toto opatření zaručí, že šifrováním identických zpráv získáme odlišné šifrové texty. To je zvlášt´důležité v případě, kdy algoritmus veřejného klíče používáme pro šifrování relačního klíče. Subjekt A může vygenerovat databázi všech možných relačních klíču a zašifrovát ji veřejným klíčem subjektu B. To bude samozřejmě vyžadovat hodně času a klást velké nároky na pamět´. Ale při 40-bitovém relačním klíči nebo 56-bitovém DES klíči k tomu celkově bude zapotřebí mnohem méně času a paměti, než k luštění veřejného klíče subjektu B. Jakmile subjekt A jednou již databázi vygeneroval, má k dispozici klíč subjektu B a bude moci číst podle libosti jeho poštu. Algoritmy veřejného klíče jsou navrženy tak, aby byly odolné proti luštění pomocí vybraných zašifrovaných textů. V systémech, kde digitální podpisová operace je inverzí šifrovací operace, nelze tomuto způsobu lůštění
zabránit,
pokud
pro
šifrování
a
podpis
nejsou
použité
odlišné
klíče.
Z toho tedy vyplývá, že musíme dávat pozor po celý systém a nejen na jeho jednotlivé části. Dobré protokoly veřejného klíče se nahrhují tak, aby různé zúčastněné subjekty nemohli libovolně dešifrovat zprávy generované jinými subjekty. Jako dobrý příklad by mohl sloužit takzvaný identifikační protokol.
5.3 Zavazadlový algoritmus Prvým algoritmem pro šifrování veřejným klíčem byl zavazadlový algoritmus vyvinutý Ralphem Merklem a Martinem Hellmanem. Tento algoritmus mohl být používan jenom pro šifrování, i kdýž Adi Shamir tento systém pozdějí upravil pro digitální podpis. Bezpečnost zavazadlového algoritmu zajišťuje NP-složitost zavazadlového problému. I když byl tento algoritmus později označen z bezpečnostního hlediska za nevyhovující, vypláti se věnovat mu pozornost, nebot´umožní demonstrovat způsob, jakým lze tuto složitost využít v kryptografii veřejného klíče. Podstata zavazadlového problému je jednoduchá. Máme množství předmětu, každý o určité váze, a našim úkolem je vybrat z tohoto množství takový soubor, aby zavazádlo po naplňení mělo 43
předepsanou váhu. Ptáme se, zda tato úloha má řešení. Formálně vyjadřeno: Je dána množina hodnot { , {Z , … , {= a součet S a má se určit množina koeficientů taková, aby platilo { Z {Z … = {=
(33)
Koeficienty mohou mít bud´hodnotu nulovou nebo jedničkovou. Jednička bude znamenat, že
předmět
nebo
položka
bude
součástí
zavazadla,
zatímco
nula
opak.
Váhy položek mohou být například 1, 5, 6, 11, 14 a 20. Zavazadlo o váze 22 bychom mohli zaplnit položkami s váhami 5, 6, a 11. Zavazadlo o váze 24 by se nam s zadanými položkami naplnit nepodařilo. Čas potřebný pro řešení tohoto problému v obecném případě roste exponenciálně s počtem položek výchozího souboru. Merkl-Hellmanův nápad spočívá ve využití zavazadlového algoritmu k zakódování zprávy do řešení řady zavazadlových problémů. Obr.1.c. Příklad šifrování pomocí zavazadlového algoritmu Otevřený text: 1 1 1 0 0 Zavazadlo
1
: 1 5 6 11 14 20
Šifrový text : 1+5+6+20=32
010 1 1
0
000 0 0 0
011 0 0 0
1 5 6 11 14 20
1 5 6 11 14 20
1 5 6 11 14 20
5+11+14=30
0=0
5+6=11
Zdroj: Přehled užité matematiky
Merkl-Hellmanův kryptografický algoritmus využívá toho, že v podstatě existují dva zavazadlové problémy, jeden řešitelný v lineárním čase a druhý v lineárním čase pravděpodobně neřešitelný. Lehké zavazadlo se dá přeměnit na těžké zavazadlo. Veřejný klíč je těžké zavazadlo, které lze snadno použít k šifrování zpráv, ale ne k jejich dešifrování. Soukromý klíč je lehké zavazadlo, umožňující snadné dešifrování zpráv. Subjekty, které neznají soukromý klíč, musí řešit problém těžkého zavazadla.
5.4 Superrostoucí zavazadlo Co znamená problém lehkého zavazadla? Jestliže množina vah bude představovat superrostoucí posloupnost, pak výsledný zavazadlový problém lze řešit jednoduše. Superrostoucí posloupnost je
44
posloupnost, jejíž každý prvek je větší než součet všech prvků předcházejících. Například posloupnost {1,3,6,13,27,52} je superrostoucí, zatímco posloupnost {1,3,4,9,15,25} nikoliv. Řešení problému superrostoucího zavazadla lze nalézt snadno. Vezme se celková váha a porovná se s největším číslem posloupnosti. Je-li celková váha menší než toto číslo, pak číslo neni součástí zavazadla. Jestliže celková váha bude větší nebo stejná jako toto číslo, pak číslo bude v zavazadle obsazeno. Snižme váhu zavazadla o tuto hodnotu a přejděme k dalšímu největšímu číslu posloupnosti. Postup opakujme až do konce. Jestliže celková váha zavazadla postupným ubíraním klesne na nulu, pak řešení existuje. V opačném případě problém nemá řešení. Jako příklad uvažujme celkovou váhu zavazadla 70 a posloupnost váh jednotlivých položek {2,3,6,13,27,52}.Váha nejtežší položky 52 je nižší než 70, takže 52 je částí zavazadla. Odečtením 52 od 70 dostaneme 18. Následující váha 27 je větší než 18, takže 27 není v zavazadle. Další váha 13 je menší než 18, a tudíž 13 je v zavazadle. Odečtením 13 od 18 dostaneme 5. Další váha 6 je větší než 5, takže 5 také není v zavazadle. Pokračováním tohoto postupu zjistíme, že 2 a 3 jsou části zavazadla, že celková váha klesne o 0 a tedy, že získané výsledky jsou řešením problému. Kdyby se jednalo o blok zprávy šifrovaný Merkle-Hellmanovým zavazadlem, pak by otevřený text získaný dešifrováním váhy 70 byl 110101. Problém normálních zavazadel, která nejsou superrostoucí, je obtížným problémem; pro jeho řešení není znám žádný rychlý algoritmus. Jediný známý způsob pro určení položek, patricích do zavazadla, spočívá v metodickém testování možných řešení tak dlouho, než se příjde na řešení správné. Doba trvání nejrychlejších algoritmů včetně rozličných algoritmů heuristických roste exponenciálně s počtem možných vah obsažených v zavazadle. Přidáním jedné položky do posloupnosti váh se doba hledání řešení prodlouží na dvojnásobek. Hledání řešení je v tomto případě mnohem těžší než u superrostoucího zavazadla, kde přídaním jedné váhy do posloupnosti přibude pří hledání spravného řešení pouze jedna operace navíc. Merkle-Hellmanův algoritmus je založen právě na této vlastnosti. Soukromý klíč je posloupnost vah pro superrostoucí zavazadlový problém. Veřejný klíč je posloupnost váh pro normální zavazadlový problém se stejným řešením. Merkle s Hellmanem odvodili postup pro transformaci superrostoucího zavazadlového problému na normální zavazadlový problém. Využili k tomu modulární aritmetiku.
45
5.5 Vytvoření veřejného klíče z klíče soukromého Činnost tohoto algoritmu se dá popsat bez pomoci teorie čísel následovně: Uvažujme jako příklad supperrostoucí zavazadlovou posloupnost {2,3,6,13,27,52}a vynásobme všechny její prvky číslem nmod m. Modulem musí být číslo větší než součet všech prvků této posloupnosti: třeba číslo 105. Násobitel nesmí mít žádné společné součinitele s modulem: například 31. Posloupnost normálního zavazadla, kterou tímto postupem získáme potom bude 2*31 mod 105 = 62 3*31 mod 105 = 93 6*31 mod 105 = 81 13*31 mod 105 = 88 27*31 mod 105 = 102 52*31 mod 105 = 37
Obsah normálního zavazadla je pak množina {62,93,81,88,102,37}. Superrostoucí zavazadlová posloupnost je soukromým klíčem, zatímco normální zavazadlová posloupnost veřejným klíčem.
5.6 Šifrování K zašifrování dvojkové zprávy je třeba zprávu nejprve rozdělit na stejný počet bloků, jako je počet položek zavazadlové posloupnosti. Potom se určí celkové váhy zavazadel odpovídajících jednotlivým blokům, příčemž celkovou váhu každého zavazadla tvoří položky přislušející jedničkovým bitům určitého bloku zprávy. Kdyby například zprávu představovala dvojková posloupnost 011000110101101110, by šifrování výše popsaného zavazadla probíhalo následovně: zpráva = 011000 110101 101110 011000 110101 101110
93 + 81 = 174 62 + 93 + 88 + 37 = 280 62 + 81 + 88 + 102 = 333
Šifrovým textem by potom byla čísla 174, 280, 333. 46
5.7 Dešifrování Opravněný příjemce této zprávy zná soukromý klíč: původní superrostoucí zavazadlo, stejně jako hodnoty n a m použité k transformaci zprávy na normální zavazadlo. Příjemce dešifruje zprávu tak, že nejprve určí W: pomocí WW: ≡ 1mod *. Potom vynásobí
všechny hodnoty šifrového textu výrazem W: mod * a výsledky rozloží na prvky posloupnosti “soukromého zavazadla”. Přiřazením jedniček těmto prvkům a nul prvkům chybejícím dostane hodnoty otevřeného textu. V našem příkladu mělo superrostoucí zavazadlo obsah {2,3,6,13,27,52}, m se rovnalo číslu 105 a n
číslu 31. Zašifrovanou zprávu představovaly čísla 174, 280, 333. V tomto případě se W: rovná číslu 61, takže čísla zašifrované zprávy musíme násobit výryzem 61 mod 105. 174 * 61 mod 105 = 9 = 3 + 6 280 * 61 mod 105 = 70 = 2 + 3 + 13 + 52 333 * 61 mod 105 = 48 = 2 + 6 + 13 + 27
011000 110101 101110
Získaný otevřený text je potom sled 011000 110101 101110.
5.8 Praktické realizace Řešení zavazadla s pouhými šesti prvky není obtížné ani v případě, že se nebude jednat o superrostoucí zavazadlo. Opravdová zavazadla by měla obsahovát alespoň 250 prvků. Hodnota každého prvku superrostoucího zavazadla by měla ležet v intervalu 200 až 400 bitů a hodnota modulu někde mezi 100 až 200 bity. Praktické realizace zavazadlového algoritmu využívají k získávání těchto hodnot generátory náhodných posloupnosti. Zavazadla takové velikosti se nedájí luštit metodou totálních zkoušek. Počítač schopný testovat milion možností každou sekundu by k prověření všech možných prvků zavazadla potřeboval více než 10> roků. Dokonce ani milion paralelně pracujících počítačů by tento problém nevyřešilo dříve než za 10 roků.
5.9 Bezpečnost zavazadlového algoritmu 47
Od doby, kdy se podařílo vyluštit původní Merkle-Hellmanův algoritmus bylo navrženo mnoho dalších zavazadlových systémů: násobné iterativní zavazadlové algoritmy, Graham-Shamirovy zavazadlové algoritmy a jiné. Všechny byly analyzovány a rozluštěny většinou pomocí stejných kryptoanalytických technik a odmítnuty. Na obdobných principech, jaké používá zavazadlový algoritmus, byly vytvořeny ještě další kryptosystémy, ale ty byly také rozluštěny. Chor-Rivestova varianta zavazadlového algoritmu je i navzdory specializovanému luštění stále bezpečná, ale množství požadovaných početních operací ji řadí daleko za dosud zmíněné algoritmy. Vzhledem k tomu, jak poměrně snadno byly všechny ostatní varianty rozluštěny, nebylo by moudré důvěřovat ani Chor-Rivestově variantě.
5.10 RSA Brzy po Merkl-Hellmanově zavazadlovém algoritmu se objevil skutečně bezpečný asymetrický kryptosystém, který se dá použít jak pro šifrování, tak pro digitální podpis. Ze všech algoritmů veřejného klíče navržených během řády let je RSA tím nejsrozumitelnějším a nejjednodušeji realizovatelným kryptosystémem. Algoritmus RSA pojmenovaný po svých tvůrcích Ron Rivestovi, Adi Shamirovi a Leonardu Adlemanovi dosud úspěšně odolává mnoholetým pokusům o luštění. I když kryptoanalýza neprokázala sílu ani slabost RSA systému, tak léta neúspěšných pokusů o jeho luštění zvýšují důvěruhodnost tohoto algoritmu. Bezpečnost algoritmu RSA je založena na obtížnosti faktorizace velkých čísel. Veřejny a soukromý klíč se odvozuje ze dvou velkých (100 až 200 místných nebo ještě větších prvočísel) K vygenerování dvou klíču je zapotřebí náhodně zvolit dvě velká prvočísla p a q. Z důvodu maximální bezpečnosti se p a q volí řádově stejně velká. Vypočte se jejich součin: W N
(34)
( ≡ 1*,(N " 1 " 1
(35)
Potom se náhodně zvolí šifrovací klíč e tak, aby čísla e a (p - 1)(q - 1) byla nesoudělná. Nakonec se pomocí rozšířeného Euclidova algorithmu vypočte dešifrovací klíč d tak, aby platilo
nebo vyjadřeno jinak
48
( : *,(N " 1 " 1
(36)
Poznamenejme, že d a n jsou také nesoudělná. Čísla e a n reprezentují veřejný klíč, zatímco číslo d tajný (soukromý) klíč. Prvočísla p a q nejsou jíž dále zapotřebí, mohou se odložit, ale nikdy prozradit. K zašifrování zprávy m je nejprve třeba rozdělit text na číselné bloky kratší než n (v případě dvojkových dat volíme nejvyšší mocninu čísla 2 menší než n). Budou-li tedy p a q stomístná
prvočísla, pak n bude dvěstěmístným číslem a každý blok zprávy * by měl být o něco kratší než
200 míst. Jestliže potřebujeme zašifrovat určitý počet bloků, tak pro zajištění podmínky *
jednotlivé bloky zprávy zaplnit zleva několika nulami. Zašifrovanou zprávu c budou tvořit bloky % přibližně stejné délky. Výraz pro šifrování má následující jednoduchý tvar % * Á mod W
(37)
* % ] mod W
(38)
K dešifrování zprávy stačí každý zašifrovaný blok % podrobit operaci
Postup shrnuje Tab.5.1.1.
Zprávu lze stejně snadno šifrovat klíčem d a dešifrovat klíčem e; volba je libovolná. Tab.1.4. Algoritmus RSA
Veřejný klíč: n ... součin dvou prvočísel, p a q (p a q musí zůstat tajné) e ... nemá s (p-1)(q-1) žadné společné součinitele Soukromý (tajný) klíč:
d ... : *,(N " 1 " 1
Šifrování:
% *Á mod W
Dešifrování:
* % ] mod W Zdroj: State of the Art in Applied Cryptography
49
Příklad Necht´p = 47 a q = 71, pak W N 3337. Šifrovací klíč e nesmí mít žadné společné součinitele s
N " 1 " 1 46 ∗ 70 3320.
Zvolme (náhodně) 79. V takovém případě ( 79: mod 3220 1019. Uveřejníme e a n a d podržíme v tajnosti. Čísla p a q odložíme. * 6882326879666683 je nejprve třeba tuto zprávu rozdělit na krátké bloky. V tomto případě vyhoví docela dobře třimístné bloky. Bloky * rozdělené zprávy m představuje tato šestice:
* 688
*Z 232 *; 687 * 996 *Â 668 *> 003 Prvý blok se zašifruje takto:
688Ã mod 3337 1570 c a ostatní bloky s podobným způsobem. Výsledná zašifrovaná zpráva
bude mít tvar
% 1570 2756 2091 2276 2423 158
Dešifrování zprávy se provede stejným umocněním pomocí dešifrovacího klíče 1019 takto 1570
mod 3337 688 m . 50
Zbývající část zprávy se získá obdobným postupem.
5.11 El Gamalův systém El Gamalův systém se dá použít jak pro digitálni podpis, jak pro šifrováni. Jeho bezpečnost spočívá v obtížností výpočtu diskrétních logaritmu v konečném tělese. K vygenerování páru klíčů je nejprve třeba zvolit prvočíslo p a dvě náhodná čísla g a x menší než p a potom spočítat ! d t mod N
(39)
Čísla y, g a p představují veřejný klíč. Čísla g a p může sdílet skupina uživatelů, ale číslo x je soukromý klíč.
5.12 El Gamalův podpis K podpisu zprávy M je třeba nejprve zvolit náhodné číslo k tak, aby k nemělo žádné společné součinitele s p – 1. Potom se vypočte d mod N
(40)
a pomocí rozšířeného Euclidova algoritmu vyřeší následující rovnice pro b: { ) mod N " 1.
(41)
Podpis představuje pár a a b. Náhodné číslo k musí zůstat utajeno. Ověření podpisu se provede prověřením platnosti vztahu ! w mod N Å mod N.
(42)
Každý El Gamalův podpis nebo šifrování vyžaduje novou hodnotu k, jejíž výběr musí být náhodný. Kdyby subjekt P někdy odhalil číslo k, které použil subjekt A, pak by také mohl zjistit i soukromý klíč x subjektu A. Kdyby P někdy získal dvě zprávy signované nebo šifrované pomocí stejného k, aniž by znal jeho hodnotu, mohl by odvalit x. El Gamalův podpis shrnuje Tab. 5.1.2. Zvolíme například p = 11 a g = 2 a soukromý klíč x = 8. Vypočítáme ! d t mod N 2Æ mod 11 3. Veřejný klíč představují čísla y = 3, g = 2 a p = 11. 51
Pro autentizaci M = 5 volíme nejprve náhodně číslo k = 9. Ověříme, že gcd(9,10) = 1 a vypočítáme d mod N 2 mod 11 6. Tab.1.5. El Gamalův podpis
Veřejný klíč: p ... prvočíslo (může být společné pro skupinu uživatelů) q < p … (může být společné pro skupinu uživatelů) ! t mod N
Soukromý klíč: x
a (podpis) = d mod N
b (podpis) takové, že M = (xa + xb) mod (p - 1) Verifikace:
Platnost se uzná tehdy, jestliže ! w mod N dÅ mod N. Zdroj: State of the Art in Applied Cryptography
K určení b použijeme rozšířený Euclidův algoritmus:
{ )mod N " 1 5 8 ∗ 6 9 ∗ bmod 10.
Řešením je b = 3 a podpisem pár: a = 6 a b = 3.
Platnost podpisu ověříme tak, že prověříme správnost vztahů
! w mod N dÅ mod N
3> 6; mod 11 2Â mod 11.
5.13 El Gamalovo šifrování El Gamalův systém může po úpravě sloužit i k šifrování. K zašifrování zprávy M je třeba nejprve zvolit náhodné číslo k tak, aby k nemělo žádné společné součinitele s (p - 1). Potom se vypočte
52
d mod N
(43)
! { mod N.
(44)
Pár a a b představuje zašifrovaný text. Poznamenejme, že zašifrovaný text je dvakrát tak dlouhý jako text otevřený. K dešifrování a a b spočítáme {
wÈ
mod N.
(45)
To všechno je plně funkční proto, že platí kongruence t ≡ d t mod N a / t ≡
sÉÅ nÈÉ
≡
d t {/ t ≡ {mod N (Tab 5.1.4.). V podstatě se jedná o shodu s Diffie-Hellmanovým systémem
pro výměnu klíčů jen s tím rozdílem, že y je částí klíče a operace šifrování zahrnuje násobení součinitelem ! .
Tab 1.6. El Gamalovo šifrování
Veřejný klíč: p q
prvočíslo (může být společné pro skupinu uživatelů) (může být společné pro skupinu uživatelů)
! d mod N t
Soukromý klíč: x
b (šifrový text) = ! { mod N
Dešifrování:
M (otevřený text) = b/ t modp
Zdroj: State of the Art in Applied Cryptography
53
6 Standartizace 6.1 IEEE P1363 IEEE P1363 je standartizační projekt pro kryptografii veřejného klíče od Institute of Electrical and Electronics Engineers (IEEE). Obsahuje specifikace pro: •
Traditional
public-key
cryptography
(IEEE
Std
1363-2000
and
1363a-2004)
pairings
(P1363.3)
Tradiční kryptografie veřejného klíče •
Lattice-based public-key cryptography (IEEE Std 1363.1-2008)
Mřížková kryptografie •
Password-based public-key cryptography (IEEE Std 1363.2-2008)
Kryptografie na bázi hesel •
Identity-based
public-key
cryptography
using
Kryptografie na základě totožnosti za použitím dvojic Předsedou pracovní skupiny z října 2008 je William Whyte z NTRU Cryptosystems, Inc, který slouží od srpna 2001. Bývalí předsedové jsou Ari Singer, také z NTRU (1999-2001), a Burt Kaliski z RSA Security (1994-1999).
6.1.1 Tradiční kryptografie veřejného klíče (IEEE Std 1363-2000 and 1363a2004) Tato specifikace zahrnuje klíčovou dohodu, podpis a šifrovací schémata s využitím několika matematických přístupů: faktorizace celého čísla, diskrétního logaritmu a diskretního logaritmu eliptických křivek.
6.1.2 Schémata klíčové dohody
54
•
DL/ECKAS-DH1 and DL/ECKAS-DH2 (Discrete Logarithm/Elliptic Curve Key Agreement
Scheme, Diffie–Hellman version): Obsahuje jak tradiční Diffie–Hellman tak Diffie–Hellman eliptické křivky. •
DL/ECKAS-MQV (Diskretní logaritmus/Schemata klíčové dohody eliptické křivky, verze
Menezes–Qu–Vanstone)
6.1.3 Podpisová schémata •
DL/ECSSA Diskretní Logaritmus/Podpisová Schémata Eliptické Křivky s Přílohou):
Obsahuje 4 hlavní varianty: DSA, ECDSA, Nyberg-Rueppel, a Elliptic Curve Nyberg-Rueppel. •
IFSSA (Schéma Faktorizace Celého Čísla s Přílohou): Obsahuje dvě varianty RSA, Rabin-
Williams, a ESIGN, s několika způsoby kódování zpráv.. "RSA1 s EMSA3" je v podstatě PKCS#1 v1.5 RSA podpis; "RSA1 s EMSA4 kodováním" je v podstatě
RSA-PSS; "RSA1 s EMSA2
kodováním " je v podstatě ANSI X9.31 RSA podpis. •
DL/ECSSR (Diskretní Logaritmus/Podpisová Schémata Eliptické Křivky s Zotávenim)
•
DL/ECSSR-PV (Diskretní Logaritmus/Podpisová Schémata Eliptické Křivky s Zotávenim,
verze Pintsov-Vanstone) •
IFSSR (Schéma Faktorizace Celého Čísla s Zotávenim)
6.1.4 Schémy kodování •
IFES (Faktorizace Celého Čísla Šifrovací Schéma): v podstatě RSA kodováni s Optimální
Asymetrické šifrování (OAEP). •
DL/ECIES ((Diskretní Logaritmus/Integrovaná Šifrovací Schema Eliptické Křivky): v
podstatě "DHAES" varianta ElGamalovešifry. •
IFES-EPOC (Šifrovací Schema Faktorizaci Celého Čísla, EPOC verze)
6.1.5 Mřížkova Kryptografie veřejného klíče (IEEE Std 1363.1-2008) 55
•
NTRU šifrovací schéma
6.1.6 Kryptografie veřejného klíče na bázi hesel (IEEE Std 1363.2-2008) Tento dokument obsahuje řádu schémat klíčových dohod na bázi autentifikaci heslem, a schému zachrány klíče na bázi heslové autentifikace. •
BPKAS-PAK (Vyvážená Schéma Dohody Klíče na bázi Heslové Autentifikace, verze PAK)
•
BPKAS-PPK (verze PPK)
•
BPKAS-SPEKE (verze SPEKE)
•
APKAS-AMP (Rozšířená Heslem Autentifikována Schéma Dohody Klíče, verze AMP)
•
APKAS-BSPEKE2 (verze BSPEKE2)
•
APKAS-PAKZ (verze PAKZ)
•
APKAS-SRP3 a SRP6 (verzeZabezpečené Vzdálené Heslo (SRP) 3 a 6)
•
APKAS-SRP5 (verzeZabezpečené Vzdálené Heslo (SRP) 5)
•
APKAS-WSPEKE (verze WSPEKE)
•
PKRS-1 (Schéma Zachrány Klíče na Bázi Heslové Autentifikace, verze 1).
6.2 Aktualizované standardy pro eliptické křivky 6.2.1 Abstrakt Dáváme kratký přehled testů bezpečnosti eliptických křivek, který musí být vnořen do standardu pro kryptografii eliptických křivek. Zejména, aktuální validace parametrů spojená s MOV condition, které se objevuje v nejnovějším návrhu IEEE P1363 standardu [3, Sekce A.12.1, Sekce A.16.8], musí být nahrazena očistěným podpolem MOV condition. Podobně by se to mělo přizpůsobit podle the Standarts for Efficient Cryptography Group’s document SEC 1 [4].
56
6.2.2 Úvod Bezpečnost eliptických kryptosystému záleží na složitosti vypočitání problému diskretního logaritmu (DLP) na eliptické křivce. Existují standartní specifikace, které má eliptická křivka splňovat, aby byla považována za bezpečnou. Mluvíme o konkretním testu, který je znám jako MOV condition, kdýž ověřujeme parametry eliptických křivek nad binarními poli. Na základě IEEE P1363 (Standard Specifications for Public Key Cryptography) MOV condition “zajišťuje, že eliptické křivky nejsou náchylné ke snížení útoku Menezes, Okamoto a Vandstone”. MOV útok využívá párování k přepravě DLP z křivky kde to může být výpočetně těžké vyřešít, k koněčnému poli kde existují mnohem efektivnější metody pro řešení diskretního logaritmu. Zajišťujeme podmínky na velikosti koněčného pole, obsahujicího vložené MOV nezbýtné pro DLP na tomto polí, se srovnatelnou obtížnosti algoritmu eliptické křivky nad oblastí této definici. Hlavní myšlenkou je, že když N- pro prvočíslo p a kladné celé číslo m, pak minimálné vnořené pole je rozšířenímÊL ,
není nutné ÊS , a tudíž i DLP může být vloženo v pole výrazně menšího rozměru než předešlé
uvedené v standartech.
6.2.3 Navrhované znění Přímo navázujeme [3, Section A.12.1] s několika navrženými opravami zdůrazněnými tučným písmem. Dříve než bude představen algoritmus pro kontrolu subfield-adjusted (očistěne podpolim) MOV condition, je nutné vybrát práh MOV. Je to kládne celé číslo B, stejne jako pří použití diskrétniho logaritmu nad 5J Ë ma být
povážováne za aspoň stejné složité jako použití eliptického diskretního logaritmu nad GF(q). IEEE P1363 nabízí vhodnou formulu a tabulku pro určení vhodného celého čísla B. Dále bude představena následujíci korekce: Jakmile bude vybráno vhodné B, následující algoritmus kontroluje subfield-adjusted MOV condition pro výběr rozměru pole Ì ÍÎ a základní bod řádu r je ověřením toho že ÍÏ není shodný s 1 modulo r pro každé 9 ÎÐ.
Vstup: MOV práh B, primární výkon q, a prvočíslo r. 57
Výstup: zpráva “True” jestli subfield-adjusted MOV condition je splňena pro eliptickou křivku nad 5J s základním bodem řádu r ; zpráva “False” v opačném případě. Aby vyhnout nežadujicímu
různočtení, další postup se dovolím celkem přívest v angličtině: Determine the prime p dividing q Určit prvočislo p dělěnim q. Set t ← 1.
For i from 1 toÐÑn Òdo
(a) Set t ← tp mod r.
(b) If t = 1 then output “False” and stop. Output “True”.
Jestli výstup výše uvedeného algoritmu je “false”, křivka musí být vyloučena, protože je náchylná k útoku MOV reduction. Je rekomendovano také posoudit o vhodnosti vnesení korekcí do jiných standardů mimo IEEE P1363 obsahujích subfield-adjusted MOV condition. Dále budou navržené korekce pro SEC 1 [4, Section 3.1.2.1 odrážky pod 3]. b ≠ 0 in ÊZ^ .
#E(ÊZ^ ) ≠ 2- .
Ð ≢1 (mod n) for any 1 ≤ B < 20m. h ≤ 4.
Navržené korekce pro [4, Section 3.1.2.2.1, Actions] jsou následující: 9. Zkontrolujte, že Ð ≢1 (mod n) pro každé1 ≤ B < 20m, a to že WG H 2- . Komentář v Příloze B.1. [4. str.60 řádek -8] musí být pozměnen takto: Této útoky efektivně redukuji ECDLP na křivkách k tradičnímu problému diskretního logaritmu v malé míře rozšíření ÊÍ .
6.2.4 Indikátor zabezpečení 58
Necht´a je kladné celé číslo a r je prvočíslo, r
a. Nejmenšímu kladnému celému číslo x jako
t ≡ 1 modulo r se říká řád (order)odmodulo r, a bude označeno jako ord .
Necht´E je eliptická křivka definována nad konečným polem ÊS , kde N- . Jesti r dělí řád ÊS , to dvojice můžou vložít podskupinu ÊS řádu r do konečného pole ÊSÓÔÕ[Ö/^ . Tomu se říká
racionální exponent q od indikátora zabezpečení k’. )
,( N *
Chceme, aby diskrétní logaritmus v minimálním vložení pole ÊSÉ byl přibližně stejné obtížný jako diskrétní logaritmus eliptické křivky nad ÊS .
Například, pokud máme (pod)skupinu řádu r, a r je 160-bitové prvočíslo, to bude vypadát takto: Je to ekvivalentní vyžadující N²°×[ L ¢ 2
¢ 2
Z
.
59
Z
7 Kryptosystémy založené na eliptických křivkách Eliptické křivky jsou zajímavé proto, že představují cestu ke konstrukci „prvků“ a „kombinačních pravidel“ pro vytváření grup. Tyto grupy disponují dobře známými vlastnostmi pro tvorbu kryptografických algoritmů, ale ne dost určitých vlastností pro usnadnění kryptoanalýzy. Neexistuje například žádná rozumná představa „vyrovnávání“ (smooth) pomocí eliptických křivek. To znamená, že neexistuje žádná množina malých elementů, která by se s velkou nadějí umožnila jednoduchým algoritmem vygenerovat náhodný prvek. Takže algoritmy pro výpočet indexu diskrétního logaritmu nebudou realizovatelné. Eliptické křivky nad konečným tělesem 5J2= jsou zvlášt’ zajímavé. Aritmetické procesy pro tělesa tohoto typu se snadno konstruují a jejich implementace je poměrně jednoduchá pro n v rozsahu 130 až 200. S klíči malých rozměrů jsou schopné vytvářet rychlejší kryptosystémy veřejného klíče. Mnoho algoritmů veřejného klíče, jako Diffie-Hellmanův, ElGamalův a Schorrův se dá realizovat eliptickými křivkami nad konečnými tělesy.
7.1 LUC systém Některé kryptografové vývinuli zobecňený RSA systém, který místo umocňování používá různé permutace polynomů. Kravitz-Reedova varianta, která využívá nerozložitelné dvojkové polynomy není bezpečná. Wilfried Můller a Wilfried Nöbauerpoužívají Dicksonovy polynomy. Navzdory všem předchozím znalostem skupina výzkumných pracovníků z Nového Zelandu přistoupila v roce 1993 k patentování tohoto systému a označila jej zkratkou LUC. Lucasovo n-té číslo Ø= p, 1 je definováno jako:
Ø= p, 1 pØ=: p, 1 " Ø=:Z N, 1
(46)
K vygenerování páru klíčů – veřejného klíče a soukromého klíče je v každém případě třeba nejprve zvolit dvě velká prvočísla p a q. Potom spočítat n jako součín p a q. Šifrovacím klíčem e je náhodné číslo, které nemá žádné společné součinitele s N " 1, " 1, N 1 a 1.
60
Možné klíče pro dešifrování jsou čtyři, ( : mod ¥lcmN 1, 1¦ ( : mod ¥lcmN 1, " 1¦ ( : mod ¥lcmN " 1, 1¦ ( : mod ¥lcmN " 1, " 1¦ kde zápis lcm vyjadřuje nejmenší společný násobek. Veřejný klíč čísla d a n; soukromý klíč pak čísla e a n. Prvočísla p a q se odloží. Zašifrování zprávy P(P musí být menší než n) se provede takto ¼ ØÁ p, 1mod W a dešifrování takto p Ø] p, 1mod W s použitím spravného d.
Příklad Lucasová funkce Každý uživatel vybírá soukromý klíč a “náhodné” velká prvočísla p a q, a zveřejňuje jejich produkt
W N. Dále, vybírá veřejný šifrovací klíč e, který je nesoudělný k N " 1, N 1, " 1a 1.
Pro odeslání zprávy M Bobu, Alice očekává Bobův veřejný klíč e, a za použitím Lucasové
posloupnosti {Ø }, ona vytváří šifrovány text ¼ ØÁ {, 1mod W. Protože Bob ví faktory p a q, on
je schopný vypočítat tajný dešifrovací klíč d na základě ( ≡ 1 mod ÙW, kde
ÙW
lcmN " ¥ ¦ , " ¥ ¦ a Û {Z " 4.∗ Tým pádem, Bob může zotavit se zprávu M vypočitáním L S Ú
Ú
Ø] ØÁ {, 1, 1 ≡ ØÁ] Ü²× Ý= {, 1 ≡ Ø {, 1 ≡ { mod W.
61
7.2 ECDH - Diffie-Hellman Eliptická Křivka ECDH je protokol klíčové dohody, který umožňuje obem stranám zřídit sdílený tajný klíč, který může být použít pro algoritmy soukromého klíče. Obe strany navzájem vyměňují určité veřejné informace. Použitím těchto veřejných dat a jejich vlastních soukromých dat této strany vypočítávají sdílený tajný klíč. Žádná třetí strana, která nemá přístup k soukromým detailům každého zařízení, ne bude schopná vypočítat sdílený tajný klíč z dostupné veřejné informaci. Přehled ECDH procesu je ukázán níže. Pro vygenerování sdíleného tajného klíče mezí A a B za použitím ECDH, obě strany mají dohodnout na doménových parametrech eliptické křivky. Oba konci mají klíčový pár sestávající ze soukromého klíče d (náhodně vybráné celé číslo menší než n a kde n je řádem křivky, doménový parametr eliptické křivky) a veřejného klíče | ( ∗ 5 (5 je generátorem, doménovým parametrem eliptické křivky). Necht' ((Þ , QÞ ) je soukromý klíč - veřejný klíč páru A, a (( , Q ) soukromý klíč - veřejný
klíč páru B.
1. Koněčné A vypočítává O , ! (Þ ∗ QË
2. Koněčné B vypočítává ß à , !à (Ë ∗ QÞ
3. Ježto (Þ QË (Þ (Ë 5 (Ë (Þ 5 (Ë QÞ . Z toho důvodu O ß a proto à
4. Odsud vychází že je sdíleným tajným klíčem.
Protože je praktické není možné najít tajný klíč (Þ nebo (Ë z veřejného klíče K nebo L, získat sdílený tajný klíč pro třetí stranu není možné.
7.3 ECDSA - Algoritmus Digitálního Podpisu Eliprické Křivky Podpisový algoritmus se používá pro autentizace zařízení nebo zprávy poslánou zařízením. Například, uvažujeme o dvou zařízeních A a B. Pro autentizaci zprávy odeslanou A, zařízení B podepisuje zprávu za použitím soukromého klíče. Zařízení A vysílá zprávu a podpis pro zařízení B. Tento podpis může být ověřen jenom za použitím veřejného klíče přislušného zařízení A. Protože zařízení B zná veřejný klíč A, lze to ověřit jestliže zpráva je opravdu poslána A, nebo není. ECDSA je variantou Algoritmu Digitálního Podpisu (DSA) který pracuje na skupinách eliptických křivek. Pro odeslání podepsané zprávy od A k B, obe strany mají dohodnout na doménových 62
parametrech eliptické křivky. Odesílatel "A" má klíčový pár složený ze soukromého klíče (Þ
(náhodné vybráné celá čísla menší než n, kde n je řádem křivky, domenovým parametrem eliptické křivky). Přehled procesu ECDSA je uveden níže.
7.3.1 Generování podpisů
Pro podepsání zprávy m odesílatelem A, za použitím veřejného klíče (Þ . 1. Vypočítáme e = HASH (m), kde HASH je kryptografická hašovací funkce, jako SHA-1.
2. Vybereme náhodné celé číslo k z [1, W " 1]
3. Vypočítáme 1 *,( W, kde 1, !1 ) ∗ 5. Když r = 0, vrátíme na krok 2. 4. Vypočítáme á ) : (Þ mod W. Když s = 0, vratíme na krok 2.
5. Podpisem je pár (r, s)
7.3.2 Ověření podpisu
Pro B, pro autentizaci podpisu A, B musí mít veřejný klíč QÞ .
1. Ověřte, že r a s jsou celá čísla v [1, W " 1]. Pokud nejsou, podpis není platný.
2. Vypočítáme e = HASH (m), kde HASH je stejná funkce, která byla použitá při generování podpisu.
3. Vypočítáme â á : mod W
4. Vypočítáme ã â mod W a ãZ â mod W
5. Vypočítáme 1, !1 ã 5 ãZ QÞ
6. Podpis je platný pokud 1 mod W, jinak je neplatný.
7.4 ECIES Integrovaná šifrovací schéma Integrována šifrovací schéma, anglicky Integrated Encryption Scheme (IES) je hybridní šifrovací schéma, která představuje semantické zabezpečení protí protíhrače, který je schopný užívat vybráný otevřený text a vybráné útoky šifrováného textu. Bezpečnost spočívá na Diffie-Hellmanovém problému. Dva ztělesnění IES jsou standartizovány: Integrována Šifrovací Sćhéma Diskrétního Logaritmu (DLIES)а Integrována šifrovací schéma Eliptické křivky (ECIES), která je také známá jako Rozšířená Šifrovací Schéma Eliptické Křivky. Této dva ztělesnění jsou identické až na změnu podkladové skupiny. 63
Pro odeslání zašifrováné zprávy Bobovi pomocí ECIES, Alice potřebuje následujíci informaci: •
KDF
-
Key
derivation
function (funkce
pro
odvození
klíče)
je
v kryptografii označení funkce, která odvozuje (vytvoří) jeden nebo více šifrovacích klíčů z nějakého tajemství (hlavní klíč, heslo, heslová fráze), typicky za použití kryptografické hašovací funkce (obecně lze použít jakýkoliv generátor pseudonáhodných čísel). KDF zajišťuje kryptografickou bezpečnost odvození klíče.Například ANSI-X9.63-KDF s SHA-1 opci. •
MACfunkce (Message Authentication Code) je kryptografická funkce podobná hašovacím funkcím. Rozdíl je, že funkce není jen výsledkem zpracovávaných dat, ale i klíče. Například HMAC-SHA-1-160 s160-bitovými klíči anebo HMAC-SHA-1-80 s 80-bitovými klíči;
•
Symetrická
šifrovací
schéma
E,
například
TDEA
(Triple
DES (označována
jako TDES či 3DES) je bloková šifra založená na šifrování Data Encryption Standard (DES), které aplikuje třikrát, čímž zvyšuje odolnost proti prolomení) v CBC způsobu (Cipher-block Chaining ) nebo XOR šifrovacím schématu. • • •
EC domenové parametry N, , , 5, W, G pro křivku nad polem prvočísel, nebo *, C , , , 5, W, G pro křivku nad binárním polem;
Bobův veřejný klíč: OË (Bob generuje ho takhle: OË )Ë 5, kde )Ë je tajným klíčem který on vybírá na náhodném: )Ë ∈ /1, W " 10);
volitělné sdílená informace: a Z .
Pro zašifrování zprávy * Alice musí provést následující operace:
1. generuje náhodné číslo ∈ /1, W " 10 a vypočítává B 5;
2. odvozuje sdílený tajný klíč: pt , kde p pt , ps OË (a p H |);
3. používá KDF pro odvození symetrického šifrování a MAC klíčů: ) ∥ )Å KDF ∥ ; 4. šifruje zprávu: % ) ; *;
5. vypočítává tag šifrované zprávy a Z : ( MAC)Å ; % ∥ Z ; 6. výstupy B ∥ % ∥ (.
Pro dešifrování šifrovaného textu B ∥ % ∥ ( Bob musí provest následující operaci:
64
1. odvozuje sdílený tajný klíč: pt , kde p pt , ps )Ë B (stejně jako to odvozovála Alice, protožep )Ë B = )Ë 5 = OË 5 = OË ), nebo výstup selhává pokud p |;
2. odvozuje klíč stejným způsobem jako Alice: ) ∥ )Å KDF ∥ ;
3. používá MAC pro ověření tagu a výstup selhávapokud ( H {¼)Å ; % ∥ Z ;
4. používá symetrickou šifrovací schému pro dešifrování zprávy * : ) ; %.
7.5 DLIES DLIES, Discrete Logarithm Integrated Encryption Scheme, neboli Integrována Šifrovací Schéma Diskretního Logaritmu, je asymetrickým procesem šifrování. DLIES představuje algoritmus pracující buď s exponenciálními funkci, anebo s Eliptickou kryptografii(ECC), a je náchylný k útokům. Tato metoda využívá výměnu klíčů a autentizační kód zprávy - Message Authentication Code (MAC). I kdýž můžeme použít stejný pár klíčů pro různé algoritmy na DLIES, měli bychom se toho vyhýbat, protože tato bezpečnostní oprávnění je tedy zpochybňováné a šifrování je zranitelné. Podobné potřeby mohou být dosažené jasnou specifikaci algoritmů s veřejným klíčem.
7.5.1 Pro zefektivnění Jak už býlo diskutováno dříve, bod násobení je hlavní operaci v ECC. Bod násobení zahrnuje velké množství bodů sčítání a bodů zdvojnasobení. Každý bod sčítání a zdvojnásobení zahrnuje multiplikativní inverzní operace. Nalezení multiplikativní inverze je nákladnou operaci v obojích konečných polech JL a JZ - .
Reprezentace bodů v projektivních souřadnicových systémech může vyloučit nutnost multiplikativní inverzní operaci v bodu sčítání a bodu zdvojnásobení zvyšením efektivity bodu multiplikativní operaci. Pro použití projektivních souřadnic v eliptických křivkách je třeba konvertovat daný bod v afinní souřadnici k projektivní souřadnici dříve než bod násobení, a pak převést zpět do afinních souřadnic, to po bodu násobení. Celý proces vyžádává pouze jednu multiplikativní inverzní operaci. Operace v projektivní souřadnici vyžaduje více skalárního násobení než v afinní souřadnici. ECC v projektivní 65
souřadnici bude efektivněji jen kdýž implementace skalárního násobení je mnohem rychleji než multiplikativní inverzní operace.
7.5.2 Závěr Pro efektivni implementaci ECC, pro algoritmus bodu násobení a základní aritmetické pole je důležitá výkonnost. Existuje různé metody pro efektivní implementaci bodu násobení a základní aritmetické pole vhodné pro různé hardwarové konfigurace. Implementace ECC za použitím projektivních souřádnic ukázala výrazné zlepšení účinnosti ve srovnání s implementací afinních souřádnic. Toto zlepšení výkonnosti je způsobeno vlivem odstraňování multiplikativní inverzní operace v bodě násobení, a v bodě zdvojnásobení, které by jinak vyžadoválo značné cykly procesoru. V ireducibilním polynomu v binárním poli implementace by měla být trinomickou nebo pentanomickou. Implementace ECC v binárním poli může být efektivnějí než implementace v základním poli. V SEC (Standards for Efficient Cryptography) jsou specikovány domenové parametry, irreducibilní polynomy jsou take trinomické nebo pentanomické. Tyto zvolené polynomy způsobí mnohem rychlejší běh polynomiální redukce v binárním poli, než je modulární redukce v primárním pole.
66
8 Nové směry v kryptografii Při sestavováni této práce jsem se uvědomila, že ve většine literatury jako vrchol kryptografické vědy je představená kvantová kryptografie. Ale vzhledem k tomu, že první kvantový kryptografický protokol byl navržen Bennettem a Brassardem až v roce 1984, mě samozřejmě zajimalo, co nového objevilo v kryptografii od této doby.
8.1 Biometrická kryptografie Spojení světa kryptografie s biometrickými systémy a zařízeními na první pohled slibuje poměrné slušné přínosy: nemuseli bychom pamatovát hesla, šifrovací klíče by byli generovány automaticky podle poskytnutého biometrického vzorku (například otisku prstu) apod. Kryptografie a biometrické systémy však představují dva výrazně odlišné světy, takže skloubení není nikterak triviální.
8.1.1 Problematické utajovaní Největší problém kryptograficko-biometrické dvojkombinace spočívá v odlišné přesnosti biometrické systémy nikdy neposkytnou stoprocentní výsledek v podobě rozhodnutí shoda/neshody, ale finální rozhodnutí závisi na nastavené úrovni. Přidržíme-li se modelu s otiskem prstu, uživatel tak může být úspěšně identifikován, i kdýž shoda nastala například jen z 90%. V ideálním případě bychom při spojení biometrických systémů (opět například otisk prstu) s kryptografií byli schopni získat zhruba následující model: uživatel poskytne svůj otisk prstu, na základě nasnímaného obrazu je automaticky vygenerován šifrovací klíč a data zašifrována. Jakmile pak uživatel svůj otisk poskytne znovu, vygeneruje se odpovidající klíč pro dešifrování chráněných dat a s jeho pomocí se získa opět původní otevřeny text. Základní a největší problém je nasnadě: z biometrik získaný klíč pro šifrování a dešifrování musí být vždy stejný. Pro zjednodušení skutečně můžeme uvažovat pouze symetrickou kryptografii - jakmile by se byt' jediný bit v šifrovacím a dešifrovacím klíči lišil, můžeme se s korektním otevřeným textem po dešifrování rozloučit. Vzhledem k faktu, že dva "stejné" otisky nikdy nejsou stejné, musí dojit k pokročilému zpracování ziskaného obrazu a co možná nejlepšímu odstranění všech chyb. Dalším z problémů by mohl být fakt, že biometriky jako takové nejsou žadným tajemstvím, například otisky prstů zanecháváme prakticky všude.. V přímem spojení s navazující kryptografií by 67
to bylo, jako kdybychom všude psali svá hesla (i kdýž bežný otisk samozřejmě technicky není snadné 100% využít). U nékterých bezkontaktních biometrik by potenciální útočník navíc hypoteticky mohl získat požadovaná biometrická data i bez vědomi uživatele.
8.1.2 Biometrické uzamčení klíče I přes veškeré spojené problémy postupem času vzniklo několik návrhů různých systémů pro spojení světu ne tolik přesných biometrik a naprosto exaktni kryptografie. Jedním z nejznamějších je například práce Johna Daugmanna a jeho kolegů, jedna se o snímání oční duhovky. První problém v podobě nepřesnosti "stejných" biometrických vzorků při různých snímáních zde má reálnou podobu zhruba 10 až 20 odlišných bitů, na pomoc proto přichází kombinace Hadamardova a Reed-Solomonova kódování. Toto dvojnásobné kódování dokaže zabránit jak chybám, které pramení přímo z obrazů získaných pomocí snímače, tak těm, jež svůj původ mají v následném zpracování. Celý proces postupu zpracování biometrického vzorku a jeho spojení s šifrovacím klíčem lze rozložit do několika následných akcí, z nichž první spočívá ve vytvoření náhodného klíče, jeho zakódování již zmíňovaným Hadamardovým a Reed-Solomonovým kódováním a doplňení na délku 2048 bitů. V dalším kroku již příchází na řadu snímání oční duhovky, jehož výsledkem je datový vzorek velikosti právě 2048 bitů. Tato posloupnost se pak operací XOR spojí s původním zakódovaným klíčem. Výsledek operace XOR je některem způsobem uchován, například uložen na libovolný token - inkriminovaných 2048 bitů není zapotřebí extra chránit, jelikož sami o sobě nic nevyzradí, a ještě jsou doplněny o hash kód odpovídajícího klíče, tedy původní posloupnosti náhodných bitů. Když útočník získá tento token, obsažené informace mu nic neřeknou, jelikož z hash kódu si takříkajíc nic nevezme a stejně tak ani z výsledné posloupnosti bitů, jež vznikla XORováním s uživatelovou duhovkou (jejím datovým otiskem). Jakmile na řadu přichází dekódování původního klíče, poskytne uživatel opět otisk své duhovky, který se XORuje s tím, jenž je uložen na tokenu. Diky symetričnosti operace XOR je tak získána původní zakódovaná posloupnost 2048 bitů, jež projde Hadamardovým a Reed-Solomonovým dekódováním (tedy nyní v opačném pořadí). Výsledný klíč by měl odpovídat původnímu, pro ověření čehož ještě dochází k porovnání souvisejících hash kódů. 68
Právě popsané schémy tedy ve výsledku nabízí dvoufaktorovou ochranu, jelikož pro korektní použití je zapotřebí jak odpovídající token, tak otisk duhovky opravněného uživatele. Nic však nebrání obohacení o další zabezpečení, a to v podobě klasického hesla - toho může být být využito například v kombinaci uloženou XORovanou posloupnosti, případně úpravě Hadamardovy matice během kódování. Práce profesora Daugmanna a jeho kolegů "suma sumárum" nabízí možnost využití oční duhovky k uzamčení šifrovacího klíče, jehož délka by měla být nejvýše 2048 bitů. Jedná se o na první pohled jednoduchý princip, který se právě díky rozšíření o ochranu heslem dokáže vyhnout pokusům s podvrženými biometrickými vzorky i nežadoucímu nevědomému bezkontaktnímu skenováni.
8.1.3 Měření dynamiky stisku kláves Odlišnou techniku spojení světa biometrie s kryptografii volí přístup Fabiana Monroseho a jeho spolupracovníků, základem je zde přitom využití biometriky v podobě měření dynamiky stisku klaves. Tato biometrická technologie je obecně nenáročná na hardware (postačuje totíž obyčejná klávesnice), vše tak obstaráva softwarová část. Nejčastěji sledovanými veličinami jsou prodlevy mezi stisky jednotlivých kláves během psaní a také délka stisku každé z nich. Právě tyto hodnoty dokážou poměrně spolehlivě odlišit dva různé uživatele. Navíc mezi jež fundamentální výhody patří uživatelská nevtíravost, jelikož v ideálním případě může sledování a analýza dynamiky probíhat na pozadí běžné práce. Právě takto získané biometrické údaje mohou být zkombinovány přímo se zadávaným heslem a vytvořít tak jakousi bezpečnější variantu klasického hesla - můžeme použít například označení zabezpečené heslo. Diky tomu by takovéto zabezpečené heslo mohlo při vhodné implementaci posloužit kupříkladu přímo během příhlašování se do systému a uživatel ani nemusí mít o systému biometrického měření na pozadí žadné extra povědomí. Pokud vezmeme v úvahu model s příhlašením se do systému biometrického měření na pozadí žádné extra povědomí. Pokud vezmeme v úvahu model s příhlašením se do systému, je ke každému příhlašovacímu jménu namísto standardního hesla přiřazeno právě vylepšené zabezpečené heslo, které v sobě již přímo kombinuje tajnou informaci a požadovánou biometrickou autentizaci. Základními biometrickými 69
daty jsou přitom již zmiňované prodlevy mezi stisky následujících klaves a doba stisku, tedy čas od úplného stlačení po uvolnění. K měření lze při implementaci využít standardních funkci operačního systému pro nízkoúrovňovou spolupráci s hardwarem. Spektrum funkcí je ale samozřejmě možné rozšířit o další, za použití speciální klavesnice by například šlo měřít i sílu stisku apod. Vlastní spojení přístupového hesla se získanými biometrickými hodnotami je už čistě otázkou použití vyšší matematiky.
8.1.4 Model BioPKI Třetí zajímavý přístup kombinace biometrik s kryptografii nabídla dvojice vědcu Hao Feng a Chan Ch.Wah. Abychom představili co možná nejšírší spektrum dostupných technik, volí take tento návrh opět jiný postup - biometrika (v tomto případě dynamika podpisu) je využita k zabezpečení soukromého klíče v použití klasického PKI. Take proto se pro popisovaný model vžilo označení BioPKI. Zkoumání dynamiky podpisu oproti porovnání standardních "statických" variant podpisu, jež jsou známé z každodenního života, přínáší hned několik neoddiskutovatelných výhod. První z nich je například schopnost analýzy rychlosti tahů perem na tabletu (ve směru obou os 2D prostoru), měření přítlaku na podložku apod. V kombinaci s prostým porovnáním výsledného podpisu je tak bezpečnost minimálně o řád výše. Průběh ověřování uživatele v rámci schématu BioPKI může být rozdělen do tŕí základních fází, jmenovitě se jedná o porovnání tvaru podpisu a konečně také generování odpovídajícího soukromého klíče. Opravněný uživatel by tak v ideálním případě naprosté datové shody při každém svém podpisu mohl pokaždé vygenerovat identický privátní klíč zde je však opět již zmíněny problém s proměnlivosti nabídnutého biometrického vzorku, a tedy určité neshodě výsledných klíčů. Na obecné úrovní je v uvedeném trojbodovém postupu prvotní výhodou statické porovnání během první fáze, jelikož to dovolí odhalit velice jednoduché pokusu o podvod (nebo skutečné nevydařené korektní podpisy) ve velice kratkém čase. Teprve v případě, že touto jednoduchou kontrolou podpis projde, extrahují se konkrétní vlastnosti (v původním návrhu jich je přes čtyři desítky). Získana data pak vstupuji do klasického generování klíču podpisového algoritmu DSA, a sice hashované pomocí SHA-1 přímo jako privátní klíč. Kombinace biometrických systému a kryptografie tak z uvedeného výčtu nejznámějších návrhů může mít různé podoby, příčemž záleží především na tom, jakým způsobem je zapotřebí ji v 70
konkrétní aplikaci využít. Do budoucna by se bezesporu mohlo jednat o žarné zitrky, ale jedině při dostatećné přesnosti zpracování získaného biometrického vzorku.
8.1.5 Termodynamická kryptografie Po kvantové kryptografii zde máme další metodu, jejíž bezpečnost údajně garantují přímo fundamentální fyzikální zákony: šifrování založené na druhé větě termodynamiky. S návrhem přišel Laszlo Kish (Texas A&M University) a jeho kolegové. Podstata metody má být jednoduchá. Linka spojující Alici s Bobem má na každém konci dva odpory. Alice použije nastavení svých odporů k tomu, aby pomocí něho zakódovala informaci, Bob naopak své odpory zapojí náhodně. V důsledku toho bude náhodný i proud/napětí na lince, tato informace bude normálně veřejná, ale jejím změřením nelze nic zjistit. Bob ale ví, jak své odpory zapojil, z měření pak dokáže vypočítat zapojení odporů Alice a z toho dekódovat i poslanou zprávu. Naopak Eva uprostřed komunikace se o nastavení jednotlivých odporů prý nemá jak dozvědět, protože pro ní je informace utopená v šumu. Zde se tedy právě uplatňuje druhá věta termodynamiky. Aby se Eva něco o odporech zjistila, musela by do systému přidat energii – a to by právě Bob i Alice poznali. Podobně jako u kvantové kryptografie jde tedy o to, že odposlech nevyhnutelně změní vlastnosti systému. Kish srovnává svůj přístup právě s kvantovou kryptografií, jejíž implementace jsou prý zranitelné a metoda s ní spojená očekávání podle něj prostě nenaplnila. Problém s konkrétní implementací ovšem nastává i zde. Nešlo by to nějak obejít? Tak například existují experimenty s využíváním Brownova pohybu pro usměrněné přesuny molekulárního robota, což také působí jako v rozporu s druhým zákonem termodynamiky – jako by se dal trochu „ohnout". Nicméně oponenti žádnou zranitelnost v Kishově postupu zatím nenašli. Skoro tak dlouho kolik tento koncept existuje, kvantová kryptografie se pohybuje jenom v představách a teorii, a její nástup je považován za revoluci a zcela bezpečné sítě. Teoreticky, kvantové crypto (na základě zákonů kvantové mechaniky) zaručujé úplné utajení přenášených zpráv: špehování na kvantové šifrované zprávě neodvolatelně mění obsah zprávy, čímž zpráva je neprolomitelná. Ačkoliv v praxi, zatímco komunikace kvantově šifrovaných zpráv je bezpečná, v počítačích na obou koncích linky není nikdy zaručena bezchýbnost. Například, k čemu potřebujeme
71
kvantový komunikační kanál, kdýž přenášecí (nebo přijímajíci) zprávy se ukládají do lokální paměti, která může být snadno prolomena? Nicméně, podle László Kish a jeho týmu z Texas A&M, existuje způsob vybudováni zcela bezpečného "end-to-end" systému, ale namísto použití kvantové mechaniky budeme muset použít klasickou fyziku: přesněji druhý termodynamický zákon. Druhý termodynamický zákon se zabývá pokračující entropií, jehož hlavní myšlenkou je, že postupem času systém vždy ztrácí energii na jeho prostředí. Tento efekt, postupně přivede k neuvěřitelně řídkému šíření energie a smrti vesmíru. Obr.1.d.Základní princip termodynamické kryptografii
Zdroj: http://computerworld.cz/technologie/termodynamicka-kryptografie-pry-prekonava-kvantovou-48548
Ale zpět k kryptografii. Kishův systém se skládá z drátu (komunikační kanál ), a dva rezistory na obou koncích (z nichž jeden představuje binární 0, druhý binární 1). Připojený k drátu zdroj energie byl ošetřen s Johnson-Nyquistovým šumem (tepelný šum). Johnsonův hluk je často základem pro vytvoření náhodných čísel s počítačovým hardwarem . Když Alice chce poslat zprávu Bobovi, ona zakóduje svou zprávu modulací zdroje napájení pomocí dvou rezistorů na konci její drátu - pokud chce poslat binární 0, ona se připojí k prvnímu rezistoru na drátu, pokud chce poslat binární 1, k druhému rezistoru. Výsledkem je signál, který se zdá 72
představen stále jako Johnsonův hluk, ale který má svou aktuální modulaci provedenou Alici. Bob se připojí své rezistory náhodně, a měří signál který přijde na jeho konec. Protože obě strany znají napětí a proud napájecího zdroje, a Bob ví jaký rezistor se připojil, on může analyzovat napětí a proud pro signál k práci, zpracovát Alice používá - a tedy binární zpráva se přenáší . Stejně jako kvantové krypto, špionážní (man-in-the-middle) útoky na tento termodynamický systém jsou zřejmě nemožné. Pokud se stalo, že Eva bude chtít odposlechnout komunikaci, ona neví který rezistor byl připojen, a proto nemůže dešifrovat Johnsonův hluk. Druhý termodynamický zákon brání Evě z získávaní informací s man-in-the-middle útoku - a aktivně naslouchaní Aliciových nebo Bobových rezistorů by vyžadovalo o doplnění většího množství energie systému, který může být snadno spatřen. Kish a jeho tým tvrdí, že tento systém je zcela bezpečný - tvrzení, které dosud nebylo zpochybňeno. Je to neuvěřitelně nepravděpodobné, že systém je doposud neprolomitelný - ale kdo ví, jak na tom bude v budoucnosti. Ale zatím neexistuje žádná zmínka o vzdálenosti přenosu maximální intenzity signálu, jestli může být opakován nebo zesílen, nebo o maximální datové rychlosti. Před 10 lety toho kvantová kryptografie slibovala hodně, za tu dobu se ale nesplnilo téměř nic; dokonce se zdá, že překážky v její implementaci mohou být neodstranitelné přímo z principu. Někteři doconce tvrdí, že termodynamické šifrování by mohlo být pro kvantovou kryptografii hřebíčkem do rakve.
73
Závěr Cílem mé práci bylo předvest čtenářovi co nejaktuálnějši a nejúplnější informaci o eliptických kryptosystémech a souvisejících článcích. Ale jakmile jsem začala s vypracováním této práci, uvědomila jsem se že naprosté neexistují podobné materiály v češtině, většina literatury byla vydána maximálně počátkem devadesátých let, a mohla jsem z ni čerpat jen několik základnějších věci. Měla jsem dokonce pocit, že vše možné české materiály které se týkají kryptografie, jsem využila ve své bakalářské práci. Táto práce na 90% se skládá z anglické literatury a trochu německé a ruské, snažila jsem to sama co nejpřesněji přeložit do češtiny. V případech, když existoval pouze anglický termín, uváděla jsem to v obou jazycích. Když něco mi nebylo jasné, zeptavala jsem se na to rovnou autorů použité literatury. Mluvila jsem třeba s Mrs. Laurou Hittovou ohledně otázek o standartizaci, a s Ed. Philippem Gaboritem ohledně postkvantové kryptografii. Chtěla jsem také uvést více o postkvantové kryptografii, ale bohužel by to bylo daleko za ramec této práce. Pro zájemce můžu doporučit knihu vydanou Phillipe Gaborit (Ed.) "Post-Quantum Cryptography" od roku 2013. V této knize můžete přečíst o nejnovějších algoritmech postkvantové kryptografie, o Lattice-Based Cryptography "mřížková kryptografie", kvantových algoritmech a další. Zájemce můžou take navštívit vědeckou konferenci PQCrypto, která probíhá každých 18 měsiců. V roce 2011 se konála v Taiwani, 2013 byla ve Francii, a příští bude konát v roce 2014 Canade, v Waterloo. Přesná adresa: PQCrypto 2014. Institute for Quantum Computing, University of Waterloo, Canada, October 1-3, 2014. Webova adresa: http://pqcrypto2014.uwaterloo.ca/ Ubytováni pro studenty je zdarma. Závěrem k moderní kryptografii můžu říci, že podle mě, i když termodynamická kryptografie představena jako důstojná a úplná záměna kvantové, bylo by nerozumně hned kvantovou kryptografii odmítat. I když je dnes ukázalo, že není docela praktická, určitě je to jedná z nejpropracovanějších oblastí, musíme jenom najít ten správný způsob použití, ale zatím není jasné zda na to potřebujeme počítače uplně nového typu. Docela zajímavá je myšlenka spojení kryptografii s biometrií, ja myslím, její použití v kombinaci například s eliptickou kryptografii by dodalo ještě vyšší stupeň zabezpečení. Co se týká eliptické kryptografii, ja myslím, že už bychom měli na ni konečné přejít. Například, kde jste viděli ECDSA certifikat? I když standardu je už 13 let, všude se stále používá RSA. Mezitím 74
RSA má hodně detailů. Popis algoritmu je jednoduchý, ale kvůli této složité detailnosti, bezpečnost může být svržena během vteriny. My dobře víme, že čím složitější je systém, tým vyšší je pravděpodobnost výskytu chyby. Pokud uzavříme tema o eliptické kryptografie , jake jsou její výhody a nevýhody? Klady: 1. Mnohem menší délka klíče v porovnání s "klasickou" asymetrickou kryptografií. 2. Rychlost eliptických algoritmu je mnohem vyšší, než klasických. To je dáno jak velikostí pole, tak i použití mnohem bližší pro počítače struktury konečného binárního pole. 3. Vzhledem k malé délce klíčů a vysokorychlostnímu provozu, můžou asymetrické kryptografické algoritmy na eliptických křivkách být použíty v čipových smart-kartech a dalších zařízeních s omezenými výpočetními zdroji. Zápory: 1. Všechny výhody eliptické kryptografie vycházejí z jedné konkrétní skutečnosti: pro příklady diskrétního logaritmu v eliptických křivkách, neexistují subexponenciální algoritmy řešení. To snižuje délku klíče a vede ke zvýšení produktivity. Avšak když týto algoritmy objeví, to bude znamenat zhroucení eliptické kryptografie. 2. Eliptická kryptografie je velice složitá. Je to obrovské množství nuancí, které je třeba vzít v úvahu. Začíná to z výběru eliptické křivky a končí s generací klíčů. V případě hromadného přechodu na eliptickou kryptografii se bude pravděpodobně vyskýtovat hodně chyb a hrozeb, které již byly propracovány u více konvenčních metod. Jakou vidím budoucnost kryptografie? Ja myslím, že je ve spojení s ostatními vědami. Je určítě hodně zajímavá myšlenka spojení kryptografii s biometrií. Pokud bychom dokázali najít způsob který by umožňoval její hromadné použití, dodá to veliký způsob zabezpečení jakémukoliv systému. Zajímavá by mohla být myšlenka spojení kryptografii s astronomií. Například, nějaký algoritmus by bylo možné rozluštít jen v určitý den a čás, třeba v pondělí v 18.28. V žádném jiném případě, i správně napsané heslo by bylo neplatné. To by mělo ale zápor v tom, že by to hodilo spíše pro dlouhodobě archivována data, které nepotřebujeme ihned, ale většinou to naopak.
75
Určitě zajímavá by byla možnost spojení kryptografii s chemií, dle analýzy pachu, krve jedince, s genetikou, podle DNA čí genomu konkretního člověka… Ale malokdo by příjal systém, kde třeba pro banální kontrolu e-mailu chtěl po člověku odebrat krevní vzorek, a bylo by to tak u dalších, vice serióznějších věcí (například při vstupu do bankovního učtu). Lidi by nechtěli žádný diskomfort, i kdyby to dávalo vyšší bezpečnost dat. Proto tohle vidím spíše u budoucího počítače. Počítač budoucnosti představují jako počítač který je řízen myšlením konkrétního člověka, a podle nastavených omezení může skenovát prostředí a získávat tím informaci. Dokázal by třeba zjístit soustavu krve jedince jen “ze vzduchu”. To by představovalo velikanský vědecký pokrok, a také pokrok v medicině. Co kdyby domací počítač dokázal momentálně zjístit že se něco ve člověku neděje správně? Většina nelečitelných dnes nemocí by tím přestala existovat, protože by byli eliminovány až na začátku. Medicinské protézy by ničím nelišíly od skutečných rukou, nohou, protože by byly dokonale řízeny myšlením. Co kdyby paralizovaný člověk dokázal stále komunikovat s rodinou, psát něco na počítači, pracovát, protože dokaže řídit počítač myšlením? Znamenálo by to velký etický pokrok. Na co potřebujeme takto výsokou ochranu? Pokud bychom dostali k revolučnímu spojení lidského mozku a těla s počítači, jakékoliv útok by představoval sebou ohrožení lidských práv a svobod, a možná zdraví a života jedince. Proto by hlavním a nejzákladnějším cílem by býla absolutní bezpečnost a neprolomitelnost. Ja věřím, že detailným studiem novějších kryptografických metod, ochotě této novější metody používat v práxi a tím jich rozvíjet, spojení kryptografie s dalšími vědy a kombinaci s jíž znamými kryptografickými metody, jsme na práhu nové éry - éry absolutně bezpečné a neprolomitelné kryptografii.
76
Použitá literatura a zdroje: [1]
PRENEEL, BART; RIJMEN, VINCENT (Eds.) State of the Art in Applied Cryptography. Course on Computer Security and Industrial Cryptography, Leuven, Belgium, June 3-6, 1997 Revised Lectures. Series: Lecture Notes in Computer Science, Vol. 1528. 1998, VIII, 400 p.
[2]
Laura HITT. Updated Standards for Validating Elliptic Curves Department of Mathematics The University of Texas at Austim Austin, TX 78112. 2007
[3]
IEEE P1363
http://en.wikipedia.org/wiki/IEEE_P1363 [4]
Mugino SAEKIElliptic Curve Cryptosystems School of Computer Science McGill University, Montreal February 1997
[5]
Eliška OCHODKOVÁMatematické základy kryptografických algoritmu Vysoká škola baňská – Technická univerzita Ostrava – Zapadočeská univerzita v Plzni
[6]
Prof. Karel REKTORYS Dr.Sk. a spolupracovniciPřehled užité matematiky SNTL – Nakladetelství technické literatury Praha 1988
[7]
Neal KOBLITZElliptic Curve Cryptosystems 1987
[8]
Anoop MS Elliptic Curve Cryptography An Implementation Guide
[email protected]
[9]
Discretní logaritmus http://mathworld.wolfram.com/DiscreteLogarithm.html
[10]
IES http://en.wikipedia.org/wiki/Integrated_Encryption_Scheme
[11]
KDF 77
http://cs.wikipedia.org/wiki/Key_derivation_function [12]
MAC http://en.wikipedia.org/wiki/Message_authentication_code
[13]
DLIES http://www.itwissen.info/definition/lexikon/DLIES-discrete-logarithm-integratedencryption-scheme.html
[14]
Permutace http://cs.wikipedia.org/wiki/Permutace
[15]
Kvantová kryptografie http://cs.wikipedia.org/wiki/Kvantov%C3%A1_kryptografie
[16]
Termodynamická kryptografie http://computerworld.cz/technologie/termodynamicka-kryptografie-pry-prekonavakvantovou-48548
[17]
Biometrická kryptografie časopis Connect! duben 2006
[18]
Eliptická kryptografie: teorie http://habrahabr.ru/post/188958/
[19]
Philippe Gaborit (Ed.)Post-Quantum Cryptography 5th International Workshop, PQCrypto 2013 Limoges, France, June 2013, Proceedings
78
Seznam obrázků a tabulek
Obrázek č. 1.a:
22
Obrázek č. 1.b:
26
Obrázek č. 1.c:
44
Obrázek č. 1.d:
62
Tabulka č. 1.1:
12
Tabulka č. 1.2:
30
Tabulka č. 1.3:
31
Tabulka č. 1.4:
49
Tabulka č. 1.5:
52
Tabulka č. 1.6:
53
79
PŘÍLOHA 1
Jak je pravděpodobnost prolomení šifry? Jaká Můžeme šifru vůbec prolomit? Zajímala mě otázka, jak je velká pravděpodobnost toho, že dokážeme jen náhodou prolomit šifru. Pokud by byla docela velká, to by asi znehodnotilo kryptografii jako vědu vůbec. kryptografii Za příklad jsem rozhodla použit standartní PIN kod - čtyřčíselný, od 0 do 9. Máme tři možnosti nedokážeme li prolomit za jednu z těch třech, blokuje to. Představíme si, že chceme dozvědět kod nedokážeme-li pouhým hádáním.
Permutace Nejdřív musím přivest pojem permutace. permutace Permutace množiny, množiny, která obsahuje
prvků, je jedno z
možných uspořádání těchto prvků, přičemž výsledná uspořádaná n n-tice tice má stejný počet prvků jako původní množina. Někdy se také uvažují tzv. permutace s opakováním opakováním,, což zahrnuje i takové uspořádání prvků, ve kterém se některé prvky vyskytují vícekrát. Máme PIN, ve kterém se můžou vyskytovat čísla od 0 do 9. Šance odhadnout správně s prvního pokusu je . Podrobnějí by to vypadalo takto: 1. pokus: 10 možností 2. pokus: krat 10 možností
3. pokus:
=
Přivedeme příklad s opakováním a bez o opakováni pakováni
1
Bez opakováni Znamená to, že pokud jednou napíšeme PIN, jako například 1465, a bude chybný, nebudeme ho dál psát. Jaká je pravděpodobnost, že odhadneme PIN v jeden z těchto třech pokusů? N NZ N; = ? ë
1 pokus.:
N
ë :
2 pokus.:
ë :Z
3 pokus.:
1 ∑= í
=:
NZ N;
.
S opakovánim Znamená to, že napsaný kod, i když je chybný, můžeme napsat podruhé a potřetí. 1,2,3 pokus = N NZ N; V tomto případě vše tři pokusy se budou rovnat
. ë
Hypergeometrické rozdělení Rozebereme o něco pravděpodobnější variantu. Máme tři pokusy, a zajímá nás, jaká je šance odhadnout správnou šifru za jeden z těchto pokusů? Na tuto otázku nám pomůže odpovědět hypergeometrické rozdělení. ) z") ¥ ¦¥ ¦ W " p z, W, ), z ¥ ¦ W
2
Obr. 1.e. Hypergeometrické ypergeometrické rozdělení na příkladu
Zdroj: vlastní uprava
Máme nadobu z bílými, a jen několika černými míčky. N
míčků
k
černých míčků
n
počet míčků (vybereme)
x
bude černých
... pravděpodobnost, že x z n bude černých
3
Hádání klíče Hypergeometrické rozdělení N ... počet možností ) 1 příznivá možnost n ...
počet pokusů pî, í,=í;,t
1 ¥ ¦1 0
1 z"1 z"1 ¥ ¦¥ ¦ ¥ ¦ W " W " z z ¥ ¦ ¥ ¦ W W
1 ¥ ¦1 1 Vratíme se k našemu příkladu s PIN kodem.
Jaká je pravděpodobnost, že při třech pokusech klíč není v žadném?
N ... 10
(4 znaky 0 ... 9)
)1
W3
(jediný klíč)
0 1
ptí
¥
¦
ë :
; ë ;
ë : ë :Z ë :; ;! ë ë : ë :Z ;!
10 " 3 3 1 " 0,9997 10 10
Jaká je pravděpodobnost, že klíč se objeví aspoň v jednem? ptí
=: ;: î;
¥
¦
ë :
Z ë ;
ë : ë :Z
ë ë : ë :Z ;!
4
3 0,0003 10
Jaká je pravděpodobnost, že odhadneme z jedného, druhého, nebo třetího pokusu? n je tady počet pokusů W1
1. Pokus: ptí
=: =:t
î=
2. Pokus: ptí 3. Pokus: ptí
¥
¦
ë :
ë Z
W3
=: =:t
î=
¥
¦
ë :
ë
W2
=: =:t
î=
¥
¦
ë :
Z ë ;
1
ë
1 0,0001 10
10 " 1 Z ë
0,0002
0,0003
V případě, že bychom měli větší počet pokusů, vícečíselnou šifru, atd. – pravděpodobnost zjistíme velice jednoduše dosazením do tohoto vzorce. Co kdyby šifra se skládala nejenom z čísel, ale znaků ASCII tabulky nebo dokonce Unicode? ASCII má 256 znaků, Unicode 110000. Znamená to, že pravděpodobnost odhadnutí správné šifry s prvního pokusu u ASCII tabulky
ZÂ>X
, u Unicode je to dokonce
X
.
Tohle nám dokazuje, že pravděpodobnost náhodného prolomení šifry je tak malá, že lze ji zanedbat.
5
