RSA暗号の仕組みを見てみよう
はじめに
最近、生成AIのブームでデータの扱い方がますます大事になっています。今回は、セキュリティ界の重鎮とも言えるRSA暗号について、概要と仕組みについて解説していきます。
RSAって何?
RSA暗号は、公開鍵暗号の一種で、ネット上の情報を守るために大活躍している仕組みです。1977年に、アメリカの研究者であるロナルド・リベスト、アディ・シャミア、そしてレオナルド・エーデルマンの3人によって生み出されました。この3人の頭文字をとって「RSA」と呼ばれるようになったんですよ。
どんなシーンで使われてるの?
RSA暗号は、Webアプリの開発はもちろん、クラウドサービスやブロックチェーンなんか、幅広い分野で使われています。たとえば、HTTPS通信ではWebサーバーとブラウザがセッション鍵を交換する際にRSA暗号が活躍。その後、実際の通信はもっと高速な対称鍵暗号で行われます。
ほかにも、APIの認証や大事なデータの秘匿、さらにはデバイス認証(OAuth 2.0なんかで)など、セキュリティを守るためにRSAは欠かせない存在になっています。
なぜRSAの解読は難しいのか?
RSA暗号がすごく強固なのは、基本となる「素因数分解」が困難であるのが理由です。RSAでは、大きな2つの素数(pとq)を掛け合わせた数字nを公開鍵として使っています。このnから元の2つの素数を見つけ出す、つまり素因数分解をするのは、数字が大きくなると計算量が爆発的に増えるので、現代のスーパーコンピュータでもほぼ無理な状態なんです。
例えるなら、パンケーキの生地を一度混ぜちゃうと、小麦粉と卵に戻すのがほぼ不可能なようなもの。(というアナロジーをよく見かけます。)
RSAの仕組み
次にRSA暗号の基本的な仕組みを確認してみましょう。
RSA鍵生成のステップ
-
2つの大きな素数の選択:
非常に大きな(数百桁以上の)素数pとqをランダムに選びます。この素数の大きさが、暗号の強度を決定します。
-
モジュラスnの計算:
選んだ2つの素数pとqを掛け合わせ、n = p × q を計算します。このnが、公開鍵と秘密鍵の基となるモジュラスになります。
-
オイラーのトーシェント関数φ(n)の計算:
オイラーのトーシェント関数φ(n)は、nと互いに素な正の整数の個数を表します。この場合、φ(n) = (p-1) × (q-1) と計算できます。
-
公開鍵eの選択:
1 < e < φ(n) かつ e と φ(n) が互いに素となるような整数eを選びます。一般的に、e = 65537 がよく使われます。このeが公開鍵の要素になります。
-
秘密鍵dの計算:
ed ≡ 1 (mod φ(n)) を満たす整数dを計算します。このdが秘密鍵の要素になります。この計算には、拡張ユークリッドの互除法が使われます。
生成された鍵の構成
-
公開鍵: (n, e)
- n: モジュラス
- e: 公開指数
-
秘密鍵: (n, d)
- n: モジュラス
- d: 秘密指数
RSA暗号の仕組み
- 暗号化: 平文mを暗号化する場合、暗号文cは c ≡ m^e (mod n) で計算される。
- 復号: 暗号文cを復号する場合、平文mは m ≡ c^d (mod n) で計算される。
具体例
1. 2つの小さな素数の選択
ここでは7と11を選択します。※実際には大きな素数が使用されています。
- p = 7
- q = 11
# 1. Select two large prime numbers
p = generate_large_prime(bits // 2)
q = generate_large_prime(bits // 2)
2. モジュラスnの計算
選択した素数の積を求めて、その値をnとします。
- n = p * q = 7 * 11 = 77
# 2. Compute the modulus n
n = p * q
3. オイラーのトーシェント関数φ(n)の計算
トーシェント関数を利用し、φ(n) の値を求めます。
- φ(n) = (p-1) * (q-1) = 6 * 10 = 60
# 3. Compute Euler's totient function φ(n)
phi_n = (p - 1) * (q - 1)
4. 公開鍵eの選択
1 < e < φ(n) かつ e と φ(n) が互いに素となるようなeを選択します。ここでは、e = 7 を選択します。
- 1 < 7 < 60 : OK
- gcd(60, 7) = 1 : OK (60と7の最大公約数が1) ※gcd: Greatest Common Divisor(最大公約数)の略
# 4. Choose the public exponent e
e = 65537 # A commonly used public exponent
5. 秘密鍵dの計算
- ed ≡ 1 (mod φ(n)) を満たすdを求めます。(拡張ユークリッドの互除法で算出)
- 7d ≡ 1 (mod 60) を満たすdは、d = 43 。
# 5. Compute the private exponent d
d = mod_inverse(e, phi_n)
生成された鍵
- 公開鍵: (n, e) = (77, 7)
- 秘密鍵: (n, d) = (77, 43)
# Return the public and private keys
public_key = (n, e)
private_key = (n, d)
暗号化と復号の例
-
平文: m = 5
-
暗号化: c ≡ m^e (mod n) より、c ≡ 5^7 mod 77 ≡ 47
print(pow(5, 7, 77)) # 5^7 mod 77 = 47
-
復号: m ≡ c^d (mod n) より、m ≡ 47^43 mod 77 ≡ 5
print(pow(47, 43, 77)) # 47^43 mod 77 = 5
最後にRSAのアルゴリズムをPythonで実装してみました。
興味のある方は以下のコードをご覧ください
参考文献
Discussion