プログラマのための公開鍵による暗号化と署名の話

初めに

公開鍵による暗号化と署名をプログラマ向け(?)に書いてみました。ちまたによくある暗号化と署名の話はインタフェースと実装がごちゃまぜになっていることが分かり、暗号化と署名の理解が進めば幸いです（と思って書いたけど、余計分からんといわれたらすんません）。登場する言語は架空ですが、多分容易に理解できると思います。

公開鍵による暗号化PKE

早速、公開鍵による暗号化(PKE : Public Key Encryption)を紹介します。登場するのは暗号化したいデータのクラスPlainText, 暗号文クラスCipherText, 秘密鍵クラスPrivateKeyと公開鍵クラスPublicKeyです。PKEは次の3個のインタフェースを提供しています。

abstract class PKE {
  abstract keyGenerator(): [PrivateKey, PublicKey];
  abstract encrypt(p : PublicKey, m : PlainText): CipherText;
  abstract decrypt(s : PrivteKey, c : CipherText): PlainText;
}

鍵生成

関数keyGenerator()は秘密鍵sと公開鍵pのペアを生成します。入力としてセキュリティパラメータなどのパラメータをとることはありますが、ここでは省略します。
keyGenerator()は乱数を使って鍵のペアを生成するので毎回異なる鍵を生成します。秘密鍵sは他人に見せてはいけませんが、公開鍵pは、pからsの情報は得られないため誰に見せても構いません。

暗号化

関数encrypt(p, m)は公開鍵pと平文mをとり、暗号文cを返します。公開鍵pは暗号化に使う鍵なので暗号（化）鍵ともいいます。安全なencryptは乱数を使って毎回異なる暗号文を生成し、秘密鍵sを知らない人は暗号文cから元の平文mの情報は何も得られません。

復号

関数decrypt(s, c)は秘密鍵sと暗号文cをとり、平文mを返します。decryptは復号失敗を返すことがある方式もありますが、ここでは簡単にするためいつでもPlainTextを返すことにします。

正当性

keyGenerator()で作られた公開鍵のペア(s, p)を使って平文mを暗号化して復号すると元の平文に戻ります。つまり

const [s, p] = PKE.keyGenerator();
assert(PKE.decrypt(s, PKE.encrypt(p, m)) === m);

assertの中は常にtrueです。

最低限の理解

公開鍵による暗号化PKEで理解すべきは上で紹介した3個のAPIとその性質だけです。どんな数学的背景を使ってこれらのAPIを実現しているのか、暗号文クラスCipherTextの形、APIの実装詳細などを知る必要はありません（利用者の視点で理解する）。理解したくなったら、それぞれの暗号化方式のドキュメントに挑戦すればよいのです（実装者の視点）。

インタフェースを越える説明に注意

PrivateKeyクラスとPublicKeyクラスは一般に同じとは限りません。また、もちろん平文クラスPlainTextと暗号文クラスCipherTextクラスも一般には異なります。「秘密鍵で暗号化」しようとしてもencryptにはPublicKeyとPlainTextのインスタンスしか渡せないので型エラーになります。「公開鍵で復号」も同様にエラー。
したがって、一般的なPKEの解説で「秘密鍵で暗号化」という文章が出てきたら、それは間違いか、意図せず何か個別の公開鍵暗号方式（恐らくRSA暗号）の話をしていることになります。標準的なブラウザアプリケーションを設計・実装しようとしているときに、断り無く一部の特別なブラウザ拡張の関数を使った実装をされたら困りますよね。
一般論の話をしているのか、個別の話をしているのか明確な切り分けとその理解が必要です。

署名

署名もPKEと同様3個のインタフェースを提供しています。登場人物は署名鍵クラスPrivateKey、検証鍵クラスPublicKey、署名Signature、任意のバイト列クラスUint8Array、trueかfalseを保持する二値クラスbooleanです。

abstract class SIGN {
  abstract keyGenerator(): [PrivateKey, PublicKey];
  abstract sign(s: PrivateKey, m : Uint8Array): Signature;
  abstract verify(p : PublicKey, m : Uint8Array, σ : Signature): boolean;
}

鍵生成

関数keyGenerator()は秘密鍵sと公開鍵pのペアを生成します。秘密鍵sは他人に見せてはいけません。署名するときに使うので署名鍵ともいいます。公開鍵pは署名の検証に使うので検証鍵ともいいます。PKEと同様pは誰に見せても構いません。
keyGenerator(), PrivateKey, PublicKeyはPKEと同じ名前ですが、こちらは署名用なので同じ型とは限りません。

署名と3種類の意味

関数sign(s, m)は署名鍵sと任意のバイト列mをとり、署名クラスSignatureのインスタンスσを返します。
インタフェースを与える抽象クラスSIGNとしての「署名(1)」と、署名するというメソッド名（sign : 動詞）の「署名(2)」、戻り値の型名（signature : 名詞）である「署名(3)」と異なる用途に全て「署名」という用語がついているため大変混乱しやすいです。ここは、そうなってしまってるので慣れるしかありません。

1. 署名(1) SIGN : 3個のインタフェースを持つ抽象クラス。
2. 署名(2) sign() : 署名(1)のメソッドの一つ。署名を生成する動作を表す。
3. 署名(3) Signature : 署名(2)の結果得られるデータ。

検証

関数verify(p, m, σ)は検証鍵pとバイト列mと署名σをとり、検証にパスすればtrue、そうでなければfalseを返します。

正当性

署名鍵を持つ人が作った署名はいつでも検証を通ります。つまり

const [s, p] = SIGN.keyGenerator();
assert(SIGN.verify(p, m, SIGN.sign(s, m)));

assertの中は常にtrueです。

偽造不可能性

攻撃者が、過去に署名者が署名したデータとその署名のペア($m_i$, $σ_i$)をいくら入手しても、そこから署名者が署名したことの無いデータm（$\neq m_i$ for all $i$）に対する検証を通るような署名σは作れないことが求められます。
逆に言えば、検証にパスしたσは署名者が作ったものと保証され、否認防止に使えます（署名鍵が漏洩しない限りは）。

最低限の理解とインタフェースを越える説明に注意その2

公開鍵による暗号化PKEと同様、署名は上記3個のメソッドと偽造不可能性などの性質の理解が重要です。中身がどうなっているかはブラックボックスで構わないのでPKEもハッシュ関数も不要です。個別の署名アルゴリズムの詳細を知りたくなったときに学べばよいのです。
一般的な署名(1)の解説をしているときに、PKEの、しかも非標準なメソッドを使って説明(e.g., 「ハッシュ値を秘密鍵で暗号化したもの」)していたら、それはやはりおかしいわけです。

署名の具体的なアルゴリズムとRSA署名の特殊性

ここまで抽象的な署名の話をしてきました。じゃあ、具体的にはどうなってるの?と思われた方は、たとえば

• 楕円曲線暗号のPythonによる実装その2（楕円曲線とECDSA）
• RSA署名を正しく理解する
• BLS署名の基本

などをごらんください。

なお最後に、この記事で何度か出てきた「秘密鍵で暗号化」について。

RSA暗号のコアでは、落とし戸つき一方向性関数$f(x, y) :=y^x \bmod{n}$ （記号の詳細は上記RSA署名を正しく理解する参照）を使って

• $\text{RSA-Enc}(e, m):=f(e, m)$ : $e$は公開鍵, $m$は平文
• $\text{RSA-Dec}(d, c):=f(d, c)$ : $d$は秘密鍵, $c$は暗号文
• $\text{RSA-Dec}(d, \text{RSA-Enc}(e, m)) = m$.

が使われます。そしてRSA暗号の極めて特殊な性質なのですが、RSA-EncとRSA-Decが同じ関数$f(x, y)$で表され、公開鍵と秘密鍵はどちらも1以上$n$未満の整数で同じ、平文クラスCipherText、暗号文クラスCipherText、署名対象の空間、署名値はどちらも0以上$n$未満の整数で同じなのです。署名の場合は$e$と$d$を入れ換えて(https://www.rfc-editor.org/rfc/rfc8017#section-5.2)

• $\text{RSA-SP}(d, m):=f(d, m)$ : SP = Signature Primitive(署名プリミティブ)
• $\text{RSA-VP}(e, c):=f(e, c)$ : VP = Verification Primitive(検証プリミティブ)
• $\text{RSA-VP}(e, \text{RSA-SP}(d, m)) = m$.

と書かれています。つまり形に着目すると次の2パターンに分類できます。

• 秘密鍵$d$を使う : RSA-SP($m^d \bmod{n}$), RSA-Dec($c^d \bmod{n}$)
• 公開鍵$e$を使う : RSA-VP($c^e \bmod{n}$), RSA-Enc($m^e \bmod{n}$)

あるいは

• $m$に対する操作 : RSA-SP($m^d \bmod{n}$), RSA-Enc($m^e \bmod{n}$)
• $c$に対する操作 : RSA-VP($c^e \bmod{n}$), RSA-Dec($c^d \bmod{n}$)

式の形は同じなので「RSA-SP」のことを秘密鍵を使うことを意識して「秘密鍵で$m$を復号」、あるいは$m$に対する操作であることを意識して 「$d$で$m$を暗号化」というのはありだと思います。（厳密には秘密鍵を使うバージョンは実装上、公開鍵のみのバージョンより最適な手法がとれるので違うといえば違うのですが、ここでは省略します）。「暗号化」や「復号」が嫌なら「操作」「変換」でも構いませんが、個人的には大差ないと思われ。
いずれにせよRSAの落とし戸つき一方向性関数の特殊な性質であることは注意してください。

まとめ

• 公開鍵による暗号化PKEと署名は3個の抽象的なメソッド（インタフェース）からなる。
• 一般論はインタフェースの言葉のみを使って説明し、個別の方式の特殊性（実装詳細）と切り分ける。