公钥加密算法和RSAppt课件.pptx
计算机信息安全,第4章公钥密码学与RSA,(1) 加密与解密由不同的密钥完成。 加密 XY: Y=EKU(X)；解密 YX: X=DKR(Y) =DKR(EKU(X)。 (2) 知道加密算法、加密密钥，得到解密密钥在计算上是不可行的。 (3) 两个密钥中任何一个都可以用作加密，而另一个用作解密(不是必 须的)，即 X=DKR(EKU(X) =EKU(DKR(X)。,(1) 密钥管理困难 两两通信分别需用一个密钥，因此n个用户需要 C(n,2)=n(n-1)/2个密钥，用户增大时,所需密钥量急增。 如: n=100 时，C(100,2)=4995个； n=5000时，C(5000,2)=12497500个。(2) 需要约定密钥 密钥要预先通过某一秘密信道进行协商，对这个信 道安全性要求比正常传送消息的信道安全性要高。(3) 数字签名问题 传统加密算法无法实现抗抵赖的需求。,对称算法的不足,应用范围：(1) 加密/解密；(2) 数字签名(身份鉴别)；(3) 密钥交换。, 涉及各方：发送方、接收方、攻击者。 涉及数据：公钥、私钥、明文、密文。 公钥算法应满足的条件： 产生密钥对在计算上是可行的； 已知公钥和明文，产生密文在计算上是可行的； 接收方利用私钥来解密密文在计算上是可行的； 对于攻击者，利用公钥来推断私钥在计算上是不可行的； 已知公钥和密文，恢复明文在计算上是不可行的； (可选)加密和解密的顺序可交换。,对公钥密码的要求,公钥密码体制的应用,单向陷门函数是满足下列条件的函数f：(1) 给定x，计算y=fk1(x)是容易的；(2) 给定y, 计算x使x=fk1-1(y)是不可行的；(3) 存在k2，已知k2时，对给定的任何y，若相应的x存在，则计算x使fk21(y) 是容易的。, 大整数分解问题（The Integer FactorizationProblem, RSA体制）。 离散对数问题 有限域的乘法群上的离散对数问题(The Discrete Logarithm Problem, ElGamal体制）。 定义在有限域的椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem, 类似ElGamal体制）。, 1977年由Ron Rivest、Adi Shamir和Len Adleman发明，1978年公布。, RSA是一种分组加密算法，明文和密文在0n-1之间，n是一个正整数。 应用最广泛的公钥密码算法。 只在美国申请专利，已于2000年9月到期。, 分组大小为k比特, 2k n 2k+1。 公开密钥n, e，其中n为两个素数p和q的乘积(推荐p、q等长), e与(p-1)(q-1)互素,且满足 ed1 (mod(p-1)(q-1)。 私有密钥n,d，d满ed1 (mod(p-1)(q-1)，即d与e关于模(p-1)(q-1) ) 互逆。 加密算法 c me mod n，这里m为明文、n与e为加密密钥。 解密算法 m cd mod n ，这里c为密文、n与d为解密密钥。,公钥密码RSA的理论基础是大素数相乘和因子分解可以被看成一个单向函数。, 用户Alice产生两个大素数p和q，pq。 Alice计算n=pq， n的Euler数(n)=(p-1)(q-1)。 Alice选择随机数e，(0e (n) )，使gcd(e, (n)=1。 Alice使用Euclidean算法计算d e1 mod (n)。 Alice使用RSA时的公开密钥为 KU=n,e，秘密密钥为 KR=n,d。, RSA的公开密钥为 KU=n,e，秘密密钥为 KR=n,d。 选好这些参数后，将明文划分成块，使每个明文报文P长度m满 足0mn。 加密P时，计算C Pe mod n。 解密C时，计算P Cd mod n。 由于模运算的对称性，可以证明，在确定的范围内，加密函数和解 密函数是互逆的。,RSA公开加解密体制, RSA的公开密钥为 KU=n,e，秘密密钥为 KR=n,d。 选好这些参数后，将明文划分成块，使得每个明文报文x长度 m满足0mn。 签名P时，计算y=Sig(x)=xd (mod n)。 验证签名时，计算x ye (mod n) ?= x。,RSA公钥密码的正确性,RSA签名,Fermat定理 p是素数，a是整数且不能被p整除，则ap11 mod p。Fermat定理推论 p素数，a是任意整数，则apa mod p。Euler定理 若a与n为互素的正整数,则a(n)1 mod n。Euler定理推论1 若n=pq，pq都是素数，k是任意整数，则m(p-1)(q-1)+1m mod n，对任意0mn。Euler定理推论2 mk(p-1)(q-1)+1m mod n, 对任意0mn。因为ed1 mod (n), 那么存在一个k使ed=1+k(n)。故,RSA应用实例,步骤1. 随机选择二个互不相同的素数；(一般采用概率测试算法) 如 p=17，q=11；步骤2. 计算模数 n = pq = 1711=187；步骤3. 计算Euler数 (n) = (p1)(q1) = 1610 = 160;步骤4. 随机选择一个满足 gcd(e,(n)=1 的参数e； 选择 e=7，满足 gcd(e,160) = 1；步骤5. 确定满足de1 mod (n) 的参数值d；(采用欧几里德算法) 本例中 (e,160)=(7,160)=1 由于160 = 227+6，7 = 16+1 7 = 1(160227)+1 = 1160227 +1, 即1160+23 7 = 1 所以 2371 mod 160，得 d=23 满足d 160 且 de 1 mod 160 。步骤6. 公开密钥 KU = 187,7；步骤7. 秘密密钥 KR = 187,23。 通过以上计算，已建立起RSA应用实例。,对任意整数a,b,k，gcd(a,b)=gcd(b, a+kb)=gcd(b, a mod b)例如 gcd(55,22)=gcd(22, 55mod22)=gcd(22,11)=11Eclid算法求最大公约数(d,f)。 假定df0，则Step1. Xd, Yf；Step2. if Y=0 then return X=gcd(d,f)；Step3. RX mod Y；Step4. XY；Step5. YR；Step6. 转Step2。上述的循环最多进行2log2(max(f,d)次。,实例,ExtEclid(d,f)：求最大共约数或模逆, 假定df0。1. (X1,X2,X3)(1,0,f)，(Y1,Y2,Y3)(0,1,d)；2. if Y3 = 0 then return X3=gcd(d,f), no inverse；3. if Y3 = 1 then return Y3=gcd(d,f)，Y2=d-1mod f；4. Q(X3/Y3)的整数部分；5. (T1,T2,T3)(X1QY1, X2QY2, X3QY3)；6. (X1,X2,X3)(Y1,Y2,Y3)；7. (Y1,Y2,Y3)(T1,T2,T3)；8. goto 2。fX1+dX2=X3，fY1+dY2=Y3；若Y3=1，则fY1+dY2=1 dY2=(Y1)f+1 dY2 1 mod f Y2 = d1 Mod f,RSA加解密实例,针对上述 RSA应用实例，若给定明文消息M = 88( 88187)，则(1) 加密M的计算过程为 C 887 mod 187 (881 mod 187)( 882 mod 187 )(884 mod 187) mod 187 由于 (881 mod 187) 88 (882 mod 187) ( 881 mod 187 ) (881 mod 187) mod 187 7744 mod 187 = 77 (884 mod 187) = ( 882 mod 187 ) (882 mod 187) mod 187 = 5929 mod 187 = 132 所以 C = 887mod 187 = (8877132) mod 187 = 894432 mod 187 = 11；(2) 解密C的计算过程为 M = 1123 mod 187 = (111 mod 187)( 112 mod 187 ) (114 mod 187)(118 mod 187) (118 mod 187) mod 187 = (1112155 3333) mod 187 = 79720245 mod 187 = 88。,模乘性质 (a b mod n) = (a mod n)(b mod n) mod n。,计算a16=aaaaaaaaaaaaaaaa，采用一般方法需15次乘法，若计算a2、a4、a8、a16，则只需4次乘法。,90年代大数分解的进程,RSA的安全性是基于加密函数ek(x)=xe (mod n)是一个单向函数，所以,对攻击者来说,求逆计算不可行。,RSA安全性依据,对RSA实现的攻击,对RSA的具体实现存在一些攻击方法，但不是对基本算法的，而是针对协议的。 对RSA的选择密文攻击； 对RSA的公共模攻击； 对RSA的小加密指数攻击； 对RSA的小解密指数攻击； 时间性攻击：取决于解密算法的运算时间。,RSA-155的分解,1999年8月22日，荷兰H.Riele领导的来自6个国家的研究人员组成的团队,用了5个月时间（计算机时间估计为8000mips years）找到了一个512-bit RSA密钥n的一个素因子。, 用户拥有自己的密钥对(KU,KR)。 公钥KU公开，私钥KR保密。 AB: Y=EKUb(X)。 B: DKRb(Y)= DKRb(EKUb(X)=X。, 条件 两个密钥中任何一个都可以用作加密而另一个用作解密。 鉴别 AALL：Y=DKRa(X)； ALL：EKUa(Y)=EKUa(DKRa(X)=X。鉴别+保密 AB：Z= EKUb(DKRa(X)； B：EKUa(DKRb(Z)=X。,END,
