中 연구팀, 양자 컴퓨터로 RSA 암호 해독 기술 개발

중국 상하이대학 연구팀이 소인수분해의 어려움을 안전성 근거로 삼은 암호 RSA 암호에 대해 양자 컴퓨터를 사용해 해독 기술을 개발했다고 발표했다.

중국 학술지(Chinese Journal of Computers)에 게재된 심사를 거친 논문에 따르면 연구팀은 캐나다에 본사를 둔 디웨이브시스템즈(D-Wave Systems)의 양자 컴퓨터인 디웨이브 어드밴티지(D-Wave Advantage)를 사용하고 고전적 알고리즘과 양자 어닐링 등 기법을 통합해 몇몇 암호 알고리즘에 대한 시스템 최적화에 성공했다고 한다.

양자 컴퓨터는 기존 암호를 언젠가 해독할 가능성이 있다고 여겨졌지만 이번 연구로 인해 그런 위협이 예상보다 훨씬 빨리 올 수 있음이 시사됐다.

전문가에 따르면 이번 연구의 의의는 양자 어닐링 알고리즘과 기존 수학적 접근법을 결합해 새로운 계산 아키텍처를 만들고 암호화 문제를 양자 컴퓨터에 적합한 이항 최적화 문제로 설정한 것에 있다고 한다.

연구팀이 대상으로 한 알고리즘은 군사 및 금융 암호화 프로토콜에 널리 도입된 시스템 기초가 되는 것들이며 그 중에는 현재 이용 가능한 가장 안전한 것으로 여겨지는 것도 있었지만 연구팀은 양자 컴퓨터가 가까운 미래에 안전성을 위협할 가능성이 있음을 시사하고 있다고 지적했다.

연구팀이 연구 대상으로 삼은 건 두 종류 양자 어닐링 기반 RSA 공개키 공격 알고리즘이다. 첫 번째는 암호 공격의 수학적 방법을 결합해 최적화 문제 또는 지수 공간 탐색 문제로 변환하고 이징 모델 또는 QUBO 모델과 같은 기존 방법으로 해결할 수 있게 하는 모델이다. 이 모델을 이웨이브 어드밴티지에 적용한 결과 22비트 RSA 정수인 2269753의 인수분해에 성공했다고 한다. 이는 기존 실험 지수를 크게 상회하며 이징 모델과 관련된 계수 범위를 80~84% 축소하고 분해 성공률을 크게 향상시켰다고 한다.

2번째는 양자 어닐링 알고리즘 융합 암호 공격이라 불리는 것이다. 연구팀은 양자 어닐링과 고전적 알고리즘을 결합해 근사 최근접 이웃 알고리즘을 최적화하고 논리 양자 비트 10개와 물리 양자 비트 16개를 사용해 845546611823483=40052303×21111061이라는 50비트 정수의 인수분해에 성공했다. 연구팀은 4~50비트 범위 내에서 RSA 정수 분해를 무작위로 선택하는 접근 방식을 취했는데 이는 알고리즘 보편성과 확장성을 증명하는 실증 실험의 의미가 컸다고 한다.

현재 사용되고 있는 2048비트 이상 키를 깨는 데는 큰 기술적 돌파구가 필요하지만 연구팀 방법은 향후 64비트 이상 RSA 정수의 인수분해에도 응용될 수 있는 가능성이 있기 때문에 연구팀은 현재 암호화되어 있는 데이터라도 장래에 해독 가능해질 것을 예상해 도난당할 수 있으며 이런 데이터는 위험에 노출될 가능성이 있다며 양자 공격이 현실화됨에 따라 조직은 데이터 안전성을 어떻게 확보할 것인지 재고할 필요가 있다고 경고했다. 관련 내용은 이곳에서 확인할 수 있다.