새 양자 알고리즘, 2000만 큐비트로 2048비트 RSA 8시간 만에 해독

양자 컴퓨터, 기존 암호 체계 위협 임박

양자 컴퓨터가 비밀 메시지 전송에 사용되는 기존 암호 코드를 깰 수 있다는 것은 확실합니다. 이러한 암호 기술은 결코 완전히 신뢰할 수 없었습니다. 대신 한 방향으로만 작동하는 복잡한 수학적 함수에 의존해 정보 암호화는 쉽게 만듭니다.

이러한 기술의 보안은 고전 컴퓨터가 정보를 해독하는 데 걸리는 시간에 기반합니다. 현대 암호 기술은 오늘날 컴퓨터로 수천 년이 걸려 코드를 해독해야 하므로 거의 뚫을 수 없습니다.

그러나 양자 컴퓨터는 이 코드를 쉽게 깰 수 있으며, 이러한 기계는 예상보다 현실에 훨씬 가까이 있습니다.

최근 구글과 스웨덴 KTH 왕립공과대학 연구진이 양자 컴퓨터가 비밀 메시지를 해독하는 데 사용할 수 있는 더 효율적인 기술을 개발했습니다. 양자 컴퓨터가 코드 해독 계산을 수행하는 데 더 적은 자원을 사용하게 해줍니다.

양자 컴퓨터 성능 급증

1994년 미국 수학자 피터 쇼어(Peter Shor)는 고전 컴퓨터에서 실행되는 최상의 기존 알고리즘보다 큰 수를 지수적으로 빠르게 인수분해하는 양자 알고리즘을 개발했습니다. 그는 충분히 강력한 양자 기계가 현대 암호 기술을 쉽게 깰 수 있다고 제안했습니다.

최근 10년간 양자 컴퓨팅에서 많은 발전이 있었습니다. 2012년 과학자들은 4큐비트 양자 컴퓨터로 '143'을 인수분해했습니다. 2년 후 비슷한 기계로 '56153'을 인수분해했습니다.

진행 속도를 고려하면 양자 컴퓨터가 곧 오늘날 컴퓨터를 능가할 것입니다. 적어도 몇 년 전 과학자들은 그렇게 예상했습니다.

하지만 양자 기계에서 큰 수 인수분해가 예상보다 훨씬 어렵다는 것이 밝혀졌습니다. 이는 대형 양자 컴퓨터의 상당한 노이즈 때문입니다. 이 문제는 오류 정정 코드로 해결할 수 있지만, 이것 자체가 추가 큐비트를 필요로 합니다.

참고: arXiv:1905.09749 | MIT Technology Review

이 노이즈 요소를 고려하면, 양자 컴퓨터는 2048비트 수 인수분해(또는 2048비트 RSA 암호 해독)에 10억 큐비트가 필요합니다. 그러나 오늘날 범용 양자 컴퓨터는 70큐비트만 갖추고 있습니다.

모듈러 지수 연산 최적화

새 알고리즘은 양자 컴퓨터가 단 2000만 큐비트로 이러한 계산을 수행할 수 있게 합니다. 사실 연구자들은 이 새 알고리즘을 실행하는 양자 장치가 2048비트 RSA 암호를 해독하는 데 단 8시간만 걸릴 것임을 보였습니다.

이 방법은 모듈러 지수 연산(modular exponentiation) — 모듈러 상에서 수행되는 지수 연산 — 을 효율적으로 수행합니다. 이 수학적 연산은 쇼어 알고리즘에서 계산 비용이 많이 듭니다.

연구자들은 이 연산을 최적화하는 다양한 방법을 찾아 알고리즘 실행에 필요한 자원을 획기적으로 줄였습니다.

2000만 큐비트 양자 컴퓨터는 가까운 미래에 실현 가능하지 않지만, 보안 전문가들은 강력한 양자 컴퓨터조차 깰 수 없는 새로운 형태의 암호화를 고민해야 합니다.