公開鍵暗号　RSAについて

解決済

質問者：mocha100
質問日時：2008/09/15 12:39
回答数：3件

こんにちは、

RSAの説明には、

公開鍵(a,N)
秘密鍵(b,N)
N＝素数ｃ×素数ｄ

を用意した場合、a,c,dを決定できれば、ｂを導いて秘密鍵を導くことができます。

とあります。N、ｃ、ｄの関係はわかりますが、a,bは何でしょうか？

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (3件)

ベストアンサー優先
最新から表示
回答順に表示

No.3ベストアンサー

回答者： R_Earl
回答日時：2008/09/30 04:26

> 具体的に、どのような数字がこの条件を満たすのでしょうか？但し、例なので、大きい数字で無くても結構です。

c = 31、d = 13でやってみます（この場合、N = cd = 403です。）
c - 1 = 30、d - 1 = 12なので、L = (30と12の最小公倍数) = 60
よって、

ab = 1 (mod 60)

となります。
abは60で割ると余り1なので、abの値として考えられるのは

ab = 61, 121, 181, 241, 301, 361, 421, 481, ……

となります。こうなるaとbの組を探します。

ab = 61の時、61 = 1×61なので、(a, b) = (1, 61)または(a, b) = (61, 1)
ab = 121の時、121を素因数分解すると11×11なので。(a, b) = (11, 11)となります。
また、121 = 1×121なので、(a, b) = (1, 121), (121, 1)もOKです。
a = 1またはb = 1となる組はいくらでも作れますが面白くないので、
そうならない他の(a, b)の組を紹介します。
ab = 301の時、301を素因数分解すると7×43なので(a, b) = (7, 43), (43, 7)。
ab = 361の時、361を素因数分解すると19×19なので(a, b) = (19, 19)。
ab = 481の時、481を素因数分解すると13×37なので(a, b) = (13, 37), (37, 13)となります。

一応これらの鍵で暗号化、復号化が正しくできるかどうかは確認済みです。
平文として利用可能なのは0～402です。
なので、この0～402の数値を順番に(a, N)で暗号化して暗号文を生成し、
その暗号文を(b, N)で復号化して、復号化された数値ともとの平文を比較しました。

ちなみに公開鍵暗号(RSA暗号も含む)は通常、公開鍵で暗号化し、秘密鍵で復号化しますが、
RSA暗号に関しては秘密鍵で暗号化し、公開鍵で復号化することもできます。
今までの計算結果を見ると、公開鍵に使われるaと秘密鍵に使われるbは交換しても大丈夫そうですよね。