现代密码学 | 椭圆曲线密码学

现代密码学 | 椭圆曲线密码学—附py代码

article/2025/6/7 23:08:46

Elliptic Curve Cryptography

椭圆曲线密码学（ECC）是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。

椭圆曲线密码学是多种数字签名算法的基础，例如椭圆曲线数字签名算法（ECDSA）。这些签名对于确保数据的真实性和完整性至关重要。椭圆曲线迪菲-赫尔曼（ECDH）之类的协议能够在不安全的信道上实现安全的密钥交换，从而在没有预先共享密钥的情况下实现安全通信。

ECC 的吸引力在于其高效性以及使用较短密钥即可提供高级别的保护，这使其非常适合计算能力、存储和带宽有限的系统。

椭圆曲线密码学能够以比RSA小得多的密钥尺寸提供相当的安全性。例如，256位的椭圆曲线密码学密钥所提供的安全性相当于3072位的RSA密钥。这使得计算速度更快，功耗更低。
由于密钥尺寸较小使得椭圆曲线密码学特别适合计算能力和内存有限的设备，例如移动设备和物联网设备。也减少了加密操作期间传输的数据量，从而在带宽受限的环境中显著提升了性能。

–

ECC 建立在椭圆曲线理论的基础上，椭圆曲线由方程 y² = x³ + ax + b 定义，其中 a 和 b 是系数，满足 4a³ + 27b² ≠ 0 的条件以确保曲线是非奇异的。密码学中使用的椭圆曲线通常定义在有限域上（要么是素数域 Fp，要么是二进制域 F₂^m），从而曲线上的点数是有限的。

ECC 的核心原理在于椭圆曲线离散对数问题（ECDLP）的难度。简单来说，给定曲线上的两个点 A 和 B，找到满足 A = k × B 的整数 k 在计算上是不可行的。其中，× 表示椭圆曲线点乘法。正是这种难以解决性使得椭圆曲线密码学成为密码学中一种强大的工具。

–

py代码示例，包含密钥生成、ECDSA签名和验证功能（仅供参考）

import random
import hashlib
from typing import Tuple# 定义椭圆曲线参数（使用secp256k1曲线 - 比特币使用的曲线）
class EllipticCurve:def __init__(self):# 曲线参数：y² = x³ + a*x + b mod pself.p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2Fself.a = 0self.b = 7# 基点（生成元）self.G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)# 基点的阶（素数）self.n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141self.h = 1  # 余因子# 椭圆曲线点运算
class ECPoint:def __init__(self, curve: EllipticCurve, x: int = None, y: int = None):self.curve = curveself.x = xself.y = y# 检查点是否在曲线上（无穷远点除外）if x is not None and y is not None and not self.is_infinity():if (y * y) % curve.p != (x*x*x + curve.a*x + curve.b) % curve.p:raise ValueError(f"点 ({x}, {y}) 不在曲线上")def is_infinity(self) -> bool:"""检查是否为无穷远点"""return self.x is None and self.y is Nonedef __eq__(self, other) -> bool:"""检查两点是否相等"""if not isinstance(other, ECPoint):return Falsereturn self.x == other.x and self.y == other.ydef __add__(self, other):"""点加法"""curve = self.curve# 处理无穷远点if self.is_infinity():return otherif other.is_infinity():return self# 处理点与自身的加法（切线）if self == other:# 计算斜率：m = (3x₁² + a) / (2y₁) mod pif self.y == 0:  # 垂直线return ECPoint(curve)  # 返回无穷远点numerator = (3 * self.x * self.x + curve.a) % curve.pdenominator = (2 * self.y) % curve.pm = (numerator * mod_inverse(denominator, curve.p)) % curve.pelse:# 不同点的加法if self.x == other.x:  # 垂直线return ECPoint(curve)  # 返回无穷远点# 计算斜率：m = (y₂ - y₁) / (x₂ - x₁) mod pnumerator = (other.y - self.y) % curve.pdenominator = (other.x - self.x) % curve.pm = (numerator * mod_inverse(denominator, curve.p)) % curve.p# 计算新点坐标x3 = (m * m - self.x - other.x) % curve.py3 = (m * (self.x - x3) - self.y) % curve.preturn ECPoint(curve, x3, y3)def __rmul__(self, scalar: int):"""标量乘法（快速幂算法）"""# 处理无穷远点if scalar == 0 or self.is_infinity():return ECPoint(self.curve)# 使用快速幂算法result = ECPoint(self.curve)  # 无穷远点addend = selfwhile scalar:if scalar & 1:result += addendaddend += addendscalar >>= 1return resultdef __repr__(self):return f"ECPoint({self.x}, {self.y})" if not self.is_infinity() else "ECPoint(Inf)"def mod_inverse(a: int, p: int) -> int:"""使用扩展欧几里得算法计算模逆元"""# 处理特殊情况if a == 0:raise ValueError("0没有逆元")if a < 0:a = a % p# 扩展欧几里得算法t0, t1 = 0, 1r0, r1 = p, awhile r1 != 0:q = r0 // r1t0, t1 = t1, t0 - q * t1r0, r1 = r1, r0 - q * r1if r0 != 1:raise ValueError(f"{a} 在模 {p} 下没有逆元")return t0 % p# ECC密钥生成
def generate_ecc_keypair(curve: EllipticCurve) -> Tuple[int, ECPoint]:"""生成ECC密钥对"""# 随机生成私钥 (1 <= d < n)private_key = random.randint(1, curve.n - 1)# 计算公钥：公钥 = 私钥 * 基点GG = ECPoint(curve, curve.G[0], curve.G[1])public_key = private_key * Greturn private_key, public_key# ECDSA签名
def ecdsa_sign(curve: EllipticCurve, private_key: int, message: bytes) -> Tuple[int, int]:"""ECDSA签名算法"""# 计算消息哈希h = int.from_bytes(hashlib.sha256(message).digest(), 'big')h = h % curve.n  # 确保在[0, n-1]范围内if h == 0:h = 1# 生成临时密钥对k = random.randint(1, curve.n - 1)G = ECPoint(curve, curve.G[0], curve.G[1])R = k * G# 计算签名r = R.x % curve.nif r == 0:return ecdsa_sign(curve, private_key, message)  # 重新选择ks = (mod_inverse(k, curve.n) * (h + private_key * r)) % curve.nif s == 0:return ecdsa_sign(curve, private_key, message)  # 重新选择kreturn r, s# ECDSA验证
def ecdsa_verify(curve: EllipticCurve, public_key: ECPoint, message: bytes, signature: Tuple[int, int]) -> bool:"""ECDSA验证算法"""r, s = signature# 验证签名值范围if r < 1 or r >= curve.n or s < 1 or s >= curve.n:return False# 计算消息哈希h = int.from_bytes(hashlib.sha256(message).digest(), 'big')h = h % curve.nif h == 0:h = 1# 计算中间值w = mod_inverse(s, curve.n)u1 = (h * w) % curve.nu2 = (r * w) % curve.n# 计算点G = ECPoint(curve, curve.G[0], curve.G[1])P = u1 * G + u2 * public_key# 验证签名if P.is_infinity():return Falsereturn r == (P.x % curve.n)# 示例测试
if __name__ == "__main__":# 创建椭圆曲线curve = EllipticCurve()# 生成密钥对private_key, public_key = generate_ecc_keypair(curve)print(f"私钥: {private_key}")print(f"公钥: {public_key}")# 签名消息message = b"Hello, Elliptic Curve Cryptography!"signature = ecdsa_sign(curve, private_key, message)print(f"\n消息: '{message.decode()}'")print(f"签名: (r={signature[0]}, s={signature[1]})")# 验证签名is_valid = ecdsa_verify(curve, public_key, message, signature)print(f"\n签名验证结果: {'有效' if is_valid else '无效'}")# 尝试篡改消息tampered_message = b"Hello, Hacker!"is_valid_tampered = ecdsa_verify(curve, public_key, tampered_message, signature)print(f"篡改消息后验证结果: {'有效' if is_valid_tampered else '无效'} (应为无效)")# 尝试篡改签名tampered_signature = (signature[0], signature[1] + 1)is_valid_tampered_sig = ecdsa_verify(curve, public_key, message, tampered_signature)print(f"篡改签名后验证结果: {'有效' if is_valid_tampered_sig else '无效'} (应为无效)")