RSA Factoring 과제

RSA Factoring Challenge

RSA Factoring Challenge는 1991년[1] 3월 18일 RSA Laboratory가 암호화에 사용되는 큰 정수를 인수하고 RSA 키를 크래킹하는 실제적인 어려움에 대한 연구를 장려하기 위해 제시한 과제였다.그들은 RSA 번호로 알려진 반감기 목록(정확히 두 가지 주요 요인이 있는 숫자)을 발표했고, 이들 중 일부에 대한 성공적인 요소화에 대한 상금을 수여했다.그 중 가장 작은 것으로 RSA-100이라고 불리는 100십진수의 숫자가 1991년 4월 1일까지 인수되었다.많은 수의 큰 숫자들은 여전히 고려되지 않았고 상당 기간 동안 미분석 상태로 있을 것으로 예상되지만 양자컴퓨터의 발전은 쇼르의 알고리즘으로 인해 이러한 예측을 불확실하게 만든다.

2001년 RSA 연구소는 팩토링 도전을 확대하여 576비트부터 2048비트까지의 팩토링 숫자에 대해 1만 달러에서 20만 달러까지의 경품을 제공하였다.[2][3][4]

RSA Factoring Challenges는 2007년에 종료되었다.[5]RSA Laboratories는 다음과 같이 말했다. "이제 업계는 공통 대칭 키와 공개 키 알고리즘의 암호화된 강도에 대해 상당히 진보된 이해를 갖게 되었으므로, 이러한 과제는 더 이상 활성화되지 않는다."[6]2007년 챌린지가 종료되었을 때 RSA-576과 RSA-640만이 2001년 챌린지 번호에서 고려되었다.[7]

인수 도전은 정수 인자화에서 첨단을 추적하기 위한 것이었다.기본 애플리케이션은 RSA 공개 키 암호화 방식의 키 길이를 선택하는 데 사용된다.이 과제의 진전은 어떤 키 크기가 여전히 안전한지, 그리고 얼마나 오랫동안에 대한 통찰력을 제공해야 한다.RSA Laboratories는 RSA 기반 제품의 제공업체로서, 이 과제는 학계가 자사의 강점을 입증하기 위해 솔루션의 핵심을 공격하도록 하는 인센티브로 이용되었다.

RSA 번호는 어떠한 종류의 네트워크도 연결되지 않은 컴퓨터에서 생성되었다.그 후 컴퓨터의 하드 드라이브가 파괴되어 어디에서나 팩토링 도전에 대한 해결책에 대한 기록이 존재하지 않게 되었다.[6]

처음 생성된 RSA 번호인 RSA-100 ~ RSA-500 및 RSA-617은 소수 자릿수에 따라 레이블이 지정되었고, 나머지 RSA 번호(RSA-576으로 시작됨)는 나중에 생성되어 이진 자릿수에 따라 레이블이 지정되었다.아래 표의 숫자는 십진수에서 이진수로 이동함에도 불구하고 증가 순서로 나열되어 있다.

수학

RSA Laboratories에 따르면, 각 RSA 번호 n에 대해 다음과 같은 소수점 p와 q가 존재한다고 한다.

n = p × q.

문제는 이 두 가지 소수점을 찾는 것이다. 단적으로 찾는 것이다.

상과 레코드

다음 표에는 모든 RSA 번호에 대한 개요가 나와 있다.RSA Factoring Challenge는 2007년에[5] 종료되었으며 더 높은 수치를 감안한 상은 더 이상 수여되지 않는다는 점에 유의하십시오.

흰색 선으로 된 도전 번호는 베이스 10으로 표시된 숫자인 반면, 노란색 선으로 된 도전 번호는 베이스 2로 표시된 숫자다.
RSA 번호 십진수 이진수 현금 경품 제공 에 근거한. 요인:
RSA-100 100 330 미화[8] 1,000달러 1991년[9] 4월 1일 아르젠 K.렌스트라
RSA-110 110 364 US$4,429[8] 1992년[9] 4월 14일 아르젠 K. 렌스트라와 MS 므낫세
RSA-120 120 397 US$ 5,898[8] 1993년[10] 7월 9일 T. 데니 외
RSA-129 [a] 129 426 미화 100달러 1994년[9] 4월 26일 아르젠 K.렌스트라 외
RSA-130 130 430 미화 14,527달러[8] 1996년 4월 10일 아르젠 K.렌스트라 외
RSA-140 140 463 미화 17,226달러 1999년 2월 2일 헤르만 테 리엘레 외
RSA-150 150 496 2004년 4월 16일 아오키 가즈마로 외
RSA-155 155 512 US$9,383[8] 1999년 8월 22일 헤르만 테 리엘레 외
RSA-160 160 530 2003년 4월 1일 옌스 프랑케 외, 본 대학교
RSA-170 [b] 170 563 2009년 12월 29일 D. 보넨버거와 M. 크론
RSA-576 174 576 미화 1만 달러 2003년 12월 3일 옌스 프랑케 외, 본 대학교
RSA-180 [b] 180 596 2010년 5월 8일 S. A. 다닐로프와 나.A. 포포비아, 모스크바 주립 대학교[11]
RSA-190 [b] 190 629 2010년 11월 8일 A. 티모페프와 나.A. 포포비아
RSA-640 193 640 미화 2만 달러 2005년 11월 2일 옌스 프랑케 외, 본 대학교
RSA-200 [b] ? 200 663 2005년 5월 9일 옌스 프랑케 외, 본 대학교
RSA-210 [b] 210 696 2013년[12] 9월 26일 라이언 프로퍼
RSA-704 [b] 212 704 미화 3만 달러 2012년 7월 2일 시바이, 에마뉘엘 토메, 폴 짐머만
RSA-220 [b] 220 729 2016년 5월 13일 S. Bai, P. Gaudry, A. Kruppa, E.톰과 P. 짐머만
RSA-230 [b] 230 762 2018년 8월 15일 새뮤얼 S.징그럽, 노블리스, 주식회사
RSA-232 [b] 232 768 2020년[13] 2월 17일 N. L. Zamarashkin, D.A. 젤트코프와 S. A. 마트베프.
RSA-768 [b] 232 768 미화 5만 달러 2009년 12월 12일 토르스텐 클라인중 외[14]
RSA-240 [b] 240 795 2019년[15] 12월 2일 F. Boudot, P. Gaudry, A.길레비치, 뉴욕 주헤닝거, E.톰과 P. 짐머만
RSA-250 [b] 250 829 2020년[16] 2월 28일 F. Boudot, P. Gaudry, A.길레비치, 뉴욕 주헤닝거, E.톰과 P. 짐머만
RSA-260 260 862
RSA-270 270 895
RSA-896 270 896 미화 75,000달러[d]
RSA-280 280 928
RSA-290 290 962
RSA-300 300 995
RSA-309 309 1024
RSA-1024 309 1024 미화 10만[d] 달러
RSA-310 310 1028
RSA-320 320 1061
RSA-330 330 1094
RSA-340 340 1128
RSA-350 350 1161
RSA-360 360 1194
RSA-370 370 1227
RSA-380 380 1261
RSA-390 390 1294
RSA-400 400 1327
RSA-410 410 1360
RSA-420 420 1393
RSA-430 430 1427
RSA-440 440 1460
RSA-450 450 1493
RSA-460 460 1526
RSA-1536 463 1536 미화 15만[d] 달러
RSA-470 470 1559
RSA-480 480 1593
RSA-490 490 1626
RSA-500 500 1659
RSA-617 617 2048
RSA-2048 617 2048 미화 20만[d] 달러
  1. ^ RSA-129는 RSA Factoring Challenge에 포함되지 않았지만 Scientific American의 Martin Gardner의 칼럼과 관련이 있었다.
  2. ^ a b c d e f g h i j k l 그 숫자는 도전이 끝난 후에 고려되었다.
  3. ^ RSA-170 또한 S. A. Danilov와 I에 의해 독립적으로 고려되었다.A. 이틀 후 포포비아인.[11]
  4. ^ a b c d 이 상이 수여되기 전에 도전이 끝났다.

참고 항목

메모들

  1. ^ Kaliski, Burt (18 Mar 1991). "Announcement of "RSA Factoring Challenge"". Retrieved 8 March 2021.
  2. ^ Leyden, John (25 Jul 2001). "RSA poses $200,000 crypto challenge". The Register. Retrieved 8 March 2021.
  3. ^ RSA Laboratories. "The New RSA Factoring Challenge". Archived from the original on 2001-07-14.
  4. ^ RSA Laboratories. "The RSA Challenge Numbers". Archived from the original on 2001-08-05.
  5. ^ a b RSA Laboratories. "RSA Factoring Challenge". Archived from the original on 2013-09-21. Retrieved 2008-08-05.
  6. ^ a b RSA Laboratories. "The RSA Factoring Challenge FAQ". Archived from the original on 2013-09-21. Retrieved 2008-08-05.
  7. ^ RSA Laboratories. "The RSA Challenge Numbers". Archived from the original on 2013-09-21. Retrieved 2008-08-05.
  8. ^ a b c d e "Status/news report on RSA data security factoring challenge (as of 3/30/00)". 30 January 2002.
  9. ^ a b c RSA 아너 롤
  10. ^ Denny, T.; Dodson, B.; Lenstra, A. K.; Manasse, M. S. (1994). On the factorization of RSA-120. Advances in Cryptology — CRYPTO' 93. pp. 166–174. doi:10.1007/3-540-48329-2_15.
  11. ^ a b Danilov, S. A.; Popovyan, I. A. (9 May 2010). "Factorization of RSA-180" (PDF). Cryptology ePrint Archive.
  12. ^ RSA-210 팩터링, mersenneforum.org
  13. ^ INM RAS 뉴스
  14. ^ Kleinjung, Thomas (18 Feb 2010). "Factorization of a 768-bit RSA modulus" (PDF). {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  15. ^ Thomé, Emmanuel (December 2, 2019). "795-bit factoring and discrete logarithms". cado-nfs-discuss (Mailing list).
  16. ^ Zimmermann, Paul (February 28, 2020). "Factorization of RSA-250". cado-nfs-discuss (Mailing list).