暗号ソフトをデザインしてみる


書きかけ&試論、まだ知識不足なので間違っているところもあるかも。
この分野に詳しい人はぜひアドバイスをください


暗号システムの概観の構築

周期の長い擬似乱数を、擬似バーナム暗号の乱数表に見立てる。
乱数を「完全にランダムに」取り、それを擬似乱数の種として秘密鍵とする。
バーナム暗号の鍵を、公開鍵暗号RSAを用いて暗号化する。
バーナム暗号の種の一部は、ユーザが指定する鍵にできる。

利点:
バーナム暗号の性質から、高速性が期待できる。
全体としては公開鍵暗号の性質を持たせるため、公開鍵暗号特有の利点がある。


擬似バーナム暗号(勝手にそう呼んでいる)とは、真の乱数表を使うのではなく、巨大な乱数表のうち「どの部分を使うか」を鍵として暗号法とする方法である。
乱数表とのXORによって構成され、乱数表は基本的に再利用されないという点は同じだが、いくつかの重要な概念においてバーナム暗号と違うので注意。

注意点:
周期の長い良い擬似乱数が必要。
擬似バーナム暗号ゆえに、原文-暗号文のXOR一致攻撃に対する考察または対策が必要。
種をランダムに選ぶための工夫が必要。


暗号アルゴリズム

・本文の暗号化
乱数発生ルーチンMersenne Twister + ハッシュSHA1 による(擬似)バーナム暗号。

・共有鍵の暗号化
RSA暗号。


強度を見積もる

基礎的な要素

擬似乱数Mersenne Twister(MT) の周期は 2^19937-1 通り。
RSA暗号のビット長は2048以上の長いものが使用できる。


擬似乱数MTは優れた性質を持つ乱数列を出力することが示されているので、これは取りあえず「2^19937-1周期内でランダムなもの」と言って良い。
そもそも、周期性・部分的周期性にさえ気をつければ、バーナム暗号の性質上、少々1が出やすかったりしても大丈夫だ(エントロピー低下は少ない)。


擬似バーナム暗号特有のクラックに対する強度(1)

ただ、原文-暗号文(の既知の一部)のXORから、バーナム暗号のビット列の一部がわかることに対する警戒をせねばならない。
本来バーナム暗号の乱数列は「完全にランダムで再現性なし」なのだが、ここでは擬似バーナム暗号なので、「乱数表」と使われた乱数列の一部がわかると、その後の乱数列が予測できてしまう危険があるのだ。

原文のうちnビットが既知であり暗号文も知られている時、バーナム暗号の乱数列のうちnビットの部分列が知られる(以後このnビットの並びを、盗聴部分列と呼ぶ)。
この場合の安全性を考えてみよう(今後、大きな値を考えている場合の-1などの小さな誤差は、全て無視する)。

最も安全な場合を考える。盗聴部分列の形の特性から(後述)、MTのビット列の中に含まれる個数期待値が最も多くなる場合(つまりMTの乱数表の位置が最も推定されにくくなる場合)である。
この場合、2^19937通りの中から「nビット部分列」を取り出す取り出し方は、
2^19937-n 通り
ある(これはほとんど2^19937に近い値である)。
したがって、盗聴部分列nと同じ並びのビット列が、この全ての取り出し方の中にたまたま見出される個数の期待値は、
2^19937/2^n  ・・・式1)
程度と概算できる。
つまり、盗聴部分列がMTのうちのどの部分であるかが、2^(19937-n)通りにまで絞られることになる。
例えばn=20000(2.5キロバイト)程度だとすると、このようなビット列はMT中に他にたくさんあるというよりはむしろほとんどないと思われる。

盗聴部分列の形の特性によっては、これよりも位置を特定される可能性が高くなる場合もある。
次のように考えるとわかりやすい。
盗聴部分列が「0101」であったとすると、MTのビット列「010101」の中にこの部分列は2つ存在することができるが、盗聴部分列が「0011」であったとすると、MTの6ビットの部分列の中にこれを2つ含ませることができない。2つ含ませるためには、「00110011」という8ビットの並びが必要である。
先に考えた「最も安全な場合」とは、重複を全て許した場合の概算であった。
重複が許されるとは、盗聴部分列と同じビット列が、MT中により多く含まれ得るということであり、つまり、乱数表の位置が特定されにくいということである。
ビットの重複が一切許されない時には(そうした形が実際にあるのか、それはどんな形なのかは考えずに)、nビットの盗聴部分列は、MTのビット列中に 
2^19937/2^n
個程度含まれると概算できる。
ところが、これは安全な場合と大差ない(式1と同じ)。
この暗号法の強度は、盗聴部分列の形の特性には依存しない。


擬似バーナム暗号特有のクラックに対する強度(2)

では仮に、n=20000程度で盗聴部分列が知られ、そのために理論上はMTビット列上の「位置」が知られ得るとしよう。
MTビット列の、それ以後のビット列と暗号文とのXORを取れば、暗号文は解読される。
たった20000ビットの一致から、擬似バーナム暗号は非力になってしまうのだろうか?

2^19937(およそ4.3×10^6000)という周期内で、20000ビットの部分列が「一致する」ような部分を見つけるのに要する計算時間を考える。
非常に高速な、あるいは並列処理のコンピュータを用意し、1秒に10^500回の「20000ビット一致演算」を行うことができるとする(世界中の全てのコンピュータを合わせても不可能なほどだが)。
1年は3.2×10^7秒なので、これを用いて1年に3.2×10^508回の演算が可能である。この回数の「比較」を行ったときにMTビット列から盗聴部分列を発見できる確率は
1 ÷ (4.3×10^6000/3.2×10^508) =~ 1 ÷ (1.34×10^5500)
である。
宇宙の寿命より遥かに長い時間をかけても、MTビット列上に唯一あるとわかっているビット列が、どの部分にあるかを検索することは「不可能」である。

原文-暗号文のXORを取ってビット列を得る方法は、例えば2^32周期のrand()のような擬似乱数に対しては強力な盗聴法であるが、MTの長い長い周期の擬似乱数に対しては効果的ではない。


MT擬似乱数の性質による脆弱さへの対処

MTの理論を構築された京都大学総合人間学部の松本先生のお話によると

この生成法は、計算量理論的に安全な乱数をそのままでは生成しません。しかし、Secure Hashing Algorithm(数ワードを圧縮して1ワードを生成する、非可逆的なアルゴリズム)と組み合わせれば使えます。 つまり、従来存在した、線形疑似乱数(GFSRなど)+SHAの、GFSRの代わりにMTを使うことは有効で、すでにそれを実施しているinternet関連の企業があります。
」(webページより引用)
とのこと。
上述の概算から考えて、なぜ計算量理論的に危険なのかちょっとわからないのだが、何らかの性質から、乱数表の位置候補が一気に絞り込まれるような場合があるのだろうか?
あいにくMT擬似乱数は数学的な多くの背景を持っていて、私にはわからない・・・。
ひょっとすると、1が100個連続するようなことがMTの方法では非常に稀で、MTの性質を熟知した人間ならそのようなビット列の位置を知っている、というような意味かもしれない。
松本先生はご自分で「この(暗号の)方面には詳しくないので・・・」とご謙遜なさっているが、まあ、ハッシュを使った方が良いと言うのだから恐らく実際にそうなのだろう、素直に従おう(笑)。

ハッシュは一方向計算(不可逆)だから、乱数列にこれを適用する場合、ビット列がa→bと減るとすると暗号上は次のような意味を持つ。
「既知のハッシュbビットに対応する元aビットを特定することが困難で、また対応するaビットの乱数列候補が複数存在する」

ハッシュのbビットからaビットを推測することは非常に難しい。
つまり、aビット列をいくつも用意してハッシュしてみてbに一致することを確かめなければならない。
例えば、aが1024だとすると、aビット列の可能な組み合わせを全て試すのには、2^1024回の演算が必要になる。
この計算回数は、盗聴者にとってほとんど絶望的だ。
2^1024回の演算を(何らかの?方法で)こなし、乱数ビット列のaビット列をいくつかの(2^b通りの)可能性に絞れたとしても、今度はそれを乱数表と照らし合わせて位置を特定する必要がある。
これにかかる莫大な時間は前述した通りである。

このようなことを考えると、確かにハッシュを使うことで暗号が堅牢になることは間違いない。
ただ、「この程度の」計算量の増加が、MTの長い周期性による安全性に対して影響を及ぼすとは考えにくい。
ハッシュはやはり、何らかのMT擬似乱数自体の「性質」を隠すためなのだろうか・・・(先ほど述べた「100個連続する1の位置が既知」のような?)。
そうであるとすれば、このハッシュ一致にかかる計算時間は、この暗号全体の安全性にダイレクトにかかわることになる。
その場合、aを多めに取る必要がある。せっかくMTが 2^19937 という莫大な計算量的安全性を用意してくれているのだから、ハッシュが32ビットではあまりにも淋しい。
ハッシュ長を長くすると暗号化に要する時間も長くなってしまうので、実用性も考えて、1024ビット程度のMT乱数列から8ビットの「暗号化用乱数列」を生成することにしようか。
盗聴者は16ビット分の「暗号化用乱数列」を突き止めた場合、真の乱数ビット列を得るために 2^2048 回の演算を行う必要がある。
わずか日本語1文字分の乱数列一致(そのような乱数ビット列は、MTの中に2^19937通りもある)という、暗号にとってあまり重要であると思えない情報のために 2^2048 回の演算を行う必要があることは、盗聴者にとって悲劇的な事実であるに違いない。


秘密鍵暗号部分の、攻撃に対する耐性

・「乱数列が未知」である限り、バーナム暗号なので解読は理論的に絶対不可能。
・乱数列の特定をすること(例えばXORによる乱数列の位置推測)は、上記のように計算量的に困難。
・ブルートフォースアタックは上記のように計算量的に困難。


ランダムな秘密鍵をどのように作るか

こちらを参照。


公開鍵暗号にする

秘密鍵暗号部分はこれで完成。
また、バーナム暗号の種の全ビットをランダムに取るだけでなく、一部のビットはユーザが鍵として与えることもできる。
こうすることで、万一「ランダムな秘密鍵発生部分」に問題が生じても、なおバーナム暗号の安全性を保つことができる。

次に公開鍵暗号RSAを用いて、秘密鍵自体を暗号化する。
せっかく秘密鍵部分を堅牢に作っているのだから、RSA部分の鍵ビット長が512ビットでは辛い。
幸い、RSAのアルゴリズムは難しくなく、また秘密鍵の鍵長(19937ビット=2.5KB弱)程度の暗号化のためには大した時間もかからないので、長い鍵長にも対応できるようにしておく。
ユーザは必要に応じて鍵長を変更できる。ドシロウトが集まっただけの部署で実用するなら鍵長9ビット(笑)でも非常に安全であろう。


この暗号システムのメリット

バーナム暗号の鍵をランダムに生成する意味はどこにあるのかと問われるかもしれない。
それもユーザが鍵として使えば、より強力な秘密鍵暗号になるのではないか?
また、とってつけたように公開鍵暗号にするのはどういうわけか?

バーナム鍵をランダムに作れることには、2つのメリットがある。
1つは、ユーザ指定の固定した鍵を用いる場合、もしバーナム鍵が盗聴者に知られてしまった場合、同じ鍵を使った他の文書も解読されてしまうという危険を防止できること。
さらにもう一つは、この方式にすることで、「秘密鍵を作成する必要がある人」が直接秘密鍵を入力する必要がなくなること。
例えば、他のコンピュータ上で自動的に生成された文章を安全に自分のコンピュータに送りたい場合を考えるといい。
暗号化のための鍵を別のコンピュータにそのまま置いておくわけにはいかないだろう。
ところがコンピュータがバーナム暗号の秘密鍵を自動生成し、RSAの公開鍵を用いて秘密鍵を暗号化したものを送ることで、自分だけがその暗号を解読できることになる。
そして、バーナム暗号のエンコード・デコードコストは、RSA暗号よりもずっと小さい。

もちろん、バーナム暗号の鍵の一部(一部といっても例えば1024bitを超えるようなものも可能だろう、何しろMTの周期は2^19937だから)をユーザが直接指定することもできる。
その部分は、暗号文に付加される「RSA暗号で暗号化された鍵」から除くことで、強度1024bitを超える秘密鍵暗号としても使える。


シロウトが作る暗号の問題

よく言われることだが、暗号(理論)は自作しない方がいい(既存の暗号理論を組み合わせた、暗号ソフトの自作は別だが)。
暗号理論は高度な数学的要素が複雑に絡み合っている。世界の最先端を行く研究と自分のささいなヒラメキごときとは2^1024どころではない開きがあることをいつも肝に銘じておきたい(これも自戒)。

「XORとrandom()を複雑に絡み合わせればそうそう解けないだろう」というのは、スキルのある人をあまりにも甘く見すぎだ。
例えば暗号化されたファイルがWindowsのexeファイルだと知っていれば、通常、ファイルの前半の数文字は知ることができる(少なくともある程度の予想が可能である)。
そして、たった4バイトわかれば、random()の乱数列のうち開始点がほとんど一意に定まるのだ。

多くのWindowsのexeファイルは、先頭に
4D 5A ・・・ 6D 6F 64 65 2E(0〜117バイト) 〜〜cannot be run in DOS mode.
4D 5A ・・・ 57 69 6E 33 32(0〜116バイト) 〜〜must be run under Win32
こういったようなデータの並びがあるので、4バイト一致を見出すことは困難ではない。

もちろん、前回の数字とXORを取ったり、random()から得られる乱数を間引いたりすることで少々の混乱を招くことはできるだろうが、暗号化されたファイルの数ビットだけを変化させた暗号文’をいくつか用意して暗号文-復号文の対応をいくつも用意すれば、その規則性がばれるのも時間の問題だろう。
世界のトップにはDESを2日で解読するプロフェッショナルがいる。
アルゴリズムを見られたらほとんど即座に解読できるような暗号は、現代の暗号分野では全く通用しないことをよく覚えておく必要がある。


展望

BlockSorting+PPMの自作圧縮ルーチン、またはDeepFreezerなどの優秀な圧縮ソフト(アルゴリズム)と組み合わせることで、圧縮+暗号化(いずれも高機能)の機能を持たせる。
末端のユーザは優秀な暗号化ツールを求めてはいないが、優秀な圧縮ツールなら需要がある。
高圧縮で強力な暗号機能を持った手軽な日本語ツールがない(法律の問題もあるのかも)。
フォルダ全体の圧縮・解凍(+暗号化)機能などユーザビリティを高め、解凍+デコード用dllを用意すれば広く使われる可能性も出てくる。