RSA暗号

1977 年に Rivest, Shamir, Adleman の３人が発明した 素因数分解問題の難しさを利用した公開鍵暗号です。

P , Q を非常に大きな 秘密の素数 とし、 その積 N を公開します。

N から、その素因数 P , Q を求めることが非常に困難なので、

暗号化用の公開鍵 e から 復号用の秘密鍵 d を 求められず、安全です。

【鍵生成】

Bob は 暗号化鍵 (e, N) を公開し、 復号鍵 d を秘密にする。

【暗号化】

Alice は Bob の 暗号化鍵 (e, N) を入手する。

Alice は 平文 M を e 乗して N で割った余りを 暗号文 C とする。

C = M ^e mod N

【復号】

Bob は 暗号文 C を d 乗して N で割った余りを 平文 M とする。

M = C ^d mod N