Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Kˇrivky a kryptografie
Miroslav Kureˇs
Pavlov, 6. ˇcervna 2011
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Obsah
1
Kˇrivky
Algebraick´e rovinn´e kˇrivky
Eliptick´e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´e kˇrivky jako grupy
2
Asymetrick´
a kryptografie
Principy
RSA (Rivest, Shamir a Adleman)
3
ECC (& HECC)
´
Uvod
do ECC
Vizualizace eliptick´ych kˇrivek nad koneˇcn´ymi poli
ˇ ad eliptick´e kˇrivky
R´
Hypereliptick´e kˇrivky
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
4
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Algebraick´
e rovinn´
e kˇrivky
Uvaˇzujeme mnoˇzinu ˇreˇsen´ı rovnice
P(x, y ) = 0
(P polynom)
Pak:
deg P = 1: pˇr´ımky
deg P = 2: kuˇzeloseˇcky
deg P = 3: 78 typ˚
u (Newton: 72)
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Kubick´
e rovinn´
e kˇrivky
Tedy: vhodnou transformac´ı souˇradnic lze kaˇzdou kubickou
kˇrivku pˇrev´est na jeden ze sedmdes´ati osmi kanonick´ych
typ˚
u. Tyto typy sdruˇzujeme do ˇctyˇr skupin.
skupina ˇcarodˇejnic Agnesiov´e:
xy 2 + ey = ax 3 + bx 2 + cx + d
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Kubick´
e rovinn´
e kˇrivky
Tedy: vhodnou transformac´ı souˇradnic lze kaˇzdou kubickou
kˇrivku pˇrev´est na jeden ze sedmdes´ati osmi kanonick´ych
typ˚
u. Tyto typy sdruˇzujeme do ˇctyˇr skupin.
skupina ˇcarodˇejnic Agnesiov´e:
xy 2 + ey = ax 3 + bx 2 + cx + d
skupina Newtonov´ych trojzubc˚
u:
xy = ax 3 + bx 2 + cx + d
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Kubick´
e rovinn´
e kˇrivky
Tedy: vhodnou transformac´ı souˇradnic lze kaˇzdou kubickou
kˇrivku pˇrev´est na jeden ze sedmdes´ati osmi kanonick´ych
typ˚
u. Tyto typy sdruˇzujeme do ˇctyˇr skupin.
skupina ˇcarodˇejnic Agnesiov´e:
xy 2 + ey = ax 3 + bx 2 + cx + d
skupina Newtonov´ych trojzubc˚
u:
xy = ax 3 + bx 2 + cx + d
skupina rozb´ıhav´ych parabol:
y 2 = ax 3 + bx 2 + cx + d
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Kubick´
e rovinn´
e kˇrivky
Tedy: vhodnou transformac´ı souˇradnic lze kaˇzdou kubickou
kˇrivku pˇrev´est na jeden ze sedmdes´ati osmi kanonick´ych
typ˚
u. Tyto typy sdruˇzujeme do ˇctyˇr skupin.
skupina ˇcarodˇejnic Agnesiov´e:
xy 2 + ey = ax 3 + bx 2 + cx + d
skupina Newtonov´ych trojzubc˚
u:
xy = ax 3 + bx 2 + cx + d
skupina rozb´ıhav´ych parabol:
y 2 = ax 3 + bx 2 + cx + d
skupina kubick´ych parabol:
y = ax 3 + bx 2 + cx + d
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Kubick´
e rovinn´
e kˇrivky
Podobnˇe jako kvadratick´e kˇrivky jsou ˇrezy kuˇzele rovinou,
bylo dok´az´ano (Clairaut), ˇze kubick´e kˇrivky jsou ˇrezy tzv.
kubick´eho kuˇzele
zy 2 = ax 3 + bx 2 z + cxz 2 + dz 3
vhodnou rovinou.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Eliptick´
e kˇrivky
Eliptickou kˇrivkou E nad polem F rozum´ıme algebraickou
kˇrivku tˇret´ıho stupnˇe s rovnic´ı
y 2 + a1 xy + a3 y = x 3 + a2 x 2 + a4 x + a6 ,
kde a1 , a2 , a3 , a4 , a6 ∈ F a kde tzv. diskriminant ∆ eliptick´e
kˇrivky E je nenulov´y. Pˇritom
∆ = −d22 d8 − 8d43 − 27d62 + 9d2 d4 d6
d2 = a12 + 4a2
d4 = 2a4 + a1 a3
d6 = a32 + 4a6
d8 = a12 a6 + 4a2 a6 − a1 a3 a4 + a2 a32 + a42 .
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Eliptick´
e kˇrivky
Mystick´e“ vlastnosti eliptick´ych kˇrivek:
”
ˇreˇsen´ı eliptick´ych rovnic, napˇr.
y2 = x3 − 2
(Fermat)
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Eliptick´
e kˇrivky
Mystick´e“ vlastnosti eliptick´ych kˇrivek:
”
ˇreˇsen´ı eliptick´ych rovnic, napˇr.
y2 = x3 − 2
(Fermat)
ˇ
Tanijamova-Simurova(-Weilova)
hypot´eza: eliptick´e
kˇrivky odpov´ıdaj´ı modul´arn´ım form´am =⇒ Velk´a
Fermatova vˇeta (Wiles 1993)
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Eliptick´
e kˇrivky
Mystick´e“ vlastnosti eliptick´ych kˇrivek:
”
ˇreˇsen´ı eliptick´ych rovnic, napˇr.
y2 = x3 − 2
(Fermat)
ˇ
Tanijamova-Simurova(-Weilova)
hypot´eza: eliptick´e
kˇrivky odpov´ıdaj´ı modul´arn´ım form´am =⇒ Velk´a
Fermatova vˇeta (Wiles 1993)
r. 1985 navrhnut kryptosyst´em zaloˇzen´y na eliptick´ych
kˇrivk´ach (Koblitz, Miller), od cca poloviny 90. let
prakticky vyuˇz´ıv´an
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Eliptick´
e kˇrivky
Je-li F koneˇcn´e pole s charakteristikou r˚
uznou od 2 a 3, pak
vhodnou zmˇenou souˇradnic lze Weierstrassovu rovnici
transformovat na rovnici
y 2 = x 3 + ax + b.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Eliptick´
e kˇrivky
Je-li F koneˇcn´e pole s charakteristikou 2, pak vhodnou
zmˇenou souˇradnic lze Weierstrassovu rovnici transformovat
na rovnici
y 2 + xy = x 3 + ax 2 + b
(tzv. nesupersingul´arn´ı eliptick´a kˇrivka) nebo na rovnici
y 2 + cy = x 3 + ax + b
(tzv. supersingul´arn´ı eliptick´a kˇrivka).
Obdobn´a vˇeta plat´ı i pro pole charakteristiky 3.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Eliptick´
e kˇrivky
Bodem eliptick´e kˇrivky E pak rozum´ıme kaˇzd´y bod [x, y ] se
souˇradnicemi x, y ∈ F splˇ
nuj´ıc´ımi jej´ı rovnici a d´ale bod ∞.
ˇad eliptick´e kˇrivky E potom definujeme jako poˇcet jej´ıch
R´
bod˚
u a znaˇc´ıme ho #E. Nad body eliptick´e kˇrivky lze
zav´est operaci + souˇctu bod˚
u tak, ˇze (E, +) je grupa.
(Jedin´y typ rovinn´ych kˇrivka, nad jej´ımiˇz body lze
netrivi´aln´ım zp˚
usobem strukturu grupy zav´est!)
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Algebraick´
e rovinn´
e kˇrivky
Eliptick´
e kˇrivky
Zjednoduˇsen´ı Weierstrassovy rovnice
Eliptick´
e kˇrivky jako grupy
Eliptick´
e kˇrivky
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Principy
RSA (Rivest, Shamir a Adleman)
Principy asymetrick´
e kryptografie
Alice a Bob si chtˇej´ı pos´ılat zpr´avy tak, aby je Eva
nepˇreˇcetla. Pˇrev´adˇej´ı proto otevˇrenou zpr´avu m na
ˇsifrovanou zpr´avu c.
Kryptologie, kryptografie, kryptoanal´yza.
Kl´ıˇc.
Asymetrick´a kryptografie = kryptografie s veˇrejn´ym kl´ıˇcem
(veˇrejn´y kl´ıˇc pro ˇsifrov´an´ı zpr´avy, tajn´y kl´ıˇc pro deˇsifrov´an´ı
zpr´avy)
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Principy
RSA (Rivest, Shamir a Adleman)
Principy asymetrick´
e kryptografie
Kaˇzd´a zpr´ava je interpretovateln´a numericky, napˇr.
bin´arn´ım ˇc´ıslem dan´ym ASCII tabulkou znak˚
u (kter´a m´a ve
sv´e rozˇs´ıˇren´e verzi 256 znak˚
u, tzn. 8 bit˚
u = 1 Byte). V
kryptografii se pak zpr´ava transformuje na skupiny bit˚
uo
pevn´e d´elce, tzv. bloky. Napˇr´ıklad 128-bitov´e ˇsifrov´an´ı
uˇz´ıv´a bloky o d´elce 128 bit˚
u, tzn. kaˇzd´ych 16 znak˚
u urˇc´ı
ˇc´ıslo, kter´e budeme ˇsifrovat. Sekvenci ˇc´ısel, kter´e budeme
ˇsifrovat, naz´yv´ame otevˇren´a zpr´ava a znaˇc´ıme m. Novou,
ˇsifrovanou sekvenci ˇc´ısel pak naz´yv´ame ˇsifrovan´a zpr´ava a
znaˇc´ıme c.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Principy
RSA (Rivest, Shamir a Adleman)
Principy asymetrick´
e kryptografie
Asymetrick´a kryptografie se op´ır´a o tzv. jednosmˇern´e
funkce, kter´e se obt´ıˇznˇe invertuj´ı. K nalezan´ı inverze ale
mohou pomoci tzv. padac´ı vr´atka: doplˇ
nkov´a informace,
kter´a efektivn´ı v´ypoˇcet inverze umoˇzn´ı.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Principy
RSA (Rivest, Shamir a Adleman)
RSA
Vezmˇeme ˇc´ıslo n = 769595379731, kter´e je souˇcinem dvou
prvoˇc´ısel, necht’ pak X = {1, 2, . . . , n − 1}. Zvolme
exponent e, napˇr. e = 7 a zadejme funkci f : X → X
pˇredpisem
y = f (x) = x e mod n.
Tedy napˇr´ıklad f (1111) = 17444456121. Pˇri znalosti e a n
(veˇrejn´y kl´ıˇc) tedy otevˇrenou zpr´avu 1111 pˇrevedeme
snadno na zaˇsifrovanou zpr´avu 17444456121.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Principy
RSA (Rivest, Shamir a Adleman)
RSA
Samotn´a znalost veˇrejn´eho kl´ıˇce nestaˇc´ı ovˇsem ke stejnˇe
snadn´emu pˇreveden´ı zaˇsifrovan´e zpr´avy na p˚
uvodn´ı
otevˇrenou; f je jednosmˇern´a funkce. Existuj´ı ale padac´ı
vr´atka: tˇemi je faktorizace ˇc´ısla n: n je souˇcinem prvoˇc´ısel
p1 = 876761 a p2 = 877771 (soukrom´y kl´ıˇc). Nyn´ı pro
φ = (p1 − 1)(p2 − 1) = 769593625200 vezmeme d tak, ˇze
1 < d < φ a ed mod φ = 1: takov´ym je
d = 659651678743. Nyn´ı je
x = yd
mod n,
tedy 17444456121659651678743 mod 769595379731 = 1111.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Principy
RSA (Rivest, Shamir a Adleman)
RSA
Vˇsimnˇeme si: hledali jsme d, aby ed mod φ = 1.
D˚
uleˇzitou souˇcast´ı vˇetˇsiny asymetrick´ych kryptosyst´em˚
u je
implementace rozˇs´ıˇren´eho Euklidova algoritmu (obecnˇe:
nad Bezoutov´ymi okruhy). Napˇr. pro nalezen´ıho inverzn´ıho
prvku k prvku e v Zφ (exponent e proto nutno vz´ıt tak, aby
nedˇelil ani p1 − 1, ani p2 − 1; jinak je v Zφ dˇelitelem nuly!)
aplikujeme rozˇs´ıˇren´y Euklid˚
uv algoritmus na prvky e a φ a
−1
pak je e = x.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Principy
RSA (Rivest, Shamir a Adleman)
RSA
ˇeny
´ Euklid˚
Algoritmus. Rozˇ
s´ır
uv algoritmus.
Vstup: a, b ∈ R
´ stup: nejve
ˇtˇ
ˇ ny
´ de
ˇlitel d = gcd(a, b),
Vy
s´ı spolec
ˇ
´
´
x, y splnujıcı a × x + b × y = d
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Principy
RSA (Rivest, Shamir a Adleman)
RSA
1: if b = 0 then
2: d ← a; x ← 1; y ← 0;
3: else
4: x2 ← 1; x1 ← 0; y 2 ← 0; y 1 ← 1;
5: end if
6: while b 6= 0 do
7: q ← a div b; r ← a − q × b; x ← x2 − q × x1;
y ← y 2 − q × y 1;
8: a ← b; b ← r ; x2 ← x1; x1 ← x; y 2 ← y 1; y 1 ← y ;
9: end while
10: d ← a;
11: return x ← x2; y ← y 2
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
ECC
Proˇc vlastnˇe hledat nov´e kryptosyst´emy?
nedok´azan´a jednosmˇernost funkc´ı (tedy nebezpeˇc´ı
prolomen´ı st´avaj´ıc´ıho syst´emu)
lepˇs´ı vlastnosti, efektivnˇejˇs´ı pouˇzit´ı (napˇr. 160-bitov´y
ECC kl´ıˇc poskytuje tut´eˇz u
´roveˇ
n bezpeˇcnosti jako
1024-bitov´y RSA kl´ıˇc)
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
ECC
Eliptick´a kˇrivka nad prvoˇc´ıseln´ym polem:
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
ECC
Eliptick´a kˇrivka nad prvoˇc´ıseln´ym polem:
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
ECC
Zn´azornˇen´ı souˇctu na eliptick´e kˇrivce nad prvoˇc´ıseln´ym
polem:
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
ECC
Zn´azornˇen´ı eliptick´e kˇrivky na toru:
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
Eliptick´
e kˇrivky
Je-li E eliptick´a kˇrivka nad polem Fq , pro jej´ı ˇr´ad #E(Fq )
plat´ı odhad
√
√
q + 1 − 2 q ≤ #E(Fq ) ≤ q + 1 + 2 q
(Hasseho interval). Existuje tedy t ∈ Z takov´e, ˇze
#E(Fq ) = q + 1 − t,
Miroslav Kureˇs
√
kde |t| ≤ 2 q.
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
Eliptick´
e kˇrivky
Legendr˚
uv symbol
m
n


1
= 0


−1
m
n
se zav´ad´ı n´asledovnˇe:
je-li m kvadratick´ym reziduem (modulo n)
je-li m nula (modulo n)
je-li m kvadratick´ym nereziduem (modulo n)
Potom ˇr´ad eliptick´e kˇrivky pomoc´ı t a Legendrova symbolu
vyj´adˇr´ıme takto:
X x 3 + ax + b t=−
p
x∈Fp
Pˇr´ım´e uˇzit´ı tohoto vztahu se nˇekdy naz´yv´a naivn´ı
algoritmus pro urˇcen´ı ˇr´adu eliptick´e kˇrivky.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
ECC
Urˇceme nejdˇr´ıve tzv. ˇr´ad bodu P eliptick´e kˇrivky: je to
ˇ ad kaˇzd´eho bodu P
nejmenˇs´ı n ∈ N takov´e, ˇze nP = ∞. R´
eliptick´e kˇrivky E dˇel´ı ˇr´ad t´eto kˇrivky. (To je obecnˇe zn´am´y
fakt z teorie grup.) Budeme uvaˇzovat pole Fp , nad n´ım
eliptickou kˇrivku kˇrivku E a na n´ı nˇejak´y jej´ı bod P s
prvoˇc´ıseln´ym ˇr´adem n. Vyberme si nˇejak´e k ∈ [1, n − 1] a
´
spoˇctˇeme Q = kP. Udaje
o poli a eliptick´e kˇrivce jsou tzv.
definiˇcn´ı parametry a pokl´adaj´ı se za zn´am´e.
Veˇrejn´ym kl´ıˇcem jsou body P a Q a soukrom´ym kl´ıˇcem
ˇc´ıslo k.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
ECC
´ kladn´ı ElGamal ˇ
´ n´ı
Algoritmus. Za
sifrova
´
´
ˇ
pomocı eliptickych krivek.
ˇn´ı parametry, ver
ˇejny
´ kl´ıc
ˇ P, Q,
Vstup: Definic
´ va m.
zpra
ˇ
´ zpra
´ va (C1 , C2 ).
´ stup: Sifrovan
Vy
a
1. Vyj´adˇri m jako bod M eliptick´e kˇrivky.
2. Vyber a ∈ [1, n − 1].
3. Spoˇcti C1 = aP.
4. Spoˇcti C2 = M + aQ.
5. Vrat’ (C1 , C2 ).
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
ECC
´ kladn´ı ElGamal deˇ
´ n´ı
Algoritmus. Za
sifrova
´
´
ˇ
pomocı eliptickych krivek.
ˇn´ı parametry, ver
ˇejny
´ kl´ıc
ˇ P, Q,
Vstup: Definic
´ kl´ıc
ˇ k, ˇ
´ zpra
´ va (C1 , C2 ).
soukromy
sifrovana
´ stup: Zpra
´ va m.
Vy
1. Spoˇcti M = C2 − kC1 .
2. Pˇreved’ M na m.
3. Vrat’ m.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
HECC
Zobecnˇen´ım eliptick´ych kˇrivek jsou tzv. hypereliptick´e
kˇrivky. Hypereliptickou kˇrivkou C rodu g nad polem F
rozum´ıme algebraickou kˇrivku
y 2 + h(x)y = f (x),
kde h(x) je polynom stupnˇe nejv´yˇse g a f (x) polynom
stupnˇe 2g + 1 (plus dalˇs´ı podm´ınky).
Tzn. eliptick´e kˇrivky jsou hypereliptick´ymi kˇrivkami s g = 1.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
´
Uvod
do ECC
Vizualizace eliptick´
ych kˇrivek nad koneˇ
cn´
ymi poli
ˇ ad eliptick´
R´
e kˇrivky
Hypereliptick´
e kˇrivky
HECC
Roli bod˚
u v hypereliptick´e kryptografii hraj´ı tˇr´ıdy
ekvivalence divizor˚
u (divizor je form´aln´ım souˇctem bod˚
u
hypereliptick´e kˇrivky); na tˇechto tˇr´ıd´ach lze opˇet zav´est
grupovou operaci. Prakticky se to prov´ad´ı tak, ˇze se
vyuˇzuje toho, ˇze kaˇzd´a tˇr´ıda m´a jednoznaˇcn´eho
reprezentanta, tzv. redukovan´y divizor a operace souˇctu se
realizuje na tˇechto redukovan´ych divizorech.
N´aroˇcn´e matematick´e pozad´ı (algebraick´a geometrie),
experimenty pˇrev´aˇznˇe jen s kˇrivkami s g = 2.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Z´
avˇ
ereˇ
cn´
e pr´
ace
Uvedeme pr´ace student˚
u FSI veden´e autorem, kter´e souvis´ı
s asymetrickou kryptografi´ı:
Trchal´ıkov´a, J., Algoritmy pro urˇcen´ı ˇr´adu eliptick´e
kˇrivky s vyuˇzit´ım v kryptografii, 2008
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Z´
avˇ
ereˇ
cn´
e pr´
ace
Uvedeme pr´ace student˚
u FSI veden´e autorem, kter´e souvis´ı
s asymetrickou kryptografi´ı:
Trchal´ıkov´a, J., Algoritmy pro urˇcen´ı ˇr´adu eliptick´e
kˇrivky s vyuˇzit´ım v kryptografii, 2008
Zav´ıralov´a, L., Okruhy endomorfism˚
u eliptick´ych
kˇrivek a Mestreho teor´em, 2009
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Z´
avˇ
ereˇ
cn´
e pr´
ace
Uvedeme pr´ace student˚
u FSI veden´e autorem, kter´e souvis´ı
s asymetrickou kryptografi´ı:
Trchal´ıkov´a, J., Algoritmy pro urˇcen´ı ˇr´adu eliptick´e
kˇrivky s vyuˇzit´ım v kryptografii, 2008
Zav´ıralov´a, L., Okruhy endomorfism˚
u eliptick´ych
kˇrivek a Mestreho teor´em, 2009
Perzynov´a, K., Hypereliptick´e kˇrivky a jejich aplikace v
kryptografii, 2010
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Z´
avˇ
ereˇ
cn´
e pr´
ace
Uvedeme pr´ace student˚
u FSI veden´e autorem, kter´e souvis´ı
s asymetrickou kryptografi´ı:
Trchal´ıkov´a, J., Algoritmy pro urˇcen´ı ˇr´adu eliptick´e
kˇrivky s vyuˇzit´ım v kryptografii, 2008
Zav´ıralov´a, L., Okruhy endomorfism˚
u eliptick´ych
kˇrivek a Mestreho teor´em, 2009
Perzynov´a, K., Hypereliptick´e kˇrivky a jejich aplikace v
kryptografii, 2010
Bajko, J., Transfer elitptick´ych kˇrivek na torus, 2011?
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Z´
avˇ
ereˇ
cn´
e pr´
ace
Uvedeme pr´ace student˚
u FSI veden´e autorem, kter´e souvis´ı
s asymetrickou kryptografi´ı:
Trchal´ıkov´a, J., Algoritmy pro urˇcen´ı ˇr´adu eliptick´e
kˇrivky s vyuˇzit´ım v kryptografii, 2008
Zav´ıralov´a, L., Okruhy endomorfism˚
u eliptick´ych
kˇrivek a Mestreho teor´em, 2009
Perzynov´a, K., Hypereliptick´e kˇrivky a jejich aplikace v
kryptografii, 2010
Bajko, J., Transfer elitptick´ych kˇrivek na torus, 2011?
Havl´ıˇckov´a, A., Algoritmy interpolace polynomy v´ıce
neurˇcit´ych, 2011?
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Z´
avˇ
ereˇ
cn´
e pr´
ace
Uvedeme pr´ace student˚
u FSI veden´e autorem, kter´e souvis´ı
s asymetrickou kryptografi´ı:
Trchal´ıkov´a, J., Algoritmy pro urˇcen´ı ˇr´adu eliptick´e
kˇrivky s vyuˇzit´ım v kryptografii, 2008
Zav´ıralov´a, L., Okruhy endomorfism˚
u eliptick´ych
kˇrivek a Mestreho teor´em, 2009
Perzynov´a, K., Hypereliptick´e kˇrivky a jejich aplikace v
kryptografii, 2010
Bajko, J., Transfer elitptick´ych kˇrivek na torus, 2011?
Havl´ıˇckov´a, A., Algoritmy interpolace polynomy v´ıce
neurˇcit´ych, 2011?
Navr´atilov´a, B., Kvadratick´e polynomy nad bin´arn´ımi
poli, 2011?
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
AMathNet
V r´amci s´ıtˇe AMathNet pl´anujeme st´aˇze student˚
u na
pracoviˇstˇe zab´yvaj´ıc´ı se teori´ı ˇ
c´ısel, kter´a ve studijn´ıch
programech student˚
u FSI chyb´ı. M˚
uˇze to b´yt napˇr.
Ostravsk´a univerzita.
Miroslav Kureˇs
Kˇrivky a kryptografie
Kˇrivky
Asymetrick´
a kryptografie
ECC (& HECC)
´ FSI VUT v Brnˇ
Eliptick´
e kˇrivky na UM
e
Souˇ
casnost
ID-kryprosyst´em BLMQ zaloˇzen´y na Sakaiovˇe-Kasaharovˇe
konstrukci vyuˇz´ıvaj´ıc´ı Weilovo p´arov´an´ı bod˚
u P, Q torzn´ı
podgrupy eliptick´e kˇrivky.
(V r´amci spolupr´ace s LEADict Group.)
Miroslav Kureˇs
Kˇrivky a kryptografie
Download

Krivky a kryptografie