2018/03/14

【読書メモ】 現代暗号入門

現代暗号入門 神永正博・著 講談社BLUE BACKS 』
本著者の著作としては、以前に『直観を裏切る数学』を拝読したことがあり、数学上のさまざまな論題についてリスク想起を併せ含めたアプローチに感心したものであった。
その同著者による此度の本、冒頭にて暗号は数学技術の塊だがなんでもありの雑多な世界でもある』 とおかれており、なるほど、多くのダイナミズムとヴァリエーションを予感させて楽しい、が、同時にまたセキュリティ/ハッキングリスクを喚起する書としても了解すべきであろう。
本書p.39にても、『暗号アルゴリズムはその外部脆弱性を常に前提におくべきであり、むしろアルゴリズムを公開してその脆弱性を積極的に検証することが望ましく、これは世界的な共通認識ですらある』 由を念押しされている。

さて、本書が呈する暗号技術の概説は、僕なりに考えても、大学生や高校生に是非とも了察させたい「超」現代的なコンセプトであるのだが、全くの初学者はやや概念捕捉に戸惑うかもしれない。
そもそも本書は、名詞の引用量に相反して動詞表現が包括的ないし省略的であり、これは新書版というコンパクトサイズ編集上の制約か、或いは数学分野における専門家の文体習慣によるものか ─ いずれにせよ、或る暗号技術についての文脈において、その実装システムを指すのか、関数モジュールを指すのか、アルゴリズムを指すのか、処理データについてなのか鍵についてなのか等々を想定し難い。
それでも、例えばだが 「システムコンセプト」「ビジネスアプリケーション」「数理(アルゴリズム)論」「リスク論」などのように思考対象ごとに階層分類した章立てがなされていれば、ヨリ読解しやすいものとなったのではないか…と、対象別の描写を好むのが、数学勘を発動しにくい僕のような読者なりの見解ではあるが、数学センスの高い読者からすれば思考の階層も対象分類も無用ということになろうか。

なお本書は、随所におけるアブストラクト図案が素晴らしく明瞭であり、例えば秘密鍵/公開鍵ベースでのチャレンジレスポンスオペレーションなどなどは、僕自身かつて電子商取引デバイスの営業に携わっていた際の研修資料の一端を想起させてくれる。
これも、本書を学生など初学者に推したい理由の一つである。

ともかくも、此度の『読書メモ』として、僕なりに本書から了察しえた範囲にて、とりあえず以下に概説を略記しおく。
(ただし、本書の随所で引用されている数学理論/数式については、どの程度までが概説か応用か判然としなかったので、仔細は記さずに留める。)


<単換字変換>
古来より、アルファベット世界では、メッセージ平文の一文字ごとに一定の秩序で数字に変換(単換字方式)、その上で特定の数理に則った「鍵」を用いて暗号化、という方式が一般的に暗号/復号に採用され続けてきた。
しかし同時に、外部からこの鍵を見抜く(そして暗/復号の文面も見抜く)脅威も常に存在し、この手口として特に留意すべきは、通常のメッセージ文における特定単語の出現頻度を元にして単換字とその数字を類推し、それで数学的ロジックから鍵を導いてしまう方法論である。

<バーナム暗号>
第一次大戦期に開発された、2進数0/1ビットと「排他的論理和」の演算論理を活かす暗/復号方式。
バーナム暗号方式にては、メッセージ平文にあたる数字を2進数0/1ビットの一定ビット長(たとえば16ビット長など)に置き換え、これらそれぞれの0/1ビットを、同じビット長の「秘密鍵」それぞれの0/1ビットと「排他的論理和」にて演算し、その出力それぞれの0/1ビットを「暗号文」の数字とする。
逆に、この暗号文に「同じ秘密鍵」をぶつけてやはり排他的論理和を出力すると、平文に復号出来る。
この同じ秘密鍵をメッセージ送信者/受信者間で共有した上で、暗/復号通信を行う。

尤も、秘密鍵が外部者から暴かれる脅威はどうしても残るため、平文の新たな暗号化送信の度に秘密鍵も新たに「乱数のごとく」生成する必要がある。
平文と秘密鍵双方のヴァリエーションが同等に確保されれば、バーナム暗号は理論的に破られない。

<ストリーム暗号>
平文の暗号化送信の度に秘密鍵を毎回乱数として生成するコストを低減すべく、平文よりも短いビット長の暗号鍵を活用する。
ただし、秘密鍵のビット長があまりにも短すぎると、ブルートフォース(総当たり攻撃)で攻撃者に見破られてしまう。
そこで、その秘密鍵を「平文よりも長い周期(ヴァリエーション)をもつ」長いビット列に変換、これを「キーストリーム」と称し、これをもってバーナム暗号と同様に平文ビットを排他的論理和で演算する。

キーストリーム秘密鍵の生成には、「LFSR(線形フィードバックシフトレジスタ)」を複数組み合わせて、長い周期の最小公倍数を秘密鍵に設定する方式があり、これはヨーロッパGSMの音声暗号化システム(A5/1)にて起用されきた。
キーストリーム秘密鍵のもうひとつの生成方式は「状態遷移型」であり、これは秘密鍵を成すビット列の一部のビットを常に入れ替え続けるロジックで、RC4システムが代表的であり、バーナム暗号方式に比べると暗号化のプロセスがかなり短縮されている。
RC4システムは最近までWi-FiのWEPプロトコルにて起用されてきた。

しかし、RC4システムで生成されるキーストリーム暗号も、既に外部者に見抜かれてしまった ─ と見做されている。
ストリームのビット列における特定の数字の出現頻度をもとに、大数の法則などによる数学的な解析によって見抜かれた、とされている。

====================

<ブロック暗号・SPネットワーク>
数学者シャノンが閃いた混合関数に始まるコンセプト。
各ビット単位ではなく64ビットや128ビットなどの「ブロック」単位で「多字換字」を行う関数(Sボックス)と、ビット位置の入れ替えつまり転字処理を為す関数(Pボックス)から成る。
これらSボックスとPボックスを複雑に組み合わせたモジュール構成をSPネットワークと称し、この構成によるビット変換は従来には無かった複雑さを実現した。
また、秘密鍵は、SボックスとPボックスの処理ラウンドごとに新たに生成され、Sボックスで多字換字されたビット列を排他的論理和で演算し、その結果がPボックスへ…、と処理ラウンドが繰り返される。

このラウンド数が多ければ多いほど、SPネットワークとしての暗号強度も高まるが、処理時間もかかることとなり、適度なラウンド数が調整されている。

<DES方式>
IBMのフェイステルは強度の高いブロック暗号アルゴリズムを考案、それを元に開発された暗号アルゴリズムがよく知られる「DES方式」である。
DES/フェイステル構造は、平文を64ビットごとにSPネットワークで暗号化するにあたり、SボックスとPボックスを組み合わせたFボックスを設け、64ビットのうち半分をこのFボックス内にて多字換字しラウンド鍵を掛けさらにPボックスで展字処理し、この出力を別の32ビットとラウンド鍵でぶつけ…と、ヨリ複雑な処理ラウンドを重ねていくつくりである。
この構造のメリットは、複雑な組み合わせ演算をFボックスにまとめて収納していること、および、ラウンド鍵の順番を逆転すればそのまま暗号文の復号が出来ること。

DESは当初から、排他的論理和を突いた「差分解読法」によって破られうることも想定されていた。
或る外部者が、幾つかの平文を試験的に作成し、これら間における排他的論理和(差分)を確認、それから、暗号文の差分をも確かめる、と、この両者間での差分の異なりをもとに、ラウンド鍵の見当がついてしまう ─ これが差分解読法で、ラウンド数に応じて、この解析精度も上がってしまう。

三菱電機の松井のチームは、試験的作成ではなく既知の平文を使用し、DESのフル16ラウンドにおいて、平文/暗号文をつなぐ線形(に近似した)関係式を作成してみせた。
この方法論は「線形解読法」と称され、「どれだけの数の既知の平文があれば、どれだけの確率でこの関係式が成立しうるか」、を表現したもの。
 (※ ここの段は本書における最初の数学上の難所で、引用されている数学論も本当のところ僕にはよく分からない。)
松井のチームはこの線形解読法さえも克服しうるブロック暗号方式MISTYを開発、2005年に国際標準規格となっている、が、これも既にNTTセキュアプラットフォーム研究所にて論理上は破られてしまっている。

1997年、アメリカ国立標準技術研究所はDESに代わる強力なブロック暗号方式を「AES」と冠し、このAESにふさわしい暗号方式を公募、2000年にRijndaelが公式採用された。
Rijndaelは平文サイズ128ビット固定の上で現在まで推奨され続けている。

<共通秘密鍵システム事例>
Sonyが開発のFelicaシステムはSuicaなどのICカード乗車券にて採用されており、これはシステムサーバ側とユーザ側にて秘密鍵を共有したもので、「チャレンジレスポンス認証」の端的な例である。

ユーザが自動改札を通過する際に、改札機(のサーバ)が乱数を発生させ(チャレンジ乱数)、これをユーザのICカードに送信、ICカードは内蔵された「秘密鍵」でこのチャレンジ乱数を暗号化し、改札機(のサーバ)に返信(レスポンス)する。
ここで同時に、改札機(サーバ)は自身が発生させたチャレンジ乱数を自身の「秘密鍵」をもって暗号化し、ICカードからの暗号と一致するか否かを判定、一致すれば双方の「秘密鍵」が同一であるとみなす - だからそのICカードを通過させるという、これがICカードの「内部認証」である。
さらに、逆にICカードがチャレンジ乱数を発生させて改札機(サーバ)がレスポンスを返すフローもあり、やはり双方の秘密鍵が同一かを確かめる、こちらはICカードの「外部認証」。

「内部認証」と「外部認証」を相互に為すシステムもあれば、どちらかだけで済ませているシステムもある。
ユーザが自動改札でICカードをかざしてから、そのユーザの正当性を認証してゲートを開くまで、このジョブオペレーションを「タッチ・アンド・ゴー」と称し、通信路自体の暗号化も含めたオペレーション所要時間は0.5秒を実現。
なお、Felicaシステムは秘密鍵のブロック暗号アルゴリズムとして当初はDESの直列方式を採用していたが、2011年以降はAESシステムに移行しつつある。

===================

<ハッシュ関数>
ハッシュ関数の設計例が「マークル・ダンガード構成法」。
或る平文データを同じサイズ長の2ブロック(と端数埋め合わせ)に分割し、この2つのブロックを圧縮関数が1つの同サイズ長のものに圧縮、それぞれの出力値を次の「同じ」圧縮関数がまた同様に圧縮演算し、さらに次の「同じ」圧縮関数が…と、圧縮演算を繰り返しすもの。
かつこの演算フローにては暗号化の初期ベクタもかかっている。
最後の圧縮関数演算により出力される「ハッシュ値」は最初の平文データからは想像もつかぬ、つまり演算の「一方向性」を満たす数値となっているはずであり、これがハッシュ関数方式の効用である。

ハッシュ関数方式のもう一つの効用は、或る平文データのどこかの部分における「改竄」の有無を明らかにすること、逆にみれば、暗号化されたハッシュ値の「同一性回避」(オペレーションにて衝突を回避)を明らかにすることである。

ハッシュ関数とブロック暗号方式はほとんど相互補完しており、たとえばAESブロック暗号方式にても、秘密鍵の代わりにハッシュ値を入力すればハッシュ関数システムとして機能する。

ハッシュ関数はウェブサービスのパスワード認証フェーズにて起用されている。
じっさい、「APOPプロトコル」では、外部者からの傍聴を前提として、サーバ/クライエントの双方にてチャレンジ乱数とパスワードをハッシュ関数MD5でハッシュ値とし、その上でチャレンジレスポンス認証を実現してきた。
だが、外部の傍受者はこのチャレンジ乱数と(自身が推察する)パスワードをもとに一連のハッシュ値を盗むことは出来、そこでもしハッシュ値の同一性を見いだせれば、それらをもとに本当のユーザパスワードを当ててしまうおそれがある。

サーバに成りすますとの前提で、2008年に電気通信大学の太田教授のグループはハッシュ関数MD5からユーザのパスワード31文字までを復元してみせた。
こうしてAPOPプロトコルは非推奨と見做されるようになり、代わって「POP3Sプロトコル」などが推奨されるに至っている。

==================

<公開鍵暗号(RSA)>

公開鍵方式は、メッセージの送信者と受信者のそれぞれが「公開鍵」と「秘密鍵」を組み合わせ、平文を「暗号化する鍵」と「それを復号化する鍵」を別に設定する仕組み。
公開鍵方式は、何らかの「一方向性関数」を活かしている。

初期の公開鍵方式である「RSA暗号」方式は、オイラーの定理(合同算術と法)が活かされている。
pもqも素数で、整数aはpもqも約数に持たず、法Nをpqとすると、a(p-1)(q-1) ≡ 1(mod N) が成り立つ、これがオイラーの定理におけるここでの着想の元。
これを変形して、ak(p-1)(q-1)+1 ≡ a(mod N) 
ここで左辺の乗数k(p-1)(q-1)+1 = ed とおくと、右辺edも法Nであり、(e,N)のペアと(d,N)のペアは異なる整数となる。
さて、M(mod N) を元の平文メッセージとする。
これをe乗して暗号文Cをつくると C ≡ Me(mod N) となる。
これをさらに両辺をd乗すると C ≡ Med ≡ Mk(p-1)(q-1)+1 ≡ M(mod N) となり、元の平文メッセージに戻る。

この式展開の意義は、或る平文Mを(e,N)のペアで暗号文Cとし、それを(d,N)のペアでまた平文Mに復号するということであり、どちらの演算でも商ではなくNを活かしているため、割り出しが困難である。
ここでの(e,N)が暗号化のための「公開鍵」で、(d,N)が復号のための「秘密鍵」であり、これを併用するのが「RSA暗号」方式。
この安全上の問題としては、素因数分解を用いて公開鍵(e,N)から秘密鍵(d,N)を割り出されるおそれが常に残ること。
この脅威を防ぐためには、Nを巨大な数とし(例えばもとの素数p,qを1024ビットの表現数として)、かつdもNと同じくらい巨大な数として、素因数分解が困難でなければならない ─ とされているが、これだけで無条件に安全ともいえない。

いわゆる電子署名は、RSA暗号とハッシュ関数を組み合わせたもの。
実用例として、SSL(セキュア・ソケット・レイヤ)通信ないしTLS(トランスポート・レイヤー・セキュリティ)通信などの暗号化システムがあり、これらはインターネットショッピングなどをはじめ、マイナンバーシステムにおけるチャレンジレスポンス認証にても起用されている。

======================

…以上、このあたりまで僕なりに読み進めてみたが、まだ本書の半分程度である。
ともあれ、暗号技術とはいったい何か、強度確保のために如何なる数学が必須であるのか、ざっと想像出来るだろう。

さて、本書は更に、RSA暗号方式が晒され続けている暗号破りの脅威を説きつつ、数論の難度もぐっと上がり、そしてヨリ現代的な公開鍵暗号方式としての「楕円曲線暗号」の紹介に至ってゆく。
また、本書後半部にては、暗号通貨/ブロックチェーンのナンス数など直近の主題概説はもとより、暗号数学についての計算量と判定時間(たとえばP≠NP問題も)、またいわゆる量子コンピュータ出現と暗号技術についての考察も挙げられている。
さぁそうなると、量子暗号なるものはどんなふうに?2進数ビットでの計算オーダーを超えたすごいものに??電子通貨の暗号セキュリティは???などなど、数学が不得手な僕なりにも想像力も掻き立てられてやまない。

なお第5章では、CPU、メモリ、更にインバータなどなどハードウェアベースでの暗号演算ハッキングのリスクについても分析されおり、何がなんでも暗号を破ってやるというハッカー攻撃の執拗さを垣間見ることが出来よう、これもまた良い意味で面白いものである。

以上