ElGamal 암호화

암호학에서, ElGamal 암호화 시스템은 Diffie-를 기반으로 하는 공개키 암호화를 위한 비대칭 키 암호화 알고리즘이다.헬먼 키 교환.1985년 타헤르 엘가말(Taher Elgamal)이 묘사한 것이다.^[1]ElGamal 암호화는 무료 GNU Privacy Guard 소프트웨어, 최신 버전의 PGP 및 기타 암호 시스템에 사용된다.ElGamal 암호화와 혼동해서는안 된다 변형으로서 DSA(디지털 서명 알고리즘)는 ElGamal 서명 방식의.

ElGamal 암호화는 정수 modulo n의 곱셈 그룹과 같은 모든 순환 그룹 $G{\displaystyle }$ ${\displaystyle G}$에 걸쳐 정의될 수 있다$.$보안은 개별 로그 계산과 관련된$$ $G{\displaystyle }$ ${\displaystyle G}$의 특정 문제의 어려움에 따라 결정된다.

알고리즘

ElGamal 암호화는 키 생성기, 암호화 알고리즘, 암호 해독 알고리즘의 세 가지 요소로 구성된다.

키 생성

제1 당사자 앨리스는 다음과 같이 키 쌍을 생성한다.

• 생성자 $g$가 ${\displaystyle g}$인 $q{\displaystyle }$ ${\$q\} 순서$$q의 $순환{\displaystyle }$ 그룹$$G {\$displaystyle$ g$}$에 대한 효율적인 설명을$$생성하십시오.$$e {\$displaystyle$ e$}$이($가$)$$G {\$displaystystyle G}$의 단위 요소를 나타내도록 하십시오$.$
• $정수{\displaystyle }$ x${\displaystyle }$${\displaystyle x}$을$({\displaystyle }$를) {${\displaystyle 1}$, …,${\displaystyle q}$- ${\displaystyle 1\}}$ ${\displaystyle \{1,\ldots,q-1\}$에서 임의로$$ 선택하십시오$.$
• 계산 $h{\displaystyle }$ ${\displaystyle :=}$ ${\displaystyle {}^{}}$ ${\displaystyle x^{}}$ ${\$
• 공개 키는 값$({\displaystyle G,}$ ${\displaystyle q,}$ ${\displaystyle g,}$ ${\displaystyle h}$) ${\displaystyle (G,q,g,h)}$로 구성된다$.$ 앨리스는 이 공개 키를 공개하고 $x{\displaystyle }$ ${\displaystyle$ x$}$을(를) 개인 키로 유지하는데, 비밀로 해야 한다.

암호화

제2자 밥은 $앨리스$의 공개 키$($, ${\displaystyle q}$,$$, h ${\displaystyle )}$로$$메시지 M ${\$$displaystyle$$M}$을(를) 다음과$$ 같이$$ 암호화한다.

• 가역적 매핑 기능을 사용하여$$ 메시지 $M{\displaystyle }$ ${\displaystyle$ M$}$을(를) $G{\displaystyle }$ ${\displaystyle$ G$}$의 $요소$ m ${\displaystyle$ m$}$에 매핑하십시오.
• $\{{\displaystyle 1}$,${\displaystyle }$…,${\displaystyle q}$- ${\displaystyle 1}$} ${\displaystyle \{1,\ldots,q-1\}$에서 정수 $y{\displaystyle }$ ${\displaystyle y}$을(를) 임의로$$ 선택하십시오$.$
• 계산 $s{\displaystyle }$ ${\displaystyle :=}$ ${\displaystyle {}^{}}$ ${\displaystyle y^{}}$ ${\$ s$:=h^{y$이것을 공유 비밀이라고 한다.
• 계산 $c{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle :=}$ ${\displaystyle {}^{}}$ ${\displaystyle y^{}}$ ${\$
• 계산 $c{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle :=}$ ${\displaystyle m}$ ${\displaystyle \cdot }$ ${\displaystyle s}$ ${\displaystyle c_{2}:==m\cdot s}$.
• 밥은 암호문$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{c\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle(c_{1},c_{2})$을 앨리스에게 보낸다$$.

암호문$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle(c_{1},c_{2})$과 일반 텍스트 $m{\displaystyle }$ ${\displaystyle$ $m$$}$을$($를) 모두 알고 있으면 $c{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$⋅${\displaystyle {\mathrm{m}}^{}}$- ${\displaystyle 1{}^{}}$= ${\displaystyle c_{2}\cdot$ m$^{-1}s$이(가)이므로 공유 비밀 $s{\displaystyle }$ ${\daysty$ s {\daystytype s$}$을 쉽게 찾을 수 있다$.$따라서 보안 향상을 위해 모든 메시지에 대해 새로운 $y{\displaystyle }$ ${\displaystyle$ y$}$이(가) 생성되며$$, 따라서 새로운$$ $s{\displaystyle }$ ${\displaystyle s}$이(가) 생성된다.이러한 이유로 $y{\displaystyle }$ ${\displaystyle y}$을(를) 사용 후 삭제 키라고도 한다$$.

암호 해독

앨리스는 암호문$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$c ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle(c_{1},c_{2}})$을 개인 $키{\displaystyle }$ x ${\displaystyle x}$로 다음과 같이$$ 해독한다.

• Compute ${\displaystyle s:=c_{1}^{x}}$. Since ${\displaystyle c_{1}=g^{y}}$, ${\displaystyle c_{1}^{x}=g^{xy}=h^{y}}$, and thus it is the same shared secret that was used by Bob in encryption.
• $계산{\displaystyle }$ $s{\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$ s$^{-1}$ 그룹 G$$ ${\displaystyle$ G$}$에서 $s{\displaystyle }$ ${\displaystyle s}$의 역행$.$ 이것은 여러 가지 방법 중 하나로 계산할 수 있다.$G{\displaystyle }$ ${\displaystyle G}$이(가) 정수 modulo $n{\displaystyle }$ ${\displaystyle n}$의 승수 그룹의 하위 그룹인$$ 경우$,$ 여기서 $n{\displaystyle }$ ${\displaystyn}$은(는) 확장된 유클리드 알고리즘을 사용하여 모듈형 승수 역학을 계산할 수 있다.An alternative is to compute ${\displaystyle s^{-1}}$ as ${\displaystyle c_{1}^{q-x}}$. This is the inverse of ${\displaystyle s}$ because of Lagrange's theorem, since ${\displaystyle s\cdot c_{1}^{q-x}=g^{xy}\cd$$ot g^{(q-x)y}=(g^{q}})^{y}=e^{y}=e$
• 계산 $m{\displaystyle }$ ${\displaystyle :=}$ c ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$ s$^{-1}$.This calculation produces the original message ${\displaystyle m}$, because ${\displaystyle c_{2}=m\cdot s}$; hence ${\displaystyle c_{2}\cdot s^{-1}=(m\cdot s)\cdot s^{-1}=m\cdot e=m}$.
• $M{\displaystyle }$ {\$displaystyle{\displaystyle }$ M}을$($를) 일반$$ 텍스트 메시지 M ${\displaystyle$ M$\}.$

실용화

대부분의 공개 키 시스템과 마찬가지로 ElGamal 암호체계는 대개 하이브리드 암호체계의 일부로 사용되는데, 여기서 메시지 자체는 대칭 암호체계를 사용하여 암호화되고, 이후 ElGamal은 대칭 암호키만을 암호화하는 데 사용된다.이는 엘가말과 같은 비대칭 암호체계는 대개 같은 수준의 보안을 위해 대칭 암호체계에 비해 속도가 느리기 때문에 임의로 클 수 있는 메시지를 대칭 암호로 암호화한 다음, 대칭 키만 암호화하기 위해 엘가말(ElGamal)을 사용하는 것이 빠르기 때문이다.

보안

ElGamal 스키마의 보안은 메시지에 사용된 패딩 스키마뿐만 아니라$$ 기본 그룹 $G{\displaystyle }$ ${\displaystyle G}$의 속성에 따라 달라진다.만약 계산 디피-헬먼 가정(CDH)은 기본 순환 그룹 $G{\displaystyle }$ ${\displaystyle G}$에서 유지되며$,$ 그러면 암호화 기능은 단방향이다.^[2]

만약 결정권 디피-Hellman 가정(DDH)은 $G{\displaystyle }$ ${\displaystyle G}$에서 유지되며$,$ 이후 ElGamal은 의미적 보안을 달성한다.^[2][3]의미적 보안은 계산적 Diffie-에 의해 함축되지 않는다.지옥의 가정 하나.^[4]의사 결정 Diffifi- 참조그 가정이 유지된다고 여겨지는 집단의 토론에 대한 헬맨 가정.

ElGamal 암호화는 무조건 암호화가 가능하므로 선택한 암호문 공격에 의해 안전하지 않다.예를 들어 $일부{\displaystyle \mathrm{}}$$({\displaystyle }$아마도 알 수 없는) 메시지 m ${\$$displaystyle$ m$}$의 암호화$$(c ${\displaystyle {}_{}}$,$c2$) ${\$displaystyle m$}$을$($를) $지정$하면 $메시지$ $2m$ {\displaystyle$$$2m$의 ${\displaystyle \mathrm{유효}}$한 암호화$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,$$ $c2)$를 쉽게 구성할 수 있다$.$

선택한 암호 텍스트 보안을 달성하려면, 계획을 추가로 수정하거나 적절한 패딩 방식을 사용해야 한다.개조에 따라 DDH 가정은 필요할 수도 있고 필요하지 않을 수도 있다.

선택한 암호문 공격에 대한 보안을 달성하는 ElGamal과 관련된 다른 계획도 제안되었다.크레이머-션프 암호 $시스템$은$DDH$가 G {\$displaystyle$ G$}$을(를) 유지한다고 가정할 때 선택된 암호문 공격에 의해 안전하며$,$ 그 증거는 임의의 오라클 모델을 사용하지 않는다.또 다른 제안 계획은 DHAES인데,^[4] DHAES의 증명에는 DDH 가정보다 약한 가정이 필요하다.

효율성

ElGamal 암호화는 확률론적인 것으로, 하나의 일반 일반 텍스트가 일반 ElGamal 암호화가 일반 텍스트에서 암호 텍스트로 1:2의 크기를 확장하는 결과로 가능한 많은 가능한 암호 텍스트로 암호화될 수 있다는 것을 의미한다.

ElGamal에 의한 암호화는 두 개의 지수를 필요로 하지만, 이러한 지수는 메시지와 독립적이며, 필요한 경우 미리 계산할 수 있다.암호 해독은 하나의 지수와 그룹 역의 계산을 필요로 하는데, 단 하나의 지수로 쉽게 결합될 수 있다.

참고 항목

• Taher Elgamal, 이것과 다른 암호 시스템의 설계자
• ElGamal 서명 방식
• 동형 암호화

추가 읽기

• A. J. Menezes; P. C. van Oorschot; S. A. Vanstone. "Chapter 8.4 ElGamal public-key encryption" (PDF). Handbook of Applied Cryptography. CRC Press.
• Dan Boneh (1998). The Decision Diffie–Hellman Problem. Lecture Notes in Computer Science. Vol. 1423. pp. 48–63. CiteSeerX 10.1.1.461.9971. doi:10.1007/BFb0054851. ISBN 978-3-540-64657-0.

참조