RSA 签名与验签
RSA 密钥对产生的数学基础
欧拉函数
欧拉函数（Euler's totient function），记作φ(n)，是数论中的一个重要函数。
它表示小于等于n且与n互质的正整数的个数。换句话说，欧拉函数给出了在1到n之间与n互质的整数的个数。
- 如果n是一个质数，那么φ(n) = n - 1。这是因为质数与小于它的所有正整数都互质。
- 如果p和q是两个互质的正整数，那么φ(pq) = φ(p) * φ(q)。这个性质可以通过计算p和q之间的相对素数的个数来证明。
- 如果n = p^k，其中p是质数，k是正整数，那么φ(n) = p^k - p^(k-1)。这是因为在1到p^k之间，只有p的倍数与p^k不互质。
欧拉定理（Euler's theorem）：对于任何整数n和与n互质的整数a，有a^φ(n) ≡ 1 (mod n)。
费马小定理（Fermat's Little Theorem）是欧拉定理的一个特例。当n是质数时，欧拉定理变为费马小定理：对于任何整数a，有a^(n-1) ≡ 1 (mod n)。
生成 RSA 密钥对
RSA签名的数学原理：
- 首先，选择两个大质数p和q，计算它们的乘积n = pq。n的位数就是RSA密钥的位数(如 2048、4096 等等)，但是 n 的值有很多可能。
- 计算欧拉函数φ(n) = (p-1)(q-1)。
- 选择一个整数e，使得1 < e < φ(n)且e与φ(n)互质。通常选择65537作为e的值。
- 计算e的模φ(n)的乘法逆元d，即ed ≡ 1 (mod φ(n))。
- 公钥为(n, e)，私钥为(n, d)。
RSA 签名的数学基础
要对消息M进行签名，首先需要对消息生成一个哈希值H(M)，然后使用私钥(n, d)对哈希值进行签名。
签名过程如下：
计算签名S = H(M)^d mod n。
要验证签名，需要使用公钥(n, e)对签名进行验证。
验证过程如下：
- 计算哈希值H(M)。
- 使用公钥计算签名的哈希值：H'(S) = S^e mod n。
- 比较H(M)和H'(S)是否相等。如果相等，则签名有效；否则，签名无效。 RSA签名的安全性依赖于大数分解问题的难度。目前，没有已知的有效算法可以在合理的时间内分解大的合数。 因此，RSA签名被认为是安全的，只要选择足够大的密钥长度（例如2048位或更大）。
签名与验签的数学逻辑推理：
给定S = H(M)^d mod n，我们可以计算S^e mod n来验证签名。计算步骤如下：
- 首先，我们已知
S = H(M)^d mod n。 - 然后，我们计算
S^e mod n。根据S的定义，我们可以将S替换为H(M)^d：S^e mod n = (H(M)^d)^e mod n - 根据幂的乘法定律，我们可以将指数相乘：
S^e mod n = H(M)^(d * e) mod n - 将d e替换为其定义（即ed ≡ 1 (mod φ(n)），我们可以得到：
S^e mod n = H(M)^(1 k φ(n)) mod n，其中k为某个整数。 - 根据欧拉定理，对于任何与n互质的整数a，都有a^φ(n) ≡ 1 (mod n)。因此，我们可以将H(M)的幂次φ(n)替换为1：
S^e mod n = H(M) * (H(M)^φ(n))^k mod n = H(M) * 1^k mod n = H(M) mod n所以，计算S^e mod n的结果就是H(M)。这正是我们在验证签名时所期望的结果：如果S^e mod n等于原始消息的哈希值H(M)，那么签名就是有效的。
RSA 常见的两种签名实现
对原始消息签名和验签
代码语言：txt复制def sign_raw_message(pri_key: RSAPrivateKey, data: bytes, hash_alg: HashAlgorithm) -> bytes:
"""
Args:
pri_key: 私钥
data: 原始明文消息
hash_alg: 哈希算法
Returns: 签名数据
如果消息较大，签名和验签的过程会非常耗时。
"""
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
)
except BaseException as e:
print(e)
return False
else:
return True对消息摘要进行签名和验签
代码语言：txt复制def sign_msg_hash(pri_key: RSAPrivateKey, hash_value: bytes, hash_alg: HashAlgorithm) -> bytes:
"""
Args:
pri_key: 私钥
hash_value: 原始消息的 hash 值
hash_alg: 哈希算法
Returns: 签名值
由于哈希值的长度通常较短，签名和验签的过程相对较快。
"""
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)
)
except BaseException as e:
print(e)
return False
else:
return True使用单测进行验证
代码语言：txt复制import random
import unittest
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes
import rsa_base
import rsa_sign
class RsaSignTestCase(unittest.TestCase):
@classmethod
def setUpClass(cls) -> None:
cls.pub_key, cls.pri_key = rsa_base.generate_rsa_keypair()
cls.hash_alg = hashes.SHA256()
def test_raw_message(self):
message = bytes([random.randint(1, 255) for _ in range(32)])
sign = rsa_sign.sign_raw_message(pri_key = self.pri_key, data = message, hash_alg = self.hash_alg)
success = rsa_sign.verify_raw_message(pub_key = self.pub_key,
message = message,
signature = sign,
hash_alg = self.hash_alg)
self.assertEqual(success, True)
success = rsa_sign.verify_raw_message(pub_key = self.pub_key,
message = bytes([0x00]),
signature = sign,
hash_alg = self.hash_alg)
self.assertEqual(success, False)
def test_msg_hash(self):
message = bytes([random.randint(1, 255) for _ in range(32)])
chosen_hash = hashes.SHA256()
harsher = hashes.Hash(chosen_hash, default_backend())
harsher.update(message)
digest = harsher.finalize()
sign = rsa_sign.sign_msg_hash(pri_key = self.pri_key,
hash_value = digest,
hash_alg = hashes.SHA256())
success = rsa_sign.verify_msg_hash(pub_key = self.pub_key,
hash_value = digest,
signature = sign,
hash_alg = self.hash_alg)
self.assertEqual(success, True)
if __name__ == '__main__':
unittest.main()RSA 盲签名
盲签名的步骤
在RSA盲签名中，签名者对与原始消息M相关的“盲化”版本进行签名，而不是直接对原始消息M进行签名，这使得签名者无法识别所签名的消息的内容。
以下是对消息M进行RSA盲签名的步骤：
代码语言：txt复制1. 发送者对消息M计算哈希值H(M)。
2. 发送者选择一个随机的盲因子r，使得1 < r < n且r与n互质。
3. 发送者使用签名者的公钥(n, e)对盲因子r进行加密：r' = r^e mod n。
4. 发送者计算盲化的哈希值H'(M) = H(M) * r' mod n。
5. 发送者将盲化的哈希值H'(M)发送给签名者。签名者不知道原始消息M，只能看到盲化的哈希值。
6. 签名者使用私钥(n, d)对盲化的哈希值H'(M)进行签名：S' = H'(M)^d mod n。
7. 签名者将盲签名S'返回给发送者。
8. 发送者计算原始签名S：S = S' * r^(-1) mod n，其中r^(-1)是r关于n的模逆元。
9. 验证签名：计算 S^e (mod n) 并检查结果是否等于原始哈希值H(M)。如果相等，则签名验证成功。为什么不选择对原始消息进行盲签名
直接对原始消息进行盲签名可能会带来以下问题：
- 效率问题：当原始消息较大时，进行加密、解密和签名操作的计算成本会很高。这可能导致性能瓶颈，特别是在需要处理大量消息的场景中。
- 消息长度限制：在RSA加密和签名中，明文的长度受到密钥长度的限制。对于超过密钥长度的消息，需要进行分段加密。这会增加签名和验证的复杂性。
- 安全性问题：当直接对原始消息进行盲签名时，攻击者可能利用已知明文攻击和所选明文攻击来获取关于签名方私钥的信息。将原始消息哈希化可以提高安全性，因为攻击者很难找到具有相同哈希值的不同消息。
- 完整性验证：直接对原始消息进行盲签名可能无法确保消息的完整性。在某些情况下，攻击者可能会修改原始消息，而不影响签名的有效性。通过对消息的哈希值进行签名，可以确保即使原始消息的微小更改也会导致签名验证失败，从而确保消息的完整性。
盲签名的示例代码
以下代码仅做示例使用，不可用于生产环境！！！
代码语言：txt复制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:
"""
Args:
n: RSA 密钥对中的参数 n
Returns: 满足 1 < r < n 且 r 与 n 互质的数 r
"""
now = time.time_ns()
count: int = 0
while True:
count = 1
r: int = int.from_bytes(os.urandom(512), byteorder = 'big') % n
if n > r > 1 and math.gcd(r, n) == 1:
end = time.time_ns()
time_cost = (end - now) / 1000
print('generated blind factor r {} time(s), time cost:{:.2f} micro-seconds'.format(count, time_cost))
return r
def blind_msg(message: bytes, public_key: RSAPublicKey, hash_alg: HashAlgorithm) -> tuple[int, bytes, bytes]:
"""
发送者使用公钥对消息进行盲化处理
Args:
message: 原始明文数据
public_key: 签名者的私钥
hash_alg: 哈希算法
Returns: [盲化因子 r, 原始消息真实的哈希值, 原始消息盲化后的哈希值]
"""
# 对原始消息计算哈希值
harsher = hashes.Hash(hash_alg, default_backend())
harsher.update(message)
real_hash_digest: bytes = harsher.finalize()
real_hash_value: int = int.from_bytes(real_hash_digest, byteorder = 'big')
# 选取盲签名因子 r 值
r: int = get_blind_factor(public_key.public_numbers().n)
# 使用公钥对 r 加密
r_cipher: int = pow(r, public_key.public_numbers().e, public_key.public_numbers().n)
# 计算盲化的哈希值
blind_hash_digest: int = real_hash_value * r_cipher % public_key.public_numbers().n
# 将哈希值作为盲化的消息返回
return r, real_hash_digest, blind_hash_digest.to_bytes(public_key.key_size, byteorder = 'big')
def blind_sign(blind_hash_digest: bytes, private_key: RSAPrivateKey) -> bytes:
"""
签名方直接对盲化的哈希值进行签名
Args:
blind_hash_digest: 盲化消息的哈希值
private_key: 签名者的私钥
Returns: 盲化签名值
"""
blind_hash_value: int = int.from_bytes(blind_hash_digest, byteorder = 'big')
blind_sign_value: int = pow(blind_hash_value, private_key.private_numbers().d, private_key.public_key().public_numbers().n)
return blind_sign_value.to_bytes(private_key.key_size, byteorder = 'big')
def get_real_hash_value(blind_sign_value: bytes, r: int, public_key: RSAPublicKey, hash_alg: HashAlgorithm) -> bytes:
"""
发送者通过对盲签名值进行计算得到真实的签名值
Args:
hash_alg: 原始消息的 hash 算法
public_key: 公钥
blind_sign_value: 盲签名的值
r: 发送者之前计算出来的 r
Returns: 真实的签名值
"""
blind_sign: int = int.from_bytes(blind_sign_value, 'big')
real_sign: int = blind_sign * pow(r, -1, public_key.public_numbers().n)
real_hash: int = pow(real_sign, public_key.public_numbers().e, public_key.public_numbers().n)
return real_hash.to_bytes(hash_alg.digest_size, byteorder = 'big')简单的调用示例：
代码语言：txt复制if __name__ == '__main__':
raw_msg: bytes = bytes([random.randint(0, 255) for x in range(128, 256)])
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)
# 签名者对盲化的消息进行盲签名
sign_value = blind_sign(blind_hash, private_key = pri_key)
# 发送者通过对盲签名值进行计算，获取消息的哈希值
calculated_hash = get_real_hash_value(sign_value, r, pub_key, hash_alg)
print('verify blind sign succeed:', raw_hash_value == calculated_hash)
运行效果
