[ElGamal] in Public-key cryptosystem

수식 입력이 번거로워서 수식 표현이 좀 매끄럽지 못합니다.

특히 주의해서 보실 것: 예를 들어 a의 역원인 경우, a역 이라 표현했습니다.

 

키생성

public key: (e1, e2, p)이고, private key: d이다.

 

큰 소수 p 선택
1 ≤ d ≤ (p - 2) 범위에서 임의의 d 선택
(Z_p)*에서 원시근 e1 선택
e2 ≡ e1^a mod p

 

암/복호화

 

암호화

임의의 r 선택
c1 ≡ e1^r mod p 
c2 ≡ (m * e2^r) mod p
최종 암호문은 (c1, c2)이다.

 

복호화

m ≡ c2 * (c1^a) mod p

 

취약점

알려진 평문 공격 

동일한 r을 이용하면 알려진 평문 공격에 위험해진다.

공격자가 m, c1, c2, c1', c2'을 알고 있을 때, (또한, m, m'은 같은 r 사용해 암호화됨)
c1 ≡ e1^r mod p, c2 ≡ m * e2^r mod p,
c1' ≡ e1^r mod p, c2' ≡ m' * e2^r mod p을 계산해낼 수 있다.
그러면 m' ≡ c2' * (e2^r)역 ≡ c2' * m * c2역 (mod p)이다. 즉, m'을 얻어낼 수 있다.

안전성

 

DDH를 통한 안전성 입증

A: ElGamal Oracle, B: DDH attacker

 

1단계) "Elgamal easy -> DDH easy" 가 참임을 증명

여기서 말하는 ElGamal easy란, 다른 말로 하자면 "ElGamal을 무조건 풀어낼 줄 아는 무언가가 있다 (그리고, 이를 ElGamal Oracle이라 하자)"라 할 수 있다.
우리는 "ElGamal easy라는 전제 하에 DDH는 easy인가?"를 판단하려는 것이기에,
ElGamal Oracle을 활용할 것이다.

DDH 문제의 입력은 p, g, g^a, g^b, g^c이다.
DDH 문제 안에서, (p, g, y = g^a)이고 (이산대수 문제), 임의의 m값을 선택한다.
Elgamal 오라클은 g^b, (g^c * m)을 입력으로 받아 결과값을 출력하는데, 이 결과값을 m'이라 하자.
이때, c = ab라면 ElGamal 복호화 과정을 통해 m' = m이며, 역도 성립한다. 즉, m'와 m을 비교함으로써 (이것은 쉽다), c = ab 여부를 확인할 수 있다. 즉, DDH가 풀린다.

따라서, "Elgamal easy -> DDH easy" 가 참임이 증명되었다.

2단계) 위의 대우인 "DDH hard -> Elgamal hard"도 참이다.

3단계) 위에서 전건이 참이므로 후건 또한 참이다.

 

 

 

CDH를 통한 안전성 입증

A: ElGamal Oracle, B: CDH attacker

 

1단계) "Elgamal easy -> CDH easy" 가 참임을 증명

여기서 말하는 ElGamal easy란, 다른 말로 하자면 "ElGamal을 무조건 풀어낼 줄 아는 무언가가 있다 (그리고, 이를 ElGamal Oracle이라 하자)"라 할 수 있다.
우리는 "ElGamal easy라는 전제 하에 CDH는 easy인가?"를 판단하려는 것이기에,
ElGamal Oracle을 활용할 것이다.

CDH 문제는 p, g, g^a, g^b를 입력으로 받는다.
CDH 문제 안에서는 (p, g, y = g^a) (이산대수 문제)이다.
Elgamal Oracle은 g^b와 R을 입력으로 받아 결과값을 출력하는데, 이를 m이라 하자.
그러면 R = m * (g^b)^a 일 것이다. (g^b를 c1, R을 c2으로 취급하여 ElGamal 복호화 과정을 거치면 그렇게 된다.)

이것에 의해, g^(ab)는 R * m역 으로 구할 수 있으며, 즉 CDH가 풀린 것이다.

따라서, "Elgamal easy -> CDH easy" 가 참임이 증명되었다.

2단계) 위의 대우인 "CDH hard -> Elgamal hard"도 참이다.

3단계) 위에서 전건이 참이므로 후건 또한 참이다.