《计算机网络安全防护技术（第二版）》 课件 第3章-任务3.2.1 探究RSA算法和DH算法

第3章数据加密技术3.2.1RSA算法和DH算法编著：

秦燊劳翠金

3.2非对称加密技术通过前面的学习，我们知道，对称加密技术要求发送者和接收者事先将对称密钥共享，如果双方事先没有共享密钥，一方就要想办法将所用的对称密钥传送给另一方。万一密钥在传送过程中被攻击者截获，攻击者就可以解密出所有用这个对称密钥加密的密文了。但如何安全的将对称密钥传送给对方，一直是个大问题。直到1976年美国科学家WhitfieldDiffie和MartinHellman提出DH算法，才解决了这个难题。DH算法不直接传递密钥，只传递用自己的私钥加密某数后的值，最终双方都能计算出一把与对方完全一致的新密钥，双方再用这把新密钥来加密和解密数据。受DH算法启发，麻省理工学院的三位科学家Rivest、Shamir和Adleman于1977年提出了RSA算法，该算法把密钥分成了两把，加密和解密使用不同的密钥，私钥由拥有者保管，不在网络间传输，公钥则是公开的。RSA算法是第一个能同时用于加密和数字签名的算法。常见的非对称加密算法有：RSA、DH、ECC等。下面，借助工具软件RSA-TOOL，先介绍RSA算法，再介绍DH算法，说明如何生成和运用非对称密钥。一、RSA算法RSA算法是如何工作的呢？下面以张三与李四通信为例。张三拥有一对密钥，分别是张三的公钥和张三的私钥。其中，张三的公钥是公开的，共享给所有人，如何确保张三的公钥不被伪造，将在后文中讲解；张三的私钥是保密的，只有张三可以使用。李四若要加密数据给张三，可用张三的公钥加密。张三收到后，再用自己的私钥解密，读取明文。攻击者没有张三的私钥，只有张三的公钥和截获到的密文，是无法获取明文的。RSA密钥对的生成方法如下：首先，要秘密地选取两个大素数。为了便于计算和说明，这里选两个小素数7和17，还要选取一个与（7-1）×（17-1）互素的数（即与96互素的数）作为公钥，这里选5作为公钥。接着，打开工具软件RSA2TOOL，将进制设置为10进制，输入公钥5，第一个素数7，第二个素数17，点击“CalcD”按钮，即可算出循环周期是119，私钥是77。我们可以把循环周期合并到公钥和私钥中书写，即把公钥记为（5，119），把私钥记为（77，119）。3.2.1RSA算法和DH算法为便于理解，下面用不严谨的方法描述一下RSA算法大致是如何工作的。RSA算法要用到欧拉函数与费马小定理。欧拉函数的特例：假如a是素数，那么a的欧拉函数等于a-1。费马小定理的特例：假如a是素数、b是一个整数，那么b^(a-1)moda=1。图3-2-1软件工具RSA-Tool为便于理解，下面用不严谨的方法描述一下RSA算法大致是如何工作的。RSA算法要用到欧拉函数与费马小定理。欧拉函数的特例：假如a是素数，那么a的欧拉函数等于a-1。费马小定理的特例：假如a是素数、b是一个整数，那么b^(a-1)moda=1。以选取两个小素数7和17为例：根据费马小定理，对于素数7，任意取一个整数b，可得到：b^(7-1)mod7=1，即b^6mod7=1;根据费马小定理，对于素数17，任意取一个整数b，可得到：b^（17-1）mod17=1，即b^16mod17=1;由此可知：b^(6×16)mod(7×17)=1，即：b^96mod119=1如果存在一个数mod96等于1，比如385mod96=1，385=4×96+1，那么，b^385mod119=b^（4×96+1）mod119=【（b^（4×96））mod119】×【（b^1）mod119】=1×b=b可见，只要找到两个数，它们的乘积mod96等于1，这两个数就是公钥和私钥。原因如下：比如，我们可以找到两个与96互素的数：5和77，5×77=385，385mod96=1，由上式b^385mod119=b可知：b^(5×77)mod119=b把5×77拆开来写，上式也可写成：【b^5mod119】^77mod119=b其中，【b^5mod119】可以看成对b进行加密，得到的结果就是密文；接着，（密文^77mod119）是对密文进行解密，得到的结果就是解密后的明文b。演算过程中，从7×17求得119很容易。119是公开的，如果能将119分解成7乘以17，再根据公钥5就可以破解出私钥是77了。但实际应用中，采用的是两个上百位的十进制大素数。由这两个上百位十进制数的乘积得到一个很大的数，RSA算法的安全性就取决于对这个大数分解的难度。将长达1024位或2048位的十进制大数分解成两个素数相乘，这样的难度非常大，接近不可能。因此，只要密钥位数足够大，RSA算法是安全的。例题：已知RSA公钥是(5,119)，私钥是（77，119），请用公钥(5,119)加密字母A（A的ASCII码是65，即加密：65），再用私钥对密文进行解密。明文：65用公钥加密：用公钥（5，119）进行加密，（65^5）mod119=46即加密后，得到密文：46用私钥解密：用私钥（77，119）进行解密，(46^77)mod119=65，即解密得到明文：65因为公钥是公开的，即5和119是公开的，若能对119作因数分解，就可以破解出私钥了，对119进行因数分解很容易，可以分解成7×17。但对1024位、2048位这样的大数进行因数分解是不可行的，因此，只要密钥位数够大，RSA算法是安全的。二、DH算法DH是Diffie-Hellman的首字母缩写，DH算法是WhitefieldDiffie与MartinHellman在1976年提出了一个的密钥交换算法。它可以使用不对称加密算法，为通信双方生成相同的临时对称密钥，然后双方利用这个临时对称密钥进一步传送真正使用的对称密钥。一）原理很简单，简单的运算过程举例如下：1.公开两个数：5和97。2.A、B双方各自取一个保密的数：A方选取36。B方选取58。3.A计算出5^36mod97给B。B计算出5^58mod97给A。4.A根据((5^58mod97)^36)mod97得到对称密钥：((5^58^36)mod97。5.B根据((5^36mod97)^58)mod97得到对称密钥：((5^36)^58)mod97。可以看出，A、B双方得到的对称密钥是一至的。二）具体过程如下：1.各自产生密钥对。2.交换公钥。3.用对方的公钥和自己的私钥运行DH算法得到一个临时的对称密钥M。4.A产生一个对称密钥N，用临时密钥M加密后发给B。5.B用临时密钥M解密得到对称密钥N。6.B用这个对称密钥N来解密A的数据。比较关键的一步，双方是如何对方的公钥计算得到临时的对称密钥M的？三）举例说明。1.各自产生密钥对。先解释什么是原根。若存在g∈[2,p-1]，对于所有i∈[1,p-1]，计算(g^i)%p得到的结果都是互不相同的，那么数g就是数p的一个原根。每个素数都有原根。1）双方协商一个素数和这个素数的一个原根，这个素数和它的原根是公开的。如取素数q=97和97的一个原根a=5。q和a由双方协商，并且都是公开的。2）A、B双方各自选择一个小于q的随机数作为自己的私有密钥(即小于97的随机数）。A选的私钥XA=36。B选的私钥XB=58。3）A、B双方计算各自的公开密钥：A的公钥YA=（5^36）mod97=50B的公钥YB=（5^58）mod97=442.交换公钥。3.根据DH算法，用对方的公钥和自己的私钥进行运算，得到临时的对称密钥M。