公開鍵暗号と電子署名の基礎知識

[公開鍵暗号をプログラムで扱う方法のまとめ](http://qiita.com/kunichiko/items/7d4945d8b512ea1a3446)のシリーズを読むのに必要な、公開鍵暗号や電子署名についての基本的な知識を解説します。

# :warning:注意
本記事はなるべく技術的に正確かつ、平易な言葉で理解しやすい形で書くように努めておりますが、 **技術的に不正確な部分がある** とのご指摘も受けております。

現時点でこの記事を完璧な形に書き直すことはできないため、その点をご了承の上読んでいただければ幸いです。技術的に正確な情報をお求めの方は、RSAの仕様書や専門書など、信頼できる情報源をあたるようにしてください。特に、暗号を取り扱うシステムの設計や製造に携わる方はご注意ください。

# 用語
このエントリでは暗号化関係の用語を以下の意味で使っています。

|    英語    | 日本語      | 意味                               |
|-----------|------------|------------------------------------|
|plaintext  | 平文        | だれでも読むことのできる文章・データのこと|
|ciphertext | 暗号(暗号文) | 特定の鍵を持っている人しか読めない文章・データのこと|
|encryption | 暗号化      | 鍵を使って平文を暗号に変換すること               |
|decryption | 平文化      | 鍵を使って暗号を平文に変換すること               |
|cryptanalysis | 解読     | 鍵を使わずに暗号を平文に変換すること             |
|encode     | 符号化      | あるルールによって情報を別の形態に変換すること。広義には暗号化を含む   |
|decode     | 復号        | あるルールによって別の形態に変換された情報をもとの形に戻すこと。広義には平文化を含む |


とくに、英語の **decryption** を日本語でなんと呼ぶかは人によってまちまちです。 **復号** と呼んでいる人もいるのですが、復号は **decode** の訳語として使いたいので、このエントリでは **平文化** を使います。


# 公開鍵暗号とは
玄関の鍵は閉めるときも開けるときも同じ鍵を使います。金庫の鍵も普通はそうです。では **金庫に貴重品を詰めて送ってもらう時はどうでしょう?**

金庫を閉める鍵と開ける鍵が同じだと、金庫にものを詰めてもらう相手にその鍵を渡す必要があります。その鍵を郵送で送ろうとしたら、途中で誰かに見られて複製を作られてしまうかもしれません。大事なものを送るために鍵をかけようとしているのに、同じ労力をかけて鍵を受け渡さなければいけないとなると本末転倒です。

これは、暗号通信でも同じことが言えます。

そこで、暗号通信において **閉めることしかできない鍵** と **開けることしかできない鍵** のペアを使うことでこの問題を解決したのが公開鍵暗号です。閉めることしかできない鍵はいくらコピーを作られても問題ないので、普通郵便で相手に送れます。なんなら、鍵の型紙をばらまいたって良いです。その鍵を使って金庫を閉めて送ってもらうと、開けられるのは自分だけなので(開ける鍵は自分がしっかり保管しておくので)安全に機密情報を送ってもらうことができます。

この２つの鍵を **公開鍵** と **秘密鍵** と呼びます。

## 公開鍵と秘密鍵の特性
- 公開鍵
	- その名の通り、公開してみんなにばらまいても問題ありません(この鍵で作った暗号文は、秘密鍵でないと平文化できないため)
	- ただし、 **公開鍵** だからと言って安全なわけではありません
		- 対応する秘密鍵が誰かに盗み見られていた場合、その公開鍵は安全ではありません(使ってはいけません)
		- 誰のものかわからない公開鍵を使って暗号化してはいけません。知らない **第三者だけに読める暗号文** ができてしまいます。
- 秘密鍵
	- 秘密の鍵で、他人に見られてはいけません。大事に保管しおてく必要があります。
	- 秘密鍵が他人に見られてしまった場合
		- 捨てて新しい鍵ペアを作るしかありません。
		- 公開鍵で暗号化しても他人に見られてしまうかもしれません。速やかに公開鍵を破棄してもらう必要があります。
		- そのため、 **公開鍵は安全** と思って安易に使用するのはセキュリティ上問題があります


### 公開鍵の有効性確認
上記の通り、出処のよくわかからない公開鍵や、秘密鍵が暴露されている公開鍵をうっかり使ってしまうとセキュリティ上問題があります。そのため、 **公開鍵証明書** と **証明書失効リスト** を使って公開鍵の有効性を確認する方法があります。

- 公開鍵証明書 (Certificate)
	- 公開鍵の出どころを第三者が証明するものです
	- 公開鍵暗号の中で「証明書」といったらこれのことを指します
	- 証明書の中に公開鍵自体が埋め込まれているのが普通です
	- 証明書は、「公開鍵に第三者の電子署名をつけたもの(署名付き公開鍵)」とも言えます
	- 証明書には通常有効期限が設定されています(その日付を越えたら使用してはいけません)
- 公開鍵失効リスト (CRL, Certificate Revocation List)
	- 秘密鍵をうっかり公開してしまうなどして、無効になってしまった公開鍵の一覧が書かれたリストです
	- 公開鍵を使う前にCRL上にその鍵が載っていないかを調べることで、間違って無効な鍵を使ってしまうことを防ぐことができます
	
これらを使うことで公開鍵暗号はより信頼できるものになりますが、別の問題も起こります。例えば、CRLは信頼できるサーバから最新のものをオンラインで入手しなければ意味がありません。そのため、暗号化の前に必ずサーバアクセスが必要になり、処理が複雑になってしまいます。また、万が一CRLのサーバが乗っ取られてしまうと、本来有効な鍵をすべて使えなくすることができるため、暗号化が一切できなくなってしまいます。

このような問題があるため、CRLまでは使わずに済ませることも多いです。その場合、 **秘密鍵が漏れないように管理することは非常に重要** です。CRLに頼れない場合は有効期限の短い証明書を使い、定期的に交換するなどして信頼性を若干向上させる工夫もできますが、効果は限定的です。

## "RSA暗号"は公開鍵暗号の具体的な実装

上記公開鍵暗号を具体的な方法として実現したのが **RSA暗号** です。

RSAでは公開鍵と秘密鍵の２つの鍵を **素数の掛け算と素因数分解** の計算コストの差を利用して実現します。コンピュータは2つの整数の掛け算、A × B を計算するのは得意です。AとBが数百桁あったとしても、かなり短時間で計算できます。ところがその掛け算の結果 Cだけが手元にある場合に、それを素因数分解して元のAとBを特定するのは簡単でない場合があります。特に、AとBがどちらも桁の大きな異なる素数だった場合、AとBを見つけるのは非常に時間がかかります。この特徴を使って **秘密鍵から公開鍵を作るのは簡単だけど、公開鍵から秘密鍵を作るのは困難** という特徴をもった以下の２つの鍵（非対称鍵）を作ります。

- RSAの公開鍵
	- この鍵で暗号化したものを平文化するためには、秘密鍵が必要
	- A × B = C のうちの **C** だけが書かれている
	- 計算によって、Cから AとB を特定するのは困難(=公開鍵から秘密鍵は作れない)
	- 公開鍵から秘密鍵を作ることができないため、「閉めることしかできない鍵」となる
- RSAの秘密鍵
	- 公開鍵で暗号化したものを平文化することができる鍵
	- A × B = C のうちの **AとB** が書かれている
	- 計算によって、AとB から Cを求めるのは簡単(=秘密鍵から公開鍵を作れる)
	- 秘密鍵から公開鍵を作ることができるので、間接的には閉めることもできる

**【重要ポイント】RSAでは、秘密鍵だけ大事に保管しておけば、無くしてしまった公開鍵をあとから生成しなおすことができる**

なお、「A,B,Cを使ってどういう計算をすれば暗号文を作ったり平文化できるのか」というところはちょっと難しいので、ここでは省略させていただきます。詳しく知りたい方は、以下のサイトなどを参照してみてください。

- [サルにも分かるRSA暗号](http://www.maitou.gr.jp/rsa/rsa10.php)

# 電子署名とは (RSAの場合)

公開鍵暗号の説明で「公開鍵は閉めることしかできない鍵」と書きましたが、これは「その暗号を解くためには秘密鍵が必要だ」という意味です。

実は **RSAの公開鍵と秘密鍵は同じ構造をしているので、どちらの鍵をつかっても暗号化することができます**。その結果生成された暗号文は、その鍵自身では解くことができず、もう一方の鍵を使うと解くことができます。言葉では良くわからないので表にしてみます。

| あなた       |        | 相手         |
|-------------|--------|--------------|
| 秘密鍵で平文化  |<=暗号化=| 公開鍵で暗号化 |
| 秘密鍵で暗号化 |=暗号化=>| 公開鍵で平文化  |


ここで、

> なんだ! 非対称って言ってるけど対称じゃん! 単に暗号化と平文化に別の鍵がいるっていうだけなのね。

と思った方、それは **誤解** です。こういった誤解してしまうと **２つの鍵ができたけど、どっちを相手に渡すんだっけ？どっちみち片方の鍵がわからなければ平文化できないんだから、どっちでもいっか** というチョンボをやらかしてしまいます。

さきほど書いたように **RSAでは秘密鍵から公開鍵を作ることができる** ということを忘れてはいけません。上記勘違いをして、公開鍵のつもりで秘密鍵を相手に渡してしまった場合、確かに相手は手元の鍵で平文化できるのでうまく動いているように見えますが、実際にはその鍵は秘密鍵なので、それを手に入れた第三者は平文化用の鍵(公開鍵)を作れてしまい、 **安全性が担保されていません。**

じゃあ、秘密鍵で暗号化なんてできない方がいいんじゃないかと思いますよね？

実は **秘密鍵の暗号文は電子署名として利用出来る** のです。
:warning: この表現は技術的に正しい表現ではありません。表面的な理解のためにこのように書いていますが、より適切な表現を思いついたら修正します。

## 電子署名の具体例

たとえば、

> 今度の飲み会は参加します。by くにちこ

というメッセージが平文で(暗号化されずに)送られてきた時に、そのままではこのメッセージを書いたのが本当にくにちこさんなのか、それとも第三者が捏造したものなのかを区別することができません。それを区別できるようにするのが電子署名です。

RSAの電子署名は、 **秘密鍵による暗号文を作り出すことで実現** します。上記文章をくにちこさんの秘密鍵で暗号化すると、受け取った人はくにちこさんの公開鍵を使って平文化できます。くにちこさんの公開鍵は公開されているので誰でも読めますが、公開鍵で平文化できる暗号文を作れたということは、くにちこさんの秘密鍵を持っているということ、つまり **本人が書いた文章だということがわかります。**これが電子署名です。

:warning: 実際には暗号文を作っているわけではないのでこの表現は適切ではありません。あくまで「そういう雰囲気のことをやっている」とご理解ください。
:warning: また、後述するように「公開鍵で平文に戻せたのだから、秘密鍵を持っている人しかそれを作れなかったはずだ」というのも、常に成り立つわけではありません。


## RSA以外の電子署名

T.B.D.

## 暗号化できたのだから本人?
[暗号化と署名は対象じゃないよという話](http://www.machu.jp/diary/20080302.html)にあるように、「暗号化できたんだから秘密鍵を持っている本人だ」というのは必ずしも正しい説明ではありません。

例えば「100」を暗号化したら「ABC」になり、「100100」を暗号化すると「ABCABC」になるような単純な暗号化アルゴリズムを考えます。この時、第三者が暗号文の「ABC」を連結することで別の暗号を作り出すことができてしまいます。

これを悪用すると、たとえば請求書の金額の桁を増やすことができてしまいます。受け取った人は公開鍵で正しく平文化できるため、本人が作った請求書と見分けがつきません。

RSAではこのような問題がない(困難である)ことが確認されているため電子署名として使えるのです。


## 電子署名は元の文章の"ダイジェスト値"に対して行う
上記例では文章自体を秘密鍵で暗号化すると言いましたが、実際にはそうはせず、元の文章のダイジェスト値を計算した上で、そのダイジェスト値を秘密鍵で暗号化し、それを電子署名として相手に渡します。ダイジェスト値に変換することで、署名対象のデータを一定長にすることができ、以下のメリットが生まれます。

- 計算コスト抑制できる
	- RSAの非対称鍵を使った暗号化/平文化の計算は非常に時間がかかる(計算コストがかかる)ので、数ギガバイトもある動画ファイルをRSAの非対称鍵で暗号化/平文化するのは大変です
	- それに対し、ダイジェスト値の計算はコストが安いです
	- ダイジェスト値は元のデータの長さによらず一定(せいぜい数百バイト)であるが、改竄したデータのダイジェスト値を意図的に衝突させる(同じになるように調整する)のは難しいです
	- そのため、「ダイジェスト値を秘密鍵で暗号化したもの」を電子署名としてつかうことで、改竄検出率を大きく損なわずに計算コストを大幅に縮小できます
- 元の文章(データ)の配信方法に手を入れなくて済む
	- 署名はせいぜい数百バイトなので、データと別に署名を配布してもデータ転送量やストレージコストを圧迫しません
	- 署名とデータを分けて配布することもできるので、既存のダウンロードサイトで配布されているデータが改竄されていないかどうかを、別の経路から入手した署名で検証することができます


ダイジェスト値を計算するアルゴリズムには **MD5** や **SHA1** などが知られています。たとえば、上記文章のMD5ダイジェスト値は以下のように計算できます。

```
> echo -n "今度の飲み会は参加します。by くにちこ" | md5
98b06861e6f88e2da85c4e0cebfe9d6f
```

```
> echo -n "今度の飲み会は参加します。by くにちこ" | shasum
f928f6292324397b12627136991ae583a19cea61  -
```

出てきた16進数がそれぞれのダイジェスト値です。この値を秘密鍵で暗号化したものを電子署名として使い、元の文章に添付して相手に送ります。送られた相手は電子署名を公開鍵で平文化すると元の文章のダイジェスト値が得られるので、受け取った文章から手元で計算したダイジェスト値と一致するかどうかを調べます。

## 実際に使われている電子署名のフォーマット
なお、電子署名のファイル構造は [PKCS #1 (RFC 3447)](https://tools.ietf.org/html/rfc3447) などで仕様が定められています。この仕様に沿った電子署名は、 ```openssl dgst``` コマンドにダイジェストの種類と秘密鍵を指定して生成することができます。

```
> echo -n "今度の飲み会は参加します。by くにちこ" | openssl dgst -sha1 -sign private-key.pem | hexdump
0000000 c2 1f 73 6d 4f b5 fa 5a 9d 9d 02 e0 a3 fe 70 0c
0000010 93 ef f5 f1 3c 34 ec 5f e0 8d 21 58 6a 27 3a e1
0000020 b0 49 81 a8 15 d2 92 39 cc fe ce 2d 3f 9f 91 3d
0000030 68 cf 99 ce 91 04 2e 72 e7 e5 c5 71 55 29 87 7d
0000040 f5 e9 f0 c3 f5 6b af f4 be 8f f9 c4 34 bb 52 1c
0000050 51 8d cf c7 64 e0 84 d2 33 ed bb 80 4f 9a 3f 42
0000060 84 2e ef 41 e4 fc b4 04 51 5e 55 11 86 63 31 fc
0000070 a1 b7 6b 93 f7 e0 67 31 04 69 e4 2e 97 e6 5f a2
0000080
```

この署名がどのように作られているかについては[電子署名のファイルフォーマット](http://qiita.com/kunichiko/items/2e0a2bd35c8e9492ceb5)というエントリで解説していますので参考にしてください。

# まとめ

RSAの公開鍵暗号では、公開鍵と秘密鍵の鍵ペアを使って暗号化と電子署名ができることを解説しました。以下にその２つの操作をまとめておきます。

| あなたの操作  |        | 相手の操作    |使いどころ                           |
|-------------|--------|--------------|-----------------------------------|
| 秘密鍵で平文化  |<=暗号文=| 公開鍵で暗号化 |秘密の情報を暗号化して相手に送るために使う|
| ダイジェスト値を計算し<br>秘密鍵で暗号化 |=電子署名=>| 公開鍵で平文化し<br>文章のダイジェスト値と比較  |受け取った文章を作ったのが"あなた"であることを証明するために使う|



# 参考サイト

- [暗号化と署名は対称じゃないよという話](http://www.machu.jp/diary/20080302.html)