微信公众平台：电子计算机与网络信息安全
ID：Computer-network
传统式的加密方法是数据加密、破译应用相同的密钥，由发件人和接受者各自储存，在数据加密和破译时应用。选用这个办法的首要问题是密钥的转化成、引入、储存、管理方法、派发等很繁杂，尤其是伴随着用户数的提升，密钥的需求成倍增加。在通信网络中，很多密钥的分派是一个解决不了的问题。
为了更好地处理基本密钥登陆密码体系的密钥分配问题，满足客户对数字签名的要求，1976年，美国学者Diffie和Hellman发布了知名毕业论文《密码学的新方向》，明确提出了创建“公布密钥登陆密码体系”：若客户A有数据加密密钥ka(公布)，有别于破译密钥ka′(信息保密)，规定ka的公布不危害ka′的安全性;若客户B要向用户A信息保密传输密文m，则能查客户A的公布密钥ka，若用ka加密获得保密c，则客户A接到c后，用仅有客户A自身才把握的破译密钥ka′对c开展破译以获得m。
1978年，美国麻省理工大学的科学研究工作组组员李维斯特(Rivest)、沙米尔(Shamir)和艾德曼(Adleman)(如下图1所显示)明确提出了一种根据公匙登陆密码体系的出色加密技术——RSA算法。RSA算法是第一个相对完善的公布密钥优化算法，它既能用以数据加密，也可以用以数字签名。RSA算法以它的三个发明人Rivest，Shamir，Adleman的名称首字母大写取名，这一优化算法承受住了很多年深层次的登陆密码剖析。登陆密码剖析者既不可以证实也不可以否认RSA算法的安全系数，但这正好表明该优化算法有一定的效率性。现阶段，RSA算法早已变成最受欢迎的公布密钥优化算法。
图1 RSA公布密钥优化算法的发明者
注：从左往右先后为李维斯特、沙米尔和艾德曼，相片拍照于1978年
1、RSA算法基本原理
RSA是最知名且使用最普遍的公布密钥优化算法，可以与此同时用以数据加密和数字签名。国际海事组织(International Organization for Standardization，ISO)在1992年施行的国家标准X.509中，将RSA算法宣布列入国家标准。1999年，美国参议院根据法律，要求了数字签名与电子签名的文档、电子邮件在美国具备相同的法律认可。
RSA算法是一种分类登陆密码体系优化算法，它的信息保密抗压强度是构建在具备大素数因素的合数上的，其因子溶解较艰难。RSA算法的公钥和私钥挑选一对大素数(100到200位十进制数或较大的数)的函数公式。而从一个公匙和保密修复出密文的难度系数，等额的于溶解2个大素数之积(这也是认可的数学难题)，但是不是为NP问题尚不确定性。表1列出了大数溶解难度系数的事例。
表1 大数溶解难度系数举例说明
RSA算法体系包含：一个公布密钥KU={e，n}，一个私有化密钥KR={d，n}。其公匙、公钥的构成及其数据加密、破译的公式计算如表2所显示。
表2 RSA算法
① 有可能寻找e、d、n的值，促使对任何的M
② 针对任何的M
③ 在给出e和n时，测算出d不是可以的。
(1)RSA算法的数论基础
下边详细介绍RSA算法中必须运用的好多个专业术语。
1)素数
素数又称之为质数，就是指在超过1的自然数中，除开1和此数本身外，不可以被别的自然数整除的数。例如，15=3×5，因此15并不是素数;又如，12=6×2=4×3，因此12也不是素数。而13除开相当于13×1之外，不可以再表明为别的一切2个整数金额的相乘，因此13是一个素数。
2)相互之间素数
公约数仅有1的2个自然数，称为互质数，即互素数。2个自然数是不是相互之间素数的辨别方式具体有下列8种(不限于此)。
① 2个质数一定是互质数，例如，2与7，13与19。
② 一个质数假如不可以整除另一个合数，那麼这两个数为互质数，例如，3与10，5与26。
③ 1并不是质数也不是合数，它和一切一个自然数全是互质数，例如，1和9908。
④ 邻近的2个自然数是互质数，例如，15与16。
⑤ 邻近的2个单数是互质数，例如，49与51。
⑥ 大数是质数的两个数是互质数，例如，97与88。
⑦ 小数是质数，大数并不是小数的倍率的两个数是互质数，例如，7与16。
⑧ 两个数全是合数(两数之差又比较大)，小数全部的质因数都并不是大数的约数，这两个数是互质数。例如，357与715，357=3×7×17，而3、7和17都不是715的约数，因此这两个数为互质数。
3)模运算
模运算是整数金额计算，有一个整数金额m，以n为模做模运算，即mmod n。令m被n整除，只留所得的的被除数做为結果，就称为模运算。例如，10 mod 3=1，26 mod 6=2，28 mod 2=0等。
模运算有下列特性。
① 同余性：若amod n=bmod n，则整数a与b同余。
② 对称：若a=b mod n，则b=amod n。
③ 传递性：若a=b mod n，b=cmod n，则a=cmod n。
4)Euler函数公式
随意给出整数n，测算在小于或等于n的整数当中有多少个与n能组成互质关联的方式称为欧拉函数，以φ(n)表明。例如，φ(8)=4，这是由于在1~8当中与8能产生互质关联的数有4个：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互质。而包括素数p的数一共有pk-1个，即1×p、2×p、…、pk-1×p。
第四种状况：假如n可以转化成2个互质的整数金额之积，例如，n=p1×p2，则φ(n)=φ(p1p2)=φ(p1)φ(p2)，即积的欧拉函数相当于每个因素的欧拉函数之积。例如，φ(56)=φ(7×8)=φ(7)×φ(8)=6×4=24。
第五种状况：针对随意超过1的整数金额，若其可以写出一系列素数的积，如
，则有
。
5)欧拉定理
假如2个整数a和n互质，则n的欧拉函数φ(n)达到：
aφ(n)≡1(mod n)
即a的φ(n)次方减掉1，被n整除。例如，3和7互质，φ(7)=6，(36-1)/7=104。
假如整数a与质数p互质，则由于φ(p)=p-1，因此欧拉函数可写出：
ap−1≡1(mod p)
这就是有名的费马小定理(Fermat Theory)。
6)费马小定理
若m是素数，且a并不是m的倍率，则am-1 mod m=1。或是，若m是素数，则ammod m=a。例如，46mod 7=4096 mod 7=1，47mod 7=16384 mod 7=4。
推理：针对互素的a和n，有aφ(n)mod n=1。
(2)素数的发生与检测
最先来详细介绍素数的简易判断优化算法。在C编程设计中，素数的判断优化算法为：给出一个整数n，用2到sqrt(n)中间的全部整数金额除去n，假如能整除，则n并不是素数，假如不能整除，则n是素数。这一优化算法的算法复杂度为O(sqrt(n))，优化算法叙述简易，完成都不艰难。可是，这一优化算法针对十位数比较大的素数判断就变得心有余而力不足了。
现阶段，适用RSA算法的最好用的素数造成方法是几率测试方法。该法的观念是任意造成一个大单数，随后检测其是不是符合条件，若达到，则该大单数可能是素数，不然，其是合数。
因为素数有无限好几个，因而判断一个整数金额是否素数一直是一个大难点，威尔逊定理(Wilson's Theorem)便是这其中的一种判断方式。
威尔逊定理：若整数n>1，则n是一个素数当且仅当(n-1)! ≡ -1(mod n)。
尽管说威尔逊定理得出了素数的等价命题，可是因为阶乘的增速太快(如13!为60多亿元)，因而其操作过程使用价值不高。从而指出了几率检测方式。
斯泰格-拉宾素性检测(Miller-Rabin Prime Test)是一种非常典型的概率检测方式。可以证明书次Miller-Rabin的恰当概率超过3/4，大家反复许多次就可以扩大这一概率。Miller-Rabin尽管有一定的概率出错，但实践证明，在反复20次的情形下，107之内的质数不容易分辨出错。
2、RSA加解密优化算法过程
(1)RSA加密算法过程
RSA加密算法的过程如下所示：
① 取2个任意大素数p和q(信息保密);
② 测算公布的变位系数n=p×q(公布);
③ 测算密秘的欧拉函数φ(n)=(p-1)×(q-1)(信息保密)，丢掉p和q，不必让所有人了解;
④ 任意选择整数金额e，使其达到gcd(e,φ(n))=1(公布e数据加密密匙);
⑤ 测算d，使其达到de≡1(mod φ(n))(信息保密d破译密匙);
⑥ 将密文X按模为r自乘e次幂以进行数据加密实际操作，进而造成保密Y(X、Y值在0到n-1范畴内)，即Y=Xemod n;
⑦ 破译，将保密Y按模为n自乘d次幂，得X=Ydmod n。
在RSA加(解)密优化算法完成过程中，关键的算法复杂度是测算模的逆元及其模指数值，一般来说，测算模的逆元的时候会选用拓展的欧几里德优化算法。
(2)RSA破译优化算法过程
因为指数值比较大，因而RSA破译过程较为用时，但运用孙子定理(Chinese Remainder Theorem，CRT)可提升破译优化算法高效率。CRT对RSA破译优化算法转化成2个破译方程式(运用M=Cdmod pq)，即：M1=Mmod p=(Cmod p)d mod (p-1)mod p，M2=Mmod q=(Cmod q)d mod (q-1)mod q。
列方程M=M1mod p和M=M2mod q，可求取其具备唯一解。
3、RSA算法运用
(1)RSA用以数字签名
① 签字：对随意信息m∈M，客户采用自身的公钥签字如下所示：S≡md(mod n)，从而可以获得签字的信息(m, S)。
② 认证签字：由该消费者的公开密钥(e, n)，认证m≡Se(mod n)是不是创立。
(2)RSA加密算法案例
可以根据一个简便的事例来了解RSA的原理。为了更好地方便测算，在下列案例中只选择小标值的素数p, q及其e，假定客户A要将密文“key”根据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≡1 mod f(n)，即3×d≡1 mod 20。d的选值可以用试算的方法来明确。试算結果如表3所显示。
表3 d的选值试算結果
根据试算得到，当d=7时，e×d≡1 mod f(n)同余等式成立。因而，会让d=7，进而可以制定出一对公与私密匙，数据加密密匙(公匙)为：KU=(e,n)=(3,33)，破译密匙(公钥)为：KR=(d,n)=(7,33)。
2)英语智能化
将密文信息内容智能化，并将其以每片2个数据开展分类。假设密文英语字母编号本表按英文字母排列顺序的标值，如表4所显示。
表4 密文英语字母编号表
则可获得分类后的key的密文信息内容为：11，05，25。
3)密文数据加密
用户加密密匙(3,33)将智能化密文分类数据加密成保密。由C≡Me(mod n)得：
C1=(M1)d(modn)=113(mod33)=11
C2=(M2)d(modn)=053(mod33)=26
C3=(M3)d(modn)=253(mod33)=16
因而，获得对应的保密信息内容为：11，26，16。
4)保密破译
客户B接到保密后，若想将其破译，则只必须测算M≡Cd(mod n)，即：
M1=(C1)d(modn)=117(mod33)=11
M2=(C2)d(modn)=317(mod33)=05
M3=(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 bits 以上，计算成本高，速度比较慢，较对称性加密算法慢好多个量级，且伴随着大数溶解技术性的发展趋势，这一长短仍在提升，不利数据类型的规范化。
因而，应用RSA只有数据加密少许数据信息，很多的数据库加密还需要借助对称性加密算法。