#2 (IISEC)

Size: px

Start display at page:

Download "#2 (IISEC)"

てるえかりこめ
4 years ago
Views:

1 #2 (IISEC)

2 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 = [x]p n := #E(F p ) E(F p ) n p p n p p (x, P ) Q x = (x k 1 x k 2... x 1 x 0 ) 2, Q = 0 i<k[2 x i]p, k = O(log p) A, B n n p (P, Q) x P E(F p ) N := # P N n 2

3 4 Square-root Generic Algo. N = O(p) Square-root N Pohlig-Hellman + {baby-step giant-step, Pollard s rho, lambda} Pohlig-Hellman Silver 1978 Pohlig Hellman Non-Generic Algo rho Menezes-Okamoto-Vanstone SSSA Index calculus

4 6 1 m 1, m 2 Z, gcd(m 1, m 2 ) = 1, x 1, x 2 Z, 0 x i < m i x x i mod m i x Z s.t. x 0 x < m 1 m 2 x = ((m 1 1 mod m 2)(x 2 x 1 ) mod m 2 )m 1 + x 1 O((log(m 1 m 2 )) 2 ) bit-operations N N = 1 i r l e i i [N/l e i i ]Q = [N/le i i x]p, i = 1,..., r # [N/l e i i ]P = le i i

5 8 Q i := [N/l e i i ]Q, P i := [N/l e i i ]P x i [0, l e i i for i [1, r] 1] s.t. Q i = P x i i x i, l e i i x x i mod l e i i for i [1, r] gcd(l e i i, le j j ) = 1 for i j 2 Given: E/F p : EC, l: prime, e N s.t. l e N, P E(F p ) s.t. # P = l e, Q P Find: x [0, l e 1] s.t. Q = [x]p P i, Q i, x i, l i, e i P, Q, x, l, e x O ( (log p) 2) bit-operations

6 e > 1 f Z 0 < f < e Q = [l f v + u]p Q = [x]p, 0 x < l e Q [u]p = [l f v]p = [v][l f ]P u, v Z s.t. x = l f v + u, 0 u < l f, 0 v < l e f [l e f ]Q = [(l e f )x]p = [(l e f )(l f v + u)]p = [(l e f l f v + l e f u)]p = [(l e v + l e f u)]p = [l e f u]p = [u][l e f ]P # b lf = l e f < l e 1: [l e f ]Q = [u][l e f ]P u 2: Q [u]p = [v][l f ]P v 3: x = l f v + u # [l e f ]P = l f < l e e = 1 f f e/2 10

7 1 step [l e f ]Q, [l e f ]P, [u]p, [l f ]P 4 [l e ]P : O(log l e ) = O(e log l)e(f p )-ops. Q = [x]p, # P = l Given: E/F p : EC, l: prime, P E(F p ) s.t. # P = l, Q P Find: x [0, l e 1] s.t. Q = [x]p + 2 O(l) T (l, e) = O(e log l) + 2T (l, e/2) = O(e log e log l + et (l, 1)) Square-root Baby-step giant-step Deterministic algo. e = 1 Pollard rho / lambda Monte Carlo algo. : O(1) 12

8 Rho/lambda Birthday Paradox S : set, n 0 = #S 23 r 1 : ( r n 0 i + 1 r = 1 i 1 ) i=1 n 0 i=1 n 0 1/2 ( r = < exp i 1 ) i=1 n x e x 365 = r = exp i 1 = exp i=1 ( ( n 0 r(r 1) 2n 0 exp 2n 0 ( ) r = 2(log 2)n 0 exp r2 = 0.5 2n 0 r2 O( n 0 ) 14 ) )

9 16 Rho Algorithm 1 Pollard s rho.alpha Input: E/F p : EC, l: prime, P E(F p ) s.t. # P = l, Q P Output: x [0, l 1] s.t. Q = [x]p 1: i := 0 2: repeat 3: i := i + 1 4: Choose α i, β i [0, l 1] randomly 5: R i = [α i ]P + [β i ]Q 6: until j s.t. 1 j < i, R j = R i 7: x = (α i α j )(β j β i ) 1 mod l /*α i + β i x α j + β j x mod l*/ 8: Output x and terminate : O( l) : O( l) Beta 4: Choose α i, β i [0, l 1] randomly 5: R i = [α i ]Q + [β i ]P W S 1, S 2, S 3 #S 1 #S 2 #S 3, P = S 1 S 2 S 3, S 1 S 2 = S 2 S 3 = S 3 S 1 = R i = W (R i 1 ) = R i 1 + P, if R i 1 S 1 [2]R i 1, if R i 1 S 2 R i 1 + Q, if R i 1 S 3

10 18 R i = W (R i 1 ) = α i = W α (α i 1 ) = β i = W β (β i 1 ) = R i 1 + P, if R i 1 S 1 [2]R i 1, if R i 1 S 2 R i 1 + Q, if R i 1 S 3 α i 1 + 1, if R i 1 S 1 2α i 1, if R i 1 S 2 α i 1, if R i 1 S 3 β i 1, if R i 1 S 1 2β i 1, if R i 1 S 2 β i 1 + 1, if R i 1 S 3 Algorithm 2 Pollard s rho.beta Input: E/F p : EC, l: prime, P E(F p ) s.t. # P = l, Q P Output: x [0, l 1] s.t. Q = [x]p 1: i := 1 2: Choose α 1, β 1 [0, l 1] randomly 3: R 1 = [α 1 ]P + [β 1 ]Q 4: repeat 5: i := i + 1 6: R i = W (R i 1 ) 7: α i = W α (α i 1 ), β i = W β (β i 1 ) 8: until j s.t. 1 j < i, c j = c i 9: x = (α i α j )(β j β i ) 1 mod l 10: Output x and terminate : O( l) : O( l)

11 20 Beta alpha Algorithm 3 Pollard s rho method Input: E/F p : EC, l: prime, P E(F p ) s.t. # P = l, Q P Output: x [0, l 1] s.t. Q = [x]p j = 2i i j i j : Choose α 1, β 1 [0, l 1] randomly 2: R 1 = [α 1 ]P + [β 1 ]Q 3: R 2 = W (R 1 ) 4: α 2 = W α (α 1 ), β 2 = W β (β 1 ) 5: while R 1 R 2 do 6: R 1 = W (R 1 ) 7: α 1 = W α (α 1 ), β 1 = W β (β 1 ) 8: R 2 = W (W (c 2 )) 9: α 2 = W α (W α (α 2 )), β 2 = W β (W β (β 2 )) 10: x = (α 2 α 1 )(β 1 β 2 ) 1 mod l 11: Output x and terminate : O( l) : O(1)

12 P E(F p ) P S 3 S 1 ; 0 X(P ) < p/3 S 2 ; p/3 X(P ) < 2p/3 ; 2p/3 X(P ) < p p = 31 S 1 : [0, 10], S 2 : [11, 20], S 3 : [21, 30] E/F p : Y 2 = X X + 22 #E(F p ) = 37: P = (10, 3), Q = (9, 10) α 1 = 35, β 1 = 36 R 1 = [α]p + [β]q i R i α i β i 1 (30, 13) S (11, 3) S (3, 19) S (15, 4) S (21, 17) S (5, 13) S (20, 17) S (29, 11) S (3, 12) S (7, 2) S (21, 14) S (8, 11) S (29, 11) S (3, 12) S (7, 2) S (21, 14) S (8, 11) S (29, 11) S (3, 12) S (7, 2) S (21, 14) S

13 24 l e α 14 α 9 β 9 α 14 α 15 α 10 β 10 α 15 α 15 α 11 β 11 α 15 α 20 α 10 β 10 α 20 mod 37 [17]P = Q mod 37 T (l, e) = O(e log l) + T (l, e/2) = O(e log e log l + et (l, 1)) = O ( e ( log e log l + l )) = e l fore = O(2 l/ log l ) e log e log l fore = Ω(2 l/ log l ) # P T # P = l e O(e l) ; # b O(e log e log l) ; # b

14 Square-root T (N) = N = 1 i r 1 i r l e i i ) O (e i l i E(F p )-ops. i e i = bit l T (N) = ) O ( l i 1 i r = O( l)e(f p )-ops., l := max(l i ) l #E(F p ) Square-root l #E(F p ) G O( l) E(F p )-ops. 80 bit l l #E(F p ) 80 bit l 160 bit 128 bit l 256 bit #E(F p ) #E(F p ) = cl, # P = l P c: small constant. 26

15 28 p = E/F p : Y 2 = X 3 + AX + B A = B = E(F p ) = {P, (3, ), (3, ),... } #E(F p ) = (161bit) = i l i e i log 2 l i

16 30 For l 1 = 2, e 1 = 4 P = ( , ) N := # P = #E(F p ) [N/l i ]P P for i = 1,..., 10 Q = (3, ) Find x s.t. Q = [x]p P 1 = [N/l e 1 1 ]P = ( , ) Q 1 = [N/l e 1 1 ]Q = ( , ) Find x 1 [0, 2 4 1] s.t. Q 1 = [x 1 ]P 1

17 Q 11 = [u]p 11 1: [l e f ]Q = [u][l e f ]P # P 11 = l f 1 = 4 u 2: Q [u]p = [v][l f ˆf = f/2 = 1 ]P v 3: x = l f v + u f = e 1 /2 = 2 P 11 = [l e 1 f 1 ]P 1 = [4]P 1 = ( , ) P 12 = [l f ˆf 1 ]P 11 = [2]P 11 = ( , 0) Q 12 = [l f ˆf 1 ]Q 11 = [2]Q 11 = ( , 0) Q 12 = [û]p 12 û = 1 Q 11 = [l e 1 f 1 ]Q 1 = [4]Q 1 = ( , ) P 13 = [l ˆf 1 ]P 11 = [2]P 11 = P 12 Q 13 = Q 12 [û]p 12 = P Q 13 = [ˆv]P 13 ˆv = 0 u = l ˆf 1ˆv + û = 1 32

18 1: [l e f ]Q = [u][l e f ]P u 2: Q [u]p = [v][l f ]P v 3: x = l f v + u P 14 = [l f 1 ]P 1 = [4]P 1 = ( , ) Q 14 = Q 1 [u]p 1 = Q 1 P 1 = ( , ) Q 14 = [v]p 14 v = 1 x 1 = l f 1 v + u = = 5 Rho part i l e 1 i / log 2 l i x i sec./stps sec. on Magma/efficēon 1G 34

19 36 CRT part x 5 mod 16 3 mod 5 20 mod mod mod mod mod mod mod mod I. Blake, G. Seroussi, and N. Smart. Elliptic Curves in Cryptography. Number 265 in London Mathematical Society Lecture Note Series. Cambridge U. P., H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen, and F. Vercauteren. Handbook of elliptic and hyperelliptic curve cryptography. Chapman & Hall/CRC, A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of applied cryptography. CRC Press, V. Shoup. A computational introduction to number theory and algebra. Cambridge University Press, x mod N

:00-16:10

3 3 2007 8 10 13:00-16:10 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