RSAElgamalECC加密码体制.ppt

1,产生密钥对 选择两个大素数p,q, pq 计算n=pq,(n)=(p-1)(q-1) 选择整数e,使得gcd(e,(n)=1 计算d e-1 mod (n) 公钥: KU=e,n, 私钥: KR=d,n 使用 加密: C = Me mod n 解密: M = Cd mod n,RSA加密过程：,2,例子： 选p7，q17 则npq119 且(n)(p-1)(q-1)61696 取e5 则d77 (57738549611 mod 96) 公钥（5，119），私钥（77，119） 加密m19 则cme mod n= 195 mod 119 = 66 mod 119 解密c66 mcd mod n = 6677mod 11919 mod 119,3,再例：p = 53，q = 61，n = pq = 3233， (n)52x60 = 3120 令d = 791，则e = 71 令m = RE NA IS SA NC E 即m = 1704 1300 0818 1800 1302 0426 170471 mod 3233 = 3106 mod 3233， C = 3106 0100 0931 2691 1984 2927,4,RSA总结：,找素数 选取两个大的随机的素数p，q（采用Miller-Rabin概率测试方法） 计算模n和Euler函数(n)， npq (n)=(p-1)(q-1) 找ed1 mod (n) 随机取一个数e(与(n)互素)，用扩展Euclid算法求d即可 发布 d保密，(d, n)是私钥 KU 发布(e,n)，这是公钥KR 销毁p、q 注意： 选择足够大的n(1024位以上),并且使得e,d之间相差不太大,也不太小，防指数攻击。,5,RSA的低指数攻击,令三用户的加密钥e均选3，而有不同的模n1, n2, n3，若有一用户将消息m传给三个用户的密文分别为 y1=m 3 mod n1 , m n1 y2=m 3 mod n2 , m n2 y3=m 3 mod n3 , m n3 一般选n1, n2, n3互素(否则，可求出公因子，而降低安全性)，利用中国余定理，可从y1, y2, y3求出 m 3 mod (n1 n2 n3)。 由mn1, mn2, mn3，可得m3 n1 n2, n3，故通过开立方可求m。,6,计时攻击,Timing Attacks on Implementations of DH, RSA, DSS, and Other Systems，1994，Paul C. Kocher,1995年有人提出了一种非常意想不到的攻击方式：假如攻击者对加密者的硬件有充分的了解，而且知道它对一些特定的消息加密时所需要的时间的话，那么她可以很快地推导出d。这种攻击方式之所以会成立，主要是因为在进行加密时所进行的模指数运算是一个位元一个位元进行的，而位元为1所花的运算比位元为0的运算要多很多，因此若能得到多组讯息与其加密时间，就会有机会可以反推出私钥的内容。,可研究，类似于ECC中的旁道攻击，它们是利用硬件实现的特征进行。,7,ElGamal密码体制,密钥产生过程 选择一个素数p，以及GF(p)的本原元g(g p), xp,计算公钥 ygx mod p, =(y,g,p)为公钥，x为私钥 加密过程 M是发送明文组，选择随机数k，且(k,p1)=1，计算： C1=g k mod p (随机数k被加密) C2=Myk mod p(明文被随机数k和公钥加密) 密文由C1、C2级连构成，即密文C=C1|C2。 解密过程 M=C2/C1x=My k/gkx=Mgxk/gkx mod p,8,例：p = 17，g = 3，xA = 2，xB = 5，m = 11，m从A发送到B，A选择k = 7. 求：密文(c1, c2)并解密 加密：YA = gxA mod P = 32 mod 17 = 9 YB = gxB mod P = 35 mod 17 = 5 K = (YB)k mod P = 57 mod 17 = 10 c1 = gk mod P = 37 mod 17 = 11 c2 = mK mod P = 11 10 mod 17 = 8 所以，密文C = (c1, c2) = (11, 8) 解密：K = c1xB mod P = 115 mod 17 = 10 c2 = mK mod P = 10m mod 17 = 8 m = c2/K mod P = c2K-1 mod P K K-1 mod P = 1，即10 K-1 mod 17 = 1，得K-1 = 12 所以，明文m = c2K-1 mod P = 8x12 mod 17 = 11,9,椭圆曲线密码体制 -加密体制,10,椭圆曲线加密-ECES 1、系统的建立,选取: 一个基域GF(p) 定义在该基域上的椭圆曲线Ep(a,b)： E上的一个拥有大素数阶n的点P 其中有限域GF(p) 、椭圆曲线参数a,b、点P和阶n都是公开信息,11,2、密钥的生成,在区间1,n-1中随机选取一个整数d作为私钥。 计算公钥:Q=d*P 公开密钥:Q（椭圆曲线上的一个点） 而私钥d保密。,12,3、加密过程,待发送消息：AliceBob:M。过程如下： 查找Bob的公开密钥：Q 将消息M表示成一个域元素:m 在区间1, n-1中随机选取一个整数k 计算点:(x1,y1)=kP 计算点:(x2,y2)=kQ，如果x2=0，则返回第(3)步 计算:c=mx2 传送加密数据(x1, y1, c)给Bob,13,4、解密过程,当实体Bob解密从Alice收到的密文(x1, y1, c)