엘가말

엘가말(El Gamal)

엘가말(El Gamal)은 1984년 미국 스탠퍼드 대학교의 타헤르 엘가말(Taher ElGamal)이 제안한 암호 알고리즘으로, 이산대수 문제의 어려움에 기반한 최초의 공개키 암호이다. 엘가말은 디피-헬만 키 교환 알고리즘을 참고하여 만들었다.

개요

엘가말은 1984년에 미국 스탠퍼드 대학교의 타헤르 엘가말(Taher ElGamal)이 제안한 공용 키 암호 방식의 하나이다. 소수 p와 원시근 g를 공통의 공용키로 한다. 이용자는 자신의 비밀키 X를 정하고 g를 X 승해서 p로 나눈 나머지 Y(Y=gX mod p)를 자신의 공용키로 한다. 평문과 난수의 공용 키로부터 암호문을 생성, 비밀키로 복호화(decoding)한다. 암호문의 길이가 평문 길이의 2배로 되는 결점이 있으나 이산대수 문제의 어려움에 안전성의 근거를 두고 있다. 엘가말은 공용 키 암호 방식의 하나로 이산대수(離散對數) 문제에 대한 최초의 공용 키 암호이며 DH 공용 키 분배법의 확장형이고, 소수(素數) p와 원시근(原始根) g를 공통의 공용키로 한다.

엘가말 암호는 이산대수(離散對數) 문제에 대한 최초의 공용 키 암호이며 DH 공용 키 분배법의 확정형이다. 이산대수 문제의 어려움이란, 주어진 g, x, p를 이용하여 y = g^x mod p를 구하긴 쉽지만, g, y, p 값을 이용하여 원래의 x는 찾기 어렵다는 것이다. 엘가말 암호의 장점은 난수 k를 이용하기 때문에, 매 암호화 시 다른 암호문을 얻어 RSA에 비해 더 안전하다. 그 이유는 RSA는 같은 메시지, 같은 킷값을 이용할 경우 그 암호문이 항상 일정한 데 반해, 엘가말 암호는 같은 메시지, 같은 킷값을 사용해도 암호화를 할 때마다 그 암호문의 값이 변하기 때문이다. 다만 메시지 M을 암호화하면 그 길이가 두 배가 되며 속도가 느리다는 단점이 있다.

특징

• 엘가말 암호 알고리즘은 메시지의 길이가 두 배로 늘어나는 특징이 있다.
• 같은 평문이라도 암호화가 이루어질 때마다 암호문이 달라진다.
• RSA 암호보다 안전하지만, 속도가 느리다.
• 이산대수 문제를 기반으로 하였다.
• 난수 K를 이용하므로 매 암호화 시 다른 암호문을 얻어 RSA에 비해 안전하다.
• 암호문의 길이가 평문 길이의 2배가 되는 단점이 있다.

• 엘가말 암호의 취약점

1. 작은 모듈러스 공격(Low-Modulus Attack) : p의 값이 충분히 크지 않을 경우 전수 조사나 이산대수의 성질을 이용한 효율적인 알고리즘을 통하여 개인 키 d나 임의의 값 r을 찾아낼 수 있다. p는 적어도 2048비트
2. 알려진 평문 공격(Known-Plain text Attack) : 평문 m에 대응하는 암호문

• 엘가말 암호의 안정성

컴퓨터 디피-헬만(The Computational Diffie-Hellman; CDH) 문제 : 계산 문제

순환군 : G of order q, 생성원 g∈G에 대하여, a,b∈{0,1,...q - 1}, ($g,g^{a},g^{b},q$), 가 주어졌을때, $g^{ab}$ mod q ≡?

The Decisional Diffie-Hellman(DDH) 문제 : 결정 문제 (Yes or No)

순환군 : G of order q, 생성원 g∈G에 대하여, a,b,c∈{0,1,...q - 1}, ($g,g^{a},g^{b},g^{c},q$), 가 주어졌을때, ab ≡?c(mod q)

엘가말을 사용한 암호 설명

대칭 키를 사용하지 않고도 EC Elgamal 방식으로 암복호화를 할 수 있다.

• Plain Text는 35이다. 밑은 5, 모듈로는 89이다.
• 앨리스의 개인 키는 13이다.
• 밥의 개인 키는 8이다.
• $X^{a,b}$ 의 89 모듈로는 다음과 같다. 밑에 계산된 두 숫자 40과 4를 교환한다. 이때 공격자 Eve는 40 혹은 4로부터 개인 키 13 혹은 8을 추출할 수 없다.

$Alice:5^{13}mod89=>40$
$Bob:5^{8}mod89=>4$

• 앨리스와 밥은 상대편의 지수 부분(비밀키)을 몰라도 전송된 각각의 40, 4를 가지고 암호 키를 계산할 수 있다. 즉 암호 키값은 16이다.

$Alice:4^{13}mod89=16$
$Bob:40^{8}mod89=16$

• 평문(Plain Text) 35를 암호화 해서 보내고자 한다.

$CT(CipherText):$
$CT<=16*35mod89=>26:X^{ab}*PmodN$
$35*16mod89=>26$

• 형성된 암호 키값 16의 모듈로 역수는 39이다. [G,C,~]=gcd(16,89); % C => 39 matlab 에서 위 함수를 사용하면 모듈로 인버스를 구할 수 있다. 모듈로의 역수를 구하는 방법은 0부터 계속 한 개씩 증가시켜서 모듈로 결과가 1이 나올 때 증가시켜서 대입한 그 값이 역수이다. 여기서는 대입해본 결과 39를 얻었다. 39번의 모듈로 계산했다는 이야기다.

• 복호(암호의 반대)를 하려면 암호된 값 26에 16의 모듈로 역수 39를 곱하면 나온다.

$CT=X^{ab}*PmodN=>26$
$PT=CT*X^{ab}-1modN$
$26*39mod89=35$

복호된 값이 암호된 값 35 와 동일하다.

matlab 확인 결과

$mod(5^{13},89)\%ans=40,PrvK:13N=89$
$mod(5^{8},89)\%ans=4,PrvK:8$

$mod(4^{13},89)\%ans=16EncryptinKey$ 
$mod(40^{8},89)\%ans=16EncryptinKey$ 

$mod(16*35,89)\%ans=26CT:CipherText$
$[G,C,~]=gcd(16,89);\%C=>39$

$mod(16*39,89)\%ans=1Inverse16$
$mod(26*39,89)\%ans=35:DecryptedV=PlainText$

• 엘가말 공개키 암호 시스템

일반 공개키 암호화의 안전성은 소인수 분해가 이루어져야 한다. 그 외의 다른 이산 로그는 문제를 공개키로 잡을 수 없고, 엘가 말은 공개 키핑이 대표적인 방법이다. 밥은 Prime Number p를 선택하고 Primitive Root을 선택한다. 여기서, m은 0 ≤ m <p 인 정수이다. 문제가되는 것은 밥은 비밀 키를 선택하고 β ≡ α ^ a (mod p)를 계산 한다. 여기서 (p, α, β)를 공개하고, 밥의 공개 키. 앨리스는 다음 과정을 거친 것이다.

1. 밥에게 메시지를 보내고, 밥의 공개 키 (p, α, β)를 가져 온다.
2. 임의의, 공시적 으로 선택을하고, r ≡ $a^{k}$ (mod p)를 계산 한다.
3. t ≡ $b^{k}$ * m (mod p)를 계산한다.
4. 앨리스는 밥에게 (r, t)를 보낸다.

밥은 해독 할 수 있다.

$TR^{-a}$ ≡ m (MOD P)

∵ $TR^{-a}$ ≡ $b^{k}$개의 * m 개의 * $(a^{K})^{-a}$ ≡ $(a^{a})^{k}$ 개의 * m의 *의 $a^{ak}$ ≡ m (mod p)

여기서, k는 임의의 선택 정수이고, β k (mod p)는 임의의 정수이다. 즉, $t=b^{k}*m(modp)$는 무작위 적이다. 결국, Eve는 대구 정보에 대해서도 마찬가지 이다. 이브는 추가 정보를 요구한다. 이브는 다음과 같이 나타낼 수있고, (- k)를 알아낼 수있다. 또한, 아무것도하지 않을 수도 있다. (r, t1)은 다른 사람들에게 (r, t2)가 거스름돈을 전달한다. 이브는 t1과 t2를 ≡ t2 / m1 / t1 (mod p)로 설정한다.

절차

키 생성

• 큰 소수 p를 선택하고 생성자 g를 선택한다.
• 비밀키인 x를 선택하고 공개키 y = g^e mod p 를 계산한다.
• (y, g, p)를 공개키로 공개하고 x는 비밀키로 안전하게 보관한다.

암호화

• 메시지 m을 암호화하기 위해 난수 k를 선택한다.
• 암호문인 $r=g^{k}modp$ 와 $s=my^{k}modp$를 계산한다.
• 암호문 (r, s)를 수신자에게 전송한다.

복호화

• 수신자는 자신의 비밀키 x를 이용하여 복호화한다.
• $m=({\frac {s}{r}})^{x}modp$ 계산한다.

예시

• 엘가말 서명

ElGamal Encryption 또한 디지털 서명 할 수 있는데, 예를 들어, 앨리스는 서명한다고 하면 앨리스는 큰 소수 p와 원시적인 루트를 선택한다. 1 ≤ a ≤ p - 2 인 선택을하고 β ≡ $a^{a}(modp)$를 계산한다. a 비밀 유지가되어야한다. 공개 키는 (p, α, β)가 있으면 앨리스는 이렇게 하면 된다.

공개되지 않은 임의의, gcd (k, p - 1) = 1을 만족하는 것을 선택 한다. 
r ≡ $a^{k}$ (mod p) (0 <r <p)를 계산한다.
s ≡ $k^{-1}$ * (m - ar) (mod p - 1)을 계산한다.

서명을 확인하십시오. Bob은 다음 과정을 진행한다. 이때 서명된 의사는 (m, r, s)가 된다.

앨리스의 공개키 (p, α, β)를 가져온다.
v1 ≡ $b^{r}*r^{s}$ (mod p)와 v2 ≡ $a^{m}$ (mod p)를 계산한다.
v1 ≡ v2라면,이 서명은 비싸지 않다.

(m - ar) (mod p - 1)는 sk ≡ (m - ar) (mod p - 1)이고, (sk + ar) ≡ $(a^{a})^{r}*(a^{k})^{s}$ ≡ $b^{r}*r^{s}$ ≡ v1 (mod p)이다. 이브는 알지도 못하는 기사를 남겨두고, 비밀을 유지하라. 즉, 결과적으로 다음과 같은 문제가 되는데, 다시 정리해 보면 $(R^{S}$ ≡ $b^{-R})*a^{m}MOD(P)$, 즉 이산 대수 (discrete logarithm) 이다.

참고자료

• 한국전국통신기술협회 공식 홈페이지 - 〈http://a.to/198yOi1〉
• 〈암호 쉽게 이해하기〉
• 〈암호학 - Public Key Cipher :: ElGamal〉, 《개인 블로그》, 2010-05-21
• Celdee, 〈엘가말 서명〉,《티스토리》, 2008-12-09
• 아랑이의 IT 탐험기, 〈공개키 암호화〉,《개인 블로그》, 2016-08-17
• 사랑과 생각, 〈EC Elgamal Encryption 설명〉,《네이버》, 2018-11-26
• JayTech, 〈EI Gamal(엘가말)과 Diffle-Hellman(디피헬만)프로토콜〉,《티스토리》, 2018-12-08

같이 보기

• 암호 알고리즘
• 공개키
• 타헤르 엘가말
• 디피-헬만
• RSA

이 엘가말 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반