암호학 - Public Key Cipher :: ElGamal

RSA 암호 알고리즘이 소인수분해 문제의 어려움에 기반한다면,

 

엘가말 암호는 이산대수 문제의 어려움에 기반한 암호 알고리즘입니다.

 

이산대수 문제의 어려움이란,

 

주어진 g, x, p 를 이용하여 y = g^x mod p 를 구하긴 쉽지만

 

g, y , p 값을 이용하여 원래의 x를 찾기 어렵다는 것이지요.

 

엘가말 암호는 1984년 스탠퍼드 대학의 테하르 엘가말(Tehar ElGamal)이 제안한 암호로,

 

키 생성, 암호화, 복호화 과정은 아래와 같습니다.

 

▷ 키 생성

  - 큰 소수 p를 선택하고 생성자 g를 선택.

  - 비밀키 x를 선택하고 공개키 y = g^e mod p를 계산.

  - [y, g, p]를 공개키로 공개하고, 비밀키 x는 보관.

 

▷ 암호화

  - 메시지 m을 암호화하기 위해 난수 k 선택.

  - 암호문 r = g^k mod p

  - 암호문 s = my^k mod p

  - 암호문 [r, s]를 수신자에게 전달

 

▷ 복호화

  - 메시지 m = s/r^x mod p 로 계산

 

엘가말 암호의 장점이라면

 

난수 k를 이용하기 때문에, 매 암호화 시 다른 암호문을 얻어 RSA에 비해 더 안전하다고 볼 수 있습니다

왜냐하면 RSA는 같은 메시지, 같은 키 값을 이용할 경우 그 암호문이 항상 일정한 데 반해

엘가말 암호는 같은 메시지, 같은 키 값을 사용해도 암호화시 마다 그 암호문의 값이 변하기 때문이지요

 

다만 메시지 m을 암호화 하면 그 길이가 두 배가 되는 단점이 있습니다.

출처 - http://reinliebe.tistory.com/