삭제와 오류로부터 RSA 개인키를 복구하는 알고리즘
Recovering RSA Private Key Bits from Erasures and Errors
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
현재 가장 많이 사용되고 있는 공개키 암호 알고리즘인 RSA에 대하여, 만약 암·복호문 이외의 부가 정보가 주어진경우 이를 이용해 RSA 시스템의 안전성을 분석하는 것은 부채널 공격, 격자 기반 공격 등에서 많이 다루어지고 있다. 최근에는 전원이 차단된 DRAM의 데이터 유지 성질을 이용한 Cold Boot Attack에서도 이러한 부가 정보를 이용한RSA 개인키 복구 방법이 많이 연구되고 있다. 본 논문에서는 전체 비트 중 일부 비트는 삭제가 되고 동시에 일부 비트에는 오류가 있는 RSA 개인키가 주어진 경우 원래의 개인키를 복구하는 문제를 다루며, 구체적으로는 이전에 제안된Kunihiro 등의 알고리즘과 비교하여 그 성능이 향상된 새로운 RSA 개인키 복구 알고리즘을 제안한다.
Abstract
Under the assumption that there is available some additional information other than plaintext-ciphertext pairs, the security of the RSA cryptosystem has been analyzed by the attack methods such as the side-channel attacks and the lattice-based attacks. Recently, based on the data retention property of the powered-off DRAMs, the so called cold boot attack was proposed in the literature, which is focusing on recovering the various cryptosystems’ key from some auxiliary information. This paper is dealing with the problem of recovering the RSA private key with erasures and errors and proposes a new key recovery algorithm which is shown to have better performance than the previous one introduced by Kunihiro et al.
참고문헌 (14)
- R. Rivest, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Commu nications of the ACM, 21(2), pp.120~126 (1978)
- M. Wiener, "Cryptanalysis of short RSA secret exponents", IEEE Trans. on Inform ation Theory, 36, pp.553~558 (1998)
- D. Boneh, "Cryptanalysis of RSA with private key d less than N0. 292", IEEE Trans. on Information Theory, 46, pp.1339~1349 (2000)
- D. Coppersmith, "Small solutions to polyn omial equations, and low exponent RSA vulnerabilities", J. Cryptology, 10(4), pp.233~260 (1997)
- P. Kocher, "Timing attacks on implement ations of Diffie-Hellman, RSA, DSS, and other systems", CRYPTO ‘96, LNCS, 1109, pp.104~113 (1996)
- P. Kocher, "Differenti al power analysis", CRYPTO ‘99, LNCS, 1666, pp.388~397 (1999)
- J. A. Halderman, "Lest we remember : cold boot atta cks on encryption keys", USENIX Securit y Symposium, pp.45~60 (2008)
- N. Heninger, "Reconstru cting RSA private keys from random key bits", CRYPTO ‘09, LNCS, 5677, pp.1~17 (2009)
- W. Henecka, "Corr ecting Errors in RSA Private Keys", CRYP TO ‘10, LNCS, 6223, pp.351~369 (2010)
- K. Paterson, "A Coding-Theoretic Approach to Recovering Noisy RSA Keys", ASIACRY PT 2012, LNCS, 7658, pp.386~403 (2012)
- S. Sarkar, "Side channel attack to actual cryptanalysis : Breaking CRT-RSA with low weight decryption exp onents", CHES 2012, LNCS, 7428, pp.476~493 (2012)
- N. Kunihiro, "Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors", PKC 2013, LNCS, 7778, pp.180~197 (2013)
- RSA Security INc, "Public-Key Cryptogr aphy Standards (PKCS) #1 v2.1 RSA Cryp tography Standard", ~ (2002)
- W. Hoeffding, "Probability inequalities fo r sums of bounded random variables", Journal of the American Statistical Association, 58(301), pp.13~30 (1963)