誤解が多いと言われる公開鍵暗号・デジタル署名とSSHを自分なりに説明してみる

# 経緯
研究室でLinuxサーバの管理をする機会があったので，SSHの仕組みなどをもう一度正確に理解しておこうと思い調べていたところ，以下の@angel_p_57さんの面白い記事を見つけました．
- [「電子署名=『秘密鍵で暗号化』」という良くある誤解の話](https://qiita.com/angel_p_57/items/d7ffb9ec13b4dde3357d#comment-fdc6e9024600c4625e59)
- [SSHのハイブリッド暗号に関する良くある誤解の話](https://qiita.com/angel_p_57/items/30a12a0d45457b5f76d5)

この記事では，SSHやSSL/TLSなどで用いられる「デジタル署名」の概念に対して，一般的な解説に誤解が多いことを指摘しています．自分の体感だと多くのサイトや記事での説明は，根本から間違っていることもあると思いますが，言葉の選び方の問題もかなり大きいと感じました．そこで自分なりに納得できる言葉でこの仕組みを説明し，合わせてSSHの内部構造についてもこの際に整理してみようと思います！

# この記事のスタンス
* 極限に理解がしやすく，本質的にもズレていない90点ぐらいの説明を目指します
    * 数学的構造の話はしない
    * 実装レベルや論文レベルまでの指摘が来るとどうかわからない（特にSSHあたり）
* デジタル署名や公開鍵暗号のニュアンスがふんわりわかってる前提で話します
* 個人的な自己満で書く

# 1. デジタル署名のおさらい
## 1-1. デジタル署名とその流れ
そもそも署名とは何でしょうか．

それは **「文書やデータが特定の者によって作成されたことを証明するための手段」** です．

このため，署名されたものは正当な方法で特定の人が署名を作成したことを誰かが検証してあげなければいけません．

では，まずは現実世界でどのように署名/検証が行なわれているのかを見てみます．

* 現実世界
現実世界では，印鑑のようなものがあります．以下の流れで署名と検証が行われます．
①書類$m$に印鑑を押して署名をする
②印鑑が押された書類・印鑑登録証明書・本人確認書類を検証者に見せる
③検証者は，署名者の必要書類と登録されている公的な情報と比較して正しさを確認
![qiita1.001.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3549959/037906a5-9540-41a9-8d26-b468f7d7751f.png)


対して，デジタル世界ではどのように署名/検証が行なわれているのでしょうか．
* デジタル世界
印鑑のようなものがないので，以下の流れで署名と検証が行われます．
①データ$m$に署名鍵を用いて，署名をする(sign)
②署名される前のデータ$m$と署名を検証者に送付
③検証者は，検証鍵で署名を解き，送られたデータ$m$と比較して正しさを確認(verify)
![qiita2.001.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3549959/8d2942ff-6326-48e5-bfcc-92b06d2e489a.png)



どちらも共通しているのは，署名の意味が **「文書やデータが特定の者によって作成されたことを証明するための手段」** であるので，署名を作成する側は唯一無二で，なおかつ作成したことを否定することができない必要がありますし，加えて，そのように正しく署名されたものは必ずその妥当性を証明できる（検証に成功する）という要件を満たさなければいけません．


## 1-2. デジタル署名に求められる要件
この性質から，デジタル署名に求められる要件は以下の2つです．
1. **偽造不可能性** 
    * どれだけ頑張ってもその署名鍵を知らなければ，妥当な署名を作成できない
2. **完全性**
    * その署名鍵で作成された署名は，必ず対になる検証鍵で検証ができる

これらを満たすような署名アルゴリズムをうまく作るわけですね．

## 1-3. デジタル署名における注意点
それは **「第3者に署名の使い回し（リプレイ攻撃）をされる」** ということです．

署名と署名鍵自体は普通に通信上で出回っているので．それを第3者がコピーして使い回して本人になりすますというのが原理上できてしまいます，

この問題の対策の一つとして，**「署名対象のデータにやりとりの際のリアルタイムの情報(現在のSessionIDなど)を署名対象データに含め，できるだけ同じ署名ができないように頑張る」** をします．そうすれば，検証者は現在署名を送付した人が実際に署名した人と一致していることが保証される可能性が高そうです．
<br>

※ここから自分の見解（間違っている可能性あり）
上記の対策は，あくまで別のセッションで使いまわしを防ぐための術であり，リアルタイムで接続を取られる場合は，全く意味がないと思っています．その対策で，httpsではデジタル証明書，sshなどでは公開鍵の事前登録や手動での確認があるのかと勝手に理解しています．

# 2. 公開鍵暗号とデジタル署名技術・暗号技術の関係
ここでは，一般的に「デジタル署名技術・暗号技術」を「公開鍵暗号」という言葉を用いて説明されていることが多いですが，その本質的な関係を説明したいと思います．

## 2-1. 出発点
  デジタル署名では，**署名を行う側が唯一**，**検証する側が複数**存在する前提がよくあります（例えば，あるサーバの署名を複数の利用者（クライアント）が検証するなど）．
   
ここで，署名鍵として秘密鍵，検証鍵として公開鍵を使う公開鍵暗号の考え方が出てくるわけです．つまり，**本人のみ**が署名を作れることと**複数人**が検証できるという公開鍵暗号の秘密鍵と公開鍵の逆の発想(**秘密鍵側から処理を施す**)をすることでうまくいくのではないかというのが公開鍵暗号をデジタル署名へ応用する出発点になります．

ちなみに，<ruby>逆の発想<rt>・・・・</rt></ruby>(秘密鍵側から処理を施す)というぐらいですから，公開鍵暗号というものは，「公開鍵で暗号，秘密鍵で復号するもの（公開鍵側から処理を施す）」という意味として捉えられる場合が多いですよね．

## 2-2. 公開鍵暗号という言葉の定義
そこで，そもそも公開鍵暗号の定義は２つあります
1. **公開鍵，秘密鍵が使用される技術(広義)**
2. **公開鍵で暗号，秘密鍵で復号(狭義)**

## 2-3. 公開鍵暗号のアルゴリズムの分類
定義1をもっと厳密に言うと，**「公開鍵から秘密鍵を求めるのはものすごく厳しいという数学的背景をもつ，公開鍵と秘密鍵の関係が使用される技術」** です．

このような数学的背景を持つ色んな数学的手法を用いた公開鍵暗号のアルゴリズムがあるわけですが，これらのアルゴリズムは **「操作の順序と可逆性」** という観点から以下の4パターンに分類できると思っています．
1. **秘密鍵 ⇒ 公開鍵の順でデータがもとに戻る**（署名向け：DSA/ECDSA）
1. **公開鍵 ⇒ 秘密鍵の順でデータがもとに戻る**（暗号化向け：ElGamal）
1. **両方対応可能** (RSA)
1. **その他**（分類対象にならないもの）

デジタル署名も暗号・復号も，**一方の鍵で処理をした後のデータにもう一方の鍵で処理をすると元のデータに戻らなければいけない**という性質は同じなので，公開鍵暗号のアルゴリズムのうち，1を満たす公開鍵暗号のアルゴリズム(DSA/ECDSA)がデジタル署名技術として使用され．2を満たす公開鍵暗号のアルゴリズム(ElGamal)が暗号・復号技術として使用され，3を満たすもの(RSA)は両方に適用可能というわけです．

※なお，公開鍵暗号の応用例として**鍵交換**もありますが，「共通鍵の安全な共有」が目的で，上記の分類とは少し違った視点なので，その他というパターンを設けています．

# 3. よくある説明の間違いの指摘
デジタル署名技術，暗号・復号技術と公開鍵暗号の関わりがわかったところで，
よくあるサイトや記事上のデジタル署名の説明を見てみます．

**「秘密鍵で暗号化して，公開鍵で復号しているので，．．．公開鍵暗号はデジタル署名の応用になっている」**

この説明の間違いは2つあります．
1. **デジタル署名の目的が暗号ではない**
[デジタル署名の要件](##1-1.デジタル署名に求められる要件)にもありますが，そもそもデジタル署名が，データを当事者間でしかわからないようにするという意味での暗号・復号を目的としていません．なので，デジタル署名の説明自体にそれらの意味を持つ暗号・復号という言葉が含まれる時点で説明として，良くないと言えます．個人的には，「秘密鍵を使用してデータを変換する」ぐらい説明が適切だと思います．
2. **逆からの操作が常に成り立つとは限らない**
この説明の中での公開鍵暗号は，定義2の前提で話されているようで，そのバイアスにかかっているからか逆からの操作（秘密鍵側から処理を施す）をしてもデータがもとに戻るという[公開鍵暗号のアルゴリズムの分類](##2-3.公開鍵暗号のアルゴリズムの分類)でも話した，両方適用可能な場合(RSAなど)を前提に話しているのが間違いです．あくまで逆からの操作も成り立つのは，公開鍵暗号のアルゴリズムの一部になるので，公開鍵暗号のアルゴリズムのすべてを指して説明するような表現はよくないと言えます．

**したがって，デジタル署名を説明する際には，暗号・復号という言葉自体を持ち出すこと自体がナンセンスなので，公開鍵暗号という言葉を使って説明するなら，定義1（広義）で説明するぐらいが間違いを生まず，ちょうどいいと言えます．** 

# 4. SSHの仕組み
ということで，おまけみたいな感じでSSHの説明もします．
内部構造は以下の図で，大まかな流れは以下の3段階です．
1. 鍵交換とサーバー認証フェーズ
2. ユーザ認証フェーズ
3. 暗号化通信フェーズ（実際にリモートアクセスでコマンド打つ段階）

![qiita4.001.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3549959/5f2d1a69-4f0b-4ea5-9b17-ff9c49ba930e.png)
![qiita4.002.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3549959/5641fe6d-f1a4-4f2f-96bc-07bded5beb68.png)
## 4-1. 鍵交換とサーバー認証フェーズ
ここでの目的は，２つです．
1. 暗号化通信のための共通鍵をお互いに生成する
2. サーバーの認証をする

これらを同時に行います．

### 目的1. 暗号化通信のための共通鍵をお互いに生成する
後に，共通鍵を用いた暗号化通信を行うため，共通鍵をお互いで生成しないといけません．
暗号化のための鍵を直接やり取りすると盗聴のおそれがあるため，SSHでは，第三者に知られずに共通鍵を安全に共有できるDiffie-Hellman鍵交換というアルゴリズム（公開鍵暗号のアルゴリズムの一種）を使って，共通鍵の生成を行っています．

 **Diffie-Hellman鍵交換の手順** 
 ※g,pは，アルゴリズム決定時に共有されます．
1. クライアント，サーバそれぞれで秘密鍵$x, y$を生成する
2. お互いに秘密鍵から，公開鍵$A, B$を生成
    - クライアント : $A = func(g, x, p)$
    - サーバー : $B = func(g, y, p)$
3. お互いの公開鍵を送り合う
4. 相手の公開鍵と自分の秘密鍵を使って共通の値（図では共有秘密$K'$）を作る
    - クライアント : $K' = func(B, x, p)$
    - サーバー : $K' = func(A, y, p)$

Diffie-Hellmanの凄い所は，**「秘密$x,y$を送らずに、同じ秘密$K'$を共有できること」** です．
もちろん，第三者は公開鍵$A, B$だけがわかったところで，秘密鍵$x, y$もわからないし，$K'$もわからないので，送り合った者だけが同じ値$K'$を計算できるという凄い数学的背景が基盤となっているわけです．


### 目的2. サーバーの認証をする
図に書いている⑥〜⑪が全てになります．

ここでは，署名対象のハッシュデータとしてリアルタイム情報である「付加情報」や「共有秘密」の値を含めることによって，署名者と送信者が同一であることの信頼性を担保しています．

また，ハッシュ値自体は送信せず，検証者側（クライアント）で構築できます．
## 4-2.  ユーザ認証フェーズ
サーバーの認証とほぼ同じ感じで，図に書いている⑬〜⑯が全てになります．

ここでも，署名対象のハッシュデータとしてリアルタイム情報である「SessionID」などを含めることによって，署名者と送信者が同一であることの保証をしています．

こちらも，ハッシュ値自体は送信せず，検証者側（サーバー）で構築できます．

# 5. 終わりに
調べていくうちに，表現って大事だなと思いました．．．．


# 6. 参考文献
- [「電子署名=『秘密鍵で暗号化』」という良くある誤解の話](https://qiita.com/angel_p_57/items/d7ffb9ec13b4dde3357d#comment-fdc6e9024600c4625e59)
- [SSHのハイブリッド暗号に関する良くある誤解の話](https://qiita.com/angel_p_57/items/30a12a0d45457b5f76d5)
- [電子署名入門](https://lab.iisec.ac.jp/~arita/pdf/lecture2.pdf)
- [電子署名の基礎知識](https://qiita.com/angel_p_57/items/437ca6235defc938b97d)
- [やはり俺の情報教科書はまちがっている。](https://qiita.com/nodai2h_ITC/items/6c7b7ad029adf17da5f0)
- [RFC 4253 - The Secure Shell (SSH) Transport Layer Protocol 日本語訳](https://tex2e.github.io/rfc-translater/html/rfc4253.html)