Page 299 - 《软件学报》2025年第5期

刘振亚 等: SM2 数字签名算法的两方门限计算方案框架 2199

(
[
−1
−1
,
2γ +1]) , 其中 w γ +1 = d (s 1 −rd 2 ) w γ+l = d s l l ∈ 2,γ +1 ]) , 得到该方程组的 (q−1) 组解. Alice 从这 (q−1) 组解中
2 2
获取 d 2 w γ+1 ,...,w 2γ+1 的难度等同于穷举. 对于 Alice 而言, 相较于仅掌握签名验证公钥以及签名结果, 掌握上述
,
信息并没有降低获取 Bob 的部分私钥 d 2 以及随机数 w γ+1 ,...,w 2γ+1 的难度. 假设 Alice 与 Bob 进行多次协作签名,
每次签名 Alice 都能够获得一个由 γ +1 个方程组成的方程组, 记第 次签名 Alice 获取的方程组为:
i

 [i] [i]
[i]
d
 s −r d 2 −w γ + 1 2 = 0
 1




 s −d 2 w = 0 ,
 [i] [i]
 2 γ+2

 .

 .
 .
该方程组包含 γ +2 个未知数, 分别为 d 2 和 w [i] ,...,w [i] . 每次签名 Bob 都会使用相同的部分私钥 d 2 , 并独立随机
2γ+1
γ+1
生成或计算 (γ +1) 个随机数 w [i] ,...,w [i] . 因此 Alice 通过与 Bob 的 n 次协作签名, 能够获取一个由 n(γ +1) 个方程
γ+1 2γ+1
[ ] [i]
组成的方程组, 其中包含 n(γ +1)+1 个未知数. Alice 令 d 2 在 1,q−1 区间上遍历取值, 并计算与之对应的 w ( j ∈ [γ +1,
j
( ) ( [ ])
−1 [i]
[i]
[i]
2γ +1]) , 其中 w [i] = d −1 s −r d 2 , w [i] = d s l ∈ 2,γ +1 , 得到该方程组的 (q−1) 组解. Alice 从这 (q−1) 组解
γ+1 2 1 γ+l 2 l
中获取 d 2 w [i] ,...,w [i] 的难度等同于穷举. 对于 Alice 而言, 相较于仅掌握签名验证公钥以及签名结果, 掌握上
,
γ+1 2γ+1
述信息并没有降低获取 Bob 的部分私钥 d 2 以及随机数 w [i] ,...,w [i] 的难度. 进一步, 根据签名随机数构造的安全
γ+1 2γ+1
w [i] ,...,w [i] 都至少包含 1 个独立随机生成的随机数, 因此在具体的两方门限计算方案中, Alice 也无法求
要求, γ+1 2γ+1
解所得的方程组. 综上, Alice 无法从协作签名的交互过程中获取任何 Bob 的私密信息, 从而无法获取完整的签名
私钥或另一部分私钥的任何信息.
在一次协作签名中, Bob 能够获取如下信息.
(1) 椭圆曲线点 Q 1 = [w 1 ]G,...,Q γ = [w γ ]G .
(2) 待签名消息的摘要 e .
(3) 签名第 2 部分 s = (d 1 (s 1 +w 1 s 2 +...+w γ s γ+1 )−r) mod q .
由于 ECDLP 和哈希函数的安全性, Bob 无法从 Q 1 和 中获取任何信息. 而 包含 Alice 的私密信息 d 1 和
s
e
s 1 ,..., s γ+1 对于 Bob 来说是已知的, 因此 Bob s− s 1 d 1 −...− s γ+1 w γ d 1 +r = 0 . 该方程
w 1 ,w 2 ,...,w γ , 且 试图求解方程
]
−1 −1
包含 (γ +1) 个未知数. Bob 令 d 1 ,w 1 ,...,w γ−1 分别在 [ 1,q−1 区间上遍历取值, 并计算与之对应的 w γ = d s
1 γ+1
( ) [ ] γ γ
s− s 1 d 1 −...− s γ w γ−1 d 1 +r , 得到该方程在 1,q−1 上的 (q−1) 组解. Bob 从这 (q−1) 组解中获取 d 1 和 w 1 ,w 2 ,...,
w γ 的难度远大于穷举. 对于 Bob 而言, 相较于仅掌握签名验证公钥以及签名结果, 掌握上述信息并没有降低获取
Alice 的部分私钥 d 1 以及随机数 w 1 ,w 2 ,...,w γ 的难度. 假设 Bob 与 Alice 进行多次协作签名, 每次签名 Bob 都能够
获取 1 个方程, 记第 i 次签名 Bob 获取的方程组为 s − s d 1 −...− s [i] w d 1 +r = 0 . 其中包含 (γ +1) 个未知数, 分
[i]
[i]
[i]
[i]
1 γ+1 γ
[i]
[i]
别为 d 1 和 w ,...,w [i] . 每次签名 Alice 都会使用相同的部分私钥 d 1 , 并独立随机生成或计算 γ 个随机数 w ,...,w [i] .
1 γ 1 γ
因此 Bob 通过与 Alice 的 n 次协作签名, 能够获取一个由 n 个方程组成的方程组, 其中包含 (nγ +1) 个未知数. Bob
]
−1 [i]−1
[i]
[i]
[i]
γ−1 1 +r ) ,
[i]
令 d 1 ,w ,...,w [i] 分别在 [ 1,q−1 区间上遍历取值, 并计算与之对应的 w = d s γ+1 (s − s [i]d 1 −...− s w [i] d [i]
γ
1
γ
γ−1
1
1
[ ] n(γ−1)+1 n(γ−1)+1 [i] [i] [i]
得到该方程组在 1,q−1 区间上的 (q−1) 组解. Bob 从这 (q−1) 组解中获取 d 1 和 w ,w ,...,w 的难度
1 2 γ
远大于穷举. 对于 Bob 而言, 相较于仅掌握签名验证公钥以及签名结果, 掌握上述信息并没有降低获取 Alice 的部
[i]
[i]
[i]
分私钥 d 1 以及随机数 w ,w ,...,w [i] 的难度. 进一步, 根据签名随机数构造的安全要求, w ,...,w [i] 总是包含至少
1 2 γ 1 γ
1 个独立随机生成的随机数, 因此在具体的两方门限计算方案中, Bob 也无法求解所得的方程组. 综上, Bob 无法从
协作签名的交互过程中获取任何 Alice 的私密信息, 从而无法获取完整的签名私钥或另一部分私钥的任何信息.
假设存在一个外部敌手 Adv 能够获取公开信息以及签名生成过程的通信信息, 包括:
(1) 椭圆曲线点 Q 1 = [w 1 ]G,...,Q γ = [w γ ]G .
(2) 待签名消息的摘要 e .
(3) 签名第 1 部分 r = (x 1 +e) mod q .
(4) 签名第 2 部分 s 的中间值 s 1 = d 2 (r +w γ+1 ) mod q s 2 = d 2 w γ+2 mod q,..., s γ +1 = d 2 w 2γ +1 mod q .
,
(5) 签名第 2 部分 s = (d 1 (s 1 +w 1 s 2 +...+w γ s γ+1 )−r) mod q .