SmartCard Forum 2010 - základní principy nesymetrické kryptografie s eliptickými křivkami
•
0 likes•518 views
![Souřadnice bodu R = P + Q
Souřadnice součtu bodů R = P + Q získáme jako (třetí) průsečík
přímky procházející body P a Q (ležícími na křivce) a eliptické
křivky, s tím, že y souřadnici změníme znaménko.
P = [x1,y1]; Q = [x2,y2]; R = [x3,-y3]
Rovnice přímky, procházející body P, Q:
y - y1 = (y2 - y1)/(x2 - x1) * (x - x1)
Ve směrnicovém tvaru y = s*x + q,
je směrnice: s = (y2 - y1)/(x2 - x1)
a posunutí v ose y: q = y1 – s*x1](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-6-320.jpg)
![Eliptická křivka nad GF(p)
Eliptická křivka E nad tělesem GF(p) je definována jako bod v
nekonečnu (nulový bod) [BvN] společně s množinou bodů
P = (x, y),
kde x a y jsou z tělesa GF(p) a splňují rovnici:
y2 = x3 + ax + b v GF(p), tj.
y2 ≡ x3 + ax + b (mod p).
Řádem křivky #E rozumíme počet bodů křivky E](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-19-320.jpg)
![Příklad eliptické křivky nad GF(23)
Křivka E: y2 = x3 + x + 1 nad tělesem F(23) – 529 bodů
Řád křivky (počet bodů na křivce): 28
Body na křivce E:
[4,0] [0,1] [11,3] [17,3] [18,3] [5,4] [6,4] [12,4] [19,5] [1,7] [9,7]
[13,7] [3,10] [7,11] [7,12] [3,13] [1,16] [9,16] [13,16] [19,18] [5,19]
[6,19] [12,19] [11,20] [17,20] [18,20] [0,22] [BvN]
Ověření, že bod [11,3] leží na křivce E:
[11,3]: 32 ≡ 113 + 11 +1 (mod 23)
9 ≡ 1331 + 11 + 1 (mod 23)
9 ≡ 20 + 11 + 1 ≡ 32 ≡ 9 (mod 23)](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-20-320.jpg)
![Sčítání bodů ležících na eliptické křivce
R = P + Q; P = [x1,y1], Q = [x2,y2], R = [x3,-y3]
s ≡ (y2 - y1)*(x2 - x1)-1 (mod p) pro P ≠ Q
s ≡ (3x12 + a)*(2y1)-1 (mod p) pro P = Q
q ≡ y1 - s*x1 (mod p)
x3 ≡ s2 - x1 - x2 (mod p) pro P ≠ Q
x3 ≡ s2 - 2x1 (mod p) pro P = Q
y3 ≡ s*x3 + q (mod p)
Eliptická křivka je vzhledem k sčítání bodů komutativní
(Abelova) grupa
22](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-22-320.jpg)
![s ≡ (y2 - y1)/(x2 - x1) (mod p)
Příklad sčítání bodů q ≡ y1 - s*x1 (mod p)
x3 ≡ s2 - x1 - x2 (mod p)
y3 ≡ s*x3 + q (mod p)
R = P+Q,
P[x1,y1] = [11,3], Q[x2,y2] = [3,13]
s ≡ (13-3)/(3-11) ≡ (13+20)*(3+12)-1 ≡ 33*15-1 ≡ 10*20 ≡ 200 ≡ 16
(mod 23)
q ≡ 3 -16*11 ≡ 3-176 ≡ 3-15 ≡ 3+8 ≡ 11 (mod 23)
x3 ≡ 162-11-3 ≡ 256+12+20 ≡ 3+12+20 ≡ 35 ≡ 12 (mod 23)
y3 ≡ 16*12 +11 ≡ 192+11 ≡ 8+11 ≡ 19 (mod 23)
-y3 ≡ (-19) ≡ 4
R [x3,-y3] = [11,3] + [3,13] = [12,4]](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-23-320.jpg)
![Příklad sčítání bodů – grafické znázornění
R = [11,3] + [3,13]
= [12,4]](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-24-320.jpg)
![Násobení bodu přirozeným číslem
Násobení bodu přirozeným číslem je zjednodušený zápis pro
opakované sčítání bodů:
n*P = nP = P+P....+P (n krát).
Důležitý je dvojnásobek bodu P+P, pomocí kterého se výhodně
konstruují vyšší násobky, například:
200P = 2(2(2(P+2(2(2(P+2P)))))), tedy stačí pouze 9 operací sčítání.
Řádem bodu #P rozumíme nejmenší násobek bodu P, kdy platí
nP=[BvN].
Po n sčítáních bodu se dostaneme do bodu [BvN]. Protože [BvN] +P=P,
po n+1 sečteních bodu s vrátíme do původního bodu P a při dalším
přičítání P se posloupnost bodů opakuje.
Platí, že řád bodu dělí řád křivky.
Různé body na křivce mohou být různého řádu.
„Nejzajímavější“ jsou body s vysokým řádem
#E/#P se nazývá kofaktor](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-25-320.jpg)
![Příklad 2 násobku bodu s ≡ (3*x12+a)/(2*y1) (mod p)
q ≡ y1 – s*x1 (mod p)
x3 ≡ s2– 2*x1 (mod p)
y3 ≡ s*x3 + q (mod p)
Bod na P = [5,4] na křivce y2 = x3 + x + 1
s = (3*5*5+1)/(2*4) = 76/8 ≡ 7*3 = 21
q = 4 – 21*5 = 4 – 105 = 4 – 13 = 4 + 10 = 14
x3 = 21*21-2*5 = 441-10 ≡ 4+13 = 17
y3 = 21*17 + 14 = 357+14 = 12+14 = 3
-y3 = (-3) = 20
2P = [17,20]](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-26-320.jpg)
![Příklad k-násobek bodu
Bod na P = [5,4] na křivce y2 = x3 + x + 1 má řád 7, jeho k
násobky jsou:
2 * [5,4] = [5,4] + [5,4] = [17,20]
3 * [5,4] = 2 * [5,4] + [5,4] = [17,20] + [5,4] = [13,16]
4 * [5,4] = 3 * [5,4] + [5,4] = [13,16] + [5,4] = [13,7]
5 * [5,4] = [13,7] + [5,4] = [17,3]
6 * [5,4] = [17,3] + [5,4] = [5,19]
7 * [5,4] = [5,19] + [5,4] = [BvN] bod v nekonečnu
8 * [5,4] = [BvN] + [5,4] = [5,4]
9 * [5,4] = [5,4] + [5,4] = [17,20] ....](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-27-320.jpg)
![Eliptická křivka y2 = x3 + x + 1 nad F(23) Násobky bodu [9,7]
Příklad ECDH
B=[9,7]
Počáteční bod B:[9,7] , řád bodu je 28 2B=[6,19]
3B=[1,7]
4B=[13,16]
5B=[19,5]
6B=[7,11]
7B=[11,20]
Počáteční 8B=[5,19]
9B=[18,20]
bod B 10B=[12,4]
11B=[3,10]
12B=[17,20]
13B=[0,22]
14B=[4,0]
15B=[0,1]
16B=[17,3]
17B=[3,13]
18B=[12,19]
19B=[18,3]
20B=[5,4]
21B=[11,3]
22B=[7,12]
23B=[19,18]
24B=[13,7]
25B=[1,16]
26B=[6,4]
27B=[9,16]
28B=[BvN]
29B=[9,7]](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-32-320.jpg)
![B=[9,7] QA=[1,7] QB=[11,20]
Příklad ECDH 2B=[6,19]
3B=[1,7]
2QA=[7,11]
3QA=[18,20]
2QB=[4,0]
3QB=[11,3]
4B=[13,16] 4QA=[17,20] 4QB=[BvN]
Eliptická křivka y2 = x3 + x + 1 nad F(23) 5B=[19,5]
6B=[7,11]
5QA=[0,1]
6QA=[12,19]
Počáteční bod B:[9,7] , řád bodu je 28 7B=[11,20] 7QA=[11,3]
8B=[5,19] 8QA=[13,7]
9B=[18,20] 9QA=[9,16]
kA: privátní klíč Alice = 3 10B=[12,4]
11B=[3,10]
10QA=[6,19]
11QA=[19,5]
kB: privátní klíč Boba = 7 12B=[17,20] 12QA=[5,19]
13B=[0,22] 13QA=[3,10]
QA=kAB: veřejný bod (klíč) Alice = 3B = [1,7] 14B=[4,0] 14QA=[4,0]
15B=[0,1] 15QA=[3,13]
QB=kBB: veřejný bod (klíč) Boba = 7B = [11,20] 16B=[17,3] 16QA=[5,4]
17B=[3,13] 17QA=[19,18]
18B=[12,19] 18QA=[6,4]
Bob spočte Z = kBQA = 7* [1,7] = [11,3] 19B=[18,3]
20B=[5,4]
19QA=[9,7]
20QA=[13,16]
Alice spočte Z = kAQB = 3* [11,20] = [11,3] 21B=[11,3] 21QA=[11,20]
22B=[7,12] 22QA=[12,4]
23B=[19,18] 23QA=[0,22]
24B=[13,7] 24QA=[17,3]
Souřadnice bodu Z mohou sloužit jako sdílené 25B=[1,16] 25QA=[18,3]
tajemství Alice a Boba 26B=[6,4]
27B=[9,16]
26QA=[7,12]
27QA=[1,16]
28B=[BvN] 28QA=[BvN]](https://image.slidesharecdn.com/10ivorosol-zkladnprincipynesymetrickkryptografieseliptickmikivkami-scf2010-130201092405-phpapp01/85/SmartCard-Forum-2010-zakladni-principy-nesymetricke-kryptografie-s-eliptickymi-krivkami-33-320.jpg)
SmartCard Forum 2010 - základní principy nesymetrické kryptografie s eliptickými křivkami
- 1. Nesymetrická kryptografie s eliptickými křivkami Základní principy Ivo Rosol ředitel vývojové divize 20. 5. 2010 Spojujeme software, technologie a služby 1
- 2. Eliptická křivka v rovině Eliptická křivka je množina bodů (x,y), které vyhovují rovnici: y2 = x3 + ax + b x, y, a, b jsou reálná čísla
- 5. Sčítání bodů na eliptické křivce
- 6. Souřadnice bodu R = P + Q Souřadnice součtu bodů R = P + Q získáme jako (třetí) průsečík přímky procházející body P a Q (ležícími na křivce) a eliptické křivky, s tím, že y souřadnici změníme znaménko. P = [x1,y1]; Q = [x2,y2]; R = [x3,-y3] Rovnice přímky, procházející body P, Q: y - y1 = (y2 - y1)/(x2 - x1) * (x - x1) Ve směrnicovém tvaru y = s*x + q, je směrnice: s = (y2 - y1)/(x2 - x1) a posunutí v ose y: q = y1 – s*x1
- 7. Souřadnice bodu R = P + Q Bod přímky (x,y) = (x, s*x+q) leží na křivce, pokud: (s*x+q)2 = x3+a*x+b, po úpravě: x3-s2*x2+(a-2*s*q)*x+b-q2 = 0 Dva kořeny x1 a x2 (x-ové souřadnice bodů P a Q) této kubické rovnice jsou známy, hledáme třetí kořen x3. Vyjádříme normovaný polynom 3. stupně ve tvaru rozkladu na kořenové činitele: (x-x1)*(x-x2)(x-x3) = 0 x3 - (x1+x2+x3)x2 + (x1x2 +x1x3 +x2x3)x - x1x2 x3 =0 Porovnáním koeficientů u x2: x1+x2+x3 = s2, tedy: x3 = s2 - x1-x2 , souřadnice y3 se získá z rovnice přímky: y3 = s*x3 + q R = (x3, -y3)
- 8. Souřadnice bodu R = P + P V případě kdy P=Q je R=P+P, což lze zapsat R = 2*P, je přímka tečnou eliptické křivky v bodě P, její směrnice je rovna derivaci (implicitní funkce) dy/dx: y2 = x3 + ax + b 2*y*dy/dx = 3x2 + a dy/dx = (3x2 + a)/2*y, v bodě P = (x1,y1) je směrnice s: (3x12 + a)/2*y1 x3 = s2 – 2*x1 y3 = s*x3 + q R = (x3, -y3)
- 9. Těleso (pole) V kryptografii nelze počítat s reálnými čísly, operace musí být přesné (bez zaokrouhlování a iracionálních čísel), prováděné s celými čísly. V počítači je navíc nutno pracovat s celými čísly s omezenou velikostí. Při výpočtech souřadnic bodů na eliptických křivkách potřebujeme sčítat, odečítat, násobit a dělit (nenulovým prvkem). Algebraická struktura s těmito operacemi se nazývá těleso (pole). Těleso reálných čísel s běžnými operacemi sčítání, odečítání, násobení a dělení nahradíme tělesem s konečným počtem prvků {0,1,2,...p-1}, kde p je prvočíslo a výpočetní operace se provádějí modulo p
- 10. Operace nad tělesem F(p) Mějme číslo p, pak množina prvků F = (0;1;2;3; ... p-1) se dvěma operacemi sčítání + a násobení *, která pro všechna a;b;c z F splňuje následující podmínky: 1. a+(b+c) = (a+b)+c (asociativní pro +) 2. existuje 0 tak, že a + 0 = 0 + a = a (nulový prvek) 3. pro všechny a z F existuje (-a) tak, že a+(-a) = (-a)+a = 0 (opačný prvek) 4. a+b = b+a (komutativní) 5. (a*b)*c = a*(b*c) (asociativní pro *) 6. (a+b)*c = a*c+b*c ; c*(a+b) = c*a+c*b (distributivní) 7. Existuje 1 tak, že a * 1 = 1 * a = a (jednotkový prvek) 8. pro všechna a z F existuje a-1 tak, že a*a-1 = a-1*a = 1 (inverzní prvek) se nazývá (konečné) Galloisovo těleso GF(p)
- 11. Prvočíselné těleso F(23) Těleso F(p), kde p je prvočíslo, má prvky F = { 0;1;2;3; ... p-1 } Pokud by p nebylo prvočíslo, neexistoval by pro každé a inverzní prvek a-1 Na rozdíl od běžných aritmetických operací se zde po každé operaci provede celočíselné dělení modulem p a výsledkem operace je zbytek po tomto dělení. Příklad: Těleso F(23): {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22} Operace sčítání: (a+b) mod p 15 + 9 = 24 = 1 (mod 23) Operace odečítání: (a + (-b)) mod p 6 – 11 = 6 + 12 = 18 (mod 23) Operace násobení: (a*b) mod p 5 * 12 = 60 = 14 (mod 23) Operace dělení: (a*b-1) mod p 8 / 14 = 8 * 5 = 40 = 17 (mod 23)
- 12. Sčítací tabulka pro F(23) + 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 3 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 4 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 5 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 6 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 7 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 8 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 9 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 10 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 11 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 12 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 13 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 14 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 21 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
- 13. Odečítání „Odečítání“ je zjednodušený zápis pro přičítání aditivního inverzního („záporného“) prvku. (a – b) → (a + (-b)) mod p, Kde b + (-b) ≡ 0 mod p
- 14. Aditivní inverzní prvek Prvek F(23) Inverzní prvek (mod 23) 0 0 1 22 (-1) 2 21 (-2) Snadné ověření: 3 20 (-3) 4 19 (-4) (3 + 20) mod 23 ≡ 0 5 18 (-5) 6 17 (-6) Příklad odečítání: 7 16 (-7) 8 15 (-8) 9 + (–15) mod 23 ≡ 9 14 (-9) 10 13 (-10) 9 + 8 mod 23 ≡ 17 11 12 (-11) 12 11 (-12) Zjednodušený zápis: 13 10(-13) 14 9(-14) 9 - 15 mod 23 ≡ 17 15 8 (-15) 16 7 (-16) 17 6 (-17) 18 5 (-18) 19 4 (-19) 20 3 (-20) 21 2 (-21) 22 1 (-22)
- 15. Násobící tabulka pro F(23) * 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2 0 2 4 6 8 10 12 14 16 18 20 22 1 3 5 7 9 11 13 15 17 19 21 3 0 3 6 9 12 15 18 21 1 4 7 10 13 16 19 22 2 5 8 11 14 17 20 4 0 4 8 12 16 20 1 5 9 13 17 21 2 6 10 14 18 22 3 7 11 15 19 5 0 5 10 15 20 2 7 12 17 22 4 9 14 19 1 6 11 16 21 3 8 13 18 6 0 6 12 18 1 7 13 19 2 8 14 20 3 9 15 21 4 10 16 22 5 11 17 7 0 7 14 21 5 12 19 3 10 17 1 8 15 22 6 13 20 4 11 18 2 9 16 8 0 8 16 1 9 17 2 10 18 3 11 19 4 12 20 5 13 21 6 14 22 7 15 9 0 9 18 4 13 22 8 17 3 12 21 7 16 2 11 20 6 15 1 10 19 5 14 10 0 10 20 7 17 4 14 1 11 21 8 18 5 15 2 12 22 9 19 6 16 3 13 11 0 11 22 10 21 9 20 8 19 7 18 6 17 5 16 4 15 3 14 2 13 1 12 12 0 12 1 13 2 14 3 15 4 16 5 17 6 18 7 19 8 20 9 21 10 22 11 13 0 13 3 16 6 19 9 22 12 2 15 5 18 8 21 11 1 14 4 17 7 20 10 14 0 14 5 19 10 1 15 6 20 11 2 16 7 21 12 3 17 8 22 13 4 18 9 15 0 15 7 22 14 6 21 13 5 20 12 4 19 11 3 18 10 2 17 9 1 16 8 16 0 16 9 2 18 11 4 20 13 6 22 15 8 1 17 10 3 19 12 5 21 14 7 17 0 17 11 5 22 16 10 4 21 15 9 3 20 14 8 2 19 13 7 1 18 12 6 18 0 18 13 8 3 21 16 11 6 1 19 14 9 4 22 17 12 7 2 20 15 10 5 19 0 19 15 11 7 3 22 18 14 10 6 2 21 17 13 9 5 1 20 16 12 8 4 20 0 20 17 14 11 8 5 2 22 19 16 13 10 7 4 1 21 18 15 12 9 6 3 21 0 21 19 17 15 13 11 9 7 5 3 1 22 20 18 16 14 12 10 8 6 4 2 22 0 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
- 16. Dělení „Dělení“ je zjednodušený zápis pro násobení multiplikativním inverzním prvkem: a/b → (a * b-1) mod p Kde b * b-1 ≡ 1 mod p Opakování – v GF(p): Existuje 1 tak, že: a * 1 = 1 * a = a (jednotkový prvek) pro všechna a z F existuje a-1 tak, že: a*a-1 = a-1*a = 1 (inverzní prvek)
- 17. Multiplikativní inverzní prvek Malý Fermatův teorém: Pokud p je prvočíslo, a je celé číslo, pak platí ap ≡ a mod p pokud a není dělitelné p (například když 0 ≤ a < p) ap-1 ≡ 1 mod p Inverzní prvek v F(p) lze nalézt pomocí: ap-1= a*ap-2 ≡ 1 mod p tedy a-1 ≡ ap-2 mod p
- 18. Multiplikativní inverzní prvek Prvek F(23) * Inverzní prvek (mod 23) Příklad: 0 neexistuje 1 1 (3-1) mod 23 = 8, neboť 2 12 3 8 (3 * 8) mod 23 = 24 mod 23 = 1 4 6 5 14 1 je jednotkový prvek v F(23) 6 4 7 10 8 3 9 18 10 7 11 21 12 2 13 16 14 5 15 20 16 13 17 19 18 9 19 17 20 15 21 11 22 22
- 19. Eliptická křivka nad GF(p) Eliptická křivka E nad tělesem GF(p) je definována jako bod v nekonečnu (nulový bod) [BvN] společně s množinou bodů P = (x, y), kde x a y jsou z tělesa GF(p) a splňují rovnici: y2 = x3 + ax + b v GF(p), tj. y2 ≡ x3 + ax + b (mod p). Řádem křivky #E rozumíme počet bodů křivky E
- 20. Příklad eliptické křivky nad GF(23) Křivka E: y2 = x3 + x + 1 nad tělesem F(23) – 529 bodů Řád křivky (počet bodů na křivce): 28 Body na křivce E: [4,0] [0,1] [11,3] [17,3] [18,3] [5,4] [6,4] [12,4] [19,5] [1,7] [9,7] [13,7] [3,10] [7,11] [7,12] [3,13] [1,16] [9,16] [13,16] [19,18] [5,19] [6,19] [12,19] [11,20] [17,20] [18,20] [0,22] [BvN] Ověření, že bod [11,3] leží na křivce E: [11,3]: 32 ≡ 113 + 11 +1 (mod 23) 9 ≡ 1331 + 11 + 1 (mod 23) 9 ≡ 20 + 11 + 1 ≡ 32 ≡ 9 (mod 23)
- 21. Graf všech bodů křivky y2 = x3 + x + 1 nad F(23)
- 22. Sčítání bodů ležících na eliptické křivce R = P + Q; P = [x1,y1], Q = [x2,y2], R = [x3,-y3] s ≡ (y2 - y1)*(x2 - x1)-1 (mod p) pro P ≠ Q s ≡ (3x12 + a)*(2y1)-1 (mod p) pro P = Q q ≡ y1 - s*x1 (mod p) x3 ≡ s2 - x1 - x2 (mod p) pro P ≠ Q x3 ≡ s2 - 2x1 (mod p) pro P = Q y3 ≡ s*x3 + q (mod p) Eliptická křivka je vzhledem k sčítání bodů komutativní (Abelova) grupa 22
- 23. s ≡ (y2 - y1)/(x2 - x1) (mod p) Příklad sčítání bodů q ≡ y1 - s*x1 (mod p) x3 ≡ s2 - x1 - x2 (mod p) y3 ≡ s*x3 + q (mod p) R = P+Q, P[x1,y1] = [11,3], Q[x2,y2] = [3,13] s ≡ (13-3)/(3-11) ≡ (13+20)*(3+12)-1 ≡ 33*15-1 ≡ 10*20 ≡ 200 ≡ 16 (mod 23) q ≡ 3 -16*11 ≡ 3-176 ≡ 3-15 ≡ 3+8 ≡ 11 (mod 23) x3 ≡ 162-11-3 ≡ 256+12+20 ≡ 3+12+20 ≡ 35 ≡ 12 (mod 23) y3 ≡ 16*12 +11 ≡ 192+11 ≡ 8+11 ≡ 19 (mod 23) -y3 ≡ (-19) ≡ 4 R [x3,-y3] = [11,3] + [3,13] = [12,4]
- 24. Příklad sčítání bodů – grafické znázornění R = [11,3] + [3,13] = [12,4]
- 25. Násobení bodu přirozeným číslem Násobení bodu přirozeným číslem je zjednodušený zápis pro opakované sčítání bodů: n*P = nP = P+P....+P (n krát). Důležitý je dvojnásobek bodu P+P, pomocí kterého se výhodně konstruují vyšší násobky, například: 200P = 2(2(2(P+2(2(2(P+2P)))))), tedy stačí pouze 9 operací sčítání. Řádem bodu #P rozumíme nejmenší násobek bodu P, kdy platí nP=[BvN]. Po n sčítáních bodu se dostaneme do bodu [BvN]. Protože [BvN] +P=P, po n+1 sečteních bodu s vrátíme do původního bodu P a při dalším přičítání P se posloupnost bodů opakuje. Platí, že řád bodu dělí řád křivky. Různé body na křivce mohou být různého řádu. „Nejzajímavější“ jsou body s vysokým řádem #E/#P se nazývá kofaktor
- 26. Příklad 2 násobku bodu s ≡ (3*x12+a)/(2*y1) (mod p) q ≡ y1 – s*x1 (mod p) x3 ≡ s2– 2*x1 (mod p) y3 ≡ s*x3 + q (mod p) Bod na P = [5,4] na křivce y2 = x3 + x + 1 s = (3*5*5+1)/(2*4) = 76/8 ≡ 7*3 = 21 q = 4 – 21*5 = 4 – 105 = 4 – 13 = 4 + 10 = 14 x3 = 21*21-2*5 = 441-10 ≡ 4+13 = 17 y3 = 21*17 + 14 = 357+14 = 12+14 = 3 -y3 = (-3) = 20 2P = [17,20]
- 27. Příklad k-násobek bodu Bod na P = [5,4] na křivce y2 = x3 + x + 1 má řád 7, jeho k násobky jsou: 2 * [5,4] = [5,4] + [5,4] = [17,20] 3 * [5,4] = 2 * [5,4] + [5,4] = [17,20] + [5,4] = [13,16] 4 * [5,4] = 3 * [5,4] + [5,4] = [13,16] + [5,4] = [13,7] 5 * [5,4] = [13,7] + [5,4] = [17,3] 6 * [5,4] = [17,3] + [5,4] = [5,19] 7 * [5,4] = [5,19] + [5,4] = [BvN] bod v nekonečnu 8 * [5,4] = [BvN] + [5,4] = [5,4] 9 * [5,4] = [5,4] + [5,4] = [17,20] ....
- 29. Problém diskrétního logaritmu nad E v F(p) Pokud je řád bodu #P velký (například 2256), je velká posloupnost různých bodů P,2P,3P,..., aniž dojde k zacyklení. Lze zvolit počáteční bod P, tajný násobitel k a vypočítat cílový bod Q=kP. Oba body P i Q lze zveřejnit, nikdo není (v rozumné době) schopen z těchto bodů určit násobitel k (jeho určení tvoří tzv. problém diskrétního logaritmu).
- 30. Kryptografie s veřejným klíčem nad E v F(p) Popis eliptické křivky y2 = x3 + ax + b (tedy koeficienty a,b a modul tělesa p), počáteční bod B, řád křivky #E a kofaktor tvoří veřejné parametry kryptografie. Tajný násobitel k tvoří privátní klíč subjektu. Koncový bod Q=kB tvoří veřejný klíč subjektu.
- 31. Algoritmus ECDH pro nalezení shody na klíči B: základní bod kA: privátní klíč Alice; QA=kAB: veřejný bod (klíč) Alice kB: privátní klíč Boba; QB=kBB: veřejný bod (klíč) Boba Společný bod Z spočtou obě strany následovně: Alice: Z = kAQB = kAkBB Bob: Z = kBQA = kBkAB Společný bod Z slouží k odvození klíčů relace (například z X souřadnice bodu Z se odvodí sdílený symetrický klíč relace mezi Alicí a Bobem)
- 32. Eliptická křivka y2 = x3 + x + 1 nad F(23) Násobky bodu [9,7] Příklad ECDH B=[9,7] Počáteční bod B:[9,7] , řád bodu je 28 2B=[6,19] 3B=[1,7] 4B=[13,16] 5B=[19,5] 6B=[7,11] 7B=[11,20] Počáteční 8B=[5,19] 9B=[18,20] bod B 10B=[12,4] 11B=[3,10] 12B=[17,20] 13B=[0,22] 14B=[4,0] 15B=[0,1] 16B=[17,3] 17B=[3,13] 18B=[12,19] 19B=[18,3] 20B=[5,4] 21B=[11,3] 22B=[7,12] 23B=[19,18] 24B=[13,7] 25B=[1,16] 26B=[6,4] 27B=[9,16] 28B=[BvN] 29B=[9,7]
- 33. B=[9,7] QA=[1,7] QB=[11,20] Příklad ECDH 2B=[6,19] 3B=[1,7] 2QA=[7,11] 3QA=[18,20] 2QB=[4,0] 3QB=[11,3] 4B=[13,16] 4QA=[17,20] 4QB=[BvN] Eliptická křivka y2 = x3 + x + 1 nad F(23) 5B=[19,5] 6B=[7,11] 5QA=[0,1] 6QA=[12,19] Počáteční bod B:[9,7] , řád bodu je 28 7B=[11,20] 7QA=[11,3] 8B=[5,19] 8QA=[13,7] 9B=[18,20] 9QA=[9,16] kA: privátní klíč Alice = 3 10B=[12,4] 11B=[3,10] 10QA=[6,19] 11QA=[19,5] kB: privátní klíč Boba = 7 12B=[17,20] 12QA=[5,19] 13B=[0,22] 13QA=[3,10] QA=kAB: veřejný bod (klíč) Alice = 3B = [1,7] 14B=[4,0] 14QA=[4,0] 15B=[0,1] 15QA=[3,13] QB=kBB: veřejný bod (klíč) Boba = 7B = [11,20] 16B=[17,3] 16QA=[5,4] 17B=[3,13] 17QA=[19,18] 18B=[12,19] 18QA=[6,4] Bob spočte Z = kBQA = 7* [1,7] = [11,3] 19B=[18,3] 20B=[5,4] 19QA=[9,7] 20QA=[13,16] Alice spočte Z = kAQB = 3* [11,20] = [11,3] 21B=[11,3] 21QA=[11,20] 22B=[7,12] 22QA=[12,4] 23B=[19,18] 23QA=[0,22] 24B=[13,7] 24QA=[17,3] Souřadnice bodu Z mohou sloužit jako sdílené 25B=[1,16] 25QA=[18,3] tajemství Alice a Boba 26B=[6,4] 27B=[9,16] 26QA=[7,12] 27QA=[1,16] 28B=[BvN] 28QA=[BvN]
- 34. Příklad ECDH – grafické znázornění Veřejný bod Boba QB= 7*B Společný počáteční bod B Veřejný bod Alice QA= 3*B Společný koncový bod 21*B = 3*7*B = 7*3*B
- 35. Šifrování s veřejným klíčem Algoritmus ElGamal: Zprávu m, která se má zašifrovat, je nutno nejprve vhodně zobrazit (mapovat) na bod na křivce E B: základní bod kA: privátní klíč Alice; QA=kAB: veřejný bod (klíč) Alice kB: privátní klíč Boba; QB=kBB: veřejný bod (klíč) Boba m: zpráva k zašifrování; Pm: bod, na který je zobrazena zpráva m Alice pošle Bobovi bod S, spočtený jako součet bodu zprávy s veřejným bodem Boba vynásobeným privátním klíčem Alice: S = Pm+ kAQB= Pm+ kAkBB Bob vynásobí svým privátním klíčem veřejný bod Alice: R = kBQA= kBkAB a výsledný bod R odečte od bodu S, který obdržel od Alice: S – R = Pm+ kAkBB – kBkAB = Pm Tímto způsobem Bob rozšifroval bod zprávy Pm od Alice
- 36. Elektronický podpis ECDSA Necháme na příště.... Smart Card Forum 2011
- 37. Dotazy, kontakt Ing. Ivo Rosol, CSc. ředitel vývojové divize OKsystem s.r.o. www.oksystem.cz rosol@oksystem.cz