【１】暗号化

通信文は正の整数Mに変換されるものとする。(M,r)=1

Mをｓ乗し、ｒを法とする余りだけを保持することにする。

E=M^s (modr)

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

【２】復号化

st=1 (modr-1) (s,r-1)=1

を解き、tを見つける。

オイラーの定理より

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

なぜなら(s,r-1)=1ならばst=s^φ(r-1)＝1 (modr-1)

したがって、

E^t=M^st (modr)であり、

st=(r-1)k+1であるから、

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

オイラー・フェルマーの定理よりM^r-1=1 (modr)であり、

E^t=M (modr)

で通信文が再生されたことになる。

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

s=3,r=17,φ(r-1)=16(1-1/2)=8,(s,φ(r-1))=1のとき、

解読用の指数は

t=s^φ(r-1)-1=3^7=11 (mod16)

M=4のとき、暗号化された通信文は

E=M^s=4^3=13 (mod17)

解読した通信文はE=13,t=11

E^t=13^11=(13^5)^2・13=13^3=4=M (mod17)

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