<一>算法运用

（1）密钥对求解步骤

{1} 设置两个质数p、q；

{2} 求p、q的乘积n；

{3} 求n的欧拉函数（欧拉函数会在本文章第二大节”简单数论基础知识介绍“中与其它一些数论基础定理介绍）；

{4} 找一个与n的欧拉函数互质的数；

{5} 根据模反定理求取上一步中与n的欧拉函数互质的数在模n的欧拉函数下的逆元；

{6} 得到俩个密钥对，其分别是公钥(n,e)和私钥(n,d)。

（2）密钥对加密及解密函数

{1} 加密公式 m^e ≡ c ( mod n )。

{2} 解密公式。

[1] c^d ≡ m ( mod n )；

[2] m = ((mq-mp)*[p^-1] mod q )*p + mp (注意mp与mq的求解公式如下 mp ≡ c^dp mod p 、mq ≡ c^dq mod q。还需注意的是 [p^-1]代表的是p在模q下的逆元)。

两个公式的区别是下面的公式解密时没有用到私钥对中的d，而是用到了dp与dq，下面第三大块《解密公式证明》会有详细证明。

Forming想说：

如果单纯为做ctf题中crypt的题，那么此时把公式记住就已经大功告成了，但是就实际情况来说当然是不够，因为不一定考rsa，而是考一个加密脚本，此时解题就需要数据运算能力和逻辑推理能力。

就算考了rsa也不一定考这两个公式，所以下面将会详细记录验证解密公式解出的值就是明文和一些数论上定理的证明，Forming是通过手写演算并拍照上传的方式记录的，因为在电脑上敲演算经过很不方便。

<二>简单数论基础知识介绍

有些字符不好打出来以下内容将附图片

{1} 同余号'≡'及理解

[同余的含义] a ≡ b ( mod n )这个式子表示“a在模n下与b同余”，通俗来说就是a除以n取余和b除以n取余的结果一样。

[同余的延申]《同余的意义》中的式子满足下面的等式 b = a - kn （k表示一个常量）值得注意的是此时b可看作a的“最小同余数”，并不代表满足 a ≡ b ( mod n )的b、a中b一定是a的最小同余数，只要a、b满足 a ≡ b ( mod n ) 则其一定满足 b = a - kn。

[同余的运用] 若将《同余的意义》中的同余式直接代入到 c = a + d 中变化为 c = ( b mod n ) + d 也是可以的，不过此时要理解为代入的 a 是其最小同余数。

{2} mod运算的法则

观察下面的等式可以发现模运算符合交换律、结合律和分配律。

• • (a + b) % p = (a%p + b%p) % p

  • (a - b) % p = (a%p - b%p) % p

  • (a*b) % p = (a%p * b%p) % p

  • a * b % p = (a % p *b) % p

  • a^b % p = ((a % p)^b) % p

{3} 数论四大基础定理及求逆元（模反定理）

[1] 欧拉定理

欧拉函数涵义：有一个数n，比n小的数且与n互质的数的个数就是欧拉函数的值。

欧拉函数通式：φ(n) = n∏(1-1/pi) （一个数肯定可以写成有限个质数相乘，pi代表的就是所有的质数，还需注意这个公式中一个质数不可代入两次）。

举例：n=8 8=2*2*2 φ(8) = 8*(1-1/2) = 4 （比八小且与其互质的数是1、3、5、7，个数为四个所以欧拉函数的值就是4）。

欧拉函数特例：

[n是质数相乘] n = p*q φ(n) = φ(p) * φ(q)

[n是指数的幂] n = p^k φ(n) = (p-1)p^(k-1) 因为质数除了不和自身的整数倍数倍互质与其余任何树都互质。

[n是奇数] φ(2n) = φ(n)

[n是质数] φ(n) = (n - 1)

欧拉定理：a^φ(n) ≡ 1 mod n

证明：根据同余乘方定理与费马小定理和模运算法则，在费马小定理同余号两边乘a再模n下的逆元后就能得到欧拉定理。

[2] 中国剩余定理（又称孙子定理）

涵义：通过公式找到一个能满足多个同余式的整数。

公式：x = Σai * N/mi * [N/mi^-1] + kN （N是所有模的乘积，k是常数，mi是某个模，ai是同余号右边的数）。

证明：

有时我们会遇到如下图的问题

这个问题很实际，但是抽象出来可以是如下图的形式。

得出公式并验证了一下。

[3] 费马小定理（采用数学归纳法证明）

涵义：一个质数p，作为任意一个数的指数的幂与这个数在模p下同余。

公式：a^p ≡ a (mod p)

证明：

[4] 威尔逊定理

涵义：p为质数，则其必能整除(p-1)!+1

公式：[(p-1)!+1]%p = k （k是常数）

[5] 求逆元

涵义：两个数φ(n)、e互质，其中φ(n)作模，则必有一个数和e的乘积在模φ(n)下与1同余。

公式：ed ≡ 1 (mod φ(n))

{4} 同余乘方定理证明（采用数学归纳法证明）

性质其实有三条但是只证明一个，其余简单就不写了。

<三>解密公式证明

{1} c^d ≡ m ( mod n ) 证明

{2} m = ((mq-mp)*[p^-1] mod q)*p + mp、mp = c^dp mod p、mq = c^dq mod q证明

mq、mp、p、q、d、dp、dq之间存在如下关系，但是这样的关系带有d而在遇到类似问题时没有d只有dp和dq所以推演的最终结果要用dp和dq求出所有需要的值。

dp ≡ d mod (p - 1)

dq ≡ d mod (q - 1)

mp ≡ c^d mod p

mq ≡ c^d mod q

第三部分总结：通过推演可以知道m与c不能是n的倍数，也就是明文和密文都不能为n的倍数，但是我们做题的时候不需要考虑这一点因为要是不满足的话他让咱们算什么，所以肯定是成立的。

Forming想说：

所谓数学就是用 "数学抽象世界" 中的法则描述现实世界

所谓数论就是 "数学抽象世界" 中关于整数的法则集合

数论就是对整数的研究