㈠ rsa加密和解密的理论依据是什么
以前也接触过RSA加密算法，感觉这个东西太神秘了，是数学家的事，和我无关。但是，看了很多关于RSA加密算法原理的资料之后，我发现其实原理并不是我们想象中那么复杂，弄懂之后发现原来就只是这样而已..
学过算法的朋友都知道，计算机中的算法其实就是数学运算。所以，再讲解RSA加密算法之前，有必要了解一下一些必备的数学知识。我们就从数学知识开始讲解。
必备数学知识
RSA加密算法中，只用到素数、互质数、指数运算、模运算等几个简单的数学知识。所以，我们也需要了解这几个概念即可。
素数
素数又称质数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。这个概念，我们在上初中，甚至小学的时候都学过了，这里就不再过多解释了。
互质数
网络上的解释是：公因数只有1的两个数，叫做互质数。；维基网络上的解释是：互质，又称互素。若N个整数的最大公因子是1，则称这N个整数互质。
常见的互质数判断方法主要有以下几种：
两个不同的质数一定是互质数。例如，2与7、13与19。
一个质数，另一个不为它的倍数，这两个数为互质数。例如，3与10、5与 26。
相邻的两个自然数是互质数。如 15与 16。
相邻的两个奇数是互质数。如 49与 51。
较大数是质数的两个数是互质数。如97与88。
小数是质数，大数不是小数的倍数的两个数是互质数。例如 7和 16。
2和任何奇数是互质数。例如2和87。
1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。
辗转相除法。
指数运算
指数运算又称乘方计算，计算结果称为幂。nm指将n自乘m次。把nm看作乘方的结果，叫做”n的m次幂”或”n的m次方”。其中，n称为“底数”，m称为“指数”。
模运算
模运算即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上，当两个整数除以同一个正整数，若得相同余数，则二整数同余。
两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作: a ≡ b (mod m)；读作：a同余于b模m，或者，a与b关于模m同余。例如：26 ≡ 14 (mod 12)。
RSA加密算法
RSA加密算法简史
RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
公钥与密钥的产生
假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥：
随意选择两个大的质数p和q，p不等于q，计算N=pq。
根据欧拉函数，求得r = (p-1)(q-1)
选择一个小于 r 的整数 e，求得 e 关于模 r 的模反元素，命名为d。（模反元素存在，当且仅当e与r互质）
将 p 和 q 的记录销毁。
(N,e)是公钥，(N,d)是私钥。Alice将她的公钥(N,e)传给Bob，而将她的私钥(N,d)藏起来。
加密消息
假设Bob想给Alice送一个消息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：
ne ≡ c (mod N)
计算c并不复杂。Bob算出c后就可以将它传递给Alice。
解密消息
Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：
cd ≡ n (mod N)
得到n后，她可以将原来的信息m重新复原。
解码的原理是：
cd ≡ n e·d(mod N)
以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。由费马小定理可证明（因为p和q是质数）
n e·d ≡ n (mod p) 和 n e·d ≡ n (mod q)
这说明（因为p和q是不同的质数，所以p和q互质）
n e·d ≡ n (mod pq)
签名消息
RSA也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话，那么她可以为她的消息计算一个散列值(Message digest)，然后用她的密钥(private key)加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。
RSA加密算法的安全性
当p和q是一个大素数的时候，从它们的积pq去分解因子p和q，这是一个公认的数学难题。然而，虽然RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。
1994年彼得·秀尔（Peter Shor）证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰RSA和相关的衍生算法。（即依赖于分解大整数困难性的加密算法）
另外，假如N的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的N。1997年后开发的系统，用户应使用1024位密钥，证书认证机构应用2048位或以上。
RSA加密算法的缺点
虽然RSA加密算法作为目前最优秀的公钥方案之一，在发表三十多年的时间里，经历了各种攻击的考验，逐渐为人们接受。但是，也不是说RSA没有任何缺点。由于没有从理论上证明破译RSA的难度与大数分解难度的等价性。所以，RSA的重大缺陷是无法从理论上把握它的保密性能如何。在实践上，RSA也有一些缺点：
产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密；
分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，。
㈡ 理论分析和举例说明RSA的加密和解密是互逆的
由于没有办法打出fai这个希腊字母 n的欧拉函数我用@（n）来表示
^ 代表幂的意思
e*d=1(mod @(n))
m为明文 c为密文
加密：c=m^e(mod n)
解密：m=c^d(mod n)
证明加密解密互逆也就是证明：
m=(m^e)^d(mod n) //把加密式子过程的c 带到解密过程那个式子中
也就是证明 m=m^(e*d) (mod n)
因为 e*d=1(mod @(n)) 可以推导出 e*d=k*@（n）+1
所以m=m*（k*@（n）+1） （mod n）
也就可以写出m=m*m^(k*@(n)) (mod n)
因为根据费马定理 m^（@(n)）=1 (mod n)
所以m^(k*@(n)) =1^k（mod n）=1（mod n）
m*m^(k*@(n)) (mod n)=m*1 （mod n）=m（mod n）证明就ok了
主要把握2点： 费马定理
公私钥关于@（n）互逆 就松松搞定
㈢ rsa加密算法
rsa加密算法如下：
算法原理：
RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥
㈣ RSA加密解密算法的证明
1. 选择两个质数 p, q
2. 设 n =p * q
3. 求出n的欧拉函数 f = (p-1)*(q-1)
4. 在[2, f)的范围内随机找一个与f互质的数 e 作为公钥的指数
5. 算出私钥指数d，d为公钥指数e对 f 的一个模反元素，即 ed = kf +1 (k为正整数)
6. 将(n, e)封装成公钥，将(n, d)封装成私钥
1. 设被加密的数为m, m为小于n的非负整数
2. 算出 c = (m^e) % n ，则 c 即为密文
算出 (c^d)%n , 即为被加密的数m，证明如下。
因为 c=m^e - n*g，其中g为非负整数，
所以 (c^d)%n = [ (m^e - n*g) ^ d ] % n
展开多项式后将n的整数倍的项去除，得到
[( m^e )^d] % n
=[ m^(e*d) ] % n
=[ m^(k*f+1) ] % n
=[ m * m^(k*f) ] % n
={ m * [ (m^f) ^ k] } % n
接下来分三种情况讨论：
第一种情况：m=0或者m=1
则 { m * [ (m^f) ^ k] } % n = m
第二种情况：m>1，且m与n互质
根据 欧拉定理 ，m^f = h*n+1，其中h为正整数
则 { m * [ (m^f) ^ k] } % n
={ m * [ ( h*n+1 ) ^ k] } % n
={ m * [ i*n + 1 ] } % n (其中i为展开指数多项式后合并n的同类项得到的正整数)
=m%n
=m (因为m<n)
第三种情况：m>1，且m与n不互质
因为n=p*q, 且p, q均为质数，则 m=j*p或者j*q, 其中j为正整数
当m=j*p时, 因为m<n, 所以m与q互质
（证明：如果m, q不互质，则m含有质因数q，因为p与q互质, 所以 j 含有质因数p, 这与m<n矛盾）
根据欧拉定理 m^(q-1)=x*q+1 ，其中x为正整数
则 { m * [ (m^f) ^ k] } % n
= { m * [ ( m^[(p-1)*(q-1)] ) ^ k] } % n
={ m * [ m^(q-1)^(p-1)^k ] } % n
={ j * p * [ ( x*q+1 )^ (p-1)^k ] } % n
={ j * p * [ y*q + 1 ] } % n (其中y为展开指数多项式后合并q的同类项得到的正整数)
=(j*p*y*q + m ) %n
=(j*y*n+m) % n
=m
同理，当m=j*q时也成立。
证明完毕。
RSA解密正确性证明_国科大网安二班的博客-CSDN博客
https://blog.csdn.net/weixin_46395886/article/details/114700012#:~:text=RSA%E8%A7%A3%E5%AF%86%E6%AD%A3%E7%A1%AE%E6%80%A7%E8%AF%81%E6%98%8E%20%E5%85%88%E6%8F%8F%E8%BF%B0%E4%B8%80%E4%B8%8BRSA%E5%AF%86%E7%A0%81%E4%BD%93%E5%88%B6%EF%BC%9A%20RSA%E5%AF%86%E7%A0%81%E4%BD%93%E5%88%B6%EF%BC%9A%20%E5%A4%A7%E7%B4%A0%E6%95%B0%20p%2Cq%20%EF%BC%8C%E6%A8%A1%E6%95%B0,n%20%3D%20pq%20%EF%BC%8C%E5%8A%A0%E5%AF%86%E6%8C%87%E6%95%B0%20b%20%EF%BC%8C%E8%A7%A3%E5%AF%86%E6%8C%87%E6%95%B0
RSA算法原理 - 知乎 (hu.com)
https://zhuanlan.hu.com/p/48249182#:~:text=RSA%E7%AE%97%E6%B3%95%E5%8E%9F%E7%90%86%201%20%EF%BC%881%EF%BC%89%E4%B9%99%E6%96%B9%E7%94%9F%E6%88%90%E4%B8%A4%E6%8A%8A%E5%AF%86%E9%92%A5%20%28%E5%85%AC%E9%92%A5%E5%92%8C%E7%A7%81%E9%92%A5%29%E3%80%82...,2%20%EF%BC%882%EF%BC%89%E7%94%B2%E6%96%B9%E8%8E%B7%E5%8F%96%E4%B9%99%E6%96%B9%E7%9A%84%E5%85%AC%E9%92%A5%EF%BC%8C%E7%84%B6%E5%90%8E%E7%94%A8%E5%AE%83%E5%AF%B9%E4%BF%A1%E6%81%AF%E5%8A%A0%E5%AF%86%E3%80%82%203%20%EF%BC%883%EF%BC%89%E4%B9%99%E6%96%B9%E5%BE%97%E5%88%B0%E5%8A%A0%E5%AF%86%E5%90%8E%E7%9A%84%E4%BF%A1%E6%81%AF%EF%BC%8C%E7%94%A8%E7%A7%81%E9%92%A5%E8%A7%A3%E5%AF%86%E3%80%82
㈤ 密码学基础（三）：非对称加密（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加密解密算法
1978年就出现了这种算法，它是第一个既能用于数据加密
也能用于数字签名的算法。它易于理解和操作，也很流行。算
法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和
Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。
RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数
（ 大于 100个十进制位）的函数。据猜测，从一个密钥和密文
推断出明文的难度等同于分解两个大素数的积。
密钥对的产生:选择两个大素数，p 和q 。计算：
n = p * q
然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 )
互质。最后，利用Euclid 算法计算解密密钥d, 满足
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )
其中n和d也要互质。数e和
n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任
何人知道。 加密信息 m（二进制表示）时，首先把m分成等长数据
块 m1 ,m2,..., mi ，块长s，其中 2^s <= n, s 尽可能的大。对
应的密文是：
ci = mi^e ( mod n ) ( a )
解密时作如下计算：
mi = ci^d ( mod n ) ( b )
RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b )
式验证。具体操作时考虑到安全性和 m信息量较大等因素，一般是先
作 HASH 运算。
RSA 的安全性。
RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理
论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在
一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，
RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显
然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，
模数n必须选大一些，因具体适用情况而定。
RSA的速度:
由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论
是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据
加密。
RSA的选择密文攻击:
RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装
(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信
息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保
留了输入的乘法结构：
( XM )^d = X^d *M^d mod n
前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征
--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有
两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体
任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不
对陌生人送来的随机文档签名，签名时首先使用One-Way HashFunction
对文档作HASH处理，或同时使用不同的签名算法。在中提到了几种不
同类型的攻击方法。
RSA的公共模数攻击。
若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险
的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互
质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥
为e1和e2，公共模数是n，则：
C1 = P^e1 mod n
C2 = P^e2 mod n
密码分析者知道n、e1、e2、C1和C2，就能得到P。
因为e1和e2互质，故用Euclidean算法能找到r和s，满足：
r * e1 + s * e2 = 1
假设r为负数，需再用Euclidean算法计算C1^(-1)，则
( C1^(-1) )^(-r) * C2^s = P mod n
另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数
的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它
成对的e’和d’，而无需分解模数。解决办法只有一个，那就是不要共享
模数n。
RSA的小指数攻击。 有一种提高
RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度
有所提高。但这样作是不安全的，对付办法就是e和d都取较大的值。
RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。
RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各
种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。
RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难
度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性
能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。
RSA的缺点主要有：
A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次
一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits
以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；
且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。
目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长
的密钥，其他实体使用1024比特的密钥。
