23 :名無しさん 08/07/28 15:29 ID:32Cgp4NymY (・∀・)ｲｲ!! (1)

ttp://ruffnex.oc.to/kenji/xrea/rsa.txt
を読んでやってみた。

＞2つの大きな素数 p, q を選びます。
＞それらを掛けたものを n とします。
＞n = p*q

＞2. 暗号化
＞m = c^e ( n を法とする世界 )

と書いてあったから、多分nは91なんだろうと考えて、
91=13*7で
p=13
q=7
とした。

＞p, q それぞれから 1 減算した値同士のの最小公倍数を求めそれをMとします。
＞M = lcm( (p-1), (q-1) )

M=lcm(12,6)
M=12

＞d と M の最大公約数をとります。
＞( gcd(a, b) は a と b の最大公約数を表していると考えてください )

＞1 = gcd( d, M )

から
1=gcd(d,12)
1から一つずつ計算してみたらd=5だと思った。

＞e * d = 1 ( M を法とする世界 )
＞を満たす e を求めます。

e*5=1 (12を法とする世界)
これを
e=(12a+1)/5 　 　 [aは任意の実数]
でa=2のときに右辺が5になったから
e=5

ここまでで、
公開鍵 n=91、e=5、秘密鍵 d=5 を得た。



＞平文を c と置き、暗号文を m と置きます。

＞では 92 を秘密鍵で復号化してみましょう。
＞d = 19, n = 143 ですね。
＞n は公開鍵ですが暗号化にも復号化にも使用します。

＞c = m^d ( n を法とする世界 )

m=32 の平文を求めると、

c=m^d=32^5
電卓で計算すると、
c=33554432
cを91で割ると368730.…
(余りが欲しかったので小数点以下を無視)。
91*368730=33554430
よってcは91を法とする世界では
33554432-33554430=2
となる。
以下、8、13、4、5も同様の手順で求めて、
「32　8　13　4　5」 はそれぞれ「2　8　13　23　31」となる。

ってことを紙とディスプレイと電卓駆使して頑張った。
確かに高校数学レベルの四則演算のみで求められるね。

現在このスレッドには書き込みできません。