微信公众号：计算机与网络安全ID：Computer-network传统的加密方式是使用同一个密钥进行加密和解密，由发送方和接收方分别存储.并在解密时使用。这种方法的主要问题是密钥的生成、注入、存储、管理和分发都非常复杂，尤其是随着用户数量的增加，对密钥的需求呈指数级增长。在网络通信中，大量密钥的分发是一个很难解决的问题。为了解决传统密钥密码体制中的密钥分配问题，满足用户对数字签名的需求，1976年，美国学者Diffie和Hellman发表了著名论文《密码学的新方向》，提出建立“公钥密码体制”：如果用户A拥有不同于解密密钥ka'(confidential)的加密密钥ka(public)，要求ka的泄露不影响ka'的安全性；如果用户B想秘密地向用户A发送明文m，用户A的公钥ka，如果密文c是用ka加密得到的，用户A收到c后，用只有用户A拥有的解密密钥ka'对c进行解密得到米。1978年，麻省理工学院研究小组成员Rivest、Shamir和Adleman（如图1所示）提出了一种基于公钥密码体制的优秀加密算法——RSA算法。RSA算法是第一个比较完善的公钥算法，既可以用于加密又可以用于数字签名。RSA算法以其三位发明者Rivest、Shamir和Adleman的名字命名。该算法经受住了多年的深入密码分析。密码分析者既不能证明也不能否认RSA算法的安全性，但这只是说明该算法具有一定的可信度。目前，RSA算法已经成为最流行的公钥算法。图1.RSA公钥算法的发明者注：从左到右依次为Livist、Shamir和Edman，照片拍摄于1978年1.RSA算法原理RSA是最著名和应用最广泛的公钥算法用于加密和数字签名。在1992年国际标准化组织（ISO）颁布的国际标准X.509中，RSA算法被正式纳入国际标准。1999年，美国参议院通过立法，规定文件和电子邮件上的数字签名和手写签名在美国具有同等法律效力。RSA算法是分组密码系统算法。它的安全强度是基于具有大质因数的合数，并且其因式分解是困难的。RSA算法的公钥和私钥选择一对大质数（100到200位或更大）的函数。从公钥和密文中恢复明文的难度相当于分解两个大质数的乘积（这是公认的数学问题），但是否是NP问题还不确定。表1给出了大数因式分解的困难示例。表1大数分解难度示例RSA算法体系包括：公钥KU={e,n}，私钥KR={d,n}。公钥和私钥的组成以及加解密的公式如表2所示。表2RSA算法①可以求出e、d、n的值，这样计算不可行当给定e和n时，d用于所有M②和所有M③。(1)RSA算法的数论基础下面介绍RSA算法中需要用到的几个术语。1）素数素数又称质数，是指大于1的自然数中除1和该数本身外，不能被其他自然数整除的数。例如15=3×5，所以15不是素数；又如，12=6×2=4×3，所以12也不是质数。而13除了等于13×1外，不能再表示为任何其他两个整数的乘积，所以13是质数。2）公分母仅为1的两个自然数称为互质数，即互质数。判断两个自然数互为质数的方法主要有以下8种（不限于这些）。①两个质数一定是互质数，例如2和7、13和19。②如果一个质数不能整除另一个合数，则这两个数是互质数，例如3和10、5和26。③1不是质数，也不是合数，它是与任意自然数的互质数，例如1和9908。④两个相邻的自然数是互质数，例如15和26。16.⑤两个相邻的奇数是互质数，例如49和51。⑥大数是质数，两个数是互质数，例如97和88。⑦小数是质数，两个小数不是小数倍数的数是互质数，例如7和16。大数，且两数互质。比如357和715，357=3×7×17，3、7、17不是715的约数，所以这两个数是互质数。3）模运算模运算是整数运算，有一个整数m，取模n作为模运算，即mmodn。令m除以n，只取余数作为结果，称为模运算。例如，10mod3=1、26mod6=2、28mod2=0等。模运算具有以下性质。①同余：如果amodn=bmodn，则正整数a和b同余。②对称性：若a=bmodn，则b=amodn。③传递性：若a=bmodn，b=cmodn，则a=cmodn。4）欧拉函数给定任意正整数n，计算有多少个小于或等于n的正整数可以与n形成互质关系的方法称为欧拉函数，用φ(n)表示。比如φ(8)=4，因为在1~8中，有4个数可以和8形成互质关系：1、3、5、7。φ(n)的计算方法并不复杂，并将在以下案例中进行讨论。第一种情况：如果n=1，那么φ(1)=1，因为1和任何数（包括它自己）都可以形成互质关系。第二种情况：如果n是质数，那么φ(n)=n-1，因为质数和每一个比它小的数都可以形成互质关系。第三种情况：若n为质数的某次幂，如n=pk，p为质数，k≥1，则φ(pk)=pk-pk-1例如φ(8)=φ(23)=23-22=4。这是因为只有当一个数不包含质数p时，它才能与n互质。并且有pk-1个数包括质数p，即1×p,2×p,…,pk-1×p。第四种情况：如果n可以分解为两个互质整数的乘积，例如n=p1×p2，则φ(n)=φ(p1p2)=φ(p1)φ(p2)，即乘积欧拉函数等于各个因素的欧拉函数的乘积。例如，φ(56)=φ(7×8)=φ(7)×φ(8)=6×4=24。第五种情况：对于任何大于1的整数，如果可以写成一系列素数的乘积，比如，则存在。5）欧拉定理若两个正整数a和n互质，则n的欧拉函数φ(n)满足：aφ(n)≡1(modn)，即a的负的φ(n)次方1,可被n整除。例如3和7互质，φ(7)=6，(36-1)/7=104。如果正整数a与质数p互质，则因为φ(p)=p-1，欧拉函数可以写为：ap?1≡1(modp)。这就是著名的费马定理。6）费马小定理如果m是质数，a不是m的倍数，则am-1modm=1。或者，如果m是质数，则ammodm=a。例如，46mod7=4096mod7=1，47mod7=16384mod7=4。推论：对于互质的a和n，存在aφ(n)modn=1。(2)素数的产生与验证首先介绍素数的简单判断算法。在C编程中，素数判定算法是：给定一个正整数n，将n除以2到sqrt(n)之间的所有整数，如果可以整除，则n不是素数，如果不能整除，则n是质数。该算法时间复杂度为O(sqrt(n))，算法描述简单，实现难度不大。但是，该算法无法判断大位数的素数。目前最实用的适合RSA算法的素数生成方法是概率检验法。这个方法的思路是随机产生一个大的奇数，然后测试它是否满足条件。如果是，则大奇数可能是质数，否则就是合数。由于质数有无穷多个，判断一个整数是否为质数一直是个大难题。威尔逊定理（Wilson'sTheorem）是确定方法之一。威尔逊定理：若正整数n>1，则n为质数当且仅当(n-1)！≡-1(modn)。威尔逊定理虽然给出了素数的等价命题，但由于阶乘的增长速度太快（比如13！就是60亿多），其实用价值并不高。因此，提出了一种概率检验方法。Miller-RabinPrimeTest是一种典型的概率检验方法。可以证明，单个Miller-Rabin正确的概率大于3/4，我们可以通过重复多次来增加这个概率。虽然米勒-拉宾有一定的出错概率，但实践证明，在重复20次的情况下，107以内的素数是不会判断错误的。2.RSA加解密算法过程(1)RSA加密算法过程RSA加密算法过程如下：①取两个随机的大质数p和q（保密）；②计算公共模数n=p×q（公共）；③计算欧拉秘密函数φ(n)=(p-1)×(q-1)（机密），丢弃p和q，不要让任何人知道；④随机选择一个整数e满足gcd(e,φ(n))=1（e加密公钥）；⑤计算d满足de≡1(modφ(n))（秘密d解密密钥）；⑥模明文Xtorself乘以e的幂完成加密运算，从而生成密文Y（X，Y值在0到n-1的范围内），即Y=Xemodn;⑦解密，将密文Y乘以n乘以d次幂，得到X=Ydmodn。在RSA加密（解密）算法的实现过程中，主要的计算是计算模的逆和模索引。通常，扩展欧几里得算法用于计算模的逆。(2)RSA解密算法过程由于指数较大，比较耗时，但利用孙子定理(ChineseRemainderTheorem，CRT)可以提高解密算法的效率。CRT为RSA解密算法生成两个解密方程（使用M=Cdmodpq），即：M1=Mmodp=(Cmodp)dmod(p-1)modp,M2=Mmodq=(Cmodq)dmod(q-1)模q。解方程M=M1modp和M=M2modq可知有唯一解。3、RSA算法的应用(1)RSA用于数字签名①签名：对于任意消息m∈M，用户使用自己的私钥进行如下签名：S≡md(modn)，然后得到签名后的消息（多发性硬化症）。②验证签名：用用户的公钥(e,n)验证m≡Se(modn)是否成立。(2)RSA加密算法示例你可以通过一个简单的例子来理解RSA的工作原理。为了计算方便，下面的例子中，只选取取值较小的素数p、q、e。假设用户A需要将明文“密钥”用RSA加密后传递给用户B，过程如下。1）设计公私钥（e,n）和（d,n），设p=3，q=11，得n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3（3和20互质），则e×d≡1modf(n)，即3×d≡1mod20。d的取值可通过试算确定。试验结果如表3所示。表3d值的试算结果试算得到，当d=7时，e×d≡1modf(n)同余方程成立。因此令d=7，这样就可以设计出一对公私钥，加密密钥（公钥）为：KU=（e,n）=（3,33），解密密钥（私钥）)为：KR=(d,n)=(7,33)。2)英文数字化将明文信息数字化，每块用两个数字分组。假设明文英文字母编码表是按字母顺序排列的数值，如表4所示。表4.明文英文字母编码表。可以得到分组后密钥的明文信息：11、05、25。3）明文加密用户加密密钥（3、33）将数字化后的明文分组信息加密成密文。从C≡Me(modn):C1=(M1)d(modn)=113(mod33)=11C2=(M2)d(modn)=053(mod33)=26C3=(M3)d(modn)=253(mod33)=16因此对应的密文信息为：11,26,16。4)密文解密用户B需要计算M≡Cd(modn)，即：M1=(C1)d(modn)=117(mod33)=11M2=(C2)d(modn)=317(mod33)=05M3=(C3)d(modn)=167(mod33)=25用户B得到的明文信息为：11,05,25。转换根据上面的编码表将其翻译成英文，就可以得到恢复后的原文“key”。当然，实际的实现要比这复杂的多。由于RSA算法的公钥和私钥的长度（模数长度）必须达到1024位甚至2048位才能保证安全，因此，p、q、e的选取，公钥和私钥的生成密钥，以及加解密模数指数的运算都有一定的计算程序需要依靠计算机的高速运算能力来完成。4、RSA加解密算法的安全性在RSA加密的应用中，公钥KU是公开的，即e和n的值可以被第三方窃听者获取。破解RSA密码的关键是从已知的e和n的值（n等于pq）中求出d的值，从而得到破解密文的私钥。由上式：d≡e-1(mod((p-1)(q-1)))或de≡1(mod((p-1)(q-1)))可知密码破解的本质问题是：从这个pq的数值中找出(p-1)和(q-1)。也就是说，只需要p和q的值就可以得到d的值，然后得到私钥。如果p和q是大质数，则从它们的乘积pq分解p和q是公认的数学问题。例如，当pq大到1024位时，迄今为止还没有人能够使用任何计算工具来完成分解它的任务。因此，RSA自提出以来经历了40多年各种攻击的考验，逐渐被人们所接受。它被普遍认为是目前最好的公钥方案之一。然而，虽然RSA的安全性依赖于大数分解，但目前还没有从理论上证明解密RSA的难度等同于大数分解的难度，即RSA的主要缺陷是不能从理论上掌握其保密性能。另外，RSA的缺点是：①生成密钥非常麻烦，而且会受到质数生成技术的限制，很难做到一次性加密；②块长度过大。为了保证安全，n至少需要600位。成本高，速度慢，比对称密码算法慢几个数量级，而且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化.因此，只有少量的数据可以使用RSA加密，而大量的数据加密依赖于对称密码算法。
