《应用密码学》由会员分享,可在线阅读,更多相关《应用密码学(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.,