본문 바로가기

엘가말

ElGamal Signature ElGamal Encryption 또한 디지털 서명에 응용될 수 있다. 예를 들어, Alice가 어떤 메세지에 서명을 하려고 한다. 먼저, Alice는 큰 Prime Number p와 Primitive Root α를 선택한다. 그리고, 1 ≤ a ≤ p - 2인 a를 선택하고, β ≡ α^a (mod p)를 계산한다. a는 비밀로 유지해야 한다. 공개키는 (p, α, β)가 된다. Alice가 메세지 m에 서명하기 위해서, 다음의 과정을 따른다. 1. 공개되지 않은 임의의, gcd(k, p - 1) = 1을 만족하는 k를 선택한다. 2. r ≡ α^k (mod p) (0 < r < p)를 계산한다. 3. s ≡ k^(-1) * (m - ar) (mod p - 1)을 계산한다. 서명된 메세지는 (m, r,.. 더보기
ElGamal Public Key Cryptosystem 일반적인 공개키 암호화의 안전성은 그것의 소인수분해가 얼마나 어려운가에 달려있다. 하지만, 그것 외에도 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... 더보기