ふたつ素数、11927と20903を掛け合わせれば、249310081になります。しかし、計算結果の249310081から、その因数であるふたつの素数を見つけ出すことはかなりむずかしいのです。この因数分解のむずかしさを利用した暗号化手段がパブリックキー暗号化です。
パブリックキーというのは、世間一般に公開されるキーで、ふたつの素数の積です。先ほどの例では、249310081です。私のところに暗号化メッセージを送りたい人は、私が世間一般に公開しているキー、249310081を使って、メッセージを暗号化し、私のところにメールします。
一方、私だけしか知らない番号として、パブリックキー算出のもととなった、ふたつの素数のペア、11927と20903があります。これが、私のプライベートキーです。これは、だれにも公表しませんし、パブリックキーからの逆算（因数分解）もかなり困難です。
パブリックキーで暗号化されたメッセージは、必ずプライベートキーでしか解読できないようになっています。こうして、あなたがパブリックキーを使って暗号化したメッセージは、プライベートキーをもっている私にしか解読できない情報となって、ネットワーク上を伝わってくるのです。
実際には、これらの暗号化や解読は、コンピュータがやってしまいますから、ユーザはほとんど意識する必要はありません。また、素数自体ももっと大きい、たとえば250桁の素数といったものが使われるようです。
と、長々とパブリックキー暗号化の説明をしてまいりましたが、ここからが本題です。(^^;
「ふたつの素数の積で暗号化ができて、それを解読するときにはもとの素数のペアがいる」。ここが、どうしても理解できないのです。
簡単のため、素数のペアを２と３だとします。そうするとパブリックキーは２×３で６になります。
送るメッセージも、簡単のため、文章ではなく「７」という数字を暗号化して送りたいとします。
「７」という数字を６というパブリックキーで暗号化するのには、どのような手法を使いますか？ たとえば、掛け算を考えてみましょう。７×６は４２です。こんな単純なわけはありませんよねぇ。もう一度パブリックキー６で割り算すれば、暗号化したはずの「７」がすぐ見つかってしまいます。
「７」を６で暗号化できて、しかも解読するのには２と３のペアが必要なような暗号化技術とはどういったものなのでしょうか。
しかも、この技術、逆もできるらしいのです。つまり、私がプライベートキーである２と３を使って暗号化し、あなたに暗号化メッセージを送る。あなたは私のパブリックキー６を使って、それを解読する。パブリックキー６で解読できる暗号を作成できるのは、世界中に私しかいないため、あなたはそのメッセージがたしかに私から届いたものだと確信できる、というものです。（プライベートキーは、ユニークなものが発番されるわけではありませんが、それぞれのコンピュータがランダムに選んだ、適当な桁数の素数のペアが偶然ぶつかる可能性は０に近いんだそうです。ほんとかな？）
「未来を語る」の中では、「パブリックキー暗号化は、1977年、ホィットフィールト・ディフィとマーティン・ヘルマンによって考案された。その後まもなく、べつのコンピュータ科学者たち、ロン・ライヴェスト、アディ・シャミール、レナード・アデルマンが、ＲＳＡ暗号体系の名で知られるシステムの一部として、素因数分解を用いるというアイデアを提起した」という紹介はあるのですが、最後には「ここまで、パブリックキーによる暗号化について、システムの技術的細部をはしょってごく簡単に説明してきた」としめくくられています。(;_;)
おーい、技術的細部をはしょるなよ... ＞ ビル・ゲイツ
べつにいますぐ暗号化技術が必要というわけではないのですが、「どうなってるんだろう」と考えはじめると、気になって気になってしかたがないのです。
どなたか、この暗号化について、もしくは「こんな本に載ってるよ（なんとか本の話題にもってきたゾ (^^; ）」という情報をお持ちの方は、ぜひ教えてください。
パブリックキーによる暗号化では、暗号化はできるものの、それを復号することはできないパブリックキーがみなさんに公開されます。今回ご紹介する方法では、ふたつの数ｅおよびＮが公開されます。
ここでは、例としてｅ＝７およびＮ＝１５を、私のパブリックキーとして公開することとしましょう。
みなさんは、このｅとＮを次の式に当てはめて、暗号を作成していきます。
ｅ
『暗号』＝『元の数』 ｍｏｄ Ｎ ... （１）
ｍｏｄというのは、剰余計算（余りの計算）を行うためのものです。たとえば、５を３で割ると、商が１で余りが２になりますが、この２を求める計算が剰余計算です。この場合だと、 ５ ｍｏｄ ３ ＝ ２ と書き表せます。ｍｏｄは＋、−、×、÷などとまったく同じものと考えてください。
そうすると、（１）は「『元の数』をｅ乗して、Ｎで割った余りを求める」という式であることがわかります。
それでは、具体的に８という数字を暗号化してみることにしましょう。８をｅ（＝７）乗すると、２，０９７，１５２となります。これをＮ（＝１５）で割って、余りを求めると２です。この２が、私のパブリックキーを使って作成した８の『暗号』ということになります。
この２が、ネットワークなどを経由して私のもとへとやってきます。
さて、私の手元には、今回のパブリックキーであるＮ＝１５の元になったふたつの素数ｐ＝３とｑ＝５があります。Ｎ＝ｐ×ｑとして、Ｎを算出したわけです。
プライベートキーの算出には、まず、（ｐ−１）と（ｑ−１）の公倍数Ｌを求めます。今回の場合は２（＝３−１）と４（＝５−１）の最小公倍数ということで、Ｌ＝４とします。
このＬ（＝４）に対して、「互いに素な数」（両者の最大公約数が１となるような数字）を適当に定めたものが、パブリックキーのもう一方の側であるｅ＝７だったのです。つまり、４と「互いに素」であればいいわけなので、ｅは３、５、９、１１など、なんでもいいわけです。
どのような「互いに素」なふたつの数（ここではＬとｅ）に対しても、１＝Ｌｃ＋ｅｄを満たすようなｃ、ｄが必ず存在することが知られています。今回の場合だと１＝４ｃ＋７ｄを満たすｃ、ｄのペアを求めればいいわけです。たとえば、ｃ＝−５、ｄ＝３などがそれにあたります。
こうして定めたｄ＝３が、実は私のプライベートキーなのです。
もちろん、ｃ＝−１２、ｄ＝７として、このｄ＝７をプライベートキーとしてもかまいません。（ただし、私が試してみた範囲では、ｄを負の数にするとうまくいかないようです。）
復号のための式は、次のとおりとなります。
ｄ
『元の数』＝『暗号』 ｍｏｄ Ｎ ... （２）
形式は（１）の式とほぼ同じです。（１）が「ｅ乗してＮで剰余計算」だったのに対し、（２）は「ｄ乗してＮで剰余計算」となります。Ｎはパブリックキーと同じもの、つまり、Ｎ＝１５です。
では、さっそく送られてきた『暗号』、２を復号してみましょう。
２をｄ（＝３）乗すると８です。これを１５で割って余りを求めることで、『元の数』８を得ることができます。
このように、みなさんにはｅ＝７とＮ＝１５を公開して暗号化してもらい、自分ではｄ＝３を使ってそれを復号化するわけです。このｄ＝３を定めるのに、ｐ＝３、ｑ＝５というＮの算出の元になった素数のペアが必要であるため、これが暗号化技術として機能するわけです。
逆に私の側が、プライベートキーｄ＝３を使って暗号化を行って、みなさんがパブリックキーｅ＝７を使って復号化することもできます。
もちろん、Ｎ＝１５などという小さい数字では、だれでもｐ、ｑを素因数分解できてしまうため、暗号にはなりませんね。実際には、たとえばＮ＝１１４３８１６２５７５７８８８８６７６６９２３５７７９９７６１４６６１２０１０２１８２９６７２１２４２３６２５６２５６１８４２９３５７０６９３５２４５７３３８９７８３０５９７１２３５６３９５８７０５０５８９８９０７５１４７５９９２９００２６８７９５４３５４１などという大きい桁（この場合１２９桁）の数字が公開されるわけです。
そして、暗号化と復号化に剰余計算を用いるところから、暗号化できるのはＮ未満の数値ということになります。そこで、実際の使用では、Ｎに１５５桁くらいの数を選び、２進数で５１２ビット（１０進数で約１５５桁）を１ブロックとして暗号化しているそうです。
ご紹介のあった「情報セキュリティの科学」の本には、「なぜこの方法で復号化できるのかの証明」、「べき乗計算の仕方（（Ｘ＾Ｙ） ｍｏｄ ｎ を効率よく計算する方法）」、「最大公約数の求め方」、「互いに素な数の見つけ方」、「互いに素な数からのプライベートキーｄの計算方法」などが載っています。また、暗号関係の参考図書類も紹介されています。
今回は、もう１冊、同じブルーバックスの「暗号と数理」という本も参考にしました。
====================================================================== 【書 名】暗号の数理 −作り方と解読の原理− ブルーバックス B-421 【著 者】一松 信 【発行所】講談社 【ISBN 】4-06-118021-5 【発行日】1980/03/20 初版 (1992/11/30 第16刷） 【価 格】740円 ---------------------------------------------------------------------- 本書は、古代のシーザー暗号から単文字換字暗号、多表式暗号を経て、新し く提案された公開鍵暗号系にいたるまでの歴史をたどり、数多くの秘話をま じえつつ、暗号の作成と解読の原理を解説した新しい暗号学の入門書である。 ======================================================================