🔐

RSA暗号の仕組みを見てみよう

2025/02/02に公開

はじめに

最近、生成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鍵生成のステップ

  1. 2つの大きな素数の選択:

    非常に大きな(数百桁以上の)素数pとqをランダムに選びます。この素数の大きさが、暗号の強度を決定します。

  2. モジュラスnの計算:

    選んだ2つの素数pとqを掛け合わせ、n = p × q を計算します。このnが、公開鍵と秘密鍵の基となるモジュラスになります。

  3. オイラーのトーシェント関数φ(n)の計算:

    オイラーのトーシェント関数φ(n)は、nと互いに素な正の整数の個数を表します。この場合、φ(n) = (p-1) × (q-1) と計算できます。

  4. 公開鍵eの選択:

    1 < e < φ(n) かつ e と φ(n) が互いに素となるような整数eを選びます。一般的に、e = 65537 がよく使われます。このeが公開鍵の要素になります。

  5. 秘密鍵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で実装してみました。
興味のある方は以下のコードをご覧ください
https://github.com/atsushi729/cryptography/blob/main/asymmetric_encryption/generate_key.py

参考文献

https://www.cryptool.org/en/cto/rsa-step-by-step/
https://en.wikipedia.org/wiki/RSA_(cryptosystem)

Discussion