|
|
|
- えりか しげまつ
- 9 years ago
- Views:
Transcription
1 ( )
2 (1) (2) (3) (ECDLP) Baby-step Giant-step ρ (ECC) ECDH ECElGamal ECDSA
3 1., ( ). 2
4 1.1 p, 0 p 1 F p = {0, 1,..., p 1}. p 0 p 1, p,. 1.1 F 7 = {0, 1, 2, 3, 4, 5, 6} x + y 1.1. F p x x + p p, F p x x + p. x y = x + p y, F p. 1.2 F 7 = {0, 1, 2, 3, 4, 5, 6} x y 1.2. (additive group). 3
5 1.1 y x F y x F G (i) G a, b, c (a b) c = a (b c), (ii) G a a e = e a = a G e, (iii) G a a a = a a = e G a,, G (group). +. ( x y = y x ), ( x + y = y + x ). 4
6 F p p,. 1.3 F 7 = {0, 1, 2, 3, 4, 5, 6} x y 1.3. F p p, x, x + p, x + 2p, x + 3p,.... x y = (x + p) y = (x + 2p) y =,. (, p, x, a, b ap + by = 1, by 1 (mod p) b y 1 (mod p), x y = x b. a, b Euclid.) 1.4 F 7 = {0, 1, 2, 3, 4, 5, 6} x y (y 0) 1.4., ( 0 ) p F p (prime field).,, ( 0 ), (finite field).,.. 5
7 1.3 y x F y x F field, field ( )., köper (, ).,, field. 6
8 1.2 F p. 1.5 ( ) E : y 2 = x 3 + ax + b (a, b F p, E = 4a b 2 0) (1.1) F p (elliptic curve). 1.6 E : y 2 = x 3 + 3x + 4 F 7. E, x, y F p (x, y) F p - (F p -rational point). (the point at infinity) O. (x, y). 1.7 F 7 E : y 2 = x 3 + 3x y 2 = x 3 + 3x + 4 F 7 - P 0 O P 1 (0, 2) P 9 (0, ) P 2 (1, 1) P 8 (1, ) P 3 (2, 2) P 7 (2, ) P 4 (5, 2) P 6 (5, ) P 5 7
9 E = 4a b 2 0, (1.1). E (discriminant). 2 F : y = x 2 + Bx + C F = B 2 4C, F 0 F. n G : y = A 0 x n + A 1 x n A n G = A 2(n 1) 0 (α 1 α 2 ) 2 (α 1 α n ) 2 (α 2 α 3 ) 2... (α 2 α n ) 2 (α n 1 α n ) 2. α 1,..., α n G., n = 3, E = 4a b 2. 8
10 1.3,. ( x, y )., ( ). 1.8 ( ) R = P + Q. F p E : y 2 = x 3 + ax + b 2 P, Q ( O) 1. 2 P, Q (P = Q P ) l. 2. E l 3 R ( R = O ). 3. R x R (R = O R = O ). R R, R = R. O, F 7 E : y 2 = x 3 + 3x + 4, 1.6 y 2 = x 3 + 3x + 4 F 7 - P 0 O P 1 (0, 2) P 6 (5, 5) P 2 (1, 1) P 7 (2, 5) P 3 (2, 2) P 8 (1, 6) P 4 (5, 2) P 9 (0, 5) P 5 (6, 0) 9
11 (elliptic curve) (ellipse).,.,., ( ).. 10
12 ( ) R = P + Q. F p E : y 2 = x 3 + ax + b 2 P, Q P = O : R = Q. Q = O : R = P. : P = (x P, y P ), Q = (x Q, y Q ) y P = y Q : R = O ( Q = P ). y P y Q : R = (x R, y R ). x R, y R x R = λ 2 x P x Q, y R = λ(x P x R ) y P, λ 2 P, Q ( P ). y P y Q x λ = P x Q 3x 2 P + a 2y P x P x Q x P = x Q F 7 E : y 2 = x 3 + 3x + 4, P 2 + P 4, 2 P 6. 11
13 2 P = (x P, y P ), Q = (x Q, y Q ) (y P y Q )/(x P x Q ). x P = x Q 0,. P, Q E : y 2 = x 3 + ax + b y P y Q = (y P y Q )(y P + y Q ) x P x Q (x P x Q )(y P + y Q ) = yp 2 yq 2 (x P x Q )(y P + y Q ) = (x3 P + ax P + b) (x 3 Q + ax Q + b) (x P x Q )(y P + y Q ) = (x P x Q )(x 2 P + x P x Q + x 2 Q + a) (x P x Q )(y P + y Q ) = x2 P + x P x Q + x 2 Q + a y P + y Q, P = Q x P = x Q, y P = y Q. y P y Q = x2 P + x P x Q + x 2 Q + a = 3x2 P + a x P x Q y P + y Q 2y P 12
14 y 2 = x 3 + 3x + 4 F y 2 = x 3 + 3x + 4 F 7 - P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9 P 0 P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9 P 1 P 1 P 8 P 9 P 6 P 7 P 4 P 5 P 3 P 2 P 0 P 2 P 2 P 9 P 1 P 4 P 6 P 3 P 7 P 5 P 0 P 8 P 3 P 3 P 6 P 4 P 1 P 9 P 2 P 8 P 0 P 5 P 7 P 4 P 4 P 7 P 6 P 9 P 8 P 1 P 0 P 2 P 3 P 5 P 5 P 5 P 4 P 3 P 2 P 1 P 0 P 9 P 8 P 7 P 6 P 6 P 6 P 5 P 7 P 8 P 0 P 9 P 2 P 1 P 4 P 3 P 7 P 7 P 3 P 5 P 0 P 2 P 8 P 1 P 9 P 6 P 4 P 8 P 8 P 2 P 0 P 5 P 3 P 7 P 4 P 6 P 9 P 1 P 9 P 9 P 0 P 8 P 7 P 5 P 6 P 3 P 4 P 1 P ,
15 , y 2 = x 3 + ax + b ( 1.4), y 2 + a 1 xy + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 (Weierstrass ). y 2 = x 3 + ax + b. 14
16 1.4,. Mordell-Weil (Mordell-Weil group). (group order) F 7 E : y 2 = x 3 + 3x + 4 #E. F p, (Hasse-Weil ) F p E #E, #E. p p #E p p Hasse-Weil ( 1.14), F p p., F ,, F 7 E : y 2 = x 3 + 3x + 4 Hasse-Weil ( 1.14). 15
17 1.8 F 7 E : y 2 = x 3 + ax + b b a Deuring Hasse-Weil ( 1.14),., Deuring. Deuring, a, b, Hasse-Weil. F 7 ( 1.8). 16
18 1.5 F p E P ( (base point) ). d, P d d P = P + + P } {{ } d (scalar multiplication)., F 7 E : y 2 = x 3 + 3x + 4, P 1. 2 P 1 = 3 P 1 = 4 P 1 = 5 P 1 = 6 P 1 = 7 P 1 =, 2, 3,..., O. (point order)., P d P = O.,, F 7 E : y 2 = x 3 + 3x + 4, P 1 17
19 x d x d, ( mod N ) RSA., d P,,. 18
20 d P, d 1., 8 P = P + P + P + P + P + P + P + P 7., 8 P = 2 (2 (2 P )), 3.,. d 2 d = 2 n 1 + d n 2 2 n d d 0 (d i {0, 1}) = (1, d n 2,..., d 1, d 0 ) : P, d = (1, d n 2,..., d 1, d 0 ) 2 : d P 1. Q P 2. i = n 2,..., 1, 0 : 2.1 Q 2 Q 2.2 d i = 1 Q Q + P 3. Q., d P ( ) 1.5 log 2 d, d , d = 3045 = (1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1) 2, Q.,. i d i
21 F q E Mordell-Weil E(F q ), E(F q ) 2 C 1, C 2, E(F q ) C 1 C 2 (#C 1 #C 2, #C 1 (q 1))., E(F q ) ( E(F q ) C 1 ). 20
22 1.6 (1),.,. F p,, ( ). ( 1.10),., (projective coordinates)., 3 (X : Y : Z)., 2 (X : Y : Z), (X : Y : Z ) X = cx, Y = cy, Z = cz c F p, 2. (X : Y : Z) = (2X : 2Y : 2Z) = = (X/Z : Y/Z : 1)., ( ) (x, y), (x : y : 1)., (X : Y : Z) (X/Z, Y/Z). 21
23 Jacobian, 2 X = c 2 X, Y = c 3 Y, Z = cz Jacobian (Jacobian projective coordinate).,. 22
24 Y 2 Z = X 3 + axz 2 + bz 3 (a, b F p, E = 4a b 2 0)., y 2 = x 3 +ax+b x = X/Z, y = Y/Z., X Z 0.,.,, ( ) F p E : Y 2 Z = X 3 + axz 2 + bz 3 2 P = (X P : Y P : Z P ), Q = (X Q : Y Q : Z Q ) R = P + Q = (X R : Y R : Z R ). P Q X R = va Y R = u(v 2 X P Z Q A) v 3 Y P Z Q Z R = v 3 Z P Z Q u = Y Q Z P Y P Z Q, v = X Q Z P X P Z Q, A = u 2 Z P Z Q v 3 2v 2 X P Z Q P = Q X R = 2hs Y R = w(4b h) 8YP 2 s 2 Z R = 8s 3 w = az 2 P + 3X2 P, s = Y P Z P, B = sx P Y P, h = w 2 8B P Q : P Q :, P = (x : y : 1) d P = (X : Y : Z), (X/Z, Y/Z)., 1,. 23
25 ,, Jacobian,. P Q P = Q 3, 1 4, Jacobian , d d i, P = Q, P Q 1/2, P = Q Jacobian. 24
26 1.7 (2) 1.1 d 2., d m. m = 8 ( n 3 ). 1.2 (8 ) : P, d = (d n 1, d n 2,..., d 1, d 0 ) 2 : d P 0. i = 0, 1,..., 7 : 0.1 P i i P 1. Q P 4dn 1 +2d n 2 +d n 3 2. i = n 4, n 7,..., 2 : 2.1 Q 8 Q 2.2 Q Q + P 4di +2 i 1 +d i 2 3. Q. 1.2, 0. P 0, P 1,..., P 7, , 3. (window method). 1.21, d = 3045 = (1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1) 2, Q.,. i d i d i 1 d i , /3, 8 P 3, 2.1 n., 2.2 1/3, 2.2 n/ /2, 2.2 n/2, ,. 25
27 d 160, m =
28 1.8 (3) 2, P P ( (x, y), (X : Y : Z))., d 2 d = 2 n 1 + d n 2 2 n d d 0 (d i { 1, 0, 1}) = (1, d n 2,..., d 1, d 0 ) 2,. 1.3 ( 2 ) : P, d = (d n 1, d n 2,..., d 1, d 0 ) 2 : d P 1. Q P 2. i = n 2,..., 1, 0 : 2.1 Q 2 Q 2.2 d i = 1 Q Q + P 2.3 d i = 1 Q Q P 3. Q. d 2, NAF (non-adjacent form, ). d, 3d ( ) 2 (e n+1, e n,..., e 0 ) 2 d ( ) 2 (f n+1, f n,..., f 0 ) 2. d = (3d d)/2, 3d 2 d 2 2, d 2 ( d i = e i+1 f i+1 ). NAF,, 1 1, d ±1 log 2 d/ NAF, 1.33 log 2 n. 27
29 2 2, d i = 1,. 28
30 p,., y 2 = x 3 + ax + b.,.,. [ ],.,,.,,., (d P d ),.,.,,,. 29
31 2,. 30
32 2.1 (ECDLP) F p E, P d Q = d P ( )., P, Q Q = d P d (1 d l, l P ) (elliptic curve discrete logarithm problem, ECDLP) F 7 E : y 2 = x 3 + 3x + 4, P = P 1, Q = P 2, Q = d P d. 2.1,.,.,. 2.2 F p, P, Q F p Q = d P d.. 31
33 P, Q = P d, P, Q d ( ), log P Q. y = log P Q. Q = d P d ( ).,. 32
34 2.2 2 P, Q Q = d P d (1 d l, l P ) ( ), 2 P, 3 P,..., l P (brute force method) GHz, ,
35 2 160,, ( = ).,,. Mathematica Maple,,. Risa/Asir,. 34
36 2.3 Baby-step Giant-step, Baby-step Giant-step (Baby-step Giant-step method). Q = d P, P l m = l ( x x ). d = sm + t (0 s, t < m), s, t d. s, t. R = m P, Q = d P = (sm + t) P = s (m P ) + t P = s R + t P, s, t Q t P = s R (2.1). 2 Q, Q P, Q 2 P, Q 3 P,..., Q (m 1) P O, R, 2 R, 3 R,..., (m 1) R, x. 2, s, t, d. m, 2m, 2 l. 2.4 Baby-step Giant-step, l , 2 81, , Baby-step Giant-step,. 35
37 , 2., , ,
38 2.4 ρ, ρ (ρ method), Baby-step Giant-step. Q = d P, s P + t Q = s P + t Q s, t, s, t (s s, t t ). (t t ) Q = (s s) P Q = s s t t P, (s s)/(t t ) d. mod l (l P ). 2.5 F 229 E : y 2 = x 3 + x + 44, P = (5, 116), Q = (155, 166) Q = d P. P l = 239., 26 P Q = 47 P Q = (9, 18) Q = P = P = 176 P d = 176. R i = s i P + t i Q, ρ, R i = R j R i, R j.. 37
39 ( ) 2,.., (365 ) 23 1/2 2..,. ρ,. 38
40 ρ,,. R, (Random Walk ) f. R + M 0 if x(r) 0 (mod 4) R + M 1 if x(r) 1 (mod 4) f(r) = R + M 2 if x(r) 2 (mod 4) R + M 3 if x(r) 3 (mod 4) x(r) R x. M i = u i P + v i Q , R 0 = (39, 159) = 54 P Q f,. R 9 R 21. M 0 = (135, 117) = 79 P Q M 2 = (84, 62) = 87 P Q M 1 = (96, 97) = 206 P + 19 Q M 3 = (72, 134) = 219 P + 68 Q. i R i s i t i x(r i ) mod 4 i R i s i t i x(r i ) mod 4 0 (39, 159) (197, 92) (160, 9) (211, 47) (130, 182) (194, 145) (27, 17) (0, 68) (36, 97) (223, 153) (119, 180) (9, 18) (108, 89) (167, 57) (81, 168) (75, 136) (223, 153) (57, 105) (9, 18) (159, 4) (167, 57) (185, 227) (75, 136) (158, 26) (57, 105) (197, 92) (159, 4) (211, 47) (185, 227) (194, 145) (158, 26) (0, 68)
41 Random walk f,, 4.. ρ,
42 , l., R i (distinguished point). x θ., 1/θ.,. R i = R j f(r i ) = f(r j ), f(f(r i )) = f(f(r j )), f(f(f(r i ))) = f(f(f(r j ))),...,, , x 1 0 ( θ = 10), R 1 = (160, 9), R 2 = (130, 182), R 19 = (0, 68), R 31 = (0, 68). R 19 R 31, R 19 = 227 P Q = 9 P + 37 Q = R 31 d = 176. ρ, l, Baby-step Giant-step. l/θ, Baby-step Giant-step., ρ,.,,. 41
43 Certicom Certicom Waterloo Scott Vanstone 1985, (, Waterloo RIM ). Certicom,. 42
44 2.5., ρ. (Certicom Challenge.) Certicom Challenge Certicom Challenge Certicom Challenge Certicom Challenge p = ( )/( ) a = b = #E = x P = y P = l = x Q = y Q = d = Q x (π 3) 10 34,. 112, PlayStation ,
45 Certicom Challenge Certicom,,., ,000,,,. 44
46 2.6, ρ., Menezes-Okamoto-Vanstone Waterloo Alfred Menezes, Scott Vanstone NTT Tatsuaki Okamoto, F p p + 1 (Supersingular ), F 7, Supersingular., ( ) Supersingluar Semaev-Smart-Satoh-Araki Igor Semaev, Bristol Nigel Smart, Takakazu Satoh Kiyomichi Araki, F p p (Anomalous ), F 7, Anomalous. 45
47 Menezes-Okamoto-Vanstone,,,. (pairing)., 2 e : E(F q ) E(F q ) G, P, P, Q, Q, e(p + P, Q) = e(p, Q) e(p, Q), e(p, Q + Q ) = e(p, Q) e(p, Q )., (bilinear map).,,, ID. 46
48 , P, Q Q = d P d.,, Baby-step Giant-step, ρ. ρ. [ ],,.,,.,. 47
49 3,.. 48
50 3.1 (ECC),. (elliptic curve cryptosystems, ECC) ( ).,. RSA, RSA RSA, ( d) 160., F p, E : y 2 = x 3 + ax + b. P = (x P, y P ), l.. p = = a = 3 = b = #E = x P = y P = l =
51 3.1 Diffie-Hellman (ECDH) Menezes-Qu-Vanstone (ECMQV) ElGamal (ECElGamal) DSA (ECDSA), (encryption), (cryptsystem) 2.,. (cryptsystem ),. 50
52 3.2 ECDH, ( ).,, Diffie-Hellman (ECDH ). 3.2 (ECDH ) Alice Bob, F p E P. Alice Bob, 2 K A = K B. 1. Alice d A, P A = d A P Bob. 2. Bob d B, P B = d B P Alice. 3. P B Alice K A = d A P B,. 4. P A Bob K B = d B P A, F 7 E : y 2 = x 3 + 3x + 4 P = P 1, d A = 2, d B = 3. P A = K B = P B = K A = 3.4 ECDH, Alice K A Bob K B. ECDH. Carol, Alice Bob ECDH, F p, E, P. Alice Bob P A, P B. P A, P d A, P B, P d B, Carol d A, d B. ECDH. 51
53 Diffie-Hellman (ECDH ) P A = d A P, P B = d B P, P A, P B, P K = d A d B P Diffie-Hellman (ECDH ). ECDH., P A, P d A, K = d A P B, ECDH. ECDH, d A, d B K,. ECDH,, ECDH. 52
54 3.3 ECElGamal ECDH, ECElGamal. 3.5 (ECElGamal ) Alice Bob, F p E P. Alice Bob, Bob M. 1. Bob d B, P B = d B P. P B, d B. 2. Alice a r, P A = r P. b Bob P B, K = r P B. c M, C = M + K. d Bob C P A. 3. Bob a P A d B, K = d B P A. b M = C K, M. 3.6 ECElGamal, Alice K Bob K.. 53
55 , 1985 IBM Victor Miller Washington Neal Koblitz.,. 54
56 3.4 ECDSA, ECDSA. 3.7 (ECDSA ) Alice Bob, F p E P l. Alice Bob, Bob m. 1. Alice d A (1 d A l), P A = d A P. P A, d A. 2. Alice a r, U = r P = (x U, y U ). b m H(m). c u = x U mod l, v = (H(m) + u d A )/r mod l. d Bob (u, v). 3. Bob a Alice P A, d = 1/v mod l V = d H(m) P + d u P A = (x V, y V ). b u = x V mod l.,,. 3.8 ECDSA,. 55
57 DTCP,., DTCP (Digital Transmission Content Protection),. DTCP, ECDH, ECDSA. 56
58 3.5,,. 2, Baby-step Giant-step, ρ l. l,.,. 3.9 ( ) P. F p E 1. p, p. 2. a, b F p, E(a, b) : y 2 = x 3 + ax + b. (Hasse-Weil, p p #E(a, b) p p ). 3. #E(a, b) #E(a, b) = p 2. (Anomalous ). 5. E(a, b) P Supersingular ,.. 57
59 NIST,,,. NIST. 58
60 (ECC), ( ). [ ],,.,., ANSI ( ), IEEE ( ), ISO ( ), NIST ( ), CRYPTREC ( ).,. 59
61 ,.,., ( ). 2,., ( ),, , ( ),, ,. 3,. 3,,.,,, Joseph Silverman, A Friendly Introduction to Number Theory (3rd edition), Pearson Prentice Hall, 2006 [, ( 3 ),, 2007 ] Victor Shoup, A Computational Introduction to Number Theory and Algebra (1st edition) [ PDF : Jeffrey Hoffstein, Jill Pipher, Joseph Silverman, An Introduction to Mathematical Cryptography, Springer-Verlag,
62 ,,. 3,.,,, ,, BP, ( ),,, , 2 (, ).,,, ,,,, ,. 4,. Neal Koblitz, A Course in Number Theory and Cryptography (2nd edition), Springer-Verlag, 1994 [, ( 2 ),, ] Ian Blake, Gadiel Seroussi, Nigel Smart, Elliptic Curves in Cryptography, Cambridge University Press, 2000 [,,, 2001 ] Darrel Hankerson, Alfred Menezes, Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2002, (, ),,, , ( : ID ). ID. Luther Martin, Introduction to Identity-Based Encryption, Artech House,
63 ,,.,,. (ISEC) [2 1 ] (JANT) [3 1 ], ISEC, 300. (SCIS) [ 1 ], (IACR) CRYPTO EUROCRYPTO ASIACRYPTO PKC,. Workshop on Elliptic Curve Cryptography (ECC) 62
楕円曲線暗号と RSA 暗号の安全性比較
RSA, RSA RSA 7 NIST SP-7 Neal Koblitz Victor Miller ECDLP (Elliptic Curve Discrete Logarithm Problem) RSA Blu-ray AACS (Advanced Access Control System) DTCP (Digital Transmission Content Protection) RSA
( 9 1 ) 1 2 1.1................................... 2 1.2................................................. 3 1.3............................................... 4 1.4...........................................
Block cipher
18 12 9 1 2 1.1............................... 2 1.2.................. 2 1.3................................. 4 1.4 Block cipher............................. 4 1.5 Stream cipher............................
7 27 7.1........................................ 27 7.2.......................................... 28 1 ( a 3 = 3 = 3 a a > 0(a a a a < 0(a a a -1 1 6
26 11 5 1 ( 2 2 2 3 5 3.1...................................... 5 3.2....................................... 5 3.3....................................... 6 3.4....................................... 7
2014 F/ E 1 The arithmetic of elliptic curves from a viewpoint of computation 1 Shun ichi Yokoyama / JST CREST,.
2014 F/ E 1 The arithmetic of elliptic curves from a viewpoint of computation 1 Shun ichi Yokoyama / JST CREST,. http://www2.math.kyushu-u.ac.jp/~s-yokoyama/yamagata2014.html. K Q, C, F p.,, f = 0.,,.,
1 1 1 1 1 1 2 f z 2 C 1, C 2 f 2 C 1, C 2 f(c 2 ) C 2 f(c 1 ) z C 1 f f(z) xy uv ( u v ) = ( a b c d ) ( x y ) + ( p q ) (p + b, q + d) 1 (p + a, q + c) 1 (p, q) 1 1 (b, d) (a, c) 2 3 2 3 a = d, c = b
1 Abstract 2 3 n a ax 2 + bx + c = 0 (a 0) (1) ( x + b ) 2 = b2 4ac 2a 4a 2 D = b 2 4ac > 0 (1) 2 D = 0 D < 0 x + b 2a = ± b2 4ac 2a b ± b 2
1 Abstract n 1 1.1 a ax + bx + c = 0 (a 0) (1) ( x + b ) = b 4ac a 4a D = b 4ac > 0 (1) D = 0 D < 0 x + b a = ± b 4ac a b ± b 4ac a b a b ± 4ac b i a D (1) ax + bx + c D 0 () () (015 8 1 ) 1. D = b 4ac
5.. z = f(x, y) y y = b f x x g(x) f(x, b) g x ( ) A = lim h g(a + h) g(a) h g(x) a A = g (a) = f x (a, b)............................................
5 partial differentiation (total) differentiation 5. z = f(x, y) (a, b) A = lim h f(a + h, b) f(a, b) h........................................................... ( ) f(x, y) (a, b) x A (a, b) x (a, b)
untitled
10 log 10 W W 10 L W = 10 log 10 W 10 12 10 log 10 I I 0 I 0 =10 12 I = P2 ρc = ρcv2 L p = 10 log 10 p 2 p 0 2 = 20 log 10 p p = 20 log p 10 0 2 10 5 L 3 = 10 log 10 10 L 1 /10 +10 L 2 ( /10 ) L 1 =10
index calculus
index calculus 2008 3 8 1 generalized Weil descent p :, E/F p 3 : Y 2 = f(x), where f(x) = X 3 + AX + B, A F p, B F p 3 E(F p 3) 3 : Generalized Weil descent E(F p 4) 2 Index calculus Plain version Double-large-prime
21 Key Exchange method for portable terminal with direct input by user
21 Key Exchange method for portable terminal with direct input by user 1110251 2011 3 17 Diffie-Hellman,..,,,,.,, 2.,.,..,,.,, Diffie-Hellman, i Abstract Key Exchange method for portable terminal with
x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y)
x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 1 1977 x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y) ( x 2 y + xy 2 x 2 2xy y 2) = 15 (x y) (x + y) (xy
( )
NAIST-IS-MT0851100 2010 2 4 ( ) CR CR CR 1980 90 CR Kerberos SSH CR CR CR CR CR CR,,, ID, NAIST-IS- MT0851100, 2010 2 4. i On the Key Management Policy of Challenge Response Authentication Schemes Toshiya
チュートリアル：ノンパラメトリックベイズ
{ x,x, L, xn} 2 p( θ, θ, θ, θ, θ, } { 2 3 4 5 θ6 p( p( { x,x, L, N} 2 x { θ, θ2, θ3, θ4, θ5, θ6} K n p( θ θ n N n θ x N + { x,x, L, N} 2 x { θ, θ2, θ3, θ4, θ5, θ6} log p( 6 n logθ F 6 log p( + λ θ F θ
ISO/IEC 9798プロトコルの安全性評価
ISO/IEC 9798 2011 2 4 ISO/IEC 9798-2 (Mechanisms using symmetric encipherment algorithms), ISO/IEC 9798-3 (Mechanisms using digital signature techniques), ISO/IEC 9798-4 (Mechanisms using a cryptographic
Jacobson Prime Avoidance
2016 2017 2 22 1 1 3 2 4 2.1 Jacobson................. 4 2.2.................... 5 3 6 3.1 Prime Avoidance....................... 7 3.2............................. 8 3.3..............................
5 36 5................................................... 36 5................................................... 36 5.3..............................
9 8 3............................................. 3.......................................... 4.3............................................ 4 5 3 6 3..................................................
untitled
1 ( 12 11 44 7 20 10 10 1 1 ( ( 2 10 46 11 10 10 5 8 3 2 6 9 47 2 3 48 4 2 2 ( 97 12 ) 97 12 -Spencer modulus moduli (modulus of elasticity) modulus (le) module modulus module 4 b θ a q φ p 1: 3 (le) module
2016 Course Description of Undergraduate Seminars (2015 12 16 ) 2016 12 16 ( ) 13:00 15:00 12 16 ( ) 1 21 ( ) 1 13 ( ) 17:00 1 14 ( ) 12:00 1 21 ( ) 15:00 1 27 ( ) 13:00 14:00 2 1 ( ) 17:00 2 3 ( ) 12
genus 2 Jacobi Pila Schoof 42 Adleman Huang 2 19 3 Gaudry Harley l genus 2 Jacobi 17 Jacobi Spallek 52 theta CM Jacobi genus2 Wang 61 Weber 60 Wamelen
6 2000 Journal of the Institute of Science and Engineering5 Chuo University Jacobi CM Type Computation of CM Type of Jacobian Varieties Jacobi CM CM Jacobi CM type reflex CM type Frobenius endomorphism
2 1 17 1.1 1.1.1 1650
1 3 5 1 1 2 0 0 1 2 I II III J. 2 1 17 1.1 1.1.1 1650 1.1 3 3 6 10 3 5 1 3/5 1 2 + 1 10 ( = 6 ) 10 1/10 2000 19 17 60 2 1 1 3 10 25 33221 73 13111 0. 31 11 11 60 11/60 2 111111 3 60 + 3 332221 27 x y xy
SQUFOF NTT Shanks SQUFOF SQUFOF Pentium III Pentium 4 SQUFOF 2.03 (Pentium 4 2.0GHz Willamette) N UBASIC 50 / 200 [
SQUFOF SQUFOF NTT 2003 2 17 16 60 Shanks SQUFOF SQUFOF Pentium III Pentium 4 SQUFOF 2.03 (Pentium 4 2.0GHz Willamette) 60 1 1.1 N 62 16 24 UBASIC 50 / 200 [ 01] 4 large prime 943 2 1 (%) 57 146 146 15
A Brief Introduction to Modular Forms Computation
A Brief Introduction to Modular Forms Computation Magma Supported by GCOE Program Math-For-Industry Education & Research Hub What s this? Definitions and Properties Demonstration H := H P 1 (Q) some conditions
.,.,..,? 2.,.?.,...,...,.,.,.,.,,..,..,,.,,.,.,..,..,....,.,.,.,?,...,,.... Dr.Hener, i
2006 D r. H e n e r 18 4 1 .,.,..,? 2.,.?.,...,...,.,.,.,.,,..,..,,.,,.,.,..,..,....,.,.,.,?,...,,.... Dr.Hener, i 1 2 1 1.1 2 10..................................... 1 1.2 2......................................
i 0 1 0.1 I................................................ 1 0.2.................................................. 2 0.2.1...........................
2008 II 21 1 31 i 0 1 0.1 I................................................ 1 0.2.................................................. 2 0.2.1............................................. 2 0.2.2.............................................
ac b 0 r = r a 0 b 0 y 0 cy 0 ac b 0 f(, y) = a + by + cy ac b = 0 1 ac b = 0 z = f(, y) f(, y) 1 a, b, c 0 a 0 f(, y) = a ( ( + b ) ) a y ac b + a y
01 4 17 1.. y f(, y) = a + by + cy + p + qy + r a, b, c 0 y b b 1 z = f(, y) z = a + by + cy z = p + qy + r (, y) z = p + qy + r 1 y = + + 1 y = y = + 1 6 + + 1 ( = + 1 ) + 7 4 16 y y y + = O O O y = y
13 0 1 1 4 11 4 12 5 13 6 2 10 21 10 22 14 3 20 31 20 32 25 33 28 4 31 41 32 42 34 43 38 5 41 51 41 52 43 53 54 6 57 61 57 62 60 70 0 Gauss a, b, c x, y f(x, y) = ax 2 + bxy + cy 2 = x y a b/2 b/2 c x
( ) x y f(x, y) = ax
013 4 16 5 54 (03-5465-7040) [email protected] hp://lecure.ecc.u-okyo.ac.jp/~nkiyono/inde.hml 1.. y f(, y) = a + by + cy + p + qy + r a, b, c 0 y b b 1 z = f(, y) z = a + by + cy z = p + qy
0.,,., m Euclid m m. 2.., M., M R 2 ψ. ψ,, R 2 M.,, (x 1 (),, x m ()) R m. 2 M, R f. M (x 1,, x m ), f (x 1,, x m ) f(x 1,, x m ). f ( ). x i : M R.,,
2012 10 13 1,,,.,,.,.,,. 2?.,,. 1,, 1. (θ, φ), θ, φ (0, π),, (0, 2π). 1 0.,,., m Euclid m m. 2.., M., M R 2 ψ. ψ,, R 2 M.,, (x 1 (),, x m ()) R m. 2 M, R f. M (x 1,, x m ), f (x 1,, x m ) f(x 1,, x m ).
¥µ¥¤¥Ü¥¦¥º¡¦¥é¥Ü¥æ¡¼¥¹ À®²ÌÊó¹ð
Python March 30, 2016 1 / 30 who? @elliptic shiho 0x10, CTF March 30, 2016 2 / 30 why? Python sage 1,, 1 NumPy, Cython Python March 30, 2016 3 / 30 why?,. -, -,, March 30, 2016 4 / 30 , E : y 2 = x 3 +
x ( ) x dx = ax
x ( ) x dx = ax 1 dx = a x log x = at + c x(t) = e at C (C = e c ) a > 0 t a < 0 t 0 (at + b ) h dx = lim x(t + h) x(t) h 0 h x(t + h) x(t) h x(t) t x(t + h) x(t) ax(t) h x(t + h) x(t) + ahx(t) 0, h, 2h,
RSA署名方式の安全性を巡る研究動向について
RSA RSA RSA RSA RSA RSA PSSRSA PSS RSARSA PSS RSA PSS RSARSA-PSS E-mail:[email protected] RSARSA PKCS ISO ISO IPS ANS X RSARSA RSA RSA RSA RSA RSA RSA bit RSA RSA PSS RSA PSS RSA ISO PKCSVer RSA
24.15章.微分方程式
m d y dt = F m d y = mg dt V y = dy dt d y dt = d dy dt dt = dv y dt dv y dt = g dv y dt = g dt dt dv y = g dt V y ( t) = gt + C V y ( ) = V y ( ) = C = V y t ( ) = gt V y ( t) = dy dt = gt dy = g t dt
1 TEPLA TEPLA (University of Tsukuba Elliptic Curve and Pairing Library) C 2 1 TEPLA TEPLA Barreto-Naehrig (BN) BN Opimal Ate TEPLA M
TEPLA (University of Tsukuba Elliptic Curve and Pairing Library) 27 12 20 ver. 2.0.0 1 1 TEPLA TEPLA (University of Tsukuba Elliptic Curve and Pairing Library) C 2 1 TEPLA TEPLA 254 2 12 Barreto-Naehrig
x = a 1 f (a r, a + r) f(a) r a f f(a) 2 2. (a, b) 2 f (a, b) r f(a, b) r (a, b) f f(a, b)
2011 I 2 II III 17, 18, 19 7 7 1 2 2 2 1 2 1 1 1.1.............................. 2 1.2 : 1.................... 4 1.2.1 2............................... 5 1.3 : 2.................... 5 1.3.1 2.....................................
waseda2010a-jukaiki1-main.dvi
November, 2 Contents 6 2 8 3 3 3 32 32 33 5 34 34 6 35 35 7 4 R 2 7 4 4 9 42 42 2 43 44 2 5 : 2 5 5 23 52 52 23 53 53 23 54 24 6 24 6 6 26 62 62 26 63 t 27 7 27 7 7 28 72 72 28 73 36) 29 8 29 8 29 82 3
I. (CREMONA ) : Cremona [C],., modular form f E f. 1., modular X H 1 (X, Q). modular symbol M-symbol, ( ) modular symbol., notation. H = { z = x
![I. (CREMONA ) : Cremona [C],., modular form f E f. 1., modular X H 1 (X, Q). modular symbol M-symbol, ( ) modular symbol., notation. H = { z = x](/thumbs/103/158868201.jpg "I. (CREMONA ) : Cremona [C],., modular form f E f. 1., modular X H 1 (X, Q). modular symbol M-symbol, ( ) modular symbol., notation. H = { z = x")
I. (CREMONA ) : Cremona [C],., modular form f E f. 1., modular X H 1 (X, Q). modular symbol M-symbol, ( ). 1.1. modular symbol., notation. H = z = x iy C y > 0, cusp H = H Q., Γ = PSL 2 (Z), G Γ [Γ : G]
(Requirements in communication) (efficiently) (Information Theory) (certainly) (Coding Theory) (safely) (Cryptography) I 1
(Requirements in communication) (efficiently) (Information Theory) (certainly) (oding Theory) (safely) (ryptography) I 1 (Requirements in communication) (efficiently) (Information Theory) (certainly) (oding
(Ryūta Hashimoto) α α p q < p/q α q Lagrange 0 0. 3.4.4.96.5.5.5.4 < 1/1 lim f(x, y) (x,y) (a,b) ( ) ( ) lim limf(x, y) lim lim f(x, y) x a y b y b x a ( ) ( ) xy x lim lim lim lim x y x y x + y y x x + y x x lim x x 1
1/5 ( ) Taylor ( 7.1) (x, y) f(x, y) f(x, y) x + y, xy, e x y,... 1 R {(x, y) x, y R} f(x, y) x y,xy e y log x,... R {(x, y, z) (x, y),z f(x, y)} R 3 z 1 (x + y ) z ax + by + c x 1 z ax + by + c y x +
untitled
[email protected] http://www.image.med.osaka-u.ac.jp/member/yoshi/ II Excel, Mathematica Mathematica Osaka Electro-Communication University (2007 Apr) 09849-31503-64015-30704-18799-390 http://www.image.med.osaka-u.ac.jp/member/yoshi/
x () g(x) = f(t) dt f(x), F (x) 3x () g(x) g (x) f(x), F (x) (3) h(x) = x 3x tf(t) dt.9 = {(x, y) ; x, y, x + y } f(x, y) = xy( x y). h (x) f(x), F (x
[ ] IC. f(x) = e x () f(x) f (x) () lim f(x) lim f(x) x + x (3) lim f(x) lim f(x) x + x (4) y = f(x) ( ) ( s46). < a < () a () lim a log xdx a log xdx ( ) n (3) lim log k log n n n k=.3 z = log(x + y ),
「産業上利用することができる発明」の審査の運用指針（案）
1 1.... 2 1.1... 2 2.... 4 2.1... 4 3.... 6 4.... 6 1 1 29 1 29 1 1 1. 2 1 1.1 (1) (2) (3) 1 (4) 2 4 1 2 2 3 4 31 12 5 7 2.2 (5) ( a ) ( b ) 1 3 2 ( c ) (6) 2. 2.1 2.1 (1) 4 ( i ) ( ii ) ( iii ) ( iv)
- 2 -
- 2 - - 3 - (1) (2) (3) (1) - 4 - ~ - 5 - (2) - 6 - (1) (1) - 7 - - 8 - (i) (ii) (iii) (ii) (iii) (ii) 10 - 9 - (3) - 10 - (3) - 11 - - 12 - (1) - 13 - - 14 - (2) - 15 - - 16 - (3) - 17 - - 18 - (4) -
2 1980 8 4 4 4 4 4 3 4 2 4 4 2 4 6 0 0 6 4 2 4 1 2 2 1 4 4 4 2 3 3 3 4 3 4 4 4 4 2 5 5 2 4 4 4 0 3 3 0 9 10 10 9 1 1
1 1979 6 24 3 4 4 4 4 3 4 4 2 3 4 4 6 0 0 6 2 4 4 4 3 0 0 3 3 3 4 3 2 4 3? 4 3 4 3 4 4 4 4 3 3 4 4 4 4 2 1 1 2 15 4 4 15 0 1 2 1980 8 4 4 4 4 4 3 4 2 4 4 2 4 6 0 0 6 4 2 4 1 2 2 1 4 4 4 2 3 3 3 4 3 4 4
1 (1) (2)
1 2 (1) (2) (3) 3-78 - 1 (1) (2) - 79 - i) ii) iii) (3) (4) (5) (6) - 80 - (7) (8) (9) (10) 2 (1) (2) (3) (4) i) - 81 - ii) (a) (b) 3 (1) (2) - 82 - - 83 - - 84 - - 85 - - 86 - (1) (2) (3) (4) (5) (6)
ASF-01
暗号モジュール試験及び認証制度 (JCMVP) 承認されたセキュリティ機能に関する仕様 平成 26 年 4 月 1 日独立行政法人情報処理推進機構 ASF-01 A p p r o v e d S e c u r i t y F u n c t i o n s 目次 1. 目的... 1 2. 承認されたセキュリティ機能... 1 公開鍵... 1 共通鍵... 3 ハッシュ... 4 メッセージ認証...
1 GDP Q GDP (a) (b) (c) (d) (e) (f) A (b) (e) (f) Q GDP A GDP GDP = Q 1990 GNP GDP 4095 3004 1091 GNP A Q 1995 7 A 2 2
/, 2001 1 GDP................................... 2 2.......................... 2 3.................................... 4 4........................................ 5 5.....................................
211 [email protected] 1 R *1 n n R n *2 R n = {(x 1,..., x n ) x 1,..., x n R}. R R 2 R 3 R n R n R n D D R n *3 ) (x 1,..., x n ) f(x 1,..., x n ) f D *4 n 2 n = 1 ( ) 1 f D R n f : D R 1.1. (x,
1: *2 W, L 2 1 (WWL) 4 5 (WWL) W (WWL) L W (WWL) L L 1 2, 1 4, , 1 4 (cf. [4]) 2: 2 3 * , , = , 1
![1: *2 W, L 2 1 (WWL) 4 5 (WWL) W (WWL) L W (WWL) L L 1 2, 1 4, , 1 4 (cf. [4]) 2: 2 3 * , , = , 1](/thumbs/49/25412084.jpg "1: *2 W, L 2 1 (WWL) 4 5 (WWL) W (WWL) L W (WWL) L L 1 2, 1 4, , 1 4 (cf. [4]) 2: 2 3 * , , = , 1")
I, A 25 8 24 1 1.1 ( 3 ) 3 9 10 3 9 : (1,2,6), (1,3,5), (1,4,4), (2,2,5), (2,3,4), (3,3,3) 10 : (1,3,6), (1,4,5), (2,2,6), (2,3,5), (2,4,4), (3,3,4) 6 3 9 10 3 9 : 6 3 + 3 2 + 1 = 25 25 10 : 6 3 + 3 3
I A A441 : April 15, 2013 Version : 1.1 I Kawahira, Tomoki TA (Shigehiro, Yoshida )
I013 00-1 : April 15, 013 Version : 1.1 I Kawahira, Tomoki TA (Shigehiro, Yoshida) http://www.math.nagoya-u.ac.jp/~kawahira/courses/13s-tenbou.html pdf * 4 15 4 5 13 e πi = 1 5 0 5 7 3 4 6 3 6 10 6 17
( [1]) (1) ( ) 1: ( ) 2 2.1,,, X Y f X Y (a mapping, a map) X ( ) x Y f(x) X Y, f X Y f : X Y, X f Y f : X Y X Y f f 1 : X 1 Y 1 f 2 : X 2 Y 2 2 (X 1
![( [1]) (1) ( ) 1: ( ) 2 2.1,,, X Y f X Y (a mapping, a map) X ( ) x Y f(x) X Y, f X Y f : X Y, X f Y f : X Y X Y f f 1 : X 1 Y 1 f 2 : X 2 Y 2 2 (X 1](/thumbs/91/105288755.jpg "( [1]) (1) ( ) 1: ( ) 2 2.1,,, X Y f X Y (a mapping, a map) X ( ) x Y f(x) X Y, f X Y f : X Y, X f Y f : X Y X Y f f 1 : X 1 Y 1 f 2 : X 2 Y 2 2 (X 1")
2013 5 11, 2014 11 29 WWW ( ) ( ) (2014/7/6) 1 (a mapping, a map) (function) ( ) ( ) 1.1 ( ) X = {,, }, Y = {, } f( ) =, f( ) =, f( ) = f : X Y 1.1 ( ) (1) ( ) ( 1 ) (2) 1 function 1 ( [1]) (1) ( ) 1:
2008 (2008/09/30) 1 ISBN 7 1.1 ISBN................................ 7 1.2.......................... 8 1.3................................ 9 1.4 ISBN.............................. 12 2 13 2.1.....................
i 1 1 1.1.......................................... 1 1.1.1......................................... 1 1.1.2...................................... 1 1.1.3....................................... 2 1.1.4......................................
ax 2 + bx + c = n 8 (n ) a n x n + a n 1 x n a 1 x + a 0 = 0 ( a n, a n 1,, a 1, a 0 a n 0) n n ( ) ( ) ax 3 + bx 2 + cx + d = 0 4
20 20.0 ( ) 8 y = ax 2 + bx + c 443 ax 2 + bx + c = 0 20.1 20.1.1 n 8 (n ) a n x n + a n 1 x n 1 + + a 1 x + a 0 = 0 ( a n, a n 1,, a 1, a 0 a n 0) n n ( ) ( ) ax 3 + bx 2 + cx + d = 0 444 ( a, b, c, d
2014 x n 1 : : :
2014 x n 1 : : 2015 1 30 : 5510113 1 x n 1 n x 2 1 = (x 1)(x+1) x 3 1 = (x 1)(x 2 +x+1) x 4 1 = (x 1)(x + 1)(x 2 + 1) x 5 1 = (x 1)(x 4 + x 3 + x 2 + x + 1) 1, 1,0 n = 105 2 1 n x n 1 Maple 1, 1,0 n 2
第122号.indd
-1- -2- -3- 0852-36-5150 0852-36-5163-4- -5- -6- -7- 1st 1-1 1-2 1-3 1-4 1-5 -8- 2nd M2 E2 D2 J2 C2-9- 3rd M3 E3 D3 J3 C3-10- 4th M4 E4 D4 J4 C4-11- -12- M5 E5 J5 D5 C5 5th -13- -14- NEWS NEWS -15- NEWS
漸化式のすべてのパターンを解説しましたー高校数学の達人・河見賢司のサイト
https://www.hmg-gen.com/tuusin.html https://www.hmg-gen.com/tuusin1.html 1 2 OK 3 4 {a n } (1) a 1 = 1, a n+1 a n = 2 (2) a 1 = 3, a n+1 a n = 2n a n a n+1 a n = ( ) a n+1 a n = ( ) a n+1 a n {a n } 1,
2 probably 3 probability theory probability theory (gàil`ü) 2 1960 2.1, 1: 583 589 666 1853 2967 2 3 1973
( ) ( C) 1 probability probability probable probable probable probable probably probably maybe perhaps possibly likely possibly
6. Euler x
...............................................................................3......................................... 4.4................................... 5.5......................................
f (x) f (x) f (x) f (x) f (x) 2 f (x) f (x) f (x) f (x) 2 n f (x) n f (n) (x) dn f f (x) dx n dn dx n D n f (x) n C n C f (x) x = a 1 f (x) x = a x >
5.1 1. x = a f (x) a x h f (a + h) f (a) h (5.1) h 0 f (x) x = a f +(a) f (a + h) f (a) = lim h +0 h (5.2) x h h 0 f (a) f (a + h) f (a) f (a h) f (a) = lim = lim h 0 h h 0 h (5.3) f (x) x = a f (a) =
96 7 1m =2 10 7 N 1A 7.1 7.2 a C (1) I (2) A C I A A a A a A A a C C C 7.2: C A C A = = µ 0 2π (1) A C 7.2 AC C A 3 3 µ0 I 2 = 2πa. (2) A C C 7.2 A A
7 Lorentz 7.1 Ampère I 1 I 2 I 2 I 1 L I 1 I 2 21 12 L r 21 = 12 = µ 0 2π I 1 I 2 r L. (7.1) 7.1 µ 0 =4π 10 7 N A 2 (7.2) magnetic permiability I 1 I 2 I 1 I 2 12 21 12 21 7.1: 1m 95 96 7 1m =2 10 7 N