격자 기반 암호SIS · LWE부터 Kyber와 ML-KEM

안녕하세요 오늘은 세미나 2번째 시간입니당

그럼 바로 ㄱㄱ하죠 

(2026-06-25에 진행한 UNKNOWN 세미나)

---

격자 기반 암호

격자

L(B) = { z₁b₁ + z₂b₂ + ⋯ + zₙbₙ : zᵢ ∈ ℤ }
기저 벡터들의 모든 정수 결합
계수가 실수면 평면 전체를 채우지만, 정수면 점무늬가 됨

• 좋은 기저 = 비밀키
  • 쉽다 — 짧고 직교에 가까우면 SVP·CVP가
    술술 풀린다. 트랩도어(뒷문) 역할
• 나쁜 기저 = 공개키
  • 어렵다 — 길고 평행에 가까우면 같은 문제가 꽉 막힘
    이 비대칭이 곧 암호

수식 읽는 법

1️⃣ mod q

계산 결과를 q로 나눈 나머지만 봄

2️⃣ 짧다

성분이 −1, 0, 1처럼 작음
아무 해가 아니라 작은 해가 어려움

3️⃣ 노이즈 e

일부러 넣은 작은 오차
가우스 소거 과정을 방해하여 비밀키를 찾게 어렵게 함

A·z ≡ 0 (mod q) = A와 z를 곱한 뒤 q로 나눈 나머지가 0

👉 A와 B는 공격자도 봄. s,e,z처럼 작거나 숨겨진 값이 핵심

SIS와 LWE

Regev 암호

1. 키 생성
2. 비밀키 s 공개키 (A, b = As + e) LWE 샘플 그 자체 — 공개해도 s는 안전
3. 암호화 — 비트 μ ∈ {0,1}
4. 행 부분집합을 무작위 선택 r ∈ {0,1}ᵐ u = Aᵀr, v = ⟨r, b⟩ + μ·⌊q/2⌋ Aᵀr = rᵢ=1인 행 aᵢ만 골라 더한 것 같은 r로 b도 골라 더한다
5. 복호화
6. d = v − ⟨s, u⟩ = μ·⌊q/2⌋ + (오류 합) d가 0 근처면 μ=0, q/2 근처면 μ=1 판정: bit = 1 ⇔ min(d, q−d) > floor(q/4) min(d,q−d)는 0에서의 시계 거리

ML-KEM

KEM은 긴 데이터를 직접 암호화하지 않고, 이후 대칭키를 만들 shared secret을 안전하
게 합의

공개 가능 : pk, ct
비밀: sk, shared secret

• KeyGen
  • 공개키 pk는 밖으로 나가도 되고, 개인키 sk는 절대 노출 금지
• Encaps
  • pk로 캡슐화 → 공개 ciphertext(ct) + 비밀 shared secret
• Decaps
  • sk와 ct로 같은 shared secret을 복원함
  • 실패 처리는조용하고 일정하게
• 그 다음
  • shared secret은 그대로 쓰지 않고 KDF(Key Derivation Function)를 거쳐 AEAD 키가 됨

Module-LWE

노이즈가 섞인 선형식을 어렵게 만든다

• 공개되는 것
  • 행렬/벡터와 노이즈가 섞인 결과는 공개될 수 있음
• 숨기는 것
  • 작은 비밀벡터와 오류값은 직접 보이지 않음
• 어려운 이유
  • 정확한 방정식이 아니라 오차가 섞인 방정식이라 역추적이 어려움
• 구현 포인트
  • 샘플링, 압축, 재암호화 검사, 상수시간 처리가 보안의 일부가 됨

보안은 문제에서, 속도는 계산 방식에서 나온다

• 큰 행렬을 그대로 들고 다니지 않음
  • 공개 행렬 A는 seed에서 다시 만들어 씀
  • 저장·전송은 작게, 계산할 때만 펼침
• 다항식 곱셈을 빠르게
  • A·s 같은 행렬-벡터 곱은 사실 다항식 곱셈의 묶음
  • NTT가 여기서 시간을 줄임
• 작게 보내고, 새지 않게 구현
  • 압축·패킹으로 바이트를 줄이고, 상수시간 구현으로 비밀이 시간 차이에 새지 않게 함

곱셈 병목

곱셈을 쉬운 좌표계로 옮긴다

랜덤은 암호의 산소다

• 대칭키 암호
  • IV/nonce가 예측되거나 재사용되면 같은 알고리즘도 위험해짐
• LWE/PQC
  • 작은 오류 e와 비밀 샘플링은 정해진 분포에서 나와야 보안 증명과 복호 안정성이 맞음
• 서명
  • 서명 nonce나 마스크가 약하면 개인키가 새는 고전적인 사고가 생김
• 구현
  • RNG(난수발생기) 품질, seed 관리, 테스트용 랜덤과 운영 랜덤 분리가 중요함

NTT는 어디에서 실제로 쓰이나

사용자는 API로 NTT를 직접 부르지 않는다. ML-KEM 구현 안에서 다항식 곱셈을 처리하는 엔진으로 지나간다

NTT와 GHASH는 둘 다 빠른 곱셈 엔진

• NTT in ML-KEM

다항식 곱셈을 빠르게 함
정수 mod q 세계에서 돌아감
LWE 기반 KEM(Key Encapsulation Mechanism)의 성능을 좌우함

• GHASH — AEAD 인증 태그 계산

인증 태그 계산을 빠르게 함
GF(2^128)=갈루아 필드 곱셈을 사용함
TLS/QUIC/IPsec 같은 실전 프로토콜에서 중요함

빠른 구현은 새 공격면도 만든다

• 상수시간 - 실제 사건
  • KyberSlash(2024): 비밀값이 들어간 나눗셈의 시간차가 decaps 키 정보를 새게 함
    여러 구현이 패치됨
• 샘플링
  • 노이즈와 비밀값을 뽑는 난수가 약하면 수학적으로 안전해도 무너짐
• 실패 처리
  • Decaps 실패 여부가 밖으로 새면 공격자가 반복 질의로 정보를 모을 수 있음
• 검증 벡터
  • 표준 KAT와 구현 간 결과가 맞는지 확인해야 최적화 버그를 잡을 수 있음

구현 보안

• 상수 시간
  • 비밀값에 따라 if문, 배열 위치, 실행 시간이 달라지면 타이밍·캐시 공격으로 정보가 새어 나갈 수 있음
• 감산
  • 덧셈·곱셈 뒤 값이 커져도 항상 mod q 범위로 빠르게 되돌림
    ex) Montgomery와 Barrett
• 거부 샘플링과 분포
  • 랜덤값을 그냥 아무렇게나 뽑지 않음
  • 약속한 분포에서 벗어나면 보안 증명과 실제 안전성이 흔들림
• 재암호화 검사와 실패 처리
  • 받은 값을 다시 암호화해 같은지 확인한다
  • 실패 여부와 실패 시간도 비밀처럼 처리해야 한다

AEAD(인증 암호) 연결

• ML-KEM이 하는 일
  • 서버와 클라이언트가 공유 비밀을 만든다.
  • KEM = Key Encapsulation Mechanism.
  • 실제 긴 데이터 전체를 직접 암호화하지 않는다.

• AEAD가 하는 일
  • 공유 비밀에서 파생된 대칭키로 데이터를 빠르게 암호화한다.
  • AAD(Additional Authenticated Data)와 인증 태그로 변조를 잡는다.
  • AEAD = 인증까지 포함한 대칭키 암호.

PKI(공개키 기반구조) 연결

• 공개키 신뢰
  • 공개키가 정말 그 사람의 것인지 증명하려면 인증서와 CA(Certificate Authority, 인증기관)가 필요함
• TLS 인증
  • 서버 인증서 체인은 키 교환과 별도로 서명 검증을 수행함
• PQC 서명
  • ML-DSA/SLH-DSA는 PQC 서명 계열이다. 인증서, 코드서명, 펌웨어 서명 전환과 연결
• 주의
  • ML-KEM을 써도 인증서 서명이 기존 RSA/ECDSA(Elliptic CurveDSA)라면 전환이 반쪽일 수 있음

TLS에서 바뀌는 곳과 안 바뀌는 곳

언어별 PQC 라이브러리

PKI(공개키 기반구조)와 인증서는 KEM과 다른 축

전체 흐름

수학을 API(함수 호출) 말로 바꾸기

TLS에서는 이 shared secret을 바로 데이터 암호화해서 쓰지 않고, 대칭키 재료로 파생해서 씀

---

두 번째 내용도 역시나....

처음 보는 내용이 많고 익숙하지 않은 주제였습니다 ㅠㅠㅠ

이해하기 쉽지 않네요..

 

-세미나 내용은 다음에 계속-