양자컴퓨터도 풀기 어렵다? 격자 기반 암호와 양자내성암호(PQC) 알아보기

격자 기반 암호는 현재 알려진 양자컴퓨터 공격에도 강할 것으로 평가되는 수학적 문제를 활용한 암호 기술입니다. 이를 포함한 양자내성암호(PQC)는 미래의 양자컴퓨터에 대비하기 위한 방법이지만, 어떤 알고리즘도 영원히 안전하다고 보장되는 것은 아닙니다. 원리와 실제 적용 기준을 쉽게 살펴보겠습니다.

핵심 요약

• 양자내성암호(PQC)는 양자컴퓨터 공격을 고려해 설계한 암호 알고리즘입니다.

• 격자 기반 암호는 복잡한 다차원 수학 문제의 계산상 어려움을 활용합니다.

• 미국 NIST는 2024년 ML-KEM과 ML-DSA를 표준으로 확정했습니다.

• PQC가 모두 격자 기반인 것은 아닙니다. SLH-DSA는 해시 기반 전자서명입니다.

양자컴퓨터는 왜 기존 암호에 위협이 될까요?

오늘날 인터넷에서 널리 쓰이는 공개키 암호 일부는 큰 수를 소인수분해하거나 이산로그 문제를 푸는 일이 어렵다는 점에 의존합니다. 충분히 강력한 양자컴퓨터가 등장하면 쇼어 알고리즘을 이용해 RSA와 타원곡선 암호(ECC) 같은 방식이 위협받을 수 있습니다.

다만 현재의 양자컴퓨터가 실무에서 사용하는 모든 암호를 즉시 깨뜨릴 수 있다는 뜻은 아닙니다. 대칭키 암호와 해시 함수의 영향도 공개키 암호와 같지 않으며, 키 길이와 설계 방식에 따라 대응이 달라집니다.

격자 기반 암호는 어떤 원리인가요?

격자(lattice)는 수학적으로 일정한 규칙에 따라 배치된 점들의 구조입니다. 이를 수백 또는 수천 차원처럼 높은 차원으로 확장하면, 특정 조건에서 가까운 점을 찾거나 잡음이 섞인 관계를 복원하는 문제가 매우 어려워질 수 있습니다.

쉽게 말해, 정답에 이르는 규칙에 작은 오차를 섞어 둔 퍼즐을 떠올리면 됩니다. 정당한 사용자는 필요한 비밀정보로 통신용 열쇠를 만들지만, 공격자는 공개된 정보만으로 그 관계를 알아내기가 어렵도록 설계합니다. 이는 이해를 돕는 비유로, 실제 알고리즘의 계산 과정과 완전히 같지는 않습니다.

중요한 차이점은 ‘절대 풀 수 없다’가 아니라 ‘현재 알려진 효율적인 공격법이 없다’는 점입니다. 새로운 수학적 발견이나 구현상의 결함으로 안전성 평가가 달라질 수 있습니다.

표준으로 채택된 PQC는 무엇이 다를까요?

미국 국립표준기술연구소(NIST)는 2024년 8월 처음 세 가지 주요 PQC 표준을 확정했습니다. 이름은 비슷하지만 실제 맡는 역할은 다릅니다.

ML-KEM은 메시지를 직접 암호화하는 방식이라기보다, 양쪽이 공통으로 사용할 비밀키를 안전하게 설정하는 기술입니다. ML-DSA는 문서나 소프트웨어가 올바른 발신자로부터 왔고 중간에 변조되지 않았는지 확인하는 데 활용할 수 있습니다.

실제 생활에서는 어디에 사용될까요?

예를 들어 온라인 서비스가 이용자의 기기와 서버 사이에 안전한 통신 연결을 만든다고 가정해 보겠습니다. 이때 PQC 기반 키 설정 기술을 지원한다면, 미래 양자 공격을 고려한 방식으로 통신용 비밀키를 마련할 수 있습니다.

소프트웨어 업데이트의 전자서명을 PQC로 바꾸는 경우에는 업데이트 파일의 진위와 무결성을 확인하는 데 도움이 됩니다. 다만 키 교환과 전자서명은 서로 다른 기능이므로 한 가지 알고리즘만 도입한다고 모든 보안 문제가 해결되지는 않습니다.

PQC로 바꾸면 무조건 안전할까요?

그렇지는 않습니다. 암호 알고리즘이 안전해도 프로그램의 오류, 비밀키 유출, 잘못된 설정, 피싱 공격까지 막아 주지는 못합니다. 또한 일부 PQC 방식은 기존 방식보다 공개키·서명·전송 데이터가 커질 수 있어 시스템의 성능과 호환성을 검토해야 합니다.

오래 보관해야 하는 민감정보라면 특히 대비가 중요합니다. 공격자가 지금 암호화된 통신을 수집해 두었다가 미래에 복호화를 시도하는 이른바 ‘지금 수집하고 나중에 해독하기’ 위험이 있기 때문입니다.

지금 무엇부터 확인하면 될까요?

개인은 운영체제·브라우저·보안 앱을 최신 상태로 유지하고, 사용하는 서비스가 안전한 업데이트를 제공하는지 살피는 것이 현실적인 출발점입니다. 기업과 개발자는 TLS 연결, 인증서, 전자서명, 백업 등에서 RSA·ECC가 쓰이는 위치를 파악한 뒤 표준 PQC 적용과 호환성 시험을 계획해야 합니다.

가장 먼저 할 일은 자신이 관리하는 서비스의 암호화·전자서명 구성 목록에서 현재 사용 중인 공개키 알고리즘을 확인하는 것입니다.