엘가말 암호

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

엘가말 암호는 디피-헬만 키 교환을 사용하여 공유 비밀을 설정하고, 이를 일회용 패드로 메시지를 암호화하는 비대칭 암호 시스템이다. 이 시스템은 키 생성, 암호화, 복호화의 세 단계로 이루어지며, 안전성은 이산 로그 문제의 어려움에 기반한다. 엘가말 암호는 가소성으로 인해 선택 암호문 공격에 취약하며, 이를 보완하기 위해 추가적인 수정이나 패딩 방식이 사용된다. 효율성을 위해 확률적 암호화 방식을 사용하며, 순환군 G의 선택에 따라 안전성이 달라진다. 하이브리드 암호 시스템에서 대칭 키 암호화를 위해 사용되기도 한다.

엘가말 암호

개요

이미지 준비중입니다.

엘가말 암호화 작동 방식

유형	공개 키 암호 방식
고안자	타히르 엘가말
발표	1985년

보안

보안 기반	이산 로그 문제

상세 정보

키 교환	디피-헬만 키 교환과 유사
변형	통합 암호화 방식 전자 서명 (엘가말 서명)

📚 더 읽어볼만한 페이지

암호 알고리즘 - 이진 코드
암호 알고리즘 - 메시지 인증 코드
메시지 인증 코드(MAC)는 메시지 무결성을 보장하기 위해 사용되는 암호화 기법으로, 송신자와 수신자가 동일한 키를 공유하여 MAC 생성, 확인 과정을 거친다.

1. 개요
2. 역사
3. 알고리즘
4. 안전성
5. 효율성
6. 순환군 G의 선택
7. 응용

2. 역사

엘가말 암호는 디피-헬만 키 교환 방식을 암호 방식으로 활용할 수 있도록 변형한 것이다. 공유된 난수를 사용하여 일회용 패드(OTP)를 수행하면 암호 통신이 가능하다는 점을 이용했다. 엘가말 암호는 암호이지만, 이와는 별도로 디지털 서명에 응용할 수 있는 엘가말 서명도 발표되었다.

3. 알고리즘

엘가말 암호 알고리즘은 디피-헬만 키 교환을 수행하여 공유 비밀 $s$ 를 설정하고, 이를 메시지 암호화를 위한 일회용 패드로 사용하는 방식이다. 엘가말 암호화는 키 생성, 암호화, 복호화의 세 단계로 수행된다.

* 키 생성: 앨리스는 순환군 $G$ 와 그 생성원 $g$ , 그리고 무작위로 선택한 정수 $x$ 를 이용하여 공개 키 $(G, q, g, h)$ 를 생성하고, $x$ 를 비밀 키로 유지한다.
* 암호화: 밥은 앨리스의 공개 키를 사용하여 메시지 $M$ 을 암호화한다. 밥은 무작위로 선택한 정수 $y$ 와 공유 비밀 $s$ 를 계산하고, 이를 통해 암호문 $(c_1, c_2)$ 를 생성하여 앨리스에게 전송한다.
* 복호화: 앨리스는 자신의 비밀 키 $x$ 와 암호문 $(c_1, c_2)$ 를 이용하여 공유 비밀 $s$ 를 계산하고, $s$ 의 역원 $s^{-1}$ 을 구한다. 그 후, $m := c_2 \cdot s^{-1}$ 계산을 통해 원래 메시지 $m$ 을 복구하고, 이를 다시 평문 메시지 $M$ 으로 변환한다.

디피-헬만 키 공유 방식으로 공유된 난수를 이용해 일회용 패드를 수행하면 암호 통신이 가능하다. 엘가말 암호는 디피-헬만 키 교환 방식을 암호 방식으로 활용할 수 있도록 변형한 것이다.

3.1. 키 생성

엘가말 암호에서 키 생성은 다음과 같은 단계로 이루어진다.

1. 차수가 소수 $p$ 인 순환군 $G$ 와 이의 한 생성원 $\alpha$ 를 정한다.
2. 밥은 정수 $y$ 를 선택한다. ( $0 \leq y \leq p-1$ )
3. $\beta := \alpha ^{y}$ 을 계산한다.
4. $(p, \alpha, \beta)$ 가 공개 키가 된다. 앨리스는 다음 단계를 따른다.
* 순환군 $G\,$ 를 생성한다. $G\,$ 는 차수가 $q\,$ 이고, 생성원 $g$ 를 갖는다.
* $\{1, \ldots, q-1\}$ 에서 정수 $x$ 를 무작위로 선택한다.
* $h := g^x$ 를 계산한다.
* $(G, q, g, h)$ 를 공개 키로 하고, $x$ 를 비밀 키로 한다. 비밀키는 비밀로 유지해야 한다.

엘가말 암호는 디피-헬만 키 교환 방식을 암호 방식으로 활용할 수 있도록 변형한 것이다. 평문 공간은 G이고, 암호문 공간은 G²이다.

3.2. 암호화

앨리스가 밥에게 메시지를 전달하는 절차는 다음과 같다.

* 앨리스는 밥의 공개 키를 전달받는다.
* 앨리스는 밥에게 전달할 메시지 m을 선택한다.
* 앨리스는 무작위로 정수 k를 선택한다. (0 ≤ k ≤ p-1)
* c₁ := α^k과 c₂ := β^km을 계산한다.
* 앨리스가 밥에게 암호문(c₁, c₂)를 전달한다.

밥은 앨리스의 공개 키 (G, q, g, h) 하에서 메시지 M을 다음과 같이 암호화한다.

* 메시지 M을 가역 매핑 함수를 사용하여 G의 요소 m으로 매핑한다.
* {1, ..., q-1}에서 정수 y를 무작위로 선택한다.
* s := h^y를 계산한다. 이것을 공유 비밀이라고 한다.
* c₁ := g^y를 계산한다.
* c₂ := m · s를 계산한다.
* 밥은 암호문 (c₁,c₂)를 앨리스에게 보낸다.

암호문 (c₁,c₂)와 평문 m을 모두 알고 있다면 c₂ · m^-1 = s이므로 공유 비밀 s를 쉽게 찾을 수 있다. 따라서 보안을 향상시키기 위해 모든 메시지에 대해 새로운 y와 새로운 s가 생성된다. 이러한 이유로 y는 임시 키라고도 한다.

디피-헬만 키 교환 방식을 통해 공유된 난수를 사용하여 일회용 패드(OTP)를 수행하면 암호 통신이 가능하다. 엘가말 암호는 이를 이용하여 디피-헬만 키 교환 방식을 암호 방식으로 활용할 수 있도록 변형한 것이다.

엘가말 암호를 정리하면 다음과 같다.
* 평문으로 G의 원소 m을 받는다.
* r을 {0,...,q-1}에서 무작위로 선택한다.
* c₁ = g^r, c₂ = m · h^r을 계산한다.
* (c₁, c₂)를 암호문으로 한다.

3.3. 복호화

앨리스가 생성한 암호문 $(c_1, c_2)$ 가 밥에게 주어졌을 때, 밥은 다음 과정을 통해 복호화를 진행한다.

* $s := c_1^x$ 를 계산한다. $c_1 = g^y$ 이므로, $c_1^x = g^{xy} = h^y$ 이며, 이는 밥이 암호화에 사용한 값과 동일하다.
* $s$ 의 역원인 $s^{-1}$ 을 계산한다. 이는 여러 방법으로 계산할 수 있다.
* $G$ 가 소수 $n$ 을 법으로 하는 정수의 곱셈 그룹의 부분군인 경우, 확장 유클리드 알고리즘을 사용하여 모듈러 곱셈 역원을 계산할 수 있다.
* $s^{-1}$ 을 $c_1^{q-x}$ 로 계산할 수 있다. 이는 라그랑주 정리에 의해 $s$ 의 역원인데, $s \cdot c_1^{q-x} = g^{xy} \cdot g^{(q-x)y} = (g^{q})^y = e^y = e$ 이기 때문이다.
* $m := c_2 \cdot s^{-1}$ 를 계산한다. 이 계산은 원래 메시지 $m$ 을 생성하는데, $c_2 = m \cdot s$ 이므로 $c_2 \cdot s^{-1} = (m \cdot s) \cdot s^{-1} = m \cdot e = m$ 이다.
* $m$ 을 평문 메시지 $M$ 으로 다시 변환한다.

$(c_1, c_2)$ 가 올바른 방법으로 생성된 암호문이라면, $m' = c_2 \cdot ({c_1}^x)^{-1} = m \cdot (g^x)^r \cdot ((g^r)^x)^{-1} = m$ 을 만족한다.

4. 안전성

제3자가 공개 키 $(p, \alpha, \beta)$ 와 암호문 $(c_{1}, c_{2})$ 를 모두 안다고 해도, 여기서 메시지 $m$ 을 찾으려면 밥만이 아는 비밀 정보인 $y$ 나 앨리스가 일회용으로 정한 수 $k$ 를 알아야 한다. 이는 이산 로그 방정식 $\beta = \alpha ^{x}$ 의 해 $x$ 를 구하는 것과 같으며, $p$ 가 클수록 해를 구하기 어렵다.

엘가말 암호의 안전성은 기저 그룹 $G$ 의 속성과 메시지에 사용된 패딩 방식에 따라 달라진다. 기저 순환 그룹 $G$ 에서 계산적 디피-헬만 가정(CDH)이 성립하면 암호화 함수는 일방향 함수가 된다.

만약 $G$ 에서 결정적 디피-헬만 가정(DDH)이 성립하면 엘가말 암호는 의미적 안전성을 달성한다. 의미적 안전성은 계산적 디피-헬만 가정만으로는 보장되지 않는다. 이 가정이 성립한다고 여겨지는 그룹은 결정적 디피-헬만 가정 문서를 참고할 수 있다.

엘가말 암호는 가소성 (암호학)을 가지므로 선택 암호문 공격에 안전하지 않다. 예를 들어 메시지 $m$ 의 암호문 $(c_1, c_2)$ 가 주어졌을 때, 메시지 $2m$ 의 유효한 암호문 $(c_1, 2 c_2)$ 를 쉽게 구성할 수 있다.

선택 암호문 안전성을 달성하기 위해서는 추가적인 수정이나 적절한 패딩 방식이 사용되어야 한다. 수정 사항에 따라 DDH 가정이 필요할 수도 있고 그렇지 않을 수도 있다.

엘가말 암호와 관련된 다른 방식들도 제안되었다. 크래머-슈프 암호 시스템은 $G$ 에 대해 DDH가 성립한다고 가정하면 선택 암호문 공격에 안전하다. 이 증명은 랜덤 오라클 모델을 사용하지 않는다. 또 다른 제안된 방식은 통합 암호화 방식인 DHIES인데, 이 증명에는 DDH 가정보다 더 강력한 가정이 필요하다.

엘가말 암호는 선택 평문 공격에 대해 완전 해독할 수 없다는 것(OW-CPA)과 CDH 가정이 동치이다. 또한, 엘가말 암호가 선택 평문 공격 하에서 Indistinguishability를 갖는다는 것(IND-CPA)과 DDH 가정은 동치이다.

5. 효율성

엘가말 암호는 확률적 암호화 방식이다. 이는 하나의 평문을 여러 개의 가능한 암호문으로 암호화할 수 있음을 의미하며, 일반적으로 엘가말 암호화는 평문에서 암호문으로 크기가 1:2로 확장되는 결과를 낳는다.

엘가말 암호화는 두 번의 지수 연산을 필요로 한다. 그러나 이러한 지수 연산은 메시지와 독립적이므로, 필요하다면 미리 계산해 놓을 수 있다. 복호화는 한 번의 지수 연산과 한 번의 그룹 역원 계산을 필요로 하지만, 이를 한 번의 지수 연산으로 쉽게 결합할 수 있다.

6. 순환군 G의 선택

* 순환군 G에서 위수가 소수인 q를 선택하고, q의 비트수는 k로 한다.
* G의 생성원 g를 선택한다.
* x를 {0,...,q-1}에서 무작위로 선택한다.
* $h = g^x$ 로 계산한다.
* $(G, q, g, h)$ 를 공개키로 하고, x를 비밀키로 한다.

평문 공간은 G이고, 암호문 공간은 G²이다. p를 소수라고 할 때, G = ${\mathbb Z}_p^{*}$ 로 설정하면 DDH 가정이 깨지므로 이 방법은 사용하지 않는다.

이 문제를 피하면서 순환군 G를 선택하는 주요 방법은 두 가지가 있다.

* 순환군 G를 ${\mathbb Z}_p^{*}$ 의 부분군으로 한다.
* 순환군 G를 타원 곡선 암호에서처럼 타원 곡선 위에서 정의한다.

여기서는 첫 번째 방법을 설명한다.

* 작은 자연수 k와 큰 소수 q에 대해 p = kq+1이 성립하는 소수 p를 찾는다.
* 먼저 소수 q를 선택한 후, p = kq + 1이 소수인지 확인하는 방식으로 진행할 수 있다.
* $g \in {\mathbb Z}_p^{*}$ 를 g의 위수가 q가 되도록 무작위로 선택한다.
* $G =$ 는 ${\mathbb Z}_p^{*}$ 의 부분군이 된다.

k=2일 때, p = 2q + 1이 성립하는 소수의 쌍(p,q)이 무한히 존재하는지는 소수#미해결 문제에서 언급된 소피 제르맹 문제와 관련하여 아직 풀리지 않은 문제이다.

7. 응용

대부분의 공개 키 시스템과 마찬가지로, 엘가말 암호 시스템은 일반적으로 하이브리드 암호 시스템의 일부로 사용된다. 여기서 메시지 자체는 대칭 암호 시스템을 사용하여 암호화되고, 엘가말은 대칭 키만 암호화하는 데 사용된다. 이는 엘가말과 같은 비대칭 암호 시스템이 동일한 보안 수준에서 대칭 암호 시스템보다 일반적으로 느리기 때문이다. 따라서 임의로 큰 메시지를 대칭 암호로 암호화한 다음, 메시지 크기에 비해 일반적으로 매우 작은 대칭 키만 엘가말로 암호화하는 것이 더 빠르다.

디피-헬만 키 교환 방식을 암호 방식으로 활용할 수 있도록, Diffie-Hellman 키 공유 방식으로 공유된 난수를 사용하여 일회용 패드(OTP)를 수행하는 방식에서 변형되었다.

엘가말 암호는 암호 (cipher)이지만, 이와는 별도로 디지털 서명 (digital signature)에 응용할 수 있는 엘가말 서명도 발표되었다.

용어에 대해서는 암호 용어, 암호 이론 용어를 참조하라.