RSA加密是比较常用的加密算法（并不会自己写到），本文测验运用最基础的办法解说RSA中的每一步的核算步骤、理论依据及证明；即使是忘记了此前学过的一切密码学常识，跟从本文的思路也能彻底了解RSA，不必死记硬背一些没有彻底了解的东西。整个篇幅会有点长，假如遇到了某个现已了解了的公式或定理，能够直接越过。
RSA加密流程
首要会介绍一下RSA的加密流程，其间有【】标示的内容会在后文做出解说：
-
找两个大质数：p、q；算出乘积n；能够确保任何人不能经过n，拆出p、q。
-
算出另一个数字fn = (p – 1) * (q – 1)；这个fn的意思是：在1到n之间，与n互质的数的数量【1】(该注释解说为什么fn能表明这个个数)，因为n没有办法被拆开，所以攻击者也核算不出fn。
-
然后挑选一个质数e = 65537作为公钥（也能够选别的），e是质数。
-
找到私钥d，满意 e * d mod f == 1【2】（该注释介绍怎么找到d）。
以上为预备工作；预备这些数据并保存私钥的咱们称为接收方，经过明文取得公钥并运用运用公钥加密的称为发送方。
发送方获取到公钥[e, n]后，经过如下办法加密：
-
现假定有需求加密的数字m，确保m<n; (假如比较长，能够分段加，接收方分段解，一向确保m<n);
-
发送方核算出密文c = m ^ e mod n ，发送给接收方。
-
接收方获取到密文c和自己保存的私钥[d,n]后，经过如下办法解密：
-
接收方核算m’ = c ^ d mod n。
-
m’ == m 必建立，解密完结【3】（该注释解说为什么 m’ == m建立，即RSA的理论基础）
【1】为什么fn = (p-1) * (q-1)表明[1, n]中与n互质的数的个数
- 因为p为质数，所以在[1, p]中，除p以外的数字，均与p互质，故fp = (p – 1)
- 因为q为质数，所以在[1, q]中，除q以外的数字，均与q互质，故fq = (q – 1)
- 因为n = p * q，所以n不是质数，故不能套用以上规则：可是能够经过排除法算出与n互质的数字的个数
- 在[1, n]中除n外共有数字 p * q – 1个；其间与n不互质的数字包括：A.一切比p小的数字，与q的乘积，共p-1个；B.一切比q小的数字与p的乘积，共q-1个；故有[1,n]中与n互质的数字个数：fn = p * q – 1 – (p – 1) – (q – 1) = p * q – p – q + 1 = (p – 1) * (q – 1)。
- 综上：在p、q为质数，n = p * q的状况下， fn = (p – 1) * (q – 1) 能够表明[1, n]之间与n互质的数字个数。
【2】在已知质数e、数字fn的状况下，怎么找到d，使得e * d mod fn = 1
为了更明晰地阐明这个进程，这儿先举一个简略的比如：
假定：p = 3；q = 13；则有n = 39；fn = 2 * 12 = 24；现在，我能够恣意指定恣意质数为公钥e，假定我指定e = 11，需求寻觅一个数字d，满意 e * d mod fn = 1。
按照最直观的操作办法，暴力遍历d = 1、2、3、4…直到找到一个d，满意d * e mod fn = 1:
11 mod 24 = 11
22 mod 24 = 22
33 mod 24 = 9
44 mod 24 = 20
55 mod 24 = 7
66 mod 24 = 18
77 mod 24 = 5
88 mod 24 = 16
99 mod 24 = 3
110 mod 24 = 14
121 mod 24 = 1
完毕；事实上，这个进程便是在寻觅:
x * 11 – y * 24 = 1；x依次添加，y在总是确保成果为正的前提下尽量大，终究找到了x是11；
所以问题就变成了：我要得到1，至少需求用多少个11（公钥），这个“多少个”便是私钥。因为是私钥*公钥 mod n = 1。
然后，咱们演示一下求解11和24最大公约数的进程，咱们需求的并不是这个最大公约数，因为你要求的最大公约数必定是1，咱们仅仅需求求解最大公约数进程中运用到的e的个数。
留意：事实上，因为RSA只规定了私钥p、q均为大质数，这儿假如(p – 1) * (q – 1)刚好是e的倍数怎么办？在此种状况下，最大公约数是e而不是1，因而，假如遇到此种状况，需求从头换个e：你只需求核算一次(p – 1)*(q – 1)/e是否为整数即可：假如不为整数，则能够运用，假如为整数，从头挑选e，只需确保fn = (p – 1) * (q – 1)不为e的整数倍，那么，fn与e必定互质，在fn与e互质的状况下，最大公约数必定是1，这一点是在挑选e的时候需求确保的。
然后咱们列出最大公约数求解进程（曲折相减）：
24 – 11 = 13
13 – 11 = 2
11 – 2 = 9
9 – 2 = 7
7 – 2 = 5
5 – 2 = 3
3 – 2 = 1
这个进程有了，那么咱们要的是什么值呢，要每一步运用到的11的个数，尾标示一下：
24 – 11 = 13 用到几个11？ 1个 ，因为24不必11，11用1个11，所以总共是1个
13 – 11 = 2 用到几个11？2个 ，因为依据上一步：13用了1个11； 本步11用了1个11，所以总共2个
11 – 2 = 9 用到了几个11？3个，因为依据上一步：2用了2个11；本步11用了1个11，所以总共是3个
9 – 2 = 7 用到了几个11？5个，因为依据上一步：9用了3个11；上上步2用2个11，所以总共是5个
7 – 2 = 5 用到了几个11？7个，因为依据上一步：7用了5个；第二步2用了2个，总共7个
5 – 2 = 3 用到了几个11？9个，因为上一步：5用了7个；第二步2用了2个，总共9个
3 – 2 = 1 用到了几个11？ 11个，因为上一步：3用了9个；第二步2用了2个；总共11个
完毕，得1的时候，用到的11个11，前面的11便是d，后边的11便是e。（Emmm，这个比如不太好了，e和d持平了，可是我现已写到这了，就不从头找别的比如了，能够自行算其他的比如验证，e、d正常来说不都是一样的，这儿刚好持平）
那为什么两种办法求出的运用11的个数是一致。假如你现已了解了，能够越过下面的比如，假如还没了解能够读完这个比如：
【2.1】上下台阶比如
依据上边求解最大公约数的步骤，是不是很像是一个动态规划：列表记载每一步的成果，后一步的成果依靠前面的成果；说到动态规划，就不得不提上下台阶，假如我把题改成：一个小人上下台阶，每次只能从：A.向上走11个台阶 或 B.向下走24个台阶中挑选一个办法走，开端方位是0，问：最少走多少次A才干走到1阶。
第一种办法：只需没超越24，就一向往上走11，超越24了，向下走24，直到走到1，记载向上走11的次数。
第二种办法，智能一点：
- 只需没超越24，我一向向上走11，超越了减24：上3次，下一次，到9；我记载一下：向上走9步需求3个11；那么下次当我快要抵达24的时候，是不是能够优先考虑9，直接用9步3次的成果。
- 从9开端，向上11到20，没超越；接着向上11，到31，超越了，此时，我能够看看，假如不必11，而是用最小的能够满意超越24的步数9，20 + 9 = 29，也超越了；那么我就直接用9；所以在本来3的基础上加1再加3得7；终究走到了5；记载：我向上走5阶，用7个11，下次能够用。
- 从5开端，向上11，到16，没超越；接着向上11，超越了，此时，我能够选一个小的值替代11：5行不可？不可，因为16 + 5 = 21 < 24; 9行不可？行，因为16 + 9 = 25 > 24;所以选9，那么也便是在本来7个11的基础上加1个11，再加3个11：7 + 1 +3 = 11，然后看到当时在25 – 24 = 1了，阐明满意成果要求，故总共需求11个11能走到1阶。
第三种办法，再智能一点：
记载两个数，向上的最小阶数m，向下的最小阶数n，初始值m = 11,n = 24; 记载另外两个值stepM、stepN，表明走到向上/向下的当时最小阶数，用到11的个数，那么初始值：mNeed11 = 1、nNeed11 = 0。开端循环：
- 我先看看向上和向下哪个大？向下大：那么我能够用24减去尽可能多的11，得到一个向下的间隔1最近的阶数：是不是24 – 2 * 11 = 2；然后用这个2替换之前的最小阶数24：m = 11, n = 2, 更新 nNeed11 = 2,因为减了两个11。
- 我再看看m、n哪个大？向上大：那么能够用11减去尽可能多的2，得到一个向上的间隔1最近的阶数：是不是11 – 5 * 2 = 1；然后用这个1替换之前向上的最小阶数11：m = 1, n = 2, mNeed11 = mNeed11 + 5 * nNeed11 = 11，因为你用了一次向上m减去尽可能多的5个n，所以后边加了前一次的mNeed11。
此时m现已等于1了，所以退出循环。
然后看看这三个办法：办法一其实便是一个一个11向上加，超24减24的办法；办法三，其实便是曲折相除法求最大公约数，在求解e和fn的最大公约数进程中，记载运用到e的个数。
此例完毕，总结：求解e * d mod fn = 1和曲折相除法求解最大公约数联系在一起时因为；前者需求的是后者中心产品，非最大公约数自身。
【3】m’ == m 必建立
间隔比较远，从头描述一下问题：
m为明文，恣意正整数；p、q为质数；n = p * q; fn = (p – 1) * (q – 1);
e为任取质数，d满意 e * d mod fn = 1；
c为密文，c = m ^ e mod n
m’为解密文，m’ = c ^ d mod n
证明：m’ == m
为了在讲述终究证明之前扫清一些妨碍，首要证明三个小推论：
【3.1】模法分配率：“积的模 等于 模积模”
即：a * b mod c = (a mod c) * (b mod c) mod c
（“模法分配率”我瞎编的，不知道怎么叫，这个读着顺口好记）
证明：将a、b拆成，关于c的倍数和余数之和的方式：
令： a = k * c + x; b = s * c + y；k、s为倍数，x、y为余数，x、y必定小于等于c。
那么有：a * b mod c = (k * c + x) * (s * c + y) mod c = (k * m* c^2 + k * c * y + m * c * x + x * y) mod c
前三项均包含c因子，故会被模掉，所以终究剩下：
a * b mod c = x * y mod c = (a mod c) * (b mod c) mod c
得证。
【3.2】若a与c互质 且 b与c互质，则a * b与c互质
反证法：若a * b与c不互质，则存在一个大于1的因子m，一起在a * b 和 c中；关于a * b，若想有因子m，则因子m不是在a中，便是在b中，或者是在a、b中；不管哪种状况，都与a、c互质和a、b互质对立，故不存在m；所以a * b 与 c互质。
得证。
【3.3】若a与b互质，则a mod b 与 b 互质
将a拆解成倍数和余数的方式 a = k * b + x；则x = a mod b；因为k * b必定与b不互质，假如x与b也不互质，那么k * b + x与b必定不互质，与a与b互质对立，故x与b必定互质。
得证。
【3.4】开端证明m’ == m，先证此问题：对互质的两个数：a和b；在[1,a]之间，一切与a互质的数x，核算出的y = b * x mod a 均不持平。
即：一切的y与x逐个映射，不存在两个不同的xi和xj能算出同一个y的状况。
反证法：我从[1,a]中任选与a互质的两个数字，xi和xj；若存在：b * xi mod a == b * xj mod a；则: (b * xj – b * xi) 必定是a的整数倍，相当于把相同的余数都减掉了，剩下的都是a的倍数，这个很好了解；也就意味着：b * (xj – xi) 是a的整数倍。
因为|xj – xi|必定比a小，所以，若想从b * (xj – xi)中提取出a因子，那么必须从b中提取出一个大于1的因子，乘上(xj – xi)，才有可能凑出一个a因子；假定从b中提取出了一个大于1的因子m，凑出了a；那么该因子m也必定是a的因子；而a、b存在大于1的因子m，与a、b互质相对立，故不存在；所以b * (xj – xi) 不可能是a的整数倍。也便是说恣意一对： b * xi mod a 和 b * xj mod a 均不持平。
得证。
【3.5】关于【3.4】中一切的y = b * x mod a，均与a互质。
明显，依据【3.2】：因为b与a互质、x与a互质，故b * x 与a 互质；又依据【3.3】因为b * x 与 a互质，故b * x mod a 与 a互质。
得证。
【3.6】归纳【3.4】和【3.5】进行推论：
因为【3.4】中一切的y均比a小；且一切的y都是与x逐个对应，没有重复，所以数量持平；且一切的y都与a互质。假如我将一切的x放入调集X，一切的y放入调集Y，那么X与Y必等价，表明的都是：一切【1，a】之间与a互质的正整数。
接着推：因为调集X和调集Y等价，所以两调集里面一切元素乘积必持平：
x1 * x2 * x3 … x(f(a)) == y1 * y2 * y3 … y(f(a))
肯定的，里面元素都一样，仅仅乘的顺序可能不持平，所以一个也不能漏。
然后将y侧都替换为：y = b * x mod a 的方式
x1 * x2 * … == (b * x1 mod a) * (b * x2 mod a) …
两头mod仍然持平：
x1 * x2 * … mod a == (b * x1 mod a) * (b * x2 mod a) … mod a
依据【3.1】“模积模 等于 积的模”：
x1 * x2 * … mod a = (b * x1 mod a) * (b * x2 mod a) … mod a = (b * x1) * (b * x2) … mod a = b ^ f(a) * (x1*x2…) mod a
f(a)便是调集X中元素个数，也便是[1,a]中一切与a互质的数字个数。
两头mod持平 的条件等价于两头相减余下k个a，k恣意；
所以有右-左有：
(b ^ fa – 1) * (x1 * x2 * …) = k * a
因为 x1、x2 … 均与a互质依据【3.2】(x1 * x2 *….)与a互质，所以 b ^ fa – 1 必为a的整数倍。
故：b ^ fa mod a = 1建立。【定理A】
依据这个推论，咱们套入RSA中，上式 a 即为 RSA中的n, b即为RSA中的m；
那么：
c = m ^ e mod n；e * d mod fn = 1；
有：m’ = m ^ (e * d) mod n = m ^ (k * fn + 1) mod n = m * (m^fn * m^ fn … *m^fn) mod n
依据【3.1】“积的模 等于 模积模”：
m’ ={ m mod n * [ (m^fn mod n) *…] } mod n
依据前面的【定理A】，m ^ fn mod n = 1,所以上式中括号中是一堆1相乘，故：
m’ = {m mod n * (1 * 1 * 1 …)} mod n = m mod n
因为RSA在截取密文m时，一向确保m < n，故 m mod n = m，即m’ = m。
得证：解密文 m’ == 原文m；RSA加解密建立。
上述【定理A】即为：欧拉定理，其核心便是证明一切x凑成的调集X 与 一切y = b * x mod a 组成的调集Y，彻底等价，所以元素相乘值持平，再将y中一切的b，独自提出，凑出b^fa方式，最后数学改换验证了：b^(fa – 1) mod a = 1建立得出。
【3.7】m与n不互质的状况
在上文【3.6】中，咱们单纯套用了【定理A】，【定理A】中对a、b的要求是：a、b互质；然而，在RSA中，咱们对原文m的要求仅为：m < n，并未确保互质；实际状况下：m可能呈现比n小的任何数字；n = p * q；n必不是质数，因而没法确保m、n互质；但在此种状况下，RSA仍然建立，以下给出证明：
考虑为数不多的几种m、n不互质的状况：因为m < n； n = p * q；p、q均为质数；那么仅有以下状况m、n不互质：
-
m = k * p; k < q;
-
m = k * q; k < p;
因为p、q等价，因而咱们只需证明其间一种状况RSA仍建立，另一种状况彻底对称。
取m = k * p; k < q；的状况进行评论：
目标：核算出 c = (k * p) ^ e mod n，验证：m’ = c ^ d mod n 与 m持平。
因为p、q为质数 且 k、q互质，依据【3.2】k * p 与 q互质；所以，k * p 与 q满意欧拉定理：
(k * p) ^ fq mod q = 1
那么：[ (k * p) ^ fq ] * [(k * p) ^ fq] mod q = ?
明显还是1，依据【3.1】“积的模 等于 模积模”：
原式 = { [ (k * p) ^ fq mod q] * [ (k * p) ^ fq mod q] } mod q = (1 * 1) mod q
那是不是我恣意个 (k * p) ^ fq 相乘 mod q都是1，所以fp个相乘也是1，故有：
(k * p) ^(fp * fq) mod q = 1
fp = p – 1; fq = q -1; fn = (p – 1) * (q – 1)；所以：
(k * p) ^ fn mod q = 1；意味着：
(k * p) ^ fn = s * q + 1 ; s恣意，不知道多少。
两头一起乘 k * p：
(k * p) ^ (fn + 1) = s * q * k * p + k * p
两头 mod n：
(k * p) ^ (fn + 1) mod n = k * p
依据RSA，e * d mod fn = 1；故：e * d = s * fn + 1 ; s恣意；
结合上式：我现在需求依据 ：
(k * p) ^ (fn + 1) mod n = k * p
推出：
(k * p) ^ (s * fn + 1) mod n = k * p
怎么办，假如我说我能依据：
(k * p) ^ (fn + 1) mod n = k * p
推出：
(k * p) ^ (2 * fn + 1) mod n = k * p；
是不是意味着我把2换成s；s >= 1；是建立的：
那就拆：
(k * p) ^ (2 * fn + 1) mod n = [ (k * p) ^ fn * (k * p)^(fn + 1)] mod n = [ (k * p) ^ fn mod n ] * {[(k * p)^(fn + 1)] mod n} mod n
后边那个fn + 1的项是不是就等于 k * p：
原式 = [ (k * p) ^ fn mod n ] * (k * p) mod n
因为k * p 必定比 n 小，所以k * p = k * p mod n
原式 = [ (k * p) ^ fn mod n ] * (k * p mod n) mod n
再把它合进去：
原式 = [ (k * p) ^ fn * (k * p) mod n ] mod n = (k * p) ^ (fn + 1) mod n = k * p
是不是前面不管再乘多少个 (k * p) ^ fn，我都能这样把它吃掉，故：
m’ = (k * p) ^ (s * fn + 1) mod n = (k * p) ^ (fn + 1) mod n = k * p = m
所以，RSA在m与n不互质的状况下，仍然建立。
【4】总结
经过从头叙说RSA加解密流程，进行总结：
- 经过寻觅两个大质数p、q，确保fn = fp * fq；fp、fq表明[0,p/q]之间与p/q互质的数字个数，因为p、q为质数，确保了：fp = (p – 1) ; fq = (q – 1)；fn = (p – 1) * (q – 1)建立（f函数叫欧拉函数，这个函数有一些特别性质，本文【1】证明的是其间一个：p、q为质数状况下的性质，f(p * q) = fp * fq）。
- 取质数e作为公钥，并依据e、n运用曲折相除求解私钥d，【2】阶段证明，并排举了上下台阶的比如便于了解为什么运用曲折相除，其本质并非求解最大公约数。
- 对原文m进行加密，c = m ^ e mod n
- 对密文c进行解密, m‘ = c ^ d mod n = m；包含两种状况：1.m与n互质，套用欧拉定理得证；2.m与n不互质，【3.7】阶段给出证明。两种状况下：m’ = m 均建立，故仅确保m < n 即可。
完毕，以上便是RSA所依靠理论基础的全部证明进程；本文的一切论证均从最基础的理论动身，是为了确保在不了解欧拉函数、欧拉定理、曲折相除用意的前提下仍然能了解RSA加解密建立的原因。一起，也添补实际运用时对发生的：e、n不互质，m、n不互质状况下的处理办法，不失为一篇全面了解RSA的好文章啊，哈哈哈；当然，关于一些现已比较了解RSA的工程师来说，本文的部分评论着实显得磨蹭了。
