728x90

ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism)은 NIST에서 2024년 8월 13일에 발표한 FIPS 203 표준입니다. 이는 양자 컴퓨터 시대에 대비한 포스트 양자 암호(PQC) 중 하나로, 안전한 공개키 기반 공유 비밀키 생성을 위한 암호 알고리즘입니다

 

ML-KEM 개요

  • 목적: 두 사용자가 공개 채널을 통해 안전하게 공유 비밀키(shared secret key) 를 설정할 수 있게 해주는 암호 기술입니다.
  • 방식: “KEM (Key-Encapsulation Mechanism, 키 캡슐화 메커니즘)” 구조를 따릅니다.
  • 기반 수학: Module Learning With Errors (MLWE) 문제의 어려움에 기반함. 이는 lattice-based 문제로, 양자 컴퓨터에도 안전한 것으로 간주됨.

 

1. Alice: KeyGen() → (pk, sk)
2. Bob: Encaps(pk) → (c, K)
3. Bob → Alice에게 c 전송
4. Alice: Decaps(sk, c) → K'
5. 이제 Alice와 Bob은 공유키 K = K'
      Alice                                 Bob
     (수신자)                             (송신자)
   ------------                         ------------
   KeyGen()                             ← ek (공개키)
   ↓                                          |
   ek, dk                                     |
                                             Encaps(ek)
                                              ↓
                                    생성: (c, K), send c →
   Decaps(dk, c)                          ← c
   ↓
   생성: K′ (≈ K)

 

 

파라미터 세트

파라미터 보안 카테고리 설명 권장 사용 예시
ML-KEM-512 Category 1
AES-128		 성능 우선, 낮은 보안 수준 IoT, 모바일 등
ML-KEM-768 Category 3
AES-192		 균형 잡힌 성능/보안 일반 보안 통신
ML-KEM-1024 Category 5
AES-256		 높은 보안, 느린 성능 고보안 시스템

 

파라미터 세트

파라미터 공개키 크기 비밀키 크기 암호문 크기 공유 비밀키
ML-KEM-512 800 Byte 1632 Byte 768 Byte 32 Byte
ML-KEM-768 1184 Byte 2400 Byte 1088 Byte 32 Byte
ML-KEM-1024 1568 Byte 3168 Byte 1568 Byte 32 Byte

 

복호화 실패율

파라미터실패 확률

파라미터 실패확률
ML-KEM-512 2⁻¹³⁸.⁸
ML-KEM-768 2⁻¹⁶⁴.⁸
ML-KEM-1024 2⁻¹⁷⁴.⁸

 

 

ML-KEM 작동 방식

 

1. KeyGen:

  • Alice가 키 페어 (Encapsulation Key, Decapsulation Key)를 생성
  • Encapsulation Key는 공개, Decapsulation Key는 비밀

입력 :

내부적으로 사용되는 랜덤 바이트 d, z (암호모듈이 생성함)

 

출력:

ek: Encapsulation Key (공개키)

dk: Decapsulation Key (비밀키)

  1. 랜덤 시드 d → NTT를 위한 행렬 A를 생성
  2. 노이즈 다항식 샘플링 → 비밀 벡터 s, 오류 벡터 e를 생성
  3. t = A ∘ s + e (모듈 기반 다항식 연산)
  4. 공개키 ek = 압축된 A, t 값
  5. 비밀키 dk = s, e, t, z, 그리고 H(ek) 해시값
Algorithm 19 ML-KEM.KeyGen()
Input: None
Output: (ek, dk) — encapsulation key, decapsulation key

1: d ←$ B32                   // 32바이트 랜덤값
2: z ←$ B32                   // 또 다른 32바이트 랜덤값
3: (ek, dk) ← ML-KEM.KeyGen_internal(d, z)
4: return (ek, dk)

 

 

 

 

2. Encaps (Bob이 실행):

  • Alice의 Encapsulation Key를 이용해 공유 비밀키 K 생성 + 캡슐화된 메시지 ciphertext 생성
  • 이 ciphertext를 Alice에게 전송

입력:

ek (Alice의 공개키)

 

출력: 

c: ciphertext (암호문)

K: 공유 비밀키 (256비트)

  1. 랜덤 메시지 m 생성 (32바이트)
  2. m과 H(ek)를 해시하여 암호화용 시드 r 및 해시값 d 생성
  3. m, r를 사용하여 Kyber 기반 PKE 암호화를 수행:
    • (u, v) 형태의 암호문 생성 (NTT 기반 다항식 연산)
  4. c = (u, v, d)
  5. 공유 비밀키 K는 H(m, c)를 통해 유도

 

Algorithm 20 ML-KEM.Encaps(ek)
Input: ek — encapsulation key
Output: (c, K) — ciphertext, shared secret key

1: m ←$ B32                         // 무작위 메시지 생성
2: d ← H(m || H(ek))               // 해시 통해 바인딩
3: (cPKE, m') ← K-PKE.Encrypt(ek, m, d)
4: K ← H(m || cPKE)                // 공유키 생성
5: c ← cPKE || d                   // 암호문 구성
6: return (c, K)

 

 

 

3. Decaps (Alice가 실행):

  • 받은 ciphertext와 자신의 비밀키(Decapsulation Key)를 사용해 공유 비밀키 K′를 복원

입력:

dk: 비밀키

c: 암호문

 

출력:

K′: 공유 비밀키 (256비트)

 

  1. 암호문 c를 디코딩 → (u, v, d)
  2. dk의 비밀값을 사용해 (u, v)를 복호화 → 메시지 m′ 복원
  3. ek 해시와 m′을 사용해 새로운 암호문 c′ 재생성
  4. c′ == c이면:
    • K′ = H(m′, c) 사용
  5. 그렇지 않으면:
    • K′ = H(z, c) (z는 비밀키 생성시 포함된 랜덤 값)
    • 마지막 단계는 IND-CCA2 보안을 보장하기 위한 방어 기법입니다. 암호문이 조작되었을 경우에도 K′를 추정할 수 없게 만듭니다.
Algorithm 21 ML-KEM.Decaps(dk, c)
Input: dk — decapsulation key, c — ciphertext
Output: K′ — shared secret key

1: Parse c as (cPKE, d)
2: m′ ← K-PKE.Decrypt(dk, cPKE)
3: (cPKE′, m″) ← K-PKE.Encrypt(ek, m′, d)
4: if cPKE′ == cPKE then
5:     K′ ← H(m′ || c)
6: else
7:     K′ ← H(z || c)              // CCA 방어
8: return K′

 

기술적 특성

  • CRYSTALS-KYBER에서 파생된 알고리즘
  • NTT (Number-Theoretic Transform) 활용해 다항식 곱셈 최적화
  • IND-CCA2 보안 보장 (적응적 선택 암호문 공격에 안전)
  • 키 및 캡슐 크기:
    • 예: ML-KEM-512는 공개키 800바이트, 비밀키 1632바이트, 캡슐화 메시지 768바이트, 공유 비밀키 32바이트

 

 

728x90

+ Recent posts

티스토리툴바