[정보보안] ElGamal 공개키 암호

ElGamal이라는 사람이 만든 엘가말 암호 역시 RSA, Rabin암호처럼 공개키(비대칭키) 암호이다. 

ElGamal암호의 핵심은 Discrete Logarithm Problem(이산 대수 문제) 이다. 

 

p가 소수이면, 

<Zp*, X> 은 abelian group이다. (곱셈역이 항상 존재하니까...)

Zp* = { 1, 2, ..., p-1 }

아벨군에 대한 설명은 https://sweetdev.tistory.com/749 를 참고하자.

Zp*에 대한 설명은 https://sweetdev.tistory.com/758 를 참고하자. 

 

아벨군이란?

이 다섯가지 규칙을 만족하는 군(Group)이다. 

 

Zp* = {1, 2, ..., p-1 }에 속한 임의의 g에 대해서, g^x mod p를 계산해보자.  (1 <= x <= p-1)

 

예를 들어, p가 7이면 Z7*는 {1, 2, 3, 4, 5, 6} 이다. 

g=2로 잡으면 2^1 ~ 2^6 mod 7은 2, 4, 1, 2, 4, 1이므로 {1,2,4}의 집합을 형성한다. 

g=3으로 잡으면 3^1~3^6 mod 7은 {1,2,3,4,5,6}으로 이를 <Zp*, X>의 primitive root라고 부른다!!

 

모든 <Zp*, X>는 primitive root를 갖긴 하는데( 값이 있다는건 수학적으로 증명 되어있다)

이를 찾는 좋은 방법은 없다. random으로 찾아야 함...

이를 discrete logarithm problem(이산 대수 문제)라고 부른다. 

 

y = g^x mod p에서, p, g, y가 주어졌을때 x를 구하는것이 어렵다는것이 discrete logarithm problem(이산 대수 문제) 이다. 왜냐면 y = g^x mod p가 일방향 함수이기 때문이다. 반대 방향으로 구하는건 되게 어렵다는 뜻이다. 

ElGamal 공개키 암호는 e2 = e1^d mod p 에서, e1, e2, p를 알아도 d를 계산하는것이 어렵다는 점을 이용한 암호화이다. 

 

Factorization(소인수분해)가 어렵다는것에 기반을 둔 암호화는 RSA암호화였다. 

 

키 생성하기

공개키: e1, e2, p

개인키: d

 

(1) p : 임의의 소수 선택

(2) e1: <Zp*, X>의 primitive root 선택

(3) d: 1<=d<=p-2 선택

(4) e2 = e1^d mod p 계산 ( y = g^x mod p )

암호( Encrpytion )

M이 평문이다. 평문은 p보다 작아야 한다!! (p가 엄청 커야한다는 뜻이기도 하다)

r은 1 <= r <= p-1에서 선택하고, 비밀로 한다. 

 

C1 = e1^r mod p

C2 = M*e2^r mod p

 

(C1, C2)가 M의 암호문. 이 점은 좀 특이하다! 하나의 평문에서 두개의 암호문이 생긴다. 

이를 message expansion이라고 부르는데 ElGamal 암호의 단점이다. 

복호

M = C2 / C1 ^d mod p 를 계산한다. 

 

 

 

예제