暗号と署名の話

某身分の義務であるアウトリーチ活動の一環として, 教科書的RSA暗号/署名と教科書的ElGamal暗号/署名を比べてみます. 以下の図をご参照ください.

追記: 絵だけみてもわからないので, 書き直し.

RSA暗号は知っているが, ElGamal暗号やElGamal署名については良く知らないという人向けです.

承前

高木浩光＠自宅の日記 - 公開鍵暗号方式の誤り解説の氾濫をそろそろどげんかせんとで問題になっている点は以下です.

最もひどく蔓延っていてしばらく消えそうにない間違い解説の典型例は次だ。

  • 「公開鍵で暗号化したものを秘密鍵で復号するのと同様に、秘密鍵で暗号化したものを公開鍵で復号できるようになっている。」
  • 「公開鍵暗号方式による署名は、メッセージダイジェストを秘密鍵で暗号化することで実現する。」
    • 事例2: 総務省「国民のための情報セキュリティサイト」用語辞典「公開鍵」
      • (略:186)

これらの解説は誤っている。これらは、RSAアルゴリズムを説明するものにはなり得ても、公開鍵暗号方式を説明するものになっていない。公開鍵と秘密鍵が「逆に使える」というのはRSAアルゴリズムがたまたま（まあまあ）そうなだけであって、そのような性質を持たない他の公開鍵暗号方式がたくさん存在する。

ということなので, そのような性質を持たない他の公開鍵暗号方式を見てみましょう.
まずRSA暗号/署名方式を復習した後, そのような性質を持たない例としてElGamal暗号/署名方式について見ていきます.

その前に, そもそも電子署名とは?

(2008/03/05 00:30 追記)
電子署名に求められるのは以下の二つです.

検証可能性
正しい署名ならば, 公開情報とともにチェックすると必ず“受理”となる.
偽造不可能性
秘密情報を持っていない人は, 検証を通るような署名を作ることが出来ない.

検証可能性は当たり前の要求ですね. 正しく作った署名は必ず正しいと判断されます. 偽造不可能性も当然の要求です. 正しい印鑑を持っていない人は正しい印を残せないというのに対応しています.

電子署名は三つのフェーズからなります. 鍵生成, 署名, 検証です.
鍵生成フェーズでは署名に使う鍵と検証に使う鍵を作ります. ここでは署名に使う鍵を署名鍵, 検証に使う鍵を検証鍵と呼ぶことにします. 公開鍵/秘密鍵という言い方や, 暗号化鍵/復号鍵という言い方は避けましょう. これが混乱の元です.
署名フェーズでは署名鍵を持った署名者が文書に対して署名を行います.
検証フェーズでは検証者が検証鍵, 文書, 署名の3つに対して検証を行います.

なお, 公開鍵暗号方式を利用した署名と言った場合には, 鍵生成が暗号方式の鍵生成と共通であることが多いです. 署名方式の署名鍵と暗号方式の復号鍵が対応し, 署名方式の検証鍵と暗号方式の暗号化鍵が対応します.

RSA暗号方式と署名方式

RSA暗号方式

さて素朴なRSA暗号方式を見てみましょう.

  • 鍵生成
    1. 大きな素数pとqを選び, \(n=pq\)とする.
    2. \(1 < e < (p-1)(q-1)\)かつ\(e\)が\( (p-1)(q-1)\)と互いに素なものを求める.
    3. \(d\)を \(de \equiv 1 \pmod{(p-1)(q-1)}\) となるものとする.
      1. \(de\)は\((p-1)(q-1)\)で割ると余り1.
    4. 暗号化鍵はnとe. 復号鍵はn, p, q, d. (nとdだけでも構わない.)

色々とややこしいですが, そういうものだと思ってください. (詳しくは検索すると出てきます.)
暗号化鍵(n,e)から復号鍵の一部dを求めることが出来るならばnをpとqに素因数分解できることが知られています. 素因数分解は難しいと思われているので暗号化鍵から復号鍵を求めることは難しそうです.

暗号化関数をE (encryptの頭文字), 復号関数をD (decryptの頭文字) とします. 暗号化関数にメッセージmを入れると暗号文cが出てきます. 復号関数に暗号文cを入れるとメッセージmが出てきます.

図だとこんな感じです.
では関数の中身を見てみましょう.

暗号化関数の方は, メッセージmを入力として, \(c=m^e \bmod n\)を出力します. 復号関数の方は, 暗号文cを入力として, \(m=c^d \bmod n\)を出力します. 任意の\(m\)について\(D(E(m))=m\)となることが数学的に証明できます. (ここで\(a^b \bmod n\)はaをb乗したものをnで割った余りです.)

さて, \(D(E(m))\)をちょっと詳しくみてみましょう.

\(m \equiv D(E(m)) \equiv D(m^e \bmod n) \equiv (m^e)^d \equiv m^{ed} \pmod{n})\).

指数法則から, \( (m^e)^d = m^{ed}\)になることを思い出してください.
上の式で指数法則を逆に適用すると,

\(m \equiv m^{ed} \equiv (m^d)^e \equiv E(m^d mod n) \equiv E(D(m)) \pmod{n}\)

が言えます.
従って, RSA暗号方式では, D(E(m))のように暗号化してから復号したものと, E(D(m))のように復号してから暗号化したものが一致します.

次に関数の引数を変えてみましょう.
よくよく考えると, EとDを2引数として見ることが出来ます.

  • \(E(m,e) = m^e \bmod n\)
  • \(D(c,d) = c^d \bmod n\)

ですね. これって形が同じですよね? ということは以下のように書いても良いわけです.

  • \(E(m,d) = m^d \bmod n\)
  • \(D(c,e) = c^e \bmod n\)

これが高木さんの記事で挙げられている公開鍵で暗号化したものを秘密鍵で復号するのと同様に、秘密鍵で暗号化したものを公開鍵で復号できるようになっているの説明です. 秘密鍵dで暗号化したものを, 公開鍵eで復号出来ますね.

RSA署名方式

さてRSA署名方式を見てみましょう.
署名鍵は(n,d), 検証鍵が(n,e)です. 署名アルゴリズムをS (signの頭文字), 検証アルゴリズムをV (verifyの頭文字) にしています. ハッシュ関数をHと書いています. メッセージをハッシュ関数に通した値をメッセージダイジェストと呼びます.

中身を見ると以下のようになっています.

署名アルゴリズムはメッセージダイジェストをd乗してそれを署名σとして出力します. 一方, 検証アルゴリズムVは, 文書と署名の組 (m, σ) を受け取って, 署名σをe乗したものがH(m)と一致するかどうかを確かめます. あっていたら検証に通ったものとして受理します. 一致していなかったら正しくない署名だと判断して, 拒否します.
これが高木さんの記事で挙げられている公開鍵暗号方式による署名は、メッセージダイジェストを秘密鍵で暗号化することで実現するにRSAが当てはまるということの説明です.

補足説明:

2008/03/05 00:30 追記
素因数pとqを記憶しておくと, 中国式剰余定理を用いて高速化が出来ます. そのため, 署名方式の署名鍵は(n,d)ではなく(p,q,d)のこともあります. また暗号の場合の復号鍵も同様です. ハードウェア実装等で暗号化チップと復号チップを共通化したいという場合には復号鍵は(n,d)のままで良いです (多分. 実装に詳しくないので実装の人にお任せ.)
という訳で, 復号鍵が(p,q,d)の場合があるので, 暗号化鍵を署名鍵に, 復号鍵を検証鍵にという説明はなるべくなら避けるべきだと思います. 鍵を単純に入れ替えたとすると, 復号鍵が(p,q,d)のときに検証鍵が(p,q,d)になります. この場合には, 検証鍵から署名鍵(n,e)を求めることが簡単になります.

さて, RSA暗号以外の暗号方式や署名方式はどうなんでしょうか?

ElGamal暗号方式と署名方式について.

RSA以外に有名な暗号化方式として, ElGamal暗号方式があります. またElGamal (人名) は同時に署名方式も提案しています. 署名方式の方はFIPS 186 - (DSS), Digital Signature Standardの元となっています. このDSSは広く使われています. 広く使われている署名方式なんですが, RSA暗号/署名とは違って単純に暗号をひっくり返しただけではできません. 暗号方式と署名方式では中身がかなり異なっています.

id:kyab ElGamalの説明。途中でDSS=DSAっぽく書かれちゃってる。

ご指摘ありがとうございます。
以下が正確な表現です。ElGamal暗号はDSAやECDSAと呼ばれる署名の元である。昔はDSS = DSAと考えてよかったが、FIPS186-2以降はRSA署名とECDSAが追加されたため、DSS = DSAではない。
ElGamal暗号方式

まずはElGamal暗号方式の鍵生成からです.

  • 鍵生成
    1. 大きな素数pを選ぶ.
    2. \(\mathbb{Z}_p^*\)を位数pの剰余環の単元からなる部分群とし, 生成元をgとする.
      1. 大雑把に言うと, \(g^{p-1} \bmod p = 1\)で, \(i=1,...,p-2\)については \(g^{i} \bmod p \neq 1\)となる \(1 < g < p-1\)です. p-1乗すると初めて1になる要素のこと.
    3. \(1 < x < p-1\) をランダムに選び, \(y = g^x \bmod p\)とする.
    4. 暗号化鍵は, p, g, y. 復号鍵は x.

これまた色々とややこしいですが, そういうものだと思ってください.
暗号化鍵(p, g, y)から復号鍵 x を求めることを離散対数問題と呼びます. これも難しいと信じられている問題です. なので, 暗号化鍵から復号鍵は探せないでしょう.

さて暗号化関数と復号関数を見てみましょう.

先ほどと違って暗号化関数への入力としてkが増えています. ElGamal暗号では暗号化の度にランダムなkを必要とします. また暗号文が\(c_1,c_2\)と二つあります.
中身を見てみましょう.

こうなってます.
暗号化関数の方は, 最初に\(c_1 = g^k \bmod p\)を計算します. 後に, \(c_2 = m \cdot y^k \bmod p\)を計算します.
復号関数の方では, 最初に\(c_1^x \bmod p\)を計算します. 後に, \(m = c_2 (c_1^x)^{-1} \bmod p\)を計算します.

関数の形で書くと以下になります.

  • \(E(y,m,k) = (g^k \bmod p, m \cdot y^k \bmod p)\)
  • \(D(x,c_1,c_2) = c_2 (c_1^x)^{-1} \bmod p\)

逆元を出さないために足し算にしていましたが, オリジナルは掛け算なのでオリジナルに合わせました.


暗号化の際には, \(y^k \bmod p\)で \(m\) をマスクしています. ということは復号の際には, \(y^k \bmod p\)が計算出来れば, mを\(c_2\)から取り出せそうです. しかし, k そのものを送ってしまうと, 盗聴者も簡単に m が取り出せてしまいます. そこで, \(c_1 = g^k \bmod p\)として k の情報を送ります. \(y^k \equiv (g^x)^k \equiv g^{xk} \bmod p\)という点を覚えておいてください.

復号の際には, \(c_1^x\) を計算して, \(c_2\)からmを取り出しています. \(c_1^x \equiv (g^k)^x \equiv g^{xk} \bmod p\) なので, 暗号化の際に使ったマスク情報と一致しています. なので, 正しくmが取り出せます.

(ちょっと知っている人向けの説明. DH鍵交換を思い出してください. Aliceが\(g^x\)をBobに送って, BobがAliceに\(g^k\)を送ります. すると二人は, \(g^{xk}\)を共有できます. 暗号化鍵の \(y = g^{x}\) と暗号文中の \(c_1 = g^{k}\) がDH鍵交換に対応します. 共有した鍵で \(m\) をマスクしているだけです.)

それでは署名方式に移りましょう. まずRSA暗号方式と同じように, 復号鍵で暗号化出来るでしょうか? 今回は暗号化関数と復号関数の形が違うため, 復号してから暗号化するという方法は上手くいきません. また復号鍵と暗号化鍵の形がRSAの場合とは違って対称では無いので復号鍵で暗号化して暗号化鍵で復号するというのもやっぱりダメです.

何故ダメか.

2008/03/05 00:30 追記

まず復号してから暗号化するという手法は関数の形が違うので無理です.
復号アルゴリズムDは, x, c1, c2を受け取って m を出力します. なので暗号化アルゴリズムはこの m を入力とするんですが, yはいいとして, kが足りません.
関数の形を思い出すと,

  • \(E(y,m,k) = (g^k \bmod p, m y^k \bmod p)\)
  • \(D(x,c_1,c_2) = c_2 (c_1^x)^{-1} \bmod p\)

です. 入出力の対応が取れていないことが良く分かります. なので復号してから暗号化するというのは上手くいきません.

次に復号鍵で暗号化して, 暗号化鍵で復号するということを考えます.
図で見ると以下のようになります.

暗号の方では暗号化鍵y, 復号鍵xについて

  • \(E(y,m,k) = (g^k \bmod p, m \cdot y^k \bmod p)\)
  • \(D(x,c_1,c_2) = c_2 (c_1^x)^{-1} \bmod p\)

でした.
復号鍵\(x\)は\(\{1,2,...,p-2\}\)のどれかなので数字です. よって, べき乗を取っても問題ありません. なので一見, xで暗号化すれば良さそうです. 復号鍵で暗号化, 暗号化鍵で復号とすると,

  • \(E(x,H(m),k) = (g^k \bmod p, m \cdot x^k \bmod p)\)
  • \(D(y,c_1,c_2) = c_2 (c_1^y)^{-1} mod p\)

となります.

暗号文がどうなるかを詳しく見てみます.
まず\(c_1 = g^k \bmod p\)でした.
暗号化鍵yの代わりに復号鍵xを使うので, \(c_2 = H(m) x^k \bmod p\) になります.

公開鍵で復号してみましょう.
復号では\(c_1\)を受け取るとそれを復号鍵のx乗していました. 復号鍵xの代わりに暗号化鍵yを使うとすると, \(c_1^y \bmod p\)を計算すればよいことになります. 元のメッセージを計算するためには, \(c_2 (c_1^y)^{-1}\)とするのでした.

さてこの\(c_2 \cdot (c_1^y)^{-1}\)はH(m)と一致するでしょうか? 真面目に計算していくと,
\(c_2 (c_1^y)^{-1} \equiv H(m) x^k ((g^k)^y)^{-1} \equiv H(m) (x g^y)^{-k} \pmod{p}\)
ということで, 元のメッセージダイジェストとは一致しません.
そもそも復号鍵で暗号化, 暗号化鍵で復号だと, 正しい署名者の署名も検証できないということが分かりました.

ElGamal署名

実際のElGamal署名は形式的には以下のようになっています.

中身は結構複雑です.

署名アルゴリズムでは, ランダムなkとH(m)を受け取ります.
まず\(r = g^k \bmod p\)とします. 次に, \(ks \equiv H(m) - rx \pmod{(p-1)}\) となるようなsを求めます. rとsが署名になります.
検証アルゴリズムでは, まずrとsが正しい範囲に入っているかどうかを確認します. 後に, \(g^{H(m)} \equiv y^r r^s \pmod p\)かどうかを確かめます.

もし正しい署名であれば, \(y^r r^s \equiv (g^x)^r (g^k)^s \equiv g^{ks+rx} \equiv g^{H(m)} \pmod p\) となって検証を通ります. 正しくない署名が検証を通らないことは各自計算してみてください.
署名鍵 x を知らない人は署名の検証を通るような, \(r = g^k\) と \(s\) を同時に選べないというのが気持ちです.

まとめ

RSA暗号は暗号化関数と復号関数が対称で, 鍵もある意味対称です.
けれどもElGamal暗号だと暗号化関数と復号関数が対称ではなく, また鍵も対称ではありません. 実際, ElGamal署名は, 秘密鍵で暗号化を行っているわけではありませんでした.

id:uruya 後で調べる / IDコールされた専門家が、まさに「非専門家の理解を意識せずに書いた文章」を書いていることに笑った。

IDコールされた専門家が俺. この説明だとどんなもんでしょか.