因数分解は難しい
皆様、お久しぶりです。開発部の長野です。
この冬は、暖かい冬なのかなと思っていましたが、今年に入って寒くなりましたね。お体の方はいかがでしょう。ご自愛ください。
さて、今年度の将棋界には新しい棋戦が誕生しました。叡王(えいおう)戦です。この叡王戦で初代のタイトルを取ったのが山崎八段です。面白いのが、この叡王戦のタイトルを取ったものは、コンピュータとのエキシビションマッチを行なうことです。どんな将棋をするのか今から楽しみです。そして、この2月11日に私の地元愛媛県の松山市で七大タイトルの一つ「棋王戦」が行なわれます。渡辺棋王に佐藤天彦八段が挑戦するわけですが、私事ですが、なんとのそ解説会を聞きに行くことができるようになりました。
30名の定員でしたので抽選でした。運が良かったとしか考えられません。解説者は先ほどお話しました叡王戦タイトル保持者の山崎八段です。いや、今から楽しみです。
昨年大晦日も四国八十八箇所五十六番の「泰山寺」に鐘を撞きに行っていきました。皆様もお寺の鐘は見たことがあると思います。その鐘の表面にあるぶつぶつ(「乳」と言うそうです)ですが、実は煩悩の数と同じ108個あるそうです。では、煩悩の数の108個とはどうやって出てきたのでしょうか。私は漠然と次のように覚えていました。
12ヶ月×3(善・悪・普通)×3(現在・過去・未来)=108
(本当の理由は違うようですので、ググッて調べて見てくださいね)
で、ここからが本題です。
先ほどの12×3×3=108ですが、その反対の108を掛け算に戻すのが因数分解です。即ち108=12×3×3です。実際は、素因数分解(素数の掛け算に戻す)の方が意味のあることが多いので108=2×2×3×3×3とするのが常です。で、この「掛け算」と「素因数分解」、何に関係するかといえば、「電子署名」や「暗号化」です。
「公開鍵暗号方式」と言う言葉があります。そこでは「公開鍵」とその元になる「秘密鍵」が存在してそのペアで「電子署名」や「暗号化」を行ないます。「秘密鍵」は秘密にして「私だけ」が持ちます。「公開鍵」は皆さんに公開して使っていただくものです。「秘密鍵」で暗号化したものはその「公開鍵」で元に戻すことができ、「公開鍵」で暗号化したものはその「秘密鍵」で元に戻すことができるのです。そして「公開鍵暗号方式」の1つ方法として先に紹介した「掛け算」と「素因数分解」を使う方法があるのです。
この図は、グーグルの証明書を表示しています。
図で示しました「RSA」という部分が、この「掛け算」と「素因数分解」を利用した「公開鍵暗号方式」である事を示しています。乱暴に言ってしまいますと、先の例の108の素因数分解ですが、「秘密鍵」が2×2×3×3×3で「公開鍵」を「108」として、RSA方式の鍵を作ることができます。「なんだ、公開鍵も秘密鍵も同じじゃないか。秘密鍵なんて全然秘密になってないし」と思われる方もいらっしゃるでしょう。そうです、(RSA方式では)「公開鍵」を素因数分解すれば「秘密鍵」を得ることができるのです。
しかし実際は、108とかの3桁程度の「公開鍵」ではなく、600桁程度(鍵長2048bitの場合)の数値を「公開鍵」にします。なんと600桁の数の素因数分解は現在のコンピュータでも10の10乗年(100億年)程度かかります。そう、素因数分解は桁数が多くなればなるほど時間がかかるのです。
ただし、コンピュータの性能は日進月歩です。既に300桁程度(鍵長1024bitの場合)の「公開鍵」は(「京」というコンピュータを使えば)1年程度で解読される恐れがあります。
http://www.nict.go.jp/publication/NICT-News/1303/page/NICT_1303_01-2p.pdf
安全に情報を交換するためには鍵の長さを長くして解読されにくくしたり、よりコンピュータに解読されにくい新しい「公開鍵暗号方式」を取り入れたりする必要があります。
リーガルでも皆様により安全な商取引をご提供できますよう、いち早く安全性の評価を行ない、製品に活かして参ります。今後ともよろしくお願いします。