#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 = [x]p n := #E(F p ) E(F p ) n p + 1 2 p n p + 1 + 2 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
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. 1. 2. rho 3. 4. Menezes-Okamoto-Vanstone SSSA Index calculus
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
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
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
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
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 1 1 364 365 363 365 343 365 = 0.507... < exp i 1 ) i=1 n 0 1 + x e x 365 = 19.104... 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 ) )
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
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)
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 3 4 5 6 7 8 9 j 12 13 14 15 16 17 18 i 10 11 12 13 14 15 16 17 j 18 19 20 21 22 23 24 25 10 11 12 13 14 15 16 26 27 28 29 30 31 32 1: 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)
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 3 + 10X + 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 3 35 36 2 (11, 3) S 2 35 0 3 (3, 19) S 1 33 0 4 (15, 4) S 2 34 0 5 (21, 17) S 3 31 0 6 (5, 13) S 1 31 1 7 (20, 17) S 2 32 1 8 (29, 11) S 3 27 2 9 (3, 12) S 1 27 3 10 (7, 2) S 1 28 3 11 (21, 14) S 3 29 3 12 (8, 11) S 1 29 4 13 (29, 11) S 3 30 4 14 (3, 12) S 1 30 5 15 (7, 2) S 1 31 5 16 (21, 14) S 3 32 5 17 (8, 11) S 1 32 6 18 (29, 11) S 3 33 6 19 (3, 12) S 1 33 7 20 (7, 2) S 1 34 7 21 (21, 14) S 3 35 7 22
24 l e α 14 α 9 β 9 α 14 α 15 α 10 β 10 α 15 α 15 α 11 β 11 α 15 α 20 α 10 β 10 α 20 mod 37 [17]P = Q 30 27 3 5 31 28 3 5 32 29 3 5 34 28 3 7 17 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
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 = 1 128 bit l 2 256 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 2 160 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
28 p = 2 160 47 E/F p : Y 2 = X 3 + AX + B A = 1419587478389183342895449 556703480177911999181832 B = 1370276796320878164248991 66044478248449528373717 E(F p ) = {P, (3, 55907912945587879110990166 1839949961707046542132), (3, 55907912945587879110990166 1839949961707046542132),... } #E(F p ) = 146150163733090291820 3687023423038479648987 002960 (161bit) = 2 4 5 23 1277 711713 1801867 2045011 4738031 38408653 1303287809 i l i e i log 2 l i 1 2 4 1 2 5 1 3 3 23 1 5 4 1277 1 11 5 711713 1 20 6 1801867 1 21 7 2045011 1 21 8 4738031 1 23 9 38408653 1 26 10 1303287809 1 31
30 For l 1 = 2, e 1 = 4 P = (68877725316734917430550420 3634807500170063433889, 10818195495524631221456171 53762479400729821670608) N := # P = #E(F p ) [N/l i ]P P for i = 1,..., 10 Q = (3, 559079129455878791109901 661839949961707046542132) Find x s.t. Q = [x]p P 1 = [N/l e 1 1 ]P = (12180858054680521922633 89671268297866637785070783, 137024357844751571954304 6637992697157748583844582) Q 1 = [N/l e 1 1 ]Q = (13053574756422264436371 50075874346449066599286139, 918498003406678847422986 552214801965456185529002) Find x 1 [0, 2 4 1] s.t. Q 1 = [x 1 ]P 1
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 = (101370728297058356849061 2136378940057879000334514, 1063366667305951199949601 774367450923795168631284) P 12 = [l f ˆf 1 ]P 11 = [2]P 11 = (4226055817864884638391297 86239210404525029853209, 0) Q 12 = [l f ˆf 1 ]Q 11 = [2]Q 11 = (4226055817864884638391297 86239210404525029853209, 0) Q 12 = [û]p 12 û = 1 Q 11 = [l e 1 f 1 ]Q 1 = [4]Q 1 = (101370728297058356849061 2136378940057879000334514, 1063366667305951199949601 774367450923795168631284) 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
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 = (101370728297058356849061 2136378940057879000334514, 1063366667305951199949601 774367450923795168631284) Q 14 = Q 1 [u]p 1 = Q 1 P 1 = (101370728297058356849061 2136378940057879000334514, 1063366667305951199949601 774367450923795168631284) Q 14 = [v]p 14 v = 1 x 1 = l f 1 v + u = 22 + 1 = 5 Rho part i l e 1 i / log 2 l i x i sec./stps. 1 2 4 5 1 2 5 3.07 3 3 3 23 20.10 5 7 4 1277 293.11 11 55 5 711713 532349.20 20 387 6 1801867 1686283.44 21 1457 7 2045011 531538.34 21 1105 8 4738031 1517838.62 23 2350 9 38408653 22671833 3.2 26 14945 10 1303287809 1094987215 8.9 31 42617.07 +.10 +.11 +.20 +.44 +.34 +.62 + 3.2 + 8.9 14sec. on Magma/efficēon 1G 34
36 CRT part x 5 mod 16 3 mod 5 20 mod 23 293 mod 1277 532349 mod 711713 1686283 mod 1801867 531538 mod 2045011 1517838 mod 4738031 22671833 mod 38408653 1094987215 mod 1303287809 I. Blake, G. Seroussi, and N. Smart. Elliptic Curves in Cryptography. Number 265 in London Mathematical Society Lecture Note Series. Cambridge U. P., 1999. 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, 2005. A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of applied cryptography. CRC Press, 1997. V. Shoup. A computational introduction to number theory and algebra. Cambridge University Press, 2005. x 743799732436366136546362638 012460649291492098213 mod N