[암호학] ElGamal

Elgamal은 RSA와 같이 Mathmetical difficult를 이용한 알고리즘입니다

DLP(Discrete Logarithm Problem)

큰 수 n을 법으로 하는 지수승 $y≡10^𝑥 𝑚𝑜𝑑19$은 계산 하기 쉽지만, 주어진 y와 k에 대하여 식 $y≡10^𝑥 𝑚𝑜𝑑19$을 만족하는 x를 구하기 어려운 점을 이용하는 이론이빈다.

system parameter로는 g와 p가 있으며
$y=g^xmodp$ 에서 y가 주어졌을 때 x를 구하는 문제입니다

다음과 같이 Alice와 Bob이 있을 때 각자의 비밀키인 $x_A$와$x_B$를 선택하고 공개되어 있는 g,p를 이용하여 공개키를 계산합니다

A가 메시지를 암호화 하고 B가 복호화를 하는 과정입니다
먼저 A에서 개인키를 정하고 B의 공개키를 사용하여 K를 생성합니다. 이후 자신의 개인키와 K와 메시지를 곱한값을 같이 Ciphertext로 전송합니다
B는 C1을 자신의 개인키로 복호화를 진행하는데 위의 수식으로 K값을 알아낼 수 있습니다. 그리고 C2를 K로 나눈값이 메시지 원본 값이라는 것을 알 수 있습니다

이는 위 수식의 예시입니다

Icon made by Freepik from www.flaticon.com