楕円曲線DSA
楕円曲線DSA(だえんきょくせんDSA、Elliptic Curve Digital Signature Algorithm、Elliptic Curve DSA、楕円DSA、ECDSA)は、Digital Signature Algorithm (DSA) について楕円曲線暗号を用いるようにした変種である。
z {\displaystyle z} を、 e {\displaystyle e} の最上位側の L n {\displaystyle L_{n}} ビットとする。
w = s − 1 mod n {\displaystyle w=s^{-1}\,{\bmod {\,}}n} を計算する。
u 1 = z w mod n {\displaystyle u_{1}=zw\,{\bmod {\,}}n} および u 2 = r w mod n {\displaystyle u_{2}=rw\,{\bmod {\,}}n} を計算する。
曲線上の点 ( x 1 , y 1 ) = u 1 ∗ G + u 2 ∗ Q A {\displaystyle (x_{1},y_{1})=u_{1}*G+u_{2}*Q_{A}} を計算する。
r ≡ x 1 ( mod n ) {\displaystyle r\equiv x_{1}{\pmod {n}}} であれば署名は正当なものである。
Straus's algorithm(Shamir's trickとも)を用いることで、2つの楕円曲線上での掛け算の和 u 1 ∗ G + u 2 ∗ Q A {\displaystyle u_{1}*G+u_{2}*Q_{A}} を、2つの楕円曲線上での掛け算よりも速く計算することができる。