RSA暗号

RSA暗号の概要

公開鍵暗号、デジタル署名に使用可能な暗号の一種であり、巨大な素数の素因数分解が困難なことを利用した暗号方式。

RSA暗号は鍵が変更されない限り平文と暗号文が一対一対応となる。このため、暗号そのものを解読できなくても、平文の機能が攻撃者に漏れてしまう可能性もある。

RSA暗号の手続き

巨大な素数\( p,q \)を用意する。
\( n=pq \\ \phi(n)=(p-1)(q-1) \\ ed \equiv \mod \phi(n) \)
を計算したとき、\( (n,e) \)を公開鍵とし、\( (d) \)を秘密鍵とする。

メッセージ\( M \)を公開鍵\( (n,e) \)を使って暗号化して暗号文\( C \)を作る。
\( C \equiv M^e \mod n \)

暗号文\( C \)から秘密鍵\( d \)を使っメッセージ\( M \)を復号する。
\( M \equiv C^d \mod n \)