LectureRSA公钥算法.ppt

RSA公钥算法 高文宇 gwyy@163.com 非对称加密简史 1976年，Whitfield Diffie和Martin Hellman提出不仅密码算法本身可以公开而且加密用的密钥也可以公开，只要解密密钥必威体育官网网址就可以——非对称密码体系(公开密码体系)。 1977年，MIT, Rivest、Shamir、Adleman合作提出了第一个实用的公开密钥密码算法，即著名的RSA算法。 通过密钥进行加密和解密过程，在时间上是可行的，即可在多项式时间内完成。 尚未找到由公钥求出私钥的多项式时间算法—NP难 密钥交换的困境 传统的对称加密算法要求通信双方事先有共享的秘密，否则无法在一个开放的环境中进行必威体育官网网址通信。 Diffie-Hellman密钥交换算法 New Directions in Cryptography W. Diffie and M. E. Hellman, IEEE Transactions on Information Theory, vol. IT-22, Nov. 1976, pp: 644–654. Diffie-Hellman算法 （1）Alice与Bob确定两个大素数n和g，这两个数不用必威体育官网网址 （2）Alice选择另一个大随机数x，并计算A如下：A=gx mod n （3）Alice将A发给Bob （4）Bob 选择另一个大随机数y，并计算B如下：B=gy mod n （5）Bob将B发给Alice （6）计算秘密密钥K1如下：K1=Bx mod n （7）计算秘密密钥K2如下：K2=Ay mod n K1=K2，因此Alice和Bob可以用其进行加解密 问题1：K1=K2 ? 因为，K1=Bx mod n， B=gy mod n 所以，K1= (gy mod n)x mod n = gyx mod n 因为，K2=Ay mod n， A=gx mod n 所以，K2= (gx mod n)y mod n = gxy mod n 所以，K1=k2 求证： 证明：令 则 则 问题2：由(n、g、A、B)=K1或K2？ K1=Bx mod n， B=gy mod n K2=Ay mod n， A=gx mod n 分析： （1）要想求出k1，则需要知道B、n、x； （2）B、n已知，因此需要求出x； （3）由A=gx mod n求出x可行否？ 这就是数论中的离散对数问题 离散对数问题 定义1（生成元）：对于一个素数q，如果数值a mod q, a2 mod q, …, aq-1 mod q是各不相同的整数，并且以某种排列方式组成了从1到q-1的所有整数，则称整数a是素数q的一个生成元，或本原元。 定义2（离散对数）：对于一个整数b和素数q的一个生成元a，可以找到一个唯一的指数i，使得： b=ai mod q (0≤ i≤ q-1) 成立，则指数i称为b的以a为底数的模q的离散对数。 对于给定的a，i，q，容易计算出b，在最坏情况下需执行i次乘法，且存在计算出b的有效算法。 但对于给定b，a，q，计算出i一般比较困难，这就是离散对数的难解性，它是Diffie-Hellman密钥交换算法和DSA数字签名算法的数学基础。 算法实现中的问题 （1）素数有界吗（素数个数有限吗）？ （2）大的指数运算如何实现？ (234561)5 mod 17=? （3）如何产生（测试）足够大的素数？ RSA算法 Rivest Shamir Adleman 非对称加密的必威体育官网网址性 非对称加密使用两个密钥，一个用于加密，一个用于解密，其它密钥都无法解密这个消息，包括用于加密的密钥。因此无需通信双方事先有共享的秘密。 非对称加密密钥的可扩展性 多方（加密）对一方（解密）的情况，只需要一个密钥。多对多时，仅需要n对密钥，而非n^2个。 非对称加密的数学基础 单向函数 对于一个函数 ，如果对于其定义域上的任意 x， 都容易计算，同时， 对于其值域中几乎所有的取值 y ，计算其逆函数 都是不可行的，则函数 被称为单向函数。 可以提供单向函数的三大数学难题 大整数分解问题（简称IFP）； 离散对数问题（简称DLP）； 椭圆曲线离散对数问题（简称ECDLP）。 RSA算法 (1)选择两个大素数P、Q (2)计算N=P*Q (3)选择一个公钥（加密密钥）E，使其不是(P-1)与(Q-1)的因子 (4)选择私钥（解密密钥）D，满足如下条件： (D*E) mod (P-1)(Q-1)=1 (5)加密时，明文PT计算密文CT如下： CT=PTE mod N (6)解密时，从密