2002 - Rivest、Shamir、Adleman 的 RSA（公開金鑰密碼學）#

import numpy as np
from sympy import isprime, nextprime
import math

# 1) RSA 的構造與運算
def rsa_keygen(p, q, e=65537):
    """產生 RSA 金鑰對"""
    N = p * q
    phi = (p - 1) * (q - 1)
    assert math.gcd(e, phi) == 1, "e 必須與 φ(N) 互質"
    d = pow(e, -1, phi)   # 模反元素
    return (N, e), d      # 公開鑰匙, 私密鑰匙

def rsa_encrypt(m, pub):
    """加密：c = m^e mod N"""
    N, e = pub
    return pow(m, e, N)

def rsa_decrypt(c, d, N):
    """解密：m = c^d mod N"""
    return pow(c, d, N)

# 2) 用小質數測試（教學用）
p, q = 61, 53   # 教學用的小質數
pub, d = rsa_keygen(p, q)
N = pub[0]
print(f"RSA 金鑰產生：")
print(f"  p = {p}, q = {q} → N = {N}")
print(f"  φ(N) = ({p}-1)({q}-1) = {(p-1)*(q-1)}")
print(f"  e = 65537, d = {d}")
print(f"  公開 (N={N}, e={pub[1]})，私密 d = {d}\n")

# 3) 加密與解密（歐拉定理的驗證）
print("加密與解密：")
for m in [65, 123, 3141]:
    c = rsa_encrypt(m, pub)
    m2 = rsa_decrypt(c, d, N)
    print(f"  明文 m = {m}: 加密 → c = {c}，解密 → {m2} {'✓' if m2 == m else '✗'}")
print("  → 加密後解密還原（歐拉定理的保證）\n")

# 4) 歐拉定理的驗證（m^φ(N) ≡ 1 mod N）
print("歐拉定理驗證（m^φ(N) ≡ 1 mod N）：")
phi = (p-1)*(q-1)
for m in [65, 100, 200]:
    val = pow(m, phi, N)
    print(f"  m = {m}: m^φ(N) mod N = {val}（應 = 1）")
print("  → RSA 的正確性 = 200 年前的歐拉定理\n")

# 5) 數位簽章（簽名與驗證）
print("數位簽章：")
m = 1234   # 明文必須 < N
sig = pow(m, d, N)       # 簽名（私密鑰匙）
m2 = pow(sig, pub[1], N) # 驗證（公開鑰匙）
print(f"  明文 m = {m}: 簽名 = {sig}")
print(f"  驗證：簽名^e mod N = {m2} {'✓ 簽名有效' if m2 == m else '✗'}")
print("  → 用私密鑰匙簽、公開鑰匙驗（不可偽造、不可否認）\n")

# 6) 質因數分解的難度（安全性）
print("質因數分解的難度（安全性的來源）：")
for N_test in [p*q, 187, 10403]:
    # 試除法（暴力）
    found = None
    for i in range(2, int(N_test**0.5)+1):
        if N_test % i == 0:
            found = (i, N_test // i)
            break
    print(f"  N = {N_test}: 試除法 → {found}")
print("  → 小質數容易分解；2048 位元的大質數需要超過宇宙年齡")
print("  → 這是 RSA 安全性的來源（直到量子電腦的 Shor 演算法）")

# 7) 真實的 RSA（2048 位元）
print("\n真實的 RSA（2048 位元）：")
p_real = int(nextprime(2**1024 + int.from_bytes(np.random.bytes(16), 'big')))
q_real = int(nextprime(2**1024 + int.from_bytes(np.random.bytes(16), 'big')))
N_real = p_real * q_real
print(f"  生成兩個 1024 位元質數 → N = {N_real.bit_length()} 位元")
print(f"  N 的十進位位數 ≈ {len(str(N_real))} 位")
print("  → 2048 位元的 RSA：GNFS 分解需要超過宇宙年齡的計算")
print("  → 但量子電腦的 Shor 演算法（1994）可以多項式時間破解")
print("  → 後量子密碼學（NIST 2022-2024）正在替代 RSA")

RSA 金鑰產生：
  p = 61, q = 53 → N = 3233
  φ(N) = (61-1)(53-1) = 3120
  e = 65537, d = 2753
  公開 (N=3233, e=65537)，私密 d = 2753

加密與解密：
  明文 m = 65: 加密 → c = 2790，解密 → 65 ✓
  明文 m = 123: 加密 → c = 855，解密 → 123 ✓
  明文 m = 3141: 加密 → c = 2173，解密 → 3141 ✓
  → 加密後解密還原（歐拉定理的保證）

歐拉定理驗證（m^φ(N) ≡ 1 mod N）：
  m = 65: m^φ(N) mod N = 1（應 = 1）
  m = 100: m^φ(N) mod N = 1（應 = 1）
  m = 200: m^φ(N) mod N = 1（應 = 1）
  → RSA 的正確性 = 200 年前的歐拉定理

數位簽章：
  明文 m = 4321: 簽名 = 3426
  驗證：簽名^e mod N = 4321 ✓ 簽名有效
  → 用私密鑰匙簽、公開鑰匙驗（不可偽造、不可否認）

質因數分解的難度（安全性的來源）：
  N = 3233: 試除法 → (53, 61)
  N = 187: 試除法 → (11, 17)
  N = 10403: 試除法 → (101, 103)
  → 小質數容易分解；2048 位元的大質數需要超過宇宙年齡
  → 這是 RSA 安全性的來源（直到量子電腦的 Shor 演算法）

真實的 RSA（2048 位元）：
  生成兩個 1024 位元質數 → N = 2049 位元
  N 的十進位位數 ≈ 617 位
  → 2048 位元的 RSA：GNFS 分解需要超過宇宙年齡的計算
  → 但量子電腦的 Shor 演算法（1994）可以多項式時間破解
  → 後量子密碼學（NIST 2022-2024）正在替代 RSA