アルゴリズムの正当性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/19 03:03 UTC 版)
「楕円曲線DSA」の記事における「アルゴリズムの正当性」の解説
ここで C {\displaystyle C} は署名検証のステップ6で得られた点とする。 C = u 1 ∗ G + u 2 ∗ Q A {\displaystyle C=u_{1}*G+u_{2}*Q_{A}} 公開鍵が Q A = d A ∗ G {\displaystyle Q_{A}=d_{A}*G} と定義されることより C = u 1 ∗ G + u 2 d A ∗ G {\displaystyle C=u_{1}*G+u_{2}d_{A}*G} 楕円曲線上での掛け算より C = ( u 1 + u 2 d A ) ∗ G {\displaystyle C=(u_{1}+u_{2}d_{A})*G} 署名検証のステップ4より u 1 {\displaystyle u_{1}} および u 2 {\displaystyle u_{2}} の定義を拡張すると C = ( z s − 1 + r d A s − 1 ) ∗ G {\displaystyle C=(zs^{-1}+rd_{A}s^{-1})*G} s − 1 {\displaystyle s^{-1}} を外に出して C = ( z + r d A ) s − 1 ∗ G {\displaystyle C=(z+rd_{A})s^{-1}*G} 署名のステップ6より s {\displaystyle s} の定義を拡張すると C = ( z + r d A ) ( z + r d A ) − 1 ( k − 1 ) − 1 ∗ G {\displaystyle C=(z+rd_{A})(z+rd_{A})^{-1}(k^{-1})^{-1}*G} 逆数の逆数は元と同じであることと、逆数と元の積は O {\displaystyle O} であることから C = k ∗ G {\displaystyle C=k*G} r {\displaystyle r} の定義より、これは署名検証のステップ6と等しい。 これは正しく署名されたメッセージは正しく検証されることのみを示しており、セキュアな署名アルゴリズムであるための他の要素については考慮していない。
※この「アルゴリズムの正当性」の解説は、「楕円曲線DSA」の解説の一部です。
「アルゴリズムの正当性」を含む「楕円曲線DSA」の記事については、「楕円曲線DSA」の概要を参照ください。
アルゴリズムの正当性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/03 03:47 UTC 版)
「Digital Signature Algorithm」の記事における「アルゴリズムの正当性」の解説
DSAの署名スキームは、検証者が常に純正の署名を受け入れるという意味では正当である。それは以下のように証明される。 g = h(p − 1)/q mod p であるとき、フェルマーの小定理より gq ≡ hp − 1 ≡ 1 (mod p) が導かれる。g > 1 かつ q が素数であるから、g は次数 q でなければならない。 署名者は次式を計算する。 s = k − 1 ( H ( m ) + x r ) mod q {\displaystyle s=k^{-1}(H(m)+xr){\bmod {\,}}q} ゆえに k ≡ H ( m ) s − 1 + x r s − 1 ≡ H ( m ) w + x r w ( mod q ) {\displaystyle {\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}} g は次数 q (mod p) であるから g k ≡ g H ( m ) w g x r w ≡ g H ( m ) w y r w ≡ g u 1 y u 2 ( mod p ) {\displaystyle {\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u1}y^{u2}{\pmod {p}}\end{aligned}}} 最終的に、DSAの正当性は以下に示される。 r = ( g k mod p ) mod q = ( g u 1 y u 2 mod p ) mod q = v {\displaystyle {\begin{aligned}r&=(g^{k}{\bmod {\,}}p){\bmod {\,}}q\\&=(g^{u1}y^{u2}{\bmod {\,}}p){\bmod {\,}}q\\&=v\end{aligned}}}
※この「アルゴリズムの正当性」の解説は、「Digital Signature Algorithm」の解説の一部です。
「アルゴリズムの正当性」を含む「Digital Signature Algorithm」の記事については、「Digital Signature Algorithm」の概要を参照ください。
- アルゴリズムの正当性のページへのリンク
