factorization

양자컴퓨터를 이용한 소인수분해는 어디까지 왔을까?

Hhan댓글 2개

이 글에서는 피터 쇼어(Peter Shor)가 1994년 (Arxiv논문 링크), 이제는 쇼어의 알고리즘이라고 불리는 양자 소인수분해 알고리즘을 제안한 이후, 여러가지 측면에서 양자컴퓨터가 소인수분해 문제를 풀기에 얼마나 발전했는지, 그리고 얼마나 빨리 소인수분해를 할것으로 예측하고 있는지를 정리하고자 한다.

이 글은 다음과 같이 구성된다.

  1. 쇼어알고리즘의 간략한 설명
  2. 쇼어알고리즘의 구체적 구현과 최적화 논문들
  3. 양자컴퓨터를 이용한 실제 소인수분해 실험들

그치만 결론만 먼저 요약하면 앞선 글에서 소개했듯 RSA-240,250, 즉 약 800비트 정수를 소인수분해 하는데 2000 core-년이 필요한 반면, 2천만 큐비트의 에러가 있는 양자컴퓨터가 있다면 그럴듯한 가정 하에 RSA-2048, 즉 2048비트 정수를 소인수분해 하는데 8시간이면 충분하다고 한다! 이게 바로 양자컴퓨터의 위력 ㅡㅡ!

다만 쇼어알고리즘을 양자컴퓨터로 실제로 돌리는 것은 (내가 아는바에 의하면) 딱히 실험적으로 진행한 바가 없다. 쇼어알고리즘에 어느정도 치팅을 한 버젼이나, Adiabatic quantum computer등을 이용한 방식이 진행되었을 뿐이다. 치팅을 한 버젼도 최대한 치팅을 한것은 아니고, 그럴듯한 정도로 해서 양자 소인수분해에 대한 어느정도 근거를 주기는 하지만 말이다.

계속 읽기 →

RSA-240, 250이 깨졌다는 소식

Hhan댓글 5개

다들 아시는 RSA암호의 안전성 기반의 가장 기초인 소인수분해를 빨리 하는 챌린지인 RSA Factoring Challenge가 있다. 이 챌린지는 1991년에 시작되어 2007년에 이제 우리가 소인수분해를 잘 이해하는것 같다는 이유로 -_- 중단되었는데, 당연히 그 이후에도 계속 연구되었다. 기존 최고 기록은 2009년 Kleinjung et al.의 768bit의 자연수를 소인수분해하는 RSA-768. 이 문제는 2000 core-년 (즉 single core로 2000년정도) 정도의 연산시간에 해결했었음.

이번에 발표된 결과는 Boudot et al.의 결과로 RSA-240, 250, 즉 10진법으로 240, 250자리를 갖는 수들을 소인수분해한 것이다. 즉 각각 795, 829비트를 갖는 자연수를 1000, 2500 core-년씩 써서 소인수분해했다고 한다. 쓴 라이브러리는 Cado-NFS라고 하는데, 이들의 메일링리스트에서는 이 결과가 이미 작년 12월, 올해 2월에 각각 발표되었었나보다. 또 DLP-240도 3000 core-년에 해결한 모양. 이 결과는 2016년 발표된 DLP-768의 5300 core-년 해결보다 훨씬 빠르다. 이런것들은 완전 새로운 알고리즘인건 아니고, 오래전부터 써오던 NFS 알고리즘을 이리저리 변형하고 파라미터를 훨씬 잘 잡은것에서 나온것인가봄.

이 분야도 계속 어찌저찌 발전은 계속 하고있나보다. 여튼 현재 한국의 많은 암호시스템은 RSA-2048에 해당하는 파라미터를 쓰니 아주 안전하다 ㅎㅎ. 개인적인 생각으로는 고전컴퓨터가 이걸 깨는거보다 양자컴퓨터가 나와서 깨는게 더 빠를것같음.