GNFS를 위한 향상된 다항식 선택 기법

Vol. 26, No. 5, pp. 1121-1130, 10월. 2016
10.13089/JKIISC.2016.26.5.1121, Full Text:
Keywords: GNFS, CADO-NFS, Polynomial Selection
Abstract

RSA 암호 시스템은 가장 널리 사용되는 공개키 암호 알고리즘 중 하나이며, RSA 암호 시스템의 안전성은 큰 수의 인수분해의 어려움에 기반을 둔다. 따라서 RSA 암호 시스템의 합성수 n을 인수분해하려는 시도는 계속 진행 중에 있다. General Number Field Sieve는 현재까지 알려진 가장 빠른 인수분해 방법이고, RSA-704를 인수분해 하는데 사용된 소프트웨어인 CADO-NFS도 GNFS를 기반으로 설계되어 있다. 그러나 CADO-NFS는 다항식 선택 과정에서 입력된 변수로부터 항상 최적의 다항식을 선택하지 못하는 문제점이 있다. 본 논문에서는 CADO-NFS의 다항식 선택 단계를 분석하고 중국인의 나머지 정리와 유클리드 거리를 사용하여 다항식을 선택하는 방법을 제안한다. 제안된 방법을 이용하면 기존의 방법보다 좋은 다항식이 매번 선택되며, RSA-1024를 인수분해 하는데 적용할 수 있을 것으로 기대한다.

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]
S. Kim, J. Kwon, S. Cho, N. S. Chang, K. Yoon, C. Han, Y. Park and S. Hong, "Enhanced Polynomial Selection Method for GNFS," Journal of The Korea Institute of Information Security and Cryptology, vol. 26, no. 5, pp. 1121-1130, 2016. DOI: 10.13089/JKIISC.2016.26.5.1121.

[ACM Style]
Suhri Kim, Jihoon Kwon, Sungmin Cho, Nam Su Chang, Kisoon Yoon, Chang Han, Young-Ho Park, and Seokhie Hong. 2016. Enhanced Polynomial Selection Method for GNFS. Journal of The Korea Institute of Information Security and Cryptology, 26, 5, (2016), 1121-1130. DOI: 10.13089/JKIISC.2016.26.5.1121.