1977 年に Rivest, Shamir, Adleman の3人が発明した 素因数分解問題の難しさを利用した公開鍵暗号です。
P , Q を非常に大きな 秘密の素数 とし、 その積 N を公開します。
N から、その素因数 P , Q を求めることが非常に困難なので、
暗号化用の公開鍵 e から 復号用の秘密鍵 d を 求められず、安全です。
【鍵生成】
Bob は 暗号化鍵 (e, N) を公開し、 復号鍵 d を秘密にする。
N = P Q
e d mod L = 1
( P, Q: 秘密の素数)
( L = lcm( P -1, Q -1))
【暗号化】
Alice は Bob の 暗号化鍵 (e, N) を入手する。
Alice は 平文 M を e 乗して N で割った余りを 暗号文 C とする。
C = M e mod N
【復号】
Bob は 暗号文 C を d 乗して N で割った余りを 平文 M とする。
M = C d mod N