:00-16:10

Size: px

Start display at page:

Download ":00-16:10"

きみのしんみおか
4 years ago
Views:

1 :00-16:10

2 2 Diffie-Hellman (1976) K K p:, b [1, p 1] Given: p: prime, b [1, p 1], s.t. {b i i [0, p 2]} = {1,..., p 1} a {b i i [0, p 2]} Find: x [0, p 2] s.t. a b x mod p Ind b a := x K a [1, p 1] K a b K a mod p (x, b, p) a b x mod p K a x = (x n x n 1... x 1 x 0 ) 2, a 0 i n b 2xi mod p, K b [1, p 1] K b bk n = O(log p) b mod p K b (a, b, p) x K K K a b mod p K K K b a mod p K

3 4 Square-root Pollard Rho (1978) O(p) Monte Carlo (Las Vegas) Algo. Square-root O ( l ) l p 1 (Adleman, 1979) L x (α, β) := exp ( β(log x) α (log log x) 1 α) O(L p (1/2, 2 + o(1))) O(L p (1/3, o(1))) : O(1) 23 1/ = =

4 Birthday Paradox Pollard ρ S : set, n 0 = #S r 1 : Find: Ind b a i.e. x s.t. a b x mod p ( r n 0 i + 1 r = 1 i 1 ) n 0 i=1 < i=1 r i=1 = exp = exp exp ( n 0 i 1 n x e x r i=1 ( ( i 1 n 0 r(r 1) 2n 0 r2 ) ) ) Given: p = 47, a = 40, b = α β a α b β mod p a 3 b 28 a 39 b 8 mod p exp 2n 0 ( ) a b (8 28)/(3 39) mod p r = 2(log 2)n 0 exp r2 = 0.5 2n 0 O( n 0 ) x mod p 1 6

5 8 Pollard ρ Algorithm 1 Pollard s rho.alpha Input: p:, a, b [1, p 1] Output: x [0, p 2] s.t. a b x mod p 1: i := 0 2: repeat 3: i := i + 1 4: Choose α i, β i [0, p 2] randomly 5: c i a α ib β i mod p 1 6: until j s.t. 1 j < i, c j = c i 7: x (β j β i )(α i α j ) 1 mod p 1 /*α i x + β i α j x + β j mod p 1*/ 8: Output x and terminate : O( p) O ( l ), l p 1 : O( p) O(1) Given: p = 47, a = 40, b = 11 Find: Ind b a i.e. x s.t. a b x mod p T = {2, 3, 5, 7, 11, 13} #T relation Ind Ind Ind Ind Ind Ind Ind Ind Ind Ind 1111 mod p

6 Ind 11 2 Ind 11 3 Ind 11 5 Ind 11 7 Ind Ind Ind 11 2 Ind 11 3 Ind 11 5 Ind 11 7 Ind Ind modp 1 mod p mod p Ind Ind Ind mod p 1 T Key Length (bit) Square-root 10

7 12 p p F p d := {F p d } Square-root log 2 p 160 F p := { p } F 5 = {0, 1, 2, 3, 4} log 2 p 1024 (?) Square-root log 2 p log 2 p

8 14 Given: p:, b [1, p 1], a {b i i [0, p 2]} + F p, (Z, Q, R, C) Find: x [0, p 2] + (N) s.t. a b x mod p F p \{0}, (Q\{0}, R\{0}, C\{0}) (Z) Given: F p : p, b F p, F p := F a b p\{0} Find: x [0, p 2] s.t. a = b x + Given: G:, b G, a b Find: x [0, #G 1] s.t. a = [x]b a = [x]b = b + b + + b }{{} x

9 G = F p Given: b F p, a b Find: x [0, p 1] s.t. a = [x]b #G p 160 bit square-root 4: Choose α i, β i [0, #G 1] randomly x Z/(p 1)Z 5: c i = [α i ]a + [β i ]b x = a/b Z/(p 1)Z 6: 7: until j s.t. 1 j < i, c j = c i x (β j β i )(α i α j ) 1 mod #G T (p) = O((log p) 2 ) bit-operations Pollard ρ Algorithm 2 Pollard s rho.alpha Input: G:,, a, b G Output: x [0, #G 1] s.t. a [x]b 1: i := 0 2: repeat 3: i := i + 1 /*α i x + β i α j x + β j mod #G*/ 8: Output x and terminate : O( #G) O ( l ), l #G : O( #G) O(1) 16

10 18 Square-root : l, l #G C : F (X, Y ) = 0, F (X, Y ) F p G Y 0 X

11 20 E : Y 2 = X 3 + a 4 X + a 6, a i F p E : Y 2 = X 3 + a 4 X + a 6, a i F p Y E(F p ) := {P = (x, y) F 2 p y 2 = x 3 + a 4 x + a 6 } {P } 0 X E(F p ) #E(F p ) p

12 22 1 P 1 + P 2 + P 3 + P 4 + P 5 + P 6 = 0 2 P = (x, y) P = (x, y) U(X)=0 Y Y=V(X) Y P 0 P1 P4 P5 0 X X P2 P3 P6 -P

13 24 P 3 = P 1 + P 2 E : Y 2 = X 3 + a 4 X + a 6 P2 P 1 = (x 1, y 1 ), P 2 = (x 2, y 2 ) Y 0 P1 -P3 P 3 = (x 3, y 3 ) = P 1 + P 2 λ = y 2 y 1 x 2 x if P 1 1 P 2 3x 2 1 +a 4 2x if P 1 1 = P 2 x 3 = λ 2 x 1 x 2, P3 X y 3 = λ(x 1 x 3 ) y 1 I 3M or 4M

14 26 F p : ab : M = O((log p) 2 ) a + b : O(log p) M a 1 : I 20M a : O(1) I + 3M 23M #E(F p ) = O(p) F 2 I + 4M 24M p E(F p ) ? ? ? p 1/5 Square-root E : O ( #E(F p ) ) = O ( ) p F p E(F p) square-root

15 28 g Algorithm 3 C : Y 2 = X 2g+1 +f 2g X 2g + +f 1 X+f 0, Input: p: f i F p Output: A secure elliptic curve E and #E(F p ) 1: repeat 2: repeat 3: Choose an elliptic curve E randmly 4: Compute N = #E(F p ) /* */ 5: until N : prime p 6: until E satisfies MOV condition 7: Output E, #E(F p ) and terminate Y 0 X

16 30 C : Y 2 = X 2g+1 +f 2g X 2g + +f 1 X+f 0, f i F p C : Y 2 = X 2g+1 +f 2g X 2g + +f 1 X+f 0, f i F p C(F p ) := {P = (x, y) F 2 p y2 = x 2g f 0 } {P } C(F p ) J C (F p ) := {D = {P 1,..., P n C(F p g) \ {P }} n g, D p = D} C(F p ) J C (F p ) J C (F p ) #J C (F p ) p g

17 32 (g = 2) D 3 = D 1 + D 2, D i = {P i1, P i2 } Mumford C : Y 2 = F (X), F F p [X], deg F = 2g + 1 Y Y=V(X) D = {P 1,..., P n C(F p g) \ {P }} n g, D p = D, P i = (x i, y i ) -P31 P11 P32 P22 0 P21 P31 X -P32 P12 1 (U, V ) (F p [X]) 2 s.t. U = 1 i n deg U > deg V, (X x i ), U F V 2, y i = V (x i ). J C (F p ) = {(U, V ) (F p [X]) 2 lc(u) = 1, deg V < deg U g, U F V 2 }

18 34 Input Weight two coprime reduced divisors D 1 = (U 1, V 1 ), D 2 = (U 2, V 2 ) Output A weight two reduced divisor D 3 = (U 3, V 3 ) = D 1 + D 2 Step Procedure Cost 1 Compute the resultant r of U 1 and U 2. 4M z 1 u 21 u 11 ; z 2 u 21 z 1 ; z 3 z 2 + u 10 u 20 ; r u 10 (z 3 u 20 ) + u 20 (u 20 u 11 z 1 ); 2 If r = 0 then call the sub procedure. 3 Compute I 1 1/U 1 mod U 2. I + 2M w 0 r 1 ; i 11 w 1 z 1 ; i 10 w 1 z 3 ; 4 Compute S (V 2 V 1 )I 1 mod U 2. (Karatsuba) 5M w 1 v 20 v 10 ; w 2 v 21 v 11 ; w 3 i 10 w 1 ; w 4 i 11 w 2 ; s 1 (i 10 + i 11 )(w 1 + w 2 ) w 3 w 4 (1 + u 21 ); s 0 w 3 u 20 w 4 ; 5 If s 1 = 0 then call the sub procedure. 6 Compute U 3 = s 2 1 ((S2 U 1 + 2SV 1 )/U 2 (F V 2 1 )/(U 1U 2 )). I + 6M w 1 s 1 1 ; u 30 w 1 (w 1 (s u 11 + u 21 f 4 ) + 2(v 11 s 0 w 2 )) + z 2 + u 10 u 20 ; u 31 w 1 (2s 0 w 1 ) w 2 ; u 32 1; 7 Compute V 3 (SU 1 + V 1 ) mod U 3.(Karatsuba) 5M w 1 u 30 u 10 ; w 2 u 31 u 11 ; w 3 s 1 w 2 ; w 4 s 0 w 1 ; w 5 (s 1 + s 0 )(w 1 + w 2 ) w 3 w 4 v 30 w 4 w 3 u 30 v 10 ; v 31 w 5 w 3 u 31 v 11 ; Total 2I + 21M In. Genus 3 HEC C : Y 2 = F (X), F = X 7 + f 5X 5 + f 4X 4 + f 3X 3 + f 2X 2 + f 1X + f 0; Reduced divisors D 1 = (U 1, V 1) and D 2 = (U 2, V 2), U 1 = X 3 + u 12X 2 + u 11X + u 10, V 1 = v 12X 2 + v 11X + v 10, U 2 = X 3 + u 22X 2 + u 21X + u 20, V 2 = v 22X 2 + v 21X + v 20; Out. Reduced divisor D 3 = (U 3, V 3) = D 1 + D 2, U 3 = X 3 + u 32X 2 + u 31X + u 30, V 3 = v 32X 2 + v 31X + v 30; Step Procedure Cost 1 Compute the resultant r of U 1 and U 2 14M + 12A t 1 = u 11u 20 u 10u 21; t 2 = u 12u 20 u 10u 22; t 3 = u 20 u 10; t 4 = u 21 u 11; t 5 = u 22 u 12; t 6 = t 2 4 ; t 7 = t 3t 4; t 8 = u 12u 21 u 11u 22 + t 3; t 9 = t 2 3 t1t5; t10 = t2t5 t7; r = t8t9 + t2(t10 t7) + t1t6; 2 If r = 0 then call the Cantor algorithm 3 Compute the pseudo-inverse I = i 2X 2 + i 1X + i 0 r/u 1 mod U 2 4M + 4A i 2 = t 5t 8 t 6; i 1 = u 22i 2 t 10; i 0 = u 21i 2 (u 22t 10 + t 9); 4 Compute S = s 2 X2 + s 1 X + s 0 = rs (V2 V1)I mod U2 (Karatsuba, Toom) 10M + 31A t 1 = v 10 v 20; t 2 = v 11 v 21; t 3 = v 12 v 22; t 4 = t 2i 1; t 5 = t 1i 0; t 6 = t 3i 2; t 7 = u 22t 6; t 8 = t 4 + t 6 + t 7 (t 2 + t 3)(i 1 + i 2); t 9 = u 20 + u 22; t 10 = (t 9 + u 21)(t 8 t 6); t 9 = (t 9 u 21)(t 8 + t 6); s 0 = (u20t8 + t5); s 2 = t6 (s 0 + t4 + (t1 + t3)(i0 + i2) + (t10 + t9)/2); s 1 = t4 + t5 + (t9 t10)/2 (t7 + (t1 + t2)(i0 + i1)); 5 If s 2 = 0 then call the Cantor algorithm 6 Compute S, w and w i = 1/w s.t. ws = S /r and S is monic I + 7M t 1 = (rs 2 ) 1 ; t 2 = rt 1; w = t 1s 2 2 ; wi = rt2; s0 = t2s 0 ; s1 = t2s 1 ; 7 Compute Z = X 5 + z 4X 4 + z 3X 3 + z 2X 2 + z 1X + z 0 = SU 1 (Toom) 4M + 15A t 6 = s 0 + s 1; t 1 = u 10 + u 12; t 2 = t 6(t 1 + u 11); t 3 = (t 1 u 11)(s 0 s 1); t 4 = u 12s 1; z 0 = u 10s 0; z 1 = (t 2 t 3)/2 t 4; z 2 = (t 2 + t 3)/2 z 0 + u 10; z 3 = u 11 + s 0 + t 4; z 4 = u 12 + s 1; 8 Compute U t = X 4 + u t3x 3 + u t2x 2 + u t1x + u t0 = 13M + 26A (S(Z + 2w iv 1) wi 2((F V 1 2 )/U1))/U2 (Karatsuba) t 1 = s 0z 3; t 2 = (u 22 + u 21)(u t3 + u t2); t 3 = u 21u t2; t 4 = t 1 t 3; u t3 = z 4 + s 1 u 22; t 5 = s 1z 4 u 22u t3; u t2 = z 3 + s 0 + t 5 u 21; u t1 = z 2 + t 6(z 4 + z 3) + w i(2v 12 w i) (t 5 + t 2 + t 4 + u 20); u t0 = z 1 + t 4 + s 1z 2 + w i(2(v 11 + s 1v 12) + w iu 12) (u 22u t1 + u 20u t3); 9 Compute V t = v t2x 2 + v t1x + v t0 wz + V 1 mod U t 8M + 11A t 1 = u t3 z 4; v t0 = w(t 1u t0 + z 0) + v 10; v t1 = w(t 1u t1 + z 1 u t0) + v 11; v t2 = w(t 1u t2 + z 2 u t1) + v 12; v t3 = w(t 1u t3 + z 3 u t2); 10 Compute U 3 = X 3 + u 32X 2 + u 31X + u 30 = (F Vt 2)/Ut 7M + 11A t 1 = 2v t3; u 32 = (u t3 + vt3 2 ); u31 = f5 (ut2 + u32ut3 + t1vt2); u 30 = f 4 (u t1 + vt2 2 + u32ut2 + u31ut3 + t1vt1); 11 Compute V 3 = v 32X 2 + v 31X + v 30 V t mod U 3 3M + 3A v 32 = v t2 u 32v t3; v 31 = v t1 u 31v t3; v 30 = v t0 u 30v t3; Total I + 70M + 113A g = 1 I + 3M = 23M if I = 20M g = 2 I+25M = 45M if I = 20M g = 3 I+70M = 90M if I = 20M #E(F p ) = O(p) #J C (F p ) = O(p g ) Square-root (?) C : O ( #J C (F p ) )

19 2 80 p = 2 160/g g = 1 p Adleman-DeMarrais-Huang (1991) g = 2 p 2 80 < s g = 3 p 2 54 U deg < s : O(L p 2g+1(1/2, c < 2.181)), log p < (2g + 1) 0.98, g g = 1 I M 160 = 23M 160 g = 2 I M 80 = 45M 80 g = 3 I M 54 = 90M 54 23M 160 > 45M 80 > 90M 54??? : O(L p g(1/2, ), p g Enge, Gaudry-Enge Gaudry (1997) U deg = 1 : O(p 2 ) : O(p 2 2/g ) Gaudry-Harley, Thériault, Nagao, Gaudry-Thomé-Thériault-Diem 36

20 Gaudry C(F p ) = {P, (1, 1), (1, 6), (2, 1), (2, 6), p = 7 C : Y 2 = (4, 1), (4, 6)(5, 3), (5, 4), (6, 3), (6, 4)} X X X X 9 #C(F p ) = 11 +2X 8 + 6X 7 + 5X 4 + 5X 3 +X 2 + 2X + 6 T = {(1, 1), (2, 1), (4, 1), (5, 3), (6, 3)} #J C (F p ) = : 18 bit D a = ( X 6 + 2X 5 + 4X 4 + X 3 + 5X 2 + 3, 4X 5 + 5X 3 + 2X 2 + 5X + 4) D b = ( X 5 + 6X 3 + 3X 2 + 1, 3X 4 + X 3 + 4X 2 + X + 3) [9343]D b = ( X 5 + 6X 4 + 6X 3 + 5X 2 + 6X + 4, X 4 + X 3 + X 2 + 4X + 6) X 5 + 6X 4 + 6X 3 + 5X 2 + 6X + 4 = (X 1) 2 (X 4) 2 (X 5) X 4 + X 3 + X 2 + 4X + 6 X=1 = 6 X 4 + X 3 + X 2 + 4X + 6 X=4 = 1 X 4 + X 3 + X 2 + 4X + 6 X=5 = 3 Find Ind Db D a s.t. D a = [Ind Db D a ]D b. [9343]D b = [2](1, 1) + [2](4, 1) + (5, 3) 38

21 40 [9343]D b [120243]D b [121571]D b = [120688]D b [151649]D b Ind Db (1, 1) Ind Db (2, 1) Ind Db (4, 1) Ind Db (5, 3) Ind Db (6, 3) (1, 1) (2, 1) (4, 1) (5, 3) (6, 3) mod #J C (F p ) D a + [105454]D b = (1, 1) + [2](2, 1) + (4, 1) (6, 3) Ind Db D a Ind Db (1, 1) + 2Ind Db (2, 1) +Ind Db (4, 1) Ind Db (6, 3) mod #J C (F p )

22 42 Gaudry [9343]D b [120243]D b [121571]D b [120688]D b [151649]D b = (1, 1) (2, 1) (4, 1) (5, 3) (6, 3) : O(gp 2 (log #G) 2 ) = O(g 3 p 2 (log p) 2 ) O(g!g 3 p(log p) 3 ) + O(g 3 p 2 (log p) 2 ) #T = O(p) g : O(p g ) g rho 1 g : O(p g /g!) Õ( #G) = O(p g/2 ) O(g!) Jacobian : O(g 2 (log p) 2 ) : O(g 3 (log p) 3 ) O(g!g 3 p(log p) 3 ) Õ(p 2 ) 4 rho

23 44 (Gaudry.Harley) g #T = O(p r ), 0 < r < 1 Õ(p) + Õ(p 2 ) Õ ( p g p rg p r) +Õ ( p 2r) = Õ ( p g+(1 g)r + p 2r) r = g g+1 Õ ( p g+(1 g)r + p 2r) = Õ ( p 2g/(g+1)) Cost rho g

#2 (IISEC)

#2 (IISEC) 2007 10 6 E Y 2 = F (X) E(F p ) E : Y 2 = F (X) = X 3 + AX + B, A, B F p E(F p ) = {(x, y) F 2 p y2 = F (x)} {P } P : E(F p ) E F p - Given: E/F p : EC, P E(F p ), Q P Find: x Z/NZ s.t. Q =