一、对称加密算法

在RSA算法出现之前，人们一直用的是对称加密算法，什么是对称加密算法：
加解密双方使用同一套密钥，即甲用密钥加密，乙还得用与甲同样的密钥来减密，这就存在极大的安全隐患。
常用的对称加减密算法有：DES, 3DES,AES,SM1（国密中的对称算法，密钥长度是128位）等。

二、非对称加密算法

针对对称算法的不足，后来有三位大牛想出了一套非对称算法，也就是现在我们常说的RSA算法。这个算法里用到了很多数学知识，起到数学，感觉就不是一般人能研究的，不过人类生活中很多东西都与数学息息相关，没有数学就没有现在美好的生活，所以下面简单说明几个数学概念。

1、互质关系

质数， 素数，这两个名词很多人在数学习课本里都听过，好像在中学的数学课本里就有了，它们表示同一个东西，只是两种不同叫法，那什么是质数？
任意一个数如果只能被1和它本身整除，这个数就是质数。 那什么是互质关系呢？如果两个正整数，除了1以外，没有其他公因子，那这两个数就是互质关系。
通过互质关系的概念，不难发现两个质数肯定是互质关系，但不一定互质关系的两个数一定都是是质数，比如15与32。以下是别人关于互质关系的总结： 　　a. 任意两个质数构成互质关系，比如13和61。 　　b. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。 　　c. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。 　　d. 1和任意一个自然数是都是互质关系，比如1和99。 　　e. p是大于1的整数，则p和p-1构成互质关系，比如57和56。 　　f. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

2、欧拉函数

何为欧拉函数？
在任意的正整数n，请问在小于等于n的正整数中，有多少个与n构成互质关系，计算这个值的方法，就叫做欧拉函数，以φ(n)表示。
比如正整数8，φ(8)=？，很快算出有1、3、5、7，所以φ(8)=4 根据前面对质数，互质关系，欧拉函数的介绍，大牛们把欧拉函数又推导出下面几个等式也成立：
1）如果n可以分解成两个互质的整数之积，即n=p×q，则有：φ(n)=φ(pq)=φ(p)φ(q);
2）一个数如果是质数，则小于它的所有正整数与它都是互质数；所以如果一个数p是质数，则有：φ(p)=p-1。
3）如果n可以分解成两个互质的整数之积n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)
4）如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
φ(p^k)=p^k-p^(k-1)=p^k(1-1/p).
比如： φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4; φ(8) = φ(2^3)=2^3(1-1/2)=4
5）因为任意一个大于1的正整数，都可以写成一系列质数的积：
n=p1^k1p2^k2…pr^kr，根据第三条定律，则φ(n)=φ(p1^k1)φ(p2^k2)…φ(pr^kr)
再根据第四条定律，则φ(n)=p1^k1p2^k2…pr^kr(1-1/p1)(1-1/p2)…(1-1/pr)，也就等于
φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pr)，这就是欧拉函数的通用计算公式，举例：1323的欧拉函数，计算过程如下：
φ(1323)=φ(3^3x7^2)=1323(1-1/3)(1-1/7)=756

3、欧拉定理

欧拉函数的用处，在于欧拉定理。
如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：
a^φ(n)≡1mod(n)
比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。

4、模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
根据欧拉定理有：
a^φ(n)=axa^φ(n-1)≡1mod(n)，令b=a^φ(n-1)，则ab≡1mod(n)，这里b就是a的模反元素。 比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。

RSA密钥生成

有了前面的理论，就可以进行RSA密钥的生成。
1）首先任意选择两个不相等的质数p和q
2）计算p和q的乘积n，令p=61, q=53，则n = 61×53 = 3233
3233写成二进制是110010100001,一共有12位, 所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位，重要场合则为2048位。
3）计算n的欧拉函数φ(n)
由前面的公式，则φ(n) = (p-1)(q-1)
φ(3233)=60×52=3120
4）随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质
在1到3120之间，随机选择了17，e=17。（实际应用中，常常选择65537。）
5）计算e对于φ(n)的模反元素d
根据前面模反元素公式e^φ(N)=exe^φ(N-1)≡1mod(N)，这个公式中的N等于这里的φ(n), 令d=e^φ(N-1), 则ed≡1mod(N)，即
ed ≡ 1 (mod φ(n))
这个式子等价于
ed - 1 = kφ(n)
于是，找到模反元素d，实质上就是对下面这个二元一次方程求解
ex + φ(n)y = 1
已知 e=17, φ(n)=3120
17x + 3120y = 1
这个方程可以用”扩展欧几里得算法”求解，此处省略具体的计算过程，有兴趣可以研究下这个算法，算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。至此所有计算完成。
6）将n和e封装成公钥，n和d封装成私钥
n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）
实际应用中，公钥和私钥的数据都采用ASN.1格式表达，ASN.1是抽象语法标记(Abstract Syntax Notation One)，它是一个 ISO/ITU-T国际标准，简单说就是加一些头部信息，有兴趣可以熟悉下ASN.1。

RSA算法的可靠性

回顾上面的密钥生成步骤，一共出现六个数字：
p
　　q
　　n
　　φ(n)
　　e
　　d
这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。
那么，有无可能在已知n和e的情况下，推导出d？
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有将n因数分解，才能算出p和q。
结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。
可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科这样写道： "对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。 假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。 只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。" 举例来说，你可以对3233进行因数分解（61×53），但是你没法对下面这个整数进行因数分解。
12301866845301177551304949
　　58384962720772853569595334
　　79219732245215172640050726
　　36575187452021997864693899
　　56474942774063845925192557
　　32630345373154826850791702
　　61221429134616704292143116
　　02221240479274737794080665
　　351419597459856902143413
它等于这样两个质数的乘积：
33478071698956898786044169
　　84821269081770479498371376
　　85689124313889828837938780
　　02287614711652531743087737
　　814467999489
　　　　×
　　36746043666799590428244633
　　79962795263227915816434308
　　76426760322838157396665112
　　79233373417143396810270092
　　798736308917
事实上，这大概是人类已经分解的最大整数（232个十进制位，768个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。

加密和减密

有了公钥和密钥，就能进行加密和解密了。
（1）加密要用公钥 (n,e)
公钥 (n,e) 对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
所谓”加密”，就是算出下式的c：
m^e ≡ c (mod n)
公钥是 (3233, 17)，m假设是65，那么可以算出下面的等式：
65^17 ≡ 2790 (mod 3233)
于是，c等于2790，即加密后的密文
（2）解密要用私钥(n,d)
用私钥(3233, 2753) 进行解密。可以证明，下面的等式一定成立：
c^d ≡ m (mod n)
也就是说，c的d次方除以n的余数为m。现在，c等于2790，私钥是(3233, 2753)，那么：
2790^2753 ≡ 65 (mod 3233)
这样就算出了原文65，至此，”加密–解密”的整个过程全部完成。
我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。 你可能会问，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；
另一种是先选择一种”对称性加密算法”（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。

私钥减密的证明

这个证明具体我也没有细研究，看得也稀里糊涂，总之又是数学，下面是摘自别人的，作为了解。 最后，我们来证明，为什么用私钥解密，一定可以正确地得到m。也就是证明下面这个式子： 　　cd ≡ m (mod n) 因为，根据加密规则 　　ｍe ≡ c (mod n) 于是，c可以写成下面的形式： 　　c = me - kn 将c代入要我们要证明的那个解密规则： 　　(me - kn)d ≡ m (mod n) 它等同于求证 　　med ≡ m (mod n) 由于 　　ed ≡ 1 (mod φ(n)) 所以 　　ed = hφ(n)+1 将ed代入： 　　mhφ(n)+1 ≡ m (mod n) 接下来，分成两种情况证明上面这个式子。 （1）m与n互质。 根据欧拉定理，此时 　　mφ(n) ≡ 1 (mod n) 得到 　　(mφ(n))h × m ≡ m (mod n) 原式得到证明。 （2）m与n不是互质关系。 此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。 以 m = kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立： 　　(kp)q-1 ≡ 1 (mod q) 进一步得到 　　[(kp)q-1]h(p-1) × kp ≡ kp (mod q) 即 　　(kp)ed ≡ kp (mod q) 将它改写成下面的等式 　　(kp)ed = tq + kp 这时t必然能被p整除，即 t=t'p 　　(kp)ed = t'pq + kp 因为 m=kp，n=pq，所以 　　med ≡ m (mod n) 原式得到证明。

RSA算法在实际中的运用

前面说了一堆，实际上都是对数学理论的理解分析，看过可以大致了解下RSA中的数学美吧，知道其中的原由即可。
我们要对一段信息进行RSA加密，通常是用公钥去密，用私钥去减密。当然，我就不按常理走，用私钥去加密，用公钥能不能减，答案当然是能，它们是可逆的，其实私钥加密在后面会讲到它的用途，它一般用于签名。
下面主要从两个方面来介绍RSA在实际中的运用，并且都以RSA2048为例子作介绍。

1.RSA的公私钥加减密

跟DES，AES一样，　RSA也是一个块加密算法（ block cipher algorithm），总是在一个固定长度的块上进行操作。但跟AES等不同的是，　block length是跟key length 以及所使用的填充模式　有关的。
RSA的填充方式，目前通常有三种：
1) RSA_PKCS1_PADDING
输入必须 比 RSA 钥模长(modulus) 短至少11个字节, 也就是　RSA_size(rsa) – 11
如果输入的明文过长，必须切割，　然后填充。
2）RSA_PKCS1_OAEP_PADDING
输入必须 比 RSA 钥模长(modulus) 短至少41个字节, 也就是RSA_size(rsa) – 41
3）RSA_NO_PADDING
这个是不做填充，输入可以和RSA钥模长一样长，如果输入的明文过长，必须切割，　然后填充，这里填充通常是在明文的前面填充零，解密后的明文也会包括前面填充的零。
这里要说一下，RSA加减密有“裸”与“国际范”两种，下面分别从这两个方面作介绍：
1)“裸”
这里的“裸”就是针对有没有padding而言的，有时我们经常遇到，自己写的算法，加密或签名后，对方那边解不开或验证失败，原因都是因为双方padding的方式不同导致的。
2)“国际范”，很多编程言语，比如java，c#等等，都有对应的加密包，我们直接调用里面的函数就可以实现各种加解密，签名验证，证书生成等各种功能，它们都是标准的算法，所以对加密都是严格按照要求来的，也就是明文块不够模长度时，要用padding的方式进行填充，一般默认的padding都是PKCS#1。
另外“国际范”还有严格的文档规范，比如PKCS #1 v1.5规范中有这样的要求：
”[RFC2313] PKCS #1: RSA Encryption Version 1.5“的”8.1 Encryption-block formatting“节提供了详细的说明，原文如下：
“`
8.1 Encryption-block formatting A block type BT, a padding string PS, and the data D shall be
formatted into an octet string EB, the encryption block. EB = 00 || BT || PS || 00 || D . (1) The block type BT shall be a single octet indicating the structure of
the encryption block. For this version of the document it shall have
value 00, 01, or 02. For a private- key operation, the block type
shall be 00 or 01. For a public-key operation, it shall be 02. The padding string PS shall consist of k-3-||D|| octets. For block
type 00, the octets shall have value 00; for block type 01, they
shall have value FF; and for block type 02, they shall be
pseudorandomly generated and nonzero. This makes the length of the
encryption block EB equal to k.
“`
简单说来，PKCS #1 v1.5规定的填充格式为：
EB = 00 || BT || PS || 00 || D
D: data （指待处理数据，即填充前的原始数据）
PS: padding string （填充字符串）
BT: block type （数据块类型）
EB: encryption block （待加密的数据块，经过填充后结果）
||: 表示连接操作 （X||Y表示将X和Y的内容连接到一起）
“填充块类型”BT决定了紧挨着的”填充字符串”PS的内容。
BT的可能取值包括00, 01和02：
A）针对私钥处理的数据，BT取值为00或01;
* BT取值为00时，PS为全00的字符串
* BT取值为01时，PS为全FF的字符串，通过填充得到的整数会足够大，可以阻止某些攻击，因此也是推荐的填充方式.
B）针对公钥处理的数据，BT取值为02；
* 使用伪随机的16进制字符串填充PS，而且每次操作进行填充的伪随机书都是独立的。
重点来了，针对公钥处理的数据，其填充内容为伪随机的16进制字符串，每次操作的填充内容都不一样。这就是为什么每次使用公钥加密数据得到的结果都不一样了。
另外，注意到D前面还有一个00，这个00与开头的那个00都是标记，通过00可以知道那里是实际的data，那里是padding，这也说明了一点，我们padding的内容中除了全是00，其他情况里不能再含有00的随机数，什么意思，比如针对公钥处理的数据，PS是随机数，那么随机数中不能含有00的数据，否则就没法判断那里开始是data，所以，一切反动派都是纸老虎嘛，加密就是最初那些人定义的一套游戏规则。 好了，上面说了加密时要按规则padding，那解密呢，自然也是按规则去解密，也就是说先对module长度的密文解密，解出module长度的明文，然后再根据那些标记把PS和标记去除，剩下的就是我们实际的明文。

2.RSA的签名与验证

对于RSA签名与验证，它是用来验证数据的完整性的，比如我要发一串报文信息，这个报文信息可长可段，对方怎么知道这个报文有没有被修改，那就可以用附在报文后面的签名信息对其进行验证，如果验证一致，就说明收到的报文信息是可靠的。
那怎么签名呢，需要先对报文计算一下摘要，通常的算法有MD5，SHA1,SHA256,SHA512，通常用得比较多的是SHA1与SHA2（SHA256），这里以SHA256为例说明，SHA256算法算出来的摘要长度是32字节，也就是256位。
最后，再用RSA私钥对这个摘要进行加密（注意，这里是用私钥加密），当然加密的规则与前面介绍一样，要按规则进行添加相应的标记与padding数据，这样算出来的就是最终的签名数据了，到这里，我们知道签名包括两部分，一是对原文算摘要，二是对算好的摘要用私钥加密。 这样是不是就结束了，貌似是可以了，其实这也不够“国际范”，在标准规范里对签名，也有一点要求，除前面padding的要求，还有一个专门针对签名而定义的。
有时我们经常对别人发来的一串签名验证，对公钥解出来的数据，发现不是32字节（SHA2算法），比32字节多了好多，这里多出来的，就是游戏规则里定义的。其实在验证时一直有一个疑问，不知大家有没有想到，对方把报文+签名的数据发过来，我虽然有对方的公开的公钥，但我不知道对方摘要算法是什么啊，是MD5，SHA1还是SHA2，这个疑问就在这个游戏规则里定义了，官方给不同的摘要算法都起了一个标记OID，这个OID是用BER编码的，关于BER编码规则，大家可以自己了解。
经过上面的分析，我们可以知道签名是由那些部分组成，签名是遵循TLV格式（前面介绍的padding规则），而且摘要是经过BER编码的。
常见的HASH算法在用于RSA签名时的BER数据编码格式为： MD2 1.2.840.113549.2.2 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 02 05 00 04 10 || H. MD4 1.2.840.113549.2.4 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 04 05 00 04 10 || H. MD5 1.2.840.113549.2.5 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10 || H SHA1 1.3.14.3.2.26 30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H SHA224 2.16.840.1.101.3.4.2.4 不确定是否这个OID 30 2D 30 0d 06 09 60 86 48 01 65 03 04 02 04 05 00 04 1C || H SHA256 2.16.840.1.101.3.4.2.1 30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H SHA384 2.16.840.1.101.3.4.2.2 30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 || H SHA512 2.16.840.1.101.3.4.2.3 30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H SM3 1.2.156.197.1.504 不确定是否这个OID 30 30 30 0c 06 08 2a 81 1C 81 45 01 83 78 05 00 04 20 || H 我们重点看下SHA256的：
SHA256
2.16.840.1.101.3.4.2.1 《—-这就是OID标识，具体怎么算的可以参考国际范的文档
30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H
《—-这就是BER格式的摘要了，H就是实际的32字节摘要，只是在前面多了这么一串头信息。这就是我们通常用公钥解密出来的摘要，实际在有私钥签名，也就是对这一串数据用前面介绍的padding方式进行padding，通常用的块类型是00 01 FF FF….00+D。
https://www.cnblogs.com/jintianhu/p/5051169.html