비트 일부로부터 Multi-Prime RSA와 Prime Power RSA의 개인키를 복구하는 알고리즘

국문 초록 (Abstract)

Multi-Prime RSA와 Prime Power RSA는 변형 RSA 시스템의 일종이며, 이 중에서 Multi-Prime RSA는 서로 다른 r(r >2)개의 소수 p1, p2, ...pr에 대하여 N = p1p2...pr을, Prime Power RSA는 서로 다른 소수 p,q와 양의 정수 r(r >1)에 대하여 N = p<SUP>r</SUP> q를 각각 모듈러스로 사용한다. 본 논문에서는 Heninger와 Shacham에 의해 제안된 방법을 사용하여 이 시스템들에 대한 안전성을 분석하며 구체적으로, 만약 p1, p2, ...pr의 전체 비트 중 2-2<SUP>1/r</SUP>의 비율에 해당하는 비트가 랜덤하게 주어지면  N=p1 p2 ...pr 이 다항식 시간 안에 소인수분해될 수 있음을, 그리고 p,q의 전체 비트 중 2-√2의 비율에 해당하는 비트가 랜덤하게 주어지면 N= p<SUP>r</SUP>q가 다항식 시간 안에 소인수분해될 수 있음을 각각 보인다. 또한 N = p1p2p3, N= p<SUP>2</SUP>q, N=p<SUP>3</SUP>q 에 적용한 실험 결과를 통해 본 논문의 결과를 검증한다.

다국어 초록 (Multilingual Abstract)

The Multi-Prime RSA and the Prime Power RSA are the variants of the RSA cryptosystem, where the Multi-Prime RSA uses the modulus p1p2 ...pr for distinct primes p1, p2, ...pr(r >2) and the Prime Power RSA uses the modulus N= p<SUP>r</SUP>q for two distinct primes p,q and a positive integer r(>1). This paper analyzes the security of these systems by using the technique given by Heninger and Shacham. More specifically, this paper shows that if the 2-2<SUP>1/r</SUP> random portion of bits of p1, p2, ...pr is given, then N = p1p2...pr can be factorized in the expected polynomial time and if the 2-√2 random fraction of bits of p,q is given, then N = p<SUP>r</SUP>q can be factorized in the expected polynomial time. The analysis is then validated with experimental results for N = p1p2p3, N= p<SUP>2</SUP>q and N=p<SUP>3</SUP>q.

목차 (Table of Contents)

• 요약
• ABSTRACT
• I. 서론
• II. 사전 지식
• III. Multi-Prime RSA와 Prime Power RSA에 대한 키 복구 알고리즘
• IV. 실험결과
• V. 결론
• References

참고문헌 (Reference)

1 N. Heninger, "“Reconstructing RSA Private Keys from Random Key Bits,” Advances in Cryptology, CRYPTO ‘09" 5677 : 1-17, 2009

2 T. Takagi, "“Fast RSA-type Cryptosystem Modulo pkq,” Advances in Cryptology, CRYPTO ’98" 1462 : 318-326, 1998

3 D. Boneh, "“Factoring n=prq for Large r,” Advances in Cryptology, CRYPTO ‘99" 326 (326): 326-337, 1999

4 D. Coppersmith, "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities" 10 (10): 233-260, 1997

5 S. Sarkar, "Revisiting Prime Power RSA" 203 : 127-133, 2016

6 RSA Security Inc., "Public-Key Cryptography Standards (PKCS) #1v2.1: RSA Cryptography Standard"

7 M. J. Hinek, "On the Security of Some Variants of RSA" University of Waterloo 2007

8 "NTL: A Library for Doing Number Theory"

9 R. L. Rivest, "Cryptographic Communications System and Method"

10 R. L. Rivest, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" 21 (21): 120-126, 1978

11 T. Takagi, "A Fast RSA-type Public-Key Primitive Modulo pkq Using Hensel Lifting" 87-A (87-A): 94-101, 2004