メイン

符号化・暗号 アーカイブ

2007年3月21日

暗号に関する素朴な疑問

 筆者は、もう10年以上も前に、このようなとても簡易な暗号化アルゴリズムを考えた。すなわち、ソースを見て戴くと分かるように、指定されたパスワードに基づき、バイトの255文字→255文字の換字テーブルを生成し、その換字で変換した結果に対して、同じく指定されたパスワードに基づき生成した擬似乱数のオフセットを加える、というとても簡易なものである。
 それで私の素朴な疑問は次のとおりである。よく世間で、DES暗号が破られたとか、公開鍵暗号が破られた、という記事をみかける。しかし、それは、暗号化方式が予め分かっている場合であって、キーだけが不明な場合ではないか、というものである。
 例えば、上記のような簡単な暗号化であっても、擬似乱数のオフセットがあるため、換字テーブル方式の変形版であることがなかなか分からないのではないか。また、たまたま換字テーブル方式の変形版であることが分かったとしても、どのような仕組みで擬似乱数が生成されているかも分かりにくいのではないか。
 もっと言うと、DES暗号や公開鍵暗号のような本格的な暗号ではなくても、文字列コード群の集合から文字列コード群の集合への全単射を与える任意の関数で、暗号化を行うことができるので、暗号化方式というのは、少なめに見積もっても加算無限個あるだろう。よって、次のような命題を提案してみる。
 任意の長さの平文と、それをある特定の暗号化方式で暗号化した暗号化文とが与えられたとき、暗号化方式のアルゴリズムとそのキーを特定するアルゴリズムは、一般には存在しない。
 なお、参考までに、上記のプログラムで、
東京特許許可局
 という文字列をもつファイルを、test1という暗号キーで暗号化してみた。

まず、「東京特許許可局」の16進バイト表示は、次のとおりである。
93 8c 8b 9e 93 c1 8b 96 8b 96 89 c2 8b c7

また、「東京特許許可局」を暗号化した結果の16進バイト表示は、次のとおりである。
ae 76 e3 4a 91 89 29 7b 1e 6c b6 b0 5d 8b

 かなり非自明だと思われるがいかがであろうか。


2007年10月29日

離散対数問題

 b ≡ am mod n のような計算を考える。すなわち、a, m, nを適当に与えたときの、bの値を求めるのである。これは、mやnが100桁程度の数だったとしても、コンピュータで計算するのは、それほど困難ではない。というのは、m = kr + s のように書き表すと、
am = ak × ak×・・・×ak + as
 と順次、計算できるからである。
 しかし、b, a, nが与えられて、b ≡ ax mod n を満たすようなxを求めなさい、という式になると、全く事情は異なる。これが実数の世界なら、x = b/log(a)であるが、整数式の世界では、そのような計算は、許されない。実際、aという値が与えられたとき、a mod nがどのような値になるか、aとnを引数とする適当な関数は存在せず、b ≡ ax mod nを求めるために、最悪、x = 1..nまで試して、計算結果がbになるかどうか確認する必要がある。しかし、もしnが100桁程度の整数であると、その計算には、宇宙開闢的な時間がかかる。これを、離散対数問題の困難性といい、RSA暗号など、いくつかの暗号が、これの困難性を利用している。
 さて、離散対数問題を高速で解くアルゴリズムは存在するのだろうか。ものの本には、量子コンピュータがそうだというが、私には全く理解不可能である。離散対数問題のmod計算を、楕円曲線のmodに置き換えると、さらに解きにくさが高まる。
 ふと、周囲の人との会話で、離散対数問題が話題になったので、整理してみた次第である。

About 符号化・暗号

ブログ「Commutative Weblog」のカテゴリ「符号化・暗号」に投稿されたすべてのエントリーのアーカイブのページです。過去のものから新しいものへ順番に並んでいます。

前のカテゴリは科学一般です。

次のカテゴリは経営学です。

他にも多くのエントリーがあります。メインページアーカイブページも見てください。