El Gamal 암호화는 Diffie-Hellman 키 교환 방식을 기반으로 하는 공개키 암호화 방식이다.
수신자는 먼저 다음을 계산한다.
- 소수 p를 정한다.
- p보다 작은 x와 g를 정한다.
- y = (g^x) % p
p, g, y를 공개한다.
Encryption
전송할 메세지를 M이라 하고 다음을 계산한다. 이때 k는 p보다 작은 임의의 정수로, 공개하지 않는다.
- a = (g^k) % p
- b = ((y^k) * M) % p
a와 b를 전송한다.
Decryption by Third Party
제3자는 x 또는 k를 알아내면 복호화가 가능하다.
x나 k를 알아내는 것은 이산 로그 방정식을 푸는 것과 같고, g와 p가 충분히 크면 풀이가 매우 오래 걸려 실효성이 없다(이것은 큰 소수를 알아내는 것이 중요한 이유 중 하나이다).
Decryption
(b / (a ^ x)) % p
= (((y^k) * M) / (g^xk)) % p
= (((g^xk) * M) / (g^xk)) % p
= M % p
= M
위를 계산하여 M을 구한다.
+개인적인 생각
a의 값은 M과는 무관하며 오로지 송신자가 결정한 임의의 수 k에 의해 정해진다. 수신자는 k값을 모르지만 계산과정에서 g^xk의 값이 약분되므로 k를 알 필요가 없다. 만약 k를 사용하지 않는다면, 즉 a를 전송하지 않고 b = (y * M) % p만을 전송한다면, 제3자는 b, y, p의 값을 바탕으로 M을 빠르게 구할 수 있게 된다.