RSA Elgamal ECC加密码体制.ppt

文档介绍：1
产生密钥对
选择两个大素数p,q, pq
计算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
例子:
选p=7,q=17
则n=pq=119
且φ(n)=(p-1)(q-1)=6×16=96
取e=5
则d=77 (5×77=385=4×96+1≡1 mod 96)
公钥(5,119),私钥(77,119)
加密m=19
则c=me mod n= 195 mod 119 = 66 mod 119
解密c=66
m=cd mod n = 6677mod 119=19 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),
n=pq
φ(n)=(p-1)(q-1)
找ed≡1 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)。由m<n1, m<n2, m<n3,可得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的运算要多很多,因此若能得到多组讯息与其加密时间,就会有机会可以反推出私钥的内容。
可研究,中的旁道攻击,它们是利用硬件实现的特征进行。
7
ElGamal密码体制
密钥产生过程
选择一个素数p,以及GF(p)的本原元g(g <p), x<p,计算公钥 ygx mod p, =(y,g,p)为公钥,x为私钥
加密过程
M是发送明文组,选择随机数k,且(k,p-1)=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,即