公開鍵暗号 RSAについて

質問

こんにちは、

RSAの説明には、

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

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

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

回答No.3

R_Earl · ベストアンサー

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

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は交換しても大丈夫そうですよね。

お礼

お返事有り難う御座います。

詳しい説明でよく解りました。

回答No.2

R_Earl

c-1とd-1の最小公倍数をLとおいた時、
Lを法とした合同式において、aとbは互いに逆数の関係になります。
つまり

ab = 1 (mod L)

あるいは

abをLで割ったあまりが1になる

となります。

補足

お返事有り難う御座います。

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

回答No.1

Toshi0230

Wikipediaに鍵生成の方法が記載されています。ご参考まで

参考URL：

http://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7#.E9.8D.B5.E7.94.9F.E6.88.90

補足

お返事有り難う御座います。

少しわかりました。