加密算法数学原理详解
目录
- 数论基础
- 对称加密数学原理
- 非对称加密数学原理
- 椭圆曲线密码学数学原理
- 哈希函数数学原理
- 密钥交换数学原理
- 数字签名数学原理
数论基础
模运算
class ModularArithmetic:
"""模运算数学原理"""
@staticmethod
def mod_exp(base, exponent, modulus):
"""模幂运算: base^exponent mod modulus"""
result = 1
base = base % modulus
while exponent > 0:
if exponent % 2 == 1:
result = (result * base) % modulus
exponent = exponent >> 1
base = (base * base) % modulus
return result
@staticmethod
def extended_gcd(a, b):
"""扩展欧几里得算法"""
if a == 0:
return b, 0, 1
gcd, x1, y1 = ModularArithmetic.extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
@staticmethod
def mod_inverse(a, m):
"""模逆元计算"""
gcd, x, _ = ModularArithmetic.extended_gcd(a, m)
if gcd != 1:
raise ValueError("模逆元不存在")
return (x % m + m) % m
@staticmethod
def chinese_remainder_theorem(remainders, moduli):
"""中国剩余定理"""
from math import prod
M = prod(moduli)
result = 0
for a_i, m_i in zip(remainders, moduli):
M_i = M // m_i
y_i = ModularArithmetic.mod_inverse(M_i, m_i)
result = (result + a_i * M_i * y_i) % M
return result
# 模运算示例
def modular_arithmetic_examples():
print("=== 模运算数学原理示例 ===")
# 模幂运算
result = ModularArithmetic.mod_exp(7, 13, 11)
print(f"7^13 mod 11 = {result}")
# 扩展欧几里得算法
gcd, x, y = ModularArithmetic.extended_gcd(240, 46)
print(f"gcd(240, 46) = {gcd}, 系数: x={x}, y={y}")
print(f"验证: 240*{x} + 46*{y} = {240*x + 46*y}")
# 模逆元
inv = ModularArithmetic.mod_inverse(17, 3120)
print(f"17 在模 3120 下的逆元: {inv}")
print(f"验证: 17 * {inv} mod 3120 = {17 * inv % 3120}")
# 中国剩余定理
remainders = [2, 3, 2]
moduli = [3, 5, 7]
solution = ModularArithmetic.chinese_remainder_theorem(remainders, moduli)
print(f"中国剩余定理解: x ≡ {solution} mod {3*5*7}")
for i, (a, m) in enumerate(zip(remainders, moduli)):
print(f" x mod {m} = {solution % m} ≡ {a}")
modular_arithmetic_examples()
素数和素数测试
import random
from math import gcd, isqrt
class PrimeTheory:
"""素数理论和测试"""
@staticmethod
def is_prime_naive(n):
"""朴素的素数测试"""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, isqrt(n) + 1, 2):
if n % i == 0:
return False
return True
@staticmethod
def miller_rabin_test(n, k=5):
"""Miller-Rabin 概率素数测试"""
if n < 2:
return False
if n in (2, 3):
return True
if n % 2 == 0:
return False
# 将 n-1 写成 d*2^r 的形式
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
def check_composite(a):
"""检查是否为合数的证据"""
x = pow(a, d, n)
if x == 1 or x == n - 1:
return False
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
return False
return True
# 进行 k 轮测试
for _ in range(k):
a = random.randint(2, n - 2)
if check_composite(a):
return False
return True
@staticmethod
def generate_large_prime(bits=1024):
"""生成大素数"""
while True:
# 生成奇数
p = random.getrandbits(bits)
p |= (1 << bits - 1) | 1 # 设置最高位和最低位为1
if PrimeTheory.miller_rabin_test(p):
return p
@staticmethod
def euler_totient(n):
"""欧拉函数 φ(n)"""
if n < 1:
return 0
result = n
# 质因数分解
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
p += 1
if n > 1:
result -= result // n
return result
def prime_theory_examples():
print("\n=== 素数理论示例 ===")
# 素数测试
test_numbers = [17, 561, 7919, 104729] # 561 是卡迈克尔数
for num in test_numbers:
naive = PrimeTheory.is_prime_naive(num)
miller_rabin = PrimeTheory.miller_rabin_test(num)
print(f"{num}: 朴素测试={naive}, Miller-Rabin={miller_rabin}")
# 欧拉函数
for n in [9, 15, 21]:
phi = PrimeTheory.euler_totient(n)
print(f"φ({n}) = {phi}")
# 生成大素数
large_prime = PrimeTheory.generate_large_prime(64) # 64位素数用于演示
print(f"生成的大素数: {large_prime}")
print(f"验证: Miller-Rabin测试 = {PrimeTheory.miller_rabin_test(large_prime)}")
prime_theory_examples()
对称加密数学原理
AES 数学原理
class AESMathematics:
"""AES 加密算法的数学原理"""
# Rijndael S-box
S_BOX = [
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
# ... 完整的S盒 (为了简洁省略部分)
]
# 不可约多项式: x^8 + x^4 + x^3 + x + 1
IRREDUCIBLE_POLY = 0x11b
@staticmethod
def gf256_multiply(a, b):
"""GF(2^8) 有限域乘法"""
result = 0
for _ in range(8):
if b & 1:
result ^= a
carry = a & 0x80
a <<= 1
if carry:
a ^= AESMathematics.IRREDUCIBLE_POLY
b >>= 1
return result & 0xff
@staticmethod
def gf256_inverse(a):
"""GF(2^8) 有限域求逆"""
if a == 0:
return 0
# 使用扩展欧几里得算法
def gf256_extended_gcd(a, b):
if b == 0:
return a, 1, 0
else:
gcd, x1, y1 = gf256_extended_gcd(b, a % b)
# 在GF(2^8)中，除法需要特殊处理
# 这里简化处理
return gcd, y1, x1 ^ AESMathematics.gf256_multiply(a // b, y1)
# 简化版本：通过查表或暴力搜索
for i in range(1, 256):
if AESMathematics.gf256_multiply(a, i) == 1:
return i
return 0
@staticmethod
def sub_bytes_transformation(byte):
"""字节替换变换的数学原理"""
if byte == 0:
return 0x63 # 0的特殊处理
# 计算在GF(2^8)中的逆元
inv = AESMathematics.gf256_inverse(byte)
# 仿射变换
result = 0
for i in range(8):
# 矩阵乘法部分
bit = (inv >> i) & 1
if bit:
result ^= (0x1f << i) & 0xff # 简化的仿射变换
return result ^ 0x63 # 加上常数向量
@staticmethod
def mix_columns_transformation(state):
"""列混合变换的数学原理"""
# 在GF(2^8)上的矩阵乘法
# 使用多项式: a(x) = 3x^3 + x^2 + x + 2
mixed_state = [0] * 16
for col in range(4):
# 每列4个字节
s0 = state[col * 4]
s1 = state[col * 4 + 1]
s2 = state[col * 4 + 2]
s3 = state[col * 4 + 3]
# 矩阵乘法
mixed_state[col * 4] = (AESMathematics.gf256_multiply(2, s0) ^
AESMathematics.gf256_multiply(3, s1) ^
s2 ^ s3)
mixed_state[col * 4 + 1] = (s0 ^
AESMathematics.gf256_multiply(2, s1) ^
AESMathematics.gf256_multiply(3, s2) ^
s3)
mixed_state[col * 4 + 2] = (s0 ^ s1 ^
AESMathematics.gf256_multiply(2, s2) ^
AESMathematics.gf256_multiply(3, s3))
mixed_state[col * 4 + 3] = (AESMathematics.gf256_multiply(3, s0) ^
s1 ^ s2 ^
AESMathematics.gf256_multiply(2, s3))
return mixed_state
def aes_mathematics_examples():
print("\n=== AES 数学原理示例 ===")
# GF(2^8) 乘法示例
a, b = 0x57, 0x83
product = AESMathematics.gf256_multiply(a, b)
print(f"GF(2^8) 乘法: {a:02x} * {b:02x} = {product:02x}")
# GF(2^8) 逆元示例
for x in [0x02, 0x03, 0x09]:
inv = AESMathematics.gf256_inverse(x)
verify = AESMathematics.gf256_multiply(x, inv)
print(f"GF(2^8) 逆元: {x:02x} 的逆元是 {inv:02x}, 验证: {x:02x}*{inv:02x} = {verify:02x}")
# 字节替换示例
byte = 0x53
sub_byte = AESMathematics.sub_bytes_transformation(byte)
print(f"字节替换: {byte:02x} -> {sub_byte:02x}")
aes_mathematics_examples()
非对称加密数学原理
RSA 数学原理
class RSAMathematics:
"""RSA 算法的数学原理"""
@staticmethod
def rsa_key_generation(bit_length=1024):
"""RSA 密钥生成数学原理"""
# 1. 生成两个大素数
p = PrimeTheory.generate_large_prime(bit_length // 2)
q = PrimeTheory.generate_large_prime(bit_length // 2)
# 2. 计算 n = p * q
n = p * q
# 3. 计算欧拉函数 φ(n) = (p-1)(q-1)
phi_n = (p - 1) * (q - 1)
# 4. 选择公钥指数 e (通常为 65537)
e = 65537
while gcd(e, phi_n) != 1:
e += 2
# 5. 计算私钥指数 d = e^(-1) mod φ(n)
d = ModularArithmetic.mod_inverse(e, phi_n)
return (e, n), (d, n), (p, q, phi_n)
@staticmethod
def rsa_encrypt(message, public_key):
"""RSA 加密数学原理: c = m^e mod n"""
e, n = public_key
return pow(message, e, n)
@staticmethod
def rsa_decrypt(ciphertext, private_key):
"""RSA 解密数学原理: m = c^d mod n"""
d, n = private_key
return pow(ciphertext, d, n)
@staticmethod
def rsa_crt_decrypt(ciphertext, private_key_crt):
"""使用中国剩余定理优化的 RSA 解密"""
d, n, p, q = private_key_crt
# 计算 m_p = c^d mod p 和 m_q = c^d mod q
d_p = d % (p - 1)
d_q = d % (q - 1)
m_p = pow(ciphertext, d_p, p)
m_q = pow(ciphertext, d_q, q)
# 使用中国剩余定理组合结果
return ModularArithmetic.chinese_remainder_theorem([m_p, m_q], [p, q])
@staticmethod
def analyze_rsa_security(n):
"""分析 RSA 安全性 - 因式分解的难度"""
from math import isqrt
# 简单的因式分解尝试（仅用于演示）
# 实际中需要使用更复杂的算法如数域筛法
limit = min(isqrt(n) + 1, 1000000) # 限制计算量
for i in range(2, limit):
if n % i == 0:
return i, n // i
return None, None
def rsa_mathematics_examples():
print("\n=== RSA 数学原理示例 ===")
# 生成 RSA 密钥（小素数用于演示）
public_key, private_key, crt_params = RSAMathematics.rsa_key_generation(32)
e, n = public_key
d, _ = private_key
p, q, phi_n = crt_params
print(f"公钥: (e={e}, n={n})")
print(f"私钥: (d={d}, n={n})")
print(f"素数: p={p}, q={q}")
print(f"欧拉函数: φ(n) = {phi_n}")
print(f"验证: e*d mod φ(n) = {e * d % phi_n}")
# 加密和解密
message = 42
ciphertext = RSAMathematics.rsa_encrypt(message, public_key)
decrypted = RSAMathematics.rsa_decrypt(ciphertext, private_key)
print(f"\n加密演示:")
print(f"原始消息: {message}")
print(f"加密: {message}^{e} mod {n} = {ciphertext}")
print(f"解密: {ciphertext}^{d} mod {n} = {decrypted}")
print(f"解密正确性: {message == decrypted}")
# CRT 优化解密
crt_decrypted = RSAMathematics.rsa_crt_decrypt(ciphertext, (d, n, p, q))
print(f"CRT 解密: {crt_decrypted} (正确性: {message == crt_decrypted})")
# 安全性分析
print(f"\n安全性分析:")
factor1, factor2 = RSAMathematics.analyze_rsa_security(n)
if factor1:
print(f"因式分解成功: {n} = {factor1} * {factor2}")
else:
print(f"因式分解失败 (在合理时间内)")
rsa_mathematics_examples()
椭圆曲线密码学数学原理
class EllipticCurveMathematics:
"""椭圆曲线密码学数学原理"""
def __init__(self, a, b, p):
"""初始化椭圆曲线: y^2 = x^3 + ax + b (mod p)"""
self.a = a
self.b = b
self.p = p
# 验证曲线参数
discriminant = (4 * pow(a, 3, p) + 27 * pow(b, 2, p)) % p
if discriminant == 0:
raise ValueError("曲线参数无效，判别式为0")
def point_addition(self, P, Q):
"""椭圆曲线点加运算"""
if P is None:
return Q
if Q is None:
return P
x1, y1 = P
x2, y2 = Q
# P + (-P) = 无穷远点
if x1 == x2 and y1 != y2:
return None
p = self.p
if P == Q:
# 点倍运算
if y1 == 0:
return None
# 斜率 λ = (3x1^2 + a) / (2y1) mod p
numerator = (3 * pow(x1, 2, p) + self.a) % p
denominator = (2 * y1) % p
lambda_val = (numerator * pow(denominator, p-2, p)) % p
else:
# 点加运算
# 斜率 λ = (y2 - y1) / (x2 - x1) mod p
numerator = (y2 - y1) % p
denominator = (x2 - x1) % p
lambda_val = (numerator * pow(denominator, p-2, p)) % p
# 计算新点坐标
x3 = (pow(lambda_val, 2, p) - x1 - x2) % p
y3 = (lambda_val * (x1 - x3) - y1) % p
return (x3, y3)
def scalar_multiplication(self, k, P):
"""椭圆曲线标量乘法: kP"""
if k == 0:
return None
if k == 1:
return P
# 使用 double-and-add 算法
result = None
addend = P
while k:
if k & 1:
result = self.point_addition(result, addend)
addend = self.point_addition(addend, addend)
k >>= 1
return result
def is_point_on_curve(self, point):
"""验证点是否在曲线上"""
if point is None:
return True # 无穷远点
x, y = point
left = pow(y, 2, self.p)
right = (pow(x, 3, self.p) + self.a * x + self.b) % self.p
return left == right
def elliptic_curve_examples():
print("\n=== 椭圆曲线数学原理示例 ===")
# 使用 secp256k1 曲线参数（比特币使用的曲线）
# y^2 = x^3 + 7 (mod p)
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
curve = EllipticCurveMathematics(a, b, p)
# 生成元点 G (secp256k1 的生成元)
G = (
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
)
print(f"椭圆曲线: y^2 = x^3 + {a}x + {b} (mod {p})")
print(f"生成元 G = ({G[0]:x}, {G[1]:x})")
print(f"G 在曲线上: {curve.is_point_on_curve(G)}")
# 点加运算: 2G = G + G
G2 = curve.point_addition(G, G)
print(f"2G = ({G2[0]:x}, {G2[1]:x})")
print(f"2G 在曲线上: {curve.is_point_on_curve(G2)}")
# 标量乘法: 3G = 2G + G
G3 = curve.scalar_multiplication(3, G)
print(f"3G = ({G3[0]:x}, {G3[1]:x})")
# 验证标量乘法正确性
G3_add = curve.point_addition(G2, G)
print(f"3G 验证: {G3 == G3_add}")
# ECDH 密钥交换数学原理
print("\n=== ECDH 密钥交换数学原理 ===")
# Alice 生成私钥和公钥
alice_private = random.randint(1, 1000) # 简化示例
alice_public = curve.scalar_multiplication(alice_private, G)
# Bob 生成私钥和公钥
bob_private = random.randint(1, 1000) # 简化示例
bob_public = curve.scalar_multiplication(bob_private, G)
# 共享密钥计算
alice_shared = curve.scalar_multiplication(alice_private, bob_public)
bob_shared = curve.scalar_multiplication(bob_private, alice_public)
print(f"Alice 私钥: {alice_private}, 公钥: ({alice_public[0]:x}, ...)")
print(f"Bob 私钥: {bob_private}, 公钥: ({bob_public[0]:x}, ...)")
print(f"共享密钥相等: {alice_shared == bob_shared}")
elliptic_curve_examples()
哈希函数数学原理
class HashFunctionMathematics:
"""哈希函数数学原理"""
@staticmethod
def sha256_compression_function(state, block):
"""SHA-256 压缩函数数学原理（简化版）"""
# 常量定义
K = [
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
# ... 其他常量
]
# 消息扩展
W = [0] * 64
for i in range(16):
W[i] = int.from_bytes(block[i*4:(i+1)*4], 'big')
for i in range(16, 64):
s0 = HashFunctionMathematics.rotate_right(W[i-15], 7) ^ \
HashFunctionMathematics.rotate_right(W[i-15], 18) ^ \
(W[i-15] >> 3)
s1 = HashFunctionMathematics.rotate_right(W[i-2], 17) ^ \
HashFunctionMathematics.rotate_right(W[i-2], 19) ^ \
(W[i-2] >> 10)
W[i] = (W[i-16] + s0 + W[i-7] + s1) & 0xFFFFFFFF
# 压缩循环
a, b, c, d, e, f, g, h = state
for i in range(64):
S1 = HashFunctionMathematics.rotate_right(e, 6) ^ \
HashFunctionMathematics.rotate_right(e, 11) ^ \
HashFunctionMathematics.rotate_right(e, 25)
ch = (e & f) ^ ((~e) & g)
temp1 = (h + S1 + ch + K[i] + W[i]) & 0xFFFFFFFF
S0 = HashFunctionMathematics.rotate_right(a, 2) ^ \
HashFunctionMathematics.rotate_right(a, 13) ^ \
HashFunctionMathematics.rotate_right(a, 22)
maj = (a & b) ^ (a & c) ^ (b & c)
temp2 = (S0 + maj) & 0xFFFFFFFF
h = g
g = f
f = e
e = (d + temp1) & 0xFFFFFFFF
d = c
c = b
b = a
a = (temp1 + temp2) & 0xFFFFFFFF
# 更新状态
new_state = [
(state[0] + a) & 0xFFFFFFFF,
(state[1] + b) & 0xFFFFFFFF,
(state[2] + c) & 0xFFFFFFFF,
(state[3] + d) & 0xFFFFFFFF,
(state[4] + e) & 0xFFFFFFFF,
(state[5] + f) & 0xFFFFFFFF,
(state[6] + g) & 0xFFFFFFFF,
(state[7] + h) & 0xFFFFFFFF
]
return new_state
@staticmethod
def rotate_right(x, n):
"""循环右移"""
return (x >> n) | (x << (32 - n)) & 0xFFFFFFFF
@staticmethod
def merkle_damgard_construction(message, block_size=64):
"""Merkle-Damgård 结构数学原理"""
# 初始向量
IV = 0x6a09e667 # SHA-256 的初始值之一
# 消息填充
original_length = len(message)
message = message + b'\x80' # 添加1比特
# 填充0直到长度满足 (length + 8) % block_size == 0
while (len(message) + 8) % block_size != 0:
message += b'\x00'
# 添加原始长度（64位）
message += original_length.to_bytes(8, 'big')
# 处理每个块
state = [IV] * 8 # SHA-256 有8个状态字
for i in range(0, len(message), block_size):
block = message[i:i+block_size]
state = HashFunctionMathematics.sha256_compression_function(state, block)
return state
@staticmethod
def avalanche_effect_test():
"""雪崩效应测试"""
import hashlib
# 测试微小变化对哈希值的影响
message1 = b"Hello, World!"
message2 = b"Hello, World?" # 仅改变最后一个字符
hash1 = hashlib.sha256(message1).hexdigest()
hash2 = hashlib.sha256(message2).hexdigest()
# 计算汉明距离
def hamming_distance_hex(hex1, hex2):
bytes1 = bytes.fromhex(hex1)
bytes2 = bytes.fromhex(hex2)
distance = 0
for b1, b2 in zip(bytes1, bytes2):
xor = b1 ^ b2
distance += bin(xor).count('1')
return distance
distance = hamming_distance_hex(hash1, hash2)
total_bits = len(hash1) * 4 # 每个十六进制字符4位
print(f"消息1: {message1}")
print(f"消息2: {message2}")
print(f"哈希1: {hash1}")
print(f"哈希2: {hash2}")
print(f"汉明距离: {distance}/{total_bits} 位")
print(f"变化比例: {distance/total_bits:.2%}")
def hash_mathematics_examples():
print("\n=== 哈希函数数学原理示例 ===")
# 雪崩效应测试
HashFunctionMathematics.avalanche_effect_test()
# 生日攻击数学原理
print("\n=== 生日攻击数学原理 ===")
def birthday_attack_probability(n_bits):
"""计算生日攻击成功的概率"""
# 对于 n 位哈希，有 2^n 个可能输出
n = 2 ** n_bits
# 生日悖论概率公式
# 碰撞概率 ≈ 1 - exp(-k(k-1)/(2n))
# 其中 k 是哈希次数
probabilities = []
for k in [2**10, 2**20, 2**30, 2**40]:
prob = 1 - math.exp(-k * (k-1) / (2 * n))
probabilities.append((k, prob))
return probabilities
for bits in [64, 128, 256]:
probs = birthday_attack_probability(bits)
print(f"\n{bits} 位哈希的生日攻击概率:")
for k, prob in probs:
print(f" 尝试 {k} 次哈希，碰撞概率: {prob:.6f}")
hash_mathematics_examples()
密钥交换数学原理
class KeyExchangeMathematics:
"""密钥交换数学原理"""
@staticmethod
def diffie_hellman_math():
"""Diffie-Hellman 密钥交换数学原理"""
# 选择大素数 p 和原根 g
p = 23 # 小素数用于演示
g = 5 # 原根
print("=== Diffie-Hellman 密钥交换数学原理 ===")
print(f"公开参数: 素数 p = {p}, 原根 g = {g}")
# Alice 选择私钥
a_private = random.randint(2, p-2)
a_public = pow(g, a_private, p)
# Bob 选择私钥
b_private = random.randint(2, p-2)
b_public = pow(g, b_private, p)
print(f"\nAlice: 私钥 a = {a_private}, 公钥 A = g^a mod p = {a_public}")
print(f"Bob: 私钥 b = {b_private}, 公钥 B = g^b mod p = {b_public}")
# 共享密钥计算
alice_shared = pow(b_public, a_private, p)
bob_shared = pow(a_public, b_private, p)
print(f"\n共享密钥:")
print(f"Alice 计算: B^a mod p = {alice_shared}")
print(f"Bob 计算: A^b mod p = {bob_shared}")
print(f"密钥匹配: {alice_shared == bob_shared}")
# 离散对数问题难度
print(f"\n离散对数问题:")
print(f"已知 g = {g}, p = {p}, A = {a_public}")
print(f"求解 a 使得 g^a ≡ A (mod p)")
# 暴力破解尝试
found = False
for i in range(1, p):
if pow(g, i, p) == a_public:
print(f"暴力破解成功: a = {i} (实际值: {a_private})")
found = True
break
if not found:
print("暴力破解失败 (在演示范围内)")
@staticmethod
def discrete_logarithm_attack(p, g, target):
"""离散对数攻击算法（简化版）"""
# 小步大步算法 (Baby-step Giant-step)
m = math.isqrt(p) + 1
# 预计算 g^j mod p (小步)
baby_steps = {}
for j in range(m):
baby_steps[pow(g, j, p)] = j
# 计算 g^(-m) mod p
g_inv_m = pow(g, -m, p)
# 大步搜索
for i in range(m):
y = (target * pow(g_inv_m, i, p)) % p
if y in baby_steps:
return i * m + baby_steps[y]
return None
def key_exchange_mathematics():
print("\n=== 密钥交换数学原理 ===")
# Diffie-Hellman 数学原理
KeyExchangeMathematics.diffie_hellman_math()
# 离散对数攻击示例
print("\n=== 离散对数攻击示例 ===")
p = 1019 # 小素数用于演示
g = 2
a_private = 123
a_public = pow(g, a_private, p)
print(f"离散对数问题: 在模 {p} 下，求解 2^x ≡ {a_public}")
# 使用小步大步算法
solution = KeyExchangeMathematics.discrete_logarithm_attack(p, g, a_public)
if solution:
print(f"小步大步算法求解: x = {solution}")
print(f"验证: 2^{solution} mod {p} = {pow(2, solution, p)}")
print(f"正确性: {solution == a_private}")
else:
print("小步大步算法求解失败")
key_exchange_mathematics()
数字签名数学原理
class DigitalSignatureMathematics:
"""数字签名数学原理"""
@staticmethod
def dsa_signature_math():
"""DSA 数字签名数学原理"""
# 全局参数
p = 0x86F5CA03DCFEB225063FF830A0C769B9DD9D6153AD91D7CE27F787C43278B447E6533B86B18BED6E8A48B784A14C252C5BE0DBF60B86D6385BD2F12FB763ED8873ABFD3F5BA2E0A8C0A59082EAC056935E529DAF7C610467899C77ADEDFC846C881870B7B19B2B58F9BE0521A17002E3BDD6B86685EE90B3D9A1B02B782B1779
q = 0x996F967F6C8E388D9E28D01E205FBA957A5698B1
g = 0x07B0F92546150B62514BB771E2A0C0CE387F03BDA6C56B505209FF25FD3C133D89BBCD97E904E09114D9A7DEFDEADFC9078EA544D2E401AEECC40BB9FBBF78FD87995A10A1C27CB7789B594BA7EFB5C4326A9FE59A070E136DB77175464ADCA417BE5DCE2F40D10A46A3A3943F26AB7FD9C0398FF8C76EE0A56826A8A88F1DBD
print("=== DSA 数字签名数学原理 ===")
print(f"全局参数:")
print(f"p = {p}")
print(f"q = {q}")
print(f"g = {g}")
# 密钥生成
x = random.randint(1, q-1) # 私钥
y = pow(g, x, p) # 公钥
print(f"\n密钥生成:")
print(f"私钥 x = {x}")
print(f"公钥 y = g^x mod p = {y}")
# 签名过程
message = b"Hello, DSA!"
message_hash = hashlib.sha1(message).digest()
h = int.from_bytes(message_hash, 'big') % q
k = random.randint(1, q-1)
r = pow(g, k, p) % q
s = (ModularArithmetic.mod_inverse(k, q) * (h + x * r)) % q
print(f"\n签名过程:")
print(f"消息哈希 h = {h}")
print(f"随机数 k = {k}")
print(f"签名: (r = {r}, s = {s})")
# 验证过程
w = ModularArithmetic.mod_inverse(s, q)
u1 = (h * w) % q
u2 = (r * w) % q
v = (pow(g, u1, p) * pow(y, u2, p) % p) % q
print(f"\n验证过程:")
print(f"w = s^(-1) mod q = {w}")
print(f"u1 = h*w mod q = {u1}")
print(f"u2 = r*w mod q = {u2}")
print(f"v = (g^u1 * y^u2 mod p) mod q = {v}")
print(f"验证结果: {v == r}")
return (r, s), (p, q, g, y), message
@staticmethod
def ecdsa_mathematics():
"""ECDSA 椭圆曲线数字签名数学原理"""
# 使用 secp256k1 曲线
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
curve = EllipticCurveMathematics(a, b, p)
# 生成元
G = (
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
)
# 曲线阶
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
print("\n=== ECDSA 数字签名数学原理 ===")
# 密钥生成
d = random.randint(1, n-1) # 私钥
Q = curve.scalar_multiplication(d, G) # 公钥
print(f"私钥 d = {d}")
print(f"公钥 Q = ({Q[0]:x}, {Q[1]:x})")
# 签名过程
message = b"Hello, ECDSA!"
message_hash = hashlib.sha256(message).digest()
h = int.from_bytes(message_hash, 'big') % n
k = random.randint(1, n-1)
kG = curve.scalar_multiplication(k, G)
r = kG[0] % n
s = (ModularArithmetic.mod_inverse(k, n) * (h + d * r)) % n
print(f"\n签名过程:")
print(f"消息哈希 h = {h}")
print(f"随机数 k = {k}")
print(f"签名: (r = {r}, s = {s})")
# 验证过程
w = ModularArithmetic.mod_inverse(s, n)
u1 = (h * w) % n
u2 = (r * w) % n
u1G = curve.scalar_multiplication(u1, G)
u2Q = curve.scalar_multiplication(u2, Q)
point_sum = curve.point_addition(u1G, u2Q)
v = point_sum[0] % n if point_sum else 0
print(f"\n验证过程:")
print(f"w = s^(-1) mod n = {w}")
print(f"u1 = h*w mod n = {u1}")
print(f"u2 = r*w mod n = {u2}")
print(f"验证点: ({point_sum[0]:x}, {point_sum[1]:x})" if point_sum else "无穷远点")
print(f"v = x-coordinate mod n = {v}")
print(f"验证结果: {v == r}")
def digital_signature_mathematics():
print("\n=== 数字签名数学原理 ===")
# DSA 数学原理
signature, public_key, message = DigitalSignatureMathematics.dsa_signature_math()
# ECDSA 数学原理
DigitalSignatureMathematics.ecdsa_mathematics()
digital_signature_mathematics()