ElGamal 서명 방식

ElGamal 서명 체계는 이산 로그 계산의 어려움에 기초하는 디지털 서명 체계다. 1985년 타헤르 엘가말(Taher Elgamal)이 묘사한 것이다.^[1]

ElGamal 시그니처 알고리즘은 실제로 거의 사용되지 않는다. NSA에서 개발되고 디지털 서명 알고리즘으로 알려진 변종이 훨씬 더 널리 사용된다. 몇 가지 다른 변종이 있다.^[2] ElGamal 서명 발명된 ElGamal 암호화와 혼동해서는안 된다 체계는 Taher Elgamal에 의해.

개요

ElGamal 서명 체계는 이산 로그 문제와 함께 모듈형 지수의 대수적 특성에 기초한 디지털 서명 체계다. 알고리즘은 공용 키와 개인 키로 구성된 키 쌍을 사용한다. 개인 키는 메시지의 디지털 서명을 생성하는 데 사용되며, 이러한 서명은 서명자의 해당 공개 키를 사용하여 확인할 수 있다. 디지털 서명은 메시지 인증(수신자가 메시지의 출처를 확인할 수 있음), 무결성(수신자가 서명한 이후 메시지가 수정되지 않았음을 확인할 수 있음) 및 비거부(수신자가 메시지에 서명하지 않았다고 거짓으로 주장할 수 없음)를 제공한다.

역사

ElGamal의 서명 체계는 1985년 Taher Elgamal에 의해 설명되었다.^[1]

작전

이 계획에는 키 생성(키 쌍 생성), 키 배포, 서명 및 서명 검증의 네 가지 작업이 포함된다.

키 생성

키 생성에는 두 가지 단계가 있다. 첫 번째 단계는 시스템의 다른 사용자들 간에 공유될 수 있는 알고리즘 매개변수의 선택이며, 두 번째 단계는 한 사용자에 대해 단일 키 쌍을 계산한다.

매개 변수 생성

키 길이 $N$ $N$ 을(를) 선택하십시오 $N$
$N$ $N$ -비트 $N$ 소수 $p$ $p$ 선택
출력 길이 $L$ $L$ 비트의 $H$ $L$ 암호화 해시함수 $H$ $H$ 를 선택하십시오. $L>N$ > $L>N$ ${\displaystyle L>N$ 인 경우 해시 출력의 $가장$ 왼쪽 N $N$ 비트만 $N$ 사용된다.
정수 modulo p, $Z_{p}^{*}$ $Z_{p}^{*}$ $Z_{p}^{*}$ ${\$ 의 곱셈 그룹에서 $g<p$ ${\displaystyle g생성기<semantics><mrow class=$ g ${\displaystyle g<semantics><mrow class=$ < p < ${\displaystyle g<semantics><annotation encoding=$ g ${\displaystyle g<semantics><annotation encoding=$ 를 선택하십시오 $Z_{p}^{*}$

알고리즘 매개변수는 $(p,g)$ ( $(p,g)$ , $(p,g)$ ) $(p,g)$ 이다 $(p,g)$ 이러한 매개변수는 시스템 사용자 간에 공유될 수 있다.

사용자별 키

매개변수 집합이 주어진 경우, 두 번째 단계는 단일 사용자에 대한 키 쌍을 계산한다.

정수 $x$ ${\displaystyle x$ $\{1\ldots p-2\}$ 을 $\{1\ldots p-2\}$ 를 $\{1\ldots p-2\}$ { $\{1\ldots p-2\}$ … p - 2 } {\ $displaystyle \{1\$ ldots $p-2\}$ 에서 임의로 $x$ 선택하십시오 $\{1\ldots p-2\}$
계산 $y:=g^{x}{\bmod {p}}$ $y:=g^{x}{\bmod {p}}$ $y:=g^{x}{\bmod {p}}$ $y:=g^{x}{\bmod {p}}$ $y:=g^{x}{\bmod {p}}$ $y:=g^{x}{\bmod {p}}$ ${\$ .

$x$ $x$ 은 $x$ (는) 개인 키이고 $y$ $y$ 은 $y$ (는) 공개 키입니다.

키 분배

서명자는 공개 키 $y$ $y$ 을(를) 신뢰할 수 있지만 반드시 비밀은 아닌 메커니즘을 통해 수신기로 보내야 $y$ 한다. 서명자는 개인 키 $x$ $x$ 을 $x$ (를) 비밀로 유지해야 한다.

서명

메시지 $m$ $m$ 은(는) 다음과 같이 서명된다 $m$ .

$\{2\ldots p-2\}$ … $\{2\ldots p-2\}$ - $\{2\ldots p-2\}$ $\{2\ldots p-2\}$ $\{2\ldots p-2\$ 에서 임의로 $k$ $정수$ k ${\$ $displaystyle k}$ 을(를 $\{2\ldots p-2\}$ $)$ $p-1$ - $p-1$ $p-1$ 에 상대적으로 $k$ prime으로 선택하십시오 $p-1$
계산 $r:=g^{k}{\bmod {p}}$ $r:=g^{k}{\bmod {p}}$ $r:=g^{k}{\bmod {p}}$ $r:=g^{k}{\bmod {p}}$ $r:=g^{k}{\bmod {p}}$ $r:=g^{k}{\bmod {p}}$ ${\$ .
계산 $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ ( $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ ( m $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ ) $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ - $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ ) k $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ - $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ ( $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ - $s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)$ ) ${\displaystyle s:=(H(m)-xr)k^{-1}{\bmod$ {{{\b-mod ${{{{{{p-1$ .
$s=0$ $s=0$ 지만 $s=0$ s $s=0$ = 0 {\ $displaystyle s$ =0}은(는) 다른임의 k {\ $displaystyle k}$ 로 다시 시작한다 $s=0$ $k$

서명은 $(r,s)$ ( $(r,s)$ , $(r,s)$ ) $(r,s)$ 입니다 $(r,s)$

서명 확인

다음과 같이 $m$ 서명 $(r,s)$ , s $(r,s)$ ) {\ $displaystyle$ (r $,s)}$ 이(가) $메시지$ m $m$ 에 대한 유효한 서명인지 $(r,s)$ 확인할 수 있다.

${\displaystyle 0<r0<semantics><mrow class=$ < ${\displaystyle 0<r<semantics><mrow class=$ < ${\displaystyle 0<r<semantics><mrow class=$ ${\displaystyle 0<r<semantics><annotation encoding=$ ${\displaystyle 0<s0</math><img alt=$ < ${\displaystyle 0<s<semantics><mrow class=$ - ${\displaystyle 0<s<semantics><mrow class=$ ${\displaystyle 0<s<semantics><annotation encoding=$ }을(를 ${\displaystyle 0<s<semantics><annotation encoding=$ 확인하십시오 ${\displaystyle 0<s.</math></span><img alt=$
서명은 $g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.$ $g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.$ ( $g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.$ ) $g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.$ y $g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.$ $g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.$ ( $g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.$ p $g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.$ ) $g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.$ . $g^{H(m)}\equiv y^{r^{s}{\pmod {p$ 인 경우에만 유효하다. $}$

정확성

서명 알고리즘으로 생성된 서명이 검증자에 의해 항상 수용된다는 점에서 알고리즘은 정확하다.

시그너처 $s$ 생성 $중$ s {\ $displaystyle$ s $}$ 의 계산은 다음을 함축한다.

H(m)\,\equiv \,xr+sk{\pmod {p-1}.

$g$ $g$ 은 $g$ (는) $p$ $p$ 에 상대적으로 prime이기 때문에 $p$

{\begin{aigned}g^{H(m)}&\equiv g^{xr+sk}{\pmod{p}\\&\equiv (g^{x})^{s}{\pmod}{pmod}^{p}{pmod}.\\end{aigned}

보안

제3자는 서명자의 비밀키 x를 찾거나 $H(m)\equiv H(M){\pmod {p-1}}$ H $H(m)\equiv H(M){\pmod {p-1}}$ ( $H(m)\equiv H(M){\pmod {p-1}}$ ) $H(m)\equiv H(M){\pmod {p-1}}$ H $H(m)\equiv H(M){\pmod {p-1}}$ ( $H(m)\equiv H(M){\pmod {p-1}}$ ) $H(m)\equiv H(M){\pmod {p-1}}$ ( $H(m)\equiv H(M){\pmod {p-1}}$ $H(m)\equiv H(M){\pmod {p-1}}$ - 1 $){\$ 에서 충돌을 발견하여 서명을 위조할 수 있다 $H(m)\equiv H(M){\pmod {p-1}}$ 두 가지 문제 모두 어려운 것으로 생각된다. 그러나 2011년 현재 계산 경도 가정에 대한 엄격한 감소는 알려져 있지 않다.

서명자는 각 서명에 대해 무작위로 다른 k를 선택하고 k, 또는 k에 대한 부분적인 정보가 유출되지 않도록 주의해야 한다. 그렇지 않으면 공격자는 아마도 실제 공격을 허용하기에 충분할 정도로 어렵게 비밀키 x를 추론할 수 있을 것이다. 특히 같은 k 값과 같은 키를 사용해 두 개의 메시지를 보내면 공격자가 x를 직접 계산할 수 있다.^[1]

실존적 위작

원래 종이는^[1] 시스템 파라미터로 해시함수를 포함하지 않았다. 메시지 m은 H(m) 대신 알고리즘에서 직접 사용하였다. 이로써 이 논문의 제4절에서 설명한 실존적 위변조라는 공격이 가능해진다. Pointcheval과 Stern은 그 사건을 일반화했고 두 가지 수준의 위조를 묘사했다.^[3]

단일 변수 위변조. {\displaystyle e}가 1<>e<>안 − 1{1<, e<, p-1\displaystyle}.는 메시지를 설치하여 r:=g e y음악과 노래의 집회 p{\displaystyle r:=g^{e}y{\bmod{p}}}과 s:=− r모드(p1−){s\displaystyle:=-r{\bmod{(p-1)}}}. 그 다음 투플(r, s){\displaystyle(r,s)}은 타당한 시그니처가 e를 선택한다. m)e는 그것 $m=es{\bmod {(p-1)}}$ - $m=es{\bmod {(p-1)}}$ ) ${\$
2-모수 위변조. . 설치하여 r:=1<>e, v<>안 − 1{1<, e,v<, p-1\displaystyle}, 그리고 gcd(v, p− 1)=1{\displaystyle \gcd(v,p-1)=1}을 선택합니다 ge는 y'v'모드 족인지 조차 p{\displaystyle r:=g^{e}y^{v}{\bmod{p}}}과 s:=− rv− 1모드(p1−){s\displaystyle:=-rv^{)}{\bmod{(p-1)}}}. 그 다음 투플(r, s){\dis.playstyle( $r,s)}$ 은 $(r,s)$ $m=es{\bmod {(p-1)}}$ = e $m=es{\bmod {(p-1)}}$ $m=es{\bmod {(p-1)}}$ $m=es{\bmod {(p-1)}}$ - 1 $m=es{\bmod {(p-1)}}$ ) ${\$ 메시지에 대한 유효한 서명이다 $m=es{\bmod {(p-1)}}$ $v=1$ 위조는 $v=1$ = 1 $v=1$ 일 때 2-모수 위조의 특수한 경우다 $v=1$

참고 항목

참조

^ ^a ^b ^c ^d Taher ElGamal (1985). "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms" (PDF). IEEE Transactions on Information Theory. 31 (4): 469–472. CiteSeerX 10.1.1.476.4791. doi:10.1109/TIT.1985.1057074. (CRIPTO'84, 페이지 10–18에 컨퍼런스 버전이 표시됨)
^ K. Nyberg, R. A. Rueppel (1996). "Message recovery for signature schemes based on the discrete logarithm problem". Designs, Codes and Cryptography. 7 (1–2): 61–81. doi:10.1007/BF00125076. S2CID 123533321.
^ Pointcheval, David; Stern, Jacques (2000). "Security Arguments for Digital Signatures and Blind Signatures" (PDF). J Cryptology. 13 (3): 361–396. CiteSeerX 10.1.1.208.8352. doi:10.1007/s001450010003. S2CID 1912537.

[ElgamalOriginalArticle-1] Taher ElGamal (1985). "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms" (PDF). IEEE Transactions on Information Theory. 31 (4): 469–472. CiteSeerX 10.1.1.476.4791. doi:10.1109/TIT.1985.1057074. (CRIPTO'84, 페이지 10–18에 컨퍼런스 버전이 표시됨)

[2] K. Nyberg, R. A. Rueppel (1996). "Message recovery for signature schemes based on the discrete logarithm problem". Designs, Codes and Cryptography. 7 (1–2): 61–81. doi:10.1007/BF00125076. S2CID 123533321.

[3] Pointcheval, David; Stern, Jacques (2000). "Security Arguments for Digital Signatures and Blind Signatures" (PDF). J Cryptology. 13 (3): 361–396. CiteSeerX 10.1.1.208.8352. doi:10.1007/s001450010003. S2CID 1912537.

[1]

[2]

[3]

Search