ＲＳＡ暗号と素因数分解
もちろん、復元規則が暗号規則とまったく無関係であるわけではあり ません。まったく無関係なら逆に、どんな暗号化をしても任意の復元規 則で復元されてしまうことになりますから。前項で「暗号規則から復元 規則が事実上推定不可能ならよい」と書きました。「事実上」というの がミソで、実は秘匿すべき復元規則は、公開されている暗号規則から、 一意に定まるものなのです。しかし、それを知るには、現在または近い 未来の世界最速コンピュータでも１万年かかるとしたら、これは事実上 推定不可能といっていいでしょう。
ＲＳＡ暗号では、復元規則とは、実は２つの素数であり、それを先に 決めるのです。素数とは、２や３や５や７や11のように、１と自分以外 には約数を持たない自然数です。但し使われる素数は百桁もあるような 大きな数です。一方の暗号規則はその素数の積です。それが公開される のです。実際にはもう一つ、別の数も指定・公開されますが。
２つの素数から積を作ることは、たとえ百桁同士でも、コンピュータ にとっては簡単な作業です。しかし２つの百桁の素数の積（約二百桁） だけが与えられて、そこから２つの素数を知ることは、事実上不可能な のです。比較的小さい数字の例ですが、143311という数字は、実は二つ の素数の積です。何だかわかりますか。少なくとも手計算では気が遠く なるでしょう。答えは257×523です。そう言われてみれば、その検算は、 簡単に行えますね。この143311という数字を知っていれば暗号化はでき る。それは公開してしまおう。しかし暗号化されたものから元の数字を 知るには、257という数字と523という数字が必要になる。どうだ143311 という数字がわかっても手も足も出るまい（実際は百桁なのですから）。 これが基本的な考え方です。
なお、情報通信研究機構、富士通、富士通研究所は2006年９月１日、 世界で初めて、専用ハードウェアを使った素因数分解実験に成功したと 発表しました。素因数分解アルゴリズム「一般数体ふるい法」をベース としています。入力可能自然数は最大で768ビットで、今回実験したのは 423ビット（10進法128桁）です。約１カ月間要しました。実際のＲＳＡ 暗号では1024ビットのものが使われているので、これでただちに解読さ れてしまうわけではありませんが、順調に高速化していくと、危ないか もしれません。
sponsored link
このページ
のTOPへ
