暗号通貨という名前からも暗号技術に関してのある程度の知識の習得は避けては通れない。ということで詳細なアルゴリズムは置いておいて、イメージを中心に解説していこうと思います!

まず、暗号技術とは何か。ずばり一言で言うなら「圧縮」技術です。「ん??」って感じですよね(笑)  徐々になるほど、となってもらえると嬉しいです。

 まず以後の例で登場する人物の役割を決めておきます。

アリス(一般人)、ボブ(一般人)、イブ(盗聴者)、マロリー(攻撃者)、トレント(信頼できる第三者)、ヴィクター(検証者) の6人です。これらは暗号技術の説明によく使われる登場人物名です。

図1

例の状況としてはアリスからボブにメッセージ(メールなど)がインターネットを経由して送られる状況を考えてほしい。いたってシンプルな状況だが、暗号技術を使わなければ、ボブにメッセージは無事に届くもイブがメッセージの内容を読んだり、マロリーが通信の阻害やメッセージの偽造をしたりする。

図2

図3

暗号技術が提供する性質は「機密性・正真性・認証・否認不可能生」などがあります。

・機密性:これは一般に暗号と聞いて最初に連想するもので、メッセージを意図していない第三者に読まれることの無いように守るというものです。この性質を提供する技術としては対称暗号・公開鍵暗号・ハイブリッド暗号システムなどがあります。

・正真性:これはメッセージを受け取ったのは良いが、果たしてそのメッセージは送信者が送った本物のメッセージで改竄されていないか、という問題に関わっています。正真性を提供する技術としては一方向ハッシュ関数があります。

・認証:正真性の問題と同じようなものとして、メッセージが期待している相手から届いたものなのかどうか、を確かめる必要があります。これにはメッセージ認証コードが「認証」という性質を提供してくれます。ちなみにメッセージ認証コードは認証だけでなく、先ほどの正真性も提供してくれます。

・否認不可能生:改竄となりすましについては、ハッシュ関数、メッセージ認証コードで解決できるが、他にもこういった問題が生じうる。アリスがボブに「100万円支払う」というメッセージを送って、ボブがそのメッセージを受け取る。しかし、アリスがしらばっくれて、「そんなメッセージ送っていない」と主張する。これは否認と呼ばれる問題です。これに「否認不可能性」という性質を提供し、かつ、改竄・なりすまし・否認の3つを防ぐ技術が「デジタル署名」であり、公開鍵暗号に並んで重要な暗号技術です。

鍵の生成に関しては乱数が重要になってきます。その乱数を生成するアルゴリズムが「擬似乱数生成器」です。

以上、対称暗号・公開鍵暗号・一方向ハッシュ関数・メッセージ認証コード・デジタル署名・擬似乱数生成器の6つの技術は暗号学の重要なツールです。

図4

これまでに述べた暗号技術はメッセージの内容を読めないようにするもので、英語でクリプトグラフィ(cryptography)といいます。一方でメッセージを読めないようにするのではなく、メッセージの存在そのものを隠してしまう技術もあり、それをステガノグラフィ(steganography)といいます。この技術はおそらく読者の皆さんも使ったことがあるかもしれません。小学生の頃に作文に縦読みを紛れ込ませたこととかないですか?まさにそれがステガノグラフィです。最近では電子透かしといった技術も使われています。当然、埋め込み方に気付かれてしまうとメッセージはすぐに読み解かれてしまいます。なのでステガノグラフィはクリプトグラフィを代替する技術ではありません。しかし、暗号とステガノグラフィを組み合わせて使うことでセキュリティはより強固なものになります。暗号がそもそもメッセージ内容を読めなくしているので、組み合わせたとしてもステガノグラフィの効果はそれほど無いのでは?と思うかもしれないが、ここでポイントとなるのが最初に述べた「暗号が圧縮技術である」ということです。

ここから6つの技術に関して詳細なアルゴリズムは別の記事で書く(かも?)として、一つずつ大まかに説明していきます。

スポンサーリンク

・対称暗号

図5図6

対称暗号の大枠のアルゴリズムはシンプルです。ある鍵を使って平文を暗号化し、その暗号文を相手に送って、同じ鍵で復号化してメッセージを読んでもらう。家の戸締まりをイメージしてもらうと良いでしょう。玄関を閉めた鍵が無いと、帰ってきたときに玄関を開けて家に入ることが出来ませんよね。さて、ここで「暗号は圧縮技術」という言葉を思い出してください。家の玄関の鍵を閉めることで、「家を直接守って侵入者が入ってくるのを防ぐ」問題を「ドアの鍵を盗まれないようにする」という問題に置き換えることが出来ました。対称暗号では「メッセージを盗聴・改竄されないように守る」という問題が、対称暗号技術によって「鍵を盗まれないように受信者と共有する」という問題に置き換わりました。つまり、守るべき対称が「メッセージ」から「鍵」へと小さいものに変化した、圧縮されたということなのです。

対称暗号のイメージが少し浮かんだと思いますので、これからビット列の操作とXORという計算操作に関して説明していきます。

現代の暗号で使われているデータ量はとても多く、暗号アルゴリズムも複雑なため、コンピュータによる暗号化・復号化が必須です。コンピュータの操作対象は「こんにちは」のような文字列ではなく、0と1が並んだビット列です。画像や音声、動画なんかもビット列として表現されます。暗号ではビット列としての平文を暗号化して、ビット列の暗号文を作成します。

文字をビット列に変換する操作を符号化(暗号化ではない)といいます。例えば”hello”という文字列は次のようにビット列に変換できます。このルールをASCII(アスキー)といいます。

h → 01101000

e → 01100101 

l  → 01101100

l  → 01101100

o → 01101111

これを並べた hello → 01101000 01100101 01101100 01101100 01101111 に暗号化をします。

次はXOR(exclusive or)という計算についてです。日本語では排他的論理和と言います。1ビットのXORは次のようです。

 0  XOR  0 = 0

 0  XOR  1 = 1

 1  XOR  0 = 1

 1  XOR  1 = 0

簡単ですよね?同じ数字同士のXORは0でその他は1というだけです。XORは⊕とも表します。このXORがなぜ暗号で使われるかというと、次のようなXORをみてみると良いでしょう。

 0 ⊕ 0 ⊕ 0 = 0

 0 ⊕ 1 ⊕ 1 = 0

 1 ⊕ 0 ⊕ 0 = 1

 1 ⊕ 1 ⊕ 1 = 1

気づいただろうか?つまり、同じ演算を二回繰り返すとインプットとアウトプットが等しくなってます。このXORの演算のイメージをそのままそっくり暗号化・復号化の流れに当てはめたのが対称暗号です。

図7

シンプルですよね。ただ対称暗号でセキュリティ万全という訳ではなく、問題が残っています。それが「鍵配送問題」です。鍵を使って暗号化されたメッセージは、鍵が盗まれない限りほとんど安全ですが、一方ボブにメッセージを読んでもらうには鍵を渡す必要があります。じゃあこの鍵を守るために、鍵を暗号化して・・・という無限ループに陥ってしまいますね(笑)対称暗号は守るべきものをメッセージから鍵へと小さくすることで、守りやすくできたというのがポイントです。

スポンサーリンク

・公開鍵暗号

先ほど説明した対称暗号では「鍵配送問題」というのが残ってしまった。この問題への解決策として(1)鍵の事前共有(2)鍵配布センター(3)Diffie-Hellman鍵交換(4)公開鍵暗号 といった解決策があります。今回は公開鍵暗号について説明していきます。

公開鍵暗号は1976年のDiffie-Hellman鍵交換の論文をきっかけに研究開発が進みました。簡単にどのようにして鍵配送問題を解決したかというと、ずばり「配送しない」という方法で解決しました。もちろん、「もう暗号技術は使いません」とかではなくて、暗号化の鍵と復号化の鍵をペアではあるものの別のものとすることで解決しました。暗号化の鍵を「公開鍵」、復号化の鍵を「プライベート鍵」と呼びます。詳しいアルゴリズムはまた別に説明するとして、具体例を用いて、この解決方法が可能なんだなということをイメージしてもらいます。

図8

駅などにあるロッカーを想像してもらうと良いでしょう。実際のロッカーの鍵の閉め方とは少々異なるが、あなたのロッカーはJR渋谷駅の改札前の10番ロッカーだとする。あなたは10番ロッカーの鍵を持っていて、その鍵は閉められたロッカーを開くためのものとする。そして、友人に10番ロッカーがあなたのロッカーだと教えておくと、友人はロッカーに荷物を入れて100円玉を投入してロッカーに鍵をかけるとする。後日、あなたがロッカーに行って持っている鍵を使って開けると友人からの荷物を受け取れる、という流れです。ここでいう100円玉が「公開鍵」で10番ロッカーの鍵が「プライベート鍵」です。あなたのロッカーがどれかをみんなに知らせておけば、誰でもあなた宛に暗号化したメッセージを送れますね。しかし、それを復号化できるのはプライベート鍵を持っているあなただけなのです。

RSA暗号という公開鍵暗号アルゴリズムが現在最も普及しています。RSA暗号の安全性の根拠となっているのが「素因数分解を高速にするアルゴリズムが、現在まで発見されていない」ということに依っています。もし仮に素因数分解を高速に効率的に行えるアルゴリズムが発見されると、公開鍵からプライベート鍵を求められてしまうのです。ただこれまでに発見もされておらず、そういう方法が存在するかもわかりません。蛇足な話ですが、数学上の未解決問題「リーマン予想」が証明されると世界中のセキュリティが危険に侵されるというような噂があったりしましたが、そんなことは全くなく、RSA暗号の安全性への影響はありません。リーマン予想はこれまで全くでたらめだと思っていた素数をゼータ関数というものを通じて性質をとらえよう、というもので、もしかすると素数判定の高速アルゴリズムには寄与する可能性はあるものの、それ自体では十分に高速な素因数分解アルゴリズムにはなりません。もっとも、リーマン予想自体が素因数分解アルゴリズムの基になることも無いでしょう。そもそもリーマン予想が証明されたとしてもリーマン定理になるだけで結果自体は変わらないので、現時点で公開鍵暗号に決定的な攻撃がなされていない以上、解かれても何も変わらないでしょう。みなさんが中学生の頃に習った素因数分解に謎がまだまだ秘められていることが世界中のセキュリティを守っている、というはなんだかおもしろくないですか?

– man in the middle攻撃

公開鍵からペアとなっているプライベート鍵を求めるという効果的な攻撃はないものの、他の攻撃方法が公開鍵暗号には存在します。それが「man in the middle攻撃」です。これは名前の通り攻撃者マロリーが送信者アリスと受信者ボブの間に入って、アリスにはボブように、ボブにはアリスのようになりすます攻撃です。言葉で説明すると長くなりそうなので下の図を参考にしてください。

図9

せっかく鍵配送問題を解決したのにまた別の問題が生じてしまいました。man in the middle攻撃を防ぐには、入手した公開鍵が本当にボブのものだという「認証」の性質を提供してくれる暗号技術が必要になってきます。

スポンサーリンク

・一方向ハッシュ関数

一方向ハッシュ関数はメッセージが期待しているメッセージと本当に同じかどうか、改竄されていないかと危険性があるため、正真性のチェックに使われる暗号技術でした。例えば、会議でのプレゼン用の資料を前日に完成させたとします。印刷は会議当日に行おうと考え、帰宅しました。次の日、会社に来て印刷しようとする前に、ふと「もしかしたら誰かに内容を書き換えられたりしてないかな」と思いました。単純に下の図のようにすればいいのでは?と思うかもしれません。

図10

ただこれはナンセンスな方法で、元のファイルのコピーを安全な場所に保存できるなら、オリジナルのファイルをそこに保存しておけばいいだけです。さらにファイルが大きければ大きいほど”昨日のファイルのコピー”と”今日のファイル”の比較作業は大変になります。そこで一方向ハッシュ関数を使って下のように正真性の確認をします。

図11

ここでも「暗号技術は圧縮技術」を思い出してください。ファイルをハッシュ値という小さなデータに圧縮して、それを守っているのです。

一方向ハッシュ関数では、インプットとアウトプットが一つずつあります。インプットがメッセージでアウトプットがハッシュ値です。ハッシュ値の大きさは同じハッシュ関数を使用する限り、インプットのメッセージが大きかろうと小さかろうと、同じ大きさで出力されます。インプットに依らず、同じ大きさのハッシュ値を出力するという性質に加えて、もう一つの性質があります。それが「一方向性」です。これはメッセージからハッシュ値は計算できるが、ハッシュ値からメッセージを逆算することはできない、という性質です。

図12

実はこの性質があるため攻撃者にハッシュ値を知られても問題ありません。ハッシュ値は通常メッセージよりも小さいため、理論的には同じハッシュ値を持つメッセージは複数存在し得ます。しかし、攻撃者がオリジナルメッセージのハッシュ値を知ったからといって、それと同じハッシュ値を持つ別のメッセージを見つけ出すことは現実には限りなく不可能に近いです。

一方向ハッシュ関数を使ってる身近な例として、ユーザー登録の際のパスワードです。ユーザーがパスワードを入力すると、そのハッシュ値が会社のデータベースに保存されます。以降、ログイン時にはハッシュ値からパスワードの正真性を確認して、登録されてるハッシュ値と等しければログインできます。なので会社にはパスワードの平文は保存されていないため、それを悪用されることはありません。ごく稀にユーザー登録後にメールにて「あなたのパスワード:abcdefg です。」とパスワードを平文で送ってくる企業がありますが、おそらくその企業はセキュリティリテラシーが欠如しているので気をつけた方がいいでしょう。

一方向ハッシュ関数ではメッセージが異なればハッシュ値も異なります。ただハッシュ値はメッセージに対して小さなデータであるため、2つの異なるメッセージが同じハッシュ値を持つことがあります。それを「衝突」と言います。一方向ハッシュ関数を暗号技術で用いるためには衝突について次の2つの衝突耐性を備えている必要があります。

一つは、あるメッセージのハッシュ値が与えられたときにそのハッシュ値を持つ別のメッセージを見つけ出すことが非常に困難である、という「弱衝突耐性」です。2つ目は、ハッシュ値が一致するような異なる2つのメッセージを見つけ出すことが非常に困難である、という「強衝突耐性」です。一度読んだだけでは「何が違うの?」という印象だと思います。一方向ハッシュ関数に対する具体的な攻撃を交えて違いを説明していきます。

– ブルート・フォース・アタック

アリスがボブに「一万円支払う」という契約書を作成し、コンピュータに保存しています。攻撃者マロリーはアリスにもボブにもばれないように契約書の内容を「一億円支払う」に書き換えようとします。ただアリスは元の契約書のハッシュ値を作成して正真性の確認をします。なのでマロリーはハッシュ値を変えないようにメッセージを変えないといけません。例えば「一億円支払う」というメッセージの末尾に空白文字を一個ずつ追加していって元の契約書のハッシュ値と同じになるまでひたすら続けます。これが「弱衝突耐性」を破ろうするブルート・フォース・アタックです。

– 誕生日攻撃

もう一つの衝突耐性の「強衝突耐性」を破ろうとする攻撃が誕生日攻撃です。この場合、契約書を作るのは攻撃者マロリーです。マロリーはあらかじめ同じハッシュ値をもつ2つの契約書「給料一万円」と「給料百万円」を作っておきます。そしてアリスに百万円の契約書を渡して、ハッシュ値を計算させ、後にこっそりと一万円の契約書にすり替えるという攻撃です。

「誕生日攻撃」の名前の由来は「N人のうち少なくとも2人の誕生日が一致する確率が50%以上になるとき、最も小さいNはいくつか?」という問題の答えが直感より大きく、N=23だということからきています。この「どの日でもよい」というのが肝心で、その結果想像以上に高い確率になることを誕生日パラドックスといいます。まさに強衝突耐性の問題と同じですね。

これら二つの攻撃は頑張れば出来ます。ただその実行難易度を非常に困難なものにしておかなければ、一方向ハッシュ関数は暗号技術として弱いものになってしまいます。

一方向ハッシュ関数をみてきましたが、序盤に述べたように解決できない問題もあります。例えば、マロリーがアリスのふりをしてボブにメッセージとハッシュ値を送ったとします。当然、正真性は確認できますが、それはマロリーの書いたメッセージの正真性です。このように一方向ハッシュ関数では「改竄」は検出できましたが、「なりすまし」は検出できません。こんなときに活躍するのが「メッセージ認証コード」と「デジタル署名」です。

続きは後編で!

参考文献:暗号技術入門 / 結城浩

BTC : 1Av3P7XBJjf5nNHaa1QDp76XGLtC6T3PLJ

LTC : LWuTZfUW9BjK3CZREdk3Y4ki12fCU5JE4m

MONA : MQx1pNvfCXuU2idsWW1xQMSRaQizAdHGTp

STR : gJ5AoP3iayUKLiEiGf87HSzQJdsKxz1Bq7

コメントを残す