Secreta

암호학 - Public Key Cipher :: ElGamal 본문

Cryptography

암호학 - Public Key Cipher :: ElGamal

준♡ 2010.05.21 13:21

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을 암호화 하면 그 길이가 두 배가 되는 단점이 있습니다.

(Textcube 서비스 종료 관계로 이전 Textcube 블로그의 내용을 옮겨옵니다)

2 Comments
  • 프로필사진 2012.04.13 01:46 비밀댓글입니다
  • 프로필사진 지나가는이 2013.06.14 04:39 실제로 해보는데 복호화가 잘 계산이 안되네요... 큰소수 p라고 하셨는데, 메세지 M이 p보다 크게 된다면 복호화 식이 가능한건지 알고 싶습니다. 암호문 s는 0~p-1사이의 정수값일 것이고, r^x mod p도 0~p-1사이의 정수값일 것입니다.
    이때, r^x mod p가 p로 나누어 떨어질리는 없으므로 최소 1이 나온다는 얘기인데, 그렇다면 메세지 M의 값은 아무리 커도 p-1밖에 안되네요. 이런경우는 어떻게 해야되는겁니까?
댓글쓰기 폼