㈠ 公钥密码系统及RSA公钥算法
公钥密码系统及RSA公钥算法
本文简单介绍了公开密钥密码系统的思想和特点，并具体介绍了RSA算法的理论基础，工作原理和具体实现过程，并通过一个简单例子说明了该算法是如何实现。在本文的最后，概括说明了RSA算法目前存在的一些缺点和解决方法。
关键词：公钥密码体制 ， 公钥 ，私钥 ，RSA
§1引言
随着计算机联网的逐步实现，Internet前景越来越美好，全球经济发展正在进入信息经济时代，知识经济初见端倪。计算机信息的保密问题显得越来越重要，无论是个人信息通信还是电子商务发展，都迫切需要保证Internet网上信息传输的安全，需要保证信息安全。信息安全技术是一门综合学科，它涉及信息论、计算机科学和密码学等多方面知识，它的主要任务是研究计算机系统和通信网络内信息的保护方法以实现系统内信息的安全、保密、真实和完整。其中，信息安全的核心是密码技术。密码技术是集数学、计算机科学、电子与通信等诸多学科于一身的交叉学科。它不仅能够保证机密性信息的加密，而且能够实现数字签名、身份验证、系统安全等功能。是现代化发展的重要科学之一。本文将对公钥密码系统及该系统中目前最广泛流行的RSA算法做一些简单介绍。
§2公钥密码系统
要说明公钥密码系统，首先来了解一下不同的加密算法：目前的加密算法按密钥方式可分为单钥密码算法和公钥密码算法。
2.1.单钥密码
又称对称式密码，是一种比较传统的加密方式，其加密运算、解密运算使用的是同样的密钥，信息的发送者和信息的接收者在进行信息的传输与处理时，必须共同持有该密码（称为对称密码）。因此，通信双方都必须获得这把钥匙，并保持钥匙的秘密。
单钥密码系统的安全性依赖于以下两个因素：第一，加密算法必须是足够强的，仅仅基于密文本身去解密信息在实践上是不可能的；第二，加密方法的安全性依赖于密钥的秘密性，而不是算法的秘密性，因此，我们没有必要确保算法的秘密性（事实上，现实中使用的很多单钥密码系统的算法都是公开的），但是我们一定要保证密钥的秘密性。
从单钥密码的这些特点我们容易看出它的主要问题有两点：第一，密钥量问题。在单钥密码系统中，每一对通信者就需要一对密钥，当用户增加时，必然会带来密钥量的成倍增长，因此在网络通信中，大量密钥的产生﹑存放和分配将是一个难以解决的问题。第二，密钥分发问题。单钥密码系统中，加密的安全性完全依赖于对密钥的保护，但是由于通信双方使用的是相同的密钥，人们又不得不相互交流密钥，所以为了保证安全，人们必须使用一些另外的安全信道来分发密钥，例如用专门的信使来传送密钥，这种做法的代价是相当大的，甚至可以说是非常不现实的，尤其在计算机网络环境下，人们使用网络传送加密的文件，却需要另外的安全信道来分发密钥，显而易见，这是非常不智是甚至是荒谬可笑的。
2.2公钥密码
正因为单钥密码系统存在如此难以解决的缺点，发展一种新的﹑更有效﹑更先进的密码体制显得更为迫切和必要。在这种情况下，出现了一种新的公钥密码体制，它突破性地解决了困扰着无数科学家的密钥分发问题，事实上，在这种体制中，人们甚至不用分发需要严格保密的密钥，这次突破同时也被认为是密码史上两千年来自单码替代密码发明以后最伟大的成就。
这一全新的思想是本世纪70年代，美国斯坦福大学的两名学者Diffie和Hellman提出的，该体制与单钥密码最大的不同是：
在公钥密码系统中，加密和解密使用的是不同的密钥（相对于对称密钥，人们把它叫做非对称密钥），这两个密钥之间存在着相互依存关系：即用其中任一个密钥加密的信息只能用另一个密钥进行解密。这使得通信双方无需事先交换密钥就可进行保密通信。其中加密密钥和算法是对外公开的，人人都可以通过这个密钥加密文件然后发给收信者，这个加密密钥又称为公钥；而收信者收到加密文件后,它可以使用他的解密密钥解密，这个密钥是由他自己私人掌管的，并不需要分发，因此又成称为私钥，这就解决了密钥分发的问题。
为了说明这一思想,我们可以考虑如下的类比：
两个在不安全信道中通信的人，假设为Alice（收信者）和Bob（发信者），他们希望能够安全的通信而不被他们的敌手Oscar破坏。Alice想到了一种办法，她使用了一种锁（相当于公钥），这种锁任何人只要轻轻一按就可以锁上，但是只有Alice的钥匙（相当于私钥）才能够打开。然后Alice对外发送无数把这样的锁，任何人比如Bob想给她寄信时，只需找到一个箱子，然后用一把Alice的锁将其锁上再寄给Alice，这时候任何人（包括Bob自己）除了拥有钥匙的Alice，都不能再打开箱子，这样即使Oscar能找到Alice的锁，即使Oscar能在通信过程中截获这个箱子，没有Alice的钥匙他也不可能打开箱子，而Alice的钥匙并不需要分发，这样Oscar也就无法得到这把“私人密钥”。
从以上的介绍可以看出，公钥密码体制的思想并不复杂，而实现它的关键问题是如何确定公钥和私钥及加/解密的算法，也就是说如何找到“Alice的锁和钥匙”的问题。我们假设在这种体制中, PK是公开信息，用作加密密钥，而SK需要由用户自己保密，用作解密密钥。加密算法E和解密算法D也都是公开的。虽然SK与PK是成对出现，但却不能根据PK计算出SK。它们须满足条件：
①加密密钥PK对明文X加密后，再用解密密钥SK解密，即可恢复出明文，或写为：DSK（EPK（X））=X
②加密密钥不能用来解密，即DPK（EPK（X））≠X
③在计算机上可以容易地产生成对的PK和SK。
④从已知的PK实际上不可能推导出SK。
⑤加密和解密的运算可以对调，即：EPK（DSK（X））=X
从上述条件可看出，公开密钥密码体制下，加密密钥不等于解密密钥。加密密钥可对外公开，使任何用户都可将传送给此用户的信息用公开密钥加密发送，而该用户唯一保存的私人密钥是保密的，也只有它能将密文复原、解密。虽然解密密钥理论上可由加密密钥推算出来，但这种算法设计在实际上是不可能的，或者虽然能够推算出，但要花费很长的时间而成为不可行的。所以将加密密钥公开也不会危害密钥的安全。
这种体制思想是简单的，但是，如何找到一个适合的算法来实现这个系统却是一个真正困扰密码学家们的难题，因为既然Pk和SK是一对存在着相互关系的密钥，那么从其中一个推导出另一个就是很有可能的，如果敌手Oscar能够从PK推导出SK，那么这个系统就不再安全了。因此如何找到一个合适的算法生成合适的Pk和SK，并且使得从PK不可能推导出SK，正是迫切需要密码学家们解决的一道难题。这个难题甚至使得公钥密码系统的发展停滞了很长一段时间。
为了解决这个问题，密码学家们考虑了数学上的陷门单向函数，下面，我们可以给出它的非正式定义：
Alice的公开加密函数应该是容易计算的，而计算其逆函数（即解密函数）应该是困难的（对于除Alice以外的人）。许多形式为Y=f（x）的函数，对于给定的自变量x值，很容易计算出函数Y的值；而由给定的Y值，在很多情况下依照函数关系f (x)计算x值十分困难。这样容易计算但难于求逆的函数，通常称为单向函数。在加密过程中，我们希望加密函数E为一个单项的单射函数，以便可以解密。虽然目前还没有一个函数能被证明是单向的，但是有很多单射函数被认为是单向的。
例如，有如下一个函数被认为是单向的，假定n为两个大素数p和q的乘积，b为一个正整数，那么定义f：
f (x )= x b mod n
(如果gcd（b,φ（n））=1，那么事实上这就是我们以下要说的RSA加密函数)
如果我们要构造一个公钥密码体制，仅给出一个单向的单射函数是不够的。从Alice的观点来看，并不需要E是单向的，因为它需要用有效的方式解密所收到的信息。因此，Alice应该拥有一个陷门，其中包含容易求出E的你函数的秘密信息。也就是说，Alice可以有效解密，因为它有额外的秘密知识，即SK，能够提供给你解密函数D。因此，我们称一个函数为一个陷门单向函数，如果它是一个单向函数，并在具有特定陷门的知识后容易求出其逆。
考虑上面的函数f (x) = xb mod n。我们能够知道其逆函数f -1有类似的形式f (x ) = xa mod n，对于合适的取值a。陷门就是利用n的因子分解，有效的算出正确的指数a（对于给定的b）。
为方便起见，我们把特定的某类陷门单向函数计为?。那么随机选取一个函数f属于?，作为公开加密函数；其逆函数f-1是秘密解密函数。那么公钥密码体制就能够实现了。
根据以上关于陷门单向函数的思想,学者们提出了许多种公钥加密的方法，它们的安全性都是基于复杂的数学难题。根据所基于的数学难题，至少有以下三类系统目前被认为是安全和有效的：大整数因子分解系统(代表性的有RSA)、椭园曲线离散对数系统(ECC)和离散对数系统(代表性的有DSA)。
§3 RSA算法
3.1简介
当前最着名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。它是一个基于数论的非对称(公开钥)密码体制，是一种分组密码体制。其名称来自于三个发明者的姓名首字母。它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的着名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。
RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。
该算法基于下面的两个事实,这些事实保证了RSA算法的安全有效性：
1)已有确定一个数是不是质数的快速算法；
2)尚未找到确定一个合数的质因子的快速算法。
3.2工作原理
1)任意选取两个不同的大质数p和q，计算乘积r=p*q；
2)任意选取一个大整数e，e与(p-1)*(q-1)互质，整数e用做加密密钥。注意：e的选取是很容易的，例如，所有大于p和q的质数都可用。
3)确定解密密钥d：d * e = 1 molo（p - 1）*（q - 1） 根据e、p和q可以容易地计算出d。
4)公开整数r和e，但是不公开d；
5)将明文P (假设P是一个小于r的整数)加密为密文C，计算方法为：
C = Pe molo r
6)将密文C解密为明文P，计算方法为：
P = Cd molo r
然而只根据r和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。
3.3简单实例
为了说明该算法的工作过程,我们下面给出一个简单例子,显然我们在这只能取很小的数字，但是如上所述，为了保证安全，在实际应用上我们所用的数字要大的多得多。
例：选取p=3, q=5，则r=15，（p-1）*（q-1）=8。选取e=11（大于p和q的质数），通过d * 11 = 1 molo 8，计算出d =3。
假定明文为整数13。则密文C为
C = Pe molo r
= 1311 molo 15
= 1,792,160,394,037 molo 15
= 7
复原明文P为：
P = Cd molo r
= 73 molo 15
= 343 molo 15
= 13
因为e和d互逆，公开密钥加密方法也允许采用这样的方式对加密信息进行"签名"，以便接收方能确定签名不是伪造的。
假设A和B希望通过公开密钥加密方法进行数据传输，A和B分别公开加密算法和相应的密钥，但不公开解密算法和相应的密钥。A和B的加密算法分别是ECA和ECB，解密算法分别是DCA和DCB，ECA和DCA互逆，ECB和DCB互逆。 若A要向B发送明文P，不是简单地发送ECB（P），而是先对P施以其解密算法DCA，再用加密算法ECB对结果加密后发送出去。
密文C为：
C = ECB（DCA（P））
B收到C后，先后施以其解密算法DCB和加密算法ECA，得到明文P：
ECA（DCB（C））
= ECA（DCB（ECB（DCA（P））））
= ECA（DCA（P））/*DCB和ECB相互抵消*/
=
P /*DCB和ECB相互抵消*/
这样B就确定报文确实是从A发出的，因为只有当加密过程利用了DCA算法，用ECA才能获得P，只有A才知道DCA算法，没 有人，即使是B也不能伪造A的签名。
3.4优缺点
3.4.1优点
RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。该算法的加密密钥和加密算法分开，使得密钥分配更为方便。它特别符合计算机网络环境。对于网上的大量用户，可以将加密密钥用电话簿的方式印出。如果某用户想与另一用户进行保密通信，只需从公钥簿上查出对方的加密密钥，用它对所传送的信息加密发出即可。对方收到信息后，用仅为自己所知的解密密钥将信息脱密，了解报文的内容。由此可看出，RSA算法解决了大量网络用户密钥管理的难题，这是公钥密码系统相对于对称密码系统最突出的优点。
3.4.2缺点
1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。
2)安全性, RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题。目前，人们已能分解140多个十进制位的大素数，这就要求使用更长的密钥，速度更慢；另外，目前人们正在积极寻找攻击RSA的方法，如选择密文攻击，一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：
( XM )d = Xd *Md mod n
前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way Hash Function对文档作HASH处理，或同时使用不同的签名算法。除了利用公共模数，人们还尝试一些利用解密指数或φ（n）等等攻击.
3)速度太慢,由于RSA的分组长度太大，为保证安全性，n至少也要600 bitx以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。为了速度问题,目前人们广泛使用单,公钥密码结合使用的方法,优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件,然后用RSA来给文件密钥加密,极好的解决了单钥密码的密钥分发问题。
§4结束语
目前，日益激增的电子商务和其它因特网应用需求使公钥体系得以普及，这些需求量主要包括对服务器资源的访问控制和对电子商务交易的保护，以及权利保护、个人隐私、无线交易和内容完整性（如保证新闻报道或股票行情的真实性）等方面。公钥技术发展到今天，在市场上明显的发展趋势就是PKI与操作系统的集成，PKI是“Public
Key Infrastructure”的缩写，意为“公钥基础设施”。公钥体制广泛地用于CA认证、数字签名和密钥交换等领域。
公钥加密算法中使用最广的是RSA。RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。目前为止，很多种加密技术采用了RSA算法，该算法也已经在互联网的许多方面得以广泛应用，包括在安全接口层（SSL）标准（该标准是网络浏览器建立安全的互联网连接时必须用到的）方面的应用。此外，RSA加密系统还可应用于智能IC卡和网络安全产品。
但目前RSA算法的专利期限即将结束，取而代之的是基于椭圆曲线的密码方案（ECC算法）。较之于RSA算法，ECC有其相对优点，这使得ECC的特性更适合当今电子商务需要快速反应的发展潮流。此外，一种全新的量子密码也正在发展中。
至于在实际应用中应该采用何种加密算法则要结合具体应用环境和系统，不能简单地根据其加密强度来做出判断。因为除了加密算法本身之外，密钥合理分配、加密效率与现有系统的结合性以及投入产出分析都应在实际环境中具体考虑。加密技术随着网络的发展更新，将有更安全更易于实现的算法不断产生，为信息安全提供更有力的保障。今后，加密技术会何去何从，我们将拭目以待。
参考文献：
[1] Douglas R.Stinson.《密码学原理与实践》.北京:电子工业出版社,2003,2:131-132
[2]西蒙.辛格.《密码故事》.海口:海南出版社,2001,1:271-272
[3]嬴政天下.加密算法之RSA算法.http://soft.winzheng.com/infoView/Article_296.htm，2003
[4]加密与数字签名.http://www.njt.cn/yumdq/dzsw/a2.htm
[5]黑客中级教程系列之十.http://www.qqorg.i-p.com/jiaocheng/10.html
㈡ RAS加密的数学原理
RSA算法是现今使用最广泛的公钥密码算法，也是号称地球上最安全的加密算法。在了解RSA算法之前，先熟悉下几个术语根据密钥的使用方法，可以将密码分为对称密码和公钥密码
对称加密：加密和解密使用同一种密钥的方式
非对称加密：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。
好多人都知道RSA加密的数学公式，但是不知道其的内部运作，那么我们以下就详细分析一波！
图1，mod就是取余的意思，上面公式的意思是3的多少次方除以17余数为12。由图2可知道3的13次方的时候就满足图1的公式。由图2的可知，公式后面的余数都是不一样的，而且是1-16。当我们好奇试试3^17%17时候，结果就是3，好明显等于了3^1%17的结果，那么我们称 3为17的原根 。
思考：任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？
计算这个值的方式叫做欧拉函数，使用：Φ(n)表示
计算8的欧拉函数，和8互质的 1 、2、 3 、4、 5 、6、 7 、8 所以 φ(8) = 4
计算7的欧拉函数，和7互质的 1、2、3、4、5、6 、7 所以 φ(7) = 6
计算56的欧拉函数：φ(56) = φ(8)* φ(7) = 4 * 6 = 24
如果两个正整数，除了1以外，没有其他公因数，我们就称这两个数是 互质关系 （coprime）。
一、当n是质数的时候，φ(n)=n-1。
二、如果n可以分解成两个互质的整数之积，如n=A*B则： φ(A*B)=φ(A)*φ(B)
根据以上两点得到：如果N是两个质数P1 和 P2的乘积则：φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)
如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。如图3所示：
我们可以设置互质的数如m=5和n=3，那么φ(3) = 3-1=2，5^2%3=1。所以上面的公式是成立的。（有兴趣的可以试多一点数字，注意是互质的两个数）
欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。如图4所示：
注意：满足第3步的时候，m必须要小于n。
如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除。那么d就是e对于x的“模反元素”。如图6所示：
公钥： n和e
私钥： n和d
明文: m
密文: c
1、n会非常大，长度一般为1024个二进制位。（目前人类已经分解的最大整数，232个十进制位，768个二进制位）
2、由于需要求出φ(n)，所以根据欧函数特点，最简单的方式n ，由两个质数相乘得到:
质数：p1、p2 Φ(n) = (p1 -1) * (p2 - 1)
3、最终由φ(n)得到e 和 d 。
总共生成6个数字：p1、p2、n、φ(n)、e、d
除了公钥用到了n和e其余的4个数字是不公开的。目前破解RSA得到d的方式如下：
1、要想求出私钥 d 。由于e*d = φ(n)*k + 1。要知道e和φ(n);
2、e是知道的，但是要得到 φ(n)，必须知道p1和 p2。
3、由于 n=p1*p2。只有将n因数分解才能算出。
㈢ 加密技术有哪几种
采用密码技术对信息加密，是最常用的安全交易手段。在电子商务中获得广泛应用的加密技术有以下两种：
（1）公共密钥和私用密钥（public key and private key）
这一加密方法亦称为RSA编码法，是由Rivest、Shamir和Adlernan三人所研究发明的。它利用两个很大的质数相乘所产生的乘积来加密。这两个质数无论哪一个先与原文件编码相乘，对文件加密，均可由另一个质数再相乘来解密。但要用一个质数来求出另一个质数，则是十分困难的。因此将这一对质数称为密钥对(Key Pair)。在加密应用时，某个用户总是将一个密钥公开，让需发信的人员将信息用其公共密钥加密后发给该用户，而一旦信息加密后，只有用该用户一个人知道的私用密钥才能解密。具有数字凭证身份的人员的公共密钥可在网上查到，亦可在请对方发信息时主动将公共密钥传给对方，这样保证在Internet上传输信息的保密和安全。
（2）数字摘要(digital digest)
这一加密方法亦称安全Hash编码法（SHA:Secure Hash Algorithm）或MD5(MD Standards for Message Digest)，由Ron Rivest所设计。该编码法采用单向Hash函数将需加密的明文“摘要”成一串128bit的密文，这一串密文亦称为数字指纹(Finger Print)，它有固定的长度，且不同的明文摘要成密文，其结果总是不同的，而同样的明文其摘要必定一致。这样这摘要便可成为验证明文是否是“真身”的“指纹”了。
上述两种方法可结合起来使用，数字签名就是上述两法结合使用的实例。
3.2数字签名(digital signature)
在书面文件上签名是确认文件的一种手段，签名的作用有两点，一是因为自己的签名难以否认，从而确认了文件已签署这一事实；二是因为签名不易仿冒，从而确定了文件是真的这一事实。数字签名与书面文件签名有相同之处，采用数字签名，也能确认以下两点：
a. 信息是由签名者发送的。
b. 信息在传输过程中未曾作过任何修改。
这样数字签名就可用来防止电子信息因易被修改而有人作伪；或冒用别人名义发送信息；或发出（收到）信件后又加以否认等情况发生。
数字签名采用了双重加密的方法来实现防伪、防赖。其原理为：
（1） 被发送文件用SHA编码加密产生128bit的数字摘要（见上节）。
（2） 发送方用自己的私用密钥对摘要再加密，这就形成了数字签名。
（3） 将原文和加密的摘要同时传给对方。
（4） 对方用发送方的公共密钥对摘要解密，同时对收到的文件用SHA编码加密产生又一摘要。
（5） 将解密后的摘要和收到的文件在接收方重新加密产生的摘要相互对比。如两者一致，则说明传送过程中信息没有被破坏或篡改过。否则不然。
3.3数字时间戳(digital time-stamp)
交易文件中，时间是十分重要的信息。在书面合同中，文件签署的日期和签名一样均是十分重要的防止文件被伪造和篡改的关键性内容。
在电子交易中，同样需对交易文件的日期和时间信息采取安全措施，而数字时间戳服务(DTS：digital time-stamp service)就能提供电子文件发表时间的安全保护。
数字时间戳服务（DTS）是网上安全服务项目，由专门的机构提供。时间戳（time-stamp）是一个经加密后形成的凭证文档，它包括三个部分：1）需加时间戳的文件的摘要(digest)，2）DTS收到文件的日期和时间，3）DTS的数字签名。
时间戳产生的过程为：用户首先将需要加时间戳的文件用HASH编码加密形成摘要，然后将该摘要发送到DTS，DTS在加入了收到文件摘要的日期和时间信息后再对该文件加密（数字签名），然后送回用户。由Bellcore创造的DTS采用如下的过程：加密时将摘要信息归并到二叉树的数据结构；再将二叉树的根值发表在报纸上，这样更有效地为文件发表时间提供了佐证。注意，书面签署文件的时间是由签署人自己写上的，而数字时间戳则不然，它是由认证单位DTS来加的，以DTS收到文件的时间为依据。因此，时间戳也可作为科学家的科学发明文献的时间认证。
3.4数字凭证(digital certificate, digital ID)
数字凭证又称为数字证书，是用电子手段来证实一个用户的身份和对网络资源的访问的权限。在网上的电子交易中，如双方出示了各自的数字凭证，并用它来进行交易操作，那么双方都可不必为对方身份的真伪担心。数字凭证可用于电子邮件、电子商务、群件、电子基金转移等各种用途。
数字凭证的内部格式是由CCITT X.509国际标准所规定的，它包含了以下几点：
(1) 凭证拥有者的姓名，
(2) 凭证拥有者的公共密钥，
(3) 公共密钥的有效期，
(4) 颁发数字凭证的单位，
(5) 数字凭证的序列号（Serial number），
(6) 颁发数字凭证单位的数字签名。
数字凭证有三种类型：
(1) 个人凭证(Personal Digital ID)：它仅仅为某一个用户提供凭证，以帮助其个人在网上进行安全交易操作。个人身份的数字凭证通常是安装在客户端的浏览器内的。并通过安全的电子邮件（S/MIME）来进行交易操作。
(2) 企业（服务器）凭证（Server ID）：它通常为网上的某个Web服务器提供凭证，拥有Web服务器的企业就可以用具有凭证的万维网站点(Web Site)来进行安全电子交易。有凭证的Web服务器会自动地将其与客户端Web浏览器通信的信息加密。
(3) 软件（开发者）凭证（Developer ID）：它通常为Internet中被下载的软件提供凭证，该凭证用于和微软公司Authenticode技术（合法化软件）结合的软件，以使用户在下载软件时能获得所需的信息。
上述三类凭证中前二类是常用的凭证，第三类则用于较特殊的场合，大部分认证中心提供前两类凭证，能提供各类凭证的认证中心并不普遍
㈣ 常见密码技术简介
##
密码技术在网络传输安全上的应用
随着互联网电子商务和网络支付的飞速发展，互联网安全已经是当前最重要的因素之一。作为一名合格的软件开发工程师，有必要了解整个互联网是如何来保证数据的安全传输的，本篇文章对网络传输安全体系以及涉及到的算法知识做了一个简要的介绍，希望大家能够有一个初步的了解。
###密码技术定义
简单的理解，密码技术就是编制密码和破译密码的一门技术，也即是我们常说的加密和解密。常见的结构如图：
其中涉及到的专业术语：
1.秘钥：分为加密秘钥和解密秘钥，两者相同的加密算法称为对称加密，不同的称为非对称加密；
2.明文：未加密过的原文信息，不可以被泄露；
3.密文：经过加密处理后的信息，无法从中获取有效的明文信息；
4.加密：明文转成密文的过程，密文的长度根据不同的加密算法也会有不同的增量；
5.解密：密文转成明文的过程；
6.加密/解密算法：密码系统使用的加密方法和解密方法；
7.攻击：通过截获数据流、钓鱼、木马、穷举等方式最终获取秘钥和明文的手段。
###密码技术和我们的工作生活息息相关
在我们的日常生活和工作中，密码技术的应用随处可见，尤其是在互联网系统上。下面列举几张比较有代表性的图片，所涉及到的知识点后面都会一一讲解到。
1.12306旧版网站每次访问时，浏览器一般会提示一个警告，是什么原因导致的？ 这样有什么风险呢？
2.360浏览器浏览HTTPS网站时，点开地址栏的小锁图标会显示加密的详细信息，比如网络的话会显示```AES_128_GCM、ECDHE_RSA```，这些是什么意思？
3.在Mac系统的钥匙串里有很多的系统根证书，展开后有非常多的信息，这些是做什么用的？
4.去银行开通网上支付都会附赠一个U盾，那U盾有什么用呢？
##如何确保网络数据的传输安全
接下来我们从实际场景出发，以最常见的客户端Client和服务端Server传输文件为例来一步步了解整个安全体系。
####1. 保密性
首先客户端要把文件送到服务端，不能以明文形式发送，否则被黑客截获了数据流很容易就获取到了整个文件。也就是文件必须要确保保密性，这就需要用到对称加密算法。
** 对称加密： **加密和解密所使用的秘钥相同称为对称加密。其特点是速度快、效率高，适用于对较大量的数据进行加密。常见的对称加密算法有DES、3DES、AES、TDEA、RC5等，让我们了解下最常见的3DES和AES算法：
** DES(Data Encryption Standard)： **1972年由美国IBM研制，数学原理是将明文以8字节分组（不足8位可以有不同模式的填充补位），通过数学置换和逆置换得到加密结果，密文和明文长度基本相同。秘钥长度为8个字节，后有了更安全的一个变形，使用3条秘钥进行三次加密，也就是3DES加密。
**3DES：**可以理解为对明文进行了三次DES加密，增强了安全程度。
** AES(Advanced Encryption Standard)： **2001年由美国发布，2002年成为有效标准，2006年成为最流行的对称加密算法之一。由于安全程度更高，正在逐步替代3DES算法。其明文分组长度为16字节，秘钥长度可以为16、24、32(128、192、256位)字节，根据秘钥长度，算法被称为AES-128、AES-192和AES-256。
对称加密算法的入参基本类似，都是明文、秘钥和模式三个参数。可以通过网站进行模拟测试：[http://tool.chacuo.net/crypt3des]()。其中的模式我们主要了解下ECB和CBC两种简单模式，其它有兴趣可自行查阅。
** ECB模式(Electronic Codebook Book)： **这种模式是将明文分成若干小段，然后对每一段进行单独的加密，每一段之间不受影响，可以单独的对某几段密文进行解密。
** CBC模式(Cipher Block Chaining)： **这种模式是将明文分成若干小段，然后每一段都会和初始向量(上图的iv偏移量)或者上一段的密文进行异或运算后再进行加密，不可以单独解密某一断密文。
** 填充补位： **常用为PKCS5Padding，规则为缺几位就在后面补几位的所缺位数。，比如明文数据为```/x01/x01/x01/x01/x01/x01```6个字节，缺2位补```/x02```，补完位```/x01/x01/x01/x01/x01/x01/x02/x02```。解密后也会按照这个规则进行逆处理。需要注意的是：明文为8位时也需要在后面补充8个```/x08```。
####2. 真实性
客户端有了对称秘钥，就需要考虑如何将秘钥送到服务端，问题跟上面一样：不能以明文形式直接传输，否则还是会被黑客截获到。这里就需要用到非对称加密算法。
** 非对称加密： **加密和解密秘钥不同，分别称为公开秘钥(publicKey)和私有秘钥(privateKey)。两者成对出现，公钥加密只能用私钥解密，而私钥加密也只能用公钥加密。两者不同的是：公钥是公开的，可以随意提供给任何人，而私钥必须保密。特点是保密性好，但是加密速度慢。常见的非对称加密算法有RSA、ECC等；我们了解下常见的RSA算法：
** RSA(Ron Rivest、Adi Shamir、Leonard Adleman)： **1977年由麻省理工学院三人提出，RSA就是他们三个人的姓氏开头字母拼在一起组成的。数学原理是基于大数分解。类似于```100=20x5```，如果只知道100的话，需要多次计算才可以试出20和5两个因子。如果100改为极大的一个数，就非常难去试出真正的结果了。下面是随机生成的一对公私钥:
这是使用公钥加密后结果：
RSA的这种特性就可以保证私钥持有者的真实性，客户端使用公钥加密文件后，黑客就算截获到数据因为没有私钥也是无法解密的。
** Tips： **
+** 不使用对称加密，直接用RSA公私钥进行加密和解密可以吗？ **
答案：不可以，第一是因为RSA加密速度比对称加密要慢几十倍甚至几百倍以上，第二是因为RSA加密后的数据量会变大很多。
+** 由服务端生成对称秘钥，然后用私钥加密，客户端用公钥解密这样来保证对称秘钥安全可行吗？ **
答案：不可行，因为公钥是公开的，任何一个人都可以拿到公钥解密获取对称秘钥。
####3. 完整性
当客户端向服务端发送对称秘钥加密后的文件时，如果被黑客截获，虽然无法解密得到对称秘钥。但是黑客可以用服务端公钥加密一个假的对称秘钥，并用假的对称秘钥加密一份假文件发给服务端，这样服务端会仍然认为是真的客户端发送来的，而并不知道阅读的文件都已经是掉包的了。
这个问题就需要用到散列算法，也可以译为Hash。常见的比如MD4、MD5、SHA-1、SHA-2等。
** 散列算法(哈希算法)： **简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。而且该过程是不可逆的，无法通过摘要获得原文。
** SHA-1(Secure Hash Algorithm 1)： **由美国提出，可以生成一个20字节长度的消息摘要。05年被发现了针对SHA-1的有效攻击方法，已经不再安全。2010年以后建议使用SHA-2和SHA-3替代SHA-1。
** SHA-2(Secure Hash Algorithm 2)： **其下又分为六个不同算法标准：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA512/256。其后面数字为摘要结果的长度，越长的话碰撞几率越小。SHA-224的使用如下图：
客户端通过上面的散列算法可以获取文件的摘要消息，然后用客户端私钥加密后连同加密的文件发给服务端。黑客截获到数据后，他没有服务端私钥无法获取到对称秘钥，也没有客户端私钥无法伪造摘要消息。如果再像上面一样去掉包文件，服务端收到解密得到摘要消息一对比就可以知道文件已经被掉包篡改过了。
这种用私钥对摘要消息进行加密的过程称之为数字签名，它就解决了文件是否被篡改问题，也同时可以确定发送者身份。通常这么定义：
** 加密： **用公钥加密数据时称为加密。
** 签名： **用私钥加密数据时称为签名。
####4. 信任性
我们通过对称加密算法加密文件，通过非对称加密传输对称秘钥，再通过散列算法保证文件没被篡改过和发送者身份。这样就安全了吗？
答案是否定的，因为公钥是要通过网络送到对方的。在这期间如果出现问题会导致客户端收到的公钥并不一定是服务端的真实公钥。常见的** 中间人攻击 **就是例子：
** 中间人攻击MITM(Man-in-the-MiddleAttack)： **攻击者伪装成代理服务器，在服务端发送公钥证书时，篡改成攻击者的。然后收到客户端数据后使用攻击者私钥解密，再篡改后使用攻击者私钥签名并且将攻击者的公钥证书发送给服务器。这样攻击者就可以同时欺骗双方获取到明文。
这个风险就需要通过CA机构对公钥证书进行数字签名绑定公钥和公钥所属人，也就是PKI体系。
** PKI(Privilege Management Infrastructure)： **支持公钥管理并能支持认证、加密、完整性和可追究性的基础设施。可以说整个互联网数据传输都是通过PKI体系进行安全保证的。
** CA(Certificate Authority)： **CA机构就是负责颁发证书的，是一个比较公认的权威的证书发布机构。CA有一个管理标准：WebTrust。只有通过WebTrust国际安全审计认证，根证书才能预装到主流的浏览器而成为一个全球可信的认证机构。比如美国的GlobalSign、VeriSign、DigiCert，加拿大的Entrust。我国的CA金融方面由中国人民银行管理CFCA，非金融CA方面最初由中国电信负责建设。
CA证书申请流程：公司提交相应材料后，CA机构会提供给公司一张证书和其私钥。会把Issuer,Public key,Subject,Valid from,Valid to等信息以明文的形式写到证书里面，然后用一个指纹算法计算出这些数字证书内容的一个指纹，并把指纹和指纹算法用自己的私钥进行加密。由于浏览器基本都内置了CA机构的根证书，所以可以正确的验证公司证书指纹（验签），就不会有安全警告了。
但是：所有的公司其实都可以发布证书，甚至我们个人都可以随意的去发布证书。但是由于浏览器没有内置我们的根证书，当客户端浏览器收到我们个人发布的证书后，找不到根证书进行验签，浏览器就会直接警告提示，这就是之前12306打开会有警告的原因。这种个人发布的证书，其实可以通过系统设置为受信任的证书去消除这个警告。但是由于这种证书机构的权威性和安全性难以信任，大家最好不要这么做。
我们看一下网络HTTPS的证书信息：
其中比较重要的信息：
签发机构：GlobalSign Root CA；
有效日期：2018-04-03到2019-05-26之间可用；
公钥信息：RSA加密，2048位；
数字签名：带 RSA 加密的 SHA-256 ( 1.2.840.113549.1.1.11 )
绑定域名：再进行HTTPS验证时，如果当前域名和证书绑定域名不一致，也会出现警告；
URI：在线管理地址。如果当前私钥出现了风险，CA机构可以在线吊销该证书。
####5. 不可抵赖性
看起来整个过程都很安全了，但是仍存在一种风险：服务端签名后拒不承认，归咎于故障不履行合同怎么办。
解决方法是采用数字时间戳服务：DTS。
** DTS(digital time-stamp)： **作用就是对于成功的电子商务应用，要求参与交易各方不能否认其行为。一般来说，数字时间戳产生的过程为：用户首先将需要加时间戳的文件用Hash算法运算形成摘要，然后将该摘要发送到DTS。DTS在加入了收到文件摘要的日期和事件信息后再对该文件进行数字签名，然后送达用户。
####6. 再次认证
我们有了数字证书保证了身份的真实性，又有了DTS提供的不可抵赖性。但是还是不能百分百确定使用私钥的就是合法持有者。有可能出现被别人盗用私钥进行交易的风险。
解决这个就需要用到强口令、认证令牌OTP、智能卡、U盾或生物特征等技术对使用私钥的当前用户进行认证，已确定其合法性。我们简单了解下很常见的U盾。
** USB Key(U盾)： **刚出现时外形比较像U盘，安全性能像一面盾牌，取名U盾。其内部有一个只可写不可读的区域存储着用户的私钥(也有公钥证书)，银行同样也拥有一份。当进行交易时，所有涉及到私钥的运算都在U盾内部进行，私钥不会泄露。当交易确认时，交易的详细数据会显示到U盾屏幕上，确认无误后通过物理按键确认就可以成功交易了。就算出现问题黑客也是无法控制U盾的物理按键的，用户可以及时取消避免损失。有的U盾里面还有多份证书，来支持国密算法。
** 国密算法： **国家密码局针对各种算法制定了一些列国产密码算法。具体包括：SM1对称加密算法、SM2公钥算法、SM3摘要算法、SM4对称加密算法、ZUC祖冲之算法等。这样可以对国产固件安全和数据安全进行进一步的安全控制。
## HTTPS分析
有了上面的知识，我们可以尝试去分析下HTTPS的整个过程，用Wireshark截取一次HTTPS报文：
Client Hello: 客户端发送Hello到服务端443端口，里面包含了随机数、客户端支持的加密算法、客户端的TLS版本号等；
Server Hello: 服务端回应Hello到客户端，里面包含了服务端选择的加密套件、随机数等；
Certificate： 服务端向客户端发送证书
服务端计算对称秘钥：通过ECDH算法得到对称秘钥
客户端计算对称秘钥：通过ECDH算法得到对称秘钥
开始用对称秘钥进行加密传输数据
其中我们又遇到了新的算法：DH算法
** DH(Diffie-Hellman)： **1976年由Whitefield与Martin Hellman提出的一个奇妙的秘钥交换协议。这个机制的巧妙在于可以通过安全的方式使双方获得一个相同的秘钥。数学原理是基于原根的性质，如图：
*** DH算法的用处不是为了加密或解密消息，而是用于通信双方安全的交换一个相同的秘钥。 ***
** ECDH： **基于ECC(椭圆曲线密码体制)的DH秘钥交换算法，数学原理是基于椭圆曲线上的离散对数问题。
** ECDHE： **字面少了一个E，E代表了临时。在握手流程中，作为服务器端，ECDH使用证书公钥代替Pb，使用自身私钥代替Xb。这个算法时服务器不发送server key exchange报文，因为发送certificate报文时，证书本身就包含了Pb信息。
##总结
| 算法名称 | 特点 | 用处 | 常用算法名 |
| --- | :--- | :---: | ---: |
| 对称加密 | 速度快，效率高| 用于直接加密文件 | 3DES、AES、RC4 |
| 非对称加密 | 速度相对慢，但是确保安全 | 构建CA体系 | RSA、ECC |
| 散列算法 | 算出的摘要长度固定，不可逆 | 防止文件篡改 | SHA-1、SHA-2 |
| DH算法 | 安全的推导出对称秘钥 | 交换对称秘钥 | ECDH |
----
㈤ RSA 加密算法（原理篇）
前几天看到一句话，“我们中的很多人把一生中最灿烂的笑容大部分都献给了手机和电脑屏幕”。心中一惊，这说明了什么？手机和电脑已经成为了我们生活中的一部分，所以才会有最懂你的不是你，也不是你男朋友，而是大数据。
如此重要的个人数据，怎样才能保证其在互联网上的安全传输呢？当然要靠各种加密算法。说起加密算法，大家都知道有哈希、对称加密和非对称加密了。哈希是一个散列函数，具有不可逆操作；对称加密即加密和解密使用同一个密钥，而非对称加密加密和解密自然就是两个密钥了。稍微深入一些的，还要说出非对称加密算法有DES、3DES、RC4等，非对称加密算法自然就是RSA了。那么当我们聊起RSA时，我们又在聊些什么呢？今天笔者和大家一起探讨一下，有不足的地方，还望各位朋友多多提意见，共同进步。
RSA简介：1976年由麻省理工学院三位数学家共同提出的，为了纪念这一里程碑式的成就，就用他们三个人的名字首字母作为算法的命名。即 罗纳德·李维斯特 （Ron Rivest）、 阿迪·萨莫尔 （Adi Shamir）和 伦纳德·阿德曼 （Leonard Adleman）。
公钥：用于加密，验签。
私钥：解密，加签。
通常知道了公钥和私钥的用途以后，即可满足基本的聊天需求了。但是我们今天的主要任务是来探究一下RSA加解密的原理。
说起加密算法的原理部分，肯定与数学知识脱不了关系。
我们先来回忆几个数学知识：
φn = φ(A*B)=φ(A)*φ(B)=(A-1)*(B-1)。
这个公式主要是用来计算给定一个任意的正整数n，在小于等于n的正整数中，有多少个与n构成互质的关系。
其中n=A*B，A与B互为质数，但A与B本身并不要求为质数，可以继续展开，直至都为质数。
在最终分解完成后，即 φ(N) = φ(p1)*φ(p2)*φ(p3)... 之后，p1，p2，p3都是质数。又用到了欧拉函数的另一个特点，即当p是质数的时候，φp = p - 1。所以有了上面给出的欧拉定理公式。
举例看一下：
计算15的欧拉函数，因为15比较小，我们可以直接看一下，小于15的正整数有 1、2、3、4、5、6、7、8、9、10、11、12、13、14。和15互质的数有1、2、4、7、8、11、13、14一共四个。
对照我们刚才的欧拉定理： 。
其他感兴趣的，大家可以自己验证。
之所以要在这里介绍欧拉函数，我们在计算公钥和私钥时候，会用到。
如果两个正整数m 和 n 互质，那么m 的 φn 次方减1，可以被n整除。
其中 .
其中当n为质数时，那么 上面看到的公式就变成了
mod n 1.
这个公式也就是着名的 费马小定理 了。
如果两个正整数e和x互为质数，那么一定存在一个整数d，不止一个，使得 e*d - 1 可以被x整除，即 e * d mode x 1。则称 d 是 e 相对于 x的模反元素。
了解了上面所讲的欧拉函数、欧拉定理和模反元素后，就要来一些化学反应了，请看图：
上面这幅图的公式变化有没有没看明白的，没看明白的咱们评论区见哈。
最终我们得到了最重要的第5个公式的变形，即红色箭头后面的：
mod n m。
其中有几个关系，需要搞明白，m 与 n 互为质数，φn = x，d 是e相对于x的模反元素。
有没有看到一些加解密的雏形。
从 m 到 m。 这中间涵盖了从加密到解密的整个过程，但是缺少了我们想要的密文整个过程。
OK，下面引入本文的第四个数学公式：
我们来看一下整个交换流程：
1、客户端有一个数字13，服务端有一个数字15;
2、客户端通过计算 3的13次方 对 17 取余，得到数字12; 将12发送给服务端；同时服务端通过计算3的15次方，对17取余，得到数字6，将6发送给客户端。至此，整个交换过程完成。
3、服务端收到数字12以后，继续计算，12的15次方 对 17取余，得到 数字10。
4、客户端收到数字 6以后，继续计算，6的13次方 对 17 取余，得到数字 10。
有没有发现双方，最终得到了相同的内容10。但是这个数字10从来没有在网络过程中出现过。
好，讲到这里，可能有些人已经恍然大悟，这就是加密过程了，但是也有人会产生疑问，为什么要取数字3 和 17 呢，这里还牵涉到另一个数学知识，原根的问题。即3是17的原根。看图
有没有发现规律，3的1~16次方，对17取余，得到的整数是从1~16。这时我们称3为17的原根。也就是说上面的计算过程中有一组原根的关系。这是最早的迪菲赫尔曼秘钥交换算法。
解决了为什么取3和17的问题后，下面继续来看最终的RSA是如何产生的：
还记得我们上面提到的欧拉定理吗，其中 m 与 n 互为质数，n为质数，d 是 e 相对于 φn的模反元素。
当迪菲赫尔曼密钥交换算法碰上欧拉定理会产生什么呢？
我们得到下面的推论：
好，到这里我们是不是已经看到了整个的加密和解密过程了。
其中 m 是明文；c 是密文； n 和 e 为公钥；d 和 n 为私钥 。
其中几组数字的关系一定要明确：
1、d是e 相对于 φn 的模反元素，φn = n-1，即 e * d mod n = 1.
2、m 小于 n，上面在讲迪菲赫尔曼密钥交换算法时，提到原根的问题，在RSA加密算法中，对m和n并没有原根条件的约束。只要满足m与n互为质数，n为质数，且m < n就可以了。
OK，上面就是RSA加密算法的原理了，经过上面几个数学公式的狂轰乱炸，是不是有点迷乱了，给大家一些时间理一下，后面会和大家一起来验证RSA算法以及RSA为什么安全。
㈥ 密码学基础（三）：非对称加密（RSA算法原理）
加密和解密使用的是两个不同的秘钥，这种算法叫做非对称加密。非对称加密又称为公钥加密，RSA只是公钥加密的一种。
现实生活中有签名，互联网中也存在签名。签名的作用有两个，一个是身份验证，一个是数据完整性验证。数字签名通过摘要算法来确保接收到的数据没有被篡改，再通过签名者的私钥加密，只能使用对应的公钥解密，以此来保证身份的一致性。
数字证书是将个人信息和数字签名放到一起，经由CA机构的私钥加密之后生成。当然，不经过CA机构，由自己完成签名的证书称为自签名证书。CA机构作为互联网密码体系中的基础机构，拥有相当高级的安全防范能力，所有的证书体系中的基本假设或者前提就是CA机构的私钥不被窃取，一旦 CA J机构出事，整个信息链将不再安全。
CA证书的生成过程如下：
证书参与信息传递完成加密和解密的过程如下：
互质关系：互质是公约数只有1的两个整数，1和1互质，13和13就不互质了。
欧拉函数：表示任意给定正整数 n，在小于等于n的正整数之中，有多少个与 n 构成互质关系，其表达式为：
其中，若P为质数，则其表达式可以简写为：
情况一：φ(1)=1
1和任何数都互质，所以φ(1)=1；
情况二：n 是质数， φ(n)=n-1
因为 n 是质数，所以和小于自己的所有数都是互质关系，所以φ(n)=n-1；
情况三：如果 n 是质数的某一个次方，即 n = p^k ( p 为质数，k 为大于等于1的整数)，则φ(n)=(p-1)p^(k-1)
因为 p 为质数，所以除了 p 的倍数之外，小于 n 的所有数都是 n 的质数；
情况四：如果 n 可以分解成两个互质的整数之积，n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)
情况五：基于情况四，如果 p1 和 p2 都是质数，且 n=p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)=(p1-1)(p2-1)
而 RSA 算法的基本原理就是欧拉函数中的第五种情况，即： φ(n)=(p1-1)(p2-1);
如果两个正整数 a 和 n 互质，那么一定可以找到整数 b，使得 ab-1 被 n 整除，或者说ab被n除的余数是1。这时，b就叫做a的“模反元素”。欧拉定理可以用来证明模反元素必然存在。
可以看到，a的 φ(n)-1 次方，就是a对模数n的模反元素。
n=p x q = 3233，3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。
在实际使用中，一般场景下选择1024位长度的数字，更高安全要求的场景下，选择2048位的数字，这里作为演示，选取p=61和q=53；
因为n、p、q都为质数，所以φ(n) = (p-1)(q-1)=60×52= 3120
注意，这里是和φ(n) 互互质而不是n！假设选择的值是17，即 e=17；
模反元素就是指有一个整数 d，可以使得 ed 被 φ(n) 除的余数为1。表示为：(ed-1)=φ(n) y --> 17d=3120y+1，算出一组解为(2753,15)，即 d=2753，y=-15，也就是(17 2753-1)/3120=15。
注意，这里不能选择3119，否则公私钥相同？？
公钥：(n,e)=(3233,2753)
私钥：(n,d)=(3233,17)
公钥是公开的，也就是说m=p*q=3233是公开的，那么怎么求e被？e是通过模反函数求得，17d=3120y+1，e是公开的等于17，这时候想要求d就要知道3120，也就是φ(n)，也就是φ(3233)，说白了，3233是公开的，你能对3233进行因数分解，你就能知道d，也就能破解私钥。
正常情况下，3233我们可以因数分解为61*53，但是对于很大的数字，人类只能通过枚举的方法来因数分解，所以RSA安全性的本质就是：对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
人类已经分解的最大整数是：
这个人类已经分解的最大整数为232个十进制位，768个二进制位，比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。所以实际使用中的1024位秘钥基本安全，2048位秘钥绝对安全。
网上有个段子：
已经得出公私钥的组成：
公钥：(n,e)=(3233,2753)
私钥：(n,d)=(3233,17)
加密的过程就是
解密过程如下：
其中 m 是要被加密的数字，c 是加密之后输出的结果，且 m < n ，其中解密过程一定成立可以证明的，这里省略证明过程。
总而言之，RSA的加密就是使用模反函数对数字进行加密和求解过程，在实际使用中因为 m < n必须成立，所以就有两种加密方法：
对称加密存在虽然快速，但是存在致命的缺点就是秘钥需要传递。非对称加密虽然不需要传递秘钥就可以完成加密和解密，但是其致命缺点是速度不够快，不能用于高频率，高容量的加密场景。所以才有了两者的互补关系，在传递对称加密的秘钥时采用非对称加密，完成秘钥传送之后采用对称加密，如此就可以完美互补。
㈦ RSA加密原理
RSA加密是一种非对称加密。可以在不直接传递密钥的情况下，完成解密。这能够确保信息的安全性，避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程，分别称为公钥和私钥。公钥加密--私钥解密，私钥加密--公钥解密
在 整数 中， 离散对数 是一种基于 同余 运算和 原根 的一种 对数 运算。而在实数中对数的定义 log b a 是指对于给定的 a 和 b ，有一个数 x ，使得 b x = a 。相同地在任何群 G 中可为所有整数 k 定义一个幂数为 b K ，而 离散对数 log b a 是指使得 b K = a 的整数 k 。
当3为17的 原根 时，我们会发现一个规律
对 正整数 n，欧拉函数是小于或等于n的正整数中与n 互质 的数的数目（因此φ(1)=1）。有以下几个特点
服务端根据生成一个随机数15，根据 3 15 mod 17 计算出6，服务端将6传递给客户端，客户端生成一个随机数13，根据 3 13 mod 17 计算出12后，将12再传回给服务端，客户端收到服务端传递的6后，根据 6 13 mod 17 计算出 10 ，服务端收到客户端传递的12后，根据 12 15 mod 17 计算出 10 ，我们会发现我们通过 迪菲赫尔曼密钥交换 将 10 进行了加密传递
说明：
安全性：
除了 公钥 用到 n 和 e ，其余的4个数字是 不公开 的（p1、p2、φ(n)、d）
目前破解RSA得到的方式如下：
缺点
RSA加密 效率不高 ，因为是纯粹的数学算法，大数据不适合RSA加密，所以我们在加密大数据的时候，我们先用 对称加密 算法加密大数据得到 KEY ，然后再用 RSA 加密 KEY ，再把大数据和KEY一起进行传递
因为Mac系统内置了OpenSSL（开源加密库），所以我们开源直接在终端进行RSA加密解密
生成RSA私钥，密钥名为private.pem,密钥长度为1024bit
因为在iOS中是无法使用 .pem 文件进行加密和解密的，需要进行下面几个步骤
生成一个10年期限的crt证书
crt证书格式转换成der证书