RSA 加密原理
原理概述：
RSA算法基于一个简单的数论事实：分解大整数是非常困难的，特别是当这个大整数是两个大素数的乘积时。该算法的安全性依赖于这一事实。
主要步骤：
选择两个不同的大素数 pp 和 qq，计算 n=pqn=pq。
计算欧拉函数 ϕ(n)=(p−1)(q−1)ϕ(n)=(p−1)(q−1)。
选择一个整数 ee，满足 1<e<ϕ(n)1<e<ϕ(n)，并且 ee 和 ϕ(n)ϕ(n) 是互质的。
确定私钥 dd，使得 ed≡1mod ϕ(n)ed≡1modϕ(n)。即 dd 是 ee 的模逆元。
公钥 是 (n,e)(n,e)，私钥 是 (n,d)(n,d)。
加密过程：明文 MM 转换为数字 mm，计算密文 c=memod nc=memodn。
解密过程：接收方使用私钥 dd 计算 m=cdmod nm=cdmodn，恢复原始消息 MM。
Python 实现示例：
import random
from sympy import isprime, mod_inverse
def generate_prime(bits):
while True:
p = random.getrandbits(bits)
if isprime(p):
return p
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def generate_keypair(bits):
p = generate_prime(bits)
q = generate_prime(bits)
n = p * q
phi_n = (p - 1) * (q - 1)
# Choose e such that 1 < e < phi_n and gcd(e, phi_n) = 1
e = random.randint(2, phi_n - 1)
while gcd(e, phi_n) != 1:
e = random.randint(2, phi_n - 1)
# Compute d, the modular multiplicative inverse of e (mod phi_n)
d = mod_inverse(e, phi_n)
return1
def encrypt(public_key, plaintext):
n, e = public_key
# Convert plaintext to integer
message = int.from_bytes(plaintext.encode(), 'big')
# Encrypt the message using the public key
cipher = pow(message, e, n)
return cipher
def decrypt(private_key, ciphertext):
n, d = private_key
# Decrypt the message using the private key
message = pow(ciphertext, d, n)
# Convert the integer back to string
plaintext = message.to_bytes((message.bit_length() + 7) // 8, 'big').decode()
return plaintext
# Example usage
public_key, private_key = generate_keypair(1024)
message = "Hello, RSA!"
encrypted_message = encrypt(public_key, message)
decrypted_message = decrypt(private_key, encrypted_message)
print(f"Original: {message}")
print(f"Encrypted: {encrypted_message}")
print(f"Decrypted: {decrypted_message}")
CBC 模式
CBC（Cipher Block Chaining，密文链接模式）是一种用于对称加密算法的操作模式，它通过将每个明文块与前一个密文块进行异或运算来增加数据的安全性。
工作原理：
初始化向量（IV）：一个随机或固定的值，用于第一个明文块的加密。
对于每个后续的明文块 PiPi，首先与前一个密文块 Ci−1Ci−1 进行异或运算，然后用密钥 KK 加密结果，得到新的密文块 CiCi。
解密时，先用密钥 KK 解密 CiCi，再与 Ci−1Ci−1 异或，恢复 PiPi。
Python 实现示例：
这里以AES加密为例，使用Python的cryptography库实现CBC模式的加密和解密。
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.backends import default_backend
import os
def encrypt_aes_cbc(key, plaintext, iv=None):
if iv is None:
iv = os.urandom(16) # Generate a random IV if not provided
cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend())
encryptor = cipher.encryptor()
ct = encryptor.update(plaintext) + encryptor.finalize()
return ct, iv
def decrypt_aes_cbc(key, ciphertext, iv):
cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend())
decryptor = cipher.decryptor()
pt = decryptor.update(ciphertext) + decryptor.finalize()
return pt
# Example usage
key = os.urandom(32) # AES-256 key
plaintext = b"Secret message"
ct, iv = encrypt_aes_cbc(key, plaintext)
pt = decrypt_aes_cbc(key, ct, iv)
print(f"Original: {plaintext}")
print(f"Encrypted: {ct}")
print(f"Decrypted: {pt}")
RSA攻击
1.小指数攻击
如果公钥中的指数 ee 很小（通常是3），并且消息 mm 较短，那么加密后的密文 c=memod nc=memodn 可能没有被完全模 nn 减少，导致 c=mec=me。此时可以通过直接开根号来恢复原始消息。
def small_exponent_attack(c, e, n):
m = int(round(c ** (1.0 / e)))
if pow(m, e, n) == c:
return m
else:
return None
# Example usage
c = 1234567890123456789012345678901234567890
e = 3
n = 1234567890123456789012345678901234567891
m = small_exponent_attack(c, e, n)
if m is not None:
print(f"Recovered message: {m}")
else:
print("Attack failed")
2.共模攻击
如果两个用户使用相同的模数 nn 但不同的公钥 e1e1 和 e2e2，并且 gcd(e1,e2)=1gcd(e1,e2)=1，则可以利用扩展欧几里得算法找到 ss 和 tt 使得 se1+te2=1se1+te2=1。这样可以通过 c1s⋅c2tmod nc1s⋅c2tmodn 来恢复消息 mm。
from sympy import gcdex
def common_modulus_attack(c1, c2, e1, e2, n):
s, t, _ = gcdex(e1, e2)
if s < 0:
s = -s
c1 = mod_inverse(c1, n)
if t = 0:
sqrt_delta = int(delta ** 0.5)
if sqrt_delta * sqrt_delta == delta:
p = (b + sqrt_delta) // 2
q = (b - sqrt_delta) // 2
if p * q == n:
return d
return None
# Example usage
e = 65537
n = 1234567890123456789012345678901234567891
d = wiener_attack(e, n)
if d is not None:
print(f"Recovered private key d: {d}")
else:
print("Attack failed")
- n, e), (n, d [↩]