Section 7 / 11
RSA暗号の基本構造と実装
RSA暗号は、公開鍵暗号方式の一つであり、安全なデータ通信を可能にするための主要な技術です。この教材では、RSA暗号の基本構造を理解し、Pythonを用いてその実装方法を学びます。
RSA暗号の基本構造
RSA暗号は以下の3つの主要なステップから成り立っています。
- 鍵の生成: 公開鍵と秘密鍵を生成します。
- 暗号化: 公開鍵を使用してメッセージを暗号化します。
- 復号化: 秘密鍵を使用して暗号化されたメッセージを復号化します。
鍵の生成
鍵の生成には、以下の手順が含まれます。
- 大きな素数 ( p ) と ( q ) を選ぶ。
- ( n = p \times q ) を計算する。
- ( \phi(n) = (p-1)(q-1) ) を計算する。
- ( e ) を選ぶ（1 < ( e ) < ( \phi(n) ) かつ ( e ) と ( \phi(n) ) が互いに素）。
- ( d ) を計算する（( e \times d \mod \phi(n) = 1 ) を満たす ( d ) を見つける）。
暗号化と復号化
-
暗号化: メッセージ ( m ) を暗号化するには、次の式を使用します。 [ c = m^e \mod n ]
-
復号化: 暗号文 ( c ) を復号化するには、次の式を使用します。 [ m = c^d \mod n ]
PythonによるRSA暗号の実装
以下に、RSA暗号を実装するためのPythonコードを示します。コードは鍵の生成、暗号化、復号化の各ステップを含みます。
import random
from sympy import isprime, mod_inverse
def generate_prime_candidate(length):
"""指定されたビット長の素数候補を生成する"""
p = random.getrandbits(length)
return p | (1 << length - 1) | 1 # 最上位ビットと最下位ビットを1にする
def generate_prime_number(length):
"""指定されたビット長の素数を生成する"""
p = 4
while not isprime(p):
p = generate_prime_candidate(length)
return p
def generate_keypair(length):
"""公開鍵と秘密鍵を生成する"""
p = generate_prime_number(length)
q = generate_prime_number(length)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537 # よく使われる公開指数
d = mod_inverse(e, phi)
return ((e, n), (d, n)) # 公開鍵と秘密鍵を返す
def encrypt(public_key, plaintext):
"""メッセージを暗号化する"""
e, n = public_key
cipher = [pow(ord(char), e, n) for char in plaintext]
return cipher
def decrypt(private_key, ciphertext):
"""暗号文を復号化する"""
d, n = private_key
plain = [chr(pow(char, d, n)) for char in ciphertext]
return ''.join(plain)
# 鍵の生成
public_key, private_key = generate_keypair(8) # 8ビットの素数を生成
print("公開鍵:", public_key)
print("秘密鍵:", private_key)
# メッセージの暗号化
message = "HELLO"
ciphertext = encrypt(public_key, message)
print("暗号文:", ciphertext)
# メッセージの復号化
decrypted_message = decrypt(private_key, ciphertext)
print("復号化されたメッセージ:", decrypted_message)
コードの説明
-
素数候補の生成:
generate_prime_candidate関数は、指定されたビット長の素数候補を生成します。最上位ビットと最下位ビットを1にすることで、偶数を排除します。 -
素数の生成:
generate_prime_number関数は、素数候補を生成し、それが素数であることを確認します。 -
鍵の生成:
generate_keypair関数は、公開鍵と秘密鍵を生成します。公開指数として65537を使用し、秘密指数はモジュラ逆数を用いて計算します。 -
暗号化:
encrypt関数は、公開鍵を使用して平文を暗号化します。各文字をASCIIコードに変換し、公開鍵の指数でべき乗してモジュラ演算を行います。 -
復号化:
decrypt関数は、秘密鍵を使用して暗号文を復号化します。暗号文の各整数を秘密鍵の指数でべき乗し、再び文字に変換します。
このコードを実行することで、RSA暗号の基本的な動作を体験できます。ビット長を変更することで、鍵の強度を調整することも可能です。