Vol. 26, No. 6, pp. 1401-1412,
12월.
2016
10.13089/JKIISC.2016.26.6.1401,
Full Text:
Keywords:
Multi-prime RSA,
Prime Power RSA,
Key Recovery,
factorization
Abstract
Multi-Prime RSA와 Prime Power RSA는 변형 RSA 시스템의 일종이며, 이 중에서 Multi-Prime RSA는 서로 다른 r(r>2)개의 소수 $p_1,p_2,{\cdots},p_r$에 대하여 $N=p_1p_2{\cdots}p_r$을, Prime Power RSA는 서로 다른 소수 p, q와 양의 정수 r(>1)에 대하여 $N=p^rq$를 각각 모듈러스로 사용한다. 본 논문에서는 Heninger와 Shacham에 의해 제안된 방법을 사용하여 이 시스템들에 대한 안전성을 분석하며 구체적으로, 만약 $p_1,p_2,{\cdots},p_r$의 전체 비트 중 $2-2^{1/r}$의 비율에 해당하는 비트가 랜덤하게 주어지면 $N=p_1p_2{\cdots}p_r$이 다항식 시간 안에 소인수분해될 수 있음을, 그리고 p, q의 전체 비트 중 $2-{\sqrt{2}}$의 비율에 해당하는 비트가 랜덤하게 주어지면 $N=p^rq$가 다항식 시간 안에 소인수분해될 수 있음을 각각 보인다. 또한 $N=p_1p_2p_3$, $N=p^2q$, $N=p^3q$에 적용한 실험 결과를 통해 본 논문의 결과를 검증한다.
Statistics
Show / Hide Statistics
Statistics (Cumulative Counts from December 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.
Cite this article
[IEEE Style]
Y. Baek, "Key Recovery Algorithm from Randomly-Given Bits of Multi-Prime RSA and Prime Power RSA," Journal of The Korea Institute of Information Security and Cryptology, vol. 26, no. 6, pp. 1401-1412, 2016. DOI: 10.13089/JKIISC.2016.26.6.1401.
[ACM Style]
Yoo-Jin Baek. 2016. Key Recovery Algorithm from Randomly-Given Bits of Multi-Prime RSA and Prime Power RSA. Journal of The Korea Institute of Information Security and Cryptology, 26, 6, (2016), 1401-1412. DOI: 10.13089/JKIISC.2016.26.6.1401.