[비대칭키 암호 시스템] Elgamal Encryption

대칭키 암호 시스템과 어떤 차이가 있는가?

각 사용자는 2개의 키를 가지고 있다. 

공개키는 모두가 알 수 있는 키이며, 개인키는 사용자만 알고 있다. 

 

A -> B에게 암호화하여 보낼 것이다.

암호화는 B의 공개키를 활용하여 암호화하여 보낼 것이다.

이를 복호화할 때는 B의 개인키를 사용할 것이다. 

 

따라서 이를 복호화하는 것은 B만 가능하다

 

비대칭키 암호화 방식

• 수학적 난제를 이용
• Elgamal -> Discrete Logarithm 문제의 어려움
• RSA -> Factorizing (소인수분해) 문제의 어려움

 

Elgamal Encryption

Public key

B의 공개키

• p : prime 엄청나게 큰 소수 선택
• g : generator g < p, \(g \in Z^*_p\)
• Y : \(Y \equiv g^x mod\ p\) -> x를 알아내기 어렵다

Private Key

B의 개인키

• x : choose at random, x < p

Encryption : Ciphertext <a,b> 

A가 M에 대해서 B의 공개키로 암호화 하는 과정

같은 메세지에 대해서도 서로 다른 암호문을 생성해야한다. -> 랜덤 k

• k : choose at random, relatively prime to p-1(secret) 
• a \(\equiv g^k mod\ p\) -> 중간에 공격자가 가로채도 k를 알 수 없다
• b \(\equiv Y^k M\ mod\ p\) -> 즉, 평문을 bob의 공개키에 앨리스가 선택한 k승 하여 공개키 p로 mod한 값이다.
• b가 암호문

Decryption 

bob도 k를 알지 못한다. 

하지만 bob은 y를 만드는 x가 무엇인지 알고 있다.

• a = \(g^k\)이므로 \(a^x\) = \(g^{xk}\)
• M = \(b/(a^x)\)(mod p)
• = \(Y^k M / g^{xk}\) 
• = \(g^{xk} M / g^{xk}\) = M