2. 基于RSA盲签名的隐私求交（PSI）协议实现
协议原理与角色分工
RSA盲签名PSI的核心思想是：接收方（Bob）将自己的集合元素通过盲化因子隐藏后发送给签名方（Alice），Alice用自己的RSA私钥对盲化值签名，Bob去盲后得到Alice对原始元素的签名。双方各自对交集元素计算哈希，Bob将哈希集合发给Alice，Alice比对后返回交集。整个过程中Alice无法得知Bob集合的具体元素，Bob也无法伪造Alice的签名。
协议涉及三个关键数学操作：盲化（Bob用随机因子r隐藏元素）、盲签名（Alice对盲化值做RSA私钥运算）、去盲（Bob用r的逆元还原签名）。安全性依赖于RSA假设和随机预言机模型。
关键实现步骤
下面给出完整的Python实现，使用cryptography库生成RSA密钥对，并手动实现盲化、签名、去盲和比对逻辑。为便于教学演示，集合元素使用小整数，实际应用中应对元素做哈希映射到模数空间。
import hashlib
import secrets
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes, serialization
# ========== 1. 密钥生成 ==========
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()
pub_numbers = public_key.public_numbers()
n, e = pub_numbers.n, pub_numbers.e
priv_numbers = private_key.private_numbers()
d = priv_numbers.d
# ========== 2. 工具函数 ==========
def H_int(x: int) -> int:
"""将整数映射到 [0, n-1] 的哈希值"""
h = hashlib.sha256(str(x).encode()).digest()
return int.from_bytes(h, 'big') % n
def H_bytes(b: bytes) -> bytes:
return hashlib.sha256(b).digest()
# ========== 3. Bob 盲化 ==========
def bob_blind(x: int):
"""返回 (盲化值 x', 盲化因子 r)"""
r = secrets.randbelow(n - 2) + 2 # r ∈ [2, n-1]
while True:
try:
r_inv = pow(r, -1, n)
break
except ValueError:
r = secrets.randbelow(n - 2) + 2
x_hash = H_int(x)
x_blind = (x_hash * pow(r, e, n)) % n
return x_blind, r, r_inv
# ========== 4. Alice 盲签名 ==========
def alice_sign(x_blind: int) -> int:
"""对盲化值做 RSA 私钥运算"""
return pow(x_blind, d, n)
# ========== 5. Bob 去盲 ==========
def bob_unblind(s_blind: int, r_inv: int) -> int:
"""去盲得到原始签名"""
return (s_blind * r_inv) % n
# ========== 6. 完整协议流程 ==========
def rsa_blind_psi(set_a: set, set_b: set):
"""
RSA盲签名PSI协议
返回: 交集集合
"""
# Bob 对每个元素盲化
blind_data = {}
for x in set_b:
x_blind, r, r_inv = bob_blind(x)
blind_data[x] = (x_blind, r_inv)
# Alice 对盲化值签名
signed_data = {}
for x, (x_blind, r_inv) in blind_data.items():
s_blind = alice_sign(x_blind)
signed_data[x] = (s_blind, r_inv)
# Bob 去盲并计算哈希
bob_hashes = {}
for x, (s_blind, r_inv) in signed_data.items():
s = bob_unblind(s_blind, r_inv)
h = H_bytes(s.to_bytes((s.bit_length() + 7) // 8, 'big'))
bob_hashes[h] = x
# Alice 对自身集合元素计算签名哈希
alice_hashes = {}
for y in set_a:
y_hash = H_int(y)
s = pow(y_hash, d, n)
h = H_bytes(s.to_bytes((s.bit_length() + 7) // 8, 'big'))
alice_hashes[h] = y
# 求交集
common_hashes = set(bob_hashes.keys()) & set(alice_hashes.keys())
intersection = {bob_hashes[h] for h in common_hashes}
return intersection
# ========== 7. 测试验证 ==========
if __name__ == "__main__":
S_A = {101, 202, 303, 404, 505}
S_B = {202, 404, 606, 707, 808}
result = rsa_blind_psi(S_A, S_B)
expected = S_A & S_B
print(f"Alice 集合: {S_A}")
print(f"Bob 集合: {S_B}")
print(f"协议输出交集: {result}")
print(f"预期交集: {expected}")
print(f"验证结果: {'✓ 通过' if result == expected else '✗ 失败'}")
正确性验证与结果判读
运行上述代码，预期输出如下（交集为 {202, 404}）：
Alice 集合: {101, 202, 303, 404, 505}
Bob 集合: {202, 404, 606, 707, 808}
协议输出交集: {202, 404}
预期交集: {202, 404}
验证结果: ✓ 通过
验证要点：协议正确性依赖三个条件同时成立——(1) 盲化因子 r 与 n 互素，保证 r 的逆元存在；(2) 去盲运算
s = s' · r⁻¹ mod n 能还原出 H(x)^d mod n；(3) 双方对签名值使用相同的哈希函数。若交集为空，说明哈希比对未命中，需检查元素编码方式是否一致。
安全性分析与参数选择
| 安全属性 | 实现机制 | 参数建议 |
|---|---|---|
| Alice 无法获知 Bob 集合 | Bob 发送的是盲化值 x' = H(x)·r^e mod n，Alice 无法从 x' 反推 H(x) | r 必须使用密码学安全随机数，且每次盲化独立选取 |
| Bob 无法伪造签名 | RSA 签名依赖私钥 d，Bob 只有公钥 e，无法对任意值生成有效签名 | 密钥长度 ≥ 2048 位，e 取 65537 |
| 交集之外元素不泄露 | Bob 只发送哈希值，Alice 无法从哈希反推原始元素；Alice 只返回交集索引 | 哈希函数使用 SHA-256，输出截断至模数长度 |
| 抗重放/链接攻击 | 每次协议运行使用独立随机因子 r，相同元素在不同会话中盲化值不同 | r 不可复用，协议结束后立即销毁 |
注意事项：本实现为教学演示版本，直接对整数做 RSA 运算。生产环境中需注意：(1) 元素应先通过哈希映射到模数空间，避免小整数攻击；(2) 应使用 RSA-OAEP 或 PKCS#1 v1.5 填充方案；(3) 需加入零知识证明或承诺机制防止恶意参与方篡改中间值；(4) 通信层应使用 TLS 保护传输安全。
计算开销与优化方向
协议的主要计算开销集中在 RSA 模幂运算上。设 Bob 集合大小为 m，Alice 集合大小为 n，则：
- Bob 端：m 次模幂（盲化，指数为 e）+ m 次模乘（去盲）+ m 次哈希
- Alice 端：m 次模幂（签名，指数为 d）+ n 次模幂（自身集合签名）+ n 次哈希
- 通信量：Bob 发送 m 个模 n 整数，Alice 返回 m 个模 n 整数，Bob 再发送 m 个哈希值
优化方向包括：使用中国剩余定理（CRT）加速私钥运算、批量模幂、以及将哈希比对改为布隆过滤器或 cuckoo filter 以降低通信轮次。