2017年12月07日

●「RSA暗号は因数分解の原理使用」(EJ第4661号)

 「因数分解」について復習します。因数分解とは、要するにあ
る数を掛け算のかたちにすることです。例えば、「36」という
数を例に上げます。
─────────────────────────────
         36 = 2 × 18
─────────────────────────────
 この場合、2と18は36の「因数」と呼ばれます。そのため
「2×18」は36を因数分解した結果になります。ところで、
36は次のような掛け算の式にすることができます。
─────────────────────────────
      36 = 2 × 2 × 3 ×3
─────────────────────────────
 この場合、3と2は、1かその数でしか割り切れない数になっ
ています。こういう数を「素数」といい、上記は「素因数分解」
といわれます。暗号で利用されるのはこの素因数分解です。
 われわれは、ネットでメールを送受信していますが、そのメー
ルの内容が機密性の高いものである場合は注意が必要です。なぜ
なら、そのメールの内容が途中で見られたり、内容が改ざんされ
る恐れがあるからです。インターネットは、そういうことが簡単
にできてしまうネット空間なのです。
 そういうときに「RSA暗号方式」が使われます。既に述べて
いるように、この暗号方式は因数分解の原理を利用して作られた
暗号方式です。AさんからBさんに、ある契約書をメールで安全
に送る場合を考えます。添付ファイルの図を参照してください。
事前に次の2つの「鍵」を用意します。
─────────────────────────────
      @公開鍵
       ・平文を暗号文化する鍵である
      A秘密鍵
       ・暗号文を平文に戻す鍵である
─────────────────────────────
 「公開鍵」というのは、文字通り公開されている鍵のことです
が、その目的は、平文(誰にでも読める文章データ)を暗号化す
ることにあります。
 Aさんは、Bさんに契約書(平文)をBさんの公開鍵で暗号文
にして、メールでBさんに送ります。Bさんは、この暗号文を自
分の秘密鍵で復号し、平文に戻します。秘密鍵は文字通り、自分
だけが知っている鍵のことです。秘密鍵の目的は暗号文を平文に
戻すことにあります。
 このRSA暗号方式について、北海道大学電子科学研究所教授
の竹内茂樹氏は、自著で次のように述べています。
─────────────────────────────
 例えば、あなたと友人は互いに秘密の番号が素数「3331」
であることを知っているとする。今、あなたは新たな秘密の番号
として、別の素数「3581」を伝えたい。しかし、電話、手紙
どの方法をとっても情報が盗まれる可能性がある。では、どうす
ればよいだろうか。
 方法は簡単である。既知の秘密の番号「3331」と新たな秘
密の番号「3581」を掛け合わせた数「11928311」を
電話や電子メールなどなんらかの方法で知らせればよい。友人は
受け取った数「11928311」を秘密の番号「3331」で
割り算することで、簡単に「3581」を得ることができる。
                      ──竹内茂樹著
        『量子コンピュータ/超並列計算のからくり』
            ブルーバックスB1469/講談社刊
─────────────────────────────
 メールで送信した「11928311」を因数分解することは
至難の業です。しかし、それを受け取った方の人が、秘密の番号
の「3331」さえ知っていれば、その数で、「1192831
1」を割れば、簡単に「3581」という数字を知ることができ
るので、簡単に暗号が解けるので便利です。RSA暗号方式には
そういうメリットがあるのです。
 しかし、「11928311」の因数分解は、絶対に解けない
桁数ではありません。そのため、秘密の番号の桁数を500桁に
すれば、掛け合わせた数は1000桁になります。こうなってく
ると、スパコンレベルのコンピュータでは解くのに時間がかかり
過ぎるので、事実上解くことは不可能になります。
 実際のRSA暗号方式の公開鍵や秘密鍵は数百桁の素数の積に
なっています。したがって、暗号が解読されることはないといえ
ます。しかし、条件があります。それは「現在のスパコンが今の
能力を超えることがない限りは」という条件です。
 現在のスーパーコンピュータの能力を超えるコンピュータとい
えば「量子コンピュータ」があります。量子コンピュータは、量
子力学の原理に基づいて動作するコンピュータであり、現在のノ
イマン型コンピュータとは比較にならない超高速で演算を行うこ
とができるといわれています。
 その演算速度は次の通りです。1万桁の因数分解に現在のスパ
コンの千倍高速の未来スパコンでも約1000億年かかりますが
量子コンピュータであれば、数時間から数日で解くことができる
といわれます。
─────────────────────────────
         スパコン 千倍高速コン 量子コンピュータ
因数分解/2百桁 約10年    約3日       数分
因数分解/1万桁 約千億年   約1億年   数時間〜数日
                ──竹内茂樹著の前掲書より
─────────────────────────────
 その量子コンピュータは、試作機ではありますが、既に使われ
つつあります。そうなると、因数分解を使うRSA暗号はすべて
解けてしまい、役に立たないことになります。
            ──[次世代テクノロジー論/51]

≪画像および関連情報≫
 ●「RSA暗号は量子コンピュータで破られない」
  ───────────────────────────
   RSA暗号の共同発明で知られる、アディ・シャミア教授
  (イスラエル・ワイツマン科学研究所)が2017年4月、
  国際科学技術財団から科学技術の進歩に大きく寄与した功績
  に送られる日本国際賞を受賞した。
   受賞会見でシャミア教授は、約40年間の研究の経緯を振
  り返り、最近の研究事例としてIoT(インターネット・オ
  ブ・シングズ)のセキュリティに警鐘を鳴らした。量子コン
  ピュータによる暗号解読の可能性や、日本の研究者への期待
  も語った。
   日本国際賞は1985年にノーベル賞並みの世界的な賞を
  作ろうと創設された。シャミア教授は学術分野として暗号学
  を確立した功績が、受賞理由となった。情報を安全に保管で
  きる「秘密分散法」や、秘匿情報に触れることなく個人を特
  定する「個人識別法」の開発のほか、共通鍵暗号を解読する
  「差分解読法」の発見などの業績で知られる。
   RSA暗号は1977年に米マサチューセッツ工科大学の
  ロナルド・リベスト氏、シャミア氏、レオナルド・エイドル
  マン氏が共同研究で開発。3人の頭文字をとって名付けられ
  た。インターネットなどでのあらゆるデータのやりとりに不
  可欠な技術だ。シャミア教授は会見で、大学で暗号学や暗号
  論として教えられるようになった40年間に及ぶ研究の歴史
  を振り返った。         http://nkbp.jp/2BIBVFY
  ───────────────────────────

「『因数分解』から生まれたRSA暗号」.jpg
「『因数分解』から生まれたRSA暗号」
posted by 平野 浩 at 00:00| Comment(0) | 次世代テクノロジー論 | このブログの読者になる | 更新情報をチェックする