はじめに
RSA暗号とは大きな数字の素因数分解が困難であることを利用した、公開鍵暗号方式のアルゴリズムの一種である。ここでは、RSA暗号の仕組みとその安全性について紹介する。
RSA暗号の仕組み
RSA暗号を用いた通信には大きく分かけて以下の3つの段階が存在する。 1. メッセージを受け取る側の準備 2. メッセージを送る側の準備 3. メッセージを受け取る側の復元方法 それぞれの項目について説明していく。
1. メッセージを受け取る側の準備
- 大きな素数 p, q を生成し、n = pqとする。
- (p−1)(q−1) と互いに素な整数kを取ってくる。
- kl ≡ 1 (mod (p -1)(q – 1)) なる整数 l を取ってくる。
- この数は一意に定まる。証明は[こちらのサイト](https://manabitimes.jp/math/1141）の例題2を参照。
kl ≡ 1 (mod (p – 1)(q – 1)) は kl を (p – 1)(q – 1) で割った余りが1であるということ。
- n と k は公開する（公開鍵）、 l は公開しない（秘密鍵）
2. メッセージを送る側の暗号化方法
- 送りたいメッセージを m とする。ただし、 m は n 未満の正の整数とする
- 公開鍵を用いて m^k を n で割った余りを計算し、これを暗号文 C とおく。
3. メッセージを受け取る側の復元方法
- 暗号文 C と秘密鍵 l を用いて C^l を n で割った余りを計算すると、もとのメッセージ m と一致する。
- この方法で復元できる理由、つまり m^(kl) ≡ m (mod n) となる理由はこちらを参照。
RSA暗号の安全性
この暗号の解読の難しさの肝は、n の素因数分解の難しさにある。暗号文 C と公開鍵 k と n が外部に漏れたとしても、 n の因数p, qがわからなければ秘密鍵 l を当てることができない。
一般に100桁の整数の素因数分解を求めるのに、現代の最新のコンピュータを使っても天文学的な時間がかかると考えられている。そのため、RSA暗号に用いられる大きい数字とはだいたい300桁程度の数のことを指す。
