［Math］RSAアルゴリズム

(1)公開鍵:

n：pq
e：gcd(e,(p-1)(q-1))=1

(2)秘密鍵:

n：pq
d：de mod (p-1)(q-1)=1

(3)公開鍵(e,n)を用いてmを暗号化する

c：m^e mod n

(4)秘密鍵(d,n)を用いてcを復号する

m：c^d mod n

例:

p=3,q=5
n=pq=15
(p-1)(q-1)=8
gcd(e, (p-1)(q-1))=1    =>    e=3
de mod (p-1)(q-1)=1    =>    d=11

  (e=3,n=15)
  (d=11,n=15)

  m=2
  c=m^e mod n=8
  m=c^d mod n=2