비트 일부로부터 Multi-Prime RSA와 Prime Power RSA의 개인키를 복구하는 알고리즘
Key Recovery Algorithm from Randomly-Given Bits of Multi-Prime RSA and Prime Power RSA
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Multi-Prime RSA와 Prime Power RSA는 변형 RSA 시스템의 일종이며, 이 중에서 Multi-Prime RSA는서로 다른 개의 소수 에 대하여 을, Prime Power RSA는 서로 다른 소수 와 양의정수 에 대하여 를 각각 모듈러스로 사용한다. 본 논문에서는 Heninger와 Shacham에 의해 제안된 방법을 사용하여 이 시스템들에 대한 안전성을 분석하며 구체적으로, 만약 의 전체 비트 중 의 비율에해당하는 비트가 랜덤하게 주어지면 이 다항식 시간 안에 소인수분해될 수 있음을, 그리고 의 전체 비트중 의 비율에 해당하는 비트가 랜덤하게 주어지면 가 다항식 시간 안에 소인수분해될 수 있음을 각각 보인다. 또한 , , 에 적용한 실험 결과를 통해 본 논문의 결과를 검증한다.
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 for distinct primes and the Prime Power RSA uses the modulus for two distinct primes and a positive integer . 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 random portion of bits of is given, then can be factorized in the expected polynomial time and if the random fraction of bits of is given, then can be factorized in the expected polynomial time. The analysis is then validated with experimental results for , and .
참고문헌 (11)
- R. L. Rivest, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, 21(2), pp.120~126 (1978)
- R. L. Rivest, "Cryptographic Communications System and Method", US Patent 4,405,829, ~ (1983)
- T. Takagi, "“Fast RSA-type Cryptosystem Modulo pkq,” Advances in Cryptology, CRYPTO ’98", LNCS, 1462, pp.318~326 (1998)
- T. Takagi, "A Fast RSA-type Public-Key Primitive Modulo pkq Using Hensel Lifting", IEICE Transactions, 87-A(1), pp.94~101 (2004)
- D. Coppersmith, "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities", J. Cryptology, 10(4), pp.233~260 (1997)
- D. Boneh, "“Factoring n=prq for Large r,” Advances in Cryptology, CRYPTO ‘99", LNCS, 326(337), pp.326~337 (1999)
- N. Heninger, "“Reconstructing RSA Private Keys from Random Key Bits,” Advances in Cryptology, CRYPTO ‘09", LNCS, 5677, pp.1~17 (2009)
- M. J. Hinek, "On the Security of Some Variants of RSA", Ph. D, pp.2007
- RSA Security Inc., "Public-Key Cryptography Standards (PKCS) #1v2.1: RSA Cryptography Standard", ~ (2002)
- S. Sarkar, "Revisiting Prime Power RSA", Discrete Applied Mathematics, 203, pp.127~133 (2016)