非对称加密算法--RSA加密原理 RSA加密的原理——为什么被公钥加密的可以被私钥解密？ RSA加密的原理——为什么被公钥加密的可以被私钥解密？ 公钥加密私钥解密&私钥加密公钥解密
密码学是在编码与破译的斗争实践中逐步发展起来的,并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。
密码学发展史
在说RSA加密算法之前， 先说下密码学的发展史。其实密码学的诞生，就是为了运用在战场，在公元前，战争之中出现了秘密书信。在中国历史上最早的加密算法的记载出自于周朝兵书《六韬.龙韬》中的《阴符》和《阴书》。在遥远的西方，在希罗多德（Herodotus）的《历史》中记载了公元前五世纪，希腊城邦和波斯帝国的战争中，广泛使用了移位法进行加密处理战争通讯信息。
相传凯撒大帝为了防止敌人窃取信息，就使用加密的方式传递信息。那么当时的加密方式非常的简单，就是对二十几个罗马字母建立一张对照表，将明文对应成为密文。那么这种方式其实持续了很久。甚至在二战时期，日本的电报加密就是采用的这种原始加密方式。
早期的密码学一直没有什么改进，几乎都是根据经验慢慢发展的。直到20世纪中叶，由香农发表的《秘密*的通信理论》一文，标志着加密算法的重心转移往应用数学上的转移。于是，逐渐衍生出了当今重要的三类加密算法：非对称加密、对称加密以及哈希算法（HASH严格说不是加密算法，但由于其不可逆性，已成为加密算法中的一个重要构成部分）。
1976年以前，所有的加密方法都是同一种模式：加密和解密使用同样规则（简称"密钥"），这被称为"对称加密算法"，使用相同的密钥，两次连续的对等加密运算后会回复原始文字，也有很大的安全隐患。
1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。也正是因为这个算法的产生，人类终于可以实现非对称加密了：A给B发送信息
- B要先生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
- A获取B的公钥，然后用它对信息加密。
- B得到加密后的信息，用私钥解密。
理论上如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是232个十进制位，也就是768个二进制位，因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全，当然量子计算机除外。
RSA算法的原理
下面进入正题，解释RSA算法的原理，其实RSA算法并不难，只需要一点数论知识就可以理解。
欧拉函数
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）计算这个值的方法就叫做欧拉函数，以φ(n)表示。
- 计算8的欧拉函数，和8互质的 1、2、3、4、5、6、7、8
φ(8) = 4
如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则φ(n) = φ(p^k) = p^k - p^(k-1)。也就是φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4 - 计算7的欧拉函数，和7互质的 1、2、3、4、5、6、7
φ(7) = 6
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。 - 计算56的欧拉函数
φ(56) = φ(8) * φ(7) = 4 * 6 = 24
如果n可以分解成两个互质的整数之积，即 n = p * k ，则φ(n) = φ(p * k) = φ(p1)*φ(p2)
欧拉定理：如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。
费马小定理：欧拉定理的特殊情况，如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。
模反元素
还剩下最后一个概念，模反元素：如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除，或者说ed被x除的余数是1。
那么d就是e相对于x的模反元素。
等式转换
-
根据欧拉定理
-
由于1^k ≡ 1，等号左右两边都来个k次方
-
由于1* m ≡ m，等号左右两边都乘上m
根据模反元素，因为e*d 一定是x的倍数加1。所以如下：
通过多次的等式转换。终于可以将这两个等式进行合并了！如下：
这个等式成立有一个前提！就是关于模反元素的，就是当整数e和φ(n)互质！一定有一个整数d是e相对于φ(n)的模反元素。
我们可以测试一下。
m取值为4
n取值为15
φ(n)取值为8
e 如果取值为3
d 可以为 11、19…(模反元素很明显不止一个，其实就是解二元一次方程)
如果你测试了，那么你可以改变m的值试一下，其实这个等式不需要m和n 互质。只要m小于n 等式依然成立。
这里需要注意的是，我们可以看做 m 通过一系列运算得到结果仍然是 m。这一系列运算中，分别出现了多个参数n、φ(n)、e还有d。
m 的 e乘上d 次方为加密运算，得到结果 c
c 模以 n 为解密运算，得到结果 m
这似乎可以用于加密和解密。但这样，加密的结果会非常大。明文数据将非常小（虽然RSA用于加密的数据也很小，但是没这么大悬殊），真正的RSA要更加强大，那么RSA是怎么演变来的呢？？
早期很多数学家也停留在了这一步！直到1967年迪菲赫尔曼密钥交换打破了僵局！
迪菲赫尔曼密钥交换
这个密钥交换当时轰动了整个数学界！而且对人类密码学的发展非常重要，因为这个伟大的算法能够拆分刚才的等式。当非对称加密算法没有出现以前，人类都是用的对称加密。所以密钥的传递，就必须要非常小心。
迪菲赫尔曼密钥交换 就是解决了密钥传递的保密性，我们来看一下
假设一个传递密钥的场景。算法就是用3 的次方去模以17。 三个角色
- 服务器 随机数 15
这个15只有服务器才知道。通过算法得到结果 6 因为 3的15次方 mod 17 = 6 。然后将结果 6 公开发送出去，拿到客户端的 12 ，然后用12^15 mod 17 得到结果10(10就是交换得到的密钥) - 客户端 随机数13
客户端用3 的 13次方 mod 17 = 12 然后将得到的结果12公布出去。
拿到服务器的 6 ，然后用6^13 mod 17 得到结果10(10就是交换得到的密钥) - 第三者
第三者只能拿到6 和 12 ，因为没有私密数据13、15，所以它没法得到结果10。
为什么 6的13次方会和12的15次方得到一样的结果呢?因为这就是规律，我们可以用小一点的数字测试一下3^3 mod 17 = 10和10 ^ 2 mod 17 ； 3 ^ 2 mod 17 = 9和9^3 mod 17结果都是15。迪菲赫尔曼密钥交换最核心的地方就在于这个规律
RSA的诞生
现在我们知道了m^e % n = c是加密，c^d % n = m是解密，m就是原始数据，c是密文，公钥是n和e，私钥是n和d，所以只有n和e是公开的。加密时我们也要知道φ(n)的值，最简单的方式是用两个质数之积得到，别人想破解RSA也要知道φ(n)的值，只能对n进行因数分解，那么我们不想m被破解，n的值就要非常大，就是我们之前说的，长度一般为1024个二进制位，这样就很安全了。但是据说量子计算机(用于科研，尚未普及)可以破解，理论上量子计算机的运行速度无穷快，大家可以了解一下。
以上就是RSA的数学原理
检验RSA加密算法
我们用终端命令演示下这个加密、解密过程。
假设m = 12(随便取值，只要比n小就OK)，n = 15(还是随机取一个值)，φ(n) = 8，e = 3(只要和φ(n)互质就可以)，d = 19（3d - 1 = 8，d也可以为3,11等等，也就是d = (8k + 1)/3 ）
终端分别以m=12，7输入结果
OpenSSL进行RSA的命令运行
Mac可以直接使用OpenSSL，首先进入相应文件夹
- 生成公私钥
// 生成RSA私钥，文件名为private.pem，长度为1024bit
openssl genrsa -out private.pem 1024
// 从私钥中提取公钥
openssl rsa -in private.pem -pubout -out publick.pem
// 查看刚刚生成好的私钥
cat private.pem
// 查看刚刚生成好的公钥
cat publick.pem
我们可以看到base64编码，明显私钥二进制很大，公钥就小了很多。
这时候我们的文件夹内已经多了刚刚生成好的公私钥文件了
// 将私钥转换为明文
openssl rsa -in private.pem -text -out private.txt
里面就是P1、P2还有KEY等信息。
- 对文件进行加密、解密
// 编辑文件message内容为hello Vincent!!!
// 刚刚的public.pem写成了publick.pem(哎。。。)
$ vi message.txt
$ cat message.txt
hello Vincent!!!
// 通过公钥加密数据时，使用encrypt对文件进行加密
$ openssl rsautl -encrypt -in message.txt -inkey publick.pem -pubin -out enc.txt
// 此时查看该文件内容为乱码
$ cat enc.txt
j��E]a��d�kUE�&<
��I*��V/��pL[���ˋ�O�+�-�M��K�ܱ�&⪅ծO��2���o34�:�$���6��C�L��,b�'M�S�k�0���A��3%�[I���1�����ps"%
// 通过私钥解密数据
$ openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
// 已成功解密，正确显示文件内容
$ cat dec.txt
hello Vincent!!!
// 通过私钥加密数据时，要使用sign对文件进行重签名
$ openssl rsautl -sign -in message.txt -inkey private.pem -out enc.bin
// 此时查看该文件内容同样为乱码
$ cat enc.bin
{���Ew�3�1E��,8-OA2�Is�:���:�ԅ@MU����
�i1B���#��6���ׂm�D(�t#/��� �ہ�������ݬ>(�>�^@�C��3�ӸMQт�O%
// 通过公钥解密数据
$ openssl rsautl -verify -in enc.bin -inkey publick.pem -pubin -out dec.bin
// 已成功解密，正确显示文件内容
$ cat dec.bin
hello Vincent!!!
RSA用途及特点
到这里，大家都知道RSA通过数学算法来加密和解密，效率比较低，所以一般RSA的主战场是加密比较小的数据，比如对大数据进行对称加密，再用RSA给对称加密的KEY进行加密，或者加密Hash值，也就是数字签名。
关于RSA数字签名后面再慢慢阐述。该文章为记录本人的学习路程，希望能够帮助大家，也欢迎大家点赞留言交流！！！https://blog.csdn.net/wjiabin/article/details/85228078
RSA加密的原理——为什么被公钥加密的可以被私钥解密？
目录
一，RSA 数学理论基础
二，RSA实现原理
三，RSA加密的过程
四，参考文献
引言
在密码学最开始，都是使用的普通加密模式
A 用加密规则加密了字符串m 然后发给B
B 用A的加密规则来解密，得到原始信息m
在这个过程中A必须把自己的加密规则告诉B，否则B无法解密这段密文，但是如果把加密规则也告诉B，在传递密钥的过程中，可能就会被拦截获取，这就是最大的问题。
所以，后来又3位数学家提供了一种算法，实现非对称加密，后来算法也以他们三个的首字母命名，R（Rivest）S（Shamir ）A（Adleman ）算法。
最开始，我一直理解不了为什么公钥加密的可以被私钥解密，一直停留在使用层面，直到今天看到一篇博客，才解决了心中的疑惑。
一，RSA 必备数学理论基础
要理解整个rsa的流程，需要以下数学基础
1，互质关系
两个正整数，除1以外，再没有别的公因子。 比如 2 和3， 2和 9。
2，欧拉函数
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）
计算上面这个多少个的函数就被成为欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。
3，欧拉定理
由上面的欧拉函数可以经过一系列的推导，得到欧拉定理
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
4，特殊情况——费马小定理
欧拉定理的特殊情况，当第二个数n为质数的情况。
假设正整数a与质数p互质，因为质数p的φ§等于p-1，
5，模反元素
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
比如a = 3 ,n = 5,则一定有（a*b）%n =1 ,即3b -1 = 5y,即一定存在一个数2，可以满足上式。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1M5YCtQO-1596075907121)(https://www.z4a.net/images/2018/08/25/image939be76f8b625518.png)]
6,快速幂取模计算
如果有两个大数a,b，ab可能是一个计算机无法表示的大数，则(ab)%c的值如何计算？
这里可以使用快速幂取模算法。
java代码如下：
/**
* 快速幂取模 计算 (a^b) %c
* @param a
* @param b
* @param c
* @return 计算结果
*/
private static int quick(int a,int b,int c) {
int ans=1; //记录结果
a=a%c; //预处理，使得a处于c的数据范围之下
while(b!=0)
{
if((b&1)==1){ //1即是0000000000000001，判断个位是否是1.如果b的二进制位是1，那么我们的结果是要参与运算的
ans=(ans*a)%c;
}
b>>=1; //二进制的移位操作，相当于每次除以2，用二进制看，就是我们不断的遍历b的二进制位
a=(a*a)%c; //不断的加倍
}
return ans;
}
参考了文章
https://blog.csdn.net/ltyqljhwcm/article/details/53043646
二，RSA实现原理
第一步，选择两个不等质数p,q（实际密钥一般为1024位或2048位）
这里我们选择 61 和53。
第二步，计算乘积n
n = p*q = 3233 (二进制110010100001，只有12位)
第三步，计算n的欧拉函数φ(n)
φ(n) = φ§*φ(q)= (p-1)(q-1) = 3120 。一个质数p的欧拉函数等于p-1
第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
取e = 17 (实际应用中，常常选择65537)。
第五步，计算e对于φ(n)的模反元素d。
即找出一个d满足 ed互质，且对于φ(n) 取模为1 ，即 ed = 1 (mod φ(n))。
即 ed -1 = kφ(n) ，带入上面已知条件：
17d -1 = k3120 即 17x +3120y = 1 (据说可以使用 扩展欧几里得算法求解)
这里直接给出答案 d = 2753。
第六步，将n和e封装成公钥，n和d封装成私钥。
代入本次的推导过程中的数字，n = 3233,e = 17, d=2753。公钥为（3233，17），私钥为（3233，2723）。
加密使用 （3233，17），解密使用（3233，2723）。
第七步，分析，私钥的获取
由六可以看出来，公钥和私钥的区别其实只是d，也就是说d的推导是否可以在已知n，e的情况下推导出来。
由第五步，要得出d,已知n,e。需要φ(n)。
由第三部，要得出φ(n)，需要p，q。
而已知n=p*q。而n已知，只需要分解n因子即可。
结论：只要n可以被分解，公私玥加密即可被破解。
第八步，n可以被分解吗？
在本例中，3233可以很快被破解，但是实际应用中，两个大质数的积是不容易被分解出来的
例如：
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
是以下两个质数的乘积：
a:
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
b:
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
人类已经分解的最大整数（232个十进制位，768个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。而RSA加密一般使用1024位或者2048位，基本可以理解为不可破解
三，RSA加密的过程
1，公钥（n,e）加密
所有字符串都可以使用ascil码/unicode值来表示，假设一个字符 m = a，ascii码为65,需要满足 m < n 对他进行加密。
m^e ≡ c (mod n),c为加密字符串
n = 3233,e = 17。 上式可以表示为： (65^17)%3233 = c ,c = 2790。
2,私钥（n,d）解密
(n,d) = (3233,2723) 。在拿到c = 2790之后，进行以下操作：
c^d ≡ m (mod n) 即可得到m 。
推导,m = (2790^2723) %3233 ，在这里使用 必备知识六中的快速幂取模，可以轻松得到答案，m = 65。
3，证明，####
略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略。
四，参考文献
1，http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
2，http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
https://blog.csdn.net/doujinlong1/article/details/82051986
公钥加密私钥解密&私钥加密公钥解密
公钥加密*
1、公钥加密*用于保密性时，就是公钥加密，私钥解密。 因为公钥是可以公开了， 那么任何人都可以使用公钥对信息进行加密，但是只有持有私钥的人才能正确解密。这样就保证了信息的保密性，因为只有私钥持有者才能正确解密。
2、公钥加密*用于认证性时，比如数字签名，即私钥持有者对信息进行签名，验证者可以根据公开的公钥进行验证签名是否正确和有效，即实现了认证性，以及不可抵赖性。
先明确一下概念：
公钥加密私钥解密，也可以说是 "公共密钥加密系统 "
私钥加密公钥解密,一般不这么说，应叫 "私钥签名,公钥验证 ",也可以说是“公共密钥签名系统”
再来说一下 "公共密钥签名系统 "目的:(如果晕就多看几遍，这个没搞清，后面的代码就更晕)
A欲传（信息）给B，但又怕B不确信该信息是A发的。
1．A选计算（信息）的HASH值，如用MD5方式计算,得到：[MD5（信息）]
2．然后用自已的私钥加密HASH值，得到：[私钥（MD5（信息））]
3．最后将信息与密文一起传给B：传给B：[（信息） + 私钥（MD5（信息））]
B接到 ：[（信息） + 私钥（MD5（信息））]
1．先用相同的HASH算法算出（信息）的HASH值，这里也使用MD5方式
得到： [MD5（信息）!]
2. 再用A的公钥解密 [ 私钥（MD5（信息））]
[公钥(私钥（MD5（信息））)] = [（MD5（信息）]
如能解开,证明该 [ 私钥（MD5（信息））]是A发送的
3.再比效[MD5（信息）!]与[（MD5（信息）]
如果相同,表示（信息）在传递过程中没有被他人修改过
https://blog.csdn.net/pthill/article/details/83670755