Guillou-Quisquater身份识别方案优化

Guillou-Quisquater身份识别方案由L.C.Guillou-Quisquater于1988年提出，它是一种基于RSA体制的安全识别方案，简称为G-Q识别方案。

1.选择参数

G-Q识别方案需要一个可信任的验证中心TA，且选择参数如下：

●p、q是两个大素数，且n=pq，保留p和q，公开n。

●b是一个长为40bit的素数作为公钥（也是安全参数）。

●h（x）是一个安全的Hash函数。

●选择签名生成算法Sig_ta和签名验证算法Ver_ta。

2.TA向示证者P颁发证书

1）TA为P建立身份信息，并颁发一个身份识别串ID_P。

2）P秘密地选择了一个整数x∈（1，n-1），且gcd（x，n）=1，P计算y≡（x^-1）^b（mod n），并将y发给TA，这里x为私有信息，y为公开信息。

3）TA计算签名S=Sig_ta（ID_P，y），将身份证书Cert_P=（ID_P，y，S）发送给P。

3.示证者P向验证者V证明自己的身份

1）P随机选择一个整数r∈[1，n-1]，并计算β≡r^b（mod n）(www.xing528.com)

2）P发送自己的身份证书Cert_P和β给V。

3）V通过检查证书Cert_P来验证TA的签名。

4）V随机地选择一个整数e∈[1，b]作为询问值发送给P。

5）P计算w≡rx^e（mod n），并把w作为对V的应答值发送给V。

6）V验证y^ew^b（mod n），判断其是否等于β，若相等，则V相信对方就是P。

实际上，若双方都诚实，则

4.安全性分析

掌握秘密随机数x的示证者P，对于验证者V的任何询问e他都能计算出w≡rx^e（mod n），把w作为对V的应答并通过V的验证，所以该协议是完全的。

在步骤4）中，假设攻击者能猜中V的询问值e，在步骤1）中先选取w并计算y^ew^b（mod n）≡β。在步骤5）中，他把自己已经选好的w送给V，使得V在步骤6）中验证成立。攻击者伪装成P成功的概率为1/b。

用类似Schnorr身份识别方案的方法可以证明：攻击者知道P传递给V的一个β值，且利用它成功伪造P的概率大于1/b，则可在多项式时间内计算出P的私有信息x，具体证明过程略。

从上面的分析可知，攻击者能以不可忽视的概率成功伪装成示证者P，并能推导出P的秘密信息x，因此该协议不满足隐藏性；反过来，不知道P的秘密信息的人成功执行识别方案的概率可以忽略不计，从而该协议是合理的。但是，没有证明Guillou-Quisquater身份识别方案是安全的。