초록

NP-Hard 문제인 정수의 소인수분해 알고리즘의 연구와 구현은 1978년 RSA 암호의 개발과 함께 암호학에서 중요한 문제로 부각되었으며 지난 25년간 이 분야에서 많은 발전이 이룩되었다. QS 인수분해 알고리즘과 NFS 인수분해 알고리즘이 최근까지도 RSA-challenge를 분석하기 위한 도구로 사용되었고, NFS가 가장 효율적인 것으로 알려져 있다. 그러나 인수분해 대상 정수의 크기가 커짐에 따라 기존의 소프트웨어 기반의 접근 방법으로 분석하는 것은 점차 어려워지고 있다. 99년도 CHES Rump Session에서 Shamir에 의해 제안된 TWINKLE은 인수분해 알고리즘의 연구에 새 지평을 마련하였다. TWINKLE는 기존과는 근본적으로 다른 접근 방법으로 수행되는 인수분해 전용 하드웨어 장비이다. TWINKLE이 발표된 이후 TWIRL와 SHARK 등 다양한 인수분해 전용 하드웨어들이 제안되었고, 이는 인수분해 방법론 연구에서 새로운 방향이 되고 있다. 본 논문에서는 이와 같은 인수분해 전용 하드웨어 연구 동향에 대해 살펴보고, 각 장비들의 효율성을 비교 분석하도록 한다.

저자의 다른 논문

참고문헌 (16)

1. R P Brent, Some Integer Factorization Algorithms using Elliptic Curves, Aus. Comp. Sci. Communications 8 (1986) pp 149-163 
2. Arjen K. Lenstra, Adi Shamir, Analysis and Optimization of the TWINKLE Factoring Device, proc. Eurocrypt 2002, LNCS 1807 35.52, Springer-Verlag, 2000 
3. R L Rivest, A Shamir and L Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.}, Communications of the ACM, 21(2) (1978) pp 120-126 
4. A Shamir, Factoring Large Numbers with the TWINKLE Device., Extended Abstract (1999) 
5. J Franke, T Kleinjung, C Paar, J Pelzl, C Priplata, C Stahlke, A Realizable Special Hardware Sieving Device for Factoring 1024-bit Integers, SHARC'06, pp.189-199, 2006 
6. Adi Shamir and Eran Tromer. Factoring Large Numbers with the TWIRL Device. Draft, February 9, 2003. Available via http://www.wisdom.weizmann.ac.il/~tromer 
7. D J. Bernstein, Circuits for integer factorization: a proposal, manuscript, 2001, http://cr.yp.to /papers.html 
8. Arjen K. Lenstra, Adi Shamir, Jim Tomlinson, Eran Tromer, Analysis of Bernstein's factorization circuit, proc. Asiacrypt 2002, LNCS 2501 1.26, Springer- Verlag, 2002 
9. 정창성, 김양희, 암호응용 문제를 위한 병렬 소인수분해 알고리즘에 관한 연구, 통신정보보호학회지 제 3장 제 2절, 1993 
10. R A Golliver, A K Lenstra and K S McCurley, Lattice Sieving and Trial Division., Algorithmic Number Theory - ANTS 94, LNCS 877 (1994) pp 18-27 
11. D J Bernstein and A K Lenstra, A General Number Field Sieve Implementation, The Development of the Number Field Sieve, LNM 1554 (1993) pp 103-125 
12. Willi Geiselmann, Rainer Steinwandt, A dedicated sieving hardware, proc. PKC 2003, LNCS 2567 254.266, Springer-Verlag, 2002 
13. C Pomerance, The Quadratic Sieve Factoring Algorithm., Advances in Cryptology - EUROCRYPT 84, LNCS 209 (1985) pp 169-182 
14. A Shamir, E Tromer, Special-Purpose Hardware for Factoring: the NFS Sieving Step, Invited talk at SHARCS'05, 2005 
15. R D Silverman, The multiple polynomial quadratic sieve., Math.Comp., Vol. 84 (1987) pp. 327-339 
16. RSA Laboratorie, Information on RSA Challenge, http://www.rsa.com/rsalabs/html/challenges.html 

이 논문을 인용한 문헌 (0)

1. 이 논문을 인용한 문헌 없음