computing – 페이지 3 – Pseudorandom Things

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

2020년 6월 11일2020년 8월 12일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에 해당하는 파라미터를 쓰니 아주 안전하다 ㅎㅎ. 개인적인 생각으로는 고전컴퓨터가 이걸 깨는거보다 양자컴퓨터가 나와서 깨는게 더 빠를것같음.

Knuth Prize Winner: Cynthia Dwork

2020년 6월 5일2020년 6월 6일Hhan댓글 한 개

2020년 Knuth Prize의 수상자로 Cynthia Dwork이 선정되었다는 소식. 현재 하버드와 Microsoft Research에 소속된 Cynthia Dwork은 Differential Privacy, Non-malleability, Lattice-based cryptography, concurrent composition, proofs of work등을 제안하고 연구했다고 한다. 2017년 Gödel Prize도 Differential privacy를 소개한 공로로 받으셨던데 연구를 참 많이도 하셨네 -_-… ACM SIGACT 페이지에 설명이 잘 되어 있지만, 여기서는 위에 언급된 것들중 몇개에 대해 간단히 소개해보고자 한다.

계속 읽기 →

삼성의 Galaxy A Quantum, QRNG, and more

2020년 5월 26일2020년 6월 2일Hhan댓글 남기기

삼성에서 Galaxy A Quantum이라는 폰이 나온다는 소식. 사실 한국에서 이런 소식이 돈건 한참됐고, 이제 외신까지 뜨고있나보다.

앞선 글에서 말했듯 구글에서 조그마한 양자컴퓨터 만드는데 골골대는데 삼성이 외계인을 고문해서 양자컴퓨터를 폰에 넣었다! 이런건 아니고, 그냥 Galaxy A의 난수생성하는 부분을 QRNG (Quantum random number generator)로 대체했다는 말이다.

이 글에서는 1. 왜 QRNG가 유용한 기술인지, 그리고 더 나아가 2. 양자컴퓨터가 난수에 대한 어떤일을 할 수 있는지 살짝 언급해보고자 한다. 얼마전에 DC 수잘갤에 쓴 글을 다듬어서 씀.

계속 읽기 →

구글의 양자컴퓨터 vs 고전 시뮬레이션, 근황

2020년 5월 9일2020년 7월 5일Hhan댓글 8개

작년 놀라운 결과가 구글에 의해 발표되었다. 최초로 프로그래밍 가능한 양자컴퓨터를 이용해서 고전컴퓨터로는 현실적으로 불가능한 시간이 필요한 태스크를 그들의 53-qubit짜리 양자컴퓨터를 이용해 실험적으로 증명했다는 것.

이 발표 직후에 IBM에서 고전컴퓨터로 불가능하진 않다는 반박을 냈는데, 현존 최고수준의 슈퍼컴퓨터로 며칠이나 걸린다는 거라서… 어떤 의미에서는 양자우월성(Quantum Supremacy)라는 말을 방증하기도 한다.

그러면 이 양자우월성이라는 것을 구글은 어떻게 증명한걸까? 그리고 이후에도 IBM등지에서 다양한 추가 논의를 시도하는 이유는 뭘까? 이 글에서는 이러한 것들에 대해 알아보고자 한다.

2020/7/5 추가: 최근 조사한 것들을 바탕으로, 구글의 양자우월성 증명과 이후 논문들을 모두 설명하도록, 쉽게 읽히도록 새로 정리함.

계속 읽기 →

How to compute greatest common divisor fast?

2016년 10월 26일2020년 5월 8일Hhan댓글 남기기

임의의 자연수는 소인수분해가 유일하고, 크기순서가 잘 주어져 있기 때문에, 다음과 같은 greatest common divisor를 정의할 수 있습니다.

(Definition)For two positive integer $a,b$ , the greatest common divisor $g$ is the largest positive number that divides $a,b$ without remainder.

짧게는 $\gcd(a,b)$ 로 씁니다. 다르게는 정수 $x,y$ 에 대하여 $ax+by$ 의 음아닌 최솟값으로 정의할 수도 있지요. 수학을 전공하지 않은 분들도 이를 계산하는 다음 유클리드 알고리즘은 한 번씩 교과서에서 보셨을 것 같습니다.

[Algorithm] ${\rm Euclidean-Gcd}(a,b)$
input : $a,b \in \mathbb{N}$
output : $\gcd(a,b)$

If $b>a$ , return ${\rm Euclidean-Gcd}(b,a)$ .
If $b=0$ , return $a$ .
Otherwise return ${\rm Euclidean-Gcd}(b,a\mod b)$ .

이 알고리즘은 시간이 얼마나 걸릴까요? $a,b$ 가 n bit size정도 되는 경우 $O(n^2)$ 정도의 시간복잡도를 가짐을 증명할 수 있습니다.

$\gcd(a,b)$ 의 계산방법은 유클리도 알고리즘이 가장 쉽고 좋은 방법일까요? 그렇다면 이런 글을 쓸 필요도 없고, 질문을 할 필요도 없었겠지요. 유클리드 알고리즘은 3번 과정에서 $a \mod b$ 의 연산을 필요로 하고, 이 연산 때문에 시간복잡도에 곱하기 항이 생기게 됩니다. 우리가 더하기나 빼기는 좀 잘하는데, 곱하기, 나누기는 글쎄요… 이를 피하기 위한 다음과 같은 알고리즘도 있습니다.