RSA公钥密码体制创新课件

RSA公钥密码体制公钥密码体制e_mail: yongzhe .cn电话：电话：公钥密码体制的基本概念公钥密码体制的基本概念 公钥密码体制的概念是在解决对称密码体制中最难解决的两公钥密码体制的概念是在解决对称密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配和数字签字。个问题时提出的，这两个问题是密钥分配和数字签字。 对称密码体制在进行密钥分配时，要求通信双方已经有了一对称密码体制在进行密钥分配时，要求通信双方已经有了一个共享的密钥，或者可籍助于一个密钥分配中心临时分配会个共享的密钥，或者可籍助于一个密钥分配中心临时分配会话密钥。对第一个要求，常常可用人工方式事先传送双方最话密钥。对第一个要求，常常可用人工方式事先传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。 第二个问题数字签字考虑的是如何为数字化的消息或文件提第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。供一种类似于为书面文件手书签字的方法。 1976年年W.Diffie和和M.Hellman对解决上述两个问题有了突破对解决上述两个问题有了突破，从而提出了公钥密码体制，从而提出了公钥密码体制。公钥密码体制的原理公钥密码体制的原理 公钥密码算法的最大特点是采用两个相关密钥将公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称为公开密钥，简称公钥公钥，用于加密；另一个密钥是，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称为用户专用，因而是保密的，称为秘密密钥，简称私钥私钥，用于解密。因此公钥密码体制也称为双钥密，用于解密。因此公钥密码体制也称为双钥密码体制或非对称密码体制。码体制或非对称密码体制。算法有以下重要特性：算法有以下重要特性：已知密码算法和公钥，求解私钥在计算上不可行。已知密码算法和公钥，求解私钥在计算上不可行。用公钥加密的消息只能用与之对应的私钥来解密。用公钥加密的消息只能用与之对应的私钥来解密。加密和解密操作在计算上可快速执行。加密和解密操作在计算上可快速执行。公开密钥体制用于加密的原理公开密钥体制用于加密的原理加密加密c=EPKB(m) 解密解密m=DSKB(c)公钥密码体制用于认证的原理公钥密码体制用于认证的原理签名：签名：s=ESKA(m) 验证签名：验证签名：m=DPKA(s)公钥密码算法应满足的要求公钥密码算法应满足的要求公钥密码算法应满足以下要求公钥密码算法应满足以下要求: 接收方接收方B产生密钥对产生密钥对(PKB,SKB)在计算上是容在计算上是容 易的。易的。 发方发方A用接收方用接收方B的公钥对消息的公钥对消息m加密以产加密以产 生密文生密文c，即，即c=EPKB(m)在计算上是容易的。在计算上是容易的。 接收方接收方B用自己的私钥对密文用自己的私钥对密文c进行解密，即进行解密，即 m=DSKB(c)在计算上是容易的。在计算上是容易的。公钥密码算法应满足的要求公钥密码算法应满足的要求 敌手由敌手由B的公钥的公钥PKB求其私钥求其私钥SKB在计算上在计算上 是不可行的。是不可行的。 敌手由密文敌手由密文c和和B的公钥的公钥PKB恢复明文恢复明文m在计在计 算上是不可行的。算上是不可行的。 加、解密次序可换，即加、解密次序可换，即DSKB(EPKB(m) =EPKB(DSKB(m) 其中最后一条虽然非常有用，但不是对所其中最后一条虽然非常有用，但不是对所有的算法都作要求。有的算法都作要求。公钥密码算法应满足的要求公钥密码算法应满足的要求以上要求的本质之处在于要求一个以上要求的本质之处在于要求一个单向陷门函数单向陷门函数。称一个函数是单向陷门函数，是指该函数是易于计算的，但求称一个函数是单向陷门函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成。定后，求逆可在多项式时间完成。总结为：单向陷门函数是一族可逆函数总结为：单向陷门函数是一族可逆函数ft，满足：，满足： Y=ft(X)易于计算（当易于计算（当ft和和X已知时）。已知时）。 X=ft-1(Y)在计算上是不可行的（当在计算上是不可行的（当Y、ft已知，但已知，但t未知时）。未知时）。 X=ft-1(Y)易于计算（当易于计算（当Y、ft 、t 均已知时）。均已知时）。因此，实现公钥密码的核心就是寻找合适的单向陷门函数。因此，实现公钥密码的核心就是寻找合适的单向陷门函数。RSA算法算法 RSA算法是算法是1978年由年由R.Rivest, A.Shamir和和L.Adleman提出的提出的一种用数论构造的公钥密码体制，该体制已得到广泛的应用。一种用数论构造的公钥密码体制，该体制已得到广泛的应用。RivestShamirAdleman2002 Turing Award (June03)RSA的数论基础的数论基础算法描述算法描述 密钥的产生密钥的产生 秘密选取两个大素数秘密选取两个大素数p和和q。 计算计算n=pq，(n)=(p-1)(q-1),其中其中(n)是是n的欧拉函数值。的欧拉函数值。 选一整数选一整数e，满足，满足1e(n)，且，且gcd(n),e)=1。 计算计算d，满足，满足de1 mod (n),即即d是是e在模在模(n)下的乘法逆元，因下的乘法逆元，因e与与(n)互素，由模互素，由模运算可知，它的乘法逆元一定存在。运算可知，它的乘法逆元一定存在。 以以e,n为公开钥为公开钥,d,n为秘密钥。为秘密钥。算法描述算法描述 加密加密 加密时首先将明文比特串分组，使得每个分组对应加密时首先将明文比特串分组，使得每个分组对应的十进制数小于的十进制数小于n，即分组长度小于，即分组长度小于log2n。然后对。然后对每个明文分组每个明文分组m，作加密运算：，作加密运算： cme mod n算法描述算法描述 解密解密对密文分组的解密运算为：对密文分组的解密运算为： mcd mod nRSA 的单向陷门函数的单向陷门函数 参数参数:N=pq. N 1024 bits. p,q 512 bits.e 加密指数加密指数 gcd(e, (N) ) = 1 . 单向函数单向函数: RSA(M) = Me (mod N) 其中其中 M ZN* 陷门陷门:d 解密指数解密指数.其中其中 e d = 1 (mod (N) ) 解密解密:RSA(M)d = Med = Mk (N)+1 = M (mod N)因子分解问题因子分解问题 三种数学攻击方法三种数学攻击方法 分解分解 N=p.q, 因此可计算出因此可计算出 (N)，从而确定，从而确定d 直接确定直接确定(N)，然后找到，然后找到d 直接确定直接确定d 大家相信：由大家相信：由N确定确定(N)等价于因子分解等价于因子分解举例举例选选p=7，q=17。求求n=pq=119，(n)=(p-1)(q-1)=96。取取e=5，满足，满足1e(n)，且，且gcd(n),e)=1。确定满足确定满足de=1 mod 96且小于且小于96的的d，因为，因为775=385=496+1，所以，所以d为为77，因此公开钥为因此公开钥为5，119，秘密钥为，秘密钥为77，119。设明文设明文m=19，则由加密过程得密文为，则由加密过程得密文为c195 mod 1192476099 mod 11966解密为解密为6677mod 11919计算问题：加密与解密过程中的指数运算计算问题：加密与解密过程中的指数运算求求am可如下进行，其中可如下进行，其中a，m是正整数：是正整数： 将将m表示为二进制形式表示为二进制形式bk bk-1b0，即，即m=bk2k+bk-12k-1+b12+b0因此因此12012222kkkbbbbbmaaaaaa 例题例题19=124+023+022+121+120，所以，所以a19=(a1)2a0)2a0)2a1)2a1例题例题例例4.9 求求7560 mod 561。将将560表示为表示为1000110000，算法的中间结果如表所示。所以，算法的中间结果如表所示。所以7560 mod 561=1。i9876543210bi1000110000c01248173570140 280 560d1749157 526160241 298 166 671例题例题计算计算551 mod 97计算问题：密钥的产生中的计算问题计算问题：密钥的产生中的计算问题 寻找大素数寻找大素数 如何选取满足如何选取满足1e(n)和和gcd(n),e)=1的的e，并计，并计算满足算满足de1 mod (n)的的d。这一问题可由推广的。这一问题可由推广的Euclid算法完成。算法完成。例题例题已知已知 RSA公钥加密方案中公钥加密方案中 p=29 q=67 n=1943 e=701 m=23求密文求密文例题例题已知已知 RSA公钥加密方案中公钥加密方案中 p=29 q=67 n=1943 e=701 c=1926求明文求明文RSA中参数的选择：密钥长度中参数的选择：密钥长度 估计在未来一段比较长的时期，密钥长度介于估计在未来一段比较长的时期，密钥长度介于1024比特至比特至2048比特之间的比特之间的RSA是安全的。是安全的。NIST:Cipher key-sizeModulus size 56 bits 512 bits. 80 bits 1024 bits 112bits 2048 bits 128 bits 3072 bits 192 bits 7680 bits 256 bits (AES)15360 bits RSA中参数的选择：中参数的选择：p和和q的选择的选择（1） |p-q|要大要大（2） p-1和和q-1都应有大素因子都应有大素因子强素数强素数强素数是满足如下条件的安全素数强素数是满足如下条件的安全素数: p - 1 和和q- 1 的最大公因子应该较小的最大公因子应该较小, p + 1 和和q+ 1 都应有都应有大的素因子大的素因子, p - 1 和和q- 1 都应有大的素因子都应有大的素因子, 分别分别记为记为p 和和q, p - 1 和和q- 1 都应有大的素因子。都应有大的素因子。强素数可以大大增强其抗穷举攻击和因子分解攻击的强素数可以大大增强其抗穷举攻击和因子分解攻击的强度强度例题例题3999991是两个素数的乘积，那么较大的素数是？是两个素数的乘积，那么较大的素数是？例题例题已知已知RSA算法中算法中n=323, (n)=288求求p,q例题例题某一用户，在某一用户，在RSA算法使用过程中，暴露了私钥，其算法使用过程中，暴露了私钥，其不改变模，而只改变公钥和私钥，问这样安全吗？不改变模，而只改变公钥和私钥，问这样安全吗？例题例题 Bob的的 RSA 模数为模数为 n = pq， p q 为不同的大素数为不同的大素数. 他的公开密钥是他的公开密钥是e. Alice 发送发送 Bob 对消息对消息m加密后加密后的密文的密文 c me (mod n). Bob 在对消息解密之后在对消息解密之后, Bob 通知通知 Eve 消息具有这样的特性：消息具有这样的特性：m12345 1 (mod n). Eve 已知已知 n; e; c, 但是不知道但是不知道 p; q;m. 但但Eve可以根据可以根据Bob 提示信息发现消息提示信息发现消息 m. 说明说明Eve是如何得到是如何得到 m的的. The Extended Euclidean AlgorithmExample 1: m = 65; n = 40Step 1: The (usual) Euclidean algorithm:(1) 65 = 1 40 + 25(2) 40 = 1 25 + 15(3) 25 = 1 15 + 10(4) 15 = 1 10 + 510 = 2 5Therefore: gcd(65; 40) = 5.Step 2: Using the method of back-substitution:(4)5 =15 - 10(3) = 15 - (25 - 15) = 2 15 - 25(2) = 2(40 - 25) - 25 = 2 40 - 3 25(1) = 2 40 - 3(65 - 40) = 5 40 - 3 65Conclusion: 65(-3) + 40(5) = 5.对对RSA的攻击：共模广播攻击的攻击：共模广播攻击 在实现在实现RSA时，为方便起见，可能给每一用户相同的模数时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。，虽然加解密密钥不同，然而这样做是不行的。 设两个用户的公开钥分别为设两个用户的公开钥分别为e1和和e2，且，且e1和和e2互素（一般情互素（一般情况都成立），明文消息是况都成立），明文消息是m，密文分别是，密文分别是 c1me1(mod n) c2me2(mod n) 敌手截获敌手截获c1和和c2后，可按如下方法恢复后，可按如下方法恢复m。 用推广的用推广的Euclid算法求出满足算法求出满足 re1+se2=1 的两个整数的两个整数r和和s，其中一个为负，设为，其中一个为负，设为r。再次用推广的。再次用推广的Euclid算法求出算法求出c-11，由此得，由此得(c-11)-rcs2m(mod n)。例题例题user1n1,e1=299,3user2n2,e2=299,5某用户传递给二个用户相同的消息某用户传递给二个用户相同的消息m, 密文分别为密文分别为129，205问：攻击者是否可以据此得出明文问：攻击者是否可以据此得出明文对对RSA的攻击：低指数广播攻击的攻击：低指数广播攻击假定将假定将RSA算法同时用于多个用户（为讨论方便，以算法同时用于多个用户（为讨论方便，以下假定下假定3个），然而每个用户的加密指数（即公开钥个），然而每个用户的加密指数（即公开钥）都很小。设）都很小。设3个用户的模数分别为个用户的模数分别为ni(i=1,2,3)，当，当ij时，时，gcd(ni,nj)=1，否则通过，否则通过gcd(ni,nj)有可能得有可能得出出ni和和nj的分解。的分解。设明文消息是设明文消息是m，密文分别是，密文分别是c1m3(mod n1)c2m3(mod n2)c3m3(mod n3)由中国剩余定理可求出由中国剩余定理可求出m3(mod n1n2n3)。由于。由于m3n1n2n3，可直接由，可直接由m3开立方根得到开立方根得到m。例题例题user1n1,e1=319,3user2n2,e2=299,3user2n3,e3=323,3某用户传递给三个用户相同的消息某用户传递给三个用户相同的消息m, 密文分别为密文分别为80，235，121问：攻击者是否可以据此得出明文问：攻击者是否可以据此得出明文教科书教科书 RSA 教科书教科书 RSA 加密加密: 公钥公钥: (N,e) 加密加密: C = Me (mod N) 私钥私钥: d 解密解密: Cd = M (mod N) (M ZN* )对教科书对教科书 RSA的一种攻击的一种攻击 Session-key K is 64 bits. View K 0,264Eavesdropper sees: C = Ke (mod N) . Suppose K = K1 K2 where K1, K2 234 . (prob. 20%)Then: C/K1e = K2e (mod N) Build table: C/1e, C/2e, C/3e, , C/234e . time: 234For K2 = 0, 234 test if K2e is in table. time: 234 34 Attack time: 240 264WebBrowserWebServerCLIENT HELLOSERVER HELLO (e,N)dC=RSA(K)Randomsession-key K通用通用 RSA 加密加密 不要使用教科书不要使用教科书 RSA. 实际中的实际中的RSA :msgPreprocessingciphertextRSAPKCS1 V1.5 PKCS1 mode 2:(encryption)02random padFFmsg1024 bits16 bits对对RSA的选择密文攻击的选择密文攻击原理原理 E(e,m1) E(e,m2)=E(e,m1 m2）PKCS1 V2.0 - OAEP New preprocessing function: OAEP (BR94). Thm: RSA is trap-door permutation OAEP is CCS when H,G are “random oracles”. In practice: use SHA-1 or MD5 for H and G.H+G+Plaintext to encrypt with RSArand.M01 00.0Check padon decryption.Reject CT if invalid.0,1n-1Rabin密码体制密码体制 它不是以一一对应的单向陷门函数为基础，对同一它不是以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文密文，可能有两个以上对应的明文; 破译该体制等价于对大整数的分解。破译该体制等价于对大整数的分解。 RSA中选取的公开钥中选取的公开钥e满足满足1e(n)，且，且gcd(e,(n)=1。Rabin密码体制则取密码体制则取e=2。Rabin算法：算法：密钥的产生密钥的产生 随机选择两个大素数随机选择两个大素数p、q，满足，满足pq3 mod 4，即，即这两个素数形式为这两个素数形式为4k+3；计算；计算n=pq。以。以n作为公作为公开钥，开钥，p、q作为秘密钥。作为秘密钥。Rabin算法：加密算法：加密cm2 mod n其中其中m是明文分组，是明文分组，c是对应的密文分组。是对应的密文分组。Rabin算法：解密算法：解密解密就是求解密就是求c模模n的平方根，即解的平方根，即解x2c mod nRabin算法：解密算法：解密由中国剩余定理知解该方程等价于解方程组由中国剩余定理知解该方程等价于解方程组由于由于pq3 mod 4，下面将看到，方程组的解可容易地求出，下面将看到，方程组的解可容易地求出，其中每个方程都有两个解，即，其中每个方程都有两个解，即xm mod p,x-m mod pxm mod q,x-m mod q22modmodxcpxcqRabin算法：解密算法：解密经过组合可得经过组合可得4个同余方程组个同余方程组由中国剩余定理可解出每一方程组的解，共有由中国剩余定理可解出每一方程组的解，共有4个，即每一密个，即每一密文对应的明文不惟一。为了有效地确定明文文对应的明文不惟一。为了有效地确定明文,可在可在m中加入某中加入某些信息些信息,如发送者的身份号、接收者的身份号、日期、时间如发送者的身份号、接收者的身份号、日期、时间等。等。mod ,mod ,mod ,mod ,mod ,mod ,mod ,mod ,xmpxmpxmqxmqxmpxmpxmqxmq Rabin算法：解密算法：解密当当pq3 mod 4，两个方程，两个方程x2c mod p,x2c mod q的平方根都可容易地求出。的平方根都可容易地求出。所以所以 和和 是方程是方程x2c mod p的两个根。的两个根。同理同理 和和 是方程是方程x2c mod q的两个根。的两个根。14pc14ppc14qc14qqc举例举例 私钥为（私钥为（p=277, q=331) 密文为（密文为（62111) 求明文求明文 其中明文加入冗余的方法为重复写入后六位其中明文加入冗余的方法为重复写入后六位 例如例如 m=0111000111 加密时写成加密时写成00111ElGamal密码体制密码体制问题的引出：离散对数问题问题的引出：离散对数问题 diffie-Hellman问题问题ElGamal公钥加密的密钥生成公钥加密的密钥生成随机生成一个大的素数随机生成一个大的素数p和整数模和整数模p的乘法群的乘法群 的生成元的生成元g.随机选择一个整数随机选择一个整数a, 1=a=p-2，计算，计算ga mod p3. 公钥为公钥为(p, g, ga ); 私钥是私钥是a*pZElGamal公钥加密的加密过程公钥加密的加密过程假设假设B为为A加密消息加密消息m, A进行解密进行解密加密时加密时B执行如下操作：执行如下操作：1. 得到得到A的可信公钥的可信公钥(p, g, ga )2. 把消息表示成把消息表示成0，1，. , p-1 中的某个整数中的某个整数m.3. 随即选择整数随即选择整数k, 1=k=p-24. 计算计算c1= gk mod p, c2=m(ga )k mod p5. 密文为密文为c=(c1, c2)ElGamal公钥加密的解密过程公钥加密的解密过程为了有为了有c恢复明文恢复明文m, A执行如下操作：执行如下操作：用私钥用私钥a计算计算c1-a mod p1. 计算计算c1-a c2 mod p得到得到m举例举例 私钥为（私钥为（P=2357, g=2, a=1751) 密文为（密文为（1430, 697) 求明文求明文 思考题思考题 ElGamal加密算法中可否用相同的随机数加密算法中可否用相同的随机数k来加密不来加密不同的信息。同的信息。下次课内容下次课内容椭圆曲线公钥密码体制椭圆曲线公钥密码体制谢谢大家谢谢大家