はじめに
今までの、各種電子署名に対する「数的構造」の記事をまとめ、計算内容のざっくりとした比較ができるようにしました。
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)$ を署名とする。
- メッセージと秘密情報 $c$ から、秘密の $q$ 未満の自然数 $k$ を生成する ( ハッシュを活用 )
- 検証操作 ( 公開鍵 $\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$ を署名とする
※ナイーブな実装で計算したときと値は同じになる
- $d_p=mod(d,p-1),~d_q=mod(d,q-1)$ を計算する
- 検証操作 ( 公開鍵 $(e,n)$ を使用 )
- メッセージに対して、署名操作と同様に $h$ を対応させる
- 署名 $s$ に対して $h'=mod(s^e,n)$ を計算する
- $h=h'$ であれば検証成功
終わりに
詳細については、元になった記事をそれぞれご参照ください。
※シュノア署名の記事はありません。気が向いたら書くかも?