본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

인수분해 전용 하드웨어 연구 동향

이상진   (고려대학교 정보보호대학원UU0000159  ); 김창한   (세명대학교 정보보호학과UU0000787  ); 장남수   (고려대학교 정보보호대학원UU0000159  ); 윤택영   (고려대학교 정보보호대학원UU0000159  );
  • 초록

    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 

 저자의 다른 논문

  • 이상진 (133)

    1. 1994 "수체 선별법(NFS) 알고리즘 실현에 관한 연구" Communications of the Korean Mathematical Society = 대한수학회논문집 9 (1): 241~251    
    2. 2001 "Practical and Provable Security against Differential and Linear Cryptanalysis for Substitution-Permutation Networks" ETRI journal 23 (4): 158~167    
    3. 2001 "27라운드 SKIP JACK에 대한 포화 공격" 情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology 11 (5): 85~96    
    4. 2002 "PKC'98에 제안된 해쉬 함수의 Original Version에 대한 전체 라운드 차분 공격" 情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology 12 (2): 65~76    
    5. 2002 "홀수 표수 확장체위의 타원곡선 고속연산" 情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology 12 (1): 81~88    
    6. 2002 "XTEA와 TEA의 축소된 라운드에 대한 불능 차분 공격" 情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology 12 (4): 77~85    
    7. 2002 "SHACAL의 축소 라운드에 대한 확장된 부메랑 공격" 情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology 12 (5): 87~93    
    8. 2002 "컴퓨터 포렌식스 기술" 情報保護學會誌 = KIISC review 12 (5): 8~16    
    9. 2002 "블록 암호에 대한 효율적인 선형 공격 방법" 情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology 12 (6): 59~69    
    10. 2002 "블라인드 XTR-DSA 스킴을 이용해 블랙메일링을 막는 효율적인 방법" 情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology 12 (6): 125~135    
  • Kim, Chang-Han (28)

  • 장남수 (13)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기