共通鍵暗号方式の歴史を紐解く

# この記事について
この投稿は[Fujitsu extended Advent Calendar 2018](https://qiita.com/advent-calendar/2018/fujitsu)の15日目の記事です。
なお、記事は全て個人の見解です。会社・組織を代表するものではありません。

みなさんは普段何気なく<b>"セキュリティ"</b>という言葉を聞くと思います。
"このシステムは安全なのか"とか"セキュリティ対策はどうなっているのか"とか・・・
このセキュリティを支えているのは暗号技術です
しかし普段どんな暗号技術が使われていて、どうやってデータを守っているかということはあまり意識しないと思います。
そこでこの記事では暗号技術の中でもとりわけ共通鍵暗号方式について、どういったものがあるか(あったか)を時代の流れとともに紹介していきます。
明日の役には立たないけれど知っておいてほしい暗号の話をできればなぁと思います。

# 共通鍵暗号方式とは
歴史を追っていく前に共通鍵暗号方式がどういうものか説明します。
共通鍵暗号方式はデータを暗号化する暗号化鍵と、暗号化したデータを元に戻す(※復号という)ときの鍵(復号鍵)が同じものを使う方式のことです。
例としてダイヤルロック錠を考えてみます。
暗号化鍵はロックするための番号になります。複合するためには暗号化した時の番号が必要でそれを知らない人はロックを解除できません。
これによって情報を安全に守れます。
ただし、この方式を使うには何らかの方法で暗号鍵(※ダイヤルロック錠のロックに使用した数字)を復号する人と共有しておかなければなりません。
共有の方法としていろいろありますが、インターネットを介する場合は一般的に[公開鍵暗号方式](https://ja.wikipedia.org/wiki/公開鍵暗号)が使われます。
この方式は暗号化する鍵と復号に使う鍵が別になります。
イメージとしては南京錠がわかりやすいかもしれません。
南京錠のロックする部分が暗号鍵で、これを配布して暗号化してもらいます。
復号には自分しかもっていない鍵の部分で復号します。
仮に配布している暗号鍵がもれたとしても、暗号化したデータをもとには戻せません。
![公開鍵暗号_イメージ.png](https://qiita-image-store.s3.amazonaws.com/0/152318/68ba5868-9960-06cc-f1f4-d4c447192934.png)

なお、この記事ではこちらに関しては詳しく解説しません。興味のある方はぜひ検索してみてください。

# 暗号技術の流れ
この記事では暗号史全体を以下の3区分に分けて説明したいと思います。

古代: 紀元前あたりに使われていたもの(手作業による暗号化)
近代: 戦争に使われる(どうやって暗号化するかといった暗号方式も秘密にする)
現代: 主にインターネット上で使われる(暗号化方式は公開、だれでも使える)

# 古代暗号
暗号は紀元前から使われてきました
主な用途は戦争です。
今も昔も戦争において情報は勝敗を左右する大切なものでした。

古代暗号の中で代表的な例としてシーザー暗号を紹介します。

## シーザー暗号
シーザー暗号は元の文章(平文)の各文字を辞書順にN個ずらすといったものです。復号にはN個もとにもどせばいいということになります。
例えばN=3、平文を"bag"とした場合、まず最初の文字"b"を辞書順(アルファベット順)に3つずらすので暗号文の最初の文字は"e"になります。次に"a", "g"を同様に3つずらすのでそれぞれ"d", "j"になります。そのためつなげると暗号文は"edj"になります。これで元の文字列がなにかわからなくなりました。復号では3つ元に戻すだけです。
![アドベントカレンダー_シーザー暗号.png](https://qiita-image-store.s3.amazonaws.com/0/152318/c82c598d-276f-2c9c-c493-0c23362b45fd.png)


シーザー暗号は、古代ローマの軍事的指導者ガイウス・ユリウス・カエサル(英語読みでシーザー)が使用したことからその名前が付きました。
そのシンプルさから非常に分かりやすいですが、現代の環境では安全に使用することはできません。

## シーザー暗号の解読
今でこそコンピュータを使えばシーザー暗号は簡単に解けますが、昔は人力だったため解くことは困難でした。
そこでどうやって解いていたかというと、言語学的に解いていました。
例えば、英語において、母音(a,eなど)は頻繁に出現するといったことや、特定のアルファベットのあとには必ず特定の母音がくるっといった言語的な性質を利用して解読のヒントを得ていったのです。
昔は暗号学者は数学者ではなく言語学者だったのです。

# 近代暗号
近代になり暗号はより進化しました。
これまで手作業で暗号が作成されていましたが、20世紀に入って機械式暗号機が登場してきました。
今回は有名なエニグマ暗号を紹介します

## エニグマ暗号
エニグマ暗号は第二次世界大戦中にドイツで使用された暗号です。
この暗号方式ではキーボードからの入力に対して内部で数枚の歯車や変換器を使って暗号文を作成します。
そして、使用する歯車や変換器の種類などが暗号化鍵になりました。(つまり、複数の歯車の候補があり、暗号化したマシンと同じ歯車を使用したマシンでないと復号できませんでした。)

#### 参考画像 from Wikipedia
![alt](https://upload.wikimedia.org/wikipedia/commons/thumb/3/3e/EnigmaMachineLabeled.jpg/330px-EnigmaMachineLabeled.jpg)

第二次世界大戦がはじまったときは難攻不落の暗号とまで呼ばれ、大戦におけるドイツ軍の初期の快進撃を支えました。
しかし、エニグマ暗号もやがて破られてしまい、ついにドイツは戦争に負けてしまいました。
当時難攻不落とも呼ばれたこのエニグマを解読したのが数学者アラン・チューリングです。
[チューリングマシン](https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3)の生みの親であるアラン・チューリングによってエニグマは解読されました。
チューリングは「定時の定型連絡」(午前6時に今日の天気予報を伝える)を突破口にエニグマを解読していきました。
ちなみに、解読に成功したことを公表してしまうとより難解な暗号方式を使用されてしまうので、エニグマ暗号が大戦中に解読に成功していたという事実は世界大戦が終わって20年以上たった1970年代になってからでした。
このあたりのエニグマ暗号やチューリングによる解読の物語は読み物としても非常に面白いのでぜひ参考文献も読んでみてください。

# 現代暗号
現代の暗号はより数学が使われるようになってきました。
インターネットというあらゆる人が共通で使えて、それでもって理論的に安全であることが求められるようになってきました。
利用例としては、インターネット上でクレジットカード情報をやり取りする際に使われたりします。
直接お金に絡むので、攻撃者は何としてでも攻撃しようします。
そのため、数学的にどんなに多数のマシンを持ってきても解くまでに何十万年もかかるという証明が欲しいのです。
実際には(特に共通鍵暗号の場合は)理論的な証明を与えることは難しいので、研究者が大真面目にテスト環境で攻撃してみて、小規模だったらどれくらいの時間で解けたっていうことを報告し合ったりしています。

現代暗号としてDESとAESについて説明したいと思います。

## DES
DESの正式名称は、`Data Encryption Standard`です。
DESという暗号があるのではなく、DESとしてアルゴリズムが公募されました。

DESの歴史は1970年代から始まります。
1972年、アメリカ政府はコンピュータセキュリティが重要であることを認識し、機密情報を暗号化するための標準規格を公募しました。
二度の公募を経て、IBMの案が採用され、安全性の評価などが行われたのち、1977年1月にアルゴリズムが公開されました。
インターネットの基礎であるTCP/IPが標準化されたのが1982年なので、それより前から統一的な規格で情報を守るという構想があったのです。
※なお、詳細は[Wikipedia](https://ja.wikipedia.org/wiki/Data_Encryption_Standard)を参照してください


DESの暗号化手順は以下のような感じです。
DESはブロック暗号の一つで、暗号化したいデータをブロック長(64bit)ごとに区切ってデータを暗号化していきます。
なお、最後のデータ長が64bitに満たない場合は決められた方法でパディングします。
パディングにも何種類かあり、[PKCS#5](https://tools.ietf.org/html/rfc2898)などの方式があります。

#### 手順
1. 暗号鍵から暗号に使用する別の鍵(48bit×16個)を準備
2. 暗号化したいデータを2進数化(0 or 1の列)
3. 先頭64bitを切り取って暗号化処理
4. 次の64bitを参照、3.に戻る(データの最後までループ)

#### 暗号化処理
詳しくは説明しませんが、概要は以下の感じです。
詳しく知りたい方は参考文献を見てください。

##### 参考 from https://www.hummingheads.co.jp/reports/series/ser01/110915.html
![alt](
https://www.hummingheads.co.jp/reports/images/series01_encryption_history_08_01_thamb.gif)

1970年代から採用されたDESですが、やがて破られてしまいます。
1994年に三菱の松井 充さんが線形解読法と呼ばれる攻撃法でDESの解読できることを示しました。
解読法こそ提案されましたが、アルゴリズム自体は実用上安全であるとされ、トリプルDESという形で使われていたりもします。
しかし、次第に新しい暗号方式が求められるようになりました。
DESの登場は暗号研究、特に暗号解読法の研究を活発化させる触媒の役割を果たしました。
NISTは後にDESについて次のように述べています。(参考: Wikipedia)
> DESは暗号アルゴリズムの非軍事的研究と開発を「ジャンプスタート」させたと言える。1970年代、暗号学者は軍隊や諜報機関以外にはほとんどおらず、暗号の学問的研究は限定的だった。今では多数の学者が暗号を研究し、数学関係の学科で暗号を教え、情報セキュリティ企業やコンサルタントが商売をしている。暗号解読者はDESアルゴリズムを解析することで経験を積んだ。暗号研究者ブルース・シュナイアーは「DESは暗号解読というフィールドを大いに活気付けた。今では研究すべきアルゴリズムのひとつだ」と述べている。1970年代から1980年代にかけて、暗号に関する多くの書籍がDESを扱っており、公開鍵暗号を比較する際の基準となっている。


## AES
AESはDESがやぶられたことで、新しい標準暗号としてアメリカ国立標準技術研究所(NIST)主導で公募されました。
AESの正式名称は`Advanced Encryption Standard`です。
そのため、DESと同じように正しい言い方としては、'AESとしてRijndaelのアルゴリズムが採用された'となります。
AESもブロック暗号でブロック長(AESは128bit)ごとに暗号化していきます。
全体の流れはDESと同じなので暗号化処理の部分の概要だけ以下に示します。

#### 暗号化処理

<img width="301" alt="tmp.png" src="https://qiita-image-store.s3.amazonaws.com/0/152318/04ad147f-95aa-2044-9fbf-9be783c496e4.png">


※各処理が何をしているかは数学なしで話せなかったので興味のある方は参考文献を調べてみてください。

今のところAESを効率よく解く方法は発見されておらず、2018年現在もAESは皆さんのデータを守るための標準な暗号方式として、陰で使用されています。


## 参考として
- AES命令
  - 今どきのIntelのCPUにはなんと組み込み命令としてAES命令というのが存在します。(https://ja.wikipedia.org/wiki/AES-NI)  
    ただこれを使えばそのままAESを実装できるというわけではなく、実装のためのヘルプをしてくれるというものです。  
    もし、実装を見てみたい方は私のGithub(https://github.com/sh-miyoshi/AES) を参考にしてください
- サイドチャネル攻撃
  - サイドチャネル攻撃とは正攻法以外の方法で解く方法の総称です。例えば、AESの場合、正攻法とは数学的に解く方法であったり、全パターンを試す方法だったりです。それに対して、それ以外の方法としては電磁波を解析するという方法があります。AESはスマホなどのデバイス上で暗号化処理をします。その際ハードウェア上に電気信号を送って暗号化処理をします。電気信号をやり取りする際には電磁波が発生するため、その電磁波を解析すれば直接AESを攻撃しなくても解けるのではないかという方法があったりします。まだまだ研究中の分野ですが、いつの日か実現されてしまう日が来るかもしれません。

# 最後に
暗号の世界はいたちごっこなのです。
どんなに素晴らしい暗号であろうとも計算機の進化や画期的な攻撃方法の発見によっていつかは破られてしまうのです。
現在安全とされている暗号も、例えば量子コンピュータの登場によって破られてしまうといわれています。(量子コンピュータについては下の参考文献を見てください)
そのため、絶えずセキュリティのアップデートは必要です
まちがっても古いサポート切れの製品(Windows XPなど)を絶対に使い続けたりしないでください
そして、保守とか定期的なメンテナンスにも力を入れてください

# 参考文献
- 全体
  - https://www.digicert.co.jp/welcome/pdf/wp_encryption_history.pdf
- シーザー暗号 
  - https://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%BC%E3%82%B6%E3%83%BC%E6%9A%97%E5%8F%B7
- エニグマ暗号
  - https://japan.cnet.com/article/35115908/
  - [https://reki.hatenablog.com/entry/2014/12/29/ナチスの暗号「エニグマ」はなぜ解読困難だった](https://reki.hatenablog.com/entry/2014/12/29/%E3%83%8A%E3%83%81%E3%82%B9%E3%81%AE%E6%9A%97%E5%8F%B7%E3%80%8C%E3%82%A8%E3%83%8B%E3%82%B0%E3%83%9E%E3%80%8D%E3%81%AF%E3%81%AA%E3%81%9C%E8%A7%A3%E8%AA%AD%E5%9B%B0%E9%9B%A3%E3%81%A0%E3%81%A3%E3%81%9F)
  - http://www.infonet.co.jp/ueyama/ip/episode/enigma_e.html
- 量子コンピュータと暗号解読
  - http://www.nttdata.com/jp/ja/insights/blog/20180611.html
- DES
  - https://ja.wikipedia.org/wiki/Data_Encryption_Standard
  - http://co-akuma.directorz.jp/blog/2012/05/des%E3%81%A8%E3%81%AF%EF%BC%9F/
  - https://www.hummingheads.co.jp/reports/series/ser01/110915.html
- AES
  - http://www.atmarkit.co.jp/ait/articles/1506/18/news019.html