« パケットフィルタ (ipfw) の設定 | トップページ | sshd を活用する »

RSA暗号のお話

 今週は、お盆があったり、風邪を引いて寝込んだり、その退屈しのぎに本を買ってきたら、案外面白くてつい読み進めてしまったり… ということがあって筆が進まなかったので、番外編をお送りします(^-^;


● RSA 暗号とは

 RSA暗号とは、SSLSSH 等に使われている暗号の一方式で、非対称鍵暗号に分類されます。

 「RSA」という名前は、この暗号を発明した3人の名前の頭文字に由来しています。


● 非対称鍵暗号(公開鍵暗号)

 非対称鍵暗号方式の説明の前に、まず、分かりやすい共通鍵暗号(対称鍵暗号、秘密鍵暗号とも呼ばれます)方式について、簡単に説明しておきます。

 共通鍵暗号は、閉める(暗号化する)ときと開ける(復号化する)ときに、同じ鍵を使う方式の暗号です。

(「復号」は、正規の鍵を持っている人が暗号を解除するときに使われる言葉です。 意図しない第三者が暗号を解除する場合は「解読」と呼ばれます。)

 ドアの鍵に例えると、鍵穴に鍵を差し込んで、右に回せば施錠され、左に回せば解錠される、といった、昔からなじみのあるタイプの暗号の方式です。

 一方の、非対称鍵暗号は、2つ(1対)の鍵を使う暗号で、片方の鍵で閉めたら(暗号化したら)、もう一方の鍵でしか開ける(復号化する)ことができないという、面白い性質があります。

 先ほどのドアに例えると、鍵穴にAの鍵を差し込んで右に回して施錠したら、解錠はBの鍵を差し込んでさらに右に回さないといけない、といった感じの暗号です。


● 非対称鍵暗号のメリット

 非対称鍵暗号のいいところは、まず1つには、「おおっぴらに、秘密のやりとりができる」ところです(^^;

 まず、共通鍵暗号では、鍵を第三者に知られてしまうと、秘密が守れないので、鍵をどうやって意中の人に渡すか、というのが頭を悩ます問題になります。
(鍵が『悪意を持った第三者』の手に渡ってしまったら、密かに暗号を「解読」するのも、ニセの暗号文を送りつけるのも、自由自在ですよね…)

 一方、非対称鍵暗号では、2つある鍵の片方を公開用の鍵、残りを自分だけの秘密の鍵にして、公開用の鍵を必要な人たちに文字通りばらまいてしまいます。
 すると、誰でも公開鍵を使って暗号を作ることができるけど、それを復号できるのは、秘密鍵を持っている自分だけ、という、非常に好ましい状況を作ることができます。

 この「暗号の鍵を公開してしまう」というインパクトがあまりに強かったため、共通鍵暗号は公開鍵暗号とも呼ばれます。


 それと、もう一つ、非対称鍵暗号の(正しくは、RSA暗号の)いいところは、間違いなく自分が送りました、という証明(専門的には「署名」といいます)ができることです。

 文書に署名をして送りたい場合、Aさんは自分の秘密鍵 SKa で施錠(暗号化)したものを、相手の公開鍵 PKbさらに施錠(暗号化)して、Bさんに送ります。
 Bさんは受け取った暗号を、自分の秘密鍵 SKb で解錠(復号)したあと(ここまではいつも通り)、さらにAさんの公開鍵 PKa で解錠(復号)して初めて、本文を読むことができます。

 ここで、非対称鍵暗号では、片方の鍵で施錠(暗号化)したら、残りの鍵でしか解錠(復号)できないということを思い出すと、Aさんの公開鍵 PKa で解錠できる暗号を作れるのは、対になっている秘密鍵 SKa を持っているAさんだけ、つまり、文書の送り主は間違いなくAさんだ、ということが証明できるわけです。


● RSA暗号 破れる!?

 …なにか、扇情的な見出しですが(^^;;、現在の暗号に対する考え方の基礎になってる話なので、紹介しておきますね。


 RSA暗号には、実は、よく知られた弱点があります。
 それは、秘密鍵を、公開鍵から数学的に導き出せる、というものです。

 以下、ごく簡単に、RSA暗号の公開鍵の正体と、秘密鍵の求め方を説明すると…

 RSA暗号の公開鍵の正体は、2つの数字を掛け合わせて作られた数字です。
 そして、公開鍵を2つの数字に分解し、それをある公式に入れれば、秘密鍵が求まってしまいます。


 では、なぜ、公開鍵から秘密鍵がばれてしまうという、暗号としては致命的とも思われる欠点を持つ、RSA暗号が使われているかというと…

 まず、現在では、暗号の研究と、「計算機」の高性能化が非常に進んでいて、素人考えの暗号では、すでに秘密を守れない、ということがあります。

 もう一つは(こちらが本命ですが(^^;)、大きな数の素因数分解が、非常に時間が掛かる作業である、ということが挙げられます。


 現在、RSA暗号で一般に用いられている公開鍵は、1024ビット(十進数に直すと、300桁を超える数字になります)という、途方もなく大きな数になっています。
 ちなみに、この宇宙に存在する「原子」の総数が 10^80 個(十進数で80桁)程度といわれているので、その途方のなさが分かると思います…(^^;;;

 これを、正攻法で、素数で順に割っていって答えを探そうとすると、宇宙の寿命が尽きても、計算し尽くせません
(というか、全宇宙の「原子」の総数を超えてしまうため、そもそも、素数の一覧表を書き留めることすらできません(^^;


 …ということで、もっと別の素因数分解方法が研究され、2005年には、2万ドルの懸賞が掛けられていた、640ビット(十進数で193桁)のRSA公開鍵が計算により破られています。

 ◆ MathWorld Headline News: RSA-640 Factored (英語、注意(^-^;
  http://mathworld.wolfram.com/news/2005-11-08/rsa-640/

 超~要約すると(^^;

 一般数体ふるい法(GNFS) を用いて、2.2GHz の CPU 80台を使い、3ヶ月かけてデータを集め、そのあと 1.5ヶ月かけて連立方程式を解きました

 …だそうです。

 意外と簡単に解けてしまったんだな~というのが私の感想ですが、とりあえず、現在主流の1024ビットRSA公開鍵を素因数分解するには、640ビットRSA公開鍵のときの約1000倍の時間が必要になりますし、2048ビットRSA公開鍵を使えば、さらにその10万倍の時間が必要になります。

 そのほかにも、「一般数体ふるい法」自体の弱点として、この方法は、大量のデータ処理を伴うので、用意できるメモリとHDDの容量で、素因数分解できる数字の最大値が制限されてしまうそうです。


 …ということで、RSA暗号も(決して油断はできませんが)、すぐに使い物にならなくなる状況では、ないようです。


● 暗号との新しいつきあい方

 前述のように、暗号の「破られやすさ」が、数値的に評価できるようになったことで、暗号を使う側にも、「秘密は、永遠に守りきれるものではない。ただ、必要な間だけ、暗号が破られなければいい」といった、新しい考え方が生じています。


 例えば、クレジットカードの情報なら、100年間秘密が守れれば、まず問題はないだろうし、極端な話、オークションの入札金額の連絡なら、オークションが終わるまでの数日~数時間の間だけ秘密が守れれば十分、という考え方です。


 そして、暗号を破ろうとする「たくらみ」に対しては、暗号の鍵を短い時間で次々と替えて、鍵が解析され破られる頃には、その鍵はもう使ってないよ~、という運用をすることで対抗しようとしています。


 …そういうわけで、会社や学校で、パスワードは定期的に変えなさい、というお達しが出ていたら、最近の暗号化技術に対して、正しい認識を持った人がいるんだな~と思って、(めんどくさいけど(^^;)協力してあげましょう。

|

« パケットフィルタ (ipfw) の設定 | トップページ | sshd を活用する »

コメント

RSA暗号より強い暗号を作った。
「phampicky blog」記事4つぐらいお読みください。

投稿: phoiueune | 2012/12/17 02:10

phoiueune さん:
暗号の設計とは、ディープな世界に足を踏み入れましたね…
ガンバ!

投稿: むらさき | 2012/12/30 19:19

Order Glimepiride Online, glimepiride 2mg tablets amaryl tablets 2mg, glimepiride 2mg tablets amaryl 3mg tablets, buy glimepiride purchase glimepiride, vacharcucall1984.soup.io,, canada glimepiride cheap amaryl!

投稿: hailiralwork1988.miiduu.com | 2013/12/01 20:50

I think this system is very important for us !!!!!

投稿: | 2017/01/13 20:49

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: RSA暗号のお話:

« パケットフィルタ (ipfw) の設定 | トップページ | sshd を活用する »