라빈 시그니처 알고리즘

암호학에서 라빈 시그니처 알고리즘은 1978년 마이클 오 라빈이 원래 제안한 디지털 시그니처 방식이다.^[1][2][3]

라빈 서명 알고리즘은 제안된 최초의 디지털 서명 체계 중 하나이다.서명에서 해싱의 사용을 필수적인 단계로 도입함으로써, 그것은 적절한 규모의 매개 변수를 가정하고 선택된 메시지 공격 하에서 위변조, 실존적 용서 불가에 대한 현재의 현대적 보안 표준에 부합하는 최초의 설계였다.

라빈 서명은 '우수 $e{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle e=2}'$의 RSA 서명을 닮았지만,$$ 이는 RSA에 대해 검증되지 않은 정수 인수화의 어려움에 비해 보다 효율적인 구현과^[4] 보안 보증을 가능하게 하는 질적 차이로 이어진다.^[2][3][5]그러나 RSASASA-PKCS1-v1_5 및 RSASA-PSS와 같은 RSA 시그니처 체계에 비해 Rabin 서명은 IEEE P1363^[6] 외부에서 상대적으로 사용이나 표준화가 거의 이루어지지 않았다.

정의

Rabin 서명 체계는 메시지 $m{\displaystyle }$ ${\displaystyle m}$ 및$$ $k{\displaystyle }$ ${\displaystyle k}$ -bit$$ 랜덤화 문자열 $u{\displaystyle }$ ${\displaystyle u}$의 임의화된 해시함수 $m,u) {\displaystystyle$ u}에 의해 매개 변수화된다$.$

공개키

공개 키는 (${\displaystyle n}$, ${\displaystyle b}$)${\displaystyle(n,b)}$이며, b< $[\displaystyle 0\leq b<$$n{\displaystyle }$$}$ 및 n ${\displaystyle n}$ 홀수$$.

서명

메시지 $m{\displaystyle }$ ${\displaystyle m}$의 서명은 $k{\displaystyle }$ ${\displaystyle k}$ -bit$$ 문자열 $u{\displaystyle }$ {\$displaystyle u}$과$($$와$$$$$) $정수{\displaystyle }$ x ${\displaystyle$ x$}$의 쌍$($, x )이다$.$

$${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}.}$$

개인 키

공개 키$({\displaystyle n}$, b${\displaystyle }$) ${\displaystyle (n,b)}$의 개인 키는 큰 프리임의 일부 공간에서 무작위로 균일하게 선택한 $n{\displaystyle }${\$displaystyle p$$\cdot q$$}$의 비밀 홀수 프라임 인수 $p{\displaystyle }$이다$.$Let ${\displaystyle d=(b/2){\bmod {n}}}$, ${\displaystyle d_{p}=(b/2){\bmod {p}}}$, and ${\displaystyle d_{q}=(b/2){\bmod {q}}}$. To make a signature on a message ${\displaystyle m}$, the signer picks a ${\displaystyle k}$-비트 문자열 $u{\displaystyle }$ ${\$$displaystyle u$$}$은(는) 임의로 균일하게 $c{\displaystyle }$ ${\displaystyle :=H(m}$, $){\displaystyle$ $c:=$$H(m,u)}$를$$$계산$한다${\displaystyle .}$ ${\displaystyle {c\mathrm{}}^{}}$ + d 2 ${\$ c+$d^{2}}$가 2차 비residue modulo $n{\displaystyle }$ ${\\$d$}$이면 $서명자$는$$u$$$}$을 버리고 다시$$ 시도한다.그렇지 않으면 서명자가 계산한다.

$${\displaystyle {\begin{aligned}x_{p}&:={\Bigl (}-d_{p}\pm {\sqrt {c+{d_{p}}^{2}}}{\Bigr )}{\bmod {p}}\\x_{q}&:={\Bigl (}-d_{q}\pm {\sqrt {c+{d_{q}}^{2}}}{\Bigr )}{\bmod {q}},\end{aligned}}}$$

제곱근 modulo a prime을 계산하기 위한 표준 알고리즘을 사용하는 것—192 $p{\displaystyle }$≡ ${\displaystyle \mathrm{q}}$ ${\displaystyle \equiv }$ 3${\displaystyle }$(${\displaystyle \mathrm{mod}}$ ${\displaystyle 4\mathrm{}}$ )${\$4}}}}}는$$ 가장 쉬운 방법이다.제곱근은 고유하지 않으며, 서로 다른 변형 서명 방식은 제곱근의 다른 선택을 한다.^[4] 어떤 경우든 서명자는 동일한 $해시{\displaystyle }$ c$${\$displaystyle c$}에 대해 서로 다른 두 개의 루트를 노출하지 않도록 해야 한다$.$그 후 서명자는 중국의 나머지 정리를 사용하여 시스템을 해결한다.

$${\displaystyle {\pmod}x&\equiv x_{q}{\pmod{n}\x&\equiv x_{pmod}{n}\pmod{n}\ended}}}}}}$$

$x{\displaystyle }$ ${\displaystyle x}$의$$경우서명자가 마침내${\displaystyle }$(${\displaystyle u}$, ${\displaystyle x}$) ${\displaystyle (u,x)}$을(를) 표시한다$.$

$서명{\displaystyle }$ 절차의 정확성은 x${\displaystyle }$( x${\displaystyle }$+ ${\displaystyle b}$)${\displaystyle }$- H${\displaystyle }$( ${\displaystyle m}$ ,${\displaystyle u}$ ${\displaystyle )}$ ${\displaystyle x(x+b)-H(m,u)}$ modulo$$ $p{\displaystyle }$ ${\displaystyle p}$ 및$$ $q{\displaystyle }$ ${\$$displaystyle q}$을($x$ {\$displaystystyle x})$로 평가하여 나타난다.예를 들어 $b{\displaystyle }$= ${\displaystyle 0}$ ${\$$displaystyle$ $b=0}$이$($가) 있는 단순 $사례$에서$$x {\$displaystyle x$$}$은(는$)$ 단순히 H($m$$,$ ${\displaystyle )}$의 제곱근일 $뿐이다$.u {\$displaystyle u}$에 대한 시행 횟수는 전체 정수의 약 1/4이 2차 잔류물 모듈로 $n{\displaystyle }$ ${\displaystyle n$이기 때문에 약 4가 예상과 함께 기하학적으로 분포한다$.$

보안

해시함수 $H{\displaystyle }$ ${\displaystyle H}($즉, 랜덤 오라클 모델의 보안) 측면에서 일반적으로 정의된 적에 대한 보안: $n{\displaystyle }$ ${\displaystyle n}$을(를) 인수하기 어려운 데서 비롯된다$.$ 위조에 성공할 확률이 높은 적들은 거의 높은 두 개의 뚜렷한 사각형 루를 찾을 수 있다.ts ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ of a random integer ${\displaystyle c}$ modulo ${\displaystyle n}$. If ${\displaystyle x_{1}\pm x_{2}\not \equiv 0{\pmod {n}}}$ then ${\displaystyle \gcd(x_{1}\pm x_{2},n)}$is a nontrivial factor of ${\displaystyle n}$, since ${\displaystyle {x_{1}}^{2}\equiv {x_{2}}^{2}\equiv c{\pmod {n}}}$ so ${\displaystyle n\mid {x_{1}}^{2}-{x_{2}}^{2}=(x_{1}+x_{2})(x_{1}-x_{2}$)}지만 n∤=1±x2{\displaystylen\nmid x_{1}\pm x_{2}}근대적 의미에서 보안 Formalizing .[3]H{H\displaystyle}의 변역과 같은 추가적인 세부 사항을 메우고;만약 우리가 소인수들을 위한 표준형 K{K\displaystyle}, 2K; 와<>q<>2K{\displa 1<>−이 필요하다.ystyle 2^{K-$1}<<2^{$$K$ 그러면 $우리$는$$H${\displaystyle }$:${\displaystyle }${ ${\displaystyle 0,}$ ${\displaystyle 1{}^{\ast }}$ ${\displaystyle {}^{}}${ 0${\displaystyle ,}$ ${\displaystyle 1{}^{}}$k${\displaystyle {}^{}}$→${\displaystyle }${ ${\displaystyle 0,}$ ${\displaystyle 1{}^{}}$} ${\displaystyle K^{}}$ ${\$\{$0,1\}\}\{0,1\}^{K}}}}$을 지정할 수 있다$.$^[5]

해시함수의 무작위화는 서명자가 2차적 잔류물을 찾을 수 있도록 도입되었으나, 이후 서명을 위한 무작위 해싱은 고정 해시함수에 대한 충돌 공격에 대한 보다 엄격한^[3] 보안 이론과 복원력을 위해 자체적으로 타당해졌다.^[7][8][9]

변형

$b{\displaystyle }$ ${\displaystyle b}$과${\displaystyle (}$$와{\displaystyle }$) ${\displaystyle$ $b$$}$이($)$ 주어진 x ${\displaystyle x}$에 대한 congruities x ($x{\displaystyle }$+$b)\equiv c{\pmod{n}}$을(를) 해결하기 위한 알고리즘은 알고리즘에서 하위 루틴으로 사소한 용도로 사용될 수 있으므로$$ 공용 $키$의 수 없다.제곱근 modulo $n{\displaystyle }$ ${\displaystyle n}$을(를) 계산하고 그 반대로 구현하면 $b{\displaystyle }$= 0 ${\displaystyle b=0}$을(를) 안전하게 설정하여 단순성을$$ $보장$할$$수 $있으며$, b {\displaystyle $b}$은(는) 최초 제안 후 처리에서 완전히 폐기되었다$$.^{[10][3][6][4]}

그 라빈 서명 계획 후에 윌리엄스는 이미 1980[10]에 p≡ 3(모드 8){\displaystyle p\equiv 3{\pmod{8}을 선택할}}과q ≡ 7(모드 8){\displaystyle q\equiv 7{\pmod{8}}},, e.과tweaked 제곱 근(e, f,)){\displaystyle(e,f,x)}에 의해 제곱 근){\displaystyle)}을 대체하겠지만다)±${\displaystyle }$서명이 대신 충족되도록$$ {\$displaystyle$ e$=\pm 1}$ 및$$ $f{\displaystyle }$ ${\displaystyle \in }${${\displaystyle 1,}$ ${\displaystyle 2\}}$ ${\displaystyle f\in \{1,2$

서명자가 보안을 희생하지 않고 단 한 번의 재판으로 서명을 할 수 있게 해 주는 겁니다이 변종은 라빈-윌리암스로 알려져 있다.^[4][6]추가 변형에서는 서명 크기와 확인 속도, 부분 메시지 복구, 서명 압축 및 공개 키 압축 간의 절충이 가능하다.^[4]

해시함수가 없는 변형들은 교과서에 실렸으며,^[11][12] 지수 2는 라빈을 신뢰하지만 해시함수는 사용하지 않았다.이러한 변형은 사소한 것으로 깨진다. 예를 들어, 서명 확인 $방정식$이 x ${\displaystyle {2\mathrm{}}^{}h}$H${\displaystyle (m}$ ${\displaystyle ,}$ ${\displaystyle u)}$가 $아닌{\displaystyle {}^{}}$ ${\displaystyle {x\mathrm{}}^{}}$ 2${\displaystyle {}^{}m}$ m${\displaystyle (모드}$ n${\displaystyle }$) ${\$ x$^{2}\equiv m{\pmod{n}}$인 $경우$, $서명{\displaystyle }$x = ${\displaystyle 2}$ ${\displaystystyle m=4}$ 메시지에 유효한 서명으로 위조할 수 있다$$.${\displaystyle \mathrm{mod}}$ ${\displaystyle n}$) ${\$

원래 논문에서 해시함수 $H{\displaystyle (m}$ ,${\displaystyle u}$ ${\displaystyle )}$ ${\displaystyle H(m,u)}$은 $표기법{\displaystyle }$ C$($${\displaystyle M}$ U$$) {\$displaystyle$C(MU$)}$와 압축용 C(MU)로 작성되었으며, 대위사를 사용하여 $M{\displaystyle }$ ${\displaystyle M}$과 $U{\displaystyle }$ ${\displaysty U}$의 결합을 비트 문자열로$$ 표시하였다.^[2]

관례에 따라, 주어진 메시지에 서명하고자 할 때, $M{\displaystyle }$ ${\displaystyle M$ [seigner] $P{\displaystyle }$ ${\displaystyle P}$이(가) $길이{\displaystyle }$ k ${\displaystyle k}$에 합의된 단어$$ $U{\displaystyle }$ ${\displaystyle$ U}를$$접미사로 추가한다$.$$U{\displaystyle }$ ${\displaystyle U}$의 선택은 메시지가 서명될 때마다 랜덤화된다$$.이제 서명자가 $M{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= M ${\displaystyle U}$ ${\displaystyle M_{1}=$를 압축함$C{\displaystyle }$(${\displaystyle {M\mathrm{}}_{}}$ 1 )${\displaystyle }$= ${\displaystyle c}$ ${\displaystyle C(M_{1}}=c$에 대한 해싱 함수에 의한$$ $MU}$을(를) 사용하여 이진수 $c{\displaystyle }$ $({\displaystyle$ c$\leq$ $\dots \}).$

이 표기법은 $나중$에 C ${\displaystyle C}$ 부분을$$ 무시하고 ${\displaystyle M}$ U ${\displaystyle MU}$을 곱셈을 의미하는$$ 것으로 오해한 일부 작가들 사이에 약간의 혼동을 초래하여 사소한 서명이 깨진 것을 오해하게 했다.^[13]

참조

외부 링크

• Rabin-Williams 서명 cr.yp.to