RSA盲签名

RSA签名与验签

RSA密钥对产生的数学基础

欧拉函数

欧拉函数(Euler’s totient function)，记作φ(n)，是数论中的一个重要函数。它表示小于等于n且与n互质的正整数的个数。

欧拉函数的性质：

如果n是一个质数，那么φ(n) = n - 1
如果p和q是两个互质的正整数，那么φ(pq) = φ(p) * φ(q)
如果n = p^k，其中p是质数，k是正整数，那么φ(n) = p^k - p^(k-1)

欧拉定理： 对于任何整数n和与n互质的整数a，有a^φ(n) ≡ 1 (mod n)

费马小定理是欧拉定理的一个特例。当n是质数时，欧拉定理变为费马小定理：对于任何整数a，有a^(n-1) ≡ 1 (mod n)。

生成RSA密钥对

RSA签名的数学原理：

选择两个大质数p和q，计算它们的乘积n = pq
计算欧拉函数φ(n) = (p-1)(q-1)
选择一个整数e，使得1 < e < φ(n)且e与φ(n)互质（通常选择65537）
计算e的模φ(n)的乘法逆元d，即ed ≡ 1 (mod φ(n))
公钥为(n, e)，私钥为(n, d)

RSA签名的数学基础

签名过程：

计算签名S = H(M)^d mod n

验证过程：

计算哈希值H(M)
使用公钥计算签名的哈希值：H’(S) = S^e mod n
比较H(M)和H’(S)是否相等

数学逻辑推理：

1
2
3
4
5
6
S = H(M)^d mod n
S^e mod n = (H(M)^d)^e mod n = H(M)^(d*e) mod n
由于ed ≡ 1 (mod φ(n))，所以d*e = 1 + kφ(n)
S^e mod n = H(M)^(1 + kφ(n)) mod n = H(M) * (H(M)^φ(n))^k mod n
根据欧拉定理，H(M)^φ(n) ≡ 1 (mod n)
所以S^e mod n = H(M) mod n

RSA常见的两种签名实现

对原始消息签名和验签

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def sign_raw_message(pri_key: RSAPrivateKey, data: bytes, hash_alg: HashAlgorithm) -> bytes:
    """对原始消息进行签名"""
    return pri_key.sign(
        data=data,
        padding=padding.PSS(
            mgf=padding.MGF1(hash_alg),
            salt_length=padding.PSS.MAX_LENGTH
        ),
        algorithm=hash_alg
    )

def verify_raw_message(pub_key: RSAPublicKey, message: bytes, signature: bytes, 
                      hash_alg: HashAlgorithm) -> bool:
    """验证原始消息的签名"""
    try:
        pub_key.verify(
            signature=signature,
            data=message,
            padding=padding.PSS(
                mgf=padding.MGF1(hash_alg),
                salt_length=padding.PSS.MAX_LENGTH
            ),
            algorithm=hash_alg
        )
        return True
    except:
        return False

对消息摘要进行签名和验签

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def sign_msg_hash(pri_key: RSAPrivateKey, hash_value: bytes, 
                 hash_alg: HashAlgorithm) -> bytes:
    """对消息摘要进行签名"""
    return pri_key.sign(
        data=hash_value,
        padding=padding.PSS(
            mgf=padding.MGF1(hash_alg),
            salt_length=padding.PSS.MAX_LENGTH
        ),
        algorithm=utils.Prehashed(hash_alg)
    )

def verify_msg_hash(pub_key: RSAPublicKey, hash_value: bytes, signature: bytes, 
                   hash_alg: HashAlgorithm) -> bool:
    """验证消息摘要的签名"""
    try:
        pub_key.verify(
            signature=signature,
            data=hash_value,
            padding=padding.PSS(
                mgf=padding.MGF1(hash_alg),
                salt_length=padding.PSS.MAX_LENGTH
            ),
            algorithm=utils.Prehashed(hash_alg)
        )
        return True
    except:
        return False

单元测试验证

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import random
import unittest
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

class RsaSignTestCase(unittest.TestCase):
    @classmethod
    def setUpClass(cls):
        cls.pub_key, cls.pri_key = generate_rsa_keypair()
        cls.hash_alg = hashes.SHA256()

    def test_raw_message(self):
        message = bytes([random.randint(1, 255) for _ in range(32)])
        signature = sign_raw_message(self.pri_key, message, self.hash_alg)
        
        # 验证正确签名
        success = verify_raw_message(self.pub_key, message, signature, self.hash_alg)
        self.assertTrue(success)
        
        # 验证错误消息
        success = verify_raw_message(self.pub_key, b'\x00', signature, self.hash_alg)
        self.assertFalse(success)

    def test_msg_hash(self):
        message = bytes([random.randint(1, 255) for _ in range(32)])
        
        # 计算消息哈希
        hasher = hashes.Hash(self.hash_alg, default_backend())
        hasher.update(message)
        digest = hasher.finalize()
        
        # 对哈希签名并验证
        signature = sign_msg_hash(self.pri_key, digest, hashes.SHA256())
        success = verify_msg_hash(self.pub_key, digest, signature, self.hash_alg)
        self.assertTrue(success)

RSA盲签名

盲签名的步骤

在RSA盲签名中，签名者对与原始消息M相关的"盲化"版本进行签名，而不是直接对原始消息M进行签名，这使得签名者无法识别所签名的消息的内容。

盲签名步骤：

发送者对消息M计算哈希值H(M)
发送者选择一个随机的盲因子r，使得1 < r < n且r与n互质
发送者使用签名者的公钥(n, e)对盲因子r进行加密：r’ = r^e mod n
发送者计算盲化的哈希值：H’(M) = H(M) * r’ mod n
发送者将盲化的哈希值H’(M)发送给签名者
签名者使用私钥(n, d)对盲化的哈希值进行签名：S’ = H’(M)^d mod n
签名者将盲签名S’返回给发送者
发送者计算原始签名：S = S’ * r^(-1) mod n
验证签名：计算S^e mod n并检查是否等于H(M)

为什么不选择对原始消息进行盲签名

直接对原始消息进行盲签名可能带来以下问题：

效率问题：当原始消息较大时，计算成本很高
消息长度限制：RSA加密和签名有长度限制
安全性问题：可能面临已知明文攻击和所选明文攻击
完整性验证：可能无法确保消息的完整性

盲签名的示例代码

注意：以下代码仅做示例使用，不可用于生产环境！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import math
import os
import random
import time
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives.asymmetric.rsa import RSAPrivateKey, RSAPublicKey
from cryptography.hazmat.primitives.hashes import HashAlgorithm

def get_blind_factor(n: int) -> int:
    """生成盲因子"""
    count = 0
    start_time = time.time_ns()
    
    while True:
        count += 1
        r = int.from_bytes(os.urandom(512), byteorder='big') % n
        
        # 检查条件：1 < r < n 且 r 与 n 互质
        if 1 < r < n and math.gcd(r, n) == 1:
            end_time = time.time_ns()
            time_cost = (end_time - start_time) / 1000
            print(f'生成盲因子尝试次数: {count}, 耗时: {time_cost:.2f} 微秒')
            return r

def blind_msg(message: bytes, public_key: RSAPublicKey, 
             hash_alg: HashAlgorithm) -> tuple:
    """对消息进行盲化处理"""
    # 计算原始消息的哈希值
    hasher = hashes.Hash(hash_alg, default_backend())
    hasher.update(message)
    real_hash_digest = hasher.finalize()
    real_hash_value = int.from_bytes(real_hash_digest, byteorder='big')
    
    # 获取公钥参数
    pub_numbers = public_key.public_numbers()
    n = pub_numbers.n
    e = pub_numbers.e
    
    # 生成盲因子
    r = get_blind_factor(n)
    
    # 使用公钥加密盲因子
    r_cipher = pow(r, e, n)
    
    # 计算盲化哈希值
    blind_hash_value = (real_hash_value * r_cipher) % n
    blind_hash_digest = blind_hash_value.to_bytes(
        public_key.key_size, byteorder='big'
    )
    
    return r, real_hash_digest, blind_hash_digest

def blind_sign(blind_hash_digest: bytes, private_key: RSAPrivateKey) -> bytes:
    """对盲化哈希值进行签名"""
    blind_hash_value = int.from_bytes(blind_hash_digest, byteorder='big')
    priv_numbers = private_key.private_numbers()
    n = private_key.public_key().public_numbers().n
    
    # 使用私钥签名
    blind_sign_value = pow(blind_hash_value, priv_numbers.d, n)
    return blind_sign_value.to_bytes(private_key.key_size, byteorder='big')

def get_real_signature(blind_signature: bytes, r: int, 
                      public_key: RSAPublicKey, hash_alg: HashAlgorithm) -> bytes:
    """从盲签名获取真实签名"""
    blind_sign_value = int.from_bytes(blind_signature, 'big')
    n = public_key.public_numbers().n
    
    # 计算r的模逆元
    r_inv = pow(r, -1, n)
    
    # 计算真实签名值
    real_sign_value = (blind_sign_value * r_inv) % n
    
    # 验证：计算真实签名对应的哈希值
    real_hash_value = pow(real_sign_value, public_key.public_numbers().e, n)
    return real_hash_value.to_bytes(hash_alg.digest_size, byteorder='big')

简单的调用示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
if __name__ == '__main__':
    # 生成测试数据
    raw_msg = bytes([random.randint(0, 255) for _ in range(128)])
    
    # 生成RSA密钥对
    pri_key = rsa.generate_private_key(
        public_exponent=65537,
        key_size=2048,
        backend=default_backend()
    )
    pub_key = pri_key.public_key()
    hash_alg = hashes.SHA256()
    
    # 发送者生成盲化消息
    r, raw_hash_value, blind_hash = blind_msg(raw_msg, pub_key, hash_alg)
    
    # 签名者对盲化消息进行签名
    blind_signature = blind_sign(blind_hash, pri_key)
    
    # 发送者计算真实签名对应的哈希值
    calculated_hash = get_real_signature(blind_signature, r, pub_key, hash_alg)
    
    print('盲签名验证结果:', raw_hash_value == calculated_hash)

运行效果

当运行上述代码时，会输出盲签名生成的过程和最终的验证结果。如果一切正常，验证结果应该为True，表明盲签名机制正常工作。

运行效果

盲签名技术在需要保护用户隐私的场景中非常有用，比如电子投票系统、数字货币等，它可以确保签名者无法获取被签名消息的具体内容，同时又能提供有效的数字签名。

RSA签名与验签#

RSA密钥对产生的数学基础#

欧拉函数#

生成RSA密钥对#

RSA签名的数学基础#

RSA常见的两种签名实现#

对原始消息签名和验签#

对消息摘要进行签名和验签#

单元测试验证#

RSA盲签名#

盲签名的步骤#

为什么不选择对原始消息进行盲签名#

盲签名的示例代码#

简单的调用示例#

运行效果#

RSA签名与验签

RSA密钥对产生的数学基础

欧拉函数

生成RSA密钥对

RSA签名的数学基础

RSA常见的两种签名实现

对原始消息签名和验签

对消息摘要进行签名和验签

单元测试验证

RSA盲签名

盲签名的步骤

为什么不选择对原始消息进行盲签名

盲签名的示例代码

简单的调用示例

运行效果