일반적인 공개키 암호화의 안전성은 그것의 소인수분해가 얼마나 어려운가에 달려있다. 하지만, 그것 외에도 discrete logarithm 문제를 효율적으로 계산할 수 없다는 것에 착안하여 공개키 방식의 암호화를 할 수도 있다. ElGamal 공개키 암호화가 대표적인 방법이다.
Alice가 Bob에게 어떤 메세지 m을 보내려고 한다. Bob은 커다란 Prime Number p를 선택하고, 그것의 Primitive Root α를 선택한다. 여기서, m은 0 ≤ m < p인 정수이다. m이 크다면, 이것을 블럭 크기로 분할한다. Bob은 비밀키 a를 선택하고, β ≡ α^a (mod p)를 계산한다. 여기서 (p, α, β)를 공개하며, 이것이 Bob의 공개키가 된다. Alice는 다음의 과정을 거친다.
1. Bob에게 메세지 m을 보내기 위해, Bob의 공개키 (p, α, β)를 가져온다.
2. 임의의, 공개되지 않는 정수 k를 선택하고, r ≡ α^k (mod p)를 계산한다.
3. t ≡ β^k * m (mod p)를 계산한다.
4. Alice는 Bob에게 (r, t)를 보낸다.
Bob은 다음을 계산함으로써 이 메세지를 decrypt 할 수 있다.
tr^(-a) ≡ m (mod p)
∵ tr^(-a) ≡ β^k * m * (α^k)^(-a) ≡ (α^a)^k * m * α^(ak) ≡ m (mod p)
여기서, k는 임의로 선택되는 정수이기 때문에, β^k (mod p)는 임의의 0이 아닌 정수이다. 따라서, t = β^k * m (mod p)는 임의의 수에 대한 m의 곱이며, t는 mod p에 대한 임의의 수가 된다(m = 0인 경우를 피한다면). 따라서, Eve는 t만 가지고서 m에 대한 어떠한 정보도 더 알아낼 수 없다. r의 경우도, Eve에게 추가의 정보를 주지 않는 것으로 알려져 있다.
정수 k를 결정하는 것 또한 어려운 것으로 알려져 있는데, 이것은 k를 알아내는 것이 discrete logarithm 문제이기 때문이다. 만약 Eve가 k를 알아낸다면, Eve는 t * β^(-k)를 알아낼 수 있고, 메세지 m을 알아낼 수 있다.
또, 각각의 메세지에 다른 k를 선택해야 한다는 것도 중요한 점이다. 즉, Alice가 Bob에게 메세지 m1을 보내기 위해 (r, t1)를 보내게 되며, 같은 k를 사용했다면 다른 메세지 m2는 (r, t2)가 된다. Eve가 만약 메세지 m1을 가지고 있다면, t1 / m1 ≡ β^k ≡ t2 / m2 (mod p)이며, Eve는 t1과 t2을 알고 있기 때문에, m2 ≡ t2 * m1 / t1 (mod p)를 통해 메세지 m2를 알 수 있게 된다.
Reference
Wade Trappe, Lawrence Washington, Introduction to Cryptography with Coding Theory, Second Edition, PEASRON Education
Alice가 Bob에게 어떤 메세지 m을 보내려고 한다. Bob은 커다란 Prime Number p를 선택하고, 그것의 Primitive Root α를 선택한다. 여기서, m은 0 ≤ m < p인 정수이다. m이 크다면, 이것을 블럭 크기로 분할한다. Bob은 비밀키 a를 선택하고, β ≡ α^a (mod p)를 계산한다. 여기서 (p, α, β)를 공개하며, 이것이 Bob의 공개키가 된다. Alice는 다음의 과정을 거친다.
1. Bob에게 메세지 m을 보내기 위해, Bob의 공개키 (p, α, β)를 가져온다.
2. 임의의, 공개되지 않는 정수 k를 선택하고, r ≡ α^k (mod p)를 계산한다.
3. t ≡ β^k * m (mod p)를 계산한다.
4. Alice는 Bob에게 (r, t)를 보낸다.
Bob은 다음을 계산함으로써 이 메세지를 decrypt 할 수 있다.
tr^(-a) ≡ m (mod p)
∵ tr^(-a) ≡ β^k * m * (α^k)^(-a) ≡ (α^a)^k * m * α^(ak) ≡ m (mod p)
여기서, k는 임의로 선택되는 정수이기 때문에, β^k (mod p)는 임의의 0이 아닌 정수이다. 따라서, t = β^k * m (mod p)는 임의의 수에 대한 m의 곱이며, t는 mod p에 대한 임의의 수가 된다(m = 0인 경우를 피한다면). 따라서, Eve는 t만 가지고서 m에 대한 어떠한 정보도 더 알아낼 수 없다. r의 경우도, Eve에게 추가의 정보를 주지 않는 것으로 알려져 있다.
정수 k를 결정하는 것 또한 어려운 것으로 알려져 있는데, 이것은 k를 알아내는 것이 discrete logarithm 문제이기 때문이다. 만약 Eve가 k를 알아낸다면, Eve는 t * β^(-k)를 알아낼 수 있고, 메세지 m을 알아낼 수 있다.
또, 각각의 메세지에 다른 k를 선택해야 한다는 것도 중요한 점이다. 즉, Alice가 Bob에게 메세지 m1을 보내기 위해 (r, t1)를 보내게 되며, 같은 k를 사용했다면 다른 메세지 m2는 (r, t2)가 된다. Eve가 만약 메세지 m1을 가지고 있다면, t1 / m1 ≡ β^k ≡ t2 / m2 (mod p)이며, Eve는 t1과 t2을 알고 있기 때문에, m2 ≡ t2 * m1 / t1 (mod p)를 통해 메세지 m2를 알 수 있게 된다.
Reference
Wade Trappe, Lawrence Washington, Introduction to Cryptography with Coding Theory, Second Edition, PEASRON Education