【セキュリティ基礎】共通鍵暗号の歴史と代表的な暗号化処理

インターネットを構成する上でとても大切な暗号化技術

情報処理試験の勉強していた頃、密教のマントラみたくAESやDESを暗記していたので、内容を全く理解していませんでしたが、暗号化の歴史や基礎理論を学ぶために、こちらを読んでみました。

暗号化処理は複雑な数式が並びがちで、本書でも図を交えながら丁寧に説明されていますが、一度で理解するのは困難なので、まず暗号化の3要素である 共通鍵暗号 を流し読みした内容を抜粋。

シーザー暗号

歴史上最もシンプルな暗号化が、古代ローマでも利用されていたシーザー暗号

暗殺時には「ブルトゥス、お前もか」とのセリフで有名なガイウス・ユリウス・カエサル(英語読みでシーザー)が使用したことから名付けられた暗号化処理。

仕組みは至極単純で、アルファベットを決まった数だけ巡回的にずらすこと(例えばa→c、c→e)で暗号化できますが、26文字のアルファベットを巡回的にずらすだけでは 25通りのパターン しかなく、組み合わせが少なすぎるので現代では使い物になりませんね。

組み合わせの少なさを克服するため、アルファベットをランダムに対応付けてる 単換字暗号 が生み出されましたが、この難読な暗号処理(組み合わせは26x25x24…..3x2x1の27桁)も、シーザーの時代から約100年後には頻度分析によって破られます。

バーナム暗号

第一次世界大戦中にギルバード・バーナムが考案したバーナム暗号は、理論上安全が保証されており、平文と同じ長さの鍵を用意し、排他的論理和(XOR)を取って暗号化。

AさんからBさんへ3ビットのメッセージm(001)を暗号化して送るケースを考えてみる。

1. 事前にメッセージmと同じ長さの鍵m(乱数列r:例として011)を共有.

2. Aさんはmとrの排他的論理和を計算して結果c(010)を算出.

3. Bさんはcとmの排他的論理和で結果を複合化(001)して算出.

鍵 xor 鍵 = 0なので 暗号文 xor 鍵 = 平文 xor 鍵 xor 鍵 = 平文 が成立。

鍵に規則性がない(乱数である)のであれば、破ることは限りなく困難ですが、メッセージと同じ長さである鍵の共有する手間 に加えて 通信毎に鍵を変える 必要性があり、使いまわしてしまうとアタッカーに規則性を見破られ、破られる可能性があります。

RC4

ロナルド・リーベルトが考案した状態遷移型のストリーム暗号。

POINTRC4 = R鍵スケジューリングアルゴリズム(KSA) + 擬似乱数生成アルゴリズム(PRGA).

KSAでデータをある規則性でスクランブルさせ、規則性が見出せないように攪拌、PRGAで要素同士を更に入れ替え、状態を変化させ続け、平文と排他的論理和して暗号化。

アルゴリズムはシンプルなので、少ないコード量(Pythonでは50行くらい)でコーディング出来るらしく、ネット上でサンプルコードを見つけたので、気になる方は コチラご参照下さい。

ちなみにWi-Fi通信路暗号化で利用されるWEPでは、中心的な役割を担うRC4ですが、幾つかのデータに偏りが発見され、現在では頻度分析により破られています。

2種類の暗号処理

暗号化をアルゴリズムの観点で分類すると、ストリームとブロックの2種類に大別。

RC4に代表されるストリーム暗号の特徴は以下のとおり。

・1bitや1byteなど細かい単位で処理

・次々に乱数発生、平文の要所(bit/byte)で乱数掛け合わせ(排他的論理和)

・ブロック暗号に比べて処理が単純で高速

乱数について擬似乱数発生器を使えば、ある条件下(シート値)で毎回同じ値が算出。

ブロック暗号で使われる 転字 は、あみだくじのように順番を入れ替える行為で、換字 は、いくつかのビットをまとめて別データに置き換える行為をさします。

・一定サイズのブロック単位で処理

・転字と換字の組み合わせ

ブロック暗号はSボックスに通して転字し、鍵と混ぜる操作を繰り返し行う。

DES

DESは Data Encryption Standard の略称でブロック暗号の一つ。

ブロック暗号は転字と換字とラウンド鍵を混ぜる操作を繰り返しますが、最初にデータを二つの山に分ける特徴があり、加えてハードウェアでの実装に適しています。

DESのアルゴリズム(入力データを32bitずつに分割し、16段の暗号化処理を繰り返す)は開発者にちなんで フェイステル構造 と呼ばれ コチラ では処理の流れを丁寧に解説されています。

DESの解読方法には 総当たり攻撃差分解読法 などがありますが、難攻不落と言われたDESを完全に破ったのが、三菱電機の松井充氏率いるチームのFEALと呼ばれる 線形解読法 だとか。

AES

AESは Advanced Encryption Standard の略称でブロック暗号の一つ。

ハード・ソフト双方での実装に適し、AES( 詳細 )はブロック長が128bit、鍵長に応じて、AES-128、AES-192、AES-256の3種類があり、鍵長を長ければ安全性は増しますが計算量も増加。

AESの構造は SPN構造 と呼ばれ、入力データを幾つかのブロックに分割して置換・転置を繰り返し行いますが、同じデータ長ならばDESよりもAESの方が高速に処理可能。