■トーシェント関数と非トーション(その59)

【1】公開鍵の暗号化

p,qは素数

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

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

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

受取人は

st=1 (modφ(r))

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

もし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)

これをtで解読すると

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

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

E^t=Mが得られる。

===================================

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

===================================