2. 양자시대의공개키암호

1. 양자컴퓨터와 PQC

• 양자컴퓨터의 Shor 알고리즘으로 인해 RSA, ECC가 안전하지 않게 된다.
• 이를 대비하기 위해 PQC가 개발되었다.
• NIST는 ML-KEM(키 교환), ML-DSA(전자서명) 등을 표준으로 선정하였다.

 

2. 기존 암호와 PQC의 역할

• AES : 실제 데이터를 암호화하는 대칭키 암호
• RSA/ECC : 키 교환과 전자서명
• PQC : 양자컴퓨터에도 안전한 공개키 암호
• PQC는 AES를 대체하는 것이 아니라 공개키 암호를 대체한다.

 

3. 보안 통신 과정

• 인증서 확인 → KEM으로 공유 비밀 생성 → HKDF로 세션키 생성 → AES-GCM으로 데이터 암호화 → 키 관리
• 실제 데이터는 AES-GCM이 암호화하고, ML-KEM은 공유 비밀만 생성한다.

 

4. 격자

• 격자는 정수 좌표들의 집합이다.
• 좋은 기저(비밀키)는 계산이 쉽고, 나쁜 기저(공개키)는 계산이 어렵다.
• 이러한 특성을 이용해 암호의 안전성을 확보한다.

 

5. 격자의 어려운 문제

• SVP : 가장 짧은 벡터 찾기
• CVP : 가장 가까운 벡터 찾기
• 이 문제들이 어렵기 때문에 격자 암호가 안전하다.

 

6. SIS 

• Az ≡ 0 (mod q) 를 만족하는 짧은 벡터 z를 찾는 문제이다.
• 작은 해를 찾는 것이 매우 어렵다.
• 해시, 전자서명 등에 활용된다.

 

7. LWE 

• b = As + e에서 작은 오류 e 때문에 비밀키 s를 찾기 어려운 문제이다.
• 노이즈가 보안의 핵심이다.
• 암호화와 키 교환의 기반이 된다.

 

8. Regev 암호

• LWE를 이용한 기본 공개키 암호 방식이다.
• 공개키 생성 → 암호화 → 복호화 과정을 통해 비트를 안전하게 암호화한다.
• ML-KEM의 기본 개념이 되는 암호 방식이다.

 

9. ML-KEM

• KEM은 공유 비밀을 생성하는 방식이다.
• 과정은 KeyGen → Encaps → Decaps 순서이다.
• 생성된 공유 비밀은 KDF를 거쳐 AES 키로 사용된다.

 

10. Ring-LWE와 Module-LWE

• 일반 LWE는 공개키가 매우 크다.
• Ring-LWE는 다항식을 사용하여 크기를 줄인다.
• Module-LWE는 Ring-LWE와 LWE의 장점을 결합한 방식이며 Kyber에서 사용된다.

 

11. NTT

• 다항식 곱셈을 빠르게 수행하는 알고리즘이다.
• 계산 속도를 O(n²) → O(n log n) 수준으로 줄인다.
• 보안을 높이는 기술이 아니라 연산 최적화 기술이다.

 

12. 난수와 노이즈

• 안전한 난수 생성은 암호의 핵심이다.
• 노이즈와 난수 품질이 낮으면 암호도 안전하지 않다.

 

13. 구현 최적화

• NTT
• Montgomery/Barrett Reduction
• CBD 샘플링
• Seed Expansion
• 압축
• 상수시간 구현
• 빠른 구현뿐 아니라 정보가 새지 않는 구현이 중요하다.

 

14. TLS에서의 PQC 적용

• 기존 X25519 대신 ML-KEM 또는 하이브리드 방식(X25519+ML-KEM)을 사용할 수 있다.
• AES-GCM은 그대로 사용되며 키 교환 부분만 변경된다.

 

15. ML-KEM 표준

• ML-KEM-512 : AES-128 수준
• ML-KEM-768 : AES-192 수준
• ML-KEM-1024 : AES-256 수준
• 현재 TLS에서는 ML-KEM-768이 가장 많이 사용된다.

 

16. PKI와 ML-DSA

• ML-KEM은 키 교환을 담당한다.
• ML-DSA는 전자서명을 담당한다.
• PQC 전환 시 키 교환뿐 아니라 인증서와 전자서명도 함께 전환해야 한다.

 

17. 실습 

• Python으로 LWE 암호화/복호화를 구현할 수 있다.
• liboqs를 이용하면 실제 ML-KEM을 실행하여 공개키, 비밀키, 암호문, 공유 비밀을 생성할 수 있다.