公開鍵暗号の作り方                   戻る

 高度情報化社会の現在において、いろいろな情報を、インターネットを通して送受信する機
会が増えた。基本的に、インターネットの世界は無政府状態なので、互いに規律を設け、互い
の安全を自分自身で守らなければならない。当然、その世界には規律破りのものが存在しう
る。取り交わされるいろいろな情報が、第三者に密かに閲覧されることも起こりうる。政府・企
業・学校内のホストコンピュータに侵入し、いろいろ悪さをするという事件も跡を絶たない。
 最近、LANの普及により、パソコン同士がつながれるようになり、その種の事故が身近でも
起こるようになった。他人のパソコンが、自分のパソコンの一つのフォルダでもあるかのように
アクセスし、簡単に情報のやりとりが行えるという利点はあるが、危険性も隣り合わせである。
 フォルダにパスワードを設定しても、あまり安心はできない。神奈川県立神奈川工業高等学
校で、校内DATAのインターネットへの流出事故があったが、フォルダにパスワードを設定する
のを忘れたことにより、校内LANのパソコン(生徒用も含めて)から無防備の状態だったらしい。
 このような事故は、セキュリティーの初歩の初歩を忘れた事故で論外であるが、本人が気が
つかないうちに、DATAを盗用されるような場合が一番怖い。インターネットの世界では、情報
は全て、第三者が閲覧しているものと考えて対処したほうがいいだろう。
 しかし、買い物などをして、その支払い手段として、クレジットカードの番号とか、どうしても送
信しなければならないDATAも存在する。このような場合、最近のシステムでは、デジタル署名
とか、DATAを暗号化して送信するようになっているので、一応安心できるようにはなってきた。

 このページでは、暗号化の一つの方式として知られる公開鍵暗号について、その作り方とそ
の理論的根拠となる数論の世界を紹介したい。
 公開鍵暗号(Public Key)は、1976年カリフォルニア、スタンフォード大学の研究者(ヘルマ
ン、W.ディフィー、R.マークル)によって、公表されたものである。これまでの暗号は、送信者、
受信者の双方に、暗号についての取り決めが必要であった。(対称的暗号という。) しかし、こ
の公開鍵暗号は、受信者のみが解読の鍵を持っている。(非対称的暗号という。) 世界中のど
んな人にも、暗号化する方法を公開しており、誰でもが暗号を送信できるのだが、その暗号を
解読できるのは、解読の鍵を持っている受信者のみなのである。解読できる者を特定化してい
る点で、優れた方式だと思う。

鍵の作り方
(1) 十分大きな素数P、Qを選び、その積PQをnとする。
(2) (P−1)(Q−1)と互いに素な整数eを選ぶ。暗号化鍵として、「n」 と 「e」 を公開する。

暗号化の方法
   整数Kに対して、Keをnで割った余りをRとする。Kを暗号化したものがRとなる。

解読の方法(合同式の記号≡については、こちらを参照)
(1) (P−1)(Q−1)=φ(n)として、de≡1(mod φ(n))となる整数dを求める。
(2) このとき、R≡K (mod n)となり、暗号化前の整数Kが復元される。

例 2つの素数2と11を考える。(計算を簡略化するため、考える素数は小さいものとした。)
 このとき、n=22で、(2−1)×(11−1)=1×10=10と互いに素な整数として、e=3とする。
 暗号化鍵として、n=22、e=3を暗号を作る側に公開する。
  今、「BAG」という英単語を暗号化して送ることを考える。

 アルファベットと数字が右の表のように対応しているものとする。
(これは、送信者、受信者とも了解しているものとする。)
 2の3乗は8で、22で割った余りは、8 ・・・・Hが対応
 1の3乗は1で、22で割った余りは、1 ・・・・Aが対応
 7の3乗は343で、22で割った余りは、13 ・・・Mが対応
A E ・・・
・・・

  従って、「HAM」という英単語を送ることになる。
 「HAM」という英単語を受信した側は、暗号解読の秘密鍵φ(n)を知っているので、次のよう
な手順で、元の英単語を知ることができる。(nの値は公開しているが、十分大きいnを2つの素
数の積に分解することは、ほとんど不可能なので、φ(n)の値が他人に知られることはない!)
 3d≡1(mod 10)となる整数dを求めると、d=7 である。
(基本的には、ユークリッドの互除法を用いて、求められる。互除法については、こちらを参照)
 8の7乗は2097152で、22で割った余りは、2 ・・・・Bが対応
 1の7乗は1で、22で割った余りは、1 ・・・・Aが対応
 13の7乗は62748517で、22で割った余りは、7 ・・・Gが対応
  このようにして、元の「BAG」という英単語が再現され、他人から知られることなく、受け取れ
 るわけである。

 解読不能な暗号を作るために、公開鍵暗号では、次のことが前提になっている。

十分大きな整数を、2つの素数の積に分解することは、コンピュータをもってしても不可能

 現在では、因数分解の方法はとんとん拍子に改良され、100桁以上の整数を扱わなければ、
安心できないという。
 また、上の例のように、1文字対1文字の置換暗号では、どうしても言語の特徴が暗号文に反
映されるので、解読のためのヒントを与えてしまう。例えば、英語で一番頻繁に現れる文字は「e」
であり、3文字の英単語だと「the」なので、文の構造が読み取られてしまう。この対策として、元
の文の各文字がいつも同じ文字に置換されないようにする方法もある。1つの単語を考え、暗号
化された文の下に繰り返し挿入すればよい。(このような暗号文を、ヴィジュネル暗号文という。)
しかし、これも万全とはいえない。
 現在の暗号理論では、いくつかのまとまった文字を一括して暗号化し、容易に解読されないよう
に工夫しているらしい。

公開鍵暗号方式の数学的背景

 nを1より大きい整数とする。1からn−1までの整数のうち、nと互いに素なものの集合を、M
とする。このとき、Mに属する要素の個数を、φ(n)で表す。φ(n)を、オイラーの関数という。

例 n=6のとき、
     1,2,3,4,5 のうちで、6と互いに素な整数は、1,5 のみ。よって、φ(6)=2
  n=15のとき、
     1,2,3,・・・,15 のうちで、15と互いに素な整数は、1,2,4,7,8,11,13,14。
    よって、φ(15)=8

定理  n=PQ (P、Qは素数)のとき、φ(n)=(P−1)(Q−1)

  証明は、易しい。全体の個数PQから、Pの倍数(Q個)、Qの倍数(P個)をひき、PかつQの
倍数(1個)を加えればよい(個数定理)。
この定理により、公開鍵暗号で本質的な数φ(n)は、実は、nのオイラー関数であった。

定理  (a,n)=1のとき、aX≡1(mod n) となるXが存在する。

  証明は、ユークリッドの互除法より明らかである。
この定理により、公開鍵暗号の解読に必要な数dの存在が保証される。

定理(フェルマーの定理)  (a,n)=1のとき、aφ(n)≡1(mod n)

 (証明) (a,n)=1、(b,n)=1 ならば、(ab,n)=1 なので、集合Mは、n を法として乗法
     について閉じている。そこで、Mの要素Xに対して、g(X)=(aXを n で割った余り) に
     より、MからMへの写像を考える。(a,n)=1 から明らかに、写像 g は単射である。
     また、Mは有限集合なので、g は全射となる。
      異なるφ(n)個のMの要素 X、X、X、・・・、Xφ(n) の g による像の積を考えると、
      aφ(n)・・・X となるが、gは全単射なので、これは、X・・・X に等しい。
     よって、aφ(n)≡1 (mod n) が成り立つ。
  (この証明より、もっと易しい証明を希望される場合は、こちらを参照)

この定理により、暗号復元の可能性が保証される。
 実際に、整数Kに対して、Keをnで割った余りをRとするとき、
       R≡K (mod n)
であることが次のように示される。
 de≡1(mod φ(n))となる整数dが存在するので、de=mφ(n)+1(mは整数)とかける。
 (K,n)=1のとき、フェルマーの定理により、
       R≡Kde=(Kφ(n)×K≡K (mod n)
 (K,n)≠1のとき、nの約数は、1,P,Q,n なので次の場合に分けられる。
       K≡0 (mod n) ならば、R≡Kde≡0≡K (mod n)
       K≡0 (mod n)でないとする。
         K≡0 (mod P)のとき、
            R≡Kde≡0≡K (mod P)
            さらに、(K,Q)=1なので、フェルマーの定理により、
            R≡Kde=(Kφ(n)×K
                        =(K(Q−1)m(P−1)×K
                        ≡K (mod Q)
              よって、R≡Kde≡K (mod n)
         K≡0 (mod Q)のときも同様で、(K,P)=1から、
                   R≡Kde≡K (mod n)
 以上から、常に、Rのd乗≡K (mod n) となり、Kの値が復元される。
(参考文献:M.ラインズ 著 片山孝次 訳 数、数、・・・不思議なふるまい(岩波書店)
        戸川 美郎 著 合同式の数学(啓林館))

(追記) 「RSA40」について、GAI さんからの投稿です。(平成27年3月4日付け)

 公開鍵 n=2955382125840746099819023667504442929041 :(mod n の意味)
       e=1999  :(メッセージ)e≡c  (mod n)
による暗号文c=1701630553066808231561404845128077448255 を電送しますから、これを
読み取って下さい。
 なお読み取りキーコードは、アルファベット26文字を
A:01 、B:02 、C:03 、・・・・・ 、Z:26 、空白:00
で定めています。

 らすかるさんからのコメントです。(平成27年3月4日付け)
 RSA暗号は概略の仕組みは知っていましたが、実際に自分で計算してみたのは初めてで
す。「HARUYO HAYAKU KOI」で合ってますよね?

 GAI さんからのコメントです。(平成27年3月4日付け)
 ハイ、このメッセージを秘密裏に送りました。読み取ってくれる人が現れたので、私のRSA
暗号の理解で大丈夫だと安心しました。もちろん、らすかるさんにはRSA40くらいでは、途中
で解読されてしまい秘密も保てなくなりますが、原理的に、300〜400位の桁数のものを公開
鍵にすれば、秘密も保てそう。(多分)これが現代社会のeコマースを支えていることを考える
と、何も役立たない代名詞のように言われている純粋数学(特に数論)がこれほど日を浴び
る時代はないのではあるまいか。原理の性質に着目していたフェルマーやオイラー、ガウス
が果たした役割は計り知れない。
 この原理を暗号に利用出来ることに気づけたリヴェスト(RSA のRにあたる人物)の着眼点
もすばらしいが、これらは全て前者の人達の遺産があればこそである。しかし、急速に発展
するコンピュータの能力のこれからを考えると果たしてRSA暗号も何時までも安心とはいって
おれない時代がくるのではないでしょうか。

 らすかるさんからのコメントです。(平成27年3月4日付け)
 基本的な考え方は合っていると思いますが、実際の手順は違いますよね?私は、
・暗号文を送りたい人が受け手にnとeを請求する
・受け手がnとeを送り手に伝える
・送り手がそのnとeを使って平文を暗号化して受け手に送る
・受け手はnの素因数を使ってそれを解読する
 (nの素因数分解を知らない他の人には解読できない)
と理解しています。

 GAI さんからのコメントです。(平成27年3月4日付け)
 表現したかったことは、もし私と第三者の間で、情報のやり取りをしている中にRSA暗号の
意味を理解している人物が、情報に流れているe、n、cの値を手に入れ(やり方はわかりま
せんが技術的には出来ると思います。)、しかもたちどころにnの因数分解(この場合2つの
素数になる。)を達成する手段さえ持っていれば、言ってみれば誰でも元のメッセージを復元
できることができる。
 この流れのイメージとして、トランプ(ただしn枚組の枚数)で想像してみると、送りたいメッ
セージを書いたカードを一番上に置き、一定のシャッフルをe回繰り返してこの中に紛れ込
ます。このとき一番上にはcのカードが来たので、このカードの情報を相手に伝える。(暗号
文を送る)受け取った相手は、c、e、n(n=p*q)の情報から、中に埋もれてしまった目的のカ
ードを一番上に現れるようにシャッフルする回数d(eの逆数に相当するもの)を計算できる。
(ですから3つの素数p,q,rからなるn=p*q*rでも可能ですよね。)
これから、今一番上にはcのカードがある状態から更にd回のシャッフルを行うことによって
一番上に本当に相手が伝えたかった目的のカードが出現する。
というイメージで自分の趣味に照らし合わせて理解しました。(どこか間違った点がありました
ら御指摘下さい。)
 この理解で本当にメッセージが伝わるものなのか試してみたかったので、実験で出題した
らRSAの構造を十分理解されていた、らすかるさんが見事ハッカーの役を演じて頂いたとい
う顛末を表現したかったのです。2者間でのやり取りは、らすかるさんが示されたことと認識
しています。