跳转至

RSA

常用工具

分解大素数

factordb （http://www.factordb.com）

yafu（p,q相差过大或过小yafu可分解成功）

sage （divisors(n)）（小素数）

Pollard’s p−1 （python -m primefac -vs -m=p-1 xxxxxxx）（光滑数）

Williams’s p+1（python -m primefac -vs -m=p+1 xxxxxxx）（光滑数）

在线sage环境：https://sagecell.sagemath.org/
Openssl

解析加密密钥：

openssl rsa -pubin -text -modulus -in pub.key

生成解密密钥：

python rsatool.py -f PEM -o key.key -p 1 -q 1 -e 1

openssl rsautl -decrypt -inkey key.pem -in flag.enc -out flag

openssl rsautl -decrypt -oaep -inkey key.pem -in flag.enc -out flag （OAEP方式）

脚本生成解密密钥：

# coding=utf-8
import math
import sys
from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)
keypair.p =
keypair.q =
keypair.e =
keypair.n = keypair.p * keypair.q
Qn = long((keypair.p - 1) * (keypair.q - 1))

i = 1
while (True):
    x = (Qn * i) + 1
    if (x % keypair.e == 0):
        keypair.d = x / keypair.e
        break
    i += 1
private = open('private.pem', 'w')
private.write(keypair.exportKey())
private.close()
脚本集
+ <https://github.com/Ganapati/RsaCtfTool>


#用法一：已知公钥(自动求私钥)
  $ python3 RsaCtfTool.py --publickey 公钥文件 --uncipherfile 加密文件

#用法二：已知公钥求私钥
  $ python3 RsaCtfTool.py --publickey 公钥文件 --private

#用法三：密钥格式转换
  #把PEM格式的公钥转换为n，e
  $ python3 RsaCtfTool.py --dumpkey --key 公钥文件
  #把n,e转换为PEM格式
  $ python3 RsaCtfTool.py --createpub -n 782837482376192871287312987398172312837182 -e 65537
+ https://github.com/yifeng-lee/RSA-In-CTF + https://github.com/ValarDragon/CTF-Crypto

​

常见类型

给p,q,e,c

import gmpy2 as gp
import binascii
p =  
q =  
e =  
c =  
n = p*q
phi = (p-1)*(q-1)
d = gp.invert(e,phi)
m = pow(c,d,n)
print(m)
print(bytes.fromhex(hex(m)[2:]))

​

给n,e,dp,c

$$dp\equiv d \pmod {(p-1)}$$

$$\because dp\cdot e\equiv d\cdot e\equiv 1 \pmod {(p-1)}$$

$$\therefore dp\cdot e-1=k\cdot (p-1)$$

$$\therefore (dp\cdot e-1)\cdot d\cdot e=k’\cdot (p-1),\quad k’=k\cdot d\cdot e \ \Leftrightarrow d\cdot e=-k’\cdot (p-1)+dp\cdot e\cdot d\cdot e\equiv 1 \pmod{\varphi(n)} \ \Leftrightarrow -k’\cdot (p-1)+dp\cdot e\equiv 1\pmod{\varphi(n)}$$

$$\therefore k_{1}\cdot (p-1)+dp\cdot e-1=k_{2}\cdot (p-1)\cdot (q-1) \ \Leftrightarrow (p-1)\cdot (k_{2}\cdot (q-1)-k_{1})+1=dp\cdot e$$

$$\because dp<p-1\quad \therefore (k_{2}\cdot (q-1)-k_{1})\in (0, e)$$

$$\therefore$$ 遍历 $$(1, e)$$，当同时满足 $$(dp\cdot e-1)\bmod i==0$$ 和 $$n\bmod((dp\cdot e-1)//i+1)==0$$ 时，$$N$$ 成功分解。

import gmpy2 as gp

e = 
n = 
dp = 
c = 

for x in range(1, e):
    if(e*dp%x==1):
        p=(e*dp-1)//x+1
        if(n%p!=0):
            continue
        q=n//p
        phin=(p-1)*(q-1)
        d=gp.invert(e, phin)
        m=gp.powmod(c, d, n)
        if(len(hex(m)[2:])%2==1):
            continue
        print('--------------')
        print(m)
        print(hex(m)[2:])
        print(bytes.fromhex(hex(m)[2:]))
  • 变种1：给 $$p,e,d_p,c,b$$，其中 $$n=p^bq$$。

Hensel lifting for Takagi’s scheme（p.189）：

Hensel_lifting_for_Takagi's_scheme

from Crypto.Util.number import *
import gmpy2
p = 
dp = 
c = 
b = 
e = 
mp1 = pow(c, dp, p)
mp = pow(c, dp - 1, p)
for i in range(1, b - 2):
    x = pow(c - pow(mp1, e), 1, p**(i + 1))
    y = pow(x * mp * (gmpy2.invert(e, p)), 1, p**(i + 1))
    mp1 = mp1 + y
print(long_to_bytes(mp1))
  • 变种2：给 $$n,e,dp_0,c,k$$，其中 $$dp_0$$ 为 $$dp$$ 高 $$(n\text{bits}-k)$$ 位，即 $$dp_0=dp>>k$$。

（Coppersmith攻击，已知dp高位攻击）

$$e\cdot dp \equiv e\cdot d\equiv 1 \pmod {(p-1)} \ \Leftrightarrow e \cdot dp=k(p-1)+1=kp-k+1 \ \Leftrightarrow e\cdot dp+k-1 \equiv 0 \pmod p$$

$$\because dp<p-1$$，$$\therefore k<e$$

$$\therefore e\cdot (dp_0<<k+x)+k-1 \equiv 0 \pmod p$$

#Sage
dp0 = 
e = 
n = 

F.<x> = PolynomialRing(Zmod(n))
d = inverse_mod(e, n)
for k in range(1, e):
    f = (secret << 200) + x + (k - 1) * d
    x0 = f.small_roots(X=2 ** (200 + 1), beta=0.44, epsilon=1/32)
    if len(x0) != 0:
        dp = x0[0] + (secret << 200)
        for i in range(2, e):
            p = (e * Integer(dp) - 1 + i) // i
            if n % p == 0:
                break
        if p < 0:
            continue
        else:
            print('k = ',k)
            print('p = ',p)
            print('dp = ',dp)
            break
* 变种3：给 $$n,e,dp,c$$​​，其中 $$dp$$​​​ 很小，$$e$$ 很大。

枚举 $$dp$$，因 $$e\cdot dp \equiv 1 \pmod {(p-1)}$$，又由费马小定理，对任意 $$r$$，有 $$m^{e \cdot dp}\equiv m \pmod p$$，即 $$p \mid (m^{e \cdot dp}-m)$$；

又 $$p \mid n$$，很大概率 $$p=\gcd(m^{e \cdot dp}-m,n)$$。

​

给p,q,dp,dq,c

$$dp=d \bmod (p-1)$$，$$dq=d \bmod (q-1)$$

$$\because d=k_{1}(p-1)+dp=k_{2}(q-1)+dq \ \Leftrightarrow k_{1}(p-1)=(dq-dp)+k_{2}(q-1) \ \Leftrightarrow k_{1}\frac{p-1}{\gcd(p-1,q-1)}=\frac{dq-dp}{\gcd(p-1,q-1)}+k_{2}\frac{q-1}{\gcd(p-1,q-1)} \ \Rightarrow k_{1}\frac{p-1}{\gcd(p-1,q-1)}\equiv\frac{dq-dp}{\gcd(p-1,q-1)} \pmod {\frac{q-1}{\gcd(p-1,q-1)}} \ \Leftrightarrow k_{1}\equiv \text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{dq-dp}{\gcd(p-1,q-1)} \pmod {\frac{q-1}{\gcd(p-1,q-1)}}$$

将 $$k_{1}=k_{3}\frac{q-1}{\gcd(p-1,q-1)}+\text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{dq-dp}{\gcd(p-1,q-1)}$$

代入 $$d=k_{1}(p-1)+dp$$

$$d=k_{3}\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}+\text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{(dq-dp)(p-1)}{\gcd(p-1,q-1)}+dp \ \Rightarrow d\equiv \text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{(dq-dp)(p-1)}{\gcd(p-1,q-1)}+dp \pmod{\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}}$$

import gmpy2 as gp

p = 
q = 
dp = 
dq = 
c = 

n = p*q
phin = (p-1)*(q-1)
dd = gp.gcd(p-1, q-1)
d=(dp-dq)//dd * gp.invert((q-1)//dd, (p-1)//dd) * (q-1) +dq
print(d)

m = gp.powmod(c, d, n)
print('-------------------')
print(m)
print(hex(m)[2:])
print(bytes.fromhex(hex(m)[2:]))

​

低解密指数攻击/低私钥指数攻击（e长度较大，d小，Wiener Attack）

适用情况：已知 $$N,e$$，且 $$e$$ 过大或过小。

$$\varphi(n) = (p-1)(q-1)=pq - (p + q) + 1=N - (p + q) + 1$$

$$\because p, q$$ 非常大，$$\therefore\,pq\gg p+q$$， $$\therefore\varphi(n)\approx N$$

$$\because ed\equiv1\,mod\,\varphi(n)$$，$$\therefore ed-1=k\varphi(n)$$，这个式子两边同除 $$d\varphi(n)$$ 可得：

$$\cfrac{e}{\varphi(n)}-\cfrac{k}{d}=\cfrac{1}{d\varphi(n)}$$

$$\because \varphi(n)\approx N$$，$$\therefore \cfrac{e}{N}-\cfrac{k}{d}=\cfrac{1}{d\varphi(n)}$$，同样 $$d\varphi(n)$$ 是一个很大的数，所以 $$\cfrac{e}{N}$$ 略大于 $$\cfrac{k}{d}$$

因为 $$e$$ 和 $$N$$ 是知道的，所以计算出 $$\cfrac{e}{N}$$ 后，比它略小的 $$\cfrac{k}{d}$$ ，可以通过计算 $$\cfrac{e}{N}$$ 的连分数展开，依次算出这个分数每一个渐进分数，由于 $$\cfrac{e}{N}$$ 略大于 $$\cfrac{k}{d}$$，Wiener 证明了，该攻击能精确的覆盖 $$\cfrac{k}{d}$$。

在 $$e$$ 过大或过小的情况下，可使用算法从 $$e$$ 中快速推断出 $$d$$ 的值。可以解决 $$q<p<2q,d<\cfrac{1}{3}N^{\frac{1}{4}}$$ 的问题。

RSAWienerHacker工具：https://github.com/pablocelayes/rsa-wiener-attack

#脚本1（带工具）
#python2
import RSAwienerHacker
n =
e =
d =  RSAwienerHacker.hack_RSA(e,n)
if d:
    print(d)
import hashlib
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"
print flag

#脚本2
#sage
def rational_to_contfrac(x,y):
    # Converts a rational x/y fraction into a list of partial quotients [a0, ..., an]
    a = x // y
    pquotients = [a]
    while a * y != x:
        x, y = y, x - a * y
        a = x // y
        pquotients.append(a)
    return pquotients

def convergents_from_contfrac(frac):
    # computes the list of convergents using the list of partial quotients
    convs = [];
    for i in range(len(frac)): convs.append(contfrac_to_rational(frac[0 : i]))
    return convs

def contfrac_to_rational (frac):
    # Converts a finite continued fraction [a0, ..., an] to an x/y rational.
    if len(frac) == 0: return (0,1)
    num = frac[-1]
    denom = 1
    for _ in range(-2, -len(frac) - 1, -1): num, denom = frac[_] * num + denom, num
    return (num, denom)

n = 
e = 
c = 

def egcd(a, b):
    if a == 0: return (b, 0, 1)
    g, x, y = egcd(b % a, a)
    return (g, y - (b // a) * x, x)

def mod_inv(a, m):
    g, x, _ = egcd(a, m)
    return (x + m) % m

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def crack_rsa(e, n):
    frac = rational_to_contfrac(e, n)
    convergents = convergents_from_contfrac(frac)

    for (k, d) in convergents:
        if k != 0 and (e * d - 1) % k == 0:
            phi = (e * d - 1) // k
            s = n - phi + 1
            # check if x*x - s*x + n = 0 has integer roots
            D = s * s - 4 * n
            if D >= 0:
                sq = isqrt(D)
                if sq * sq == D and (s + sq) % 2 == 0: return d

d = crack_rsa(e, n)
m = hex(pow(c, d, n))[2:]
print(bytes.fromhex(m))

#脚本3
from Crypto.Util.number import long_to_bytes
e = 
n = 
c = 

#将分数x/y展开为连分数的形式
def transform(x,y):
    arr=[]
    while y:
        arr+=[x//y]
        x,y=y,x%y
    return arr

#求解渐进分数
def sub_fraction(k):
    x=0
    y=1
    for i in k[::-1]:
        x,y=y,x+i*y
    return (y,x)
data=transform(e,n)

for x in range(1,len(data)+1):
    data1=data[:x]
    d = sub_fraction(data1)[1]
    m = pow(c,d,n)
    flag = long_to_bytes(m)
    if b'flag{' in flag:
        print(flag)
        break
  • 变种1：$$\cfrac{N_1}{N_2}<\cfrac{q_1}{q_2}<1$$

参考：2020年羊城杯 - RRRRRRRSA

Paper: https://eprint.iacr.org/2015/399.pdf

尝试对 $$\cfrac{N_1}{N_2}$$ 进行连分数展开并求其各项渐进分数，记为 $$\cfrac{t_i}{s_i}$$ 并验证 $$N_1\% {t_k}==0$$ 是否成立，如果成立，那么 $$q_1=t_k，q_2=s_k$$。

连分数逼近：

def transform(x,y):    #使用辗转相除将分数x/y转为连分数的形式
    res=[]
    while y:
        res.append(x//y)
        x,y=y,x%y
    return res

def continued_fraction(sub_res):
    numerator,denominator=1,0
    for i in sub_res[::-1]:   #从sublist的后面往前循环
        denominator,numerator=numerator,i*numerator+denominator
    return denominator,numerator   #得到渐进分数的分母和分子，并返回

#求解每个渐进分数
def sub_fraction(x,y):
    res=transform(x,y)
    res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res)))))  #将连分数的结果逐一截取以求渐进分数
    return res

def wienerAttack(n1,n2):
    for (q2,q1) in sub_fraction(n1,n2):  #用一个for循环来注意试探n1/n2的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if q1==0:                    #可能会出现连分数的第一个为0的情况，排除
            continue
        if n1%q1==0 and q1!=1:           #成立条件
            return (q1,q2)
    print("该方法不适用")

N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
print(wienerAttack(N1,N2))

​

低加密指数广播攻击（Hastad攻击）

适用情况： $$n,c$$ 不同，$$m,e$$ 相同。一般会是 $$e=k$$，然后给 $$k$$ 组数据。

如果一个用户使用同一个加密指数 e 加密了同一个密文，并发送给了其他 e 个用户。那么就会产生广播攻击。这一攻击由 Håstad 提出。

使用不同的模数 $$n$$，相同的公钥指数 $$e$$ 加密相同的信息，就会得到多个 $$m^e \equiv c_i \pmod {n_i}$$，将 $$m^e$$ 视为一个整体 $$M$$，这就是典型的中国剩余定理适用情况。容易求得 $$m^e$$ 的值，当 $$e$$ 较小时直接开 $$e$$ 方即可，可使用gmpy2.iroot(M,e) 方法。

更一般情况（$$k$$ 组数据的 $$N$$ 不同）见15。

#sage
def chinese_remainder(modulus, remainders):
 Sum = 0
    prod = reduce(lambda a, b: a*b, modulus)
 for m_i, r_i in zip(modulus, remainders):
        p = prod // m_i
     Sum += r_i * (inverse_mod(p,m_i)*p)
    return Sum % prod
chinese_remainder([3,5,7],[2,3,2]) #23

#sage
crt([2,3,2],[3,5,7])

​

共模攻击（n,m相同，c,e不同）

当$$n$$不变的情况下，知道$$n,e_1,e_2,c_1,c_2$$可以在不知道$$d_1,d_2$$的情况下，解出$$m$$。

首先假设$$e_1,e_2$$互质,

即 $$\gcd(e_1,e_2)=1$$

此时则有 $$e_1s_1+e_2s_2 = 1$$

式中，$$s_1,s_2$$皆为整数，但是一正一负。

通过扩展欧几里德算法，我们可以得到该式子的一组解$$（s_1,s_2）$$，假设$$s_1$$为正数,$$s_2$$为负数。

因为 $$c_1 = m^{e_1}\bmod n, c_2 = m^{e_2}\bmod n$$

所以 $$(c_1^{s_1}c_2^{s_2})\bmod n = ((m^{e_1}\bmod n)^{s_1}(m^{e_2}\bmod n)^{s_2})\bmod n$$

根据模运算性质，可以化简为 $$(c_1^{s_1}c_2^{s_2})\bmod n = ((m^{e_1})^{s_1}(m^{e_2})^{s_2})\bmod n$$

即 $$(c_1^{s_1}c_2^{s_2})\bmod n = (m^{e_1s_1+e_2s_2})\bmod n$$

又前面提到 $$e_1s_1+e_2s_2 = 1$$

所以 $$(c_1^{s_1}c_2^{s_2})\bmod n = m\bmod n$$

即 $$c_1^{s_1}c_2^{s_2}= m$$

import gmpy2 as gp
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

n = 
c1 = 
c2 = 
e1 = 
e2 = 
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
if s1<0:
    s1 = - s1
    c1 = gp.invert(c1, n)
elif s2<0:
    s2 = - s2
    c2 = gp.invert(c2, n)

m = pow(c1,s1,n)*pow(c2,s2,n) % n
print(hex(m)[2:])
print(bytes.fromhex(hex(m)[2:]))

​

e,m相同，多个n中存在两个n有GCD（模不互素）

适用情况：存在两个或更多模数 ，且 $$\gcd(n_1,n_2)\ne 1$$ 。

多个模数 $$n$$ 共用质数，则可以很容易利用欧几里得算法求得他们的质因数之一 $$\gcd(n_1,n_2)$$，然后这个最大公约数可用于分解模数分别得到对应的 $$p$$ 和 $$q$$，即可进行解密。

import gmpy2 as gp

n=[]
for i in n:
    for j in n:
        if (i<>j):
            pub_p=gp.gcdext(i,j)
            if (pub_p[0]<>1)&(i>j):
                print(i)
                print(j)
                print(pub_p[0])
                a=i,p=pub_p[0]
q=a//p
p =
q =
e =
c =
n = p*q
phi = (p-1) * (q-1)
d = gp.invert(e, phi)
m = pow(c, d, n)
print(hex(m)[2:])
print(bytes.fromhex(hex(m)[2:]))

​

Rabin加密

适用情况：$$e=2$$ 。

一般先通过其他方法分解得到 $$p,q$$，然后解密。

函数返回四个数，这其中只有一个是我们想要的明文，需要通过其他方式验证。

import gmpy2

def rabin_decrypt(c, p, q, e=2):
    n = p * q
    mp = pow(c, (p + 1) // 4, p)
    mq = pow(c, (q + 1) // 4, q)
    yp = gmpy2.invert(p, q)
    yq = gmpy2.invert(q, p)
    r = (yp * p * mq + yq * q * mp) % n
    rr = n - r
    s = (yp * p * mq - yq * q * mp) % n
    ss = n - s
    return (r, rr, s, ss)

c = 
p = 
q = 
m = rabin_decrypt(c,p,q)
for i in range(4):
    try:
        print(bytes.fromhex(hex(m[i])[2:]))
    except:
        pass

​

Boneh and Durfee attack

$$e$$ 非常大接近于$$N$$，即 $$d$$ 较小时。与低解密指数攻击类似，比低解密指数攻击（Wiener Attack）更强，可以解决$$\cfrac{1}{3}N^{\frac{1}{4}} \leq d \leq N^{0.292}$$的问题。

参考 https://github.com/mimoo/RSA-and-LLL-attacks 。

2k [(N + 1)/2 + (-p -q)/2] + 1 = 0 mod e

Boneh and Durfee attack:
f(x,y) = 1 + x * (A + y)
e d = x [(N + 1)/2 + y] + 1
故：
x = 2k
y = (-p-q)/2
  • 变种1：$$e$$ 很大，$$dp$$ 很小，且 $$d>2N^{\beta}$$。

May’s Attack

假设 $$e<\varphi(N),q \le N^{\beta},\beta \le \frac{1}{2}$$，因 $$ed_p \equiv 1 \pmod {p-1}$$，有 $$ed_p=1+k(p-1)$$，

对于 $$k \in \mathbb{N}$$，有 $$ed_p=(k-1)(p-1)+p$$，即 $$ed_pq=(k-1)(N-q)+N$$。

设 $$x,y$$ 为参数，则多项式 $$f(x,y)=x(N-y)+N$$ 在模 $$e$$ 下存在根 $$(x_0,y_0)=(k-1,q)$$，用coppersmith attack可解。

​

Coppersmith定理指出在一个 $$e$$ 阶的 $$\bmod n$$ 多项式 $$f(x)$$ 中，如果有一个根小于 $$n^{\frac{1}{e}}$$，就可以运用一个 $$O(\log n)$$ 的算法求出这些根。

Coppersmith攻击（已知p的高位攻击）

知道 $$p$$ 的高位为 $$p$$ 的位数的约$$\frac12$$时即可。

#Sage
from sage.all import *
n = 
p4 = 
#p去0的剩余位
e =  
pbits = 1024
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
#经过以上一些函数处理后，n和p已经被转化为10进制
if roots:        
    p = p4+int(roots[0]) 
    print("n: "+str(n))
    print("p: "+str(p))
    print("q: "+str(n//p))

​

Coppersmith攻击（已知m的高位攻击）

这里我们假设我们首先加密了消息 $$m$$，如下

$$C\equiv m^e \bmod N$$

并且我们假设我们知道消息 $$m$$ 的很大的一部分 $$m_0$$，即 $$m=m_0+x$$，但是我们不知道 $$x$$。那么我们就有可能通过该方法进行恢复消息。这里我们不知道的 $$x$$ 其实就是多项式的根，需要满足 Coppersmith 的约束。

可以参考 https://github.com/mimoo/RSA-and-LLL-attacks 。

$$e$$ 足够小，且部分明文泄露时，可以采用Coppersmith单变量模等式的攻击，如下：

$$c=m^{e}\bmod n=(mbar+x_{0})^{e}\bmod n$$，其中 $$mbar = (m >> k\text{bits}) << k\text{bits}$$

当 $$\vert x_{0}\vert\leq N^{\frac{1}{e}}$$ 时，可以在 $$\log N$$ 和 $$e$$ 的多项式时间内求出 $$x_0$$。

#Sage
n = 
e = 
c = 
mbar = 
kbits = 
beta = 1
nbits = n.nbits()
print("upper {} bits of {} bits is given".format(nbits - kbits, nbits))
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n
print("m:", mbar + x0)

​

Coppersmith攻击（已知d的低位攻击）

如果知道 $$d$$ 的低位，低位约为 $$n$$ 的位数的 $$\frac14$$ （$$\frac{n.n\text{bits}()}{4}$$）就可以恢复 $$d$$。

#Sage
def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()
    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.4)  # find root < 2^(nbits//2-kbits) with factor >= n^0.4
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)
def find_p(d0, kbits, e, n):
    X = var('X')
    for k in range(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p and p != 1:
                return p
if __name__ == '__main__':
    n = 
    e = 
    c = 
    d0 = 
    beta = 0.5
    nbits = n.nbits()
    kbits = d0.nbits()
    print("lower %d bits (of %d bits) is given" % (kbits, nbits))
    p = int(find_p(d0, kbits, e, n))
    print("found p: %d" % p)
    q = n//int(p)
    print("d:", inverse_mod(e, (p-1)*(q-1)))
  • 变种1：$$n=p\cdot q\cdot r$$，已知 $$n,p,d=\text{inv}(e,\varphi(n)),e,c$$

$$k(p-1)\rightarrow k’,qr\rightarrow n’,q+r\rightarrow s$$

$$ed_{0}\equiv 1+k’(n’-s+1) \pmod {2^{d_{0}.n\text{bits}()}}\quad (1)$$

$$q^{2}-sq+n’\equiv 0 \pmod {2^{d_{0}.n\text{bits}()}}\quad (2)$$

联立可得，$$(ed_{0}-1-k’n’-k’)q+k’q^{2}+k’n’\equiv 0 \pmod {2^{d_{0}.n\text{bits}()}}$$

即求解同余方程可得 $$q$$ 的低 $$size(d0)$$ 位，本来是个partial d的coppersmith问题，但因为step1求解同余方程后得到的 $$q$$ 已是完整的 $$q$$，所以无需后续的coppersmith。

参考：Dragon CTF 2019 - RSA Chained

#Sage
def find_p(d0, kbits, e, n, p):
    X = var('X')
    for k in range(1, e + 1):
        k_dot = k * (p - 1)
        results = solve_mod([e * d0 * X - k_dot * X * (n - X + 1) + k_dot * n == X], 2^kbits)
        for x in results:
            q = ZZ(x[0])
            if n % q == 0:
                return q
    return None

n = ... # q * r
p = 
c = 
d0 = 
e = 
kbits = d0.nbits()
q = find_p(d0, kbits, e, n, p)
phi = (p - 1) * (q - 1) * (n // q - 1)
d = inverse_mod(e, phi)
print(bytes.fromhex(hex(pow(c, d, p * n))[2:]))

​

Coppersmith攻击（已知N一个因子的高位，部分p）

当我们知道一个公钥中模数 $$N$$ 的一个因子的较高位时，我们就有一定几率来分解 $$N$$。

参考 https://github.com/mimoo/RSA-and-LLL-attacks 。

关注下面的代码：

beta = 0.5
dd = f.degree()
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon)) + 1000000000000000000000000000000000
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)

其中，

  • 必须满足 $$q\ge N^{beta}$$，所以这里给出了 $$beta=0.5$$，显然两个因数中必然有一个是大于的。
  • XX 是 $$f(x)=q′+x$$ 在模 $$q$$ 意义下的根的上界，自然我们可以选择调整它，这里其实也表明了我们已知的 $$q′$$ 与因数 $$q$$ 之间可能的差距。
#Sage
n = 
e = 
c = 
pbar = 
kbits = 
print("upper %d bits (of %d bits) is given" % (pbar.nbits()-kbits, pbar.nbits()))
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
p = x0 + pbar
print("p:", p)
q = n // int(p)
d = inverse_mod(e, (p-1)*(q-1))
print("m:", pow(c, d, n))

注：

sage的small_root传参X不能过大，需自行判断阈值并调整（如果X过大，即使存在X内的解，也无法求出）；

比如 $$p$$ 的低位泄露时因为不确定缺失高位的具体比特数，所以要在 $$2^{\frac{n.n\text{bits}()}{2}−k\text{bits}}$$ 附近作X的阈值估计；

无法确定拿到的 $$p$$ 是否大于 $$q$$，所以对 $$\beta=0.5$$ 进行调整至 $$0.4$$。

​

目前在大部分消息加密之前都会进行 padding，但是如果 padding 的长度过短（$$m \in (0,\lfloor\frac{n.n\text{bits}()}{e^2}\rfloor]$$），也有可能被很容易地攻击。

这里所谓 padding 过短，其实就是对应的多项式的根会过小。

当 Alice 使用同一公钥对两个具有某种线性关系的消息 $$M_1$$ 与 $$M_2$$ 进行加密，并将加密后的消息 $$C_1$$，$$C_2$$ 发送给了 Bob 时，我们就可能可以获得对应的消息 $$M_1$$ 与 $$M_2$$ 。这里我们假设模数为 $$N$$，两者之间的线性关系如下：

$$M_1 \equiv f(M_2) \bmod N$$

其中 $$f$$ 为一个线性函数，比如说 $$f=ax+b$$。

在具有较小错误概率下的情况下，其复杂度为 $$O(e\log^2N)$$。

这一攻击由 Franklin与Reiter 提出。

#脚本1
#Sage
import binascii
def attack(c1, c2, n, e):
    PR.<x>=PolynomialRing(Zmod(n))
    # replace a,b,c,d
    g1 = (a*x+b)^e - c1
    g2 = (c*x+d)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]
c1 =
c2 =
n =
e =
m1 = attack(c1, c2, n, e)
print(binascii.unhexlify("%x" % int(m1)))


#脚本2
#Sage
def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+y)^e - c2
    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)
    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()
    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
    return diff
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]
if __name__ == '__main__':
    n = 
    e = 
    c1 =
    c2 = 
    diff = short_pad_attack(c1, c2, e, n)
    print("difference of two messages is %d" % diff)
    m1 = related_message_attack(c1, c2, diff, e, n)
    print("m1:", m1)
    print("m2:", m1 + diff)
​

RSA Hastad Attack with non-linear padding and different public keys（带非线性padding和不同公钥的广播攻击）

适用情况：$$m$$ 经 $$k$$ 次非线性padding处理后，分别用 $$k$$ 组 $$(N_i,e_i)$$ 加密后得 $$k$$ 组 $$c_i$$。

参考：2020年羊城杯 - Invitation

#Sage
#e=3, padding: m²+(3^431)k
def linearPaddingHastads(cArray,nArray,aArray,bArray,eArray,eps):
    if(len(cArray) == len(nArray) == len(aArray) == len(bArray) == len(eArray)):
        for i in range(4):
            cArray[i] = Integer(cArray[i])
            nArray[i] = Integer(nArray[i])
            aArray[i] = Integer(aArray[i])
            bArray[i] = Integer(bArray[i])
            eArray[i] = Integer(eArray[i])
        TArray = [-1]*4
        for i in range(4):
            arrayToCRT = [0]*4
            arrayToCRT[i] = 1
            TArray[i] = crt(arrayToCRT,nArray)
        P.<x> = PolynomialRing(Zmod(prod(nArray)))
        gArray = [-1]*4
        for i in range(4):
            gArray[i] = TArray[i]*(pow(aArray[i]*x**2 + bArray[i],eArray[i]) - cArray[i])
        g = sum(gArray)
        g = g.monic()
        roots = g.small_roots(epsilon=eps)
        if(len(roots)== 0):
            print("No Solutions found!")
            return -1
        return roots
    else:
        print("Input error!")

def nonLinearPadding():
    eArr = [3 for i in range(4)]
    nArr = [146694460234280339612721415368435987068740712812770728817136582256341063038147863645902264969297892447333024201649306207442798919845916187823646745721109151386096190207317810424580842120750075213595282979568495342617919336417068886973047979116994072272482630372638964064972815256237040541007947708358680368391,65031485534704406281490718325237831433086480239135617407356760819741796565231283220528137697949585150709734732370203390254643835828984376427852793969716489016520923272675090536677771074867975287284694860155903327351119710765174437247599498342292671117884858621418276613385329637307269711179183430246951756029,126172075578367446151297289668746433680600889845504078949758568698284471307000358407453139846282095477016675769468273204536898117467559575203458221600341760844973676129445394999861380625435418853474246813202182316736885441120197888145039130477114127079444939102267586634051045795627433724810346460217871661901,75691424835079457343374072990750986689075078863640186724151061449621926239051140991748483370587430224317778303489124525034113533087612981452189061743589227565099659070008017454957304620495920813121234552401715857719372861565651204968408267740732475458128601061676264465241188491988485848198323410127587280471]
    cArr = [129274519334082165644106292383763271862424981496822335330342328217347928093592453953990448827969549377883054831490973006383371688359344675312001881631556371220779971357039899721241880304156884612458373310254854821837978876725801047977081900824202659636258168216028784656056334358157381820784576207338479493823,8140023566779187828652447593867705813386781164538611122714708931585587727699213769519135028841126072130625547328311301696554048174772606261707345115571968105138543476580875347239912760797035694220505996377127309341770427102697008350472060971360460756799310951343070384766137332401117333917901167639276168214,25434511525127530194830986592289179576070740435049947678930286998924519588985583799757299734846614343604661534391991096353170465467791358514448923161460366596251448937540153262731348684727026598527904328268639060306102090278287818149679940661579357649191023269947102746200467430583428889484549034314463114080,9435583236354598287661880148272717764447540972316605192855157484524753847806158586224733743434644389385148450722945845355791145016665856388503878165725148745517696840251674049929524448078129458846254866804153080766917319923905682824180976106679633180818527967145571143203594244851742143986040226240019541346]
    aArr = [1 for i in range(4)]
    bArr = [i * 3 ** 431 for i in [3,8,10,11]]
    msg = linearPaddingHastads(cArr,nArr,aArr,bArr,eArr,eps=1/20)
    for i in msg:
        print(bytes.fromhex(hex(i)[2:]))

if __name__ == '__main__':
    nonLinearPadding()

​

Least Significant Bit Oracle Attack （LSB Oracle Attack / Parity Oracle）

适用情况：可以选择密文并泄露明文的最低位（奇偶性）。

假设存在一个oracle，能对给定密文进行解密并给出对应明文的奇偶信息，则我们只需要 $$\log(N)$$ 次就能解密任意密文。

在一次RSA加密中，明文为 $$m$$，模数为 $$n$$，加密指数为 $$e$$，密文为 $$c$$。我们可以构造出

$$c’=((2^e)\cdot c)\%n=((2^e)\cdot(m^e))\%n=((2\cdot m)^e)\%n$$ ，

因为 $$m$$ 的两倍可能大于 $$n$$，所以经过解密得到的明文是 $$m’=(2\cdot m)\%n$$ 。

我们还能够知道 $$m’$$ 的最低位lsb 是1还是0。 因为 $$n$$ 是奇数，而 $$2\cdot m$$ 是偶数，所以如果lsb 是0，说明$$(2\cdot m)\%n$$ 是偶数，没有超过 $$n$$，即 $$m\lt \cfrac{n}{2}$$ ，反之则 $$m\gt \cfrac{n}{2}$$ 。举个例子就能明白 $$2\%3=2$$ 是偶数，而$$4\%3=1$$ 是奇数。以此类推，构造密文 $$c’’=((4^e)\cdot c)\%n$$ 使其解密后为 $$m’’=(4\cdot m)\%n$$ ，判断 的奇偶性可以知道 $$m’’$$ 和 $$\cfrac{n}{4}$$ 的大小关系。所以我们就有了一个二分算法，可以在对数时间内将 $$m$$ 的范围逼近到一个足够狭窄的空间。

更多信息可参考：RSA Least-Significant-Bit Oracle Attack 和 RSA least significant bit oracle attack 。

import decimal
def oracle():
    return lsb == 'odd'

def partial(c, e, n):
    k = n.bit_length()
    decimal.getcontext().prec = k  # for 'precise enough' floats
    lo = decimal.Decimal(0)
    hi = decimal.Decimal(n)
    for i in range(k):
        if not oracle(c):
            hi = (lo + hi) / 2
        else:
            lo = (lo + hi) / 2
        c = (c * pow(2, e, n)) % n
        # print i, int(hi - lo)
    return int(hi)

​

Common Private Exponent（共私钥指数攻击，d相同）

加密用同样的私钥并且私钥比较短，从而导致了加密系统被破解。

假定：

$$\begin{cases} e_1d=1+k_1\varphi(N_1) \newline e_2d=1+k_2\varphi(N_2) \newline {\vdots} \newline e_rd=1+k_r\varphi(N_r) \end{cases}$$

其中，$$N_1 \lt N_2 \lt \cdots \lt N_r \lt 2N_1$$。

构造格：

$$B_r=\begin{bmatrix}{M}&{e_1}&{e_2}&{\cdots}&{e_{r}}\newline
{0}&{-N_1}&{0}&{\cdots}&{0}\newline{0}&{0}&{-N_2}&{\cdots}&{0}\newline{\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}\newline{0}&{0}&{0}&{\cdots}&{-N_r}\newline\end{bmatrix}$$

其中 $$M=\lfloor N_r^{\frac{1}{2}} \rfloor$$。

再利用LLL算法进行规约得到 $$\vert b_1\vert=Md$$，则 $$d=\cfrac{\vert b_1 \vert}{M}$$，从而解密密文得到明文。

  • 使用条件：

$$d \lt N_r^{\delta_r}，\delta_r \lt \cfrac{1}{2}-\cfrac{1}{2(r+1)}-\log_{N_r}{(6)}$$ * 参考：

Lattice Based Attack on Common Private Exponent RSA

SCTF 2020 - RSA

###Sage###
from gmpy2 import *
e0=
n0=
c0=
e1=
n1=
c1=
e2=
n2=
c2=

M=iroot(int(n2),int(2))[0]
a=[0]*4
a[0]=[M,e0,e1,e2]
a[1]=[0,-n0,0,0]
a[2]=[0,0,-n1,0]
a[3]=[0,0,0,-n2]

Mat = matrix(ZZ,a)
Mat_LLL=Mat.LLL()
d = abs(Mat_LLL[0][0])/M
print(bytes.fromhex(hex(pow(c1,int(d),int(n1)))[2:]))

​

多组低解密指数攻击

适用情况：2-4组 $$e$$，且 $$d$$ 较小

  • 给定2组

$$g=\gcd(p-1,q-1),\lambda(n)=\frac{\varphi(n)}{g},s=1-p-q$$

且有 $$ed-k\lambda(n)=1$$，得到 $$edg-kn=g+ks\quad (1)$$

设 $$e_1$$ 对应 $$k_1$$，$$e_2$$ 对应 $$k_2$$，则有 $$k_{2}d_{1}e{1}-k_{1}d_{2}e_{2}=k_{2}-k_{1}\quad (2)$$

由(1)(2)有：

$\left\{ \begin{matrix} e_{1}d_{1}g-k_{1}n=g+k_{1}s \newline k_{2}d_{1}e{1}-k_{1}d_{2}e_{2}=k_{2}-k_{1} \newline e_{1}e_{2}d_{1}d_{2}g_{2}-e_{1}d_{1}gk_{2}n-e_{2}d_{2}gk_{1}n+k_{1}k_{2}n^{2}=(g+k_{1}s)(g+k_{2}s) \end{matrix} \right.$

上述等式组也可表示为

$$bL_2 =[k_{1}k_{2},k_{2}d_{1}g,k_{1}d_{2}g,d_{1}d_{2}g^{2}]\cdot\left[ \begin{matrix} n & -M_{1}n & 0 & n^{2} \newline 0 & M_{1}e_{1} & M_{2}e_{1} & -e_{1}n \newline 0 & 0 & -M_{2}e_{2} & -e_{2}n \newline 0 & 0 & 0 & e_{1}e_{2} \end{matrix} \right] =[k_{1}k_{2}n,M_{1}k_{2}(g+k_{1}s),M_{2}g(k_{2}-k_{1})，(g+k_{1}s)(g+k_{2}s)]$$

（其中 $$M_{1}=n^{1/2},M_{2}=n^{1+\alpha_{2}},d\approx n^{\alpha_{2}}$$）

对部分参数进行上界估计，k上界近似于 $$d\approx N^{\alpha_{2}}$$, $$|s|$$ 上界 $$\approx N^{1/2}$$，$$g$$ 一般相对极小

因此上面的矩阵表示 $$BA=C$$ 中，$$C$$ 的每个元的size都近似 $$n^{1+2\alpha_{2}}$$，所以 $$|C|\approx 2\cdot n^{1+2\alpha_{2}}$$

$$B$$ 作为格基的格中，最短向量由Minkowski Bounds知 $$\approx \sqrt{4}\det(B)^{1/4}\approx 2\cdot n^{(13/2+\alpha_{2})/4}$$

因此只要满足 $$n^{1+2\alpha_{2}}<n^{(13/2+\alpha_{2})/4}$$ 即可将问题转化为SVP（$$\alpha_{2}<\frac{5}{14}$$）

from sage.all import *
import gmpy2
N = 
e1 = 
e2 = 
c = 
 for i in range(1000):
    alpha2 = i/1000
     M1 = int(gmpy2.mpz(N)**0.5)
    M2 = int( gmpy2.mpz(N)**(1+alpha2) )
    D = diagonal_matrix(ZZ, [N, M1, M2, 1])
    B = Matrix(ZZ, [ [1, -N,   0,  N**2],
                 [0, e1, -e1, -e1*N],
                 [0,  0,  e2, -e2*N],
                 [0,  0,   0, e1*e2] ]) * D
    L = B.LLL()
    v = Matrix(ZZ, L[0])
    x = v * B**(-1)
    phi = (x[0,1]/x[0,0]*e1).floor()
    try:
        d = inverse_mod( 65537, phi)
        m = hex(power_mod(c, d, N))[2:]
        if m.startswith('44415343'):
            print(i)
            print(bytes.fromhex(m))
            break
    except:
        pass

参考：De1CTF 2020 - easyRSA

  • 给定3组

类似2组情况，其中

$$b=[k_1k_2k_3,d_1gk_2k_3,k_1d_2gk_3,d_1d_2g^2k_3,k_1k_2d_3g,k_1d_3g,k_2d_3g,d_1d_2d_3g^3]$$

$$L_3=\left[\begin{matrix} 1-N & 0 & N^2 & 0 & 0 & 0 & -N^3 \newline e_1 & -e_1 & -e_1N & -e & 0 & e_1N & e_1N^2 \newline 0 & e_2 & -e_2N & 0 & e_2N & 0 & e_2N^2 \newline 0 & 0 & e_1e_2 & 0 & -e_1e_2 & -e_1e_2 & -e_1e_2N \newline 0 & 0 & 0 & e_3 & -e_3N & -e_3N & e_3N^3 \newline 0 & 0 & 0 & 0 & e_1e_3 & 0 & -e_1e_3N \newline 0 & 0 & 0 & 0 & 0 & e_2e_3 & -e_2e_3N \newline 0 & 0 & 0 & 0 & 0 & 0 & e_1e_2e_3 \end{matrix}\right] \times D$$

其中 $$D={\rm diag}(N^{3/2},N,N^{(3/2)+\alpha_3},N^{1/2},N^{(3/2)+\alpha_3},N^{1+\alpha_3},N^{1+\alpha_3}，1)$$

参考：3kCTF - RSA Textbook

from sage.all import *
import gmpy2

N = 
e1 = 
e2 = 
e3 = 
c = 

for i in range(1000):
    alpha2 = i/1000
    M1 = int(gmpy2.mpz(N)**(3./2))
    M2 = int( gmpy2.mpz(N) )
    M3 = int(gmpy2.mpz(N)**(3./2 + alpha2))
    M4 = int( gmpy2.mpz(N)**(0.5) )
    M5 = int( gmpy2.mpz(N)**(3./2 + alpha2) )
    M6 = int( gmpy2.mpz(N)**(1.+alpha2) )
    M7 = int( gmpy2.mpz(N)**(1.+alpha2) )
    D = diagonal_matrix(ZZ, [M1, M2, M3, M4, M5, M6, M7, 1])
    B = Matrix(ZZ, [ [1, -N,   0,  N**2,   0,      0,      0,    -N**3],
                 [0, e1, -e1, -e1*N, -e1,      0,   e1*N,  e1*N**2],
                 [0,  0,  e2, -e2*N,   0,   e2*N,      0,  e2*N**2],
                 [0,  0,   0, e1*e2,   0, -e1*e2, -e1*e2, -e1*e2*N],
                 [0,  0,   0,     0,  e3,  -e3*N,  -e3*N,  e3*N**2],
                 [0,  0,   0,     0,   0,  e1*e3,      0, -e1*e3*N],
                 [0,  0,   0,     0,   0,      0,  e2*e3, -e2*e3*N],
                 [0,  0,   0,     0,   0,      0,      0, e1*e2*e3] ]) * D

    L = B.LLL()

    v = Matrix(ZZ, L[0])
    x = v * B**(-1)
    phi_ = (e1*x[0,1]/x[0,0]).floor()
    try:
        d = inverse_mod( 65537, phi_)
        m = hex(power_mod(c, d, N))[2:]
        if m.startswith('44415343'):
            print(i)
            print(bytes.fromhex(m))
            break
    except:
        pass
  • 给定更多组

西湖论剑 2021 - WienerStudyTwice * 参考Paper

Common Modulus Attacks on Small Private Exponent RSA and Some Fast Variants (in Practice)

Extending Wiener’s Attack in the Presence of Many Decrypting Exponents

​

多项式RSA

在整数RSA原理基础上将多项式代入分析：

在有限域上选取两个不可约多项式 $$g(p),g(q)$$，$$g(n)=g(p) \cdot g(q)$$，计算出 $$g(n)$$ 的欧拉函数 $$\varphi(g(n))=\varphi$$，

选取一个整数 $$e$$ 作为公钥，$$e$$ 与 $$\varphi$$ 是互素的，那么对于明文 $$g(m)$$，加密过程为 $$g(m)^e \equiv g(c) \pmod {g(n)}$$，

计算私钥 $$d$$ 满足 $$ed \equiv 1 \pmod \varphi$$，则 $$g(c)^d \equiv (g(m)^e)^d \equiv g(m)^{ed} \equiv g(m)^{\varphi+1} \pmod {g(n)}$$，

同样考虑 $$g(n)$$ 与 $$g(m)$$ 互素，欧拉定理对于多项式亦成立，

得到 $$g(m)^{\varphi+1} \equiv g(m) \pmod {g(n)}$$，所以 $$g(c)^d \equiv g(m) \pmod {g(n)}$$。

显然RSA对于整数的体制可以适用于有限域上的多项式。

★注意：

对于素数 $$x$$，$$\varphi(x)=x-1$$，但是对于不可约多项式 $$g(x)$$，$$\varphi(g(x))=p^n-1$$。（此 $$p$$ 为 $$GF(p)$$ 的模，此 $$n$$ 为多项式最高项次数）

原因：

由欧拉函数定义本身，欧拉函数是小于 $$n$$ 的所有与 $$n$$ 互质的数的个数。

多项式的欧拉函数则类似，表示不高于 $$g(x)$$ 幂级的环内所有多项式中，与 $$g(x)$$ 无公因式（非1）的其他多项式的个数，所以每一个不高于 $$g(x)$$ 幂级的环内多项式（除了它自己）均满足此条件。

#脚本1
#Sage
#已知p,n,m^e
p= 
P = PolynomialRing(Zmod(p), name = 'x')
x = P.gen()
e = 
n = 
c =

#分解N
q1, q2 = n.factor()
q1, q2 = q1[0], q2[0]

#求φ，注意求法，
phi = (p**q1.degree() - 1) * (p**q2.degree() - 1)
assert gcd(e, phi) == 1
d = inverse_mod(e, phi)
m = pow(c,d,n)

#取多项式系数
flag = bytes(m.coefficients())
print("Flag: ", flag.decode())

#脚本2
#Sage
#已知p=2,n,e,c
p = 
P = PolynomialRing(GF(p), name = 'x')
x = P.gen()
e = 
n = 
R.<a> = GF(2^2049)
c = []

q1, q2 = n.factor()
q1, q2 = q1[0], q2[0]

phi = (p**q1.degree() - 1) * (p**q2.degree() - 1)
assert gcd(e, phi) == 1
d = inverse_mod(e, phi)

ans = ''
for cc in c:
    cc = P(R.fetch_int(cc))
    m = pow(cc,d,n)
    m = R(P(m)).integer_representation()
    print(m)
    ans += chr(m)
print(ans)

参考：

0ctf - babyrsa

watevrCTF 2019 - Swedish RSA

InCTF 2020 - PolyRSA

Polynomial based RSA

​

Weak prime factors （p具线性特征）

适用情况：$$p$$ 满足 $$ap=u_0+M_1u_1+\cdots+M_ku_k$$

先根据 $$n$$ 确定 $$M$$ 的大小，再根据 $$M$$ 选取符合要求的 $$k$$ 和 $$c$$，然后构造一个格如下：

$$M(\mathcal{L})=\begin{bmatrix}{1}&{0}&{0}&{\cdots}&{0}&{CM^{2k}} \newline
{0}&{1}&{0}&{\cdots}&{0}&{CM^{2k-1}} \newline {\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}&{\vdots} \newline {0}&{0}&{0}&{\cdots}&{1}&{CM} \newline {0}&{0}&{0}&{\cdots}&{0}&{-CN} \newline \end{bmatrix}$$

用LLL算法进行格基规约，将规约后的某个向量作为多项式系数，再对多项式进行分解，即可完成对 $$n$$ 的分解。

  • 参考

Factoring RSA moduli with weak prime factors

N1CTF2020 - easyRSA

from tqdm import tqdm
import gmpy2

class success(Exception):
    pass

def attack_weak_prime(basenum, exp, n):
    m = basenum^exp
    k = len(n.str(base=basenum))//(2*exp) + 1
    c = gmpy2.iroot(2*k^3, int(2))
    # assert c[1] == True
    tmp = int(c[0])

    try:
        for c in tqdm(range(1, tmp)):
            amount = 2*k+1

            M = Matrix(RationalField(), amount, amount)
            for i in range(amount):
                M[i, i] = 1
                M[i, amount-1] = c*m^(2*k-i)
            M[amount-1, amount-1] = -c*n

            new_basis = M.LLL(delta=0.75)
            for j in range(amount):
                last_row = list(new_basis[j])
                last_row[-1] = last_row[-1]//(-c)

                poly = sum(e * x^(k*2-i) for i,e in enumerate(last_row))
                fac = poly.factor_list()
                if len(fac) == 2:
                    p_poly, q_poly = fac
                    p_coefficient = p_poly[0].list()
                    q_coefficient = q_poly[0].list()
                    ap = sum(m^i * j for i,j in enumerate(p_coefficient))
                    bq = sum(m^i * j for i,j in enumerate(q_coefficient))
                    p = gcd(ap, n)
                    q = gcd(bq, n)

                    if (p*q == n) and (p != 1) and (q != 1):
                        raise success

    except:
        print ('n =', n)
        print ('p =', p)
        print ('q =', q)
        print ('p*q == n ?', bool(p*q == n))


if __name__ == '__main__':
    print ('[+] Weak Prime Factorization Start!')
    print ('-------------------------------------------------------------------------------------------------------------------------------')
    basenum, exp = (3, 66)
    n = 32846178930381020200488205307866106934814063650420574397058108582359767867168248452804404660617617281772163916944703994111784849810233870504925762086155249810089376194662501332106637997915467797720063431587510189901

​

其他特别情形

  • 多素数因子（Multi-prime RSA）

$$n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m} \ \Rightarrow \begin{eqnarray}\varphi(n) &=&\varphi(p_1^{k_1})\varphi(p_2^{k_2}) \cdots \varphi(p_m^{k_m}) \ &=&(p_1^{k_1-1}\cdot(p_1-1))(p_2^{k_2-1}\cdot(p_2-1)) \cdots (p_m^{k_m-1}\cdot(p_m-1)) \end{eqnarray}$$

​ * ##### next_prime()

根据素数定理，素数的平均间隔为：$$\cfrac{x}{\pi(x)} \approx \ln(x)$$，因此常见的下一个素数比当前素数大一点，一般不会超过1500。

  • 变种1：$$n=p \cdot q \cdot \text{nextprime}(p) \cdot \text{nextprime}(q)$$

费马因式分解。​ * 给 e,p,c

$$c \equiv m^e \pmod n \ \Leftrightarrow c_1 \equiv c \pmod p \equiv m^e \pmod p$$

令 $$ed_1 \equiv 1 \pmod {(p-1)}$$，有 $$m \equiv c^d \pmod n \equiv c_1^{d_1} \pmod p$$。

​ * ##### 给 e,d,modinv(q,p),c

已知：$$p,q$$ 同比特位数。

令 $$cf=q^{-1} \bmod p$$，有 $$q\cdot cf=1 \pmod p$$。

  • $$ed=1+k(p-1)(q-1)$$，

比较比特位数，$$k$$ 与 $$e$$ 同长，可爆破 $$k$$，得 $$\varphi(n)=(p-1)(q-1)=\cfrac{ed-1}{k}$$； + 上式 $$\varphi(n) =(p-1)(q-1) \pmod p=-(q-1) \pmod p$$，

结合 $$q\cdot cf=1 \pmod p$$，即 $$q\cdot cf-1=0 \pmod p$$，

联立：

$$\begin{eqnarray} \varphi(n)&=&(p-1)(q-1) \ &=&pq-p-q+1 \ &=&n-p-q+1 \end{eqnarray}$$

$$\begin{eqnarray} cf\cdot \varphi(n)&=&cf\cdot(n-p-q+1) \ &=&cf\cdot n-cf\cdot p-cf\cdot q+cf \end{eqnarray}$$

$$\begin{eqnarray} cf\cdot \varphi(n) \bmod p&=&(cf\cdot n-cf\cdot p-cf\cdot q+cf) \bmod p \ &=&0-0-(cf\cdot q)+cf \bmod p \ &=&-1+cf \bmod p \end{eqnarray}$$

有 $$1+cf\cdot \varphi(n)-cf=0\pmod p$$，

即$$x=1+cf\cdot \varphi(n)-cf$$ 能被 $$p$$ 整除； + 由费马小定理，存在 $$r$$ 满足 $$r^{p-1}=1 \pmod p$$，

$$\begin{eqnarray}r^{\varphi(n)}&=&(r^{(p-1)})^{(q-1)} \ &=&1^{(q-1)} \pmod p \ &=&1 \pmod p \end{eqnarray}$$，

因对于任意 $$r,k_1,k_2$$，当 $$k_2$$ 为 $$k_1$$ 因子时，$$r \bmod k_2=(r \bmod k_1) \bmod k_2$$，

故 $$r^{\varphi(n)} \bmod p=(r^{\varphi(n)} \bmod x) \bmod p=1 \bmod p=kp$$，

已知 $$\varphi(n)$$，由 $$(r^{\varphi(n)} \bmod x) \bmod p=kp$$ 可得到多组 $$p$$ 的乘积，计算 $$\gcd$$ 可得到 $$p$$； + 由 $$q\cdot cf=1 \pmod p$$ 求模逆可得 $$q$$，再用 $$c$$ 计算出 $$m$$。

参考：TSG CTF 2020 - Modulus Amittendus​ * ##### gcd(e,φ(n)) ≠ 1

$$\gcd(e,\varphi(n))\neq 1$$ 时，$$e$$ 与 $$\varphi(n)$$ 不互素，

$$m^e \equiv (m^{\gcd(e,\varphi(n))})^{\frac{e}{\gcd(e,\varphi(n))}} \equiv c \pmod n$$，计算 $$\frac{e}{\gcd(e,\varphi(n))}$$ 的模逆 $$d’$$，

则 $$c^{d’}\equiv m^{\gcd(e,\varphi(n))}\pmod n$$。

当 $$\gcd(e,\varphi(n))$$ 较小时，可以直接对 $$c$$ 开根，有两种情况：

  • $$m^e = c<n$$，这种情况直接对 $$c$$ 开 $$e$$ 次方即可；
  • $$m^e = c>n$$，这种情况需要在有限域下对 $$c$$ 开方，一般先计算 $$c_p=c \bmod p$$，$$c_q=c \bmod q$$，分别求出 $$c_p,c_q$$ 在 $$c$$ 下的 $$e$$ 次根（可能有多个），然后使用CRT遍历所有组合，分别check得出明文。当 $$\gcd(e,\varphi(n))$$ 较大时，求 $$p,q$$ 的 $$e$$ 次根步骤需要替换为一些有限域开根的高效算法（如AMM算法等）进行计算。

参考：

De1CTF2019 - Baby RSA

0ctf 2016 - RSA?

​ * ##### e|(p-1), e|(q-1)

上面的 $$\gcd(e,\varphi(n))\neq 1$$ 情况不针对 $$\gcd(e,\varphi(n))= e$$，这里对 $$e\mid (p-1),e\mid (q-1)$$ 的特殊情况进行讨论。

解题思路即求解 $$m \bmod p$$ 和 $$m \bmod q$$ ，再通过CRT还原 $$m \bmod n$$。主要难点则是在 $$\text{GF}(p)$$ 上求 $$e$$ 次根。

在有限域上求r-th root有两个常见算法（Adleman-Manders-Miller algorithm和Cipolla-Lehmer algorithm），Namhun Koo提出一种更具一般性的开根算法，且在 $$s$$ 足够小的时候更高效（$$r^{s}\mid (p-1),r^{s}\nmid (p-1)$$）。

★参考：NCTF 2019 - easyRSA （Adleman-Manders-Miller rth Root Extraction Method）

本题则为 $$e$$ 和 $$p-1$$ （或 $$q-1$$）的最大公约数就是 $$e$$ 本身，也就是说 $$e\mid (p-1)$$，只有对 $$c$$ 开 $$e$$ 次方根才行。

可以将同余方程 $$m^e \equiv c \pmod n$$ 化成

$$\begin{cases} m^e \equiv c \pmod p \ m^e \equiv c \pmod q \end{cases}$$

然后分别在 $$\text{GF}(p)$$ 和 $$\text{GF}(q)$$ 上对 $$c$$ 开 $$e$$ 次方根，再用CRT组合一下即可得到在 $$\bmod n$$ 下的解。

问题是，如何在有限域内开根？

这里 $$e$$ 与 $$p-1$$ 和 $$q-1$$ 都不互素，不能简单地求个逆元就完事。

这种情况下，开平方根可以用Tonelli–Shanks algorithm，Wiki说这个算法可以扩展到开n次方根。

在这篇paper里给出了具体的算法：Adleman-Manders-Miller rth Root Extraction Method。

这个算法只能开出一个根，实际上开 $$e$$ 次方，最多会有 $$e$$ 个根（这题的情况下有0x1337个根）。

如何找到其他根？

StackOverflow – Cube root modulo P 给出了方法。

如何找到所有的primitive 0x1337th root of 1?

StackExchange – Finding the n-th root of unity in a finite field 给出了方法。

Exploit（以 e=0x1337​ 为例）

  • 先用Adleman-Manders-Miller rth Root Extraction Method在 $$\text{GF}(p)$$ 和 $$\text{GF}(q)$$ 上对 $$c$$ 开 $$e$$ 次方根，分别得到一个解。大概不到10秒。
  • 然后去找到所有的0x1336个primitive nth root of 1，乘以上面那个解，得到所有的0x1337个解。大概1分钟。
  • 再用CRT对 $$\text{GF}(p)$$ 和 $$\text{GF}(q)$$ 上的两组0x1337个解组合成 $$\bmod n$$ 下的解，可以得到0x1337**2=24196561个 $$\bmod n$$ 的解。最后能通过check()的即为flag。大概十几分钟。
#脚本1
#Sage
import random
import time

# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(a, d)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp


c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 0x1337
cp = c % p
cq = c % q
mp = AMM(cp, e, p)
mq = AMM(cq, e, q)
p_proot = findAllPRoot(p, e)
q_proot = findAllPRoot(q, e)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)
print(mps, mqs)

def check(m):
    h = m.hex()
    if len(h) & 1:
        return False
    if bytes.fromhex(h).startswith(b'NCTF'):
        print(bytes.fromhex(h))
        return True
    else:
        return False


# About 16 mins to run 0x1337^2 == 24196561 times CRT
start = time.time()
print('Start CRT...')
for mpp in mps:
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if check(solution):
            print(solution)
    print(time.time() - start)

end = time.time()
print("Finished in {} seconds.".format(end - start))

#脚本2
#Sage
c = 346925245648012783854132941104554194717281878370806475831055718275298366664505658836564073456294047402009856656647760
p = 21122913513992623721920275602985463699928507831138027
q = 16471885912035642894544190467774867069446937372970845578732298073
e = 239

P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^e-c
mps=f.monic().roots()

P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
g=a^e-c
mqs=g.monic().roots()

for mpp in mps:
    x=mpp[0]
    for mqq in mqs:
        y=mqq[0]
        solution = hex(CRT_list([int(x), int(y)], [p, q]))[2:]
        if solution.startswith('666c'):
            print(solution)

​ * ##### SMUPE 问题（不同N,e加密线性关系明文）

a system of univariate polynomial equations problem = 一元多项式方程组求解问题

  • 定义

$$k$$ 是一个整数，$$N$$ 为满足RSA算法的模数，$$\delta$$ 是多项式的阶。有

$$N_i<N_{i+1},\delta_i \in N\quad(i=1,2,\cdots,k)$$

多项式方程组表示如下, 目的是求解 $$x$$：

$$\begin{cases} f_1(x)\equiv 0 \pmod {N_1}\newline f_2(x)\equiv 0 \pmod {N_2} \newline {\vdots} \newline f_k(x)\equiv 0 \pmod {N_k} \end{cases}$$ + 求解条件

Alexander May, Maike Ritzenhofent提出一种求解方法，简单地说当多项式的阶 $$\delta$$ 满足以下情况时可解（$$\delta$$ 是多项式的阶）：

$$\sum\limits_{i=1}^k \cfrac{1}{\delta_i} \geq 1$$

具体描述：

令 $$(f_i,\delta_i,N_i) \quad(i=1,2,\cdots,k)$$ 作为SMUPE问题的首一多项式组，

定义 $$M=\prod\limits_{i=1}^k N_i^{\frac{\delta}{\delta_i}},\delta=\text{lcm}(\delta_i) \quad (i=1,2,\cdots,k)$$

则SMUPE问题可以在 $$O(\delta^6\cdot \log_2M)$$ 复杂度解决。参考：2019红帽杯 - 精明的Alice

​ * ##### 反素数（emirp数）

已知：$$q=\text{reverse_x}(p)$$，$$\text{x}$$ 为进制数。

爆破思路类似RSA parity oracle。$$p,q$$ 是bit翻转关系，已知 $$p$$ 最低的 $$k$$ 位，则已知 $$q$$ 最高的 $$k$$ 位。

假设已知 $$k$$ 位的 $$p,q$$，记为 $$ph,qh$$，利用不等式

$$ph\cdot qh\cdot 2^{1024-2k}<=n<(ph+1)\cdot(qh+1)\cdot 2^{1024-2k}$$ ，

逐位向低地址爆破，不断收缩不等式的范围，最终可求得 $$n$$ 值。

参考：

ASIS 2015 Finals: RSASR

Midnight Sun CTF 2020 Quals

RoarCTF 2020 - Reverse

#python2
#x=10
n = 6528060431134312098979986223024580864611046696815854430382374273411300418237131352745191078493977589108885811759425485490763751348287769344905469074809576433677010568815441304709680418296164156409562517530459274464091661561004894449297362571476259873657346997681362092440259333170797190642839587892066761627543
def t(a, b, k):
    # sqrt(n) has 155 digits, so we need to figure out 77 digits on each side
    if k == 77:
        if a*b == n:
            print a, b
        return
    for i in xrange(10):
        for j in xrange(10):
            # we try to guess the last not-already-guessed digits of both primes
            a1 = a + i*(10**k) + j*(10**(154-k))
            b1 = b + j*(10**k) + i*(10**(154-k))
            if a1*b1 > n:
                # a1 and b1 are too large
                continue
            if (a1+(10**(154-k)))*(b1+(10**(154-k))) < n:
                # a1 and b1 are too small
                continue
      if ((a1*b1)%(10**(k+1))) != (n%(10**(k+1))):
                # The last digits of a1*b1 (which won't change later) doesn't match n
          continue
            # this a1 and b1 seem to be a possible match, try to guess remaining digits
        t(a1, b1, k+1)

# the primes have odd number of digits (155), so we try all possible middle digits (it simplifies the code)
for i in xrange(10):
    t(i*(10**77), i*(10**77), 0)

​ * ##### 4p-1 method

对使用一类特定素数乘积的模数的分解。

当一类特殊的素数用在 RSA 模数中时，可以轻易的将该素数从 $$n$$ 中分解出来。由于这一类素数都形如 $$4p−1=Ds^2$$，因此又被称为 4p-1 method。此外，有些人也会将其视为 RSA 的后门之一，称之为 RSA backdoor。

  • QiCheng Prime

$$Ds={3,11,19,43,67,163}$$

import sys

sys.setrecursionlimit(10^6)

def QiCheng(n):
    R = Integers(n)
    attempts = 20
    js = [0, (-2^5)^3, (-2^5*3)^3, (-2^5*3*5)^3, (-2^5*3*5*11)^3, (-2^6*3*5*23*29)^3]

    for _ in range(attempts):
        for j in js:
            if j == 0:
                a = R.random_element()
                E = EllipticCurve([0, a])

            else:
                a = R(j)/(R(1728)-R(j))
                c = R.random_element()
                E = EllipticCurve([3*a*c^2, 2*a*c^3])

            x = R.random_element()
            z = E.division_polynomial(n, x)
            g = gcd(z, n)
            if g > 1:
                return g

n = 
p = int(QiCheng(Integer(n)))
+ Masaaki Shirase & Vladimir Sedlacek Improvement

更多 $$Ds$$ 值。

CM-based factorization参考：

浅谈 QiCheng Prime

NCTF 2020 - RSA_revenge

CryptoHack Challenge - RSA Backdoor Viability

​ * ##### Common Prime RSA

情形：$$\gcd(p-1,q-1)=g$$

分解的n方法有四种：

（1）修改Pollard’s rho方法分解n；

（2）知道a、b的值分解n；

（3）知道g的值分解n；

（4）分解N-1。

# Pollard’s rho
def f(x, n):
    return (pow(x, n - 1, n) + 3) % n
def rho(n):
    i = 1
    print 'Factorizing'
    while True:
        x1 = getRandomRange(2, n)
        x2 = f(x1, n)
        j = 1
        while True:
            p = gmpy2.gcd(abs(x1 - x2), n)
            if p == n:
                break
            elif p > 1 and isPrime(p):
                print 'Found!'
                return (p, n // p)
else:
                x1 = f(x1, n)
                x2 = f(f(x2, n), n)
            j += 1
        i += 1

详细原理

二十年以来对 RSA 密码系统攻击综述

CTF Wiki - RSA

0xDktb’s Blog

RSA常见攻击方法

Cryptanalysis of RSA and It’s Variants

原文链接： https://lazzzaro.github.io/2020/05/06/crypto-RSA/index.html