KS X ISO IEC 18032-2007 Information technology－Security techniques－Prime number generation《信息技术 安全技术 素数生成》.pdf

1、 KS X ISO/IEC 18032 KSKSKSKS SKSKSKS KSKSKS SKSKS KSKS SKS KS KS X ISO/IEC 18032 ：2007 (2012 ) 2007 11 30 http:/www.kats.go.krKS X ISO/IEC 18032：2007 : e- ( ) ( ) () () ( ) : () ( ) () () JS ( ) KS X ISO/IEC 18032：2007 : (http:/www.standard.go.kr) ： ：2007 11 30 ：2012 12 31 2012-0848 ： e ： e ( 02-509

2、-7262) (http:/www.kats.go.kr). 10 5 , . KS X ISO/IEC 18032：2007 i ii iii 1 1 2 1 3 .2 4 .3 5 .3 6 .4 6.1 Miller-Rabin 4 6.2 Frobenius-Grantham 5 6.3 Lehmann .5 7 .6 7.1 6 7.2 Maurer 7 8 8 8.1 8 8.2 8 8.3 10 9 11 A() 12 A.1 .12 A.2 Miller-Rabin 13 A.3 Miller-Rabin 13 A.4 Frobenius-Grantham .13 A.5 Fr

3、obenius-Grantham .13 A.6 Lehmann .14 A.7 Lehmann .14 B() 15 B.1 .15 B.2 .15 B.3 RSA modulus .16 17 .18 KS X ISO/IEC 18032：2007 ii e . KS X ISO/IEC 18032：2007 . A() B() KS X ISO/IEC 18032 “ ” . KS X ISO/IEC 18032：2007 iii 2005 1 ISO/IEC 18032, Information technologySecurity techniquesPrime number gen

4、eration . ISO IEC . ISO IEC , . ISO IEC . , ISO IEC . . ISO/IEC JTC 1/SC 27 Standing Document 8 (SD 8) “ ” SD 8 http:/www.ni.din.de/sc27 . . ISO IEC . KS X ISO/IEC 18032：2007 (2012 ) Information technologySecurity techniquesPrime number generation 1 . . . (probabilistic) . , . (deterministic) . (pri

5、mality certificate) . . . , . . “ ” 1 . B . , , . . . Frobenius-Grantham . 2 . ( ) . ( ) ( .) . KS X ISO/IEC 97962：2005, 2： KS X ISO/IEC 18032：2007 2 KS X ISO/IEC 159461：2003, 1： 3 . 3.1 (composite number) N 1 , (trivial divisor) N . 3.2 (entropy) . . 3.3 Jacobi n a Jacobi n (prime factor) a Legendr

6、e ( Legendre ). KS X ISO/IEC 97962 A . 3.4 Legendre p , a . p a Legendre a (p1)/2 mod p . KS X ISO/IEC 97962 A . 3.5 (primality certificate) . (trial division) . . 3.6 (prime) N N 1 3.7 (pseudo-random bit generator) k l k , 3.8 (trial division) N N N . KS X ISO/IEC 18032：2007 3 3.9 (trivial divisor)

7、 N 1, 1, N, N , N . 4 a mod n a n , a mod n a n . C C(N) N C 0 (N) (empty) . , N . gcd g(x) mod (N, f(x) g(x) f(x) , (coefficient) N (modulo) k N L log b (a) (base) b a ln( ) (, e) M mina, b a, b N , n 0 (incremental search) n max T Z N N (ring) 0, 1, 2, , N1 Z N * N Z N (, N , 1, 2, ., N1 .) Z N x/

8、f(x) Z N f(x) x x (parameter) (step) 5 N . . 1. N p 1) N mod p = 0, “(reject)” . 2. “(accept)” . N , . L . L . 1 . , . KS X ISO/IEC 18032：2007 4 2 . L L= 10 3 . 6 N “ ” “ ” . N “ ” . , . , “” . Miller-Rabin Frobenius-Grantham N “ ” . Lehmann . . 6.1 Miller-Rabin N Miller-Rabin . 1. N1 = 2 t s t s .

9、s . Miller-Rabin t, s, N , “” “ ” 1 . 2 b N2 b . 1 N b . 1. 2 b N2 b . 2. y = b smod N . 3. y 1, y N1, . a. i = 1 b. i t, y N1 . i) y = y 2 mod N ii) y = 1, “” . iii) i = i1 c) y N1, “” . 4. “” . . 1 “ ” , . b smod N 1 . b smod N N1. i(0 i t) ( b s ) 2 imod N N1. “ ” . “ ” , . A KS X ISO/IEC 18032：2

10、007 5 6.2 Frobenius-Grantham Z N x/(f(x) (arithmetic) . f(x) (degree) 2 . . N Miller-Rabin . 1. N min50 000, N ( ) 2. N . , N . 3. 2 r s = N 2 1 r s() r, s, N , “” “ ” 1 . b c . 1. b, c Z N . gcd(b 2 4c, N) gcd(c, N) N (non-trivial divisor). N b 2 4c Jacobi 1 mod N, N c Jacobi 1 mod N. N . . 2. x (N

11、1)/2mod(N, x 2 bxc) 0 Z N . , N . 3. x N1 mod(N, x 2 bxc)=c . N . 4. x s mod(N, x 2 bxc) = 1, x 2 j smod(N, x 2 bxc)=1 (0 j r2) j . , N . N . 1 N Jacobi N 16. 2 9 . Frobenius-Grantham 1 Miller-Rabin 3 . 3 A . 6.3 Lehmann Lehmann . N 1 aZ N *：a (N1)/2= 1 mod N, aZ N *：a (N1)/2=1 mod N. Lehmann N t .

12、. 1. f =“(false)” . 2. t . a. 2 b N2 b . b. y = b (N1)/2mod N . c. y 1, y N1 “ ” . d. y =N1, f = “(true)” . 3. f =“” “ ”, “ ” . A . KS X ISO/IEC 18032：2007 6 7 (verification) . 2 . Maurer (8.3.1 ) . 2 , ( , ) . C 0 . . . Maurer , , . 7.1 KS X ISO/IEC 159461 . 1 . gcd(N, 6)=1 , r r (N 1/4 1) 2 . (non

13、-singular) y 2= x 3 axb modulo N r P 0 N . . r (recursion) . . , N . 2 N , . , . (, ), N . 7.1.1 gcd(N, 6)=1 N . 1. C = . 2. j = 0 . 3. r = N . r L r . 1. j = j1 2. t min= 2 4 ) 1 ( r KS X ISO/IEC 18032：2007 7 3. t, a, b P . a. t , t t min . b. E：y 2= x 3 axb mod r t c. P t E . 4. C j=(r, t, a, b, P

14、) . 5. C j C . 6. r = t r L , r . C. 3.b. 2 . 7.1.2 gcd(N, 6)=1 N C = C 1 , C 2 , , C k . , C i= (p i , r, a i , b i , P i ) , . p 1= N r k L . i = 1, 2, , k , . 1. gcd(p i , 6)=1 2. P i E：y 2= x 3 a i xb imod p i , 3. P i r i . 4. 1 i (p i 1/4 1) 2 , N . 7.2 Maurer 8.3.1 . Maurer . N =12Rq . q , q

15、R. a N1= 1 mod N gcd(a 2R 1, N) =1 a , N . N L . Proof(N) = (N, q, a) , (tuple) . q q N1 q 2(N1)/2 a 1 a N a N1 (mod N) =1 KS X ISO/IEC 18032：2007 8 gcd(a (N1)/q 1, N) = 1 N C(N) . N L C(N) =C 0 (N) N L, C(N) =“Proof(N), C(q)”, Proof(N) = (N, q, a). 8 2 . . . . Maurer . 8.1 k . 2 100 . B k 1/3 . (ab

16、solute bound) (relative bound) . 1 B =100, =12 . . , 2 k 1/3 k , . (seed) (pseudo random number generator) , (uncertainty) . , ( , RSA ) . (number field sieve algorithm) 2 k (modulus) 13. =12 , k 512( 512 ) . 2 A . . (conjecture) . 8.2 T 6. . T . A . 8.1 2 . . , . 8.2.1 KS X ISO/IEC 18032：2007 9 T . 1. 2 k1n max 1 , 2 . n 0 , n 0 , n 0 2, , n 0 2 . , n 0 . 1 . , T . (independent) . (trade-off) . “ ” , , . . =10 ln(2 k ) . , . 2 k . . ( A ) . , , , . KS X ISO/IEC 18032：2007 10 8.2.3 8.2.1 8.2.2 , 7.1.1 . 8.3 8.3.1 Maurer Maurer N (scratch) N . . 8.1 .