フェルマーの小定理からRSA暗号をどうつくるか
p×qを法とする
mp-1≡1 (mod p) ⇒ mp-1-1は pで割り切れる
mq-1≡1 (mod q) ⇒ mq-1-1は qで割り切れる
では、mod (p·q)にするにはどうしたら良いか?
つまりpでもqでも割り切れる数は?
m(p-1)(q-1)-1を考えてみると、
(m(p-1))(q-1)-1は qで割り切れる。
(m(q-1))(p-1)-1は pで割り切れる。
よってm(p-1)(q-1)-1は p·qで割り切れる。(p·q=nとおく)⇒ m(p-1)(q-1)≡1 (mod n)
ここで、( )≡m にするために、両辺にmをかける。
m(p-1)(q-1)·m≡m (mod n)
m(p-1)(q-1)+1≡m (mod n)
この時、(p-1)(q-1)+1=e·dとすると、(me)d≡m (mod n)となる。