公開鍵暗号の作り方　　　　　　　　　　　　　　　　　　　

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

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

鍵の作り方
（１）　十分大きな素数Ｐ、Ｑを選び、その積ＰＱをｎとする。
（２）　（Ｐ−１)(Ｑ−１)と互いに素な整数eを選ぶ。暗号化鍵として、「ｎ」 と 「e」 を公開する。

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

解読の方法（合同式の記号≡については、こちらを参照）
（１）　（Ｐ−１)(Ｑ−１)＝φ（ｎ）として、ｄe≡１（mod　φ（ｎ））となる整数ｄを求める。
（２）　このとき、R^ｄ≡K　（mod　ｎ）となり、暗号化前の整数Kが復元される。

例　２つの素数２と１１を考える。（計算を簡略化するため、考える素数は小さいものとした。）
　このとき、ｎ＝２２で、（２−１)×(１１−１）＝１×１０＝１０と互いに素な整数として、e＝３とする。
　暗号化鍵として、ｎ＝２２、e＝３を暗号を作る側に公開する。
　　今、「ＢAＧ」という英単語を暗号化して送ることを考える。

　　従って、「ＨAＭ」という英単語を送ることになる。
　「ＨAＭ」という英単語を受信した側は、暗号解読の秘密鍵φ（ｎ）を知っているので、次のよう
な手順で、元の英単語を知ることができる。（ｎの値は公開しているが、十分大きいｎを２つの素
数の積に分解することは、ほとんど不可能なので、φ（ｎ）の値が他人に知られることはない！）
　３ｄ≡１（mod　１０）となる整数ｄを求めると、ｄ＝７ である。
（基本的には、ユークリッドの互除法を用いて、求められる。互除法については、こちらを参照）
　８の７乗は２０９７１５２で、２２で割った余りは、２　・・・・Ｂが対応
　１の７乗は１で、２２で割った余りは、１　・・・・Aが対応
　１３の７乗は６２７４８５１７で、２２で割った余りは、７　・・・Ｇが対応
　　このようにして、元の「ＢAＧ」という英単語が再現され、他人から知られることなく、受け取れ
　るわけである。

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

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

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

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

　ｎを１より大きい整数とする。１からｎ−１までの整数のうち、ｎと互いに素なものの集合を、Ｍ
とする。このとき、Ｍに属する要素の個数を、φ（ｎ）で表す。φ（ｎ）を、オイラーの関数という。

例　ｎ＝６のとき、
　　　　　１，２，３，４，５ のうちで、６と互いに素な整数は、１，５ のみ。よって、φ（６）＝２
　　ｎ＝１５のとき、
　　　　　１，２，３，・・・，１５ のうちで、１５と互いに素な整数は、１，２，４，７，８，１１，１３，１４。
　　　　よって、φ（１５）＝８

定理　　ｎ＝ＰＱ （Ｐ、Ｑは素数）のとき、φ（ｎ）＝（Ｐ−１)(Ｑ−１）

　　証明は、易しい。全体の個数ＰＱから、Ｐの倍数（Ｑ個）、Ｑの倍数（Ｐ個）をひき、ＰかつＱの
倍数（１個）を加えればよい（個数定理）。
この定理により、公開鍵暗号で本質的な数φ（ｎ）は、実は、ｎのオイラー関数であった。

定理　　（ａ，ｎ）＝１のとき、ａＸ≡１（mod ｎ） となるＸが存在する。

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

定理（フェルマーの定理）　　（ａ，ｎ）＝１のとき、ａ^φ（ｎ）≡１（mod　ｎ）

　（証明）　（ａ，ｎ）＝１、（ｂ，ｎ）＝１ ならば、（ａｂ，ｎ）＝１ なので、集合Ｍは、ｎ を法として乗法
　　　　　について閉じている。そこで、Ｍの要素Ｘに対して、ｇ（Ｘ）＝（ａＸを ｎ で割った余り） に
　　　　　より、ＭからＭへの写像を考える。（ａ，ｎ）＝１　から明らかに、写像 ｇ は単射である。
　　　　　また、Ｍは有限集合なので、ｇ は全射となる。
　　　　　　異なるφ（ｎ）個のＭの要素　Ｘ１、Ｘ２、Ｘ３、・・・、Ｘφ(ｎ) の ｇ による像の積を考えると、
　　　　　　ａ^φ（ｎ）Ｘ１Ｘ２・・・Ｘｎ となるが、ｇは全単射なので、これは、Ｘ１Ｘ２・・・Ｘｎ に等しい。
　　　　　よって、ａ^φ（ｎ）≡１　（mod　ｎ） が成り立つ。
　　（この証明より、もっと易しい証明を希望される場合は、こちらを参照）

この定理により、暗号復元の可能性が保証される。
　実際に、整数Kに対して、K^eをｎで割った余りをRとするとき、
　　　　　　　Ｒ^ｄ≡Ｋ　（mod　ｎ）
であることが次のように示される。
　ｄe≡１（mod　φ（ｎ））となる整数ｄが存在するので、ｄe＝ｍφ（ｎ）＋１（ｍは整数）とかける。
　（K，ｎ）＝１のとき、フェルマーの定理により、
　　　　　　　Ｒ^ｄ≡K^ｄｅ＝（Ｋ^φ（ｎ））^ｍ×Ｋ≡Ｋ　（mod　ｎ）
　（K，ｎ）≠１のとき、ｎの約数は、１，Ｐ，Ｑ，ｎ なので次の場合に分けられる。
　　　　　　　K≡０　（mod　ｎ）　ならば、Ｒ^ｄ≡K^ｄｅ≡０≡Ｋ　（mod　ｎ）
　　　　　　　K≡０　（mod　ｎ）でないとする。
　　　　　　　　　K≡０　（mod　Ｐ）のとき、
　　　　　　　　　　　　Ｒ^ｄ≡K^ｄｅ≡０≡Ｋ　（mod　Ｐ）
　　　　　　　　　　　　さらに、（Ｋ，Ｑ）＝１なので、フェルマーの定理により、
　　　　　　　　　　　　Ｒ^ｄ≡K^ｄｅ＝（Ｋ^φ（ｎ））^ｍ×Ｋ
　　　　　　　　　　　　　　　　　　　　　　　　＝（Ｋ^{（Ｑ−１）}）^{ｍ（Ｐ−１）}×Ｋ
　　　　　　　　　　　　　　　　　　　　　　　　≡Ｋ　（mod　Ｑ）
　　　　　　　　　　　　　　よって、Ｒ^ｄ≡K^ｄｅ≡K　（mod　ｎ）
　　　　　　　　　K≡０　（mod　Ｑ）のときも同様で、（Ｋ，Ｐ）＝１から、
　　　　　　　　　　　　　　　　　　　Ｒ^ｄ≡K^ｄｅ≡K　（mod　ｎ）
　以上から、常に、Ｒのｄ乗≡K　（mod　ｎ）　となり、Kの値が復元される。
（参考文献：Ｍ．ラインズ　著　片山孝次　訳　数、数、・・・不思議なふるまい（岩波書店）
　　　　　　　　戸川　美郎　著　合同式の数学（啓林館））

（追記）　「ＲＳＡ４０」について、ＧＡＩ さんからの投稿です。（平成２７年３月４日付け）

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

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

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

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

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


（追記）　平成３０年２月１２日付け

　次の問題は公開鍵暗号のモデルとも言える問題である。

問題　５１より小さい自然数 ａ について、ａ¹¹を５１で割ったら余りが１３になった。
　　　このとき、ａ の値を求めよ。

（解）　５１＝３×１７　なので、　ａ¹¹＝５１×Ｑ＋１３　より、

　　　ａ¹¹を３で割った余りは１なので、ａ＝３ｓ＋１　と書ける。

　　　ａ¹¹を１７で割った余りは１３なので、

　　　　２¹¹≡８　（ｍｏｄ　１７）、３¹¹≡７　（ｍｏｄ　１７）、４¹¹≡１３　（ｍｏｄ　１７）、
　　　　５¹¹≡１１　（ｍｏｄ　１７）、６¹¹≡５　（ｍｏｄ　１７）、７¹¹≡１４　（ｍｏｄ　１７）、
　　　　８¹¹≡２　（ｍｏｄ　１７）、９¹¹≡１５　（ｍｏｄ　１７）、１０¹¹≡３　（ｍｏｄ　１７）、
　　　　１１¹¹≡１２　（ｍｏｄ　１７）、１３¹¹≡４　（ｍｏｄ　１７）、１４¹¹≡１０　（ｍｏｄ　１７）、
　　　　１５¹¹≡９　（ｍｏｄ　１７）、１６¹¹≡１６　（ｍｏｄ　１７）

　　　より、ａ＝１７ｔ＋４　と書ける。

　　　よって、ａ＝４、２１、３８　の中で、３で割って余りが１となるものは、　ａ＝４　　（終）


　この解に対して、公開鍵暗号の理論が分かっている方は次のように簡単に計算してしまう。

（別解）　１３³＝２１９７＝５１×４３＋４　より、　ａ＝４　　（終）

　実際に、　４≡１３³　（ｍｏｄ　５１）　より、　４¹¹≡１３³³　（ｍｏｄ　５１）
　　　　　　　１３⁴≡１　（ｍｏｄ　５１）　なので、　１３³²≡１　（ｍｏｄ　５１）
　　　　　　従って、　４¹¹≡１３　（ｍｏｄ　５１）　となり、題意に適する。


　上記の計算を公開鍵暗号理論をもとに検証してみよう。

　Ｐ（＝３）、Ｑ（＝１７）は素数で、ｎ＝ＰＱ＝５１　である。

　（Ｐ−１）（Ｑ−１）＝２×１６＝３２　と互いに素な整数 ｅ として、ｅ＝１１　とする。

　暗号化キーとして、　ｎ＝５１、ｅ＝１１　を公開する。

　暗号化される元の整数 ａ に対して、ａ¹¹をｎで割った余りＲ（＝１３）が ａ の暗号化に当たる。

　復号するために、ｄｅ≡１　（ｍｏｄ　φ（ｎ）＝３２　※φ（ｎ）：オイラー関数）　となるｄを求めると、

ｄ＝３　なので、　復号化　Ｒ^ｄ＝１３³＝２１９７≡４　（ｍｏｄ　５１）　により、　ａ＝４　であるこ

とが分かる。



　　以下、工事中！