Strongly Asymmetric Publick Key Algorithms について（その１）

今週の水曜日に開催された、電子情報通信学会の情報セキュリティ研究会に参加してきました。お目当ては

(18) Strongly Asymmetric Public Key Agreement Algorithms
○Luigi Accardi（Roma II）・Satoshi Iriyama・Masanori Ohya（TUS）・Massimo Regol（Roma II）

と

(19) Strongly Asymmetric PKD Cryptographic Algorithms -- an implementation using the matrix model --
Luigi Accardi（Roma II）・Satoshi Iriyama・Masanori Ohya（TUS）・○Massimo Regol（Roma II）

を聴講することでした。というのも、これら暗号があの「CAB暗号」と関係があるのではないかという憶測がインターネットで話題になっていたからでした。以下に聴講した雑感をまとめていこうと思います。

(2011年07月16日追記) 私を含む聴講者の中継の模様はこちらにまとめられています。ただし、少なくとも私のつぶやきはいくつか誤っておりますので、ご注意下さい。

さて、発表された暗号方式は、どちらも鍵交換と呼ばれる技術に分類されます。つまり、AとBが共通鍵暗号を用いた暗号化通信をする際、事前に暗号鍵（セッション鍵）を共有する必要があり、そのセッション鍵を共有させるプロトコルが鍵交換となります。鍵交換方式としては、Diffie-Hellman の方式がとても有名です。 (18)は提案鍵交換方式の一般的な記述、(19)はその一例（(18)で使用する写像として行列を用いた場合に相当）となっています。

それで、その鍵交換方式の内容は...といきたいところなのですが、説明には大量な数式が必要となるため、なかなか本質は伝えられないでしょうから、今はやめておくことにします。ただし、処理の流れとしては、1. A が秘密鍵を生成、2. A は対応する公開鍵を生成し、B に送る、3. B は秘密鍵を生成しておき、受信した A の公開鍵とから B の公開鍵を生成し、A に返送する、4. A は受信した B の公開鍵と A の秘密鍵とからセッション鍵を生成、5. B は A の公開鍵と B の秘密鍵とからセッション鍵を生成、となっており、Diffie-Hellman の鍵交換方式に手順的には似ています。ただし、A の処理量と B の処理量が大きく違っていることから、提案方式は "Strongly Asymmetric" と名付けられています。

実はまだ理解し切れていない部分が残っているのですが、提案方式は鍵交換方式として機能しているとは思います。しかしながら、次のような疑問が残りました。

• 安全性の根拠が不明：公開鍵暗号系の場合、安全性は何らかの数学的な問題の難しさに帰着されます（例えば、Diffie-Hellman 鍵交換であれば離散対数問題や Diffie-Hellman 問題、RSA 暗号であれば素因数分解問題やｅ乗根問題）。しかし提案問題はどのような数学的問題を仮定しているかが不明で、安全性の根拠はよくわかりません。もちろん、安全性の議論はなされていますが、十分とはいえない分量でした。
• 適切な鍵長が不明：どのような暗号であれ、セキュリティパラメータを大きくすればするほど安全性は高まりますが、処理速度も低下します。なので、実用上は十分なセキュリティを確保可能なパラメータサイズ（鍵長）を選択することが必要です。提案方式ではこの手の議論が見受けられませんでした。（予稿でこそ触れられていませんが、口頭の説明では、提案方式はRSAの10000倍高速と主張していました。しかし鍵長が示されていない以上、セキュリティをRSAと同じにした上での比較であるかが疑問であり、その主張は受け入れにくいです)
• 鍵選択法が不明：提案方式は多くの(Aの)秘密鍵を必要とするのですが、その選択法はかなり自由度があり、弱鍵が存在する可能性が残ります。実用上、弱鍵を選択しないような鍵生成アルゴリズムや、平均的な／最悪な場合での鍵の強さの評価は必須です。

まとめると、鍵交換方式としてのアルゴリズム提案の内容は理解できたけど、安全性評価はまだまだ、といったところが大体の感想です。

あと、講演者の態度に関する感想が一つ。講演後に、提案方式を攻撃できた可能性があるので検証させて欲しいという聴講者からの質問がありました。他の聴講者からの後押し（拍手）もあって、質問者はスクリーン横のホワイトボードを使って攻撃法を説明し始めたのですが、途中から発表者（のうちの一人）は機嫌を損ねてしまい、そっぽを向いて説明を無視していました。私は他の研究会をあまり知らないのですが、どうも暗号系の研究会や会議では、発表後に聴講者から厳しい指摘を受けることが多いことと、「攻撃」「破った」など語気が強い用語が登場することが多いのが当たり前です。なので、あれ位で立腹していたら...というのが率直な感想でした。

ではこれら提案方式は「CAB暗号」なのでしょうか。残念ながら発表者からはそのような主張は聞けませんでした。確かに合致する部分は多いのですが、微妙にずれている感じもします。提案鍵交換方式＋別途考案されている疑似乱数生成アルゴリズムを用いたストリーム暗号、あたりで説明できそうですが、それでも「基本的にRSAで行っていることはすべてCABで代替できる」あたりの説明がつけにくいです。この辺はまだ考察する必要が残っているように思います。

もう少し勉強してから、(18)や(19)のアルゴリズムの詳細を紹介していきたいと思いますので、この先を知りたい方は、気長にお待ちいただきたいと思いますｗ