rsa_attack

发表于 更新于 分类于 阅读次数： 阅读次数：

分解n

1.当n比较小的情况下，使用sagemath的factor或者http://www.factordb.com/index.php

2.当生成的p，q接近的时候，使用费马分解或者yafu分解

理论证明：
$$
因为|p-q|小，则|p-q|^2小
$$

$$
那么\frac{|p+q|^2}{4}=\frac{|p-q|^2}{4}+n略大于n
$$

$$
对于\frac{|p+q|^2}{4}-n=\frac{|p+q|^2}{4}-p*q=\frac{|p-q|^2}{4}就小
$$

$$
\frac{|p+q|}{2}也略大于\sqrt{n}那么从\sqrt{n}开始寻找到一个x，
$$

$$
满足x^2-n=y^2为一个完全平方数，其中x=\frac{|p+q|}{2}，y=\frac{|p-q|}{2}，这样就分解出p，q
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def fermat(n):
    a = isqrt(n)
    b2 = a * a - n
    b = isqrt(n)
    count = 0
    while b * b != b2:
        a = a + 1
        b2 = a * a - n
        b = isqrt(b2)
        count += 1
    p = a + b
    q = a - b
    assert n == p * q
    return p, q

3.出现多个pi得到n的情况下，注意是否有重复的pi，不可单纯使用(pi-1)的手法获得phi，注意使用欧拉公式来计算phi

需要得到标准分解式子，
$$
n=\prod_{i=1}^{m}{p_i}^{k_i}
$$

然后
$$
phi=\prod_{i=1}^{m}{p_i}^{k_i-1}({p_i}-1)
$$

特殊情况下的e，p，q

第一大种情况：e特殊

1.如果e过于小
$$
c\equiv m^e \pmod p
$$

$$
m^e = c+k\times N
$$

$$
m = \sqrt[e]{c+k\times n}
不难直接爆破k获得m
$$

2.如果e刚好等于2时

e=2会得到一种基于RSA的衍生算法，Rabin算法，根据上面的公式不难想出
$$
m_p \equiv \sqrt{c} \bmod p
$$

$$
m_q \equiv \sqrt{c} \bmod q
$$

根据扩展欧几里得公式可以求出
$$
y_p \cdot p + y_q \cdot q = 1 中的y_p和y_q
$$
根据孙子定理解出4个明文
$$
a = (y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p)\bmod n
$$

$$
b = n - a
$$

$$
c = (y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \bmod n\
$$

$$
d = n - c
$$

ps:其中一般来说
$$
p \equiv q \equiv 3 \pmod 4
$$
则费马小定理计算的知识
$$
m_p \equiv c^\frac{(p+1)}{4} \bmod p\
$$

$$
m_q \equiv c^\frac{(q+1)}{4} \bmod q
$$

3.多个k进行多轮的加密，并且已知e，d，phi
$$
设c \equiv m^{k1k2k3…}\pmod n
$$

$$
设m^{x} \equiv c \pmod n
$$

$$
存在ed - 1=k*phi
$$

$$
y \equiv x^{-1} \pmod {k*phi}
$$

$$
xy \equiv 1\pmod {phi}
$$

$$
c^{y} \equiv m^{xy} \equiv m \pmod n
$$

4.根据3的问题，如果已知d，如何对p，q进行恢复

https://www.di-mgt.com.au/rsa_factorize_n.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def gcd(a, b):
   if a < b:
     a, b = b, a
   while b != 0:
     temp = a % b
     a = b
     b = temp
   return a
 
def getpq(n,e,d):
        p = 1
        q = 1
        while p==1 and q==1:
                k = d * e - 1
                g = random.randint ( 0 , n )
                while p==1 and q==1 and k % 2 == 0:
                        k /= 2
                        y = pow(g,k,n)
                        if y!=1 and gcd(y-1,n)>1:
                                p = gcd(y-1,n)
                                q = n/p
        return p,q

第二大种情况：p，q特殊

1.p与q的生成具有一定的关系，那么

法一：可以根据n=p*q关系求出一个近似p的值，去寻找符合条件的p或者q值

法二：可以使用高位爆破的方法对p进行爆破，通过检测生成的n值进行寻找

2.p-1或者p+1是光滑的

1
from Crypto.Util.number import getPrime

所生成的素数是根据前10000个素数的相乘+1来生成的，那么根据p-1光滑理论

参考：https://blog.csdn.net/qq_42667481/article/details/106729900

p+1光滑

参考：https://blog.csdn.net/m0_62506844/article/details/125774485