LoginSignup
9
8

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-03-07

はじめに

今までの、各種電子署名に対する「数的構造」の記事をまとめ、計算内容のざっくりとした比較ができるようにしました。
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'$ であれば検証成功

終わりに

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

9
8
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
9
8