Schnorr身份识别方案的优化与应用

Schnorr身份识别方案由Schnorr在1991年提出，它是一种计算量、通信量都很小的识别方案。该识别方案的安全性基于计算离散对数的困难性，它特别适用于在智能卡（Smart Card）上使用。

1.选择参数

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

●p、q是两个大素数，且q|（p-1），q至少为140bit，而p至少512bit。

●α∈Z_p*，为q阶元。

●h（x）是输出为t bit的单向函数，t是一个安全参数（t=40bit或t=72bit）。

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

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

1）TA为P建立身份信息ID_P，一般为512bit。

2）P选取随机数x作为自己的私钥x∈[1，q-1]，计算出公钥y≡α^-x（mod p），P到TA处注册其公钥。

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

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

1）P将自己的身份证书Cert_P交给验证者V。

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

3）P任意选择一整数r，r∈[1，q-1]，计算β≡α^r（mod p）发给V。

4）V任选取一整数e∈[1，2^t]作为询问值发送给P。

5）P计算w≡r+xe（mod q），把w作为对V的应答值发送给V。

6）V验证α^wy^e（mod p），判断其是否等于β，若相等，则V相信对方就是P。(www.xing528.com)

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

α^wy^e≡α^r+xe（α-x）e≡αr（mod p）≡β

4.安全性分析

掌握秘密随机数x的示证者P，对于验证者V的任何询问e他都能正确回答w并通过V的验证，所以该协议是完全的。在步骤5）中，由于随机整数r的干扰，P并未向V暴露自己的私钥x，而V完全可以相信P拥有私钥x，否则无法得到α^wy^e（mod p）≡β的结果。

在步骤4）中，t是安全参数，如果t值不够大，则攻击者有可能猜中V的询问值e。假设攻击者在步骤3）中先选取w∈[1，q-1]，再计算α^wy^e（mod p）≡β，并将β送给V。在步骤5）他把自己已经选好的w送给V，V在验证时肯定通过。攻击者伪装成P成功的概率为2^-t。

假设攻击者知道P传递给V的一个β值，且成功伪装成P的概率大于2×2^-t，这说明对于一个β值攻击者已知道了（e₁，w₁）和（e₂，w₂）两对值，使得

从而有

w₁^-w2≡x（e₁-e₂）（mod q）

因0＜|e₁-e₂|＜2^t＜q，有gcd（（e₁-e₂），q）=1，则（e₁-e₂）^-1存在，所以P的私钥可求出

x≡（w₁-w₂）（e₁-e₂）^-1（mod q）

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

因此，针对一般交互式身份识别协议，有以下三方面要求。

1）完全性：对于诚实的合法示证者和验证者，验证成功的概率几乎百分之百。

2）合理性：当不知道示证者信息和私钥时，验证通过的概率几乎为零。

3）隐蔽性：若示证者是诚实的，无论协议执行多少次，任何人（包括验证者）都无法推知示证者的密钥，无法冒充这个示证者。

然而，一个满足完全性和合理性的协议，未必是安全的。比如P可以把私钥有意泄露给C，从而C能够冒充P，使协议变得不安全。但完全性和合理性却不受影响。