OthloBlog - オスロブログ -

名古屋のIT系学生コミュニティOthloTechのブログです。

【初心者向け】情報セキュリティで使われる現代暗号の分類

f:id:ozaki-physics:20180523131035j:plain

やっほー! こんにちはー!
OthloTechのオザキ(@sena0801masato)です。

今回は、

情報化社会で安全な通信ってどのようにしているの?
情報の勉強も暗号の勉強もしたことない!
どんな暗号技術が使われているか分類だけ知りたい!
数学は得意じゃない!

そんなあなたに暗号についてのまとめをお伝えしようと思います。
自分も始めて勉強する分野で、間違っている可能性は許してください(笑)

まず私が勉強し始めて分かったことは、暗号の分野は見方によって大きく2つに分かれるということです。 1つ目が情報、2つ目が数学です。
本気で勉強したいなら、数学の代数学を中心とする集合、群論、写像を学ぶ必要があると思います。
今回は数学的な部分には踏み込まず、まとめてみます。

用語の紹介

暗号を勉強するときによく出てくる単語を紹介しようと思います。

  • 平文:第三者に見られたくない元の文のこと。
  • 暗号文:平文を第三者が見ても意味が分からないように細工した文のこと。
  • 暗号化:平文を暗号文にすること。
  • 復号:暗号文を平文にすること。
    復号化と書かれることもあるが、正しくない。 ○○化と書きたいなら、暗号にするから暗号化、平文にするから平文化になる。(でも平文化は一般的に使われていない)
    「暗号化」の対語が「復号化」ではない理由の記事が参考になります。
  • 鍵:暗号文にするとき、平文にするときの細工(暗号化、復号)で使うもの。

暗号の分類

歴史的に分けると2つ、古典暗号と現代暗号があります。

古典暗号

過去に使われていた暗号たちのことです。換字式暗号と転字式暗号があります。

換字式暗号:文字が1対1(または1対多)の対応をしているもの。

シャーロックホームズの「踊る人形」、名探偵コナン12巻で阿笠博士の伯父(阿笠栗介)の別荘で使われていた暗号などです。具体的にはシーザー暗号があります。

  • シーザー暗号
    文字を任意の数ずらす暗号(「おやすみ」を2文字ずらすと「きよそめ」など)

転字式暗号:文字の順番を入れ替えるもの。

  • スキュタレー暗号
    棒にひもを巻き付けてひもの方向と違う方向に書く暗号(ひもの向きで読むと「おこおはんや...」)

スキュタレー暗号のイメージ図
スキュタレー暗号のイメージ図

古典暗号から機械式の暗号装置へ

エニグマ

古典暗号では人の手で暗号化と復号をしていて、変換方法そのものが秘密でないと見破られるため、限られた人しか暗号は使えませんでした。 そこでより多くの人が暗号を使えるようにと、第二次世界大戦中にドイツ軍が「エニグマ」という装置を開発しました。
(幸か不幸か戦争が技術を発展させた例ですね。)

エニグマは使う人によって装置内の電気回路をつなぎ変えられるようになっています。 電気回路のつなぎ方が鍵の意味合いを持ち、同じ装置を使う場合でも鍵によって違う暗号が作れるため、鍵をたくさん作れば多くの人が暗号を使えるようになりました。

チューリングマシン

チューリングマシンとは計算機を単純化した理想的な模型です。
機械式の暗号装置が開発されたことにより、解読は言語学から数学の分野に移っていきました。 ここで暗号装置や計算機を数学的に議論するため、チューリングマシンという概念が出てきました。

戦争中だったこともありポーランドやイギリスが、エニグマの作る暗号を解読しようとしました。 その暗号学校(解読しようとした機関)で働いていたのがチューリングマシンの概念を作ったアラン チューリングさんです。
チューリングさんは仲間たちとチューリングマシンの概念からコロッサスというコンピュータを開発しました。 そして見事に解読を成功させ、ノルマンディー上陸作戦を成功に導いたとされています。
(この頃から情報戦が重要になっていたのですね。)

現代暗号

現在使われている暗号たちのことです。共通鍵暗号と公開鍵暗号があります。

共通鍵暗号:暗号化に使う鍵と復号に使う鍵が同じもの。

例えると玄関の鍵みたいな感じです。
住んでる人全員が同じ鍵(共通鍵)を持っていれば家の中(平文)が見れます。 今回は2つ紹介します。

ストリーム暗号

bit、バイト、ワードごとに暗号化します。
(ワードとは自分のコンピュータが単位時間あたり一括して処理できるビット数のこと)
共通鍵は擬似乱数によって平文より長いデータにして使われます。

  • RC4
    ストリーム暗号の一種で、インターネットの暗号プロトコル(データ処理手順)にも使われています。
ワンタイムパッド

ストリーム暗号の基礎となった暗号に、ワンタイムパッドがあります。
ワンタイムパッドとは平文と共通鍵をbit(0と1の並び)で考えて、bitごとにXOR演算をします。
共通鍵に真の乱数を使うと、共通鍵の推測や平文を特定することがまったくできません。
ただし共通鍵のデータが平文より長くなってしまうため、利便性が悪く現在あまり使われていません。

記事の最後にもう少しワンタイムパッドの考察を書きました。
より詳しく知りたい方は【初心者向け】ストリーム暗号のワンタイムパッドの安全性を書きました。

ブロック暗号

ある一定の長さのデータ(64bitや128bit)ごとに暗号化します。
共通鍵は1つのまとまり(64bitや128bitなどブロック)として使われます。
このブロックのことを「暗号化するブロック」としてブロック暗号ということもあります。(分かりにくいことに、方式としてのブロック暗号とは違う意味です。)
平文がブロックの整数倍でないとき、足りないデータ分を補う処理をする必要があります。
また暗号化するときに暗号化モードという複数のパターンがありますが、今回は説明を省略させていただきます。

  • DES
    1977年にNBS(国立標準局、NISTの前身)によって米国標準暗号として採用されました。しかし今は非推奨です。ブロックの長さは64bitです。
  • AES
    2000年にNIST(アメリカ国立標準技術研究所)によって米国標準暗号として採用されました。2005年にDESからAESに移行が推奨されました。ブロックの長さは128, 192, 256bitに対応しています。 暗号化の方法がDESより複雑で、安全性の高いものになっています。

ストリーム暗号とブロック暗号の比較

  • ストリーム暗号のメリット
    共通鍵より擬似乱数を暗号化を始める前に作れるから、待ち時間が少ない
    暗号文のデータ量と平文のデータ量が同じで、ブロック暗号みたいに余計なデータを送信する必要がない

  • ストリーム暗号のデメリット
    ブロック暗号でストリーム暗号が再現できてしまう
    ブロック暗号ほど安全性の検証がされていない

  • ブロック暗号のメリット
    ストリーム暗号より安全性が高い
    ある暗号利用モードを使うとストリーム暗号と同じ働きをする

  • ブロック暗号のデメリット
    ブロック分のデータが揃うまで暗号化できない
    平文のデータ量がブロックサイズの整数倍でないとき、足りない分を補う処理をする必要がある
    ブロック暗号(秘密鍵)よりも平文の方が長いことが多いため、ブロック暗号を平文に対して繰り返し使うと、同じ暗号文ができることがある

公開鍵暗号:暗号化に使う鍵と復号に使う鍵が違うもの。

例えると南京錠みたいな感じです。
ロックできるひっかける方(公開鍵)はみんなに渡して、開ける鍵(秘密鍵)は自分だけが持ちます。だからロック(暗号文)は誰でもできるが、開ける(平文を読む)ことは自分しかできません。
今回は3つ紹介しますが、どれも数学的になるため詳しい説明を避けさせていただきます。
また、公開鍵暗号の秘密鍵を利用して電子署名という技術もあります。(電子署名の説明は省略させていただきます。)


余談
公開鍵暗号の問題は、その公開鍵が本当に送りたい相手の公開鍵か保証しないといけない点です。
そこで公開鍵と送りたい相手が合っていることを保証する機関を認証局といい、認証局が鍵証明書を発行してくれます。この仕組みをPKI(公開鍵暗号基盤)といいます。


RSA暗号

数学的に素因数分解問題が解けにくいことを利用した方式です。
大きい桁の素数と大きい桁の素数をかけ算して、大きい桁の数(2個の素数から構成される数)を求めるのは簡単だけど、
大きい桁の数(2個の素数から構成される数)を、大きい桁の素数と大きい桁の素数に分解するのは難しいことを利用しています。
メリットは、仕組みがシンプルなことです。
デメリットは、べき乗や余りの計算で処理が遅い、多くの素数を用意しなければならないなどあります。

数学的に知りたい人へ
RSA暗号の仕組みと安全性 | 高校数学の美しい物語
サルにも分かるRSA暗号
RSA 暗号がようやく分かった気がしたのでまとめてみる

エルガマル(ElGamal)暗号

数学的に離散対数問題が解けにくいことを利用した方式です。
ある数を大きな桁の素数でわり算したとき、余りが出てきます。その余りから元のある数が推測しにくいことを利用しています。
ディフィーヘルマン鍵交換を応用しています。

ディフィーヘルマン鍵交換(DH交換)

エルガマル暗号の基礎に、ディフィーヘルマン鍵交換という技術があります。
ディフィーヘルマン鍵交換とは事前に共通鍵の共有をしていないくても、安全でない通信を使って共通鍵の共有ができる手順のことです。

楕円曲線暗号

数学的に離散対数問題が解けにくいことを利用した方式です。
数学的にはエルガマル暗号と似ており、エルガマル暗号と同様に余りからのある数が推測しにくいことを利用しています。
メリットは、RSA暗号よりもデータ量が少ない鍵で安全性が保たれていることです。
デメリットは、処理が複雑なことです。
少ないデータで安全性が高いため、ICカードに利用されています。
他にも署名の一種としてECDSA(楕円曲線DSA)があります。 DSAとはNISTが決めたデジタル署名の基準のことです。 今後は楕円曲線暗号が使われるようになるため、ECDSAが主に使われるのではないかと思います。
またIDベース暗号、IDベース署名にも応用されています。

共通鍵暗号と公開鍵暗号の比較

  • 共通鍵暗号のメリット
    シンプルな処理の繰り返しだから、公開鍵暗号より処理が速い

  • 共通鍵暗号のデメリット
    事前に共通鍵の共有が必要

  • 公開鍵暗号のメリット
    共通鍵のように共有するものがない
    電子署名にも使える

  • 公開鍵暗号のデメリット
    べき乗計算など大変な演算が多く、共通鍵暗号より処理が遅い

ハイブリット暗号

ハイブリット暗号とは共通鍵暗号と公開鍵暗号を組み合わせて使う方式です。

  1. 送信者は任意の共通鍵を作成し、公開鍵を使って共通鍵を送信します。
  2. 受信者は秘密鍵を使って共通鍵を手に入れます。
  3. そのあと送信者は共通鍵で暗号化された暗号文を送信します。
  4. 受信者は共通鍵を使って復号します。

このハイブリット暗号のメリットは、2つあります。

  • 共通鍵を送信者が任意で作れる
  • 平文を共通鍵暗号で送受信できるため、公開鍵暗号より処理が速い

送信者が任意で作れる共通鍵をセッション鍵ともいいます。
セッション鍵のメリットは、使い捨てができるため安全性が高いことです。
一定時間ごとにセッション鍵を捨てて、またセッション鍵を公開鍵暗号で送ればいいからです。
実際には無線LANの暗号化に使われています。
参考にした記事:ハイブリッド暗号方式---共通鍵暗号と公開鍵暗号を組み合わせる

まとめ

勉強してみて分かったことは、暗号技術は奥が深すぎるという点でした。
数学的な部分を勉強しつつ公開鍵暗号についてもう一度取り組もうと思います。
これを読んでいただいて、少しでも勉強するきっかけになれば幸いです。
特に例に挙げた暗号のアルゴリズムを調べたり、暗号技術が使われている電子署名やIDベース暗号、ハッシュ関数などを勉強してみてはいかがでしょうか。
ではでは!


ワンタイムパッドの考察

  • なぜbitで考えるか?
    もしbitではなく文字の並びで考えると、文章を作っているのは人間のため、平文で使われている文字に偏りが出てしまいます。
    (統計的にアルファベットだとe,t,aがよく使われ、z,qがあまり使われません)
    だからbitで考えます。

  • 疑問に思ったこと
    平文の文字に偏りがあるから、それに基づいてbitに変換してもbitの並びを見たら、あるまとまりごとに同じ並びが出てきたり、偏りがあるのでは?と思いました。
    しかしbitにすると、どこからどこまでを1つのまとまりとして見るか分かりにくくなる、共通鍵にも何かしらの偏りがないと同じ並びが出てこないことに気づきました。
    よって共通鍵を作るときは、あるルール(擬似乱数など)によって作られるものではなく、完全な真の乱数を使う必要があると納得しました(笑)

  • なぜXOR演算を使うのか?
    XOR演算を使う利点は2つあります。
    1つ目は、平文に鍵を2回演算させると平文に戻るからです。
    2つ目は、暗号文の各bitで0と1になる確率が同じになるからです。
    (XNOR演算でもいいが回路の作りやすさからXOR演算を使っていると思います。)


参考文献

今井秀樹 『トコトンやさしい暗号の本』 2010/04/28第1刷  日刊工業新聞社

神永正博『現代暗号入門』 2017/10/20第1刷 講談社

中西透『現代暗号のしくみ』 2017/01/10第1刷 共立出版