電子署名計算の大雑把な違い ( 数的構造シリーズ外伝 )

# はじめに
今までの、各種電子署名に対する「数的構造」の記事をまとめ、計算内容のざっくりとした比較ができるようにしました。
DSA/ECDSA, EdDSA(ed25519/ed448), RSA が対象です。
※2020/10/10追記、シュノア署名も追加しました。

# 各署名の概要
## DSA/ECDSA
* 前提
    * 公知の $\gamma$ と演算 $\circ$ を準備する
    * 演算 $\circ$ に対してべき乗を $\omega^n=\underbrace{\omega\circ\omega\circ\cdots\circ\omega}\_{n個} $ とする。  
      ※楕円曲線を使うECDSAでは $n\omega=\underbrace{\omega\circ\omega\circ\cdots\circ\omega}\_{n個}$ という表現がポピュラー
    * 公知の素数 $q$ に対し、$\gamma^1,~\gamma^2,~\gamma^3,\cdots$ は周期 $q$ で繰り返すものとする ( そのように $\gamma$ を用意する )  
      ※別の言葉で言えば、$\gamma^q=\epsilon$ ( $\epsilon$ は $\circ$ に関する単位元 )
    * なお、$\circ$ の実装は、次の通り。
        * DSAの場合は $\alpha\circ\beta=mod(\alpha\times\beta,p)~(~pは公知の素数~)$
        * ECDSAの場合は、楕円曲線上の点に関する加算
* 鍵データ
    * 秘密の自然数 $x$ ( $q$未満 ) を用意し、秘密鍵とする
    * $\chi=\gamma^x$ を計算し、公開鍵とする
* 署名操作 ( 秘密鍵 $x$ を使用 )
    * ランダムな ( 再利用しない ) $q$ 未満の自然数 $k$ を用意する ( 秘密とする )
    * $\rho=\gamma^k$ を計算し、公知の方法で $\rho$ を $q$ 未満の自然数に対応させ $r$ とする
    * メッセージに対して、$q$ 未満の自然数 $z$ を対応させる ( 公知の方法、一般にハッシュ )
    * $s\equiv (z+x\times r)/k~\bmod~q$ を計算し、$(r,s)$ を署名とする  
      ※modでの除算 $/k$ は、$k\times k_{inv}\equiv 1~\bmod~q$ のような逆数 $k_{inv}$ による乗算 $\times k_{inv}$ として計算する
* 検証操作 ( 公開鍵 $\chi$ を使用 )
    * メッセージに対して、署名操作時と同様に $z$ を対応させる
    * $u_1\equiv z/s~\bmod~q,~~u_2\equiv r/s~\bmod~q$ を計算する  
      ※modでの除算は、署名操作時の $/k$ と同様
    * $\rho'=\gamma^{u_1}\circ\chi^{u_2}$ を計算し、署名操作の $r$ の時と同様の対応により $\rho'$ から $r'$ を計算する
    * $r=r'$ であれば検証成功

## シュノア署名
* 前提  
  ※DSA/ECDSAと同様
    * 公知の $\gamma$ と演算 $\circ$ を準備する
    * 演算 $\circ$ に対してべき乗を $\omega^n=\underbrace{\omega\circ\omega\circ\cdots\circ\omega}\_{n個} $ とする。  
      ※楕円曲線を使うECDSAでは $n\omega=\underbrace{\omega\circ\omega\circ\cdots\circ\omega}\_{n個}$ という表現がポピュラー
    * 公知の素数 $q$ に対し、$\gamma^1,~\gamma^2,~\gamma^3,\cdots$ は周期 $q$ で繰り返すものとする ( そのように $\gamma$ を用意する )  
      ※別の言葉で言えば、$\gamma^q=\epsilon$ ( $\epsilon$ は $\circ$ に関する単位元 )
    * なお、$\circ$ の実装は、次の通り
        * オリジナルのシュノア署名の場合は $\alpha\circ\beta=mod(\alpha\times\beta,p)~(~pは公知の素数~)$
        * 楕円曲線上の点に関する加算にすればEC版のシュノア署名となる
* 鍵データ  
  ※DSA/ECDSAと同様
    * 秘密の自然数 $x$ ( $q$未満 ) を用意し、秘密鍵とする
    * $\chi=\gamma^x$ を計算し、公開鍵とする
* 署名操作 ( 秘密鍵 $x$ を使用 )
    * ランダムな ( 再利用しない ) $q$ 未満の自然数 $k$ を用意する ( 秘密とする )
    * $\rho=\gamma^k$ を計算する
    * メッセージと $\rho$ の2要素の組に対して、公知の方法で $q$ 未満の自然数 $r$ を対応させる ( 一般にハッシュ )
    * $s = mod(k-xr,q)$ を計算し、$(r,s)$ を署名とする  
* 検証操作 ( 公開鍵 $\chi$ を使用 )
    * $\rho'=\gamma^s\circ\chi^r$を計算する
    * メッセージと $\rho'$ の2要素の組に対して、署名操作時と同様の方法で $r'$ を対応させる
    * $r=r'$ であれば検証成功

## EdDSA(ed25519/ed448)
* 前提
    * 公知の $\gamma$ と演算 $\circ$ を準備する
    * 演算 $\circ$ に対してべき乗を $\omega^n=\underbrace{\omega\circ\omega\circ\cdots\circ\omega}\_{n個} $ とする。  
      ※DSA/ECDSAのときと同様
    * 公知の素数 $q$ に対し、$\gamma^1,~\gamma^2,~\gamma^3,\cdots$ は周期 $q$ で繰り返すものとする  
      ※DSA/ECDSAのときと同様
    * なお、$\circ$ の実装は、変形版の楕円曲線 ( ツイスト化されたエドワーズ曲線 ) 上の点に関する加算
* 鍵データ
    * 秘密情報 $c$ を用意し、秘密鍵とする。そこから、$q$ 未満の自然数 $x$ を対応させ処理に使う
    * $\chi=\gamma^x$ を計算し、公開鍵とする
* 署名処理 ( 秘密鍵 $c$ および $x$ を使用 )
    * メッセージと秘密情報 $c$ から、秘密の $q$ 未満の自然数 $k$ を生成する ( ハッシュを活用 )  
      ※DSA/ECDSAでのランダムな $k$ に対応している
    * $\rho=\gamma^k$ を計算する  
      ※DSA/ECDSAでの $r$ に相当する
    * メッセージと$\chi,\rho$ から $q$ 未満の公知の自然数 $z$ を生成する ( ハッシュを活用 )  
      ※DSA/ECDSAでの $z$ に相当する
    * $s=mod(k+zx,q)$ を計算し、$(\rho,s)$ を署名とする。 
* 検証操作 ( 公開鍵 $\chi$ を使用 )
    * メッセージと $\chi,\rho$ から、署名操作時と同様に $z$ を生成する
    * $\gamma^s$ と $\rho\circ\chi^z$ を計算して比較し、一致していれば検証成功  
      ※ed25519 では、使用している曲線の co-factor が 8 であることから $\gamma^{8s}$ と $\rho^8\circ\chi^{8z}$ の比較でも十分  
      ※ed448 の場合は co-factor が 4 なので、同様に $\gamma^{4s}$ と $\rho^4\circ\chi^{4z}$ の比較でも十分

## RSA

* 鍵データ
    * 秘密の素数$p,q$を用意して、$n=pq$ を計算する
    * $ed\equiv 1~\bmod~LCM(p-1,q-1)$ となる $e,d$ を用意する  
      ※一般に $e$ には固定の数値を使用して、条件を満たす $d$ を計算する
    * 秘密鍵(署名鍵)が$(d,n)$あるいは$(d,p,q)$、公開鍵(検証鍵)が$(e,n)$
* 署名操作 ( 秘密鍵 $(d,n)$ あるいは $(d,p,q)$ を使用 )
    * メッセージに対して $n$ 未満の自然数 $h$ を対応させる ( 公知の方法、一般にハッシュ )
    * ナイーブな実装では $s=mod(h^d,n)$ を署名とする
    * 一般の実装では、$n=pq$ という素因数分解の結果を利用して次のように効率化を行う
        * $d_p=mod(d,p-1),~d_q=mod(d,q-1)$ を計算する  
          ※メッセージに依存しないので鍵生成時に予め行い鍵に含める
        * $q\times q_{inv}\equiv 1~\bmod~p$ を解いて $q_{inv}$ を求める  
          ※メッセージに依存しないので鍵生成時に予め行い鍵に含める
        * $c_p=mod(h^{d_p},p),~c_q=mod(h^{d_q},q)$ を計算する
        * $s=c_q+mod((c_p-c_q)\times q_{inv},p)\times q$ を署名とする  
          ※ナイーブな実装で計算したときと値は同じになる
* 検証操作 ( 公開鍵 $(e,n)$ を使用 )
    * メッセージに対して、署名操作と同様に $h$ を対応させる
    * 署名 $s$ に対して $h'=mod(s^e,n)$ を計算する
    * $h=h'$ であれば検証成功

# 終わりに
詳細については、元になった記事をそれぞれご参照ください。
※シュノア署名の記事はありません。気が向いたら書くかも?

* [電子署名DSA/ECDSAの数的構造](/angel_p_57/items/f2350f2ba729dc2c1d2e)
* [電子署名EdDSA(ed25519)の数的構造](/angel_p_57/items/a1dc4e9c0b18a23c5242)
* [公開鍵暗号RSAの数的構造](/angel_p_57/items/4989494481cbf3c61f04)