素数と暗号

　
石井俊雄
最近、素数という言葉が暗号との関連で語られることが多い。 例えば、ＮＨＫでは１年ほど前、「素数の魔力に囚われた人たち」という表題で、リーマン予想や、暗号への応用、を分かりやすく説明していた。 小生が、興味をもったのは、後者の「暗号への応用」。
それで、その素数をどうやって暗号に応用するのか、肝心のアルゴリズムを調べてみた。 暇つぶしには丁度いいかなというところだ。
昔の暗号は、共通鍵暗号を用いるのに対し、新しい暗号は公開鍵暗号を用いる。
共通鍵暗号は、１つの鍵で暗号化し、同じ鍵で復号化する。 だから、共通鍵は秘密にしなければならない。 一方、公開鍵暗号は、公開鍵と秘密鍵を使う。そして、公開鍵は公開するのだ。秘密鍵は秘密にして大事にしまっておく。 両者の根本的な違いは、公開鍵を公開すること。 従って、共通鍵暗号方式では必須であった秘密鍵の搬送が、公開鍵暗号方式では不要となる。 ここに、決定的な相違があるのだ。
分かりやすくするため、例を掲げる。
共通鍵暗号の例：シーザー暗号
シーザー暗号（Caesar cipher）は、ジュリアス・シーザーが使ったと言われる暗号だ。紀元前１００年くらい前に使われた。 シーザー暗号では、平文（ひらぶん：plaintext）で使われているアルファベットを、一定の文字数だけ「ずらす」ことによって暗号化(encript)する。
例えば、３文字ずらすとすると、平文の"EIGHT"は暗号文の"HLJKW"となる。 復号化（decript）は、３文字逆にずらすことで、暗号文の"HLJKW"は平文の"EIGHT"となる。 この場合の３という数字が共通鍵である。
シーザー暗号のアルゴリズムは、非常に簡単なもので、暗号解読（criptanalysis）も比較的に容易である。 盗聴者は、高々２６通りの総当たりで解読できる。 このように、すべての鍵の候補をためしてみるという解読方法を、総当たり法、しらみつぶし法などと呼ぶ。
公開鍵暗号の例は、ＲＳＡ
ＲＳＡは、公開鍵暗号のアルゴリズムの１つだ。ＲＳＡという名前は、３人の開発者の名前、ロン・リヴェスト（Ron Rivest）、アデイ・シャミア(Adi Shamir)、 レナード・アドルマン（Leonard Adelman）の頭文字をとってつけられた。１９８３年、アメリカにおける特許をとったが、現在は期限切れである。
その概要は、ある個人が、秘密鍵と公開鍵という二種類の鍵を所有し、 秘匿に利用する場合は、どの通信相手にも公開鍵で暗号化させ、受信した暗号文を自分だけが持つ秘密鍵で復号する。
こうすれば、秘密鍵を搬送しなくてよいことになり、搬送中に盗まれたり、漏れたりすることはなくなり、 搬送が必要な共通鍵暗号方式に比べ秘匿性が格段に高くなるのだ。
ＲＳＡは、素数の見つけ難さと素因数分解の困難性を利用している。「素数」とは、それ自体しか約数を持たない整数のこと。 整数一覧を見たい方はこちらを参照されたい。
具体的にやってみよう。尚、掛け算を表す記号は「＊」、べき乗は「＾」と表記することにする。
以上により、
公開鍵 Ｎ＝６８８７　　ｅ＝１３
秘密鍵 d＝５１７
と暗号が決まってくる。
ｐ＝７１，ｑ＝９７、φ（Ｎ)＝６７２０のどれが分かってもｄを計算することができるので、ｐ，ｑ，φ（Ｎ)，ｄは、すべて秘密であるが、 秘密通信や認証に使うのはｄ＝５１７だけである。
秘密通信を実際やってみよう。
公開鍵方式の利点は、秘密鍵（復号鍵のこと）を搬送しなくてよいことにある。 搬送中に盗まれたり、漏れたりしたことは、過去、数限りないのである。 だから、デリバリ問題の解消が公開鍵方式の最大の利点である。
秘匿通信を行いたい人（ここでは「秘匿原因者」と呼ぼう。）は、先ず自分の秘密の復号鍵（上では「ｄ」）を定めてから、それに対応する暗号化鍵を計算し、 これを公開して、自分宛の暗号化文は、誰でもこの暗号化鍵で暗号化して送信できるようにする。そうすれば、秘密鍵は搬送等、外部に出ることなく、 秘匿通信を行うことができるのだ。
これが、１９７０年代以降行われているポストモダーン暗号の核心である。
このような公開鍵方式の暗号が実現できた数理マジックの種は、暗号化・復号化で使用する一方向性関数の性質にある。 一方向性関数とは、平文から暗号文を作成することは簡単にできるが、暗号文が盗まれても平文を割り出すことは困難、 即ち、順方向の計算はできるが、逆方向の計算は実際上不可能となるような関数のことである。
現在のところ、頼りになる一方向性関数は、オイラー関数である。もう一つ離散対数関数というのもあるがここでは省略する。
オイラー関数は、
φ（Ｎ)＝（p−１)（q−１）
であるが、p、q　が与えられれば、簡単にφ（Ｎ)を求めることができるが、逆に、φ（Ｎ)が与えられて、ｐ，ｑ　を求めることは簡単ではない。 この　ｐ，ｑ　を求める行為を「素因数分解」とよぶ。 コンピュータを使っても、効率よく素因数分解するアルゴリズムは見つかっていない。 この事実が数理マジックの種なのだ。
だが、技術は日進月歩、何時素数の秘密が解き明かされるか分かったものではない。 アメリカ国家安全保障局（ＮＳＡ）は、数学者の学会がある度に、エージェントを送り素数とリーマン予想に関する論文をチェックしているそうだ。 我が国でも、少なくとも銀行協会あたりは、世界の数学論文をモニタしているはず。 そうでなければ、素数の秘密が解き明かされた時、大損をする羽目に陥るからだ。 大損で済めばいいが、下手すると事業継続が不可能になる、・・・それほどインパクトのある出来事と言えると思う。
以上、説明の便宜上、小さな数を例として用いているが、実際には、ｐ，ｑは十進数で１５０〜３００桁くらい、 従って、Ｎは３００〜６００桁くらいのとてつもない大きな数が用いられている。 これでは、スーパーコンピュータ回しても現実的な時間では、素因数を割り出すことはできない。 このことは、公開鍵から秘密鍵を割り出すことはできないことを意味し、暗号を意味あるものとしているのである。
人間の悪意に対抗するための工学的体系としての暗号技術、今後、ますます発達すること間違いないだろう。 ネット社会を担保する技術として不可欠の技術であり、孫やひ孫にも、やりがいのある専門分野として、推奨できるのではなかろうか。
以上、公開鍵暗号方式を「秘匿」に使うとした場合について説明したが、セキュリティには、「秘匿」のほか、「認証」という使われ方がある。 別の言葉でいえば、「本人確認」のことである。
ここで、この「認証」について説明しよう
ある個人が、秘密鍵と公開鍵という二種類の鍵を所有し、
  1. 秘匿に利用する場合は、どの通信相手にも公開鍵で暗号化させ、受信した暗号文を自分だけが持つ秘密鍵で復号する。
  2. 認証に利用する場合は、まず、秘密鍵で署名文を作成（暗号化すること）し、どの相手にも公開鍵で検証（復号化すること）させる。
ということになり、いずれの場合も秘密鍵は自分のみで使い、公開鍵は他の多数の人々に使わせている。
１と２を比べれば、秘密鍵と公開鍵の使い方が逆になっているこに気がつく。 「認証」では、秘密鍵で暗号化した文章が公開鍵で復号化できたという事実が、本人確認そのものなのだ。 何故なら、本人（秘密鍵を保持している人）にしか暗号化できないのだから。
このように、よく考えもしたものだと思う。頭の中がひっくり返るようだけど面白い。 数独パズル（朝日新聞の毎土曜日のＢｅ紙上にある）にはかなわないかもしれないが。
素数については、近年面白い発見があった。
１９９０年代、リーマン予想で有名な素数の零点（ゼータ関数の自明でない零点の間隔）と原子核のエネルギーレベルの間隔が一致することが発見されて以来、 素数研究が急速に進んでいるそうだ。 そして、今や「非可換幾何学」という極めて可能性のある学問分野で素数を物理学に取り込む研究や超弦理論などへの応用などの研究が進んでいるとか。 なんでも、「非可換幾何学」とは、宇宙空間が微細構造を持つとして、微細構造を持つ空間を取り扱う幾何学だそうだ。 微細構造を持つとは、空間をミクロな目で眺めれば、そこは滑らかではなく切れ目がある空間ということになるとか。・・・段々面白くなるよね。
中には、こんな予想もあるとか。 リーマン予想が証明されたとき、森羅万象を説明する万物の法則も解明されると。
そんな大発見ではないが、リーマン予想が証明されたとき、暗号通信、即ち、インターネットのセキュリティに大穴が空くだろう。 だが、そんなことで、リーマン予想が証明されないことを願ったりはしない。万物の法則の発見の方が価値があるから。
　
　
　
（参考＆引用：講談社学術文庫「暗号」辻井重男著、ソフトバンク　パブリッシング「暗号技術入門」結城浩著、など）
　
　
　
　
　
コメントはこちらへメールして下さい。その際、文中冒頭に「ＨＰコメント」と記して下さい。 Email
　
＜コメント欄＞　　　当欄は上記のメールをコメントとして掲示するものです。