RSA相关数论知识

费马小定理

若p是素数，q是正整数且不能被p整除，则：

\[q^{(p-1)} \% p = 1\]

推论：若p是素数，q是正整数且不能被p整除，则：

\[q^p \% p = q^{(p-1)} * q \% p = 1 * q \%p = q \% p\\q^{p-1}=q^{p-2}*q=1\bmod p，因此，q^{-1}=q^{p-2}=q^{\varphi(p)-1}\bmod p\]

引理一，剩余系定理2：当jq%p = kq%p，如果q和p互素，有j%p=k%p

证明：

由于：jq %p = kq %p，有：(jq-kq)%p = 0，可得：(j-k)q%p = 0，即：(j-k)q = np，由于q和p互素，只能够n=xq，因此q可以约去，得：(j-k)%p=0，即j%p=k%p

证明：

依赖集合相等的思想。考虑小于p的正整数集合Y={1,2,…,p-1}，用q乘以集合中所有元素并对p取模，得到集合X={q%p, 2q%p, …, (p-1)q%p}，因为p不能整除q，因此X的元素都不等于0，而且各元素不相等（反证法：假设jq%p=kq%p，其中0<j<k<p，根据引理一，有j%p=k%p，因为j，k都是小于p的正整数，与假设不符，得证）。所以X和Y构成相同，只是元素顺序不同，将两个集合元素分别相乘，并对结果模p，得：

\[X = q*2q*...*(p-1)q \% p = q^{(p-1)}(p-1)! \% p = Y = 1*2*...*(p-1) \% p = (p-1)! \% p\]

因为(p-1)!和p互素，根据引理一，可以约去(p-1)!，得证：

\[q^{(p-1)} \% p = 1\]

推导1：

\[q^{(p-1)} = np + 1\\q^{(p-1)} * q = (np+1)q\\q^{p} = npq + q\\q^p \% (p*q) = q\]

推导2，p，q均为素数：

\[(p+q)^{(p+q)} \% (p*q) = (p^{(p+q)} + np^iq^j+... + q^{(p+q)}) \% (p*q) \\= (p^{(p+q)} + q^{(p+q)}) \%(p*q) //p^iq^j可以被p*q整除\\=(p^p*p^q + q^q*q^p)\%(p*q)\\=(p^p*p + q^q * q) \%(p*q) //推导1\\=(p^{(p+1)} + q^{(q+1)}) \% (p*q)\]

推导3：

\[p^p \% q = x\\设:p^p = n * q + x\\p^p * p = n * p * q + x*p\\p^{(p+1)} = n * p * q + (p^p\%q) * p\\p^{(p+1)} \% (p*q) = (p^p\%q) *p//p^p\%q小于q，因此乘积小于p*q，无需再模(p*q)\]

以模指数pow(p,e,n)形式表示，要求指数为素数，底是正整数且不能被指数整除：

\[pow(p, q-1, q) = 1\\pow(p, q, q) = p\\pow(p, q, p*q) = p\\pow(p+q, p+q, p*q) = (pow(p, p+1,p*q) + pow(q, q+q, p*q)) \% (p*q)\\pow(p, p+1,p*q) = pow(p, p, q) * p\]

欧拉函数

欧拉函数是小于或等于n的正整数中与n互质的数的个数。性质：

\[1.若n为奇数，\varphi(2n) = \varphi(n)\\2.若n为质数，所有小于质数的正整数均与该质数互质，\varphi(n)=n-1\\3.若p，q互质，\varphi(p*q)=\varphi(p)*\varphi(q)，根据中国余数定理，\varphi(p*q)的元素和\varphi(p)*\varphi(q)的元素一一映射\\4.若p，q均为质数，则\varphi(p*q)=\varphi(p)*\varphi(q)=(p-1)*(q-1)\\5.对任意k\ge1，\varphi(p^k)=p^k-p^{k-1}=p^{k-1}*(p-1)=p^k*(1-\frac{1}{p})\\证明：因为只有p的倍数与p^k不互质，这样的数只有1p,2p,...p^{k-1}*p，共p^{k-1}个，余下的p^k-p^{k-1}都与p^k互质\\6.由4，5得：当n=p_1^{k_1}*p_2^{k_2}...*p_r^{k_r}\\\varphi(n)=\varphi(p_1^{k_1})*\varphi(p_2^{k_2})...*\varphi(p_r^{k_r})=p_1^{k_1}*(1-\frac{1}{p_1})*p_2^{k_2}*(1-\frac{1}{p_2})...*p_r^{k_r}*(1-\frac{1}{p_r})\\=p_1^{k_1}*p_2^{k_2}...*p_r^{k_r}*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_r})\\=n*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...*(1-\frac{1}{p_r})\]

欧拉定理（费马小定理可视作欧拉定理特例，n为质数的情况）

\[若m，n互质，则m^{\varphi(n)}\equiv1\pmod n\\证明：类似费马小定理集合相等原则，所有与n互质的数构造X=\{x_1,...,x_\varphi(n)\}，构造Y=\{mx_1,...,mx_\varphi(n)\}\\仅需证明：1.Y中任意两个数模n不同余（反证法：若mx_i与mx_j模n同余，因为m与n互质，x_i需等于x_j）\\2.Y中任意值模n的值与n互质（反证法：若模数r与n有公因子c，则：mx_i=kn+r=xc+yc与n有公因子c，但m和x_i均与n互质）\\因为模n所有与n互质的数集合为X，因此X=Y，将两个集合元素分别相乘，并对结果模n得证\]

RSA解密原理

\[ed \equiv 1 \bmod \varphi(N)，则ed=k*\varphi(N) + 1，即证明：m^{k*\varphi(N)+1}\equiv m \bmod N\\1.若m，N互质，根据欧拉定理：m^{k*\varphi(N)+1}=(m^{\varphi(N)})^k * m\equiv 1 * m \bmod N\\2.若m，N不互质，则m为p或q的倍数（不能同时为p和q倍数，否则m为N的倍数，则密文c=m^e \bmod N=0）\\设m=xp，由于q为质数，根据欧拉定理：m^{\varphi(q)}\equiv 1 \bmod q\\因此：m^{k*\varphi(N)}=m^{k*(p-1)(q-1)}=(m^{\varphi(q)})^{k*(p-1)}\equiv 1\bmod q\\m^{k*\varphi(N)+1}=(y*q+1)*m=m+m*y*q=m+x*p*y*q=m+x*y*N\equiv m\bmod N\]

欧几里德算法（辗转相除法）

gcd(a,b) = gcd(b, a%b)

证明一：

第一步：令c=gcd(a,b)，则设a=mc，b=nc
第二步：可知r=a-kb=mc-knc=(m-kn)c
第三步：根据第二步结果可知c也是r的因数
第四步：可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，（d>1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数≥cd，而非c，与前面结论矛盾】
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)，得证

证明二：

证明gcd(a,b)==gcd(b,a%b)，我们只要证明gcd(a,b)==gcd(a-b,b)即可，因为可以由此逐步扩展为gcd(a,b)==gcd(a-k*b,b)，而gcd(a-k*b,b)==gcd(a%b,b)。
因为a,b的公约数必然是a-b,b的公约数，因此gcd(a,b) <= gcd(a-b,b);另a-b,b的公约数也必然是a,b的公约数，因此gcd(a,b) >= gcd(a-b,b)，得：gcd(a,b) == gcd(a-b,b)。

扩展欧几里德算法

求解：a*x + b*y = gcd(a, b)

递归到最后一步：设r = gcd(r,0) = r*x' + 0*y'，此时，x'=1，y'=0
从最后一步往回推导，当已知下一步的x',y'如何求得上一步的x,y：
a*x + b*y = gcd(a, b) = gcd(b, a%b) = b*x' + (a%b)*y' = b*x' + (a-a/b*b)*y' = a*y' + b*(x'-a/b*y')
因此：x=y', y=x'-a/b*y'

求解：a*x + b*y = c

当且仅当：c%gcd(a,b)==0时方程有解。 
可以先求出a*x+b*y=gcd(a,b)的解x',y'
将x',y'同时扩大c/gcd(a,b)倍得到a*x+b*y=c的一组解：
x0 = x' * c/gcd(a,b), y0 = y' * c/gcd(a,b)
通解为：
x = x0 + (b/gcd)*t, y = y0 – (a/gcd)*t
可见，对于通解x而言，以b/gcd为周期，因此最小整数解为：((x' * c/gcd) % (b/gcd) + (b/gcd)) % (b/gcd)

r = φ(N)，e * d = 1 (mod r)，求：e关于r的模反元素（模逆元）d

e * d - r * k = 1，由a*x + b*y = c有通解的充要条件：c%gcd(a,b)==0，因此gcd(e,r)=1
因此可以通过扩展欧几里德算法，求得d0，根据通解：d = d0 + (r/gcd(e,r)) * t，以(r/gcd(e,r))=r为周期，因此一定存在一个最小整数d'是e关于r的模反元素，在(0,r)之间

中国剩余定理（孙子问题，Chinese Remainder Theorem, CRT）

今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？

解法分三步：

找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。
用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗2得到和233。
用233除以3，5，7三个数的最小公倍数105，得到余数23，即233%105=23。这个余数23就是符合条件的最小数。

原理：

假设n1是满足除以3余2的一个数，比如2，5，8等等，也就是满足3∗k+2（k>=0）的一个任意数。同样，我们假设n2是满足除以5余3的一个数，n3是满足除以7余2的一个数。

从n1出发，已知n1满足除以3余2，尝试寻找合适的n1+n2的和仍然满足除以3余2，进而寻找合适的n1+n2+n3的和仍然满足除以3余2。根据a%b=c，则有(a+k∗b)%b=c(k为非零整数)。因此，如果n2是3的倍数，n1+n2的和将仍然满足除以3余2，同理，如果n3是3的倍数，则n1+n2+n3的和仍然满足除以3余2。同理，对于n2和n3，可知：

为使n1+n2+n3的和满足除以3余2，n2和n3必须是3的倍数。
为使n1+n2+n3的和满足除以5余3，n1和n3必须是5的倍数。
为使n1+n2+n3的和满足除以7余2，n1和n2必须是7的倍数。

因此，为使n1+n2+n3的和作为“孙子问题”的一个最终解，需满足：

n1除以3余2，且是5和7的公倍数。
n2除以5余3，且是3和7的公倍数。
n3除以7余2，且是3和5的公倍数。

孙子问题解法的本质：是从5和7的公倍数中找一个除以3余2的数n1，从3和7的公倍数中找一个除以5余3的数n2，从3和5的公倍数中找一个除以7余2的数n3，再将三个数相加得到解。在求n1，n2，n3时又用了一个小技巧，以n1为例，并非从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2（如果a%b=c，那么(a∗k)%b=a%b+a%b+…+a%b=c+c+…+c=k∗c(k>0)，也就是说，如果一个除法的余数为c，那么被除数的k倍与除数相除的余数为k∗c）。也就是通过扩展欧几里德算法先求出5和7的公倍数模3下的逆元，再用逆元去乘余数。

最后，n1+n2+n3只是问题的一个解，并不是最小的解。如何得到最小解？我们只需要从中最大限度的减掉3，5，7的公倍数105即可。原理是前面讲过的定理“如果a%b=c，则有(a−k∗b)%b=c”。所以(n1+n2+n3)%105是最终的最小解。

Gauss Algorithm

\[已知：m_i\equiv m\bmod N_i\\m=\sum_{i=1}^k m_i*t_i*(t_i^{-1}\bmod N_i)\pmod {\prod_{i=1}^k N_i} (其中t_i=(\prod_{i=1}^k N_i)/N_i)\]

Garner Algorithm

\[将N_1,N_2\ldots,N_k视作混合基数（mixed radix），寻求将m表达为：\\m=x_1+x_2*N_1+x_3*N_1*N_2+\ldots+x_k*N_1\ldots*N_{k-1}\\如果可以通过m_i对应求得x_i，代入上式即可求得m。为表达方便记：r_{ij} = N_i^{-1} \pmod{N_j}\\显然：x_1 \equiv m_1 \pmod{N_1}\\m_2 \equiv x_1 + x_2*N_1 \pmod{N_2}\\m_2 - x_1\equiv x_2*N_1\pmod{N_2}\\(m_2 - x_1)*r_{12} \equiv x_2 \pmod{N_2}\\x_2 \equiv (m_2 - x_1)*r_{12}\pmod{N_2}\\同理：x_3 \equiv ((m_3 - x_1)*r_{13} - x_2)*r_{23} \pmod{N_3}\]

for (int i = 0; i < k; ++i) {
    x[i] = m[i];
    for (int j = 0; j < i; ++j) {
        x[i] = r[j][i] * (x[i] - x[j]);
        x[i] = x[i] % N[i];
        if (x[i] < 0)
            x[i] += N[i];
    }
}

特别地，当k=2时，用于CRT_RSA加速解密：

\[c^d=m\bmod N，因此：c_p^d=(k*N+m)\bmod p=m\bmod p（因为N=p*q）\\m_p=c_p^d=c^{d\bmod \varphi(p) + k*\varphi(p)}\bmod p=c^{d\bmod \varphi(p)}*c^{\varphi(p)*k}\bmod p=c^{d\bmod \varphi(p)}\bmod p\\因为：c^{\varphi(p)}\bmod p=1，当p为质数时\varphi(p)=p-1，因此：c_p^d\equiv c_p^{d\bmod (p-1)}\bmod p\\同理：m_q=c_q^d\equiv c_q^{d\bmod (q-1)}\bmod q\\因此：m=m_p*q*(q^{-1}\bmod p)+m_q*p*(p^{-1}\bmod q)\bmod N\\根据中国剩余定理推论：p*(p^{-1}\bmod q)+q*(q^{-1}\bmod p)=1\bmod N\\p*(p^{-1}\bmod q)=1-q*(q^{-1}\bmod p)\bmod N\\因此：m=m_p*q*(q^{-1}\bmod p)+m_q*(1-q*(q^{-1}\bmod p))\bmod N\\=m_q+(m_p-m_q)*q*(q^{-1}\bmod p)\bmod N\\=m_q+((m_p-m_q)*(q^{-1}\bmod p)\bmod p)*q（因为k*q\bmod p*q=(k\bmod p)*q）\\因为m_q<1*q且(m_p-m_q)*(q^{-1}\bmod p)\bmod p<p，因此上式小于p*q=N，无需再模N\]

简单地，令N_1=q，N_2=p可以直接通过Garner’s Algorithm直接得到：

\[m=m_q+((m_p-m_q)*(q^{-1}\bmod p)\bmod p)*q\]

先对c mod p，再求d mod (p-1)次幂要比直接求c的d次幂效率会高。因此，利用RSA私钥文件中的prime1（p），prime2（q），exponent1（d mod (p-1) ），exponent2（d mod (q-1) ），coefficient（(inverse of q) mod p ）即可加速解密。

当d太大时，也可以先求c mod p，再求e对(p-1)模逆次幂，因为：

\[m^e=c\bmod N,因此：c=m^e-k*N，取d'=invert(e,\varphi(p))\\c_p^{d'}=(m^e-k*N)^{d'}=m^{e*d'}=m\bmod p（因为N=p*q）\\因为m\equiv c^{d\bmod \varphi(p)}\equiv c^{d'}\bmod p，且d\bmod \varphi(p) < \varphi(p)，d'=invert(e,\varphi(p))<\varphi(p)\\因此d'=invert(e,\varphi(p))=d\%\varphi(p)=invert(e,\varphi(N))\%\varphi(p)\]

Gauss Algorithm另一种表达方式

\[因为：p*p^{-1}\equiv p^{q-1}\equiv 1\bmod q\\m=\sum_{i=1}^k m_i*t_i^{(N_i-1)}\pmod {\prod_{i=1}^k N_i}\]

特别地，当k=2时：

\[m=m_p*q^{p-1}+m_q*p^{q-1}\pmod N\\=c_p^d*q^{p-1}+c_q^d*p^{q-1}=(c_p^{d\bmod (p-1)}\bmod p)*q^{p-1}+(c_q^{d\bmod (q-1)}\bmod q)*p^{q-1}\pmod N\]

推论：

\[N=lcd(N_1,N_2,...N_k)，对所有整数x和a:\\x\equiv a\bmod N_i当且仅当x\equiv a\bmod N\\证明：已知a=k*N+x，则a\%N_i=x\\已知a\%N_i=x，则(a-x)\%N_i=0，(a-x)是N_i公倍数，因此(a-x)\%N=0，即a\%N=x，得证\\特别地，N_1,N_2,...,N_k两两互质，N=lcd(N_1,N_2,...N_k)=N_1*N_2*...N_k，对所有整数x和a:\\x\equiv a\bmod N_i当且仅当x\equiv a\bmod N\]

特别地，当k=2时：

\[1\equiv a\bmod p,1\equiv a\bmod q\\利用剩余定理求a=1*p*(p^{-1}\bmod q)+1*q*(q^{-1}\bmod p)\equiv 1\bmod(p*q=N)\]

中国剩余定理扩展（模数不互素）

如果模数不互素，则需要将不互素的方程两两合并：

\[x=a_1+m_1*x_1\\x=a_2+m_2*x_2\\因此：a_1+m_1*x_1=a_2+m_2*x_2\\得到：m_1*x_1+m_2*x_2=a_2-a_1\\利用扩展欧几里德算法求得x_1的最小正整数解，代回a_1+m_1*x_1，得到x的最小正整数解x'\\所以，x的通解是x'加上lcm(m_1,m_2)*k，这样才能保证x模m_1和m_2的余数是a_1和a_2\\因此，把x'当作新方程的余数，把lcm(m_1,m_2)当作新方程的模数，即合并得到：\\x=x'\pmod {lcm(m_1,m_2)}\]

wiener attack攻击原理（连分数）

\[任意一个数都可以展开成连分数：x=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{...}}}}\\ 展开成连分数就是对分子分母做辗转相除，因此，有理数的连分数是有限的，会停在两者的最大公约数，无理数连分数展开无限。\\ 把i个分母后面的分数略去，称为第i个渐进分数，i越大，离x越近,如圆周率的疏率和密率：\\ \frac{22}{7}=3+\frac{1}{7}\\ \frac{355}{113}=3+\frac{1}{7+\frac{1}{16}}\\ 对于RSA，N=pq，\varphi(N)=(p-1)(q-1)=p*q-(p+q)+1=N-(p+q)+1\\ e*d=k*\varphi(N)+1，两边同除d*\varphi(N)\\ \frac{e}{\varphi(N)}-\frac{k}{d}=\frac{1}{d*\varphi(N)}\\ 由于p，q都非常大，p*q远大于(p+q)，N约等于\varphi(N)\\ \frac{e}{N}-\frac{k}{d}=\frac{1}{d*\varphi(N)}\\ 由于d*\varphi(N)很大，因此\frac{e}{N}略大于\frac{k}{d}，由于e，N已知，计算e，N的连分数展开\\ 依次计算每一个渐进分数，wiener证明了，该攻击能精确覆盖到k/d\\ 定理2：满足|x-\frac{c}{d}|<\frac{1}{2d^2}时，\frac{c}{d}是x的渐进分数。\\ 已知e，N，k，d，根据e*d=k*\varphi(N)+1，求得\varphi(N)\\ 构造方程：x^2-(p+q)x+p*q=0，有解时，解为p，q\\ b=p+q=N-\varphi(N)+1，c=p*q=N，代入b^2-4*c为完全平方数\]

扩展应用

\[N_1=p_1^rq_1,N_2=p_2^rq_2,p_1>p_2\\ |\frac{N_2}{N_1}-\frac{q_2}{q_1}|=\frac{q_2N_1-q_1N_2}{q_1N_1}=\frac{q_1q_2(p_1^r-p_2^r)}{q_1^2p_1^r}\\ 由定理2，当\frac{q_1q_2(p_1^r-p_2^r)}{q_1^2p_1^r}<\frac{1}{2q_1^2}，即p_1^r-p_2^r<\frac{p_1^r}{2q_1q_2}时，通过可求\frac{N_2}{N_1}渐进分数求\frac{q_2}{q_1}\]

Pollard-Rho算法分解大整数，比试除法快多个量级

生日悖论：如果一年中有N天（地球365），那么每k=N^(1/2)个人中有50%的可能性生日冲突。

如果问多少个数整除N，答案只有两个，p和q
如果问多少个数使得gcd(x,N)>1，答案便很多：p,2p,3p...(q-1)p,q,2q,...(p-1)q，有p+q-2个数。

因此，采用如下策略：

在区间[2, N-1]随机选取k个数，x1，…，xk
判断是否存在gcd(xi-xj,N)>1，若存在，gcd(xi-xj,N)是N的一个因子（p或q）

需要选取大约N^(1/4)个数，为了解决数太多无法存储的问题，Pollard-Rho算法通过函数f生成伪随机数列，对该数列产生的连续两个数作差求gcd，则无需存储所有的数。常用的伪随机数列生成函数为：f(x)=(x**2+a)%N

为了探测是否陷入f环，设置两个指针，一个走一步，一个走两步，当后者赶上（等于）前者时，表示陷入f环，此时，重新找一个函数f，或者重新选一个随机种子。