公開鍵暗号方式の復号に関して質問します。

質問

暗号方式は、発信者Aさんが正当な受信者Bさんに暗号化した電文を送付し、途中で不正に傍受したCさんには電文の復号ができず、正当な受信者Bさんには復号ができるという考えかたです。

正当なる受信者Bさんには復号が可能で、不正なる傍受者Cさんには復号が不可能であるためには、BさんとCさんの間に情報格差を維持しないと駄目だと思うのですが、公開鍵方式の場合に正当なる受信者Bさんと不正な傍受者Cさんの間にどのような情報格差が存在するのでしょうか。

＝＝＝　RSA暗号の例題を考えます ＝＝＝

A：暗号の発信者
B:正当なる暗号の受信者
C:不正なる暗号傍受者

Aさんは
素数P=3
素数Q=11
を選んで、
33を法とする世界（Mod33）を利用します。

Aさんは原文を3乗し、Mod33を取った暗号文をBさんに送付しますが、ここで、公開鍵情報として、「33を法とする」および「3乗した」という二つの情報を開示して暗号を送付します。

暗号を不正に傍受したCさんは、33の素因数分解ができないために、P=3、Q=11という二つの素数を特定できず、3xD=｛nｘ（p-1｝X(Q-1)+1｝において、N=1の場合でもP,Qが分からないので、復号することがきません。
ところが正当なる受信者Bさんは、3xD=1x（3-1）ｘ（11-1）+1=21より、D=7を求め、受診した暗号を7乗することで受信電文の復号が可能となります。
　＝＝＝＝　以上例題おわり　＝＝＝＝

不正なる傍受者Cさんは素因数分解が困難であることから二つの素数P、Qの特定ができずに復号ができないことは良く理解できます。
しかし、正当なる受信者Bさんは、なぜP,Qを特定し、D=7を求めることが出来るのでしょうか。

質問１：なぜBさんだけが復号可能なのでしょうか？
質問2：Bさんは素因数分解をせずとも、P=3、Q=11という二つの素数を知ることができるのでしょうか？
質問3：素数P、Qの値を特定できなくてもD=7を知ることができるのでしょうか？

公開鍵暗号方式の根本原理が分かっていないと思われるので、公開鍵暗号方式、あるいはRSA暗号方式の考え方をご存じの方ご教示いただけると助かります。

回答No.1

ikutana · ベストアンサー

質問1：Bさんだけが復号可能なのは、3*11の答を知っているからです。逆に言うと、Aさんは知らないのです。公開鍵は「元々の受信者」であるところのBさんが作るのです。そしてそれを事前にAさんに教える必要があります。（ただし、これは秘密に送る必要はありません）

質問2：Bさんは、P=3とQ=11からPQ=33を計算した張本人だからです。掛算は容易ですが、素因数分解は困難なので、Bさん以外は3と11の積であることを知ることは困難です。

質問3：秘密鍵を容易に知るためには素数P,Qの値を特定しておく必要があります。ただし、計算すればD=7を求めることはできます。ただs，その計算は非常に計算量が多く、素因数分解と計算量がほぼ同じであることが知られています。つまり、解読者が素因数分解を出来る能力がなければ、Dを求めることはできません。

お礼

ikutanaさん、

早速に回答ありがとうございました。

＞公開鍵は「元々の受信者」であるところのBさんが作るのです。そしてそれを事前にAさんに教える必要があります。（ただし、これは秘密に送る必要はありません）

目からウロコが落ちました。
ミステリー・ドラマの種明かしを観たような感動です(笑)。

Bさんが自分で選択した素数のペアをAさんにさえも秘密しておくこところで、情報格差を維持している訳ですね！！。

このプロトコールを理解していなかったために、RSA暗号のケースで具体例を考えても、なぜ情報格差が維持できるのか理解できずに不思議に思っていました。

かれこれ15年ぐらい毎日のようにVPNを使っており、RSA暗号方式のお世話になりながら、その仕組みを知らずにおりました。
IT関係を仕事にしている専門家に聞いてみたこともあるのですが、ITの専門家でもRSA暗号方式自体を理解していわけではなくて、単なるブラックボックスとして日常的に使っているようでした。

お蔭さまで長年の疑問が一挙に解決しました。
質問してみて良かったです。

本当にどうもありがとうございました。

回答No.2

Kon1701

RSA暗号を例にしておられますが、公開鍵方式の暗号はいくつもあり、暗号方式としては同じようなものです。暗号化する鍵（公開鍵）と復号する鍵（秘密鍵）の2つがペアになっています。暗号化する鍵から復号する鍵の推測は困難です。秘密鍵は知られないように厳重に保管します。
暗号化する鍵は、公開鍵といわれるとおり、暗号化して送る人に公開します。Aさんは公開鍵をつかって暗号化し、Bさんに送ります。Bさんはペアになる秘密鍵を使って復号します。傍受したCさんは復号に使う鍵が分かりませんから復号できません。
RSA暗号は、2つの素数の積から、もとの2つの素数を求めるのが困難であることを利用しています。公開鍵暗号には、他には楕円曲線暗号などがあります。

公開鍵暗号でよくたとえられるのは南京錠です。南京錠で施錠するのは鍵が無くても錠があれば可能です。しかし、開錠するには鍵がなくてはできません。南京錠が公開鍵、鍵が秘密鍵に相当します。

お礼

ありがとうございます。