[암호학] 7.5 The ElGamal Public Key Cryptosystem

Chapter6에서는 인수분해의 계산 난이도에 기반한 공개키 암호체계에 대해 배웠다.

지금까지 알아본 이산로그의 계산 난이도를 활용한 보안 시스템 설계도 물론 가능하다.

 

Alice가 Bob에게 메시지 m을 보내고 싶어한다고 가정하자.

가장 먼저 Bob은 큰 소수 p와 원시근 a를 선택한다. (0 <= m < p인 정수)

만약 m이 크다면 작은 블록들로 나누어준다.

Bob은 비밀 정수 a를 선택하고 b = a^a (mod p)를 계산한다.

이때 (p, a, b)는 공개되며, Bob의 공개키가 된다.

 

Alice는 아래의 작업을 수행한다.

1. (p, a, b)를 가져온다.

2. 비밀 난수 정수 k를 선택하고 r = a^k (mod p)를 계산한다.

3. t = b^k*m (mod p)를 계산한다.

4. (r, t)를 Bob에게 보낸다.

 

Bob은 아래의 식을 통해 메시지를 복호화한다.

이것은 아래와 같은 원리로 계산된다.(참고)

 

만약에 Eve가 a를 알아낸다면, Eve도 Bob과 같은 과정을 거쳐서 복호화가 가능하다.

그러므로, Bob이 보안을 지키는 것은 매우 중요하다.

여기서 a, b는 공개되며 b = a^a (mod p)인데, 이산로그를 계산하는 것은 매우 어렵기 때문에 보안이 유지된다.

 

k는 랜덤 정수이므로, b^k는 0이 아닌 랜덤 정수 (mod p)가 될 것이다.

따라서 t = b^k*m (mod p)는 m에 랜덤 정수를 곱하고 t는 랜덤 mod p 이다(m=0인 경우는 제외).

그러므로, t는 Eve에게 메시지 m에 대한 정보를 추가 제공하지 않는다. 즉, r을 알아도 Eve에게는 영양가있는 정보가 될 수 없다.

 

정수 k는 이산로그문제이므로 r을 통해서 알아내기 힘들다. 하지만, Eve가 k를 찾으면 메시지 m에 해당하는 t*b^(-k)를 알아낼 수 있다.

 

각 메시지 m에 대해 서로 다른 임의의 k를 사용하는 것은 중요하다. Alice가 Bob에게 메시지 m_1과 m_2를 암호화하고 각 메시지에 동일한 값 k를 사용한다면, r은 두 메시지에 대해 동일하므로 암호문은 (r, t_1)과 (r, t_2)가 된다. 이때, Eve가 평문 m_1을 찾으면 아래와 같이 m_2도 찾아낼 수 있다.

Eve는 t_1, t_2를 알고 있어 아래와 같이 m_2를 계산할 수 있다.

Chapter 16에서는 타원 곡선을 활용한 ElGamal method를 다룰 예정이다.

---

7.5.1 Security of ElGamal Ciphertexts

Eve가 RSA 암호문 c에 해당하는 평문 m을 얻었다고 주장한다고 가정하자.

- Eve의 주장을 증명하는 것은 간단하다. m^e (mod n)을 계산하고 이 값이 c와 같은지 확인하면 된다.

 

Eve가 ElGamal 암호화에 필요한 (r, t)에 해당하는 메시지 m을 소유한다고 주장한다면 입증할 수 있을까?

- 해당 경우에는 Diffie-Hellman problem만큼이나 계산이 어렵다. 또한, ElGamal 알고리즘은 RSA 알고리즘과 매우 다르다. (Ex. OAEP를 통해서 RSA 평문에 randomness를 추가하면 RSA 암호화 방식도 유사한 속성을 가짐)

---

 

Proposition1.

- Decision Diffie-Hellman problem mod p를 해결하는 시스템을 사용하여 mod p ElGamal 암호문의 유효성을 결정할 수 있으며, mod p ElGamal 암호문의 유효성을 결정하는 시스템을 사용하여 Decision Diffie-Hellman 문제 mod p를 해결할 수 있다.

 

Proof1.

- ElGamal 암호 해독의 정확성을 판단할 수 있는 기계 M_i가 있다고 가정해 보자. 입력 p, a, b, (r, t), m이 주어졌을 때 기계는 m이 (r, t)를 사용한 복호화의 결과라면 yes"를 출력하고 그렇지 않으면 "no"를 출력할 것이다.

- Diffie-Hellman 문제를 해결하기 위해 이 기계를 사용해보자. a^x과 a^y가 주어지고 c = a^xy인 c가 있는지 여부를 결정하려고 한다고 가정하자.

- b = a^x, r = a^y (modp)로 두고, t = c, m = 1로 하자. 이 모든 값을 M_1에 입력한다. 이때 x가 비밀 정수 a이고 a^y가 r = a^k를 대신한다. (r,t)를 사용한 올바른 복호화 결과는 tr^(-a) = cr^(-x) = ca^(-xy)이다. 따라서 M_1은 m = 1이 ca^(-xy)(mod p), 즉 c = a^xy(mod p)일 때 정확하게 "yes"를 출력한다. 이것으로 decision Diffie-Hellman problem을 해결할 수 있다.

 

---

반대로, decision Diffie-Hellman problem을 해결할 수 있는 기계 M_2가 있다고 가정하자.

M_2에 p, a, a^x, a^y, c를 입력하면 M_2는 c = a^xy이면 "yes"를 출력하고 그렇지 않으면 "no"를 출력한다.

 

ElGamal (r, t)을 사용한 암호문의 복호화를 수행시킨다.

b = a^a를 입력하면 a^x이므로 x = a이다. 또한, r = a^k은 a^y과 같으므로 y = k이다.

c로는 tm^(-1)(mod p)를 입력한다. m = tr^(-a) = ta^(-xy)인 경우에만 m이 암호문(r, t)에 대한 올바른 평문이며, tm^(-1) = a^xy인 경우에 성립한다 하자.

그렇다면 c = tm^(-1)가 Diffie-Hellman problem의 solution인 경우에만 m이 올바른 평문이다.

M_2는 이러한 입력을 사용하여 m이 올바른 일반 텍스트일 때 정확하게 "yes"를 출력합니다.

 

방금 사용된 추론은 계산적 Diffie-Hellman problem을 해결하는 것이 ElGamal 시스템을 깨는 것과 같다는 것을 보여주는 데에도 사용될 수 있다.

 

Proposition2.

Computational Diffie-Hellman problem mod p를 해결하는 시스템을 사용하여 Mod p ElGamal 암호문를 복호화할 수 있으며, Mod p ElGamal 암호문을 복호화하는 기계(machine)을 사용하여 Diffie-Hellman problems mod p를 해결할 수 있다.

 

Proof2.

모든 ElGamal 암호문을 복호화할 수 있는 기계 M_3가 있다면 b = a^x(따라서 a = x)와 r = a^y를 입력한다. t는 0이 아닌 아무 값이다. 그리고 M_3은 m = tr^(-a) = ta^(-xy)를 출력한다. 따라서 tm^(-1)(mod p)는 computational Diffie-Hellman 문제에 대한 solution인 a^xy를 출력한다.

반대로, computational Diffie-Hellman problem을 해결할 수 있는 기계 M_4가 있다고 가정한다. ElGamal 암호문(r, t)이 있으면 a^x = a^a = b 및 a^y = a^k = r을 입력한다. 그러면 M_4는 a^xy = a^ak을 출력한다. 결과적으로 m = tr^(-a) = ta^(-ak)이므로 일반 텍스트 m을 구할 수 있다.