不可区分性在公约密码学中的应用分析

1、不可区分性在公钥密码学中的应用摘要：本文主要总结了不可区分性在公钥密码体制中的运用，这些运用主要包括如何刻画密码体制的安全性（语义安全性）、如何通过规约的方式利用不可区分实验证明密码体制的安全性、以及一些常见的密码体制中不可区分性的作用。全文主要分为三个部分，第一部分主要介绍了一些基础知识，包括密码体制的组成以及完善保密密码体制的含义，如何利用不可区分性来等价描述完善保密密码体制。第二部分主要介绍了不可区分实验（游戏）在公钥密码学中的应用。这一部分先对攻击者的层次进行了划分，之后介绍了如何用不可区分实验来给最基本的密码体制的语义安全性下定义。这一部分最后利用CCA2的语义安全性作为例子说明如何

2、利用不可区分实验定义拥有特定防御功能的公钥密码体制的语义安全性。第三部分介绍了规约证明的相关内容，规约证明现如今已成为现代公钥密码学可证明安全理论常用的证明方法，而两个问题规约的过程中与不可区分性密不可分。第四部分主要举了一个例子来说明不可区分性在证明密码体制安全性中的应用。本文对公钥密码学中的不可区分性理论做了比较简单的总结和归纳，不可区分性在公钥密码学可证明安全理论中有着十分重要的地位，本文对刚刚接触不可区分性的学者有着一定的帮助。第一部分：基础知识及不可区分性的定义这一部分内容主要介绍一下有关于不可区分性的基础知识，包括密码体制的组成、完善保密密码体制、完美不可区分性的含义以及敌手不可区

3、分性的含义。首先先给出密码体制的定义：定义1.1密码体制一个密码体制由三个部分构成：密钥产生算法Gen、加密算法Enc、解密算法Dec。他们的功能如下：（1）密钥产生算法Gen是一个概率算法，能够根据方案定义的某种分布选择并输出一个密钥k.（2）加密算法Enc,输入为密钥k和明文m,输出为密文Co把使用密钥k加密明文m记为Enck（m）.（3）解密算法Dec,输入为密钥k和密文c,输出为明文m。把使用密钥k解密密文c记为Deck（c）.对任意的密码体制的基本要求是：对任意通过Gen输出的密钥k,每个明文消息m都满足Deck(Enck(m)=m密钥生成函数Gen输出的所有可能的密钥称为密钥空间，

4、用K表示。所有明文消息的集合称为明文空间，记作M。集合K和M一起定义了所有可能的密文的集合C,称为密文空间。上述密码体制可记为明文空间为M的密码体制(Gen,Enc,Dec).如何刻画一个密码体制的安全性，完善保密密码体制是所有密码体制中最理想的情况：定义1.2完善保密密码体制1明文空间为M的密码体制(Gen,Enc,Dec)是完善保密密码体制，如果对于M上任意的概率分布，任何明文mwM,任何密文cWC且PrC=c0,都有PrM=m|C=c=PrM=m下面给出完美不可区分性对于完善保密密码体制的等价刻画。记C(m)为加密mwM时的密文概率分布。定义1.3完美不可区分性1C的概率分布独立于明文。

5、也就是说，对于任意的m0,m1WM,C(m0)和C(mJ的分布是相同的。由此，可以得到一下结论：定理1.11明文空间为M的密码体制(Gen,Enc,Dec)是完善保密密码体制当且仅当对于任意M上的概率分布，m0,m1亡M以及c-C,都有PrC=c|M=m0=PrC=c|M=m1证明：必要性显然。下证充分性：记p=PrC=c|M=m0由条件可知，对于任意的mM,都有PrC=c|M=m=PrC=c|M=m0=p,于是PrC=c=、PrC=c|M=mPrM=mm.-M=pPrM=mm：-M=p、PrM=mm.M二p=PrC=c|M=m0由于m0的任意性，故对任意的PrM=m|C=c=PrM=m,即该

6、密码体制星空差的一ZHTU口口Jo以上使用完美不可区分性给出了完善保密密码体制的等价条件。而在现代公钥密码学领域更多研究的则是称之为“敌手不可区分性”与密码体制安全性的内在联系。在第二部分将给出敌手不可区分性的相关内容，这块内容将涉及不可区分实验(游戏)，根据敌手能力的不同，游戏的进行方式也有所不同。第二部分：不可区分实验(游戏)在给出敌手不可区分性的定义之前，有必要对敌手的能力进行简单的分析和归类。下面首先介绍公钥密码体制中，敌手的攻击手段以及相应与这种攻击手段，敌手所具备的破译密码体制的能力：(1)唯密文攻击(COA):敌手只能通过考察一些密文来试图推导出解密密钥(即私钥)或这些密文对应的

7、明文(2)已知明文攻击(KPA):敌手已知一定数量的明文和相对应的密文，试图推导出私钥或者其他密文对应的明文。(3)非适应性选择明文攻击(CPA1):敌手可以选择一些明文，通过访问加密谕言机，得到这些明文相对应的密文(4)适应性选择明文攻击(CPA2):敌手可以选择一些明文，通过访问加密谕言机，得到这些明文相应的密文，且明文的选可依赖于前面得到的密文。值得注意的是，CPA1和CPA2的主要区别是在访问加密预言机的时候，CPA1只能一次性提交所选择的所有明文，而CPA2可以多次分阶段提交所选择的明文。所以从敌手能力的角度来说，CPA2的敌手能力更强。CPA1和CPA2统称为CPA。但是CPA的敌

8、手毕竟是属于被动的，下面两种攻击方式属于主动攻击:(5)非适应性选择密文攻击(CCA1)5:敌手可以选择密文，接着得到相应的明文。即敌手拥有解密谕言机的访问权。(6)适应性选择密文攻击(CCA2)5:敌手可以选择密文，得到相应的明文。且在见到挑战密文之后还能继续访问解密谕言机。在这里CCA2与CCA1的区别在于敌手是否拥有在见到挑战密文后还能访问解密谕言机的能力。CCA2中敌手有这个能力，但CCA1没有。CCA1也称为“午餐攻击”，意味着过了“午餐”时间，就不能再访问解密谕言机了。敌手的攻击能力基本上可以分为以上六种，但是随着科技的进步，敌手的能力在不断增强，需要我们对最新的攻击方式做出新的安

9、全性分析和证明。下面将介绍近代公钥密码体制中对安全性(语义安全性)普遍刻画一一不可区分实验(游戏)。首先需给出最基本的所谓窃听不可区分实验：设任意对称密钥密码体制n=(Gen,Enc,Dec),任何敌手A,对任意安全参数n,定义窃听不可区分实验PrivKAn)：(1)敌手A输出两个长度相等的消息m0,m1。(2)运行Gen函数生成密钥k,选择一个随机比特bw10,1,将mb加密得到密文c,并将密文给敌手A。(c称为挑战密文)(3)敌手输出b,如果b=b,则敌手攻击成功。1(注意：这里的敌手默认为PPT的敌手)定义2.1敌手优势函数参数为n的函数1AdvA,口(n)=Prb=b称为敌手优势函数。

10、这个函数形象地刻画了敌手猜对那一比特b的优势。利用敌手优势函数，我们可以非常自然地给出密码体制语义安全性的定义。不过在这之前，首先应该给出所谓函数“可忽略”的定义：定义2.22对于函数():Nt6,1)是可忽略的，如果Vc0,存在正整数Nc使得VNNc时都有,1；(N)屋Nc定义2.3密码体制n=(Gen,Enc,Dec)是语义安全的，如果对于任何PPT的敌手A,敌手优势函数AdvAn)可忽略。这个定义给出了一般密码体制的安全性刻画，下面针对于公钥密码体制，我们给出它的安全性定义，为了方便起见，我们将给出一个包含了不可区分实验以及敌手优势函数的全新定义：定义2.42一个公钥密码体制是语义安全的

11、，如果对于所有的PPT敌手，函数Pr:b=b2(pk,sk)Gen;(m0,m1)A(pk);b-Q1;cEnc(mb);b-A(pk,c)是可忽略的。在这个定义中，(pk,sk)Gen和(m0,m1)A(pk)对应着实验中的第步(公钥密码体制中密钥是公开的，所以出现在第一步)，b.0,1和c-Enc(mb)是实验中的第二步，b-A(pk,c)则是实验中的第三步，最后考察的事件则是b=b。以后如果不作说明，均已这个定义来阐述密码体制的语义安全性。这里可以举一个例子来说明如何定义能够防御特定攻击能力的敌手的密码体制的安全性：由上述对低收的分类我们知道适应性选择密文攻击即CCA2的敌手拥有比较强大

12、的攻击能力，针对这样的敌手，我们应该如何定义相应的安全性呢？CCA2,、首先我们可以写出CCA2的不可区分实验PubKAn(n):(1)运行Gen函数生成密钥(pk,sk),敌手A获得公开钥pk。(2)敌手访问解密谕言机。(即敌手输入密文，谕言机返回该密文对应的明文)(3)敌手A输出两个长度相等的消息m0,m1o(4)选择一个随机比特be6,1)，将mb加密得到挑战密文c,并将挑战密文给敌手A。(5)敌手继续访问解密谕言机。(敌手输入的密文不能是挑战密文)(6)敌手输出b,如果b=b,则敌手攻击成功。3从上面的过程中我们可以发现在CCA2的不可区分实验中，敌手可以随时访问解密谕言机，敌手试图通

13、过这些访问的结果来增加自己猜对的可能。正是因为如此,我们要求敌手无法从这些访问的信息中得到挑战密文的任何信息或者得到可忽略的信息。因此，CCA2安全性定义如下：定义2.4.1一个公钥密码体制是CCA2语义安全的，如果对于所有的PPT敌手,都有Vc0wC,Cq#c,有mwM时，函数(pk,sk)-Gen;(mo,mi)A(pk);I1PrIri:b=bJb.0,1)c-Enc(mb);b-A(pk,c)J2是可忽略的。类似的我们可以定义很多密码体制的语义安全性，在这里不多作赘述。第三部分：规约证明这一部分主要介绍如何证明一个密码体制安全性的一种方法一一规约证明。定义3.1所谓规约，其实是复杂性理

14、论中的概念，一个问题P规约到问题P2是指，已经解决问题P的算法Mi,我们能够构造另一个算法M2,M2可以以Mi作为子程序，用来解决问题P2O如果我们将规约的方法运用到密码学领域中的话，则可以达到证明密码体制安全性的目的。我们可以把敌手对密码体制的攻击规约到一个易经得到深入研究的密码本原。即如果敌手能够对该密码体制发动有效的攻击，就可以利用敌手构造一个算法来攻破密码本原，从而得出矛盾。下面我们具体到对密码体制的安全性证明上来讨论规约。假设我们要证明一个密码体制I的安全性，我们可以将体制I规约到体制n上，即如果敌手A能够攻击体制I,则敌手B能够攻击体制n,其中体制n是已经证明安全的，或是一个困难问

15、题，或是一个密码本原。我们可以通过下图来描述两个方案之间的规约3图中挑战者表示建立密码体制的一方,A,B表示敌手。当敌手A能够成功地攻击体制I的时候，敌手B模才AA的挑战者，参考体制n的挑战者对自己的训练去训练敌手A,使A攻破体制I,从中敌手B掌握了如何利用敌手A攻破体制I的方法以及挑战者对自己的训练来攻破体制no任何密码体制规约证明的方法已经成为现代公钥密码学可证明安全性的基础,被提出必须对其进行安全性进行证明。而规约证明的方法则是目前一个非常实用的证明密码体制安全性的方法。下面一个部分我们将看到如何使用规约证明的方法给出一些特殊的密码体制的安全性证明第四部分：一个例子这一部分将通过一个例子

16、说明不可区分性在公钥密码学中的应用。例1.ElGamal加密算法在选择明文（CPA）攻击下的安全性分析日Gamal加密算法：密钥产生：设G是阶为大素数p的群，g为其生成元，即G=ga。随机选择一*.V.x=Zp,计算y=gmodp。以x为秘号钥，（y,g,p）为公开钥。加密(Encx)：设消息mwG,随机选择与p1互素的整数k,计算kkG=gmodp,c2=mymodp密文为c=Ci|C2解密(Decx)：m=c2/c,xmodp在分析其安全性之前，我们首先验证一下加密算法的正确性，即是否满足式子Decx(Encx(m)=m()显然，Q/cxmodp三myk/(gk)x三m(gx)k/(gk)

17、x=m满足()式。下面对其安全性进行分析：日Gamal加密算法的安全性是基于Diffie-Hellman判定性问题：设G是阶为大素数p的群，g1,g2为其生成元。没有多项式时间的算法可以区分以下两个分布： 随机4元组R=(g1,g2,u1,u2)亡64的分布； Diffie-Hellman4元组D=(g1,g2,u1,u2)乏G4的分布，其中5=9；,出=g2,r用。这里对次问题进行变形，我们做代换：g1=g,g2=g1x,u1=gy,u2=gxy,那么上述两个分布变形为： 随机3元组R=(gx,gy,gz)WG4的分布； Diffie-Hellman3元组R=(gx,gy,gxy)wG4的分

18、布。，那么日Gamal加密算法与Diffie-Hellman判定性问题不可区分。原因在于当挑战者与敌手进行CPA不可区分游戏时，敌手输出两个长度相同的消息m0,m1,挑战者加密mb(bw心,1j,得到密文c=G|c2=gkmodp11mbykmodp。如果b=0,则(Gyc/m。)=(gkmodp,gxmodp,gkxmodp)为Diffie-Hellman3元组。如果b=1,则kxkx(GV/mi)=(gmodp,gmodp,gmodp)也为Diffie-Hellman3元组。两者不可区分。不可区分性在公钥密码学中扮演着十分重要的角色，是可证明安全理论的基石，也是证明密码体制或者加密算法在某种意义下安全的必要手段。本文对于不可区分性内容的归纳尚未系统化，有些结论也只是适用于较平凡的情况。比如第四部分的例子中，ElGamal加密算法在CPA意义下已经能够证明是安全的，但是这是基于敌手完全被动的情况，如果敌手能够选择性的发动主动攻击，这个加密算法也是不安全的。例如敌手可以在得到的密文C=G|C2上进行更改，构造出新的密文c=g|c2,其中c2=c2m,解密询问以后得到M=mm,通过计算M/mmodp