하계 보안 세미나 2일차 - 격자 기반 암호 (SIS · LWE부터 Kyber와 ML-KEM)

 

 

PQC가 AES를 없애는 것이 아니라 공개키 암호 쪽을 바꾸는 것

 

 

 

 

 

이번 강의에서는 양자컴퓨터 시대의 공개키 암호를 주제로, 격자 기반 암호가 왜 중요한지 배웠다.
제목만 봤을 때는 SIS, LWE, Kyber, ML-KEM 같은 용어가 한 번에 나와서 꽤 어렵게 느껴졌는데, 전체 흐름을 잡아보면 핵심은 생각보다 단순했다.

 

기존의 공개키 암호인 RSA와 ECC는 지금까지 많이 사용되어 왔지만, 양자컴퓨터가 충분히 발전하면 위험해질 수 있다. 특히 Shor 알고리즘은 소인수분해와 이산로그 문제를 빠르게 풀 수 있기 때문에 RSA와 ECC의 기반을 흔들 수 있다. 그래서 양자컴퓨터 이후에도 버틸 수 있는 암호, 즉 PQC(Post-Quantum Cryptography, 양자내성암호)가 필요해졌다.

PQC는 AES를 대체하는 것이 아니다

처음에 헷갈렸던 부분은 “PQC가 나오면 AES도 사라지는 건가?”였다.
그런데 강의에서는 역할이 다르다고 설명했다.

AES 같은 대칭키 암호는 실제 데이터를 빠르게 암호화하는 역할을 한다. 반면 PQC는 RSA나 ECC처럼 키 교환이나 서명 쪽 공개키 암호를 대체하는 쪽에 가깝다. 즉, PQC가 세션키를 안전하게 만들고, 그 세션키로 AES-GCM 같은 대칭키 암호가 실제 데이터를 보호하는 구조다.

보안통신 흐름을 간단히 보면 다음과 같다.

인증서 확인
→ KEM 또는 ECDH로 공유 비밀 생성
→ HKDF로 세션키 파생
→ AES-GCM으로 실제 데이터 암호화
→ 키 관리

결국 PQC 전환은 단순히 알고리즘 이름 하나 바꾸는 일이 아니라, 통신 프로토콜과 키 관리까지 같이 봐야 하는 문제였다.

격자란 무엇인가

이번 강의의 중심은 격자 기반 암호였다.
격자는 쉽게 말하면, 일정한 규칙으로 찍힌 점들의 집합이라고 볼 수 있다.

PPT에서는 격자를 “기저 벡터들의 모든 정수 결합”이라고 설명했다. 말이 조금 어려운데, 풀어보면 어떤 방향 벡터들이 있고, 그 벡터들을 정수 배만큼 더해서 만들 수 있는 점들이 격자점이 된다. 예를 들어 v = 2b₁ + b₂처럼 기저 벡터를 정수만큼 조합하면 격자 위의 한 점이 된다.

여기서 중요한 점은 같은 격자라도 어떤 기저로 보느냐에 따라 문제의 난이도가 달라질 수 있다는 것이다. 짧고 서로 직교에 가까운 좋은 기저를 알면 문제가 쉽게 풀리지만, 길고 거의 평행한 나쁜 기저만 알고 있으면 같은 문제도 매우 어려워진다. 강의에서는 이 차이를 “좋은 기저는 비밀키, 나쁜 기저는 공개키”처럼 설명했다.

SIS: 짧은 해를 찾는 문제

SIS는 Short Integer Solution의 약자로, 짧은 정수해 문제라고 한다.

형태는 대략 이렇게 생겼다.

A · z ≡ 0 (mod q)

여기서 공개된 행렬 A가 있고, 이 식을 만족하는 작은 벡터 z를 찾아야 한다.
그냥 아무 해나 찾는 것은 비교적 쉽지만, 성분이 -1, 0, 1처럼 작은 해를 찾는 것이 어렵다. 강의에서는 이 “짧다”는 조건이 SIS의 어려움을 만든다고 설명했다.

즉 SIS는 한마디로 정리하면 이렇게 볼 수 있다.

공개된 A가 있을 때,
A·z가 0이 되도록 만드는 작은 z를 찾아라.

SIS는 해시, 서명, 커밋먼트 같은 쪽과 연결된다.

LWE: 노이즈가 섞인 식에서 비밀을 찾는 문제

LWE는 Learning With Errors의 약자다.
이름 그대로, 오류가 섞인 상태에서 뭔가를 알아내야 하는 문제다.

기본 형태는 다음과 같다.

b = A · s + e

여기서 A와 b는 공개될 수 있고, s는 비밀값, e는 작은 오류다.

오류가 없다면 공격자는 그냥 연립방정식을 풀어서 s를 구할 수 있다. 그런데 중간에 작은 오류 e가 섞이면 상황이 달라진다. 겉보기에는 값이 조금만 흔들린 것 같지만, 실제로 식을 풀면 완전히 다른 답이 나올 수 있다. PPT에서도 노이즈가 없을 때는 비밀값이 깔끔하게 복원되지만, +1, -1 정도의 작은 노이즈만 들어가도 가우스 소거 결과가 틀어지는 예시가 나왔다.

내가 이해한 LWE의 핵심은 이거였다.

정답 근처에 일부러 안개를 끼워서,
겉으로는 보이지만 정확히 되돌리기는 어렵게 만든다.

SIS와 LWE 차이 정리

강의 중간정리에서는 SIS와 LWE를 이렇게 구분했다.

SIS = 짧은 우연을 찾는 문제
LWE = 오류가 섞인 직선을 복원하는 문제

SIS는 A·z ≡ 0을 만족하는 작은 z를 찾는 문제이고, LWE는 b = A·s + e에서 오류 e 때문에 숨겨진 s를 찾기 어렵게 만드는 문제다. 둘 다 결국 “작은 것”이 핵심이다. SIS는 작은 해, LWE는 작은 오류가 난이도를 만든다.

ML-KEM은 무엇인가

ML-KEM은 Module-Lattice Key Encapsulation Mechanism의 약자다.
쉽게 말하면, 격자 기반 수학을 이용해서 두 사람이 같은 공유 비밀을 만들 수 있게 해주는 방식이다.

여기서 중요한 건 ML-KEM이 긴 데이터를 직접 암호화하는 것이 아니라는 점이다. ML-KEM은 이후 대칭키를 만들기 위한 shared secret을 안전하게 합의하는 역할을 한다. 그 shared secret은 그대로 쓰이지 않고, KDF를 거쳐 AES-GCM 같은 AEAD 암호의 키로 사용된다.

흐름은 다음과 같다.

KeyGen   → 공개키 pk, 개인키 sk 생성
Encaps   → pk로 캡슐화해서 ct와 shared secret 생성
Decaps   → sk와 ct로 같은 shared secret 복원
그 다음 → KDF를 거쳐 실제 대칭키로 사용

공개키 pk와 암호문 ct는 네트워크로 오가도 되지만, 개인키 sk와 shared secret은 절대 새면 안 된다.

왜 Module-LWE가 나오는가

일반 LWE는 이론적으로는 좋지만, 그대로 쓰기에는 공개키가 너무 커질 수 있다. 그래서 실용화를 위해 Ring-LWE, Module-LWE 같은 구조가 나온다.

강의에서는 Module-LWE를 “숫자 행렬의 각 칸이 작은 다항식으로 바뀐 버전”처럼 설명했다. 숫자 하나하나를 전부 들고 다니는 대신, 다항식 구조를 이용해 더 작고 빠르게 만드는 것이다. Kyber, 즉 ML-KEM은 이런 Module-LWE 구조를 이용해 실용적인 키 교환 방식으로 만든 표준이라고 볼 수 있다.

NTT는 보안이 아니라 속도를 위한 장치

강의 후반부에서 NTT도 나왔다. 처음에는 이게 또 새로운 보안 가정인가 싶었는데, 그건 아니었다.

NTT는 Number Theoretic Transform의 약자로, 다항식 곱셈을 빠르게 하기 위한 계산 방식이다. ML-KEM 내부에서는 다항식 곱셈이 많이 필요한데, 그냥 모든 항을 하나씩 곱하면 느리다. NTT는 다항식을 곱하기 쉬운 좌표계로 바꾼 뒤, 각 자리끼리 곱하고 다시 원래 형태로 되돌리는 방식이다.

한 문장으로 정리하면:

Module-LWE는 보안의 근거,
NTT는 그 계산을 빠르게 돌리는 엔진.

이 둘을 구분하는 게 중요했다.

구현 보안도 중요하다

수학적으로 안전한 알고리즘이라고 해서 실제 구현까지 자동으로 안전한 것은 아니다. 강의에서는 KyberSlash 같은 사례도 언급하면서, 비밀값에 따라 실행 시간이 달라지면 타이밍이나 캐시를 통해 정보가 샐 수 있다고 설명했다.

구현에서 중요한 요소는 다음과 같았다.

상수시간 구현
정확한 mod q 감산
올바른 샘플링과 분포
재암호화 검사
실패 처리 숨기기
검증 벡터 확인

특히 Decaps 과정에서 실패 여부가 밖으로 드러나면 공격자가 반복 질의를 통해 정보를 모을 수 있기 때문에, 실패 처리도 조용하고 일정하게 해야 한다.

TLS에서는 어떻게 쓰이나

기존에는 X25519 같은 ECDH 방식으로 공유 비밀을 만들었다면, 양자컴퓨터 위협 이후에는 ML-KEM 같은 PQC 기반 KEM이 그 자리를 대체하거나 함께 사용될 수 있다.

강의에서는 전환기에는 X25519와 ML-KEM을 함께 쓰는 하이브리드 방식도 설명했다. 중요한 점은 이것도 실제 데이터를 암호화하는 부분이 아니라, 세션키를 만드는 앞단이라는 것이다. 실제 데이터 보호는 여전히 AES-GCM 같은 AEAD가 담당한다.

마무리

이번 강의는 수식이 많아서 따라가기 쉽지는 않았지만, 큰 흐름은 이렇게 정리할 수 있었다.

양자컴퓨터가 RSA/ECC를 위협한다.
그래서 PQC가 필요하다.
그중 격자 기반 암호가 유력하다.
격자 기반 암호의 핵심 문제로 SIS와 LWE가 있다.
ML-KEM은 LWE 계열을 실용화한 키 캡슐화 표준이다.
실제 데이터 암호화는 여전히 AES-GCM 같은 대칭키 암호가 맡는다.

가장 기억에 남은 부분은 PQC가 AES를 없애는 것이 아니라 공개키 암호 쪽을 바꾸는 것이라는 점이었다. 그리고 수학적으로 안전한 구조를 만드는 것도 중요하지만, 실제 구현에서 시간 차이나 실패 처리 같은 작은 정보가 새지 않게 하는 것도 그만큼 중요하다는 걸 알 수 있었다.