【１】公開鍵の暗号化

p,qは素数

r=pq, (s,φ(r))=1なる暗号用指数sを利用する。

秘密の通信文を受け取りたい人は三つの組p,q,sを選び、暗号用指数ｓおよび暗号用法ｒを公表する。

秘密の通信文を送りたい人はＭをｓ乗し、ｒを法とした結果を求める。

受取人は

st=1 (modφ(r))

によって与えられる解読用指数ｔを必要とする。

もしｒの因数が既知ならφ(r)も既知である。

r=pqに対して、φ(r)=(p-1)(q-1)

t=s^φ(φ(r)-1)-1 (modφ(r))

となる。なぜなら、

ts==s^φ(φ(r)) (modφ(r))

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

受け取った暗号化された通信文はE=M^s (modr)

これをｔで解読すると

E^t=M^st=M^φ(r)k+1 (modr)

オイラーに定理を使うとM^φ(r)=1 (modr)

E^t=Mが得られる。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

解読用指数は公開したsとrから導けるのではなく、sとｒの因数すなわち、ｐとｑだけから導けるのである。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝