$\require{mediawiki-texvc}$

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

인수분해 전용 하드웨어 연구 동향 원문보기

情報保護學會誌 = KIISC review, v.16 no.4, 2006년, pp.7 - 14  

이상진 (고려대학교 정보보호대학원) ,  김창한 (세명대학교 정보보호학과) ,  장남수 (고려대학교 정보보호대학원) ,  윤택영 (고려대학교 정보보호대학원)

초록
AI-Helper 아이콘AI-Helper

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

AI 본문요약
AI-Helper 아이콘 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

  • 본 논문에서는 인수분해 연구에서 새로운 방향을 제 시한 시빙 하드웨어 설계 기술 관련 연구 동향에 대해 살펴보고 각 장비의 효율성을 비교한다.
  • 어떤 정수가 주어진 인수 기저 집합의 원소들로 인수 분해가 되는 경우에 그 정수를 smooth 하다고 하자. 본 논문에서는 특정 알고리즘을 대상으로 시빙 단계를 설명하지 않고 일반적인 개념만 설명하도록 한다. 우선 B를 smoothness의 기준이 되는 경계값 (boundary)보다 작은 소수로 구성된 인수 기저라고 하자.
  • 본 소절에서는 1년 이내에 1024Bit 합성 수를 인수 분해하는데 필요한 시빙을 할 수 있는 특수 목적 하드웨어 SHARK에 대하여 기술한다〔5〕.
  • 본 소절에서는 TWIRL (The Weizmann Institute Relation Locator) 하드웨어 설계 기법에 관하여 기술한다〔14〕.(표준 0.
  • 본 절에서는 NFS에서 가장 큰 시간과 비용을 필요로 하는 시빙 연산부의 하드웨어 구성에 관하여 논한다. 시빙 하드웨어로는 대표적으로 TWINKLE, TWIRL, SHARK 등이 있다.
  • 시빙 전용 하드웨어 장비에 대한 논의를 진행하기에 앞서 시빙을 기반으로 수행되는 인수분해 알고리즘에 대해 간략히 살펴보도록 하자.
  • 본 논문에서는 특정 알고리즘을 대상으로 시빙 단계를 설명하지 않고 일반적인 개념만 설명하도록 한다. 우선 B를 smoothness의 기준이 되는 경계값 (boundary)보다 작은 소수로 구성된 인수 기저라고 하자. 3의 원소들로 완전히 나누어지는 정수는 smoothness를 만족한다고 정의된다.
본문요약 정보가 도움이 되었나요?

참고문헌 (16)

  1. 정창성, 김양희, 암호응용 문제를 위한 병렬 소인수분해 알고리즘에 관한 연구, 통신정보보호학회지 제 3장 제 2절, 1993 

  2. 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 

  3. D J. Bernstein, Circuits for integer factorization: a proposal, manuscript, 2001, http://cr.yp.to /papers.html 

  4. R P Brent, Some Integer Factorization Algorithms using Elliptic Curves, Aus. Comp. Sci. Communications 8 (1986) pp 149-163 

  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. Willi Geiselmann, Rainer Steinwandt, A dedicated sieving hardware, proc. PKC 2003, LNCS 2567 254.266, Springer-Verlag, 2002 

  7. 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 

  8. RSA Laboratorie, Information on RSA Challenge, http://www.rsa.com/rsalabs/html/challenges.html 

  9. Arjen K. Lenstra, Adi Shamir, Analysis and Optimization of the TWINKLE Factoring Device, proc. Eurocrypt 2002, LNCS 1807 35.52, Springer-Verlag, 2000 

  10. 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 

  11. C Pomerance, The Quadratic Sieve Factoring Algorithm., Advances in Cryptology - EUROCRYPT 84, LNCS 209 (1985) pp 169-182 

  12. 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 

    상세보기 crossref

  13. A Shamir, Factoring Large Numbers with the TWINKLE Device., Extended Abstract (1999) 

  14. 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 

  15. A Shamir, E Tromer, Special-Purpose Hardware for Factoring: the NFS Sieving Step, Invited talk at SHARCS'05, 2005 

  16. R D Silverman, The multiple polynomial quadratic sieve., Math.Comp., Vol. 84 (1987) pp. 327-339 

저자의 다른 논문 :

관련 콘텐츠

섹션별 컨텐츠 바로가기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper 아이콘
AI-Helper
안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로