ESIGN-TSH 10 NTT 2002 5 23
1 3 2 4 3 4 31 (I2BSP) 4 32 (BS2IP) 6 33 (BS2OSP) 6 34 (OS2BSP) 7 35 (I2OSP) 7 36 (OS2IP) 8 4 8 41 ESIGN 8 42 ESIGN 9 5 9 51 KGP-ESIGN-TSH 9 52 SP-ESIGN-TSH 9 53 VP-ESIGN-TSH 10 6 11 61 SSA-ESIGN-TSH 11 611 11 612 11 7 12 71 EMSA-ESIGN-TSH 12 711 12 712 13 8 13 81 14 811 SHA-1 14 82 14 821 MGF1 14 A 16 B 16 C 16 2
1,, ESIGN-TSH, IEEE P1363a / D10 [1] IFSP-ESIGN, IFVP-ESIGN, EMSA5, ESIGN-TSH, SSA-ESIGN-TSH-Sign SSA-ESIGN-TSH-Verify, KGP-ESIGN-TSH SP-ESIGN-TSH VP-ESIGN-TSH EMSA-ESIGN-TSH 3
2 0 1 0 255 R Z N a = b b a, a b (B 0, B 1,, B i 1 ) 2 i N, i, (0, 1, 0, 0) 2 (M 0, M 1,, M i 1 ) 256 i N, i, (170, 255, 00) 256 {0, 1} i i N, i i = 0, {0, 1} {0, 1} i i=0 {0, 1,, 255} i i N, i i = 0, {0, 1,, 255} {0, 1,, 255} i y y [X] y GCD(a, b) a b a mod m a 1 mod m i=0, (0, 1, 0, 0) 2 (1, 1, 0) 2 = (0, 1, 0, 0, 1, 1, 0) 2, (170, 255) 256 (0, 20) 256 = (170, 255, 0, 20) 256, y R, y y R, y y N, X y a N, b N, a b a Z, b Z, a b a Z, m N, m (b a) b a Z, m N, ab mod m = 1 b 3, 1 31 (I2BSP), 2 I2BSP(x, l) x, l, 4
n =, M i {0, 1,, 255} 8 M = M 0 M 1 M n 1 I2OSP(x, l) OS2IP(M, l) x B = B 0 B 1 B l 1 B i {0, 1} BS2IP(B, l) I2BSP(x, l) BS2OSP(B, l) OS2BSP(M, l) 1 B l INVALID 1 l = 0, 2 x 2 l, INVALID 3 0 i l 1 i x 2 x i {0, 1} x = x l 1 2 l 1 + x l 2 2 l 2 + + x 1 2 + x 0 4 0 i l 1 i B i = x l 1 i 5 B B = B 0 B 1 B l 1 5
32 (BS2IP), 2 BS2IP(B, l) B l B, x B = B 0 B 1 B l 1 x 1 l = 0, 0 2 B i 0 1, 0 i l 1 i x i = B i l 1 x = 2 (l 1 i) x i 3 x i=0 33 (BS2OSP), 8 0, 8 BS2OSP(B, l) B l B, M n = 8 B = B 0 B 1 B l 1 M = M 0 M 1 M n 1 1 l = 0, 2 0 < i n 1 i M i = B l 8 8(n 1 i) B l 7 8(n 1 i) B l 1 8(n 1 i) 3 M 0 { B0 B 1 B 7 (8n l = 0) M 0 = ZB 0 B 1 B l+7 8n (8n l 0),, Z 8n l, 0 (Z = (0, 0,, 0) 2 ) 6
4 M 34 (OS2BSP), OS2BSP(M, l) M n = 8 l, B l M = M 0 M 1 M n 1 B = B 0 B 1 B l 1 1 l = 0, 2 0 < i n 1 i B l 8 8(n 1 i) B l 7 8(n 1 i) B l 1 8(n 1 i) = M i 3 0 j l+7 8n i, B j = Z j+8n l, Z 0 Z 1 Z 7 = M 0 4 B 35 (I2OSP), 256 I2OSP(x, l) x, l x, M n = 8 INVALID 1 l = 0, 2 x 2 l, INVALID 7
3 0 i n 1 i x 256 x i {0,, 255} x = x n 1 2 8(n 1) + x n 2 2 8(n 2) + + x 1 2 8 + x 0 4 0 i n 1 i M i = x n 1 i 5 M M = M 0 M 1 M n 1 36 (OS2IP), 256 OS2IP(M, l) M n = 8 l x, x M = M 0 M 1 M n 1 x 1 l = 0, 0 2 M i 0 255, 0 i l 1 i x i = M i 3 x x = n 1 i=0 2 8(n 1 i) x i mod 2 l 4, ESIGN ESIGN 2 41 ESIGN ESIGN 5 p q n, plen, e, 8
ESIGN 2 plen 1 < p < 2 plen, 2 plen 1 < q < 2 plen, n = p 2 q, 2 3pLen 1 < n < 2 3pLen 42 ESIGN ESIGN 3 n, plen, e, ESIGN 2 3pLen 1 < n < 2 3pLen 5, 3 51 KGP-ESIGN-TSH KGP-ESIGN-TSH(k, e) k, e, P K ESIGN (n, plen, e) SK ESIGN (p, q, n, plen, e) INVALID 1 e e < 8, INVALID 2 2 k 1 < p < 2 k, 2 k 1 < q < 2 k, p q, 2 3k 1 < p 2 q < 2 3k p, q, n = p 2 q 3 plen = k 4 P K = (n, plen, e), SK = (p, q, n, plen, e) 52 SP-ESIGN-TSH SP-ESIGN-TSH(SK, f), 9
SK ESIGN (p, q, n, plen, e) f, 0 f < 2 plen 1 s, 0 s < n INVALID SK 1 f 0 f < 2 plen 1, INVALID 2 z = f 2 2pLen 3 GCD(r, n) = 1 r {1, 2,, pq 1} 4 α = (z r e ) mod n 5 (w 0, w 1 ) α w 0 =, pq w 1 = w 0 pq α 6 w 1 w 1 2 2pLen 1, 3 7 t = w 0 (er e 1 ) 1 mod p, s = r + tpq 8 s, 53 VP-ESIGN-TSH VP-ESIGN-TSH(P K, s), P K ESIGN (n, plen, e) s, 0 s < n f, 0 f < 2 plen 1 INVALID P K 1 s 0 s < n, INVALID 2 T = s e mod n T 3 f = 2 2pLen 4 f 0 f < 2 plen 1, INVALID 5 f 10
, 6, 1 61 SSA-ESIGN-TSH SSA-ESIGN-TSH, SP-ESIGN-TSH, VP-ESIGN-TSH EMSA-ESIGN-TSH 611 SSA-ESIGN-TSH-Sign(SK, M), SK ESIGN M, s, 0 s < n INVALID 1 EMSA-ESIGN-TSH-Encode (711 ), M f f = EMSA-ESIGN-TSH-Encode(M, plen 1), INVALID, INVALID 2 SP-ESIGN-TSH (52 ), SK f s s = SP-ESIGN-TSH(SK, f) 3 s 612 SSA-ESIGN-TSH-Verify(P K, M, s), P K ESIGN M,, s, 0 s < n VALID SIGNATURE INVALID SIGNATURE 11
1 VP-ESIGN-TSH (53 ), P K s f f = VP-ESIGN-TSH(P K, s), INVALID, INVALID SIGNATURE 2 EMSA-ESIGN-TSH-Verify (712 ), f M Result = EMSA-ESIGN-TSH-Verify(M, f, plen 1), Result CONSISTENT, VALID SIGNATURE, INVALID SIGNATURE 7, 1 71 EMSA-ESIGN-TSH, IEEE P1363a / D10 [1] EMSA5 711 EMSA-ESIGN-TSH-Encode(M, l), Hash hlen, MGF M, l, f, INVALID 1, M, INVALID hlen 2 M, H 8 H = Hash(M) 3 H, T 8 T = MGF (H, l) 12
4 T f 5 f f = OS2IP(T, l) 712 EMSA-ESIGN-TSH-Verify(M, f, l), Hash hlen, MGF M, f, l f, CONSISTENT INVALID 1 f, T T = I2BSP(f, l), I2BSP INVALID, INVALID 2, M, INVALID hlen 3 M, H 8 H = Hash(M) 4 H, T 8 T = MGF (H, l) 5 T T T = OS2BSP(T, l) 6, T T, CONSISTENT, INVALID 8, 13
81, SHA-1 811 SHA-1 SHA-1 FIPS PUB 180-1 [2] SHA-1 160, 512 82, MGF1 [3] 821 MGF1 MGF1 MGF1(M, l) Hash hashlen, M, l, mask, 8 INVALID 1 l 0 M, l 0 + 32, INVALID 2 cthreshold = l hashlen 3 M 4 counter = 0 (a) counter 32 C C = I2OSP(counter, 32) hashlen (b) M C, 8 H H = Hash(M C) (c) M H, M M = M H 14
(d) counter 1 counter < cthreshold, 4a 5 M mask 8 mask = M 0M 1 M l/8 1 6 mask [1] IEEE P1363a / D10 (Draft Version 10), Standard Specifications for Public Key Cryptography Additional Techniques,, IEEE, to be appeared [2] FIPS PUB 180-1, Secure Hash Standard (SHS), US Department of Commerce / National Institute of Standards and Technology, April 17, 1995 [3] RSA Laboratories, PKCS #1 v21 RSA Encryption Standard, draft 2, January 5, 2001 15
A ESIGN-TSH k 342 (n 1024 ) e 8 B ESIGN-TSH k = 384 (n 1152) e = 1024 Hash = SHA-1 hlen = 160 MGF = MGF1(SHA-1, hashlen = 160) C ESIGN-TSH, M 1 ESIGN-TSH CMA OM-CMA ( ESIGN Theorem 23 ), M 0,,,, 1 OT, M = M 0 OT (OT 1 ) OT 20 OT = I2OSP(c, 160) c, 0 c < 2 160 20 OT = I2OSP(ps, 160) ps 1970 1 1 000000000000000000 UTC ( ), 0 ps < 2 160 16
20 OT = I2OSP(r, 160) r, 0 r < 2 160 17