ネット通信の安全性 ～RSA暗号の業績と未来

ネット通信の安全性
～ＲＳＡ暗号の業績と未来～
１．はじめに
長野県伊那北高等学校 理数科
土田大地 金田理紗
２．ＲＳＡ暗号とは
・公開鍵暗号の一種。公開鍵暗号とはその名の通り、暗号化する鍵（以下、公開鍵）が
全体に公開される暗号である。
・公開鍵と解読する鍵（以下、秘密鍵）が別のもので、秘密鍵は受信者のみが持つ。
したがって、暗号化は誰にでもできるが、解読(以下、復号)は受信者しかできない。
私たちの生活する社会は、「コンピュータ社会」と言われている。そこでは今
や、メールの内容や、ネットショッピングの際に使われる、カードや口座の番号
などの個人情報が飛び交っている。
私たちはそのような個人情報を暗号化する、ＲＳＡ暗号に目をつけ、主にそ
のしくみと安全性を探ることにした。
３．ＲＳＡ暗号のしくみ
① ２つの素数 P,Q を設定する
⑤ 元の文（以下、平文）を決め、公開鍵を受け取る
・ここでは、P = 19 Q = 41 とする。
・コンピュータ上では、あらゆる文字が数字に変換される。
・この P，Q が、秘密鍵を作るもととなり、素数でないと簡単に秘密鍵
が計算されてしまう。
・ここでは、平文
M = 21 と変換されたとする。
⑥ 平文 M を暗号化し、暗号文を送信する
② N,φ (N) を計算する
・暗号文
C は、C = ME mod N を満たす。
これは、M の E 乗を N で割った余りが C であることを示す。
したがって C は、217 ÷ 779 = 2312052 あまり 33 より、C = 33
N = P×Q = 19×41 = 779
φ (N) は、(P - 1) と (Q - 1) の最小公倍数
φ (N) = 360
・これを送信する。
③ 鍵E を設定する
⑤
②
③
⑥
④
⑦ 暗号文 C を復号する
・鍵E は、φ (N) より小さく、互いに素である（１以外の公約数がない）
任意の数。
・解読後
となる。
⑦
の文（平文） M は、M = CD mod N を満たす。
したがって M は、33103 ÷ 779 = …… あまり 21 より、M = 21
・これは、『送信者』が⑤で設定した平文の値と等しくなるので、
復号成功！！
・ここでは、E = 7 とする。
・この E と、前記の N が公開鍵
①
図１
④ 鍵D を計算する
・鍵D は、E × D = n × φ (N) ＋ 1 を最小の n で満たす数。
・ 7 × D = n × 360 ＋ 1 は、 n = 2 のとき、D = 103 をとる。
・この D と、前記の N が秘密鍵
となる。
秘密鍵の１つである N は、P，Q の積
N を素因数分解すれば、P，Q が求まってしまう
安全と言えるのだろうか？
４．ＲＳＡ暗号の安全性
①事実上の安全性
◎理論的には、公開鍵暗号として完全な安全性を持たない
◎現在のコンピュータ性能においては、事実上安全であるといえる
(
・安全な公開鍵暗号方式は、次の要件を満たす必要がある。
１．識別不可能性 ２．強秘匿性 ３．頑強性
・ＲＳＡ暗号は、これら３つの要件を必ずしも満たすわけではない。
理論的には完全に安全とは言えない
・ＲＳＡ暗号特有の安全性の根拠と
して、素因数分解の困難さがある。
・現在の素因数分解世界記録は、
2009年時点で232ケタ（768ビット）
であり、解読に3年かかる。(図2)
・推奨されているＲＳＡ暗号の大き
さは、最低1024ビットであるため、
このペースだと、瞬時に解読され
るまでに十分な猶予があると考
えられる。
②ソフトウェアを用いた安全性の検証
図3
検証目的
秘密鍵を知らない第三者が、任意の秘
密鍵で復号を試みた場合、復号されるか
検証する。
検証方法
① ソフトウェア（図3）の操作手順に従い、
平文を暗号化する。
② 図の『復号鍵』の欄に、正規の秘密鍵
とは異なる、任意の数を設定する。
③ 『復号文』の真偽を確かめる。
結果
図3 ： フリーソフトウェア ＲＳＡ Ｅｘｐｅｒｉｍｅｎｔｓ
より
・ 私たちは、『復号鍵』の欄に任意の数を 50 種類設定し、試行してみた。その結果、
すべての数において『復号文』は文字化けを起こしてしまい、復号することはでき
なかった。
・ 今回使用したフリーソフトウェア「ＲＳＡ Ｅｘｐｅｒｉｍｅｎｔｓ」は、Ｐ，Ｑ に 200 以下の
素数までしか設定できない。だが私たちの生活に普及しているＲＳＡ暗号は、数百
桁のものであるため、正しい秘密鍵を知らない第三者による復号は、事実上不可
能であるといえる。
５．ＲＳＡ暗号の未来
新たな技術が生まれたら、解読される危険性がある
①現在の技術的課題
・前述のように、1024ビットのＲＳＡ暗号の場合、暗号の内容が意味を持ちうる期間内（例えば、３年前の
暗号を解いたとしても、３年前の内容など意味がない）に解読できるようになるには、まだ時間がかかる。
・また、完全に安全ではないとはいえ、現在ＲＳＡ暗号を解く効率的なプログラムは存在しない。
②量子コンピュータ
・量子コンピュータは、現在のコンピュータでは実現しえない、超並列処理ができる。理論上、現在のスー
パーコンピュータで数千年かかる計算を、数十秒といった短い時間でこなすことができる。
・ 2011年時点で、実用化には至っていない。しかし、実現すれば、1024ビットのＲＳＡ暗号の解読は時間
の問題である。
こまめなセキュリティソフトの更新が、必要不可欠！！
６．感想
ＲＳＡ暗号のしくみと安全性を探っていく中で、オイラーの
関数や定理、中国の剰余定理などの難解な数学的知識に
触れ、改めて数学の複雑さと深さを感じた。
今回の研究を通して、暗号に関してより興味を持つことが
できたので、量子コンピュータの動向などにも注目していき
たい。
７．参考文献
・東京書籍『数学のリアル Real-Use Math Skills』
桜井進 著
・RSA Experiments
・SPPコンピュータセキュリティ講座講演会資料
富士通研究所セキュアコンピューティング研究部
下山武司
・Wikipedia
RSA暗号/公開鍵暗号