Rsa基础知识

1	rsa是经常出现在ctf考题中的一类题，它是基于大素因数分解难题产生的公钥密码

数学基础

素数

素数又叫质数，除了1和其本身，不能被其他数整除的数叫做素数

模运算

模运算是取余运算，其符号为 $mod$

同余

两个数 $a$ ， $b$ 对同一个数 $m$ 取余结果相同，则称 $a$ 与 $b$ 模 $m$ 同余

互质

当两个正整数除了1之外没有其他公因子，我们就称这两个数互质

任意两个质数一定互质

欧拉函数

数论中，对正整数 $n$ ，欧拉函数 $\varphi(n)$ 指的是小于或等于 $n$ 的正整数中与 $n$ 互质的数

易知质数 $n$ 的欧拉函数是 $n-1$

若不是质数，其欧拉函数有公式：

欧拉定理

若两个正整数 $a,\ n$ 互质，则如下等式成立

$a^{\varphi(n)}\equiv1\mod{n}$

费马小定理

是欧拉定理的特例，当 $n$ 是质数并且 $a$ 和 $n$ 互质

$a^{p-1}\equiv1\mod{p}$

模逆元

对整数 $a,b$ ，若 $ab\equiv1\mod{n}$ 则称 $a$ 和 $b$ 关于模 $n$ 互为模倒数，也称为模反元素或模逆元，还可以记作

$b=a^{-1}\mod{n}$

Rsa原理

准备两个非常大的素数 $p,q$
计算 $n=p*q$
计算 $\varphi(n)$ ，由于 $p,\ q$ 都是素数，所以 $\varphi(\ n)=\varphi(\ p)*\varphi(\ q)$ ，根据数论基础知识， $\varphi({\ p})=\ p\ -\ 1,\varphi({\ q})=\ q\ -\ 1$
选取公钥 $e$ 与 $\varphi(n)$ 互素 $\varphi(\ p)$
求得私钥 $d$ ， $d*e\equiv1\mod{\varphi(n)}$ ，也就是 $d$ 是 $e$ 模 $\varphi(n)$ 的逆元

加密公式

用公钥对明文 $m$ 进行加密，得到密文 $c$

$c=E(m)=m^{e}\mod{n}$

解密公式

用私钥进行解密

$m=D({c})=c^{d}\mod{n}$

RSA证明

由于 $d*e\equiv1\mod{\varphi(n)}$ ，所以 $d*e=k*{\varphi(n)}+1$

已知 $c\equiv m^{e}\mod{n}$ ，则

$\begin{aligned} c^{d}\mod{n}&\equiv m^{e*d}\mod{n} \\&\equiv m^{k*\varphi(n)+1}\mod{n} \end{aligned}$

此时要分情况讨论

当 $m$ 和 $n$ 互质的时候

有 $\ m^{\varphi(n)}=1\mod{n}$ 则此时有

$\begin{aligned} m^{k*\varphi(n)}&\equiv1^{k}\mod{n} \\&\equiv 1\mod{n} \\m^{k*\varphi(n)+1}&\equiv m\mod{n} \end{aligned}$

也就是说 $c^d\mod{n}\equiv m$
当 $m$ 和 $n$ 不互质的时候

由于 $m<n,n=pq$ ，所以 $m$ 是 $p$ 或者 $q$ 的倍数，意为 $m=t*q$ ，这里的 $t$ 为正整数

也就是说 $gcd(m,p)=1$

由费马小定理， $m^{\varphi(p)}=1\mod{p}$ ，两边同时进行 $\varphi(q)$ 次方得到 $m^{\varphi(n)}\equiv1\mod{p}$ ，

那么存在正整数n，使得 $m^{\varphi(n)}=1+n*p$

两边同时乘以 $m=t*q$ ，得到 $m^{\varphi(n)+1}= m+nt*p*q$ ，也即是

$m^{\varphi(n)+1}\equiv m\mod{n}$

Rsa常见攻击方式

关于模数的攻击

模不互素

攻击原理

当两个模数 $n$ 不互素的时候，其公因子就是 $p$ 或 $q$ ，因此可以直接将 $n$ 分解

共模攻击

生成秘钥的过程中使用了相同的模数n，此时用不同的秘钥e加密同一信息m：

$c_1=m^{e_1}\mod{n}$

$c_2=m^{e_2}\mod n$

若是两次生成的公钥 $\ e_1$ 和 $\ e_2$ 互素，则根据扩展欧几里得算法，存在 $s$ 和 $t$ 使得：

$s*{e_1}+t*{e_2}=gcd(e_1,e_2)=1$

所以

$\begin{aligned} c_1^sc_2^t &\equiv m^{se_1}m^{te_2} \mod n \\&\equiv m^{se_1+te_2} \mod n \\&\equiv m \mod n \end{aligned}$

因此只要计算 $c_1^sc_2^t$ 即可得出明文c

此处贴上通解代码：

import primefac

 def same_n_attack(n,e1,e2,c1,c2):
     def egcd(a,b):
         x, lastX = 0, 1
         y, lastY = 1, 0
         while (b != 0):
             q = a // b
             a, b = b, a % b
             x, lastX = lastX - q * x, x
             y, lastY = lastY - q * y, y
         return (lastX, lastY)
     s = egcd(e1,e2)
     s1 = s[0]
     s2 = s[1]
     if s1 < 0:
         s1 = -s1
         c1 = primefac.modinv(c1, n)
         if c1 < 0:
             c1 += n
     elif s2 < 0:
         s2 = -s2
         c2 = primefac.modinv(c2, n)
         if c2 < 0:
             c2 += n
     m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
     return m

dp泄露

首先 $dp \equiv d \mod (p-1)$ ，这个 $dp$ 是比较重要的，因为其中蕴含了 $p$ 的信息，只要稍加推导就能得到 $p$ 和 $q$ 。

此时推导如下：

$\begin{aligned} dp*e &\equiv d*e \mod (p-1) \\ dp*e &= d*e+k_1*(p-1) \\d*e &= dp*e+k_1(p-1) \end{aligned}$

由于 $d*e \equiv 1 \mod \varphi(n)$ ，所以

$\begin{aligned} dp*e+k_1(p-1) &\equiv 1\mod \varphi(n) \\dp*e+k_1(p-1) &\equiv 1\mod (p-1)(q-1) \\dp*e+k_1(p-1) &= k_2*(p-1)(q-1)+1 \\dp*e &= k_2(p-1)(q-1)+1-k_1(p-1) \\dp*e &= (k_2(q-1)-k_1)(p-1)+1 \\令(k_2(q-1)-k_1)&为x，则该式变成: \\dp*e &= x(p-1)+1 \end{aligned}$

此时由于 $dp<(p-1)$ ，因此 $e>x$ ，所以 $x$ 就在 $(1,e)$ ，此时只要遍历 $(1,e)$ ，并且计算

$(dp*e-1)/x$

只要最后结果是整数，那么就大概率是 $(p-1)$ ，这时候继续往下算，如果解密结果不是乱码就基本上是正确的了。脚本如下：

for i in range(1,e):
    if (dp*e-1)%i == 0:
        if n%(((dp*e-1)/i)+1)==0:
            p=((dp*e-1)/i)+1
            q=n/(((dp*e-1)/i)+1)
            phi = (p-1)*(q-1)
            d = gmpy2.invert(e,phi)%phi

e特别大的情况

$e$ 特别大的时候遍历都需要花很长的时间，再进行判断以及计算更需要大量时间，可能跑一年都跑不出来。这时候我们换一种分析方式：

$\begin{aligned} dp*e &\equiv d*e \mod (p-1) \\dp*e &\equiv 1 \mod(p-1) \\2^{dp*e-1} &\equiv 1 \mod p \\k*p&= 2^{dp*e-1}-1 \\p&=gcd(2^{dp*e-1}-1,n) \end{aligned}$

有关rsa