작은 CRT 지수를 사용한 RSA에서의 일부 키 노출 공격
Partial Key Exposure Attack on Unbalanced RSA with small CRT exponent
0
조회
0
다운로드
0
인용
0
참고문헌
초록
RSA 공개키 시스템은 비밀키의 크기를 작게 하여 효율성을 높이고 있는 데 이는 안전성 측면에서 취약하다. 이를 보완하기 위하여 중국인의 나머지 정리를 이용한 비밀키 생성 기법이 많이 이용되고 있다. 그러나 이러한 기법은 side channel attack 에 매우 취약하다. 따라서 일부 키 노출에 따른 전체 키 복원에 관한 연구가 활발히 진행되고 있다. May는 2003년 Crypto에서 두 소수의 크기는 같고 중국인의 나머지 정리를 이용하여 비밀키를 생성한 경우에 비밀키의 일부 비트가 노출되면 전체가 복원되는 것을 보였다. 또한, May는 2002년 Crypto에서 변형된 RSA형태 중의 하나인 두 소수의 크기가 다르고 작은 CRT(중국인의 나머지 정리) 지수를 이용한 RSA를 분석하였는데 이때 작은 소수의 크기가 보다 작으면 CRT 지수의 크기에 따라 이 소인수분해 될 수 있다고 경고하였다. 본 논문에서는 May의 두 소수의 크기가 다른 변형된 RSA(작은 소수의 크기가 보다 큰 경우)에서 작은 CRT 지수를 이용하여 비밀키를 생성한 경우에 어느 정도의 노출이 전체를 복원하게 하는지를 살펴본다. 공개키 가 너무 크지 않을 때 작은 소수 의 크기와 관계없이 비밀키 의 약 정도의 비트가 노출되면 이 소인수분해가 된다. 의 크기가 비슷할 때 의 약 비트만 노출이 되면 을 소인수분해 할 수 있다는 것을 Coppersmith가 보였는데 본 논문에서는 두 소수의 크기가 다를 때도 약 비트가 노출되면 소인수분해가 가능한 것을 보이고 이를 이용하여 위의 내용을 증명한다.
Abstract
In Crypto 2002 May analyzed the relation between the size of two primes and private key in unbalanced RSA with small CRT exponent. Also in Crypto 2003 he showed that if amount of most significant bits(least significant bits) of is exposed in balanced RSA with CRT, N can be factored. To prove this he used Howgrave-Graham's Theorem. In this paper we show that if amount of , is smaller than , and bigger than to avoid May's attack, is exposed in unbalanced RSA with small CRT exponent, it is enough to expose . We use Coppersmith's theorem with unbalanced primes.
참고문헌 (12)
- "Cryptanalysis of short RSA secret exponents", 36(3), pp.553~558 (1990)
- "Cryptanalysis of RSA with private key less than", 46(4) (2000)
- "ON the design of RSA with short secret exponent In proc. of Asiacrypt'99", 1716, pp.150~164 (1999)
- "Cryptanalysis of the RSA schemes with short Secret Exponent from Asiacrypt'99", 1976, pp.14~29 (2000)
- "Cryptanalysis of Unbalanced RSA with small CRT-exponent", pp.242~256 (2002)
- "Exposing an RSA Private Key Given a Small Fraction of its Bits" (1998)
- "Small Solutions to Polynomial Equations, and Low Expo-nent RSA vulnerabilities", 10(4) (1997)
- "New Partial Key Exposure Attacks on RSA", pp.27~43 (2003)
- "Approximate Integer Common Divisors", 2146, pp.51~66 (2001)
- "Twenty years of Attacks on the RSA Cryptosystem" (1999)
- "Finding small roots of univariate modular equations revisited" (1997)
- "RSA 암호방식의 안전성에 관한 연구", 8(4), pp.15~46 (1998)