엘가말

엘가말(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) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반