RSA加密基础
数学基础：
一、 什么是“素数”？
只能被1和它自己整除的整数。
二、什么是“互质数”（或“互素数”）？
小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”这里所说的“两个数”是指自然数。
判别方法主要有以下几种（不限于此）：
（1）两个质数一定是互质数。例如，2与7、13与19。
（2）一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与 26。
（3）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。
（4）相邻的两个自然数是互质数。如 15与 16。
（5）相邻的两个奇数是互质数。如 49与 51。
（6）大数是质数的两个数是互质数。如97与88。
（7）小数是质数，大数不是小数的倍数的两个数是互质数。如 7和 16。
（8）两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。如357与715，357=3×7×17，而3、7和17都不是715的约数，这两个数为互质数。等等。
三、什么是模指数运算？
模运算是整数运算，有一个整数m，以n为模做模运算，即m mod n。怎样做呢？让m去被n整除，只取所得的余数作为结果，就叫做模运算。例如，10 mod 3=1；26 mod 6=2；28 mod 2 =0等等。
模指数运算就是先做指数运算，取其结果再做模运算。如 (5*5*5) mod 7 = 125 mod 7 = 6
算法描述：
好了，直接举例子说明算法：
（1）选择一对不同的、足够大的素数p，q。 （3 11）
（2）计算n=pq。 （33）
（3）计算f(n)=(p-1)(q-1)，同时对p, q严加保密，不让任何人知道。 （20）
（4）找一个与f(n)互质的数e，且1<e<f(n)。 （取 3）
（5）计算d，使得de≡1 mod f(n)。这个公式也可以表达为d ≡e-1 mod f(n)
这里要解释一下，≡是数论中表示同余的符号。公式中，≡符号的左边必须和符号右边同余，也就是两边模运算结果相同。显而易见，不管f(n)取什么值，符号右边1 mod f(n)的结果都等于1；符号的左边d与e的乘积做模运算后的结果也必须等于1。这就需要计算出d的值，让这个同余等式能够成立。 d*3 = 1 mod 20
算出d=7。
（6）公钥KU=(e,n)，私钥KR=(d,n)。 公钥：3 33 私钥：7 33
（7）加密时，先将明文变换成0至n-1的一个整数M。若明文较长，可先分割成适当的组，然后再进行交换。设密文为C，则加密过程为：。
（8）解密过程为：。
原文件信息为：2，3，7。下面对这三个数进行加密。
明文加密
用户加密密钥(3,33) 将数字化明文分组信息加密成密文。由C≡Me(mod n)得：
M1≡2^3(mod 33)=8
M1≡3^3(mod 33)=27
M1≡7^3(mod 33)=13
因此，得到相应的密文信息为C： 8 27 13。
密文解密。
用户B收到密文，若将其解密，只需要计算，即：
M1≡8^7(mod 33)=2
M1≡27^7(mod 33)=3
M1≡13^7(mod 33)=7
用户B得到明文信息为：2 3 7 。
这里取的素数是非常小的。假设取得比较大的时候，就需要程序来计算了。否则long long 类型很容易就会溢出。
数学基础就是：大数因式分解的计算非常复杂。
该算法计算复杂度高，适合对少量数据加密。