现代密码学74身份识别技术

身份证明技术

传统的身份证明：

一般是通过检验“物”的有效性来确认持该物的的身份。徽章、工作证、信用卡、驾驶执照、身份证、护照等，卡上含有个人照片(易于换成指纹、视网膜图样、牙齿的X适用的射像等)。

信息系统常用方式：

用户名和口令交互式证明两方参与示证者P(Prover)，知道某一秘密，使V相信自己掌握这一秘密；验证者V(Verifier)，验证P掌握秘密；每轮V向P发出一询问，P向V做应答。V检查P是否每一轮都能正确应答。

交互证明与数学证明的区别数学证明的证明者可自己独立的完成证明交互证明由P产生证明，V验证证明的有效性来实现，双方之间要有通信交互系统应满足完备性：如果P知道某一秘密，V将接收P的证明正确性：如果P能以一定的概率使V相信P的证明，则P知道相应的秘密身份识别方案自行识别是一种重要的安全服务，在诸如访问自动出纳机、登录计算机、识别入网蜂窝电话用户等等都需要用到识别方案。识别和身份验证是不同的：身份验证：需要交换承载信息，其通信的一方或双方需要验证。识别：不需要交换承载信息，是对一个用户身份的实时验证。弱识别是基于非时变的口令或密码。认证过程：（1）A将他的秘密口令传送给计算机（2）计算机完成口令的单向函数计算（3）计算机把单向函数值和机器存储的值进行比较。弱识别

一个安全的识别协议至少应该满足以下两个条件：（1）证明者A能向验证者B证明他的确是A。（2）在证明者A向验证者B证明他的身份后，验证者B没有获得任何有用的信息，B不能模仿A向第三方证明他是A。识别协议

暂时号：在同一个目的中只使用一次，它可以消除重发攻击。如：随机号码、时戳、序列号等。例子（1）A通过密码和用户名向B登记；（2）B发给A一个随机号码（询问）；（3）A用一个随机号码的加密值答复，其中使用了A的密码作为密钥完成加密（响应）；（4）B证明A确实拥有密钥（密码）。询问-响应识别（强识别方案）Schnorr协议需要一个可信中心，记为TA.TA将为协议选择下列一些参数：（1）p及q是两个大素数，且q|(p-1).q至少140位，而p至少为512位。（2）α∈Z*P为q阶元（3）h是一输出为t位的单向函数，t为一个安全参数；（4）公开密钥v和秘密密钥s，用作签名。p,q,h及其公开密钥都公布。每位用户自己选定个人秘密密钥s∈[1,q-1],且计算公开密钥v=α-smodp。Schnorr身份识别方案证明者A能向验证者B证明他身份的协议（Schnorr识别协议）可描述为：（1）用户A将其身份名I及公开密钥送交验证者B。验证者根据TA的数字签名来验证用户A的公开密钥。（2）用户A任选一整数r，1≤r≤q-1,计算X=αrmodp,并将X送给验证者B。（3）验证者B任选一整数e∈[1,2t],送给用户A。（4）用户A送给验证者B：y=r+semodq;（5）验证者B验证X=αy×vemodp.Schnorr身份识别方案

针对一般的交互式用户身份证明协议，都必须满足以下三种性质：（1）完全性（2）健全性或合理性（3）隐藏性Schnorr身份识别方案TA将为协议选择下列一些参数：p及q是两个大素数，α1,α2∈ZP为q阶元,对系统的所有参加者包括A，TA保密c=logα1α2。假定任何人计算c都是不可能的。TA选择一个签名方案和一个Hash函数。Okamoto身份识别方案TA向A颁布一个证书的协议为：（1）TA建立A的身份并颁布一个识别串ID(A);（2）A秘密地选择两个随机指数m1,m2,1≤m1,m2≤q-1，并计算v=α1-m1α2-m2

modp，将v发送给TA；（3）TA对（ID,v）签名，s=SigTA(ID,v)。TA将证书C(A)=(ID(A),v,s)发送给A。Okamoto身份识别方案（1）A随机选择两个数r1,r2,0≤r1,r2≤q-1，并计算X=α1r1α2r2

modp;（2）A将他的证书C(A)=(ID(A),v,s)和X发送给B；（3）B通过检测VerTA(ID,v)=TURE来验证TA的签名。（4）B随机选择一个数e,1≤e≤2t,t为安全参数并将e发送给A。（5）A计算y1=(r1+m1e)modq,y2=(r2+m2e)mod，并将y1,

y2发给B。（6）B验证X=α1y1α2y2

vemodpOkamoto身份识别方案

协议建立过程如下：TA选取两个大素数p和q，形成n=pq。保密p和q，公开n。TA选择一个大素数b（用作一个安全参数）和一个公开的RSA加密指数。TA选择一个签名方案和一个Hash函数。Guillou-Quisquater身份识别方案TA向A颁布一个证书的协议为：（1）TA建立A的身份并颁布一个识别串ID(A);（2）A秘密地选择一个随机数m,0≤m≤n-1，A计算v=(m-1)

bmodp,并将v发送给TA；（3）TA对（ID,v）签名，s=SigTA(ID,v)。TA将证书C(A)=(ID(A),v,s)发送给A。Guillou-Quisquater身份识别方案（1）A随机选择一个整数r,0≤r≤n-1，并计算X=rb

modn;（2）A将他的证书C(A)=(ID(A),v,s)和X发送给B；（3）B通过检测VerTA(ID,v)=TURE来验证TA的签名。（4）B随机选择一个数e,0≤e≤b-1,并将e发送给A。（5）A计算y=rmemodn,并将y发给B。（6）B验证X=veybmodn.Guillou-Quisquater识别协议Shamir的基于身份的密码方案的基本思想基于身份的身份识别方案基于身份的密码方案的安全性主要依赖于以下几个方面:（1）所使用的密码变换的安全性（2）存储在密钥产生中心的特权信息的保密性（3）在密钥产生中心给用户颁布Smart卡之前所完成的识别检测的严格性。（4）为了阻止用户的Smart卡的丢失、复制或未授权的使用，用户所采取的措施。基于身份的身份识别方案基于身份的身份识别方案签名的产生签名的验证合法/非法密钥的产生随机种子k信道m,s,l公钥号码本消息mkv签名的产生签名的验证合法/非法密钥的产生随机种子k信道m,s,l签名者的身份消息mkvkgII公钥签名方案基于身份的签名方案TA向A颁布一个值u的过程如下：（1）TA建立A的身份并颁布一个识别串ID(A);（2）TA计算u=(H(ID(A))-1)αmodn,并将u发送给A。Guillou-Quisquater的基于身份的识别协议Guillou-Quisquater的基于身份的识别协议如下：（1）A随机选择一个整数r,0≤r≤n-1，并计算X=rbmodn;（2）A把ID(A)和X发送给B；（3）B计算H(ID(A))；（4）B随机选择一个数e,0≤e≤b-1,并将e发送给A。（5）A计算y=ruemodn,并将y发给B。（6）B验证X=veybmodn.Guillou-Quisquater的基于身份的识别协议零知识证明最小泄露证明和零知识证明：以一种有效的数学方法，使V可以检验每一步成立，最终确信P知道其秘密，而又能保证不泄露P所知道的其他信息。简化的Fiat-Shamir身份识别方案(1)P取随机数r(0<r<n)，计算a=r2modn，送给V；(2)V将一随机选e∈{0,1},将e发送给P；(3)P计算b≡ryemodn，若e=0，b=r,则P将b送给V；若e=1，b≡rymodn,则P将b送给V；(4)若b2

≡axemodn，V接受证明。

简化的Fiat-Shamir身份识别方案完备性如果P和V遵守协议，且P知道y，则应答b≡ryemodn是应是模n下axe的平方根，V接收P的证明，所以协议是完备的。正确性P不知道y，他也可取r，送b=r2modn给V，V送b给P。P可将r送出，当b=0时则V可通过检验而受骗，当b=1时，则V可发现P不知y，B受骗概率为1/2，但连续t次受骗的概率将仅为2-tV无法知道P的秘密，因为V没有机会产生(0,1）以外的信息，P送给V的消息中仅为P知道v的平方根这一事实。零知识证明的基本协议例[Quisquater等1989]。

设P知道咒语，可打开C和D之间的秘密门，不知道者都将走向死胡同中。ABCD零知识证明的基本协议

(1)V站在A点；

(2)P进入洞中任一点C或D；

(3)当P进洞之后，V走到B点；

(4)V叫P：(a)从左边出来，或(b)从右边出来；

(5)P按要求实现(以咒语，即解数学难题帮助)；

(6)P和V重复执行(1)～(5)共n次。若A不知咒语，则在B点，只有50%的机会猜中B的要求，协议执行n次，则只有2-n的机会完全猜中，若n=16，则若每次均通过B的检验，B受骗机会仅为1/65536零知识证明的基本协议哈米尔顿回路图论中有一个著名问题，对有n个顶点的全连通图G，若有一条通路可通过且仅通过各顶点一次，则称其为哈米尔顿回路。Blum[1986]最早将其用于零知识证明。当n大时，要想找到一条Hamilton回路，用计算机做也要好多年，它是一种单向函数问题。若A知道一条回路，如何使B相信他知道，且不告诉他具体回路？

零知识证明的基本协议

(1)A将G进行随机置换，对其顶点进行移动，并改变其标号得到一个新的有限图H。因，故G上的Hamilton回路与H上的Hamilton回路一一对应。已知G上的Hamilton回路易于找出H上的相应回路；

(2)A将H的交给B；

(3)B向A提出下述问题之一：(a)出示证明G和H同构，(b)出示H上的Hamilton回路；

(4)A执行下述任务之一：(a)证明G和H同构，但不出示H上的Hamilton回路，(b)出示H上的Hamilton回路但不证明G和H同构；

(5)A和B重复执行(1)～(4)共n次。智力扑克A和B通过网络进行智力扑克比赛，不用第三方做裁判，发牌者由任一方担任，要求发牌过程满足任一副牌是等可能的发给A，B的牌没有重复每人知道自己手中的牌，不知道别人的牌比赛结束后，每一方都能发现对方的欺骗行为为满足要求，A,B方需要加密一些信息，比赛结束前，这些机密算法都是保密的。智力扑克A和B的加密解密算法记为EA，EB，DA，DB，满足EA(

EB(m))=EB(

EA(m))A,B协商好用以表示52张牌的w1,…,w522.随机选5个EB(wi)3.另选5个EB(wi)，以EA加密以DA解密1.洗牌，用EB对52个wi加密解密，作为发给自己的牌以DB解密52个EB（wi）5个随机的E