《零知识证明及其安全协议构造》

第六讲:零知识证明及其安全协议构造,主讲人：xxxxxx系2020年5月11日星期一,通信网安全理论与技术课程,实践性,通信安全保障,协议安全设计,理论和技术基础,前导性,课程体系及主要内容讲解内容,通信网安全现状、趋势与策略第1讲通信网技术基础与安全体系第2讲通信网安全基础理论与技术(密码学、攻击与防御技术)第3讲网络安全协议理论设计与分析认证协议以及密钥建立协议第4讲特殊数字签名与阈下信道设计第5讲零知识证明及其安全协议构造第6讲安全协议形式化分析与设计第7讲典型的网络安全协议(IPSec协议、Kerberos协议、Radius/AAA协议)第810讲通信网安全保障技术第11讲无线网络安全性增强技术(WLAN为主)第12讲网络防火墙与入侵防御技术第13讲网络安全实现方案设计与分析第14讲,内容提要,零知识证明：基本概念与形式零知识身份认证协议零知识公平性游戏协议,内容提要,零知识证明：基本概念与形式基本概念交互零知识证明交互零知识证明例子：Q-G零知识证明协议交互零知识证明一般形式零知识身份认证协议零知识公平性游戏协议,1.零知识证明基本概念,若我们知道某些秘密信息，如果我们想让别人相信我们知道这些秘密信息，同时又不想让别人知道这些秘密信息是什么，那么，我们该怎么办？解决方法零知识证明,情形：A要向B证明自己拥有某个房间的钥匙，假设该房间只能用钥匙打开锁，而其他任何方法都打不开。这时A怎么证明？A把钥匙出示给B，B用这把钥匙打开该房间的锁，从而证明A拥有该房间的正确的钥匙B确定该房间内有某一物体，A用自己拥有的钥匙打开该房间的门，然后把物体拿出来出示给B，从而证明自己确实拥有该房间的钥匙方法属于零知识证明，其好处在于在整个证明的过程中，B始终不能看到钥匙的样子，从而避免了钥匙的泄露,1.零知识证明基本概念,假设：实体：P是某些秘密信息的拥有者，V是验证者任务：P想向V证明自己掌握这些秘密信息，V验证P是否真的掌握这些秘密信息零知识证明：P设法使V相信自己掌握这些秘密信息，同时又不向V泄露这些秘密信息,与之相对应的有：最大泄漏证明：出示或说出此事，但这也使V和A知道或掌握了这一秘密最小泄漏证明：利用数学方法，使V可检验每一步成立，最终确信P知道其秘密，而又能保证P的秘密尽可能少泄露,零知识证明是现代密码学中的一个非常有趣、艺术性的研究领域，目前在密码学中得到了广泛的应用，尤其是在认证协议、数字签名方面,1.零知识证明基本概念,优势：除了证明结论的正确性外，零知识证明不泄漏任何其他信息，因此它是构造安全协议的主要工具，可用安全协议的一部分，使各方都能放心地执行该协议RSA算法就是一种典型的零知识证明系统，用户通过让别人用它的公开密钥来解密他用私钥加密的密文，以表明他确实拥有私钥，而不需把私钥实际拿出来给别人看零知识证明可分为交互式的和非交互式的两个类型,1.零知识证明交互证明,有两个参与者P、V，其中P称为证明者，V称为验证者，P希望向V证明她知道某一个事实，但是她又不愿意把事实告诉给VP和V可采用交互式证明来达到目的交互证明是一个一问一答的协议，由若干轮构成，在每一轮中，P和V轮流作如下工作：接收从对方发送来的消息进行自己的计算发送消息给对方如果P要向V证明她知道某一个事实，那么先由V提问，然后P回答。在协议的最后，V根据P是否成功地回答了他所提出的所有问题，来接受或拒绝P证明的事实,1.零知识证明交互证明,一个交互证明系统应满足如下的两个条件：完备性(Completeness)：若P回答正确，则V接受P的证明的概率很大有效性(Soundness)：若P回答错误，则V接受P的证明的概率很小在零知识协议中，还满足下述性质零知识性(Zero-knowledge)：无论V采取任何手段，当P的声明是真的，P不违背协议时，V除了接受P的结论以外，得不到其他额外的信息,1.零知识证明交互证明,在交互式证明中，有两个重要问题值得关注证明过程中，验证者V获取了多少信息？为了让验证者V确信P要证明的事实，他们间需进行多少次交互？,第2个问题不仅对于零知识的实际应用非常重要，而且在计算复杂性理论中也具有重大意义,第1个问题的理想答案是0，即：信息量为0。正是由于验证者获取的信息量为0，所以将具有这样性质的交互式证明称为零知识协议,1.零知识证明例子：Q-G零知识证明协议,1990年，Quisquater和Guillon提出一种形象的基本零知识证明协议的例子，如图表示一个简单的迷宫，只有知道秘密口令的人才能打开C和之间的密门,现在，P希望向V证明P能够打开此门，但是又不愿意向V泄漏P掌握的秘密口令P采用了所谓的“分隔与选择”技术实现一个零知识证明协议,1.零知识证明例子：Q-G零知识证明协议,1)V站在点2)P一直走到迷宫深处，随机选择点或者点3)在P消失后，V走到点,4)V向P喊叫，要她：从左通道出来，或者从右通道出来5)P答应了，如果有必要她就用秘密口令打开密门P和V重复第(1)至第(5)步n次,1.零知识证明例子：Q-G零知识证明协议,在上述协议中，如果P不知道秘密口令，他只能从来路返回到B点，而不能走另外一条路此外，P每一次猜对V要求他走哪一条路的概率是1/2,因此，每一轮协议P能够欺骗V的概率是1/2。执行n轮协议后，P成功欺骗V的概率是1/2n假定n=16，则执行16轮协议后，P成功欺骗V的概率是1/216=1/65536在该过程中，如果P能够16次按V的要求路线返回，V即能证明P确实知道秘密口令；同时，V无法从上述证明过程中获取丝毫有关P的秘密口令的消息零知识证明,1.零知识证明例子：Q-G零知识证明协议,分隔与选择(cutandchoose)：A将蛋糕分成两半；B为自己选择其中的一半A得到剩下的一半A如果分割不均匀，B总能选择对自己有利的一半公平协议,1.零知识证明一般形式,证明者P和验证者V共享输入(函数或者是值)如果验证者V检查，对于每一个挑战的响应都是正确的，这个协议才输出Accept，否则，输出Reject,1.零知识证明形式1：整数分解问题,设p和q两个大素数，n=pq。假设P知道n的因子，若P想让V相信他知道n的因子，并且P不想让V知道n的因子，则他们可执行下面的协议：1.V随机的选取一个大整数x，计算y=x4modn，V将y告诉给P2.P计算z=y1/2modn，P将z告诉给V3.V验证z=x2modn是否成立,1.零知识证明形式1：整数分解,上述协议可重复执行多次。如果P每次都能正确地计算出y1/2modn，则V就可以相信P知道n的因子p和q可以证明：计算y1/2modn等价于对n进行因子分解如果P不知道n的因子p和q，则计算y1/2modn是一个困难的问题即：在P不知道n的因子情形下，在多次重复执行上述协议后，P每次都能正确地计算出y1/2modn的概率非常小协议的执行过程中，V没有得到关于n的因子p和q的任何信息,1.零知识证明形式2：平方根问题,1.参数选取选定一个随机模n=pq,p,q是不同的大素数。产生随机数s，使得gcd(s,n)=1且s2=vmodn。n和v是公开的，p,q,s作为示证者P的秘密(注意找到modn的平方根与分解n等价)2.一次证明过程PV：P取随机数r(n)，计算x=r2modn,将x发送给验证者VVP：V将一随机比特b发送给PPV：若b=0,则P将r发送给V若b=1，则P将y=rs发送给VV：若b=0，则V证实x=r2modn，但不能证明P知道s若b=1，则V证实xv=y2modn，从而证明P知道s3P和V重复执行t次过程2，直到V相信P知道s为止,1.零知识证明形式2：平方根问题,基于平方根问题的零知识证明协议性质：完备性：如果P和V遵守协议，且P知道s，则应答rs应是模n下xv的平方根，V接收P的证明，所以协议是完备的有效性：P不知道s，他也可取r，发送x给V，V发送b给P。P可将r送出，当b=0时则V可通过检验而受骗；当b=1时，则V可发现P不知s。V受骗概率为1/2，但连续t次受骗的概率将仅为2t零知识性：V无法知道P的秘密,2.一次证明过程(n和v是公开的，p,q,s作为示证者P的秘密)PV：P取随机数r(n)，计算x=r2modn,将x发送给验证者VVP：V将一随机比特b发送给PPV：若b=0,则P将r发送给V若b=1，则P将y=rs发送给VV：若b=0，则V证实x=r2modn,但不能证明P知道s若b=1，则V证实xv=y2modn,从而证明P知道s,1.零知识证明形式3：离散对数问题,找到两个公开的数字：一个素数q和一个整数p，定义p为素数q的一个原根，如果数值pmodq，p2modq，pq-1modq是各不相同的整数并且以某种排列方式组成了从1到q-1的所有整数对于一个整数b，可以找到一个唯一的指数i，使得b=pimodq其中0iq-1，0bq-1指数i称为b的以p为基数的模q的离散对数（i=logpbmodq）已知p,q,i,，计算b很容易反之，已知p,q,b，计算i很困难(应用时：p,q,b公开，i保密)计算模一个素数的指数相对容易，计算离散对数很困难小心地选择素数，对于离散对数问题目前还没有多项式时间算法为了抵抗已知攻击，该素数一般应是超过150位的大数),1.零知识证明形式3：离散对数问题,假定：P的秘密是xq，p、q和x对应的值b=pxmodq都是公开的重复以下步骤m次（p、q、b公开；x保密）：P选取某一个kq，计算commit=pkmodq，发送commit给VV通过抛硬币的方式选择challenge是0或1发送给P如果challenge=0，P计算Response=k；如果challenge=1，P计算Response=(k+x)modq，发送Response给V如果challenge=0，V验证presponsemodq是否是commit；如果challenge=1，V验证presponsemodq是否是commitb如果m次检验都成功，则V接受证明,1.零知识证明形式3：离散对数问题,完备性：如果P和V遵守协议，且P知道x，很容易证明V可以接收P的证明，所以协议是完备的有效性：P不知道x，他可以猜测Challenge：如果为0，则一开始就发送commit=pkmodq给V；如果为1，则一开始就发送commit=(pkmodq)/b给V。之后总是在第三步发送k给V。每次受骗概率为1/2，但连续m次受骗的概率将仅为2-m零知识性：V无法知道P的秘密，因为V没有机会产生(0,1）以外的信息，根据离散对数的单向性质可以推断V无法获知新的信息,如果challenge=0，V验证presponsemodq是否是commit；如果challenge=1，V验证presponsemodq是否是commitb,1.零知识证明形式4：单向函数,假定：P的秘密是xq，存在一个单向函数f，满足条件：f(x*y)=f(x)f(y)，V可以知道X=f(x)重复以下步骤m次：P选取某一个k，计算commit=f(k)，发送commit给VV通过抛硬币的方式选择challenge是0或1发送给P如果challenge=0，P计算Response=k；如果challenge=1，P计算Response=k*x，发送Response给V如果challenge=0，V验证f(Response)是否是commit；如果challenge=1，V验证f(Response)是否是commit*X如果m次检验都成功，则V接受证明（被欺骗的概率是2-m）,1.零知识证明形式4：单向函数,完备性：如果P和V遵守协议，且P知道x，显然P可以任意给出k或者k*x，而在f(x*y)=f(x)f(y)条件下，验证确实也总是成功的，所以协议是完备的有效性：P不知道x，他可以猜测Challenge，如果为0，则一开始就发送commit=f(k)给V；如果为1，则一开始就发送commit=f(k)/X给V。之后总是在第三步发送k给V。每次受骗概率为1/2，但连续m次受骗的概率将仅为2-m零知识性：V无法知道P的秘密，因为V没有机会产生(0,1)以外的信息，只要f(x)这一函数的单向性能够保证即可,如果challenge=0，V验证f(Response)是否是commit；如果challenge=1，V验证f(Response)是否是commit*X,内容提要,零知识证明：基本概念与形式零知识身份认证协议FFS协议(简化版)FFS协议(增强版)GQ协议Schnorr协议零知识公平性游戏协议,2.零知识身份认证协议,在一个安全的身份认证协议中，我们希望被认证者P能向验证者V证明他的身份，而又不向P泄露他的认证信息目前典型的零知识身份认证协议有：Feige-Fiat-Shamir身份认证协议：FFS协议Guillo-Quisquater身份认证协议：GQ协议Schnorr身份认证协议,2.零知识身份认证协议,一个安全的身份认证协议至少应满足以下两个条件：证明者P能够向验证者V证明他的确是P在证明者P向验证者V证明他的身份后，验证者V不能获得关于P的任何有用信息，使得V能冒充P向第三方证明V是P也就是说，P即能向V证明他的身份，又没有向V泄露P的识别信息，安全的身份识别协议应满足零知识证明,2.零知识身份认证协议FFS协议(简化版),可信赖仲裁方TTP：选定一个随机模数n=p1p2，p1、p2为两个大素数；产生随机数v(v为对模n的二次剩余)，其中n至少为512比特，尽量长达1024比特；按如下方式分配公钥和私钥：选择随机数v使得x2=vmodn有一个解并且v1modn存在，以v作为被验证方P的公钥计算最小的整数s：ssqrt(v1)modn，将它作为P的私钥,2.零知识身份认证协议FFS协议(简化版),身份认证过程：PV：用户P取随机数r（rn），计算x=(r2)modn，发给验证方VVP：V将随机比特b送给PPV：若b=0，则P将r送给V；若b=1，则将y=r*smodn发给VV：若b=0，则V验证x=r2modn，从而证明P知道sqrt(x)；若b=1，则V验证x=y2vmodn，从而证明P知道s这是一轮认证，P和V可将此协议重复t次，直到V确信P知道s为止,2.零知识身份认证协议FFS协议(简化版),安全性讨论如下：,V伪装P的可能性：V和其他验证者W开始一轮协议：第一步他可用P用过的随机数r，若W所选的b值恰与以前V发给P的一样，则V可将在第(3)步所发的r或y重发给W，从而可成功的伪装P。但W可能随机地选b为0或1，故这种工具成功的概率为1/2，执行t次，则可使其将为2t,P欺骗V的可能性：P不知道s，他也可选取随机数r，将x=r2modn发给V，V发送随机比特b给P，P可将r发出当b=0时，则V让P通过检验而受骗当b=1时，则V可发现P不知道sV受骗的概率为1/2，但连续t次受骗的概率将仅为21。,2.零知识身份认证协议FFS协议(增强版),TTP选n=p1p2，p1、p2为两个大素数，并选k个不同的随机数v1,v2,vk，各vi是modn的平方剩余，且有逆。以v1,v2,vk为被验证方P的公钥计算最小正整数si，使si=(vi)1/2modn，将s1,s2,sk作为P的私钥,身份认证过程：PV：P选随机数r(rm)，计算x=r2modn并发送给验证方VVP：V选k比特随机二进制串b1,b2,bk传送给PPV：P计算y=r(s1b1s2b2skbk)modn，并送给VV：V验证x=y2(v1b1v2b2vkbk)modn此协议可执行t次，直到V相信P知道s1,s2,sk，P欺骗V的机会为2kt,2.零知识身份认证协议FFS协议(增强版),2.零知识身份认证协议GQ协议,该协议也需要三方参与、三次传送，它是利用公钥体制实现，具体如下：TTP：先选定RSA的秘密参数p和q，生成大整数模n=pq公钥指数有e3，其中gcd(,e)=1，=(p1)(q1)计算出秘密指数d=e1mod，公开(e,n)，各用户选定自己的参数用户A的唯一性身份IA，由散列函数H得散列值JA=H(IA)，IJA2160)元素a为q阶元素，lap1令g为GF(p)的生成元，则得到a=g(p1)/qmodq由TTP向各用户分发系统参数(p,q,g)和验证函数(即TTP的公钥)，用此验证TTP对消息的签字,2.零知识身份认证协议Schnorr协议,A：对每个用户给定惟一身份I，用户A选定秘钥s，0sq1，并计算v=gsmodpATTP：A将IA和v可靠地送给TTPTTPA：并从TTP获得证书，CA=(IA,v,ST(IA,v),具体认证过程如下：A：选定随机数r，1rq1，计算x=grmodp，这是预处理步骤，可在B出现之前完成；AB：A将(CA,x)送给B；BA：B以TTP的公钥解密ST(IA,v)，实现对A的身份IA和公钥v认证，并传送一个介于0到2t1之间的随机数e给A；AB：A验证1e2t，计算y=(se+r)modq，并将y送给B；B：B验证x=gyvemodp，若该等式成立，则认可A的身份合法,安全性基于参数t，t要选得足够大以使正确猜对e的概率2t足够小，Schnorr建议：t为72位，p大约为512位，q为140位。它是一种对s的零知识证明，在认证中没有暴露有关s的任何有用信息,2.零知识身份认证协议Schnorr协议,2.零知识身份认证协议Schnorr协议,从v求s就是求离散对数，在计算上是不可行的r和s都是用户的秘密，假冒者Eve是无法从y中得到用户的秘密，当然也就无法假冒证明者A,内容提要,零知识证明：基本概念与形式零知识身份认证协议零知识公平性游戏协议智力扑克掷硬币协议采用平方根掷硬币利用单向函数掷硬币采用二次剩余,3.零知识公平性游戏协议智力扑克,假设两个人A和B通过计算机网络进行智力扑克比赛，比赛中不用第三方做裁判。发牌者可由任一方担任，发牌过程应满足以下要求：1.任一副牌（即发给参赛人员手中的牌）是等可能的2.发给A、B手中的牌没有重复的3.每人都知道自己手中的牌，但却不知对方手中的牌4.比赛结束后，每一方都能发现对方的欺骗行为(如果有的话),3.零知识公平性游戏协议智力扑克,为满足这些要求，A、B之间必须以加密形式交换一些信息协议执行，可是单钥加密体制也可以是公钥密码设EA和EB、DA和DB分别表示A和B的加密变换和解密变换，在比赛结束之前，这些变换都是保密的，比赛结束后才公布用以证明比赛的公正性要求加密变换满足交换律，即对任意消息M有：EA(EB(M)=EB(EA(M),3.零知识公平性游戏协议智力扑克,比赛开始前A、B协商好用以表示52张牌的消息w1,w2,w52，协议中设A为发牌人，并设给每人发5张牌。协议如下：B先洗牌，然后用EB对52个消息分别加密，将加密结果EB(wi)发送给AA从收到的52个加密消息中随机选5个EB(wi)，并发送给B，B用DB对这5个值解密，并作为发给自己的一副牌(因为EB和DB都是保密的，所以A无法知道B手中的牌),随机选5个EB(wi),洗牌，用EB对52个wi加密解密，作为发给B的牌,52个EB（wi）,5个随机的EB（wi）,A,B,3.零知识公平性游戏协议智力扑克,A另选5个EB(wi)，用EA加密后发送给BB用DB对收到的值解密后再发送给A，A用DA对收到的值解密后作为发给自己的一副牌，这是因为B发送给A的值是DB(EA(EB(wi)=DB(EB(EA(wi)=EA(wi)其中用到加密变换的交换律,随机选5个EB(wi)另选5个EB(wi)，以EA加密以DA解密，作为发给A的牌,洗牌，用EB对52个wi加密解密，作为发给B的牌以DB解密,52个EB（wi）,5个随机的EB（wi）,5个的EA(EB(wi),5个的EA(wi),完后公开所有加密变换,A,B,3.零知识公平性游戏协议智力扑克,分析它是否满足发牌要求：对第2和第4个要求，可在比赛结束后公开所有的加密变换和解密变换，双方都可检查对方的牌看是否有欺诈对第1个和第3个要求来说，关键在于加密变换EB的强度，由EB(wi)可能得不出wi，但有可能得出wi的部分信息例如：wi是一个比特串，则可能从EB(wi)得出wi的最后一个比特，因此A可将52个EB(w1),EB(w2),EB(w52)分成两个子集，A在发牌时可将发给B的牌集中在某一子集中，因此使得第个和第个要求无法满足因此EB加密变换应该足够强,1.任一副牌（即发给参赛人员手中的牌）是等可能的2.发给A、B手中的牌没有重复的3.每人都知道自己手中的牌，但却不知对方手中的牌4.比赛结束后，每一方都能发现对方的欺骗行为(如果有的话),3.零知识公平性游戏协议掷硬币协议,在某些密码协议中要求通信双方在无第三方协助的情况下，产生一个随机序列，因为A、B之间可能存在不信任关系，因此随机序列不能由一方产生再通过电话或网络告诉另一方该问题可通过掷硬币协议来解决：Alice抛币Bob猜测是花还是字好处：Alice和Bob各有50%的机会获胜；任何一方欺骗则认为其在博弈中失败；协议执行结束后，Alice和Bob都知道结果如果由一个人来完成，他可以作弊,3.零知识公平性游戏协议掷硬币协议,掷硬币协议主要有如下几种实现方式：采用平方根掷硬币利用单向函数掷硬币二次剩余,3.零知识公平性游戏协议掷硬币协议：平方根,1.采用平方根掷硬币协议如下：AB：A选择两个大素数p、q，将乘积n=pq发送给B。BA：B在1和n/2之间，随机选择一整数u，计算zu2modn，并将z发给AA：A计算模n下z的4个平方根x和y，设x是xmodn和-xmodn中较小者，y是ymodn和-ymodn中较小者，则由于1un/2，所以u为x和y之一(注：求z在模n下的平方根与分解n是等价的)AB：A猜测u=x或u=y(或者A找出最小的i使得x的第i个比特与y的第i个比特不同，A猜测u的第i个比特是0还是1)，A将猜测发送给BBA：B告诉A猜测正确或不正确，并将u的值发送给A。A：A公开n的因子,3.零知识公平性游戏协议掷硬币协议：平方根,安全性分析：1.A能否欺骗B？因u是B随机选取的，A不知道u，所以要猜测u只能是计算模n下z的4个平方根，猜中的概率是1/22.B如何能欺骗A？如果B在A猜测完后能够改变u的值，则A的猜测必不正确，A可通过判断zu2modn？检查出B是否改变了u的值，所以B要想改变u的值就只能在x和y之间进行。而B若掌握x和y，就可通过gcdx-y,n或gcdx+y,n求出p和q，说明B的欺骗与分解n是等价的,3.零知识公平性游戏协议掷硬币协议：平方根,例子(采用平方根掷硬币)：A取p=3,q=7，将n=21发送给BB在1和21/2之间，随机选择一个整数u=2，计算z22modn4并将z=4发送给AA计算模21下z=4的4个平方根x=2,-x=19,y=5,-y=16，取x=2，y=5A猜测u=5并将猜测发送给BB告诉A猜测不正确，并将u=2发送给A，A检验u=2在1和21/2之间且满足422mod21，A知道自己输了A公开n=21的因子p=3,q=7，B检验n=pq，知道自己赢了,3.零知识公平性游戏协议掷硬币协议：单向函数,利用单向函数掷硬币设