양자컴퓨터도 뚫지 못하는 암호가 있다고?

[디지털투데이 추현우 기자] 양자컴퓨터 기술이 발전해도 AES-128 같은 대칭키 암호는 현실적인 위협 대상이 아니라는 주장이 나왔다.

21일(현지시간) 온라인 매체 기가진에 따르면 고 프로그래밍 언어의 암호 표준 라이브러리 유지보수를 맡는 암호기술 엔지니어 필리포 발소르다는 양자 위협은 공개키 암호와 대칭키 암호를 구분해 봐야 한다고 밝혔다.

RSA, ECDSA, EdDSA 같은 비대칭 암호는 쇼어 알고리즘에 취약해 대체가 시급한 대상으로 거론된다. 반면 AES-128처럼 암호화와 복호화에 같은 키를 쓰는 대칭키 암호는 그로버 알고리즘이 적용되더라도 실제 공격 비용이 매우 크다고 그는 설명했다.

그로버 알고리즘은 이론적으로는 무차별 대입 탐색 횟수를 줄일 수 있다. 하지만 정답 판별 함수 자체를 양자회로 안에 넣어야 하고, 이 과정은 사실상 직렬 처리에 가깝다. 병렬화도 쉽지 않아 탐색 공간을 여러 장비에 나눠도 고전 컴퓨터처럼 효율이 그대로 줄지 않는다.

실제로 64비트 키를 2의 16제곱대의 고전 컴퓨터에 분산하면 각 장비의 작업량은 2의 16제곱분의 1로 줄어든다. 그러나 128비트 키에 대한 그로버 공격을 2의 16제곱대의 양자컴퓨터에 나눠도 각 인스턴스의 부담은 2의 8제곱분의 1 줄어드는 데 그친다.

필요한 계산 규모도 크다. 양자 게이트 1회 계산에 1마이크로초가 걸리고 장비를 10년간 거의 멈추지 않고 돌린다고 가정해도, 한 대가 수행할 수 있는 직렬 계산 길이는 약 2의 48제곱 게이트다. 2025년 발표된 AES-128 최적화를 적용해도 정답 판별에는 724 논리 양자비트를 2의 32제곱개 병렬로 두고 약 10년간 가동해야 한다는 설명이다.

발소르다는 AES-128을 그로버 알고리즘으로 푸는 비용이 256비트 타원곡선암호를 쇼어 알고리즘으로 푸는 경우보다 약 2의 78.5제곱배, 약 43×10의 20제곱배 크다고 봤다. 미국 국립표준기술연구소와 독일 정보보안청도 AES-128, AES-192, AES-256을 계속 사용해도 된다는 입장이다.

암호 연구자 사무엘 제이크스도 2024년 비슷한 견해를 내놨다. 그는 그로버 알고리즘 때문에 AES 키 길이를 두 배로 늘려야 한다는 주장은 틀렸다고 했고, 병렬 공격 비용이 지나치게 높아 AES-128이 깨질 가능성은 매우 낮다고 봤다. 발소르다는 대칭키 암호를 일괄적으로 256비트로 올리기보다, 쇼어 알고리즘에 취약한 공개키 암호 교체에 자원을 집중해야 한다고 주장했다.