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

Question

暗号方式は、発信者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暗号方式の考え方をご存じの方ご教示いただけると助かります。

ikutana · Accepted Answer

質問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を求めることはできません。

Kon1701 · Answer

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

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

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

質問1：Bさんだけが復号可能なのは、3*11の答を知っているからです。

RSA暗号を例にしておられますが、公開鍵方式の暗号はいくつもあり、暗号方式としては同じようなものです。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング