2019年12月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
無料ブログはココログ

« TRUST 2008 の Submission Deadline Extended | トップページ | FSE 2008 の Accepted Papers »

原理から学ぶネットワーク・セキュリティ(3)

ITpro の『原理から学ぶネットワーク・セキュリティ 第3回 公開鍵と秘密鍵を作るアルゴリズム』(2007年11月27日)という記事より。今回の記事には驚きべき記載が...このブログの記事は茶化すような内容が多いのですが、今回は正面から取り上げたいと思います。

まずは復習。RSAはSSLなどに使用される標準公開鍵暗号であることはご存じの通りと思います(余談ですが、RSAは立派な標準暗号であって、RSAをデファクトスタンダードと形容することには違和感を覚えます)。RSAは暗号なので、暗号文から平文が求められないという性質が必要ですし、公開鍵から秘密鍵が特定できないという性質も必要です。これら性質は「巨大合成数の素因数分解は非常に難しい」という事実によって保証されています。

とまとめたとこで、記事を見てみましょう。

一方向関数に素因数分解が使えることを発見したのは,MITに所属する3人の科学者でした。

一方向関数では暗号文が復号できないので、落とし戸付き一方向関数じゃないとまずい、という指摘は小さな話ですね。この連載記事でもっともマズイのは

問題を解く最初のステップは,与えられた数を2つの数に因数分解することです。これ自体はさほど難しくありません。難しいのは,その因数が素数であるかどうかの判定です。

えーっ。因数分解は簡単なんですか。ていうか、因数分解できても素数判定をしないといけないんですか!

Nが素数であるかどうかを検査する方法として,√Nまでの素数で次々と割り算してみるというのがあります。しかし,「nより小さな素数は,およそ n/log(n)個ほど存在する」(素数の定理)ため,10進数で150けた程度あるNが素数かどうかを判定するには,10進数で70けた以上の個数の素数をラインナップして割り算をしなければなりません。現在のコンピュータでは,この計算が終了するまでに太陽が燃え尽きているということになります。

えーと、この素数判定法はエラトステネスの篩(ふるい)と呼ばれるアルゴリズムですが、性能的には悪い部類に入ります。賢くないアルゴリズムを理由に、その問題(素数判定問題)が難しいと結論づけるのは、詭弁ですね。素数判定は素因数分解に比べて非常に簡単です。理論的には、素数判定には決定的多項式時間アルゴリズム(AKSアルゴリズム)が存在しますが、素因数分解には知られていません。つまり「素因数分解は難しい、素数判定は簡単」なのです。著者の方は完全に誤解していると思われます。記事ではこの後にRSAのアルゴリズムが紹介されているのですが、因数分解が簡単ならば公開鍵である合成数から秘密鍵である素数が求められることになり、破綻しています。これ位、気づいて欲しいと思います。

気づいて欲しいと言えば

1024ビット(10進数で155けた程度)の素数が使用されています

もおかしいことに気づいて欲しかったです。

« TRUST 2008 の Submission Deadline Extended | トップページ | FSE 2008 の Accepted Papers »

記事」カテゴリの記事

コメント

>1024ビット(10進数で155けた程度)の素数が使用されています

この誤りはは、素人の私でもわかりました。
2^1024=1024xLog2≒300桁(10進)

元記事の「原理から学ぶネットワーク・セキュリティ」は、多少の間違いはあるものの、素人向けの記事としては分かりやすいものでした。

>2^1024=1024xLog2
は?????

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: 原理から学ぶネットワーク・セキュリティ(3):

« TRUST 2008 の Submission Deadline Extended | トップページ | FSE 2008 の Accepted Papers »

リンク