RSA暗号化と復号の数学

RSA鍵を生成したので、次はそれを使います。暗号化も復号もモジュラーべき乗であり、計算は簡単ですが、秘密鍵なしで逆算することは現実的に困難です。

公開鍵(e, n)でメッセージM（整数）を暗号化します。 C = M^e mod n 例：M=42、e=17、n=3233 C = 42^17 mod 3233 Python: C = pow(42, 17, 3233) = 2557

秘密鍵(d, n)で暗号文Cを復号します。 M = C^d mod n C=2557、d=2753、n=3233 M = 2557^2753 mod 3233 Python: M = pow(2557, 2753, 3233) = 42 ✓

C^d mod n = (M^e)^d mod n = M^(ed) mod n。 ed ≡ 1 (mod φ(n))なので、M^(ed) = M^(1+k×φ(n)) = M × (M^φ(n))^k ≡ M × 1^k = Mとなります。

M^eを単純に計算すると、e回の乗算が必要になります。繰り返し二乗法を使うと、乗算の回数をO(log e)まで減らせます。 Pythonのpow(base, exp, mod)は、この方法を自動的に使用します。

教科書的RSAではM < nでなければなりません。RSA-2048の場合、Mは最大256バイトです。これは短いAES鍵の暗号化には適していますが、大きなファイルを直接暗号化する用途には適していません。

生のRSAには次の問題があります。 1. 同じMは常に同じCになる（決定的） 2. eが小さくMも小さい場合、C = M^eがそのまま成立する（法による剰余計算が行われない） 3. 乗法的である：Enc(M1)×Enc(M2) = Enc(M1×M2) パディング方式によって、これらの問題をすべて解決できます。

from cryptography.hazmat.primitives.asymmetric import padding from cryptography.hazmat.primitives import hashes ciphertext = public_key.encrypt( b'Secret message', padding.OAEP( mgf=padding.MGF1(algorithm=hashes.SHA256()), algorithm=hashes.SHA256(), label=None ) )

plaintext = private_key.decrypt( ciphertext, padding.OAEP( mgf=padding.MGF1(algorithm=hashes.SHA256()), algorithm=hashes.SHA256(), label=None ) ) print(plaintext) # b'Secret message'

# Real-world pattern: aes_key = os.urandom(32) # Random 256-bit AES key encrypted_key = rsa_encrypt(aes_key, recipient_pub) # RSA ciphertext = aes_gcm_encrypt(aes_key, plaintext) # AES # Send: encrypted_key + ciphertext

RSA-2048の暗号化（公開鍵）：約0.1ミリ秒。RSA-2048の復号（秘密鍵）：約1ミリ秒。AES-256-GCM：約100 MB/秒。ハイブリッド暗号により、RSAの鍵交換速度とAESのデータ処理速度を組み合わせられます。

e=3、n=33の教科書的RSAを使う場合、M=5の暗号化結果はいくつですか？

RSAの暗号化と復号の数学が明確になりました。次は、実際の世界でRSAがHTTPS、SSH、コード署名をどのように保護しているかを見ていきます。