공개키 - Elgamal 암호

1. Elgamal 암호

- 같은 평문이라도 암호화가 이루어질 때마다 암호문이 달라짐

- 다른 공개키 암호 알고리즘에 비해 길이가 2배로 늘어남

- 이산대수(로그) 문제에 바탕을 둔 공개키 알고리즘

- RSA 암호에 비해 안전하지만 속도가 느림

 

y = g의 x승 mod p --> g는 원시원소, p는 소수

g와 x를 아는 사람이 y를 계산하는 것은 간단하나, g와 y를 아는 사람이 x를 계산하는 것은 어렵다.

Bob은

1) 큰 소수 p, 원시원소 g -->공개

2) x 선정, y = g의 x승 mod p [ x는 비밀, y는 공개]

 

Alice는

3) 난수 r을 선정 -> K = y의 r승 mod p

4) C1 = g의 r승 mod p, C2는 KM mod p

 

Bob은

5) C = ( C1, C2 )

6) K = C1의 x 승 mod p

7) M = C2 x K(-1승) mod p