RSA暗号

質問

どのトピックかがいまいちわからないのでこのトピックに質問を載せさせて頂きます。

いま、大学の課題でRSA暗号をパソコンで実装する

という課題に取り組んでいます。
２桁以上の素数を選んで、その素数から暗号化鍵と復号化鍵を選んでアスキーコードを暗号化するという初歩的なものなので、実用性は全くありませんが…

プログラムはできたのですが

暗号化鍵と復号化鍵を生成して

暗号化を行って複合化を行うと

元の平文に戻らない鍵のペアがあるらしいのです。

そういうときってあるのでしょうか？

回答No.2

koinobori7 · ベストアンサー

２．RSAの計算
　平文を一定長さのブロックに分け、各ブロックを大きな数とみなし、この数よりも大きな数　N　をとります。素数ｐ、ｑをその積ｎ(n=pq)がNよりも大きくなるように選びます...

この計算で、
ｎがNより小さいと
計算が　n　を法とした計算なので、
N　以外の数が　ｎ　を法として合同になります。
そうすると、復号化したとき、
N　ではなく、N　を　ｎ　で割ったときの余りが出てきて
元に戻らない。

参考URL：

http://www002.upp.so-net.ne.jp/uyamakc4/RSAFFT/RSAFFT.htm

お礼

ご回答ありがとうございます

考えてみれば当たり前の事ですよね…
数学は整数論は苦手なので
こんな基本的な事もわからないなんて
まだまだ勉強不足です

回答No.3

Tacosan

すげ～, #2 がまさにドンピシャ. ひょっとして超能力者?
そこに書いてあることがすべてなんだけど, RSA はすべて剰余系で計算をおこなうから, 使ってる法より大きい数値は当然扱えません.

お礼

どんぴしゃですね
その部分を直して、暗号化鍵と復号化鍵のとる範囲をもう少し大きくしてみたら、問題なく暗号化と復号化が行えました。

「らしい」と書いたのは
自分が暗号数学をそこまで詳しく勉強したわけではなかったので、もしかしたら
すごく簡単なミスで、断定的に「戻らない」と言ってしまうとちゃんと勉強してる方々に悪い気がしたからです…

案の定、簡単なミスだったようです…

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

回答No.1

Tacosan

例をあげることはできますか?
あくまで理論的には「暗号化鍵と復号化鍵が正しく対応していれば戻るはず」です. なので, 正しいペアができているかどうかをまず調べてみてはどうでしょうか.
それにしても, 「らしい」ってどういうことなんだろう.

補足

例えばですね。
二つの素数をpq
n=pq
φ(n)=(p-1)(q-1)
e:暗号化鍵
d:複合化鍵
ed=1 (mod φ(n) )

とすると
p:17
q:5
n:85
e:13
d:5

なのですが…
この時
平文:14 暗号文:39
複合化後の文:14
と正しい場合があるけども
平文:89 暗号文:4
複合化後の文:4

なるようだったんですが、
調べてみたらなんとなく原因分かってきました(^^;)

**** 計測結果 ****
…
暗号文を復号化をしたもの:79 == 平文:79
平文:80 暗号文:65
暗号文を復号化をしたもの:80 == 平文:80
平文:81 暗号文:81
暗号文を復号化をしたもの:81 == 平文:81
平文:82 暗号文:22
暗号文を復号化をしたもの:82 == 平文:82
平文:83 暗号文:53
暗号文を復号化をしたもの:83 == 平文:83
平文:84 暗号文:84
暗号文を復号化をしたもの:84 == 平文:84
平文:85 暗号文:0
暗号文を復号化をしたもの:0 == 平文:85
平文:86 暗号文:1
暗号文を復号化をしたもの:1 == 平文:86
平文:87 暗号文:32
暗号文を復号化をしたもの:2 == 平文:87
平文:88 暗号文:63
暗号文を復号化をしたもの:3 == 平文:88
平文:89 暗号文:4
暗号文を復号化をしたもの:4 == 平文:89
平文:90 暗号文:20
暗号文を復号化をしたもの:5 == 平文:90
平文:91 暗号文:61
暗号文を復号化をしたもの:6 == 平文:91
平文:92 暗号文:57
暗号文を復号化をしたもの:7 == 平文:92
平文:93 暗号文:43
暗号文を復号化をしたもの:8 == 平文:93
平文:94 暗号文:59
…

平文≧ｎ
となるときは正しく戻らないようです(^^;)

わざわざこの質問の為に時間割いてくれてありがとうございました！