今回はRSA暗号です。
RSA暗号の概要
発明
1977年にロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンによって発明されました。名前は発明者の頭文字から取られています。
背景
RSA暗号は、1976年に公開鍵暗号の概念を提唱したディフィーとヘルマンの研究を受けて、実用的なアルゴリズムとして具体化されました。
原理
RSAはフェルマーの小定理に基づいています。これは、特定の数学的性質を利用して、暗号化と復号化を行う方法です。
特許と公開
RSAは1983年に特許が取得され、RSA Security社が独占していましたが、特許が2000年に満了し、以降は誰でも自由に使用できるようになりました。
使い方
RSA暗号は以下の用途に使われます:
- 秘匿: データを暗号化して第三者に解読できないようにします。
- 認証: デジタル署名を用いてデータの信頼性を保証します。
RSAは公開鍵暗号の一つで、暗号化と復号化に異なる鍵を使用することが特徴です。公開鍵で暗号化したデータは、対応する秘密鍵でしか復号できません。
RSA暗号の基本的な仕組み
RSA暗号は、「大きな素数の積を素因数分解することが非常に難しい」という数学的な性質に基づいています。RSAは公開鍵（暗号化に使用）と秘密鍵（復号化に使用）の2つの鍵を使います。公開鍵は誰でも知ることができますが、秘密鍵は鍵の所有者だけが知っているべきものです。
1. 鍵の生成
RSA暗号で使用される公開鍵と秘密鍵は、以下の手順で生成されます。
- 大きな素数を2つ選ぶ:
非常に大きな素数 p と q を選びます（通常は数百桁の素数を使います）。 - これらを掛け合わせる:
n = p × q として、積 n を計算します。n は公開鍵の一部になります。 - オイラーのトーシェント関数を計算:
ϕ(n) = (p − 1) × (q − 1) を計算します。これは、公開鍵を生成するための中間計算に使います。 - 公開鍵の指数 e を選ぶ:
1 < e < ϕ(n) かつ e と ϕ(n) が互いに素であるような e を選びます。e は通常、公開鍵として広く使われる数値である65537が選ばれることが多いです。 - 秘密鍵の指数 d を計算:
e × d ≡ 1 (mod ϕ(n)) を満たすような d を計算します。この d が秘密鍵になります。
2. 暗号化
メッセージ M を暗号化するには、以下の手順を使います。
- 公開鍵を取得:
公開鍵 (n, e) は公開されているので、誰でも取得できます。 - メッセージを暗号化:
メッセージ M を次のように暗号化します:
C = M^e mod n
ここで、C は暗号文です。
3. 復号化
暗号文 C を復号化して元のメッセージ M を取得するには、以下の手順を使います。
- 秘密鍵を使用:
秘密鍵 (d) を使って暗号文 C を次のように復号化します:
M = C^d mod n
これにより、元のメッセージ M を得ることができます。
Python
このサンプルはわかりやすくする為にセキュリティ向上させる機能は省いています。
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
def generate_keys(keysize=2048):
"""RSA暗号の鍵ペアを生成する"""
# 鍵ペアを生成
key = RSA.generate(keysize)
public_key = key.publickey()
return public_key, key
def encrypt(plaintext, public_key):
"""平文を暗号化する"""
# PKCS#1 OAEPパディングを用いて暗号化
cipher = PKCS1_OAEP.new(public_key)
ciphertext = cipher.encrypt(plaintext.encode('utf-8'))
return ciphertext
def decrypt(ciphertext, private_key):
"""暗号文を復号する"""
# PKCS#1 OAEPパディングを用いて復号
cipher = PKCS1_OAEP.new(private_key)
plaintext = cipher.decrypt(ciphertext)
return plaintext.decode('utf-8')
if __name__ == "__main__":
# 鍵の生成
public_key, private_key = generate_keys()
# 公開鍵と秘密鍵をPEM形式でエクスポート
public_key_pem = public_key.export_key().decode('utf-8')
private_key_pem = private_key.export_key().decode('utf-8')
# 公開鍵と秘密鍵を表示
print("公開鍵:")
print(public_key_pem)
print("秘密鍵:")
print(private_key_pem)
# 平文
message = "Hello, RSA!"
# 暗号化
ciphertext = encrypt(message, public_key)
print("暗号文:", ciphertext)
# 復号化
decrypted_message = decrypt(ciphertext, private_key)
print("復号文:", decrypted_message)
実行の概要
暗号化:
- encrypt 関数は公開鍵を使って平文を暗号化し、暗号文をリストとして返します。
復号化:
- decrypt 関数は秘密鍵を使って暗号文を復号化し、元の平文を返します。
実行結果
公開鍵:
—–BEGIN PUBLIC KEY—–
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAtL63nW412wf+oz+b1thN
2jQxjPwTSnigTcXMYrunUMUvYLgNNePtFgoD3YyPa356xlHucuIwESVhA8X6GqTq
IiAQUw4dL/IQzoshrTi0H1gfwVtDPeUworgUYLkBnXPOigtzYT2vu6teh3LUgAUx
oCbj2q22snI3NNdF04LRK6z3z/JYEZjAEasJuLlgn6+ZvqVDXO21SjrBQ8B2Qb4O
3P89qT1E+zayVH573p2JALkgZdW4xpEEJ0KYeVXU05mlwfeH+FLQ032CqPiQxaXX
Es9W3asT/RQhgtjyrtq4qHy0iCHQ+PXJl8pjD2B+pVy24w8xG+08qxQyZTxJjOHn
NQIDAQAB
—–END PUBLIC KEY—–
秘密鍵:
—–BEGIN RSA PRIVATE KEY—–
MIIEpQIBAAKCAQEAtL63nW412wf+oz+b1thN2jQxjPwTSnigTcXMYrunUMUvYLgN
NePtFgoD3YyPa356xlHucuIwESVhA8X6GqTqIiAQUw4dL/IQzoshrTi0H1gfwVtD
PeUworgUYLkBnXPOigtzYT2vu6teh3LUgAUxoCbj2q22snI3NNdF04LRK6z3z/JY
EZjAEasJuLlgn6+ZvqVDXO21SjrBQ8B2Qb4O3P89qT1E+zayVH573p2JALkgZdW4
xpEEJ0KYeVXU05mlwfeH+FLQ032CqPiQxaXXEs9W3asT/RQhgtjyrtq4qHy0iCHQ
+PXJl8pjD2B+pVy24w8xG+08qxQyZTxJjOHnNQIDAQABAoIBAAx54KtDhQCoOd2z
YZKwLhmKgkQYz00T6/7KUTwcd2VmIwnSUokegUpE6TTlA65YFen0FFlGPyqj0aFE
zGmD6ixuWaod/opFc38KUAoIsLg8KT77yXWviQ6mVbPCeXfQm1hgh3eWHjf+UYFY
fg4TLbSAErjQxlxlcWWamXWK4VzaDyNOqFtMuJ3wZL27grtJmDpbEfsYfUewd22F
PEKMluXobJ59DYkk/MCQOsazK+SiCOd95eY4GMH0xawrETRpZ0ill96GISrH8b66
EmKXxcTy89bha2jr3/x7yhG3yifuq/PXtyx7r4YIv3HuXbcXjfnOqm5whaTEKroQ
oPwu2YkCgYEAyWki7087YCUxhN7Q5Wf0OzFGReORuEzTmuBpv04sqGpuo8LhotoP
/cFEGqd8Ld9D8bOuDeOJnChBafU9HrUj9q7E6Bd+ktETaPlOtkqec3OQjLx4hJpj
ar4cTLqCs9nyrPVBAgYk8EujEZlnq/uT8VPCbEgD7yJFWoXiRkJvtWkCgYEA5bux
ZJouaNd+RsdcTzOyDzOPRVWRVODlU0sJw66p6771IdWgNIRovOQYtBiA+VqW81TO
ce+w86wDbIOS2rvqdfycbuSMyUhz45OFLThmK+HeIZ0LcJhkdr6jSvicN5V96WHO
D9xCJ/zl1JH7DMijku74xoT/uNdoiuzJKtgHre0CgYEAnoxa6dOPRAJDVvsnqk8I
3UfOr9mSrmgb80FRPT1GvlT6P4N7p3zNNc5b1Def82Rb0frFuz0w6HJv+/8HXBLv
+pJdgu5rvxtCklIe+jUHQo7obUE4Bfqa5D4/fM8dcILTG//8aqF3lomUFpiSGbpz
HXf4BtEx958cxUO7ed92nHECgYEAwwQGvWDIvsUXc9vud2lp4M+i8neFzGixI3jS
jCNsKSxMCPHAcnRoONjkQ5V9fq8w7tTx/vQ64U8HBQnYEwhsKsZKwTQQcxmnDuv+
pHl4+g1dtGkM+gLTXZ3NHmpWqjSj0wbslrgiDLH5I+7cD2kOuj9UPalPL0jkfPIu
fskuE60CgYEAjH35EyLtjamA0nYf87xk6YNLqrzfWK7SgCaubrMbNWw3G5r0j293
GNUAq/hlydJR6yOleOTRUOns3SFxH7ks1MEen+M0Tq60jMWw+HEmRQy9c1AxiwYL
VdcVhkzFoGwqWUXDiSbN6cmiNkgh8IVJL4Xss2Z6HtB+a/ws5qiIrRA=
—–END RSA PRIVATE KEY—–
暗号文:b”\\\nB}k\x0bQ\x95\x01\x8c\xa2\x02z\x1b\xaa\xd21\t\xac\xb9\xf4\xe0WK\xb4’P\tx\xaf\x81\x1f\xbd,F\t\xb2\x8b\xd9y\xff\x18\xc1\x80\x96\xa2\xb0\xcb\xaeAQpv\xcfW\x18\xd9\xbe4:\xe6\xd1y\xf3\xd4\xe0U\x8ft\x10\xcd\xf2’Jl\x97\xb5\xf7\x1dtE\x0c<\xa8\xbeB&G3\x92\x15\xfcD\xe7%\xc9\xaeEn\x01\x87\xc2\xad&Oy]:\xbe.\xb0\xb2\xdf\x1c+q6\x96\xeb\xea\x90\xcf\xd5\xfa\x8b\xa7\xd7\x9af!.\x1c4oX\xbbKU\x9f\xbb\xe9x^\x7f\x9e\x92\x86\xcd5\xf9\xe8\xb9D\x0eB3\xe6\xd8\rZLD\xed\xee\xe0\xc5\x13\xa9J8/\\\xf5\xf0\xb4\xddS\xbb\x12\xf7m(\x8b\xe8\xb0\x18@\x94w`\xb7\xd0\x8f[l\x0e\x8a\x10\x91\xc4\x8d\x1f\x98T\xc0\xc6\x8c\x01\xcd\xbc4\xbe\xd7{\xd2\x9f\xf6,E;\xdc\xe9\x1d\x14\xda3\x1fi\xef\xb9\x85\x93\x08\xf241/\xeeB\x9eY\xb3Qi/\xa4kp#F`f\xdc\xea^\x9c"
復号文: Hello, RSA!
