第13讲--公钥密码3(EIGAMAL)(密码学)

第五章EIGamal体制与椭圆曲线离散对数求模下的整数幂根据欧拉定理，若gcd(a,n)=1,则af(n)≡1modn。考虑一般am≡1modn,如果a,n互素，至少有一个整数m满足这一方程。称满足这一方程的最小正整数m为模n下a的阶。例：a=7,n=19.71≡7mod19,72≡11mod19,73≡1mod19,所以7模19的阶为3。从幂次为4开始出现循环，循环周期与元素的阶相同离散对数定理：设a的阶为m，则ak≡1modn的充分必要条件是k是m的倍数。推论：a的阶整除j(n)。本原根（元）：a的阶m等于j(n)，a为n的本原根。如果a是n的本原根，a1,a2,...,aj(n)在模n下互不相同且与n互素。本原根不唯一。并非所有元素都有本原根，仅有以下形式的整数才有本原根：2，4，pa,2pa,p是奇素数离散对数指标y=ax(a0,a≠1)的逆函数称为以a为底的对数，记为x=logay设p为素数，a是p的本原根，则a0,a1,...,ap-1产生1到p-1中所有值，且每个值只出现一次。对任一b∈{1,…,p-1}，都存在唯一的i(1≤i≤p)，使b≡aimodp。i称为模p下以a为底b的指标，记为i=inda,p(b)离散对数指标的性质1.inda,p(1)=02.inda,p(a)=13.inda,p(xy)=[inda,p(x)+inda,p(y)]modj(p)4.inda,p(yr)=[r×inda,p(y)]modj(p)后两个性质基于下列结论若az≡aqmodp,a和p互素，则z≡qmodj(p)离散对数设p是素数，a是p的本原根。对b∈{1,…,p-1},有唯一的i∈{1,…,p-1},使b≡aimodp。称i为模p下以a为底b的离散对数，记为i≡logab(modp)=inda,p(b)已知a,p,i,求b比较容易，已知a,b,p,求i非常困难EIGamal公钥密码体制设计过程:(1)选取大素数p,再选取的一个本原元a,并将p和a公开.(2)随机选取整数,并计算出并将作为公开的加密密钥,将d作为保密的解密密钥.21:pdd*pZpdmod加解密变换加密变换:,秘密选择一个整数，则密文为其中解密变换:对任意密文明文为*pZm21:pkk**21),(ppZZcccpmcpckkmodmod21**21),(ppZZcccpccmdmod)(112解密正确性证明因为所以因此，解密变换能正确地从密文恢复出相应的明文。ppmcpcdkkmodmodmod21，，)(mod)(mod)()(mod)(mod)(11112pmpmpmpccdkdkdkkd特点在EIGamal公钥密码体制中，密文依赖于明文m和秘密选取的随机整数k，因此，明文空间中的一个明文对应密文空间中的许多不同的密文。实例P=2597,取a＝2，秘密密钥为765，可以计算出公开密钥为y＝2765mod2597＝949。取明文M＝1299，随机数k＝853，则C1＝2853mod2597＝435，C2＝1299×949853mod2597＝2396所以密文为:（C1，C2）＝（435，2396）解密时计算:M＝2396×(435765)-1mod2597＝1299特点(1)密文长度扩展1倍;(2)只利用了有限域的乘法群的性质,即只使用了乘法运算和求乘法逆的运算安全性分析因为该算法是基于有限域上的离散对数问题的，所以p的选取必须足够的大，为150位以上的十进制数，且p－1有大素因子为了加密和签名的安全，k必须是一次性的设计思想(1)利用Diffie-Hellman密钥交换协议生成双方加密用的密钥.此时不同之处在于已将作为公开密钥公布,不需每次发送.(2)采取了一次一密的加密思想.将作为双方交换的密钥,利用它对明文进行加解密.pppdkkdkmodmod)(modpdmodpkmod问题为什么要求?答案:因为的周期为p-1,即备注:(1)参数可以全网公用,也可一人一套;(2)加密不同的明文分组时选用独立的随机数,但秘密的解密密钥需和其版本号一起长期不变.21:pdd1mod1pp实现方法(1)大素数的选择与构造将大素数p选为安全素数,即p=2q+1且q为素数.实验表明,平均100个随机数中可选出1个素数,平均100素数中可选出1个安全素数.(2)安全素数条件下本原元的判断方法由Fermat定理知,即因而如果则有w整除p-1=2q,因而由q是素数知,w只能是2或q.此时本原元等价于且1mod1pp1mod2pq}1mod:0min{ptwt1mod2p1modpq安全素数条件下本原元的构造方法在(p=2q+1)中随机选择一个,若且,则判定是本原元;否则再随机选择另一个进行检验.*pZ1mod2p1modpq习题在用户a对用户b利用RSA公钥密码体制进行消息的加密＋签名时，若二者使用的模数nanb，为了使解密正常进行，应该先加密还是先签名？