《应用密码学》由会员分享，可在线阅读，更多相关《应用密码学（64页珍藏版）》请在金锄头文库上搜索。
1、ElGamal算法,1,主要内容,EIGamal公钥密码算法,2,EIGamal算法的安全性证明,3,基础知识,1,基础知识,1,公钥密码,定义1 公钥加密算法是如下多项式时间算法(Gen,Enc,Dec)的三元组：,(2) 加密算法Enc:输入公钥pk和来自某个明文空间的一个消息m，输出密文c，记为 。,(3) 解密算法Dec:输入私钥sk和密文c，输出消息m或一个定义为失败的特殊符号 。记为 。,基础知识,(1) 密钥生成算法Gen：输入安全参数1n，输出一对密钥(pk,sk)。pk是公钥，sk是私钥。假设pk和sk的各自长度至少是n。,给定一个公钥密码方案 ，敌手 进行窃听不可区分实验
2、：,窃听不可区分实验,方案执行者 （模拟者）, , =b,实验输出1；否则，输出0.,(1) 执行Gen(1n)，获得(pk,sk)。,(2) 敌手被给予pk, 输出一对相同长度的消息 , （消息必须在与pk相关的明文空间中）。,(3)随机选择, ，然后计算= ( )并且给，称 为挑战密文。,窃听不可区分实验,(4) 输出一位 。,(5) 如果= ,实验输出1，否则输出0。,A可以自由访问加密机,基础知识,定义2 如果对于所有概率多项式时间的敌手 存在可忽略函数negl，满足则公钥加密方案 在窃听者存在情 况下具有不可区分加密。,给定一个公钥密码方案 ，敌手 进行CPA不可区分实验 ：,方案执
3、行者 （模拟者）, , =b,实验输出1；否则，输出0.,CPA不可区分实验,(1) 执行Gen(1n)，获得(pk,sk)。,(2) 敌手被给予pk, A可以自由访问加密机, 输出一对相同长度的消息 , 。 。,(3)随机选择, ，然后计算= ( )并且给，称 为挑战密文。,CPA不可区分实验,(4) 继续访问加密机，输出一位 。,(5) 如果= ,实验输出1，否则输出0。,基础知识,定义3 如果对于所有概率多项式时间的敌手 存在可忽略函数negl，满足则公钥加密方案 在选择明文攻击 条件下具有不可区分加密。,命题1 如果一个公钥加密方案，在窃听者存在的情况下具有不可区分加密，则在选择明文攻
4、击下也具有不可区分加密。,基础知识,A拥有pk, 等价于A拥有加密预言机！,对称密码算法不具有上述安全等价性！,小结： 窃听攻击条件下的密文不可区分安全性 选择明文攻击条件下的密文不可区分安全性 两者的等价性,基础知识,完美安全的密码方案:,从密文不可区分性的角度 给出完美安全的公钥密码方案的定义！,基础知识,完美安全:,密文不可区分:,基础知识,引理 明文空间为M的加密方案是完全保密的， 当且仅当对于任意M上的概率分布，每个 , 以及每个 ,有,基础知识,(必要条件)已知该方案是完全保密的，即,根据引理1，得到 ,可以得到：对于每个 ,以及每个 ,有：,基础知识,定理1 对于任何敌手 满足的
5、公钥密码方案称为完美安全的公钥密码方案。,任何敌手：假设敌手具有无限的存储资源和计算资源！,完美安全的公钥密码： 已知公钥和加密算法，明文m0,m1, 具有无限资源的敌手无法区分挑战密文对应的明文是m0,还是m1.,存在完美安全的公钥加密方案吗？,基础知识,不存在！,确定性的公钥加密方案：密钥相同的条件下，相同 的消息对应相同的密文。,概率性公钥加密方案：密钥相同的条件下，相同的 消息对应不同的密文。,基础知识,确定性的公钥加密方案容易受到攻击，因此不应使用。,基础知识,练习：假定一个确定性公钥加密方案用来加密消息m，该消息来自于一个具有L个可能值的小集合。 如何在关于L的线性时间里确定m(假
6、设加密 一个元素耗费一个单元时间),基础知识,定理1：在窃听者存在的情况下，没有一种确定性的公钥加密方案具有不可区分性。,小结： 完美安全的另一种描述方式：密文的完美不可区分 不存在完美安全的公钥密码方案（由于已知条件太多！） 确定性公钥密码算法（如RSA）（不具有不可区分性！），概率性公钥密码算法（如EIGamal）现实生活中，应使用概率公钥密码算法！,EIGamal公钥密码算法,2,公钥密码,定义：G是阶为q的循环群，g是其生成元，即= , , , ，已知 ，求满足 h= 的唯一，就是上的离散对数问题。,离散对数问题,注：q可以是素数，也可以是合数。,EIGamal公钥密码算法, 输入1n
7、，输出(G, , )， 为G的生成元，, 选取x，满足0x，计算h= ，（G,q,g,h)是公钥，x是私钥。,Gen(1n):,EIGamal公钥密码算法,EIGamal算法的安全证明,3,公钥密码,1,数学困难问题,DDH困难性问题： 给定（, , ,） , 判决 T 是否等于 , 若 = ,输出1，否则输出0。,1,数学困难问题,DDH困难性假设： 如果对任意概率多项式时间算法， 存 在一个可忽略函数negl，满足P , , , =P , , , = (),注：上述不等式的意思是判决优势可忽略！,判决优势和判决正确的概率之间的关系是什么？,2,安全性证明,定理 如果DDH问题是困难的，则E
8、lGaml加密方案在选择明文攻击情况下是不可区分的加密(在CPA模型下是安全的)。,安全目标？ 选择明文攻击下不可区分加密,2,安全性证明,安全模型？ 选择明文攻击实验,数学困难问题？ DDH问题,证明方法？ 反证法。如果存在多项式时间算法以不可忽略 的优势区分挑战密文，则存在多项式时间算法 以不可忽略的优势解决DDH问题。,2,安全性证明,得到想要的结论：由于DDH问题是困难的，因此密文是不可区分的，因此算法具有密文不可区分安全性！,算法的模拟者是为了解决DDH问题。拥有DDH问题 的已知信息（ , , , ）. 模拟者构造一个EIGamal算法（一个与EIGamal算 法无法区分的算法），
9、攻击者的目的是区分挑战密文。,2,安全性证明,模拟者利用攻击者的判决结果给出自己的判决结果！ 模拟者利用攻击者！,证明：,ElGamal方案在选择明文条件下不可区分， 即需要证明,2,安全性证明,令 表示ElGaml加密方案，令 为多项式时间的敌手， 并且定义,证明：,2,安全性证明,模拟者已知 , , , 。 模拟ElGaml算法，令 PK= ， 得到 .,是如何利用 解决DDH问题呢？,证明：,2,安全性证明,(1)模拟者将的公钥h= 给，向加密预言机问询 m，模拟者随机选取0,q-1 ，计算密文 ( , ( ) )返回给。,(2)选取两个等长的消息( 0 , 1 )给模拟者,(3) 随机
10、选择 0,1 ，将挑战密文 =( ,) 给。,(4)继续查询加密预言机；,(5)给出判决结果 。,(6)判断 是否等于b，若相等输出1，否则输出0。,若在多项式时间内以()( 1 2 +() 的概率将挑战密文区分开，则能在多项式时间解决DDH问题,即,P , , , = P , , , = (),2,安全性证明,针对模拟的EIGamal算法，只有当 = ， 才是一个与真实算法不可区分的算法。 此时：,假设 ，则 ，即,这与DDH问题的困难假设是矛盾的，因此， ， 即ElGaml算法在CPA模型下可证明安全的。,2,安全性证明,小结 DDH问题 判决优势和判决正确的概率 EIGamal算法的安全
11、性证明思路 密文区分正确的概率和DDH问题的区分优势之间的概率,EIGamal算法实现方面的问题,4,公钥密码,两个问题： 1. 寻找大素数p 2. 寻找生成元g,p是大素数，G=1,2,p-1时，生成元g的个数= 1 个。,参数的选取问题,寻找大素数： Rabin素性检测算法生成大素数！,理论基础： （费马定理）若N为素数，则对任意的整数,12, 1 =1 即|( 1 1),设N1= 2 1 1= 2 1= 2 1 1 2 1 +1 = 1 =0 1 2 +1,|( 1 1)即:| 1 或i0,1,s1,满足 | 2 +1 。,Rabin素性检测算法,令 = : 1 且对于i0,1,s1,满
12、足 2 +1 . 是0,1,N-1中与N互素的元素构成的集合。,Rabin算法： (1) 任取一个大奇数N； (2) 任取一个正整数1aN; (3) 如果gcd(a,N)=1且 ,则称N通过一次测试，则N可能是素数；否则，N必定为合数。重复上述步骤(2),(3)，任意选择不同的共次，进行测试。,Rabin素性检测算法,重复k次上述步骤(2),(3)，判定N为素数的误判概率小于等于 (1/4) .,Pr判定为素数|是合数1/4,问题： 怎样找生成元？,输入：群G 的阶为q, q的素因子 1 , . 输出：判定是否为的生成元。 for i=1 to kif =1 判定“不是一个生成元” 判定“是一个生成元”。,2.令p是一个强素数，即q=(p-1)/2也是一个素数。二次剩余模p的集合构成一个模乘法群G，其阶为q.,
