RSA暗号の基本構造と実装

RSA暗号は、公開鍵暗号方式の一つであり、安全なデータ通信を可能にするための主要な技術です。この教材では、RSA暗号の基本構造を理解し、Pythonを用いてその実装方法を学びます。

RSA暗号の基本構造

RSA暗号は以下の3つの主要なステップから成り立っています。

1. 鍵の生成: 公開鍵と秘密鍵を生成します。
2. 暗号化: 公開鍵を使用してメッセージを暗号化します。
3. 復号化: 秘密鍵を使用して暗号化されたメッセージを復号化します。

鍵の生成

鍵の生成には、以下の手順が含まれます。

1. 大きな素数 ( p ) と ( q ) を選ぶ。
2. ( n = p \times q ) を計算する。
3. ( \phi(n) = (p-1)(q-1) ) を計算する。
4. ( e ) を選ぶ（1 < ( e ) < ( \phi(n) ) かつ ( e ) と ( \phi(n) ) が互いに素）。
5. ( 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)

コードの説明

1. 素数候補の生成: generate_prime_candidate関数は、指定されたビット長の素数候補を生成します。最上位ビットと最下位ビットを1にすることで、偶数を排除します。

2. 素数の生成: generate_prime_number関数は、素数候補を生成し、それが素数であることを確認します。

3. 鍵の生成: generate_keypair関数は、公開鍵と秘密鍵を生成します。公開指数として65537を使用し、秘密指数はモジュラ逆数を用いて計算します。

4. 暗号化: encrypt関数は、公開鍵を使用して平文を暗号化します。各文字をASCIIコードに変換し、公開鍵の指数でべき乗してモジュラ演算を行います。

5. 復号化: decrypt関数は、秘密鍵を使用して暗号文を復号化します。暗号文の各整数を秘密鍵の指数でべき乗し、再び文字に変換します。

このコードを実行することで、RSA暗号の基本的な動作を体験できます。ビット長を変更することで、鍵の強度を調整することも可能です。