Crypto Alarm Basic(CAB方式)について再び考えてみる

    • 関数からなる無限集合から鍵となる関数をピックアップ
    • 逆関数の計算が極めて難しい関数の集合を利用--その関数自体が無限個の中から利用者が自由に選べて、いつでも変えられる
    • CAB方式は、適当な初期値を取ることで任意の長さのランダムなバイナリ列を生成するアルゴリズムや、公開鍵分配アルゴリズムからなる。
    • 公開鍵暗号方式はCAB方式の特殊な場合
    • ワンタイムパッドはCAB方式によって可能となる暗号通信の1つで、CAB方式は、これがすべてではない
  • 計算機上で実際に実装した上で、安全性を保障する必要がある暗号アルゴリズムにおいて、無限を持ち出すのはやはりおかしい。これは、無限と言っていいほど多数の、という概念を、考案者が素人にわかりやすく表現しただけ、と見た。Haskellの無限リストみたく、有限の計算資源で無限を扱う方法も無くはないが、多分今回は関係ないでしょ。無限の概念の濫用はサイエンスのマナーに反するので、サイエンティストは無限という言葉の使用には敏感なはず。
  • そういう理解のもとで考えると、どうもカオス暗号のことを言っているような気がする。「無限(といえるくらい大きい)集合から鍵となる関数をピックアップ」する、というのはカオス源となる関数をあらかじめ決めておいて、そのパラメータを鍵として考えているということでしょう。たとえばロジスティック写像だったら関数形がx=ax(1-x)で、aとxの初期値を鍵とする、みたいな。パラメータが有理数だったら確かに無限個あるけど、計算機上では浮動小数点で表現するわけだから、まあやっぱり有限だよね。
  • さてそう決めつけて考えると、以下のようなハイブリッド暗号を考えることができる
    1. Aliceは秘密鍵としてaとxを生成
    2. AliceとBobは何らかの公開鍵暗号を使った鍵分配アルゴリズムでaとxを共有
    3. AliceとBobはaと初期値xから作られるカオス関数からどんどんランダム(に見える)値を吐き出させ、これをonetime padの鍵にする
    4. Aliceはカオスの列からonetime padでじゃんじゃんメッセージを暗号化
    5. Bobは同様にカオスの列からメッセージをじゃんじゃん複合化
  • このスキーム自体はたぶん全然新しい話じゃなくてカオス暗号の一般的な枠組みだと思われます(良く知らないけど)。このスキームの弱点は二つある。
    • カオス関数から吐き出される値が一様ランダムであることは証明されてないこと。onetime padを使っているので情報理論的に安全にみえるけれど、実際はそうじゃない(かもしれない)。かもしれないからこそ、「ランダムな数列生成ではNIST(米国立標準技術研究所)で使われるテストで検証済み」として安全性を担保しているのだろう。
    • 「何らかの公開鍵暗号を使った鍵分配アルゴリズム」を使っているために、ここが計算量的に安全性であるにすぎないならば、全体も計算量的に安全にすぎない、ということ。でもこれは実際はsshRSAとtriple DES/AESのハイブリッドで構成されていることを考えれば何の問題もない。
  • 一方このスキームのいいとこはとにかく鍵生成が高速なとこ。カオス関数の計算は、巨大素数をぶん回すような計算は不要で、ごく単純な代数的計算ですむし、暗号化・復号化部分は単なる排他的論理和だ。これなら「10万ビットの鍵でも1秒未満で生成でき」て、「4MBほどある聖書のテキストを、その聖書に含まれるビット数と同じ長さの鍵を使って暗号化するのに、一般的なPCでも1秒もかからない」ってのも納得です。
  • 実際にはカオス暗号ってのは理論の世界ではいまのとこ中心的に議論されているとはいえなくって、今後にこうご期待、というような立ち位置ではあるけれど(see 信頼性の低い暗号アルゴリズム - Wikipedia)、別にIND-CPAだとなんだといわなくても、速くて使い勝手がいいんだったら、用途を選んでどんどん使ったらいいと思う。ゆっていいのかどかわからないのでゆわないけれど、どっかの電機メーカもカオス暗号をつかった映像配信のシステムを試作してたようだし。
  • 実際にはこれくらいの枠組みで、あのような大々的な成果を誇るってことは多分なくて、もっと画期的な発明があったのだろう。以下は単なる予想。
    • 暗号に(どのような点でかは知らないが)すごく良く適したカオス関数の群れを発見した
    • 鍵交換アルゴリズムとカオス関数の間になにか良い性質があって、それがスキームの大幅な効率向上をもたらした
  • でもどう考えてもこれらのスキームがRSAなどの公開鍵暗号の一般化になっているとは思えない。全然違う。もし本当にそうであるとしたら、
    • カオス関数の群れ自体を鍵集合とした公開鍵暗号系が構築できてて、それらのサブセットにRSAや離散対数暗号や楕円曲線暗号が含まれる、
  • このぐらいまで証明する必要があると思う。こうだったらかなりの大発見でしょう。でもそれはやっぱりないよな。。。
  • と、つらつら書いてきたけど、本当にこの@ITの記事で納得できないのは、暗号系自体の説明や扱いではないんですよ。長くなったから続きはまた明日。