035_密码学实战：数字签名技术深度解析——从RSA到ECDSA的完整指南

手写签名 vs 数字签名：
┌───────────────┬─────────────────────┬─────────────────────┐
│ 特性          │ 手写签名            │ 数字签名            │
├───────────────┼─────────────────────┼─────────────────────┤
│ 唯一性        │ 较低，可被模仿      │ 极高，基于密码学    │
│ 防篡改        │ 低，文档可被修改    │ 高，修改会破坏签名  │
│ 验证方式      │ 人工视觉比对        │ 密码学算法自动验证  │
│ 可复制性      │ 不可直接复制        │ 可复制但验证不变    │
│ 绑定关系      │ 弱，仅与签名本身相关 │ 强，与整个文档内容相关 │
└───────────────┴─────────────────────┴─────────────────────┘

签名流程：
消息 → 哈希函数 → 消息摘要 → 私钥加密 → 数字签名 → 消息+签名

验证流程：
消息+签名 → 公钥解密 → 原始摘要
       ↓
   消息 → 哈希函数 → 计算摘要 → 比较 → 验证结果

import math
from Crypto.Util import number

# 简化的RSA签名示例（仅用于演示，不安全）
def simple_rsa_signature_demo():
    # 1. 密钥生成（在实际应用中，应使用更大的素数）
    p = 61  # 素数
    q = 53  # 素数
    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = 17  # 公钥指数
    
    # 计算私钥指数d
    def mod_inverse(a, m):
        g, x, y = extended_gcd(a, m)
        if g != 1:
            raise ValueError("模逆不存在")
        else:
            return x % m
    
    def extended_gcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            g, y, x = extended_gcd(b % a, a)
            return (g, x - (b // a) * y, y)
    
    d = mod_inverse(e, phi_n)
    
    print(f"密钥生成完成:")
    print(f"p = {p}, q = {q}")
    print(f"n = {n}")
    print(f"phi(n) = {phi_n}")
    print(f"公钥 (n, e) = ({n}, {e})")
    print(f"私钥 (n, d) = ({n}, {d})")
    
    # 2. 签名生成（简化版，实际应先哈希）
    message = 42  # 简化的消息表示
    signature = pow(message, d, n)
    print(f"\n签名生成:")
    print(f"消息 = {message}")
    print(f"签名 = {signature}")
    
    # 3. 签名验证
    verified_message = pow(signature, e, n)
    is_valid = (verified_message == message)
    print(f"\n签名验证:")
    print(f"验证结果 = {verified_message}")
    print(f"签名有效: {is_valid}")

# 运行演示
simple_rsa_signature_demo()

0x00 || 0x01 || 0xFF...FF || 0x00 || ASN.1编码的哈希算法OID || 哈希值

y² = x³ + ax + b (mod p)

算法性能对比：
┌────────────┬──────────┬──────────┬───────────┐
│ 算法       │ 密钥生成 │ 签名生成 │ 签名验证  │
├────────────┼──────────┼──────────┼───────────┤
│ RSA (2048) │ 慢       │ 慢       │ 快        │
│ DSA (2048) │ 中       │ 中       │ 中        │
│ ECDSA (P-256) │ 快    │ 快       │ 快        │
└────────────┴──────────┴──────────┴───────────┘

from Crypto.PublicKey import RSA
from Crypto.Signature import pkcs1_15
from Crypto.Hash import SHA256
from Crypto import Random
import base64

def generate_rsa_keys(key_size=2048):
    """生成RSA密钥对"""
    random_generator = Random.new().read
    key = RSA.generate(key_size, random_generator)
    private_key = key.export_key()
    public_key = key.publickey().export_key()
    return private_key, public_key

def rsa_sign(message, private_key_pem):
    """使用RSA私钥对消息进行签名"""
    # 加载私钥
    key = RSA.import_key(private_key_pem)
    # 计算消息的哈希值
    h = SHA256.new(message)
    # 使用PKCS#1 v1.5进行签名
    signature = pkcs1_15.new(key).sign(h)
    # 将签名转换为Base64编码的字符串
    return base64.b64encode(signature)

def rsa_verify(message, signature_b64, public_key_pem):
    """使用RSA公钥验证签名"""
    try:
        # 加载公钥
        key = RSA.import_key(public_key_pem)
        # 计算消息的哈希值
        h = SHA256.new(message)
        # 解码Base64编码的签名
        signature = base64.b64decode(signature_b64)
        # 验证签名
        pkcs1_15.new(key).verify(h, signature)
        return True
    except Exception:
        return False

# 演示使用
def rsa_signature_demo():
    print("RSA数字签名演示")
    print("=" * 50)
    
    # 1. 生成密钥对
    print("生成RSA密钥对...")
    private_key, public_key = generate_rsa_keys()
    print(f"私钥长度: {len(private_key)} 字节")
    print(f"公钥长度: {len(public_key)} 字节")
    
    # 2. 准备消息
    message = b"这是一个测试消息，用于RSA数字签名演示"
    print(f"\n原始消息: {message.decode()}")
    
    # 3. 生成签名
    print("\n生成数字签名...")
    signature = rsa_sign(message, private_key)
    print(f"签名 (Base64): {signature.decode()}")
    
    # 4. 验证签名
    print("\n验证数字签名...")
    is_valid = rsa_verify(message, signature, public_key)
    print(f"签名有效: {is_valid}")
    
    # 5. 验证被篡改的消息
    tampered_message = b"这是一个被篡改的测试消息，用于RSA数字签名演示"
    print(f"\n验证被篡改的消息: {tampered_message.decode()}")
    is_valid = rsa_verify(tampered_message, signature, public_key)
    print(f"签名有效: {is_valid}")

# 运行演示
rsa_signature_demo()

from Crypto.PublicKey import ECC
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
import base64

def generate_ecdsa_keys(curve='P-256'):
    """生成ECDSA密钥对"""
    key = ECC.generate(curve=curve)
    private_key = key.export_key(format='PEM')
    public_key = key.public_key().export_key(format='PEM')
    return private_key, public_key

def ecdsa_sign(message, private_key_pem):
    """使用ECDSA私钥对消息进行签名"""
    # 加载私钥
    key = ECC.import_key(private_key_pem)
    # 计算消息的哈希值
    h = SHA256.new(message)
    # 使用FIPS 186-3标准进行签名
    signer = DSS.new(key, 'fips-186-3')
    signature = signer.sign(h)
    # 将签名转换为Base64编码的字符串
    return base64.b64encode(signature)

def ecdsa_verify(message, signature_b64, public_key_pem):
    """使用ECDSA公钥验证签名"""
    try:
        # 加载公钥
        key = ECC.import_key(public_key_pem)
        # 计算消息的哈希值
        h = SHA256.new(message)
        # 解码Base64编码的签名
        signature = base64.b64decode(signature_b64)
        # 验证签名
        verifier = DSS.new(key, 'fips-186-3')
        verifier.verify(h, signature)
        return True
    except Exception:
        return False

# 演示使用
def ecdsa_signature_demo():
    print("ECDSA数字签名演示")
    print("=" * 50)
    
    # 1. 生成密钥对
    print("生成ECDSA密钥对...")
    private_key, public_key = generate_ecdsa_keys()
    print(f"私钥长度: {len(private_key)} 字节")
    print(f"公钥长度: {len(public_key)} 字节")
    
    # 2. 准备消息
    message = b"这是一个测试消息，用于ECDSA数字签名演示"
    print(f"\n原始消息: {message.decode()}")
    
    # 3. 生成签名
    print("\n生成数字签名...")
    signature = ecdsa_sign(message, private_key)
    print(f"签名 (Base64): {signature.decode()}")
    
    # 4. 验证签名
    print("\n验证数字签名...")
    is_valid = ecdsa_verify(message, signature, public_key)
    print(f"签名有效: {is_valid}")
    
    # 5. 验证被篡改的消息
    tampered_message = b"这是一个被篡改的测试消息，用于ECDSA数字签名演示"
    print(f"\n验证被篡改的消息: {tampered_message.decode()}")
    is_valid = ecdsa_verify(tampered_message, signature, public_key)
    print(f"签名有效: {is_valid}")

# 运行演示
ecdsa_signature_demo()

def rsa_common_modulus_attack(n, e1, e2, c1, c2):
    """RSA共模攻击实现"""
    # 计算贝祖系数s1, s2使得e1*s1 + e2*s2 = gcd(e1, e2)
    def extended_gcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            g, y, x = extended_gcd(b % a, a)
            return (g, x - (b // a) * y, y)
    
    g, s1, s2 = extended_gcd(e1, e2)
    
    # 由于e1和e2互质，g=1
    assert g == 1, "e1和e2不互质"
    
    # 处理负数情况
    if s1 < 0:
        s1 = -s1
        c1 = pow(c1, -1, n)  # 计算模逆
    elif s2 < 0:
        s2 = -s2
        c2 = pow(c2, -1, n)  # 计算模逆
    
    # 计算结果: m = (c1^s1 * c2^s2) mod n
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    
    return m

def ecdsa_reuse_k_attack(s1, s2, r, h1, h2, n):
    """ECDSA重用k攻击实现"""
    # 计算k = (h1 - h2) * (s1 - s2)^(-1) mod n
    numerator = (h1 - h2) % n
    denominator = pow((s1 - s2) % n, -1, n)
    k = (numerator * denominator) % n
    
    # 计算私钥d = (s1 * k - h1) * r^(-1) mod n
    d = ((s1 * k - h1) % n) * pow(r, -1, n) % n
    
    return d, k

def analyze_timing_leakage(signature_function, message, iterations=1000):
    """分析签名过程中的时间侧信道信息"""
    import time
    
    timings = []
    for i in range(iterations):
        start = time.time()
        signature_function(message)
        end = time.time()
        timings.append(end - start)
    
    # 分析时间模式，寻找可能的密钥信息
    # 这里只是一个简单的演示，实际的侧信道分析要复杂得多
    avg_time = sum(timings) / len(timings)
    max_time = max(timings)
    min_time = min(timings)
    
    print(f"平均签名时间: {avg_time:.10f} 秒")
    print(f"最长签名时间: {max_time:.10f} 秒")
    print(f"最短签名时间: {min_time:.10f} 秒")
    print(f"时间差异: {max_time - min_time:.10f} 秒")
    
    # 如果时间差异较大，可能存在侧信道泄露
    if max_time - min_time > 0.001:
        print("警告: 可能存在时间侧信道泄露")

def rsa_partial_key_recovery(partial_d, n, e, bits_known):
    """RSA部分私钥恢复攻击"""
    # 这里实现的是Coppersmith定理在RSA部分密钥恢复中的应用
    # 当知道d的高位时，可以恢复完整的d
    
    # 简化版本，实际实现需要使用格基规约算法
    # 这里只是概念演示
    print(f"已知d的高位 {bits_known} 位: {partial_d:x}")
    print("应用Coppersmith定理恢复完整私钥...")
    print("注意: 实际攻击需要使用专业的格基规约库")
    
    # 在实际CTF中，可能会使用诸如sage数学库来实现
    # 这里仅作示意
    return "需要更复杂的实现来恢复完整私钥"

def demonstrate_parameter_injection_attack():
    """演示参数注入攻击"""
    print("参数注入攻击演示:")
    print("1. 攻击者可以尝试注入特殊构造的参数")
    print("2. 例如，在JSON Web Token中修改算法字段为'none'")
    print("3. 或者在验证函数中利用类型混淆漏洞")
    print("\n防御措施:")
    print("- 严格验证所有输入参数")
    print("- 明确指定算法类型，不接受用户提供的算法选择")
    print("- 对所有参数进行类型检查和范围验证")

def explain_length_extension_in_signatures():
    """解释签名中的长度扩展攻击"""
    print("签名中的长度扩展攻击:")
    print("- 当签名直接应用于消息，而不是先计算哈希时")
    print("- 攻击者可能能够在不知道私钥的情况下扩展签名")
    print("\n防御措施:")
    print("- 始终先对消息计算哈希，再进行签名")
    print("- 使用经过验证的签名库和标准")
    print("- 定期更新和审计签名实现")

def timing_attack_simulation(validate_signature, target_message, max_iterations=10000):
    """模拟针对签名验证的时间攻击"""
    print(f"模拟时间攻击，目标消息: {target_message.decode()}")
    
    # 简化的时间攻击模拟
    # 实际攻击会更复杂，需要统计分析和信号处理
    
    # 这里只是概念演示，展示如何测量和分析时间差异
    possible_chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
    best_char = None
    max_time = 0
    
    for char in possible_chars[:20]:  # 仅测试前20个字符作为演示
        test_signature = ("a" * 20 + char).encode()
        total_time = 0
        
        for _ in range(100):
            import time
            start = time.time()
            validate_signature(target_message, test_signature)
            end = time.time()
            total_time += (end - start)
        
        avg_time = total_time / 100
        print(f"字符 '{char}' 的平均验证时间: {avg_time:.10f} 秒")
        
        if avg_time > max_time:
            max_time = avg_time
            best_char = char
    
    print(f"\n可能的密钥字符: {best_char}")
    print("注意: 这只是一个简化的模拟，实际的时间攻击需要更复杂的技术")

def group_signature_concept():
    """群签名概念演示"""
    print("群签名系统组成:")
    print("1. 群管理员: 负责群体管理、成员加入和身份追踪")
    print("2. 群成员: 可以生成代表群体的签名")
    print("3. 验证者: 验证签名是否来自有效群体")
    
    print("\n群签名工作流程:")
    print("1. 初始化阶段: 群管理员设置系统参数，生成群公钥")
    print("2. 加入阶段: 新成员向群管理员注册，获取成员密钥")
    print("3. 签名阶段: 群成员使用成员密钥生成群签名")
    print("4. 验证阶段: 验证者使用群公钥验证签名")
    print("5. 打开阶段: 必要时，群管理员可以揭示签名者身份")
    
    print("\n典型群签名方案:")
    print("- ACJT方案: 首个高效的群签名方案")
    print("- BBS方案: 基于双线性映射的群签名")
    print("- 基于格的群签名: 后量子密码学中的群签名方案")

def ring_signature_demo():
    """环签名概念演示"""
    print("环签名原理:")
    print("1. 签名者选择一组公钥（包括自己的）形成一个环")
    print("2. 对于环中的每个公钥，生成对应的签名部分")
    print("3. 利用自己的私钥生成一个特殊的签名部分，连接其他部分")
    print("4. 验证者只能确认签名来自环中某成员，无法确定具体是谁")
    
    print("\n环签名的数学表示:")
    print("签名: σ = (c₀, s₁, s₂, ..., sₙ)")
    print("其中环成员为: P₀, P₁, ..., Pₙ")
    print("如果签名者是Pᵢ，那么cᵢ由签名者的私钥生成")
    print("其他cⱼ (j≠i) 通过哈希链计算得到")
    
    print("\n实现环签名的Python伪代码:")
    print("'''
    def ring_sign(message, private_key, ring_pubkeys):
        # 找到签名者在环中的位置
        signer_index = ring_pubkeys.index(get_pubkey(private_key))
        
        # 生成随机值和初始哈希
        s = [random() for _ in ring_pubkeys]
        c = [0] * len(ring_pubkeys)
        
        # 从签名者的下一个位置开始计算哈希链
        current_index = (signer_index + 1) % len(ring_pubkeys)
        c[current_index] = hash(message + g(s[current_index], ring_pubkeys[current_index]))
        
        # 继续计算哈希链
        while current_index != signer_index:
            next_index = (current_index + 1) % len(ring_pubkeys)
            c[next_index] = hash(c[current_index] + g(s[current_index], ring_pubkeys[current_index]))
            current_index = next_index
        
        # 使用私钥计算签名者的s值
        s[signer_index] = solve_for_s(private_key, c[(signer_index - 1) % len(ring_pubkeys)], c[signer_index])
        
        return (c[0], s)
    
    def ring_verify(message, signature, ring_pubkeys):
        c0, s = signature
        c = [c0]
        
        # 验证哈希链
        for i in range(len(ring_pubkeys)):
            next_index = (i + 1) % len(ring_pubkeys)
            c.append(hash(c[i] + g(s[i], ring_pubkeys[i])))
        
        # 检查链的闭合性
        return c[0] == c[-1]
    '''")

def blind_signature_demo():
    """盲签名概念演示"""
    print("盲签名工作流程:")
    print("1. 盲化阶段: 用户将消息与盲因子结合，生成盲化消息")
    print("2. 签名阶段: 签名者对盲化消息进行签名")
    print("3. 去盲阶段: 用户使用盲因子将盲签名转换为原始消息的签名")
    print("4. 验证阶段: 任何人都可以使用签名者的公钥验证签名")
    
    print("\nRSA盲签名示例:")
    print("'''
    # 初始化 (签名者)
    n, e = public_key  # RSA公钥
    d = private_key   # RSA私钥
    
    # 盲化阶段 (用户)
    m = message       # 原始消息
    k = blind_factor  # 随机选择的盲因子，与n互质
    m_blind = (m * pow(k, e, n)) % n  # 盲化消息
    
    # 签名阶段 (签名者)
    s_blind = pow(m_blind, d, n)  # 盲签名
    
    # 去盲阶段 (用户)
    k_inv = pow(k, -1, n)  # 盲因子的模逆
    s = (s_blind * k_inv) % n  # 原始消息的签名
    
    # 验证阶段 (任何人)
    # 验证 m == pow(s, e, n)
    '''")
    
    print("\n盲签名的安全性考虑:")
    print("1. 盲因子必须足够随机且与模数互质")
    print("2. 签名者可能受到多重签名攻击，需要限制签名次数")
    print("3. 应用中需要防止签名的滥用，如电子现金中的双重支付问题")

def homomorphic_signature_concept():
    """同态签名概念演示"""
    print("同态签名原理:")
    print("1. 签名者对数据进行签名，生成初始签名")
    print("2. 数据处理者在不知道私钥的情况下，基于初始签名生成处理后数据的签名")
    print("3. 验证者可以验证处理后数据的签名，确认计算结果的正确性")
    
    print("\n加法同态签名示例:")
    print("假设我们有签名函数Sign和验证函数Verify")
    print("如果: Verify(m₁, Sign(m₁)) = 有效")
    print("且: Verify(m₂, Sign(m₂)) = 有效")
    print("那么存在组合函数⊕，使得:")
    print("Verify(m₁ + m₂, Sign(m₁) ⊕ Sign(m₂)) = 有效")
    
    print("\n同态签名的挑战:")
    print("1. 安全性与功能性的平衡")
    print("2. 签名大小可能随计算复杂度增长")
    print("3. 计算效率问题")
    print("4. 实现的复杂性")
    
    print("\n代表性方案:")
    print("- Gennaro等人的线性同态签名")
    print("- Boneh等人的基于双线性映射的同态签名")
    print("- 基于格的同态签名方案")

数字签名学习路径建议:
基础密码学 → 传统签名算法(RSA/DSA) → 椭圆曲线签名(ECDSA) → 高级签名技术 → 应用实践 → 安全研究