<4D F736F F D20838A B F955C8E8682A982E796DA8E9F914F E718F9096BC816A5F E646F63>

Size: px

Start display at page:

Download "<4D F736F F D20838A B F955C8E8682A982E796DA8E9F914F E718F9096BC816A5F E646F63>"

みさきねぎたや
5 years ago
Views:

1 2008 年度版リストガイド ( 電子署名 ) 平成 21 年 3 月独立行政法人情報通信研究機構独立行政法人情報処理推進機構

2 DSA ECDSA DSA ECDSA RSASSA-PKCS1-v1 5 RSASSA-PSS RSASSA-PKCS1-v RSASSA-PSS i

3 (Digital Signature) FIPS Draft [FIPS186-3] ( ) DSA, ECDSA RSA PKCS#1 v.2.1 [PKCS1] (RSA ) RSASSA-PKCS1-v1 5, RSASSA-PSS MAC ( ) DSA ECDSA RSASSA-PKCS1-v1 5 RSASSA-PSS (PKI) (CA) (PKI) PKI 1

4 CA Bit Octet x00 0xff 0 1 ( ) ANS American National Standard CA Certification Authority CRYPTREC Cryptography Research and Evaluation Committees DSA Digital Signature Algorithm (specified in this Standard) ECDSA Elliptic Curve Digital Signature Algorithm specified in ANS X9.62 FIPS Federal Information Processing Standard NIST National Institute of Standards and Technology PKCS Public Key Cryptography Standard PKI Public Key Infrastructure PSS Probabilistic Signature Scheme 2

5 RBG Random Bit Generator; specified in SP RSA Algorithm developed by Rivest, Shamir and Adelman (specified in ANS X9.31 and PKCS #1) SHA Secure Hash Algorithm; specified in FIPS SP TTP NIST Special Publication Trusted Third Party ( ) sk M S M S sk ( ) pk M S ( ) pk pk M S pk S M pk VALID INVALID k sk pk sk 2 pk () 1 2 sk 3

6 M sk S 3 M S pk S M pk VALID INVALID [GMR84] pk 4 1. k pk 2. M i 5 S i i 1 i q S q S 3. M, S 3 M, S M {M i } i M, S, pk RSASSA-PKCS1-v1 5 RSASSA-PKCS1-v1 5 RSA RSASSA- PSS 3 4 k 5 (signing oracle) 4

7 RSASSA-PSS RSASSA-PSS RSA [BR93] RSA RSA (n, e) y Z n y ( 1/e) mod n 1 ( ) 5

8 1: DSA ECDSA RSASSA-PKCS1-v1 5 RSASSA-PSS RSA-PKCS#1 v2.1 RSA-PKCS#1 v2.1 ( 1) RSA ( 2) ( 3) 2048, , 256, 384, , , 3072 ( 4) 7 ( 1) ( 2) ( 3) CRYPTREC ( 4)DSA, ECDSA SHA-1 6

9 1.3.4 RSA-PKCS#1 v2.1 RSASSA-PKCS1-v1 5 RSASSA-PSS n 3 n 2 n 3 n NIST FIPS Draft ( ) 6 B.3.1 B.3.2 n p, q SP RSASSA-PSS salt 0 slen hlen ( ) EM (Encoded Message) 6 NIST FIPS Draft( ) Bleichenbacher [B06] RSASSA-PKCS1-v1 5 EM (Encoded Message) EM EM [OKW07] EM EM DSA NIST NIST FIPS FIPS Draft p 1024, 2048, 3072 SHA-1 SHA-224 SHA-256 ( ( CRYPTREC FIPS (+Change Notice 1) CRYPTREC p 2048 SHA-1 7

10 FIPS Draft FIPS (+Change Notice 1) DSA ECDSA ANS X9.62, FIPS Draft, SEC 1 ECDSA ECDSA ANS X9.62 ECDSA SEC 1 FIPS Draft ANS X9.62 DSA FIPS Draft ANS X9.62 8

11 DSA ECDSA a mod n = r : a n 0 r (n 1) r counter : DSA d : ECDSA domain parameter seed : g : DSA g q GF(p) Hash(M) : FIPS Draft FIPS index : g k : DSA ECDSA L : DSA p (L, N) : DSA L p N q M : m : ECDSA GF 2 m N : DSA q n : ECDSA n p : DSA 1 GF (p) q : DSA 1 p 1 Q : ECDSA (r, s) : DSA ECDSA r, s x : DSA y : DSA DSA DSA x k y 9

12 p : 2 L 1 < p < 2 L L p L q : 2 N 1 < q < 2 N (p 1) N q N g : 1 < g < p q mod p x : 0 < x < q [1, q 1] y : y = g x mod p k : 0 < k < q [1, q 1] FIPS Draft L, N p, q L = 1024, N = 160 L = 2048, N = 224 L = 2048, N = 256 L = 3072, N = 256 DSA FIPS CRYPTREC 256 (L, N) SP FIPS Draft (L, N) N N SP CA (L, N) DSA 6 L = 2048, N = 256 SP L, N L = 2048, N = L = 2048, N = L = 2048, N =

13 DSA p, q, g p, q domain parameter seed, counter (p, q, g, {domain parameter seed, counter}) CA (TTP: Trusted Third Party) FIPS Draft p, q Appendix A.1 L, N domain parameter seed, conter g Appendix A.2 x y SP x, y (p, q, g {, domain parameter seed, counter}) FIPS Draft Appendix B.1 SP FIPS Draft

14 3. 4. FIPS Draft 5. SP CA CA DSA k FIPS Draft k k 1 q 0 < k 1 < q 1 = (k 1 k) mod q k k k 1 FIPS Draft Appendix B.2 k k 1 k FIPS Draft Appendix B.2 12

15 N q M r, s r = (g k mod p) mod q z = Hash(M) N s = (k 1 (z + xr)) mod q s Hash(M) Appendix C.2 r k, p, q p, q k r k, k 1, r x s SP r s r = 0 s = 0 0 k (r, s) ID 3 CA M, r, s M, r, s y N q 1. 0 < r < q, 0 < s < q INVALID 2. w = (s ) 1 mod q. z = Hash(M ) N. u 1 = (zw) mod q. u 2 = ((r )w) mod q. v = (((g) u 1 (y) u 2 ) mod p) mod q. 13

16 (s ) 1 s mod q Appendix C.1 3. v = r VALID M = M, r = r, s = s v = r Appendix E 4. v = r 5. (1) ID (2) (3) (4) ECDSA ECDSA ECDSA (q, F R, a, b, domain parameter seed, G, n, h) q F R a b domain parameter seed G n h 2 G = (x G, y G ) G (cofactor) n 14

17 2: ECDSA n log 2 n (h) FIPS Draft n 5 ANS X9.62 h FIPS Draft GF p p 2 GF 2 m ECDSA Appendix D 3 1. P XXX 2. 2 B XXX 3. Koblitz K XXX XXX FIPS Draft ANS X9.62 ANS X9.62 G canonical ANS X9.62 G canonical element 1 FIPS Draft element G ECDSA FIPS Draft Hash FIPS CRYPTREC FIPS (Change Notice 1) SHA-1 CRYPTREC 256 n SP n n n 15

18 CA n 112 n CA 112 n SP n CA ECDSA G ECDSA d Q d Q SP ECDSA ECDSA d Q (q, F R, a, b, domain parameter seed, G, n, h) FIPS Draft Appendix B.4 Q = dg FIPS Draft ECDSA DSA DSA k k Appendix B.5 k 1 k n 0 < k 1 < n, 1 = (k 1 k) mod n k 1 k k 1 Appendix C.1 16

19 k 1 k FIPS Draft k 1 k FIPS Draft ECDSA (r, s) ANS X9.62 SP M 1. k [1, n 1] 2. r = x 1 mod n, (x 1, y 1 ) = kg r = z = Hash(M) n 4. s = k 1 (z + rd) mod n (r, s) FIPS Draft ANS X9.62 M, r, s M, r, s Q 1. r, s [1, n 1] INVALID 2. w = s 1 mod n 3. z = Hash(M ) n 4. u 1 = z w mod n, u 2 = r w mod n 5. (x 2, y 2 ) = u 1 G + u 2 Q 6. r = x 1 mod n VALID INVALID RSASSA-PKCS1-v1 5 RSASSA-PSS RSASSA-PKCS1-v1 5 RSASSA-PSS 17

20 d : RSA ( ) d P : p CRT 7 e d P 1 (mod(p 1)) d Q : q CRT ( ) e d Q 1 ( mod (q 1)) e : RSA EM : (Encoded Message) embits : EM emlen : EM GCD(.,.) : 2 Hash : hlen : Hash k : n 8 K : RSA LCM(.,,.) : m : 0, n 1 M : mask : MGF masklen : mask MGF : mgfseed : mlen : M n : RSA 9 n = p q (n, e) : RSA p, q : RSA n qinv : CRT q qinv 1 (mod p) p s : 0 s n 1 S : salt : RSASSA-PSS slen : RSASSA-PSS salt x : X : x xlen : X 0x : 16 0x (0x) e , 09, 0e : 2 : x x : : a b (mod n) n a b I2OSP OS2IP 7 (Chinise Reminder Theorem, CRT) 8 9 RSA PKCS#1 v2.1 3 n 2 p, q n = p q 18

21 I2OSP(x, xlen) x: xlen: X: xlen OS2IP(X) 1. x 256 xlen 2. x 256 xlen x = x xlen xlen 1 + x xlen xlen x x 0 x i 0 x i < 256 x 256 xlen X i x xlen i X = X 1 X 2... X xlen (1 i xlen) X: x: 1. X X 1 X 2... X xlen x xlen i X i (1 i xlen) 2. x = x xlen xlen 1 + x xlen xlen x x 0 3. x RSASSA-PKCS1-v1 5 RSASSA-PSS k 256 (2048 ) 384 (3072 ) CRT ( ) (n, e) (n, d) p, q: ( ) k/2 n = pq: ( ) k e: ( ) GCD(e, LCM(p 1, q 1)) = 1 d: ( ) e d 1 (modlcm(p 1, q 1)) CRT (n, e) (p, q, d P, d Q, qinv) d P = d mod p 1: ( ) d Q = d mod q 1: ( ) qinv: CRT q qinv 1 (mod p) p 19

22 : RSA PKCS#1 v2.1 k 256 (2048 ) 384 (3072 ) 128 (1024 ) 256 (2048 ) 384 (3072 ) RSASSA-PKCS1-v1 5 RSASSA-PSS RSASP1 (RSA ) RSAVP1(RSA ) RSASP1(K, m) K: RSA (n, d) (p, q, d P, d Q, qinv) m: 0 m n 1 s: 0 s n 1 K RSA 1. m [0, n 1] 2. s (a) K = (n, d) s = m d mod n (b) K = (p, q, d P, d Q, qinv) i. s 1 = m d P mod p, s 2 = m d Q mod q ii. h = (s 1 s 2 ) qinv mod p iii. s = s 2 + q h 3. s RSAVP1((n, e), s) (n, e): RSA s: 0 s n 1 m: 0 m n 1 (n, e) RSA 1. s [0, n 1] 2. m = s e mod n 3. m 20

23 1: EMSA-PKCS-v1 5 2: EMSA-PKCS-v RSASSA-PKCS1-v RSASSA-PKCS1-v1 5-SIGN RSASSA-PKCS1-v1 5- VERIFY RSASSA-PKCS1-v1 5-SIGN EMSA-PKCS-v1 5 RSASP1 RSASSA-PKCS1-v1 5-VERIFY EMSA-PKCS-v1 5 RSAVP1 EMSA-PKCS-v1 5 RSASSA-PKCS1-v1 5-SIGN RSASSA-PKCS1-v1 5-VERIFY EMSA-PKCS-v1 5(M, emlen) M: emlen: DER T 21

24 tlen emlen tlen + 11 Hash: hlen EM : emlen 1. H = Hash(M) 2. ID ANS.1 DigestInfo DER (Design Encoding Rules) T DigestInfo ::= SEQUENCE{ } digestalgorithm AlgorithmIdentifier, digest OCTET STRING T tlen T 3. emlen < tlen emlen tlen 3 PS 0xff PS 8 5. EM = 0x00 0x01 PS 0x00 T 6. EM DER T SHA-256: (0x) d H. SHA-384: (0x) d H. SHA-512: (0x) d H. : RSA PKCS#1 v2.1 Hash MD2 MD5 SHA-1 DER MD2 MD5 SHA-1 RSASSA-PKCS1-v1 5-SIGN(K, M) K: RSA M S: k k RSA n RSA 22

25 M Hash EM= PS 00 HID H 3: EMSA-PKCS-v EMSA-PKCS-v1 5 k EM = EMSA-PKCS-v1 5(M, k) EM RSA 2. RSA (a) OS2IP m = OS2IP(EM ) (b) RSASP I2OSP 4. S s = RSASP1(K, m) S = I2OSP(s, k) RSASSA-PKCS1-v1 5-VERIFY((n, e), M, S) (n, e): RSA M: S: k k RSA n 23

26 RSA 1. S k 2. RSA (a) OS2IP s = OS2IP(S) (b) RSAVP1 m = RSAVP1((n, e), s) m (c) I2OSP EM = I2OSP(m, k) EM 3. EMSA-PKCS-v1 5 k EM = EMSA-PKCS-v1 5(M, k) EM RSA 4. EM = EM : Bleichenbacher EM RSASSA-PSS 4 5 RSASSA-PSS-SIGN RSASSA-PSS-VERIFY RSASSA-PSS-SIGN EMSA-PSS-ENCODE RSASP1 RSASSA-PSS-VERIFY EMSA- PSS-VERIFY RSASSA-PSS-SIGN MGF EMSA- PSS-ENCODE EMSA-PSS-VERIFY RSASSA-PSS-SIGN RSASSA-PSS-VERIFY 24

27 4: EMSA-PKCS-v1 5 5: EMSA-PKCS-v1 5 MGF1(mgfSeed, masklen) mgfseed: masklen: masklen 2 32 hlen Hash: hlen mask: masklen 1. masklen > 2 32 hlen 2. T 3. counter 0 masklen/hlen (a) counter 4 C C = I2OSP (counter, 4) (b) mgfseed C T T = T Hash(mgfSeed C) 25

28 4. masklen T mask MGF1 id-mgf1 id-mgf1 OBJECT IDENTIFIER ::= {pkcs-1 8} AlgorithmIdentifier OID parameters MGF1 hashalgorithm EMSA-PSS-ENCODE(M, embits) M: embits: embits 8hLen + 8sLen + 9 Hash: hlen MGF1: slen: salt EM : emlen = embits/8 1. M 2. hlen mhash = Hash(M) 3. emlen < hlen + slen slen salt slen = 0 salt hlen + slen M = (0x) mhash salt 8 0x00 6. H = Hash(M ) H hlen 7. emlen slen hlen 2 0x00 PS PS 0 8. emlen hlen 1 DB = PS 0x01 salt 9. dbmask = MGF1(H, emlen hlen 1) 10. maskeddb = DB dbmask 11. maskeddb 8emLen embits EM = maskeddb H 0xbc 13. EM 26

29 M Hash M = padding 1 mhash salt DB= padding 2 salt MGF Hash EM= maskeddb H bc 6: EMSA-PSS-ENCODE EMSA-PSS-VERIFY(M, EM, embits) M: EM : emlen = embits/8 embits: embits 8hLen + 8sLen + 9 Hash: hlen MGF1: slen: salt 1. M 2. hlen mhash = Hash(M) 3. emlen < hlen + slen EM 0xbc 5. EM emlen hlen 1 maskeddb hlen H 6. maskeddb 8emLen embits 0 27

30 7. dbmask = MGF1(H, emlen hlen 1) 8. DB = maskeddb dbmask 9. DB 8emLen embits DB emlen hlen slen emlen hlen slen 1 0x DB slen salt hlen + slen M = (0x) mhash salt 8 0x H = Hash(M ) H hlen 14. H = H RSASSA-PSS-SIGN(K, M) K: RSA M: S: k k RSA n 1. EMSA-PSS-ENCODE k EM = EMSA-PSS-ENCODE(M, k) EM RSA 2. RSA (a) OS2IP m = OS2IP(EM ) (b) RSASP I2OSP 4. S s = RSASP1(K, m) S = I2OSP(s, k) 28

31 RSASSA-PSS-VERIFY((n, e), M, S) (n, e): RSA M: S: k k RSA n 1. S k 2. RSA (a) OS2IP s = OS2IP(S) (b) RSAVP1 m = RSAVP1((n, e), s) m (c) I2OSP EM = I2OSP(m, emlen) EM 3. EMSA-PSS-VERIFY Result = EMSA-PSS-VERIFY(M, EM, embits 1) 4. Result = 29

32 [BR93] Mihir Bellare, Phillip Rogaway, Random Oracles are Practical: A Paradigm for Designing Efficient Protocols, ACM Conference on Computer and Communications Security 1993, pp , 1993 [BR96] Mihir Bellare, Phillip Rogaway, The Exact Security of Digital Signatures - How to Sign with RSA and Rabin, EUROCRYPT 1996, pp , 1996 [B06] Daniel Bleichenbacher, Forging Some RSA Signatures with Pencil and Paper, presentation in the rump session, CRYPTO 2006, 2006 [GMR88] Shafi Goldwasser, Silvio Micali, Ronald L. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM J. Comput. 17(2), pp , 1988 [OKW07] Yutaka Oiwa, Kazukuni Kobara, Hajime Watanabe, New Variant for an Attack Against RSA Signature Verification Using Parameter Field, Proceedings of EuroPKI 2007, pp , [RSA78] Ronald L. Rivest, Adi Shamir, Leonard M. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Commun. ACM 21(2), pp , 1978 [ANS X9.62] ANSI, ANS X , Public Key Cryptography for Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA). [FIPS186-3] NIST, FIPS DRAFT Digital Signature Standard (DSS), [PKCS1] RSA Laboratories, PKCS #1: RSA Cryptography Standard, 30

33 不許複製禁無断転載発行日 2009 年 5 月 14 日第 1 版第 1 刷発行者東京都小金井市貫井北四丁目 2 番 1 号独立行政法人情報通信研究機構 ( 情報通信セキュリティ研究センターセキュリティ基盤グループ ) NATIONAL INSTITUTE OF INFORMATION AND COMMUNICATIONS TECHNOLOGY NUKUI-KITAMACHI,KOGANEI TOKYO, JAPAN 東京都文京区本駒込二丁目 28 番 8 号独立行政法人情報処理推進機構 ( セキュリティセンター暗号グループ ) INFORMATION-TECHNOLOGY PROMOTION AGENCY, JAPAN HONKOMAGOME,BUNKYO-KU TOKYO, JAPAN

<4D F736F F D20838A B F955C8E8682A982E796DA8E9F914F5F A815B FD B A5F E646F63>

<4D F736F F D20838A B F955C8E8682A982E796DA8E9F914F5F A815B FD B A5F E646F63> 2008 年度版リストガイド ( メッセージ認証コード ) 平成 21 年 3 月独立行政法人情報通信研究機構独立行政法人情報処理推進機構 1 1 1.1............................. 1 1.1.1............................ 1 1.1.2....................... 1 1.1.3...........................