RSA暗号とは、公開鍵暗号の一種であり、1977年にロナルド・リベスト、アディ・シャミア、レオナルド・アダルマンによって提案された。RSA暗号は、現在でも最も広く使われている公開鍵暗号の一つである。
RSA暗号では、鍵ペアとして、公開鍵と秘密鍵が用いられる。公開鍵は、暗号化に用いられ、秘密鍵は、復号に用いられる。RSA暗号の安全性は、大きな素数を用いることによって保証される。
RSA暗号のアルゴリズムは以下の手順で動作する。
-
鍵生成
1-1. 2つの素数p, qをランダムに選ぶ。
1-2. N = pqとし、Nを使って公開鍵と秘密鍵を生成する。
- 公開鍵：(N, e) ※eは1 < e < φ(N)かつgcd(e, φ(N)) = 1を満たす値
- 秘密鍵：(N, d) ※dはed ≡ 1 (mod φ(N))を満たす値 -
暗号化
2-1. 平文mを整数に変換する。
2-2. 暗号文をc ≡ m^e (mod N)として生成する。 -
復号
3-1. 暗号文cを平文に戻す。
3-2. 平文m ≡ c^d (mod N)として生成する。
RSA暗号の特徴は、鍵生成時にランダムな素数を使用するため、同じ鍵ペアが生成される確率が極めて低いことである。これにより、RSA暗号は、暗号化に使用される公開鍵を公開しても、秘密鍵を知らなければ解読することができないため、安全性が高いとされている。
また、RSA暗号は、暗号化、復号において、指数計算のみを必要とするため、高速に動作することができる。しかし、鍵長が短い場合には、暴力的攻撃によって解読されることがあるため、鍵長の適切な設定が必要となる。
RSA暗号は、データの暗号化だけでなく、デジタル署名や鍵交換などの用途にも広く利用されている。しかし、量子コンピュータの登場により、RSA暗号は破られる可能性があるため、今後の暗号方式の研究が重要となっている。