1. 개요
공개키 암호화 방식 중 하나이다. 이집트 암호학자 Taher Elgamal이 1985년에 개발한 방식이다. 이산 로그 문제에 기반을 두고 있으며, 디피-헬만 키 교환 알고리즘을 발전시켜 키 교환에 그치지 않고 RSA 같이 암호화-복호화를 지원하는 동시에 전자서명으로도 활용될 수 있는 알고리즘이다. 현재 PGP 등 여러 널리 쓰이는 암호화 모듈 패키지에 탑재된 방식이다.2. 작동 방식
상기하였듯이, 이산 로그 문제를 다항 시간 내로 풀 수 있는 기법이 존재하지 않는다는 상황을 활용한 기법이기에 큰 수의 거듭제곱 같은 걸 많이 계산한다.여기서는 앨리스와 밥이 통신을 한다고 가정할 것이며, 키를 생성하는 사람은 앨리스로 두겠다.
2.1. 암복호화
2.1.1. 키 생성
통신을 위해 앨리스는 다음과 같은 수들을 준비한다.[1]- (충분히 큰) 소수 [math(p)],
- [math(1, \cdots, p - 1)] 중 하나인 (충분히 큰) [math(g)],
- [math(1, \cdots, p - 2)] 중 하나인 [math(x)][2].
아래를 보면 알겠지만 [math(x)]는 충분히 크고 예측이 안 되는 수인 것이 좋다.
이제 [math(h = g^x \textrm{ mod } p)]라고 두겠다. 이제 다음과 같이 공개키(public key)와 개인키(private key)를 정의하겠다.
- 공개키: [math((p, g, h))],
- 개인키: [math(x)].
앨리스는 이 공개키를 밥에게 건네줄 것이며[3], 개인키는 누구에게도 공개하지 않을 것이다.
2.1.2. 암호화
이제 밥은 앨리스에서 어떤 수 [math(m)] ([math(1 \le m \le p - 1)])을 보내고자 한다.[4] 이를 위해 밥은 다음을 준비한다.- [math(1, \cdots, p - 2)] 중 하나인 [math(y)].
이 수 역시 [math(x)]와 마찬가지로 충분히 크고 예측이 안 되는 수인 것이 좋다. 아래의 계산이 끝난 후 이 [math(y)]는 폐기하는 것이 좋을 것이다. 이제 밥은 다음을 계산할 것이다.
[math(\displaystyle c_1 = g^y \textrm{ mod } p)],
[math(\displaystyle c_2 = m \cdot h^y \textrm{ mod } p)].
이렇게 구해진 [math((c_1, c_2))]가 밥이 앨리스에게 보낼 암호화된 메세지이다.[5] 여기서 [math(c_2)]가 본체이고 [math(c_1)]은 밥이 앨리스에게 알려주는 복호화를 위한 힌트라고 생각해도 좋을 것이다. 하지만 공격자가 이 메세지를 입수한다고 해도 [math(x)]와 [math(y)]를 모르면 아래에 소개할 [math(h^{-y} \textrm{ mod }p)]는커녕 [math(h^y)]가 뭔지도 알아낼 수 없을 것이다. 그나마 힌트랍시고 있는 [math(c_1)]으로부터 [math(y)]를 구하는 것은 (그리고 [math(h)]로부터 [math(x)]를 구하는 것도 포함하여) 위에서 언급한 이산 로그 문제로, 상기했듯이 이는 현재 기술로 적당한 시간과 연산량으로 풀 수 없는 문제다.
2.1.3. 복호화
앨리스가 밥으로부터 [math((c_1, c_2))]를 받았다고 하자. 그러면 이제 앨리스는 다음을 계산한다.[math(\displaystyle t = c_1^{-x} \textrm{ mod } p)].
웬 유리수가 나오냐고 하겠지만, 이건 그런 유리수가 아닌 [math(c_1^x t \equiv 1 \textrm{ (mod $p$)})]를 만족하는 그런 정수 [math(t)]를 의미한다. 이건 확장된 유클리드 알고리즘으로 계산할 수 있지만, 페르마의 소정리에 의하여 [math(c_1^{p - 1} \equiv 1 \textrm{ (mod $p$)})]임을 이용하면 [math(t = c_1^{p - 1 - x} \textrm{ mod } p)]로 계산할 수도 있다. 표기가 헷갈릴 수 있지만, 군론적으로 생각해 보면 엄연히 맞는 표기이며, 이 녀석이 앨리스의 최종 계산에서 수행하는 핵심적인 역할을 보면 이 표기가 적합하다는 것을 알 수 있다.
여기서 [math(c_1^x \equiv (g^y)^x \equiv g^{xy} \equiv (g^x)^y \equiv h^y \textrm{ (mod $p$)})]임을 먼저 체크해 두자.
이제 앨리스는 다음을 계산할 것이다.
[math(\displaystyle y = c_2 \cdot t \textrm{ mod } p)].
이때 다음을 알 수 있다.
[math(\displaystyle c_2 \cdot t \equiv (m \cdot h^y) \cdot t \equiv m \cdot (c_1^x t) \equiv m \textrm{ (mod $p$)})].
이렇게 해서 앨리스는 밥이 보내고자 했던 메세지 [math(m)]을 얻을 수 있다.
2.2. 전자서명
RSA이 그러하듯, ElGamal 역시 전자서명 기능을 지원한다. 다만 공개키와 개인키를 그냥 바꾸기만 하면 되는 RSA와는 다르게 ElGamal은 제법 다른 방식으로 전자서명 기능을 수행한다.여기서는 앨리스가 서명을 하는 것으로 하겠다. 마침 위에서 만든 키들이 있으니, 이들을 이용해 전자서명을 만든다고 해 보자.[6] 이를 위해 먼저 공개키와 개인키를 위와 똑같이 정한다.
- 공개키: [math((p, g, h))],
- 개인키: [math(x)].
앨리스는 앨리스 자신이 발급할 전자서명을 확인하고자 하는 모든 유저에게 이 공개키를 최대한 안전하게 배포할 것이다.[7]
전자서명을 위해 하나 더 필요한 것이 있는데, 바로 해시 함수이다. 여기서 [math(2^N - 1 < p)]를 만족하는 [math(N)]을 하나 고르자. 여기서 쓰일 해시 함수 [math(H)]는 메세지 [math(m)]을 받았을 때 [math(N)] 비트 짜리 해시값을 주는 함수라고 하겠다.[8][9]
그 다음, 앨리스는 다음과 같은 수를 준비한다.
- [math(2, \cdots, p - 2)] 중 하나이며 [math(p - 1)]과 서로소인 (충분히 큰) [math(k)].
이제, 앨리스는 자신이 서명할 메세지 [math(m)]에 대하여 다음을 계산한다. (계산 직후 [math(k)]는 폐기하는 것이 좋다.)
[math(\displaystyle r = g^k \textrm{ mod }p)],
[math(\displaystyle s = (H(m) - xr) k^{-1} \textrm{ mod }(p - 1))].
여기서 [math(k^{-1})]은 [math(kl \equiv 1 \textrm{ (mod $(p - 1)$)})]을 만족하는 [math(l)]과 같은 값이며, 이는 확장된 유클리드 알고리즘으로 계산할 수 있다. 이때 [math(s)]가 0이 나올 수 있는데, 이런 경우엔 [math(k)]를 다시 고르고 [math(r)]과 [math(s)]를 계산한다. 물론, 또 [math(s = 0)]가 나오면 다시 고르고 또 계산해야 하며, 이를 [math(s \ne 0)]일 때까지 반복해야 한다. 이렇게 계산된 [math((r, s))]가 앨리스의 전자서명이다.
이제 밥이 앨리스 혹은 다른 누군가로부터 [math(m)]과 [math((r, s))]를 받았다고 하자. 밥은 이 [math(m)]을 전송받는 도중 (오류 혹은 악의적인) 변조가 있었는지 알고 싶어 한다. 상기했듯이 밥은 이미 앨리스의 [math((p, g, h))]를 가지고 있다. 이제 이들을 이용해서 약간의 계산을 수행해 보자.
[math(\displaystyle z = h^r r^s \textrm{ mod } p)].
변조가 없다는 가정 하에 이 값이 어떤 값이랑 같은지 차근차근 살펴 보자. 먼저 다시 한 번 페르마의 소정리에 의하여 [math(r^s \equiv g^{a} \textrm{ (mod $p$)})] ([math(a := (H(m) - xr) \textrm{ mod } (p - 1))])임을 바로 확인할 수 있다. 그러면, [math(z \equiv g^{xr} g^{a} \equiv g^{xr + a} \textrm{ (mod $p$)})]임을 알 수 있고, 또 한 번 페르마의 소정리에 의하여 다음을 알 수 있다.
[math(\displaystyle z \equiv g^{H(m)} \textrm{ (mod $p$)})].
이때 우변은 밥이 [math(g)]와 [math(m)] 둘 다 가지고 있으므로 직접 따로 계산 가능한 값이다.
여기서 강조할 것은 [math(r)]과 [math(s)]를 어떤 의도한 [math(m')]에 대하여 [math(h^r r^s \equiv g^{H(m')} \textrm{ (mod $p$)})]이도록 변조하는 것이 사실 상 불가능하다는 것이다. 이를 수행하려면 [math(x)]가 필요하기 때문이다. 거꾸로 해시 함수의 특성 상 주어진 [math(r)]과 [math(s)]에 대하여 [math(h^r r^s \equiv g^{H(m')} \textrm{ (mod $p$)})]을 만족하는 다른 [math(m')]을 (그것도 공격자의 입맛에 맞는 값을 갖도록) 구하는 것 또한 불가능하다. 그렇기 때문에 저 등식이 성립하는지 유무를 확인하는 것으로 [math(m)]이 문제 없이 (즉, 변조 없이) 잘 전송된 것임을 확인할 수 있다.
3. 일반화
위에서는 소수 [math(p)]를 골라 [math(p)]로 나눈 나머지들 간의 연산으로 암복호화를 수행하였다. 이 부분을 유한 순환군(finite cyclic group)으로 해석할 수 있다. 즉, 위의 경우에선 순환군이 곱셈 연산으로 연산이 정의된 [math((\Z/p\Z)^*)]인 경우이고[10] 지수 부분을 제외한 밑수들은 전부 [math((\Z/p\Z)^*)]의 원소이며 그 값들을 곱하여 [math(p)]로 나눈 나머지를 취하는 것은 [math((\Z/p\Z)^*)]의 연산을 수행한 것이라고 해석할 수 있다. 한편, [math(g)]는 이 순환군의 생성자(generator)로 일반화할 수 있으며, 위에서 나온 지수부에 쓰일 값들에 주어진 조건 중 [math(p - 2)]에 해당하는 값은 순환군의 위수 [math(q)]에서 1을 뺀 값이라고 볼 수 있다.[11] 이러한 아이디어에 입각하여, 위수(order)가 [math(q)]인 순환군 [math(G)]가 주어져 있을 때 공개키, 개인키 및 암호화와 복호화를 다음과 같이 고칠 수 있다.- 공개키: [math((G, q, g, h))] ([math(h = g^x)]),
- 개인키: [math(x)] ([math(1 \le x \le q - 1)]),
- 암호화: [math(c_1 = g^y)], [math(c_2 = m \cdot h^y)] ([math(1 \le y \le q - 1)]),
- 복호화: [math(c_2 \cdot c_1^{-x} = c_2 \cdot c_1^{q - x})].
여기서 라그랑주 정리에 의하여 임의의 [math(a \in G)]에 대하여 [math(a^q = 1)]임을 상기하면[12][13] [math(c_1^{q - x} = c_1^{-x})]임을 바로 알 수 있다. 이 부분이 페르마의 소정리의 일반화에 해당한다.
사실 상 위에서 소개한 정수론적 방식 중 [math(p)]를 [math(G, q)]로, [math(p - 2)]를 [math(q - 1)]로 바꾼 다음, [math(\textrm{mod $p$})]를 빼고 다시 쓴 것과 다를 게 없어 보인다. 거꾸로, [math(G)]가 [math((\Z/p\Z)^*)]인 경우, [math(q = p - 1)]이 되고 위의 암복호화에서 사용된 곱 연산들이 전부 정수들의 곱에서 [math(p)]로 나눈 나머지를 구하는 것으로 바뀌게 되어 위의 정수론적 ElGamal 방식과 일치하게 된다. 즉, (정수론적) ElGamal 방식은 이 방식의 특수한 경우 중 하나라고 봐도 좋을 것이다. 이제 [math(G)]를 충분히 크고 복잡하게 정하기만 하면, 특히 이산 로그 문제와 같이 [math(h = g^x)]에서 [math(h)]와 [math(g)]를 알아도 [math(x)]를 알기 어렵도록 [math(G)]를 정해 놓으면, 통신에 필요한 보안도 확보하게 될 것이다. 가장 대표적인 것으로는 타원곡선으로부터 얻어지는 유한 순환군을 활용하는 것을 들 수 있다.[14]
다만 위에서 소개한 서명 알고리즘을 순환군으로 일반화하는 것은 어렵다. 또다른 법 연산 [math(\textrm{mod $(p - 1)$})]이 쓰이고, [math(r)]이 [math(G)]의 원소이어야 할텐데 이 [math(r)]이 [math(s)]와 [math(z)]의 지수에 들어가 버리는 등, 바로 [math(G)]의 연산들로 바꾸기에는 무리가 있다. 이로 인해 타원곡선 연산을 적용시키기 위해서는 ElGamal 서명 방식을 다소 변형시킨 방식을 기본으로 하여 서명 알고리즘을 구성해야 한다. 이렇게 해서 나온 것이 ECDSA이다.[15]
4. 기타
[1] 이 문서의 어지간한 표기는 영문 위키피디아(#, #)를 따랐다.[2] [math(p - 1)]으로 안 나누어 떨어지기만 하면 사실 저 범위를 넘어서도 상관 없지만, 페르마의 소정리에 의하여 어차피 저 중에서 고르는 것과 차이가 없다.[3] 이 단계에서 중간자 공격을 조심하여야 한다. 이를 위해 키만 보내지 않고 밥이 이미 보유하고 있는 어떤 공개키로 (보통 인증기관(CA)의 공개키이다) 확인이 가능한 전자서명을 같이 보낼 수 있다. 자세한 것은 전자서명 문서 및 TLS 문서를 참고하라.[4] 모든 [math(N)] 비트 데이터는 0부터 [math(2^N - 1)]까지의 수로 유일하게 표현할 수 있다. 따라서 [math(N)]을 [math(2^N - 1 < p)]이도록 정한 다음, 데이터를 [math(N)] 비트 씩 잘라다 암호화를 하여 전송하면 임의의 크기의 데이터를 문제 없이 암호화하여 전송할 수 있을 것이다. 물론 원문을 몇 비트 씩 쪼개서 보냈는지도 앨리스에게 따로 알려줘야 한다.[5] 다만 여기서 [math(c_2)]가 [math(m)]과 선형인 것이 보안 상 문제가 될 수 있다. 이를 해결하기 위해 [math(m)]을 그대로 암호화하는 대신 [math(m)] 앞이나 뒤에 적당한 무작위 패딩(padding)을 붙인 다음 암호화할 수 있다. (솔트(salt)를 생각하자.) 물론 밥은 앨리스에게 패딩이 어디서부터 어디까지인지 따로 알려줘야 할 것이다. 아니면 이것저것 안전장치를 붙여서 확장시킨 알고리즘을 쓸 수도 있는데, Cramer-Shoup 방식 같은 것을 참고하자.[6] 여기선 설명의 편의 상 이렇게 설정했지만, 이는 위험천만한 행동이며, 당연히 암복호화에 사용되는 키와 전자서명에 사용되는 키는 완전히 달라야 한다.[7] 예를 들어 앨리스가 공인된 인증기관일 경우, 운영체제나 웹 브라우저가 이 공개키를 탑재하고 있을 것이다. 물론 이 공개키가 '안전하게 배포'되기 위해서는 운영체제나 웹 브라우저에 악의적인 변조가 없어야 할 것이다. 불법 복제나 불법 다운로드 같은 경로로 이들을 설치하면 이러한 변조로부터의 안전이 절대 담보되지 않으니, 최소한 이 둘만큼은 정품을 공인된 경로로 입수 및 설치해야 함을 알 수 있다.[8] 해시 문서에서도 나와 있는 내용이지만, 이 해시 함수는 데이터 비교를 위해 쓸 수 있을 정도로 충돌 가능성이 적어야 하며 (즉, [math(H(m) \ne H(m'))]일 때 [math(m = m')]일 확률이 작아야 하며), 같은 해시값을 가지지만 원문과 전혀 다른 (그리고 어떤 (악의적인) 의도를 위한 내용이 담긴) 메세지를 찾는 것이 현실적인 시간 및 연산량 내에 사실 상 불가능하다는 성질을 가지고 있어야 한다.[9] 그냥 해시 함수를 쓰지 말고 원문으로 해도 괜찮냐고 할 수 있는데, 원문이 충분히 작거나 하지 않은 이상, 전체 메세지를 변환하는 것은 비효율적이기에 해시 함수를 쓰는 것이다.[10] 즉, 이 안에서의 덧셈은 무시한 것이다.[11] 주석 중에 상기했듯이 이 범위를 넘어가도 상관 없긴 하다. 이 경우에는 후술할 라그랑주 정리에 의한 것이다.[12] [math(G)]가 유한하므로 [math(a^r = 1)]인 [math(r)]이 존재할텐데, 그 중 최소인 [math(r)]이 [math(a)]로 생성되는 [math(G)]의 부분군의 위수와 같다는 것을 쉽게 보일 수 있다. 이제 라그랑주 정리에 의해 부분군의 위수 [math(r)]은 [math(G)]의 위수 [math(q)]를 나누어야 하므로, [math(a^q)]는 [math(a^r = 1)]의 거듭제곱, 즉 1임을 알 수 있다.[13] 편의 상 [math(G)]의 항등원(identity)을 1로 표기하였다.[14] 대수학이 익숙치 않은 이들에겐 이쪽으로 넘어가는 것이 약간 고역일 수 있는 게 사실 익숙해도 헷갈리는 건 똑같다, 타원곡선에서 다뤄지는 군의 연산은 덧셈으로 표기된다. 그래서 여기서 [math(a^x)]로 썼던 것을 타원곡선 쪽 표기 대로 쓰자면 [math(xa)]로 써야 한다는 것이다.[15] 이름과는 다르게 DSA의 알고리즘을 그대로 옮긴 것도 아니며, 타원곡선으로 나온 순환군이 가지는 어떤 내부 구조를 활용하기까지 하는 알고리즘이다. (그런 이유로 이 문단에서 소개한 일반화와 아주 부합하지는 않는다.) 그래도 전체적으로는 DSA와 비슷한 모양새이다.