09. 이산로그, Diffie-Hellman과 ElGamal

Diffie-Hellman은 공개된 통신만으로 두 사람이 같은 비밀값을 계산하게 한다. 그 기반에는 군의 연산과 이산로그 문제가 있으며, ElGamal 암호도 이 구조를 이용한다.

1. 군(Group)의 정의

집합 G와 이항연산 ∘\circ에 대해 다음 네 가지 조건을 만족하면 (G,∘)(G,\circ)를 군이라고 한다.

  1. Closure: 모든 a,b∈Ga,b\in G에 대해 a∘b∈Ga\circ b\in G

  2. Associativity: (a∘b)∘c=a∘(b∘c)(a\circ b)\circ c=a\circ(b\circ c)

  3. Identity: e∈Ge\in G가 존재하여 a∘e=e∘a=aa\circ e=e\circ a=a

  4. Inverse: 모든 a∈Ga\in G에 대해 a∘a−1=a−1∘a=ea\circ a^{-1}=a^{-1}\circ a=e인 역원이 존재

추가로 a∘b=b∘aa\circ b=b\circ a이면 **Abelian Group(가환군)**이다. 부분집합 H⊆GH\subseteq G가 같은 연산으로 군이면 **Subgroup(부분군)**이다.

군의 예제

  • (Z,+)(\mathbb Z,+), (Q,+)(\mathbb Q,+), (R,+)(\mathbb R,+), (C,+)(\mathbb C,+)는 가환군

  • (Z,+)(\mathbb Z,+)는 (Q,+)(\mathbb Q,+)의 부분군

  • (Q∖{0},⋅)(\mathbb Q\setminus\{0\},\cdot), (R∖{0},⋅)(\mathbb R\setminus\{0\},\cdot), (C∖{0},⋅)(\mathbb C\setminus\{0\},\cdot)는 곱셈에 대한 가환군

  • (Z∖{0},⋅)(\mathbb Z\setminus\{0\},\cdot)는 3의 곱셈 역원이 이 집합 안에 없으므로 군이 아님

  • 가역 2×22\times2 행렬의 곱셈군은 일반적으로 비가환군(AB가 BA와 다름)

  • (Zn,+)(\mathbb Z_n,+)는 n원소의 가환군

  • (Zn∗,⋅)(\mathbb Z_n^*,\cdot)는 n과 서로소인 원소만 포함하는 곱셈 가환군이며 ∣Zn∗∣=φ(n)|\mathbb Z_n^*|=\varphi(n)

2. 원소의 위수와 순환군

2.1 Order of an Element

a∈Ga\in G의 위수는 반복 연산으로 단위원이 처음 나오는 최소 양의 정수다.

ord⁡(a)=min⁡{k≥1:ak=e}.\operatorname{ord}(a)=\min\{k\ge1:a^k=e\}.

예시에서 Z11∗\mathbb Z_{11}^* 안의 3은

31=3, 32=9, 33≡5, 34≡4, 35≡1(mod11).3^1=3,\ 3^2=9,\ 3^3\equiv5,\ 3^4\equiv4,\ 3^5\equiv1\pmod{11}.

따라서 ord⁡(3)=5\operatorname{ord}(3)=5다.

2.2 Cyclic Group과 Generator

어떤 g∈Gg\in G의 위수가 ∣G∣|G|이면 G는 순환군이고 g를 생성원(generator, primitive element)이라 한다.

G=⟨g⟩={e,g,g2,…,g∣G∣−1}.G=\langle g\rangle=\{e,g,g^2,\ldots,g^{|G|-1}\}.

Z11∗\mathbb Z_{11}^* 예시:

21≡2, 22≡4, 23≡8, 24≡5, 25≡10,2^1\equiv2,\ 2^2\equiv4,\ 2^3\equiv8,\ 2^4\equiv5,\ 2^5\equiv10, 26≡9, 27≡7, 28≡3, 29≡6, 210≡1(mod11).2^6\equiv9,\ 2^7\equiv7,\ 2^8\equiv3,\ 2^9\equiv6,\ 2^{10}\equiv1\pmod{11}.

따라서 ord⁡(2)=10=∣Z11∗∣\operatorname{ord}(2)=10=|\mathbb Z_{11}^*|이고, 2는 생성원이다. 반면 3은 전체군의 생성원은 아니지만 부분군

⟨3⟩={1,3,9,5,4}\langle3\rangle=\{1,3,9,5,4\}

의 생성원이다.

3. Discrete Logarithm Problem(DLP)

3.1 정의

군 G의 생성원 g와 A=gaA=g^a가 주어졌을 때 미지의 지수 a를 찾는 문제다.

Given (G,g,A=ga),find a.\text{Given }(G,g,A=g^a),\qquad\text{find }a.

실수에서의 로그 계산과 달리 충분히 큰 유한군에서의 이산로그 계산은 어려울 수 있다. 단, 작은 군에서는 손으로 거듭제곱을 반복하여 쉽게 구할 수 있다. 예를 들어 Z31∗\mathbb Z_{31}^*에서 g=3,A=20g=3,A=20일 때, 3a≡20(mod31)3^a\equiv20\pmod{31}을 만족하는 a를 찾는 문제다.

3.2 알려진 공격 알고리즘

군의 크기와 구조에 따라 다음 알고리즘을 고려한다.

  • 법 p가 충분히 커야 한다. 유한체 곱셈군 전체에 대한 General/Special Number Field Sieve 공격을 고려해야 한다.

  • 부분군의 위수 q도 충분히 커야 한다. Pollard rho 같은 generic DLP 공격의 복잡도는 대략 q\sqrt q에 비례한다.

NIST(2020)의 보안강도별 크기 비교:

목표 강도q의 비트 수p의 비트 수
801601024
1122242048
1282563072
1923847680
25651215360

이는 2020년 시점의 보안강도 비교로, 최신 표준 선택을 대체하는 것은 아니다.

4. Diffie-Hellman Key Exchange

4.1 목적과 역사

Alice와 Bob이 공개 채널만 이용해 같은 공유 비밀값을 생성하는 절차다. Whitfield Diffie와 Martin Hellman이 1976년에 발표했다.

4.2 사전 공유 매개변수

  • 소수 p

  • Zp∗\mathbb Z_p^* 또는 선택된 순환 부분군의 생성원 g

  • 각 참여자는 별도의 개인 지수 a,b를 선택

4.3 키 교환 절차

Alice

  1. 비밀 지수 a 선택

  2. A=ga mod pA=g^a\bmod p 계산

  3. A를 Bob에게 전송

  4. Bob의 B를 받아 KAB=Ba mod pK_{AB}=B^a\bmod p 계산

Bob

  1. 비밀 지수 b 선택

  2. B=gb mod pB=g^b\bmod p 계산

  3. B를 Alice에게 전송

  4. Alice의 A를 받아 KBA=Ab mod pK_{BA}=A^b\bmod p 계산

양쪽 결과의 동일성:

KAB=Ba=(gb)a=gab=(ga)b=Ab=KBA(modp).K_{AB}=B^a=(g^b)^a=g^{ab}=(g^a)^b=A^b=K_{BA}\pmod p.

4.4 계산 예제

매개변수 p=31,g=3p=31,g=3, Alice의 a=6a=6, Bob의 b=8b=8일 때

A=36 mod 31=729 mod 31=16.A=3^6\bmod31=729\bmod31=16. B=38 mod 31=6561 mod 31=20.B=3^8\bmod31=6561\bmod31=20.

공개값을 교환한 뒤

KAB=206 mod 31=4,KBA=168 mod 31=4.K_{AB}=20^6\bmod31=4,\qquad K_{BA}=16^8\bmod31=4.

두 참여자 모두 공유값 4를 얻는다.

5. DH의 안전성과 CDH

공격자 Eve는 g,p,ga,gbg,p,g^a,g^b를 볼 수 있다. 개인 지수 a 또는 b를 획득하면 공유값을 바로 계산할 수 있다. 개인 지수 복원이 DLP와 연결된다.

CDH(Computational Diffie-Hellman) Problem

Given g,ga,gb,compute gab.\text{Given }g,g^a,g^b,\quad\text{compute }g^{ab}.

CDH는 지수 a 또는 b를 반드시 직접 구하지 않더라도 공유 비밀을 계산할 수 있는지를 묻는다. DLP를 풀 수 있으면 CDH도 풀 수 있지만, 일반적으로 두 문제가 다항시간 동치라고 증명된 것은 아니다.

6. Man-in-the-Middle(MITM) Attack

6.1 문제 상황

인증되지 않은 DH는 중간자 Eve가 Alice에게는 Bob인 척, Bob에게는 Alice인 척할 수 있다.

  1. Eve가 비밀 지수 e를 선택하고 E=ge mod pE=g^e\bmod p 계산

  2. Alice가 보낸 A와 Bob이 보낸 B를 가로채 양쪽 모두에게 E 전달

  3. Alice는 KAE=Ea=geaK_{AE}=E^a=g^{ea} 생성

  4. Bob은 KBE=Eb=gebK_{BE}=E^b=g^{eb} 생성

  5. Eve는 A와 B를 알므로 KEA=AeK_{EA}=A^e, KEB=BeK_{EB}=B^e를 각각 계산 가능

따라서 Alice와 Bob이 같은 비밀키를 공유하지 못하고 각각 Eve와 다른 비밀키를 공유하게 된다. Eve는 Alice의 메시지를 복호화하고 재암호화하여 Bob에게 전달할 수 있다.

6.2 방어

**참가자 인증(Authentication)**이 필요하다. 공개값을 보낼 때 전자서명을 덧붙여 인증할 수 있다. 단, 서명만 붙이는 것으로 끝나지 않고 검증키가 실제 해당 주체의 것이라는 신뢰 관계도 필요하다.

MITM 공격 그림

7. ElGamal Encryption

7.1 역사와 성질

Taher El Gamal이 1985년 제안한 공개키 암호다. Probabilistic Encryption이며 각 암호화에 랜덤 지수 r이 필요하다.

7.2 DDH(Decisional Diffie-Hellman) Problem

g,ga,gb,Xg,g^a,g^b,X가 주어졌을 때

X=gab인지X=gcX=g^{ab}\quad\text{인지}\quad X=g^c

인지를 구분하는 문제다. 후자는 독립적으로 무작위 선택한 c의 거듭제곱이다. 적절한 그룹과 DDH 가정 아래 원래의 ElGamal은 IND-CPA 안전성을 얻는다.

7.3 Key Generation

  1. 큰 소수 p, 그리고 관련 부분군 위수 q를 선택

  2. Zp∗\mathbb Z_p^*의 위수 q인 순환 부분군 G의 생성원 g 선택

  3. 비밀 지수 x←Zqx\leftarrow\mathbb Z_q 선택

  4. 공개 원소 X=gx mod pX=g^x\bmod p 계산

pk=(p,q,g,X),sk=x.pk=(p,q,g,X),\quad sk=x.

7.4 Encryption

평문 M을 부분군의 원소로 표현해야 한다. 일회용 무작위값 r←Zqr\leftarrow\mathbb Z_q를 선택하여

C1=gr mod p,C2=MXr mod pC_1=g^r\bmod p,\qquad C_2=M X^r\bmod p

를 계산하고 암호문은

CT=(C1,C2).CT=(C_1,C_2).

이다.

7.5 Decryption

M=C2(C1x)−1 mod p.M=C_2(C_1^x)^{-1}\bmod p.

정합성 증명:

C1x=(gr)x=grx=(gx)r=XrC_1^x=(g^r)^x=g^{rx}=(g^x)^r=X^r C2C1x=MXrXr=M.\frac{C_2}{C_1^x}=\frac{MX^r}{X^r}=M.

C1C_1만으로 메시지를 알아낼 수 없으며, 무작위 r을 선택하므로 같은 메시지에서도 서로 다른 암호문이 나올 수 있다.

8. ElGamal의 곱셈 준동형성과 보안 모델

ElGamal은 원래 구조에서

Enc⁡(M)⋅Enc⁡(M′)∼Enc⁡(MM′)\operatorname{Enc}(M)\cdot\operatorname{Enc}(M') \sim\operatorname{Enc}(MM')

라는 곱셈 준동형성을 갖는다. 암호문 두 쌍의 각 성분을 곱하면 그 결과는 평문의 곱에 대한 적절한 무작위화된 암호문이 된다. 이 성질은 응용에서 유용하지만, 원래 ElGamal 자체가 IND-CCA2를 제공하지 않음도 뜻한다. 더 강한 보안성을 얻으려면 별도의 안전한 변환이 필요하다.

9. 중요 비교

개념질문결과
DLPg,gag,g^a에서 a를 계산할 수 있는가?개인 지수 복원 문제
CDHg,ga,gbg,g^a,g^b에서 gabg^{ab}을 계산할 수 있는가?공유 비밀 계산 문제
DDH주어진 X가 gabg^{ab}인지 구별하는가?공유 비밀의 무작위성 구별
DH공개 채널로 같은 비밀을 공유할 수 있는가?가능하지만 인증 없는 MITM에 취약
ElGamal공개키로 확률적 메시지 암호화를 할 수 있는가?DDH 가정 하 IND-CPA
Discussion

Comments