一种基于多变量的可抗合谋攻击的代理重签名方法

摘要

一种基于多变量的可抗合谋攻击的代理重签名方法，由生成系统、密钥生成、生成重签名密钥、受托人A产生签名、代理人产生重签名、重签名正确性验证步骤组成。由于本发明采用可信第三方产生代理重签名中受托人A和委托人B使用的两个随机密钥和用这两个随机密钥和分别生成新的重签名密钥，代理人使用该重签名密钥将受托人A对某一消息的签名转换成委托人B对同一消息的签名，并且由于随机密钥的保密性，无论是委托人B与代理人合谋，还是代理人与受托人A合谋，均不能得到另一人的秘密钥，可有效地抵抗合谋攻击。它具有效率高、安全可靠、抵抗受托人A与代理人和代理人与委托人B的合谋攻击等优点，可用于代理重签名。

说明书

技术领域

本发明属于信息安全技术领域，涉及多变量公钥系统及消息的代理认证，特别涉及一种基于多变量的可抗合谋攻击的代理重签名方法。

背景技术

代理重签名是指一个半可信任的代理人(他拥有一个和受托人A与委托人B的信息相关的重签名密钥)负责将受托人A对某一消息的签名转化为委托人B对同一消息的签名，同时，要求代理人只有重签名密钥，无法获悉受托人A及委托人B的私钥，并且不能代表委托人B或者受托人A生成新的签名。

代理重签名的安全性分为内部安全性和外部安全性。外部安全性：非法第三方不能与签名参与方合谋。内部安全性：委托人B与代理人或代理人与受托人A无法合谋，即委托人B与代理人合谋或代理人与受托人A合谋都不能对此签名方案攻击泄露。内部安全和外部安全确保方案的安全。

一个代理重签名方案是由五个多项式时间算法(密钥生成，生成重签名密钥，签名，重签名，验证)构成，其中(密钥生成,签名,验证)是标准的签名产生和验证算法。“生成重签名密钥”是重签名密钥生成算法：输入受托人A和委托人B的公私钥对，产生一个重签名密钥。“重签名”是指：代理人使用重签名密钥可将受托人A的签名转换为委托人B的签名。“重签名”是通过重签名生成算法来执行：输入一个重签名密钥rk_A→B、一个消息、一个A的签名和一个用户A的公钥。该算法的正确性是指，输出一个对应于用户B的公钥的同一个消息的B的签名；否则，输出⊥。

传统的网络代理签名体制大致可分为三类：一类是基于RSA的代理签名体制；一类是基于离散对数的代理签名方案；最后一类是基于椭圆曲线的代理签名方案。然而这些方案的安全理论均是基于数论中的大整数分解和离散对数的 困难性。然而，美国科学家Peter Shor于1995年提出了一种量子分解算法，它通过利用量子计算的并行性，可以在多项式时间内快速分解出大数的质因子和离散对数问题，也就是说，量子计算机的产生，对现有基于传统密码体制的数字签名的安全性构成了严重的威胁。

多变量公钥体制是有限域上根据多变量非线性方程组的求解问题而设计的密码系统，其安全性基于求解一组多变量多项式方程是一NP-C问题，目前被认作是量子时代的一种安全的密码体制备选方案，04年提出的签名方案Flash入选了欧洲密码计划NRSSIE，成为密码研究中具有潜力的技术之一。

孙昌毅,李益发,斯雪明.基于多变量公钥密码体制的代理重签名方案[J].计算机工程,2012,38(17):116-118.首次基于多变量体制的Rainbow方案提出一种代理重签名方案，但遗憾的是正如文中3.3节所说该方案不能抗合谋攻击“…代理人与受托人合谋…委托人的私钥信息会泄露…”。因此，本发明以多变量公钥体制为基础，设计一种可抗合谋攻击的代理重签名方案，以为量子计算机时代提供一种安全代理签名的候选方案。

发明内容

本发明所要解决的技术问题在于克服上述现有技术的缺点，提供一种可有效地抵抗合谋攻击、效率高、安全可靠、适用于消息代理认证环境、为信息安全和信任体系的建立提供基础技术的基于多变量的可抗合谋攻击的代理重签名方法。

解决上述技术问题所采用的技术方案是由下述步骤组成：

(1)生成系统

(1.1)建立二次方程组为：

式中的a₁₁₁～a_nnn,b₁₁～b_nn,c₁～c_n均为有限域上的元素，n是有限的正整数，i,j为取自1～n的正整数，该二次方程组记为Q，根据(1)的构造，得相应Q^-1为：

式中的均取自同一个有限域。

(1.2)分别取有限域上的可逆仿射变换T、S和H，他们的一般形式如下，其中T为：

S为：

H为：

x₁～x_n,y₁～y_n,u₁～u_n,v₁～v_n,δ₁～δ_n,t₁₁～t_nn,s₁₁～s_nn,h₁₁～h_nn均为有限域上的元素，y₁～y_n,v₁～v_n均为自变量；T、S和H为秘密钥，H用于产生代理重密钥；T和S共同封装二次方程组Q即(1)式的结构，即将S、Q、T，依次进行代入计算，记为，表示从右向左依次代入，得到二次方程组为公钥，记为P：

式中的d₁₁₁～d_nnn,e₁₁～e_nn,f₁～f_n均为有限域上的元素，上述给出的公钥P和秘密钥S、秘密钥T具有关系：

(2)生成密钥

代理重签名时，可信第三方要首先产生随机密钥、受托人密钥、代理重签名密钥，并且为便于验证代理重签名的正确性，还需要产生委托人的密钥。

(2.1)产生随机密钥

随机密钥由两部分构成。可信第三方从有限域中随机选择两组不同的数 和分别代入H中即(5)式，分别得到：

该变换记为为随机密钥的一部分。

该变换记为为随机密钥的另一部分；随机密钥和均为随机产生，且一次有效，即仅在本次代理重签名中有效，下次代理重签名需重新生成。

通过线性反解，得出随机密钥的逆，记为为：

通过线性反解，得出随机密钥的逆，记为为：

(2.2)产生受托人A的密钥

受托人A的密钥包括秘密钥、随机秘密钥、公钥、随机公钥四部分。

1)产生受托人A的秘密钥

可信第三方从有限域中随机选择两组数为t_AB11,…,t_ABnn,t′_AB1,…,t′_ABn和s_A11,…,s_Ann,s′_A1,…,s′_An，将t_AB11,…,t_ABnn,t′_AB1,…,t′_ABn代入T即(3)式中，得到：

该变换不仅为受托人A的一部分秘密钥，也是委托人B的一部分秘密钥，所以不再分别记为T_A，T_B，而是统一记为T，T发送给受托人A，成为受托人A秘密钥的一部分。

将s′_A1,…,s′_An代入S即(4)式中，得到受托人A秘密钥的另一部分：

该变换记为S_A，受托人A的秘密钥由T和S_A两部分构成，始终不变，并由A秘密保存。

利用线性反解得出T的逆，记为T^-1，为：

2)产生受托人A的随机秘密钥

可信第三方对受托人A的秘密钥S_A即(11)式，通过线性反解法得S_A的逆，记为为：

将代入到随机秘密钥即(6)式中，生成：

该变换记做发送给受托人A，成为受托人A的随机秘密钥，在代理重签名时，受托人A用随机秘密钥代替秘密钥进行签名。

3)产生受托人A的公钥

可信第三方将S_A即(11)式中代入到Q即(1)式中，得到的结果再代入到T即(10)式中，得到受托人A的公钥：

该变换记为P_A。

4)产生受托人A的随机公钥

可信第三方将即(8)式中代入到受托人A的公钥P_A即(15)式中，得到：

该变换记为为受托人A的随机公钥。

(2.3)产生委托人B的密钥

委托人B的密钥包括秘密钥、公钥、随机公钥三部分。

1)产生委托人B的秘密钥

委托人B的秘密钥由两部分构成，其中一部分为受托人A的秘密钥T，另一部分由可信第三方产生：可信第三方从有限域中随机选择一组数为 s′_B1,…,s′_Bn，将s′_B1,…,s′_Bn代入S即(4)式中，得到委托人B秘密钥的另一部分：

该变换记为S_B，委托人B的秘密钥由T和S_B两部分构成，并由B秘密保存。

对S_B经过线性反解得S_B的逆，记为为：

2)产生委托人B的公钥

可信第三方将S_B即(17)式代入到Q即(1)式中，得到的结果再代入到委托人B的秘密钥即(10)式T中，得到委托人B的公钥：

该变换记为P_B。

3)产生委托人B的随机公钥

可信第三方把即(9)式代入到P_B即(19)式中，得到：

该变换记为为委托人B的随机公钥。

(3)生成重签名密钥

可信第三方将即(8)式代入到受托人A的秘密钥S_A即(11)式中，将得到的结果再代入到委托人B的秘密钥即(18)式中，再将得到的结果再代入到委托人B的随机密钥即(7)式中，得到代理人进行重签名的重签名密钥>

该变换记为rk_A→B。

(4)受托人A产生签名

已知消息M，其编码记为(u₁,…,u_n)，受托人A将编码(u₁,…,u_n)代入到受托人A的秘密钥的逆T^-1即(12)式中，得到的结果记为(y_A1,…,y_An)，再将(y_A1,…,y_An)代入Q^-1即(2)式中，得到的结果记为(x_A1,…,x_An)，再将(x_A1,…,x_An)代入到即(14)式中，得到的结果为(δ_A1,…,δ_A1)，其中，经过即(13)式得到的结果记为(v_A1,…,v_An)，(δ_A1,…,δ_A1)为受托人A对消息(u₁,…,u_n)的签名。

(5)代理人产生重签名

代理人产生重签名需要两步：

(5.1)代理人收到受托人A对消息(u₁,…,u_n)的签名(δ_A1,…,δ_A1)，首先用受托人A的随机公钥即(16)式验证签名(δ_A1,…,δ_A1)的正确性：即将签名(δ_A1,…,δ_A1)代入到(16)式中，检验得到的结果是否为原消息(u₁,…,u_n)，若是，则(δ_A1,…,δ_A1)为正确签名；否则拒绝重签名。

(5.2)若(δ_A1,…,δ_A1)为受托人A对消息(u₁,…,u_n)的正确签名，则代理人将(δ_A1,…,δ_A1)代入到重签名密钥即(21)式中，得到(rk₁,…,rk_n)，即为代理重签名，代理重签名(rk₁,…,rk_n)和受托者A签名(δ_A1,…,δ_A1)具有关系(rk₁,…,rk_n)＝rk_A→B(δ_A1,…,δ_A1)。

(6)重签名正确性验证

将重签名(rk₁,…,rk_n)代入到委托人B的随机公钥即(20)式中，检验其结果是否为原消息(u₁,…,u_n)，即是否等于(u₁,…,u_n)，若相等，则说明该重签名(rk₁,…,rk_n)为正确签名，否则重签名无效。

在本发明的生成密钥步骤(2)中,本发明的受托人随机密钥的逆和委托人B的随机密钥均为随机产生，仅一次有效。

在本发明的生成密钥步骤(2)中，本发明的随机密钥和随机密钥由可信第三方产生，受托者和委托者均无法预测，并由可信第三方秘密保存，且仅一次有效。

在本发明的生成密钥步骤(2)中，本发明的随机密钥和随机密钥为一次、可逆、仿射变换。

在本发明的密钥生成步骤(2)中，本发明的受托人A的秘密钥T与委托人B的秘密钥T相同。

由于本发明采用可信第三方产生代理重签名中受托人和委托人使用的两个随机密钥和用这两个随机密钥和分别生成新的重签名密钥，代理人使用该重签名密钥将受托人对某一消息的签名转换成委托人对同一消息的签名，并且由于随机密钥的保密性，无论是委托人与代理人合谋，还是代理人与受托人合谋，均不能得到另一人的秘密钥，可有效地抵抗合谋攻击。代理重签名中所使用的重签名密钥是由受托人和委托人的随机密钥和共同构成，该随机密钥均由可信第三方随机产生，仅一次有效，受托人和委托人均无法预测，并由可信第三方秘密保存，仅一次有效。所使用的两个随机密钥和互不相同，均为一次仿射变换。

本发明与现有技术相比，可抵抗常规的量子攻击，具有效率高、安全可靠、抵抗受托人与代理人和代理人与委托人的合谋攻击等优点，可用于代理重签名。

附图说明

图1是代理重签名原理示意图

图2是本发明实施过程图。

具体实施方式

下面结合附图和实施例对本发明进一步详细说明，但本发明不限于这些实施例。

实施例1

以二次方程组中n＝2，即自变量和方程个数均为2个为例，基于多变量的可抗合谋攻击的代理重签名方法步骤如下：

(1)生成系统

选择系统参数：取一个有限域F₅,即该域元素为{0,1,2,3,4}，运算为模5加和模5乘，一个元素o的逆元是指满足与o相乘再模5为1的元素，记为o^-1，即在F₅上有：-5＝0mod>-1＝1,2^-1＝3,3^-1＝2,4^-1＝4；取n＝2，即自变量和方程个数均为2个；取a₁₁₁＝0,a₁₁₂＝1,a₁₂₂＝0,b₁₁＝0,b₁₂＝0,c₁＝0；a₂₁₁＝0,a₂₁₂＝0,a₂₂₂＝0,b₂₁＝1,b₂₂＝0,c₂＝0，则二次方程组Q为：

相应的Q的逆Q^-1为

(2)生成密钥

(2.1)产生随机密钥

可信第三方从有限域中随机选择两组数代入(5)式，得到为：

为：

为随机产生，一次有效，即仅在本次代理重签名中有效，下次代理重签名需重新生成；

对式(2-6)和式(2-7)分别用线性反解法求逆得

为：

(2.2)产生受托人A的密钥

受托人A的密钥包括秘密钥、随机秘密钥、公钥、随机公钥四部分；

1)产生受托人A的秘密钥

可信第三方从有限域中随机选择一组数t_AB11＝1,t_AB12＝0,t′_AB1＝2；t_AB21＝0,t_AB22＝2,t′_AB2＝0,代入到(3)式，得到受托人A的秘密钥T(因为取T_B＝T_A，均记为T)为：

再随机选择一组数s_A11＝2,s_A12＝0,s′_A1＝0；s_A21＝0,s_A22＝1,s′_A2＝0，代入(4)式，得到受托人A的秘密钥S_A为：

对T即(2-10)式线性反解得T^-1为：

T和S_A构成受托人A的秘密钥，由A秘密保存；

2)产生受托人A的随机秘密钥

可信第三方对S_A即(2-11)式线性反解得为：

将代入到即(2-6)式中，得到受托人A的随机秘密钥记为(δ_A1,δ_A2)

受托人A用随机秘密钥对消息进行签名；

3)产生受托人A的公钥

可信第三方将S_A代入到Q即(2-1)式中，得到的结果再代入到T即(2-10)式中，得到的受托人A的公钥P_A，即

4)产生受托人A的随机公钥

将代入到受托人A的公钥P_A即(2-15)式中，即将v₁,v₂分别作为x₁,x₂代入到受托人A的公钥P_A中得到为：

(2.3)产生委托人B的密钥

委托人B的密钥包括秘密钥、公钥、随机公钥三部分；

1)产生委托人B的秘密钥

由前述知，委托人B的秘密钥的一部分也为T，为(2-10)式：

可信第三方从有限域中随机选择一组数s_B11＝0,s_B12＝1,s′_B1＝0；s_B21＝1,s_B22＝0,s′_B2＝1,，代入(4)式，得到委托人B的秘密钥S_B为：

对S_B即(2-17)式线性反解得为：

T和S_B构成委托人B的秘密钥，由B秘密保存；

2)产生委托人B的公钥

可信第三方将S_B即(2-17)式代入到Q即(2-1)式中，得到的结果再代入到T即(2-10)式中，得到的委托人B的公钥P_B，即

3)产生委托人B的随机公钥

将即(2-9)式代入到委托人B的公钥P_B即(2-19)式中，即将v₁,v₂代入P_B中得到为：

(3)生成重签名密钥

可信第三方将秘密钥即(2-8)式代入到受托人A的秘密钥S_A即(2-11)式中，得到的结果再代入到委托人B密钥即(2-18)式中，再将得到的结果再代入到秘密钥即(2-7)式中，得到代理人进行重签名的重签名密钥rk_A→B为：

(4)受托人A产生签名

取消息M，其编码记为(u₁,u₂)＝(0,1)，将得到的结果代入到T^-1即(2-12)式中，得(y1,y2)＝(3,3)，将(y1,y2)＝(3,3)再代入到Q^-1即(2-2)式中结果为(x₁,x₂)＝(0,2)，再将(x₁,x₂)＝(0,2)代入到即(2-14)式中，得到的结果为(δ_A1,δ_A2)＝(1,1)，即为受托人A对消息(0,1)的签名；

(5)代理人产生重签名

代理人产生重签名需要两步：

(5.1)代理人对收到受托人A对消息(0,1)的签名(δ_A1,δ_A2)＝(1,1)，首先用>A1,δ_A2)＝(1,1)代入到A的随机公钥即(2-16)式中，得结果为(0,1)，与原始消息相等，即受托人A对消息(0,1)的签名为正确；

(5.2)因为(δ_A1,δ_A2)＝(1,1)为受托人A对消息(0,1)的正确签名，则代理人将(δ_A1,δ_A2)＝(1,1)代入到重签名密钥rk_A→B即(2-21)式中，得到结果为(rk₁,rk₂)＝(1,1)，即为代理人对受托人A签名的重签名；

(6)重签名正确性验证

将重签名(rk₁,rk₂)＝(1,1)代入到委托人B的随机公钥即(2-20)式中，得到(0,1)，与原始消息相等，则该重签名(rk₁,rk₂)＝(1,1)为正确签名；

上述的为可信第三方随机产生，系数均取自有限域，具有可逆性，且仅一次有效，即仅在本次代理重签名中有效，下次代理重签名需重新生成。

本发明可以抵抗合谋攻击：

(1)受托人A通过随机秘密钥和秘密钥T对消息(u₁,…,u_n)进行签名，签名可表示为

(2)代理人通过重签名密钥将受托人A的签名(δ_A1,…,δ_A1)转换为委托人B的签名时，签名为：(rk₁,…,rk_n)＝rk_A→B(δ_A1,…,δ_A1)。

(3)若委托人B直接对该消息(u₁,…,u_n)进行签名，则为：>B1,…,δ_B1)。由于：

即对同一个消息，代理人产生的签名(rk₁,…,rk_n)和委托人B产生的签名(δ_B1,…,δ_B1)相同，因此，重签名正确且有效。

本发明的安全性分析：

代理重签名的安全性包括外部安全性和内部安全性。

(1)外部安全性分析

当存在外部非法第三方时，非法第三方无法与签名参与方进行合谋。这是因为，非法第三方在没有代理重签名密钥的情况下，若想伪造重签名，则只能根据委托人B的随机公钥进行签名伪造，即需要计算需要利用委托人B的随机公钥求逆，求解委托人B的随机公钥即为有限域上求解非线性方程组解的问题，该问题为多变量公钥体制的安全基础，无法求解出，非法第三方无法与参与者合谋获取有效签名，外部攻击无效，本发明满足外部安全性。

(2)内部安全性分析

(2.1)仅有重签名密钥代理人无法自行代表委托人B或者受托人A进行消息签名。

(2.2)当委托人B可信，受托人A不可信，代理人与受托人A合谋。受托人A和代理人有重签名密钥和A的秘密钥S_A、随机秘密钥由于秘密钥是可信第三方随机产生，并且与不相同，均为第三方秘密保存，在本次代理重签名中受托人A无法获得的信息，从重签名密钥rk_A→B和受托人A的秘密钥S_A、随机秘密钥中无法获得无法获得委托人B的秘密钥信息S_B，委托人B的秘密钥S_B仍为安全，方案可靠。

(2.3)当委托人B不可信，受托人A可信，委托人B和代理人合谋时，委托人B和代理人只有重签名密钥和委托人B的秘密钥S_B、随机密钥由于秘密钥是可信第三方随机产生，并且与不相同，均为第三方秘密保存，即在本次代理重签名中委托人B无法获得的信息，从重签名密钥rk_A→B和B的秘密钥S_B、随机密钥中无法获得无法>A，受托人A的秘密钥S_A仍为安全，方案可靠。

(3)随机密钥和安全性分析

随机密钥和是由可信第三方秘密、随机产生，分配给受托人A和委托者B，由于随机密钥和仅一次有效，在下一次代理重签名时需要第三方重新产生，在本次代理重签名完成后，随机密钥和即刻失效，可有效地防止受托人A和委托人B对随机密钥的重复使用，可有效地抵抗合谋攻击。

本发明所应用的理论基础如下：

(1)有限域

有限域是一个包含两个运算加和乘的有限个元素的集合，且满足对加法和乘法均具有结合律、交换律、非零元有逆元和乘法对加法的分配率等性质。域中元素的个数称为该域的阶数，q阶有限域，常记为或简记为有限域上的运算为模运算。

(2)多变量问题

多变量问题也简称为多变量二次-问题。由于多变量公钥密码体制的安全性是基于有限域上求解一组多变量非线性多项式方程：

p₁(x₁,…,x_n)＝p₂(x₁,…,x_n)＝…＝p_m(x₁,…,x_n)＝0，

求解该问题为一NP-C问题，其中p_i的系数和变量均取自有限域通常方程p_i取为二次，基于多变量问题构造的方案，前安全性基础来自于从公钥二次方程的直接破解的困难性，即已知公钥求解方程组为一个非多项式时间完全(NP-C)困难问题。

(3)变换

F是一个有限域，(y₁,…,y_n)＝f(x₁,…,x_n),x_i,y_i∈F称之为一个变换，是指存在变化规则使得(x₁,…,x_n)经过该变化规则变成为(y₁,…,y_n)，该变化规则记为f。