J2Cgeek's Blog

RSA攻击方式汇总

crypto rsa
Word count: 6.2kReading time: 32 min
2020/11/06 Share

明文攻击

小明文攻击

明文过小,导致明文的$e$次方仍然小于$n$(或者大不了多少),这种情况直接对密文$e$次开方(或者爆破$k$加$kn$后$e$次开方),即可得到明文.

分段加密明文

如果每段长度字节数很小,也就是说明文空间太小,就可以直接爆破生成表.

分解N

暴力分解

在$N$的比特位数小于$512$的时候,可以采用大整数分解的策略获取$p$和$q$.网站分解.

p&q不当

当$|p-q|$很大时,一定存在某一个参数较小,可以通过穷举的方法对模数进行试除.

当$|p-q|$很小时.$\frac{(p + q)^2}{4} - n = \frac{(p + q)^2}{4} - pq = \frac{(p - q)^2}{4}$.

说明$\frac{p + q}{2}$接近$\sqrt{n}$,从而找出$\frac{p + q}{2}$和$\frac{p - q}{2}$.然后分解出$p$,$q$.

在$p$,$q$的取值差异过大,或者$p$,$q$的取值过于相近的时候,$Format$方法与$Pollard rho$方法都可以很快将$n$分解成功.此类分解方法有一个开源项目$yafu$将其实现了.

p+1/p-1光滑

光滑数指可以分解为小素数乘积的正整数,当$p-1/p+1$是光滑数的时候,可能可以使用$Pollard’s p − 1$算法或者$Williams’s p + 1$算法来分解$N$.

首先$a^{t(p-1)} - 1 = k * p$.根据Pollard’s p - 1算法:如果$p-1$是一些很小质数的乘积,那么$n!$就能被$p-1$整除,即$n! = t(p-1)$.

对于每一个$n = 2, 3, 4, …$,任意选择一个底数$a$,并计算:$gcd(a^{n!} - 1, N)$,如果结果不为1或$N$,那么就已成功分解$N$.

1
2
3
4
5
6
7
8
9
10
11
import gmpy2

def Pollards_p_1(N):
    a = 2
    n = 2
    while True:
        a = pow(a, n, N)
        p = gmpy2.gcd(a - 1, N)
        if p != 1 and p != N:
            return p
        n += 1

q = next_prime(t * p)

当$q$是$p$的$t$倍的后几个素数,甚至$q$就是$p$的后几个素数,可以在较短时间内分解$n$.

由于$p$是整数,所以$\sqrt{k^2 + 4tn}$是整数,即$k^2 + 4tn$开方后是整数.

如果$pq == n$,那么已成功分解.否则继续寻找$k$.

1
2
3
4
5
6
7
8
9
def factor():
    n_4t = n * 4 * t
    for k in range(100000):
        delta = k ** 2 + n_4t
        if gmpy2.iroot(delta, 2)[1]:
            p = (-k + gmpy2.iroot(delta, 2)[0]) / (2 * t)
            q = t * p + k
            if p * q == n:
                return p, q

模不互素

n1,n2

当存在两个公钥的$N$不互素时,显然可以直接对这两个数求最大公因数(最大公因数为其中一个的$p$或者$q$),然后直接获得两对$p$,$q$,进而获得相应的私钥.

c1,c2,c3,c4,…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import size,bytes_to_long,getStrongPrime
from itertools import combinations

msg = bytes_to_long("Your secret flag is : flag{**************************}")
e = 65537
pri = []

f = open('cipherx.txt', 'w')

for i in range(5):
    pri.append(getStrongPrime(1024,65537))
for k in combinations(pri, 2):
	n = k[0] * k[1]
	print k[0], k[1]
	f.write(str(pow(msg, e, n)) + '\n')
1
2
3
4
5
6
7
8
9
10
11
import primefac
import gmpy2
import libnum
# c1, c2, c3, c4, c5, c6, c7 = ......
e = 65537
k1 = primefac.gcd(abs(c1 - c2), abs(c2 - c3))
k2 = primefac.gcd(abs(c5 - c6), abs(c6 - c7))
n = k1 * k2
phi = (k1 - 1) * (k2 - 1)
d = gmpy2.invert(e, phi)
print libnum.n2s(pow(c1, d, n))

多素因子

如果选取两个以上的素数,记为$p_1, p_2, p_3, \cdots$,相乘得到$n$.

公钥,私钥,加解密都与一般RSA相同.

共模攻击

不同的$e$和$d$共用一个模数$N$,会导致不用分解$N$就能恢复明文.假设$m$为信息明文,加密密钥为$e1$和$e2$,公共模数为$N$.

1
2
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

$e_1$,$e_2$,$c_1$,$c_2$,$N$是公开的.用扩展欧几里得算法求出满足$re1 + se2 = 1$的两个整数$r$和$s$.

假如其中有一个为负数(最多一个为负数),则需要进行处理.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
rs = egcd(e1, e2)
r = rs[0]
s = rs[1]
# 求模反元素
if r < 0:
    r = -r
    c1 = invert(c1, n)
elif s < 0:
    s = -s
    c2 = invert(c2, n)
m = pow(c1, s1, NN) * pow(c2, s2, N) % N

低加密指数攻击

$e$特别小的情况下.已知:

攻击者可以从小到大枚举$k$.

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from gmpy2 import iroot

def smallEattack(c, e, n):
        for i in range(10 ** 10):
            res = iroot(n * i + c, e)
            if res[1]:
                print(res)
                break

低加密指数广播攻击

假设n1,n2,n3互素,否则可计算最大公约数直接得到p,q`,根据中国剩余定理,在$e = 3$时,可以得到:$c_x\equiv m^3 mod n_1 n_2 n_3$,通过对$c_x$进行三次开方就可以求得明文.

1
2
3
4
5
6
7
8
from CRT import chinese_remainder
from gmpy2 import iroot

# datas = ...
nList = [x[1] for x in datas]
cList = [x[2] for x in datas]

print(iroot(chinese_remainder(nList, cList), datas[0][0]))

d泄露攻击

当获得了一次加密中的$d$,不仅可以解密本次加密的数据,还可以对模数$N$进行分解.

$\forall a \in \mathbb{Z}^*_n$,满足$a^{ed-1} \equiv 1 \pmod{n}$.

令:$ed - 1 = 2^st$,$t$是一个奇数.对于至少一半的$a \in \mathbb{Z}^*_n$,存在一个$i \in [1, s]$,使得:$a^{2^{i-1}t} \not\equiv \pm 1 \pmod{n}, 2^{2^it} \equiv 1 \pmod{n}$(二次剩余相关定理).

如果$a$,$i$满足上述条件,则$gcd(a^{2^{i-1}t} - 1, n)$是$n$的一个非平凡因子(也就是$p,q$之一),所以可以对$n$进行暴力破解.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import random
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

n = 0xa66791dc6988168de7ab77419bb7fb0c001c62710270075142942e19a8d8c51d053b3e3782a1de5dc5af4ebe99468170114a1dfe67cdc9a9af55d655620bbab
e = 0x10001
d = 0x123c5b61ba36edb1d3679904199a89ea80c09b9122e1400c09adcf7784676d01d23356a7d44d6bd8bd50e94bfc723fa87d8862b75177691c11d757692df8881
p, q = getpq(n, e, d)

低解密指数攻击

Wiener Attack

如果满足:$d<\frac{1}{3}N^\frac{1}{4}$和$q < p < 2p$,就可以通过$Wiener Attack$分解$n$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import gmpy2

def Simplify(ctnf):
# 连分数化简
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]:
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)

def continuedFra(x, y):
# 展开为连分数
    cF = []
    while y:
        cF += [x / y]
        x, y = y, x % y
    return cF

def calculateFrac(x, y):
# 生成d,k的估计值
    cF = continuedFra(x, y)
    cF = map(Simplify, (cF[0:i] for i in xrange(1, len(cF))))
    return cF

def solve_pq(a, b, c):
# 解韦达定理,已知p+q和n求p,q.
# (p-q)^2 = (p+q)^2 - 4n.
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) / (2 * a), (-b - par) / (2 * a)

def wienerAttack(e, n):
    for (d, k) in calculateFrac(e, n):
        if k == 0: continue
        if (e * d - 1) % k != 0: continue
        phi = (e * d - 1) / k
        p, q = solve_pq(1, n - phi + 1, n)
        #n - phi + 1 = p + q
        if p * q == n:
            return abs(int(p)), abs(int(q))
    print 'not find!'

p, q = wienerAttack(e, n)

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

1
2
3
4
5
6
7
8
9
Bob is extremely paranoid, so he decided that just one RSA encryption is not enough. Before sending his message to Alice, he forced her to create 5 public keys so he could encrypt his message 5 times! Show him that he still is not secure.
Here are the 5 public keys that Bob used, each in the format of (N, e):
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 11)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 41)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 67623079903)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 5161910578063)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 175238643578591220695210061216092361657427152135258210375005373467710731238260448371371798471959129039441888531548193154205671)
Here is his encrypted message:
7117565509436551004326380884878672285722722211683863300406979545670706419248965442464045826652880670654603049188012705474321735863639519103720255725251120
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator
def hack_RSA(e,n):
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.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
            discr = s * s - 4 * n
            if (discr >= 0):
                t = Arithmetic.is_perfect_square(discr)
                if t != -1 and (s + t) % 2 == 0:
                    print("Hacked!")
                    return d

c = 7117565509436551004326380884878672285722722211683863300406979545670706419248965442464045826652880670654603049188012705474321735863639519103720255725251120
e = e1 * e2 * e3 * e4 * e5 % n1
d = hack_RSA(e, n1)
m = pow(c, d, n1)

Boneh and Durfee attack

当$d$较小时,满足$\frac{1}{3}N^\frac{1}{4} \le d < N^{0.292}$时可以利用该攻击.

https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage.

Coppersmith相关攻击

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

Known high in plaintext

1
2
3
4
5
6
7
8
e = 0x3
b = 0x9e67d3a220a3dcf6fc4742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000
n = 0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953
c = 0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c451562c816e2303990834c94e580bf0cbd1
kbits = 72
PR.<x> = PolynomialRing(Zmod(n))
f = (x + b)^e - c
x0 = f.small_roots(X = 2^kbits, beta = 1)[0]

Factoring with High Bits Known

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

1
2
3
4
5
6
7
8
9
10
n = 0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578d
p_fake = 0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000
pbits = 1024
kbits = 130
pbar = p_fake & (2^pbits - 2^kbits)
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X = 2^kbits, beta = 0.4)[0]
#X – an absolute bound for the root (default: see above)
#beta – compute a root mod b where b is a factor of N and b≥N^β

Partial Key Exposure Attack

已知低位的$d$和$N$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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.3)
    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 xrange(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:
                return p
if __name__ == '__main__':
    e = 3
    n = 57569201048993475052349187244752169754165154575782760003851777813767048953051839288528137121670999884309849815765999616346303792471518639080697166767644957046582385785721102370288806038187956032505761532789716009522131450217010629338000241936036185205038814391205848232364006349213836317806903032515194407739
    nbits = n.nbits()
    kbits = floor(nbits * 0.5)
    d0 = 1244848677959253796774387650148978357579294769878147704641867595620534030329181934099194560059806799908134954814673426128260540575360296026444649631806619
    p = find_p(d0, kbits, e, n)
    q = n//p
    print inverse_mod(e, (p - 1))

Coppersmith’s short-pad attack

dp&dq泄露(RSA_CRT leaks)

1
2
dp = d % (p - 1)
dq = d % (q - 1)

假设题目仅给出$p,q,dp,dq,c$,即不给公钥$e$.

由中国剩余定理可得.

$m_2$同理.

1
2
3
4
5
6
7
8
9
10
11
import gmpy2
import binascii

def decrypt(dp,dq,p,q,c):
    InvQ = gmpy2.invert(q, p)
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)
    m=(((mp - mq) * InvQ) % p) * q + mq
    print (binascii.unhexlify(hex(m)[2:]))

decrypt(dp, dq, p, q, c)

dp泄露

假设题目给出公钥$n,e$以及$dp$.

这里可以遍历$(0,e)$,通过$(k2 ∗ (q−1) − k1)(p−1) + 1 = dp e$求出$p - 1$,验证$p$能否被$n$整除.

1
2
3
4
5
6
7
8
9
10
11
import gmpy2
import libnum

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

Least-Significant-Bit Oracle Attack

假如用户知道公钥中$N$,$e$,$c$,并且可以任意构造密文$c1$,返回此密文解密后$p1$的末尾某些比特位的性质(记为函数$f$),可以通过$f$求出明文.

假设函数$f$是表示$p1$的奇偶性.攻击者得到密文$C = P^e \pmod{N}$,将其乘以$2^e \pmod{N}$,并作为密文发送出去.

返回值为$f(2P)$.如果$f(2P)$返回的最后一位是$0$,那么$P < \frac{N}{2}$,如果$f(2P)$返回的最后一位是$1$,那么$P > \frac{N}{2}$.

同理可以获取$f(2P)$和$f(4P)$.如果返回的是$(0,0)$,那么有$P < \frac{N}{4}$,如果返回的是$(0,1)$,那么有$\frac{N}{4} < P <\frac{N}{2}$,如果返回的是$(0,1)$,那么有$\frac{N}{2} < P < \frac{3N}{4}$,如果返回的是$(1,1)$,那么有$\frac{3N}{4} < P < N$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import random
flag = "CTF{this_is_my_test_flag}"
m = bytes_to_long(flag)
key = RSA.generate(1024)
c = pow(m, key.e, key.n)
print("Welcome to BACKDOORCTF17\n")
print("PublicKey:\n")
print("N = " + str(key.n) + "\n")
print("e = " + str(key.e) + "\n")
print("c = " + str(c) + "\n")
while True:
    try:
        temp_c = int(raw_input("temp_c = "))
        temp_m = pow(temp_c, key.d, key.n)
    except:
        break
    l = str(((temp_m & 5) * random.randint(1, 10000)) % (2 * (random.randint(1, 10000))))
    print "l = " + l
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from pwn import *
import libnum
import re
from binascii import unhexlify

def oracle(c):
    l = []
    for i in range(20):
        p.sendline(str(c))
        s = p.recvuntil("temp_c")
        l.append(int(re.findall("l\s*=\s*([0-9]*)", s)[0]))
    flag0 = 0
    flag2 = 0
    for i in range(20):
        if l[i] % 2 != 0:
            flag0 = 1
        if l[i] > 10000:
            flag2 = 1
    return [flag2, flag0]

def main():
    ss = p.recvuntil("temp_c")
    N = int(re.findall("N\s*=\s*(\d+)",ss)[0])
    e = int(re.findall("e\s*=\s*(\d+)",ss)[0])
    c = int(re.findall("c\s*=\s*(\d+)",ss)[0])
    size = libnum.len_in_bits(N)
    c = (pow(2, e, N) * c) % N
    LB = 0
    UB = N
    i = 1
    while LB != UB:
        flag = oracle(c)
        if flag[1] % 2==0:
            UB = (LB + UB) / 2
        else:
            LB = (LB + UB) / 2
        c = (pow(2, e, N) * c) % N
        i += 1
    for i in range(-128, 128, 0):
        LB += i
        if pow(LB, e, N) == C:
            print unhexlify(hex(LB)[2:-1])
            exit(0)

if __name__ == '__main__':
    main()
    p.interactive()

存在$padding$的情况下,$rsa$也存在各种风险,若$e=3$则可以利用$Related Message Attack$.

可以获得下面这个方程组,方程组的解为$x \equiv M_2 \pmod{n}$.

$k_1,k_2$为多项式.$gcd(k_1,k_2)=1 \Rightarrow gcd(s(x),t(x))=x-M_2$.

最后求得$m \equiv \frac{\frac{3b(a^3c_2-b^3)}{c1-a^3c_2+2b^3}+b}{a}-padding2 \pmod{n}$.

1
2
3
4
5
6
7
8
9
10
11
12
def getM2(a, b, c1, c2, n):
    a3 = pow(a, 3, n)
    b3 = pow(b, 3, n)
    first = c1 - a3 * c2 + 2 * b3
    first = first % n
    second = 3 * b * (a3 * c2 - b3)
    second = second % n
    third = second * gmpy2.invert(first, n)
    third = third % n
    fourth = (third + b) * gmpy2.invert(a, n)
    return fourth % n
m = getM2(a, b, c1, c2, n) - padding2

Coppersmith’s short-pad attack（e!=3)

若$e$不为$3$,但$padding$过短,则可以利用$Coppersmith’s short-pad attack$.

工具：
https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage

e与phi(n)不互素

RSA衍生算法-Rabin算法

$Rabin$算法的特征在于$e = 2$.加密过程和$RSA$一样.

$c = m^2 \pmod{n}$

解密过程.

如果$p$,$q$模$4$余$3$的不同素数,则.

证明.

小性质:$p = gcd(|r-s|,n)$.

p,q模4不余3

由$m^2 \equiv c \pmod{n}$分解为两个同余式:$m^2 \equiv c \pmod{p},m^2 \equiv c \pmod{q}$.

可以用二次同余方程的通用解法得到$m \equiv C1 \pmod{p}$和$m \equiv C2 \pmod{q}$.其中$C1$和$C2$均有两个不同的解,然后再用中国剩余定理联立上面两个方程就能解得$m \equiv M \pmod{n}$.

二次同余方程解法的通用算法可以参考$Cipolla’s algorithm$.这个算法主要处理形如$x^2 \equiv n \pmod{p}$,其中$p$是奇素数的方程的$x$的解.

设$a$满足$w=a^2-n$且不是模$p$的二次剩余,由欧拉定理:$w^{\frac{p-1}{2}} \equiv -1 \pmod{p}$,则$x \equiv (a + \sqrt{w})^{\frac{p+1}{2}}$.

主要的问题是根号$w$可能是负数,可以定义实部和虚部利用快速幂算法进行计算,使得最终结果抵消掉根号,时间复杂度为$O(log N)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from Crypto.Util.number import getPrime
from random import randint
from libnum import *
from gmpy2 import *

def power(s1, s2, k1, k2, w, p):
    return ((s1 * k1 + s2 * k2 * w) % p, (s1 * k2 + s2 * k1) % p)

def Cipolla_algorithm(p, n):
    a = randint(1, p)
    w = a ** 2 - n
    while pow(w, (p - 1) / 2, p) != p - 1:
        a = randint(1, p)
        w = a ** 2 - n
    times = (p + 1) / 2
    k1 = 1
    k2 = 0
    first = True
    sum1 = 1
    sum2 = 0
    while times != 0:
        if first:
            k1, k2 = power(k1, k2, a, 1, w, p)
            first = False
        else:
            k1, k2 = power(k1, k2, k1, k2, w, p)
        if times & 1:
            sum1, sum2 = power(sum1, sum2, k1, k2, w, p)
        times >>= 1
    return sum1

def CRT(c, n):
    for i in range(len(n)):
        for j in range(i + 1, len(n)):
            assert gcd(n[i], n[j]) == 1
    assert len(c) == len(n)
    N = reduce(lambda a, b: a * b, n)
    x = 0
    for i, j in zip(c, n):
        N_i = N / j
        N_i_1 = invert(N_i, j)
        x += i * N_i * N_i_1
    return x % N

if __name__ == '__main__':
    p = getPrime(512)
    while p % 4 != 1:
        p = getPrime(512)
    q = getPrime(512)
    while q % 4 != 1:
        q = getPrime(512)
    n = p * q
    m = s2n('this is plaintext')
    c = pow(m, 2, n)
    print 'm is '+str(m)

    get_x1 = Cipolla_algorithm(p, c)
    get_x2 = Cipolla_algorithm(q, c)

    assert  pow(get_x1, 2, p) == c % p
    assert  pow(get_x2, 2, q) == c % q

    c11 = get_x1
    c12 = p - get_x1
    c21 = get_x2
    c22 = q - get_x2

    print 'possible m :' + str(CRT([c11, c21], [p, q]))
    print 'possible m :' + str(CRT([c11, c22], [p, q]))
    print 'possible m :' + str(CRT([c12, c21], [p, q]))
    print 'possible m :' + str(CRT([c12, c22], [p, q]))

n次同余方程

题目给的是$m^e \equiv c \pmod{n}$,其中$p$,$q$已知但是$e$和$\phi(n)$不互素的话,就可以先解出$m^2 \equiv c \pmod{p},m^2 \equiv c \pmod{q}$再用$CRT$联合.

针对$m^3 \equiv c \pmod{p}$,$python$有$sympy$库可以进行处理,算法应该是利用的原根进行计算,所以当$p$比较大的时候计算也是很难的,而且也不是一定有原根的.

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import getPrime
from random import randint
from sympy.ntheory.residue_ntheory import nthroot_mod
p = getPrime(150)
x = randint(1, p)
n = pow(x, 4, p)
x1 = nthroot_mod(n, 4, p, all_roots = False)
assert pow(x1, 4, p) == n
print x1

e = prime * 2^k

$Rsabin(hitcon-2015)$.

$c= m^e = m^{e_0∗2} = (m^{e_0})^2\pmod{N}$,通过Rabin解密算法得到四个可能的$m^{e_0}$,令$c=m^{e_0}$,递归调用上式,直到$m^{e_0}$为素数,即可正常求解.

1
2
3
4
5
6
7
partially_decoded_ct = [ct]
for i in range(5):
    new_partially_decoded_ct = []
    for ct_p in partially_decoded_ct:
        new_ct_p = rabin.decrypt(ct_p)
        new_partially_decoded_ct.extend(list(new_ct_p))
    partially_decoded_ct = set(new_partially_decoded_ct)

素数因子较小

计算$x^e=c mod p$可能的根$x$,即为明文$m$对素数因子$p$的余数,依次求出$m$对所有素数因子的余数,再利用中国剩余定理$CRT$即可求得明文$m$.

e与φ(n)不互素时

1
2
3
4
5
6
7
8
9
10
n1 = 0xcfc59d54b4b2e9ab1b5d90920ae88f430d39fee60d18dddbc623d15aae645e4e50db1c07a02d472b2eebb075a547618e1154a15b1657fbf66ed7e714d23ac70bdfba4c809bbb1e27687163cb09258a07ab2533568192e29a3b8e31a5de886050b28b3ed58e81952487714dd7ae012708db30eaf007620cdeb34f150836a4b723
e1 = 0xfae3a
c1 = 0x81523a330fb15125b6184e4461dadac7601340960840c5213b67a788c84aecfcdc3caf0bf3e27e4c95bb3c154db7055376981972b1565c22c100c47f3fa1dd2994e56090067b4e66f1c3905f9f780145cdf8d0fea88a45bae5113da37c8879c9cdb8ee9a55892bac3bae11fbbabcba0626163d0e2e12c04d99f4eeba5071cbea
n2 = 0xd45304b186dc82e40bd387afc831c32a4c7ba514a64ae051b62f483f27951065a6a04a030d285bdc1cb457b24c2f8701f574094d46d8de37b5a6d55356d1d368b89e16fa71b6603bd037c7f329a3096ce903937bb0c4f112a678c88fd5d84016f745b8281aea8fd5bcc28b68c293e4ef4a62a62e478a8b6cd46f3da73fa34c63
e2 = 0x1f9eae
c2 = 0x4d7ceaadf5e662ab2e0149a8d18a4777b4cd4a7712ab825cf913206c325e6abb88954ebc37b2bda19aed16c5938ac43f43966e96a86913129e38c853ecd4ebc89e806f823ffb802e3ddef0ac6c5ba078d3983393a91cd7a1b59660d47d2045c03ff529c341f3ed994235a68c57f8195f75d61fc8cac37e936d9a6b75c4bd2347
assert pow(flag, e1, n1) == c1
assert pow(flag, e2, n2) == c2
assert gcd(e1, (p1 - 1)*(q1 - 1)) == 14
assert gcd(e2, (p2 - 1)*(q2 - 1)) == 14

$e,b,a$已知,可以求出$bd$($a$模$\phi(n)$的逆元).可以得到:$m^b \pmod{n_1},m^b \pmod{n_2}$.进一步求出$m^b \pmod{q_1},m^b \pmod{q_2}$,然后$CRT$合并求出$m^b \pmod{q_1q_2}$.

此时可以当做一个新的$RSA$题目:密文等于中国剩余定理求出的$m$特解,公钥等于$b$,模数已经分解为$q1$和$q2$.

这里的$e$和$\phi$又不是互素的,有公约数$2$,由于$2$次方太小,所以重复一次将$e$变成$2$然后直接对$m$开方即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from libnum import *
import gmpy2

p = gcd(n1, n2)
q1 = n1 / p
q2 = n2 / p
f1 = (p - 1) * (q1 - 1)
f2 = (p - 1) * (q2 - 1)
e1 = e1 / gcd(e1, e2)
e2 = e2 / gcd(e1, e2)
d1 = invmod(e1, f1)
d2 = invmod(e2, f2)
m1 = pow(c1, d1, n1)
m2 = pow(c2, d2, n2)
m3 = m1 % p
m2 = m2 % q2
m1 = m1 % q1

m = solve_crt([m1, m2, m3], [q1, q2, p]) 
#重新解密一个rsa
n = q1 * q2
f = (q1 - 1) * (q2 - 1)
m = m % n
d = invmod(7, f)
m = pow(m, d, n)
print n2s(gmpy2.iroot(m, 2)[0])

e整除N的欧拉函数(p-1)和(q-1)

$easyRSA(NCTF-2019)$.https://blog.soreatu.com/posts/intended-solution-to-crypto-problems-in-nctf-2019/#easyrsa909pt-2solvers.

先用$Adleman-Manders-Miller rth Root Extraction Method$在$GF(p)$和$GF(q)$上对$c$开$e$次根,分别得到一个解.

然后去找到所有的$0x1336$个$primitive nth root of 1$,乘以上面那个解,得到所有的$0x1337$个解.

再用$CRT$对$GF(p)$和$GF(q)$上的两组$0x1337$个解组合成$mod n$下的解,可以得到$0x1337**2==24196561$个$mod n$的解.最后能通过$check$的即为$flag$.

外部资料

使用SageMath尝试Coppersmith’s Attack

Sage的small_root方法

1
2
3
4
5
6
N = 10001
K = Zmod(10001)
P.<x> = PolynomialRing(K)
f = x^3 + 10*x^2 + 5000*x - 222
print f.small_roots()
[4]

http://sage-doc.sis.uta.fi/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html#sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots

p的高位或低位已知时

Sage的small_root方法b >= N^β可以找到以N的除数b为模的解。在此，模数为N的解就是β = 1这种情况。 考虑到公钥n是RSA中相同位数的p和q的乘积，可以通过设置β = x度数来求b = p or q模解,满足n ^ x < p，暂设x=0.3。

已知p的高位是n的位数的1/4，即p的位数的约1/2时，将其余位设置为0, 设为pbar。

此时f(x) = x + pbar = 0 (mod b)，可以通过求出满足的f（x）的值x0,即p = x0 + pbar。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
p = 0x00f23799c031b942026e420769b74d22fa2114428189139c43c366c6ab8367c6b3d6f821449aafb2058b0e6ed964fa0ad45fb306f96376e80823a72b58101919e50acad3b5e6d079e7ff9218ed6df6edbef536742714ce88b2e717f45af53ef0d04c89faf01c80b28e764973aba27726c85c0236e8756a865c03577722bac5e391
q = 0x00c9d24330fa4945cfe1e5d6912d6bde0231035a1cc8d8ae67d949347b895f8d579bce2adaf37c568957b17a6564dbf80d36d81e4622ab30e02132b0155aefbd3912a27c625a9b7b05bc72217039f5aa88c20cbf9871c3228e9d80d9106f94b11c1f50c40c96862b5cd6b6f781883dd2eff80a059d3ca027af6a03edeb34a7390f
n = p*q

beta = 0.5
epsilon = beta^2/7

pbits = p.nbits()
kbits = floor(n.nbits()*(beta^2-epsilon))
pbar = p & (2^pbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits)

PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar

print p
x0 = f.small_roots(X=2^kbits, beta=0.3)[0]  # find root < 2^kbits with factor >= n^0.3
print x0 + pbar

运行结果：upper 586 bits (of 1024 bits) is given

1
beta`和`X`参数的作用是缩小范围，限制了`n ^ 0.3 < p`和`x0 < 2 ^ kbits

即使知道了低位而不是高位，也可以通过使用多项式来恢复p的值。

当秘密密钥d的低位已知时

若e较小，对于秘密密钥d，如果已知低位，大约是n位的1/4，则可以恢复d的值。称为部分密钥暴露攻击。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    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 xrange(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:
                return p


if __name__ == '__main__':
    n = 0x00bef498e6eb2cffe71312da47ab89d2c47db7438ea2cfa992ddddbc2a01978001fc51e286e6ebf028396cdb8b3323c60e6b9d50cd84187cf7f48e3875a2f0890f70b02333ad89db2923863ce146562286f63fb0a1d0198e3a6862ba5ac12e85a5c6d0d27cb1c81bdf69cc5bc95b8001a2f744517f9437b4ddd5a076fc0e9a5de1a7a268c40f31aa29e8dc27c0b3a182299ca7a9335b4bd4585452f6107c238e486c98dd73a5f9862e9e80b152f53381c72f897107551c281259ac3ee32c4b4f46cc03127d1bf699acd0266f3c6729253c70da0c69b1560fa172735709866b375b6eba294e1ce8b46fba798ba380080b4bf9603998cac199d9cd46e30ae8da9e7f
    e = 3
    d = 0x7f4dbb449cc8aa9a0cb73c2fc7b1372da924d7b46c8a710c93e9281c010faaabfd8bec59ef47f5702648925cccc284099d138b33ad65a8a54db425a3c1f5b0b4f5cac22273b13cc617aed340d98ec1af4ed5206be011097c459726e72b7459192f35e1a8768567ea46883d30e7aaabc1fa2d8baa62cfcde93915a4a809bc3e9547bb07e1ecca16e51078312e89f0561e31b55db8b0ea5bc87a6ca7464a3d7c28a68c60e2ba88fe6a7d2b300d723e549910a987da89fc0a1c0de197a3d62c501b1f0e819891b1c32a0d6c233f2a285df87bb9e5c6c72d983ff3e706696bba639f573f9c3646968f02f3a615a438e20bb7c38d53621079f2899547a95350f3abeb

    beta = 0.5
    epsilon = beta^2/7

    nbits = n.nbits()
    kbits = floor(nbits*(beta^2+epsilon))
    d0 = d & (2^kbits-1)
    print "lower %d bits (of %d bits) is given" % (kbits, nbits)

    p = find_p(d0, kbits, e, n)
    print "found p: %d" % p
    q = n//p
    print d
    print inverse_mod(e, (p-1)*(q-1))

运行结果：lower 585 bits (of 2048 bits) is given

当知道明文m的高位或低位时

若e较小，当已知明文m的高位约为n位数的（1-1 / e）时，其余位设置为0，设为 mbar。当对应的密文为c时，f(x) = (mbar + x)^e - c (mod n)可以通过获得以下公式的解来获得满足此要求的f（x）的值，即m。这b = n是因为是这种情况β = 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 0x00bef498e6eb2cffe71312da47ab89d2c47db7438ea2cfa992ddddbc2a01978001fc51e286e6ebf028396cdb8b3323c60e6b9d50cd84187cf7f48e3875a2f0890f70b02333ad89db2923863ce146562286f63fb0a1d0198e3a6862ba5ac12e85a5c6d0d27cb1c81bdf69cc5bc95b8001a2f744517f9437b4ddd5a076fc0e9a5de1a7a268c40f31aa29e8dc27c0b3a182299ca7a9335b4bd4585452f6107c238e486c98dd73a5f9862e9e80b152f53381c72f897107551c281259ac3ee32c4b4f46cc03127d1bf699acd0266f3c6729253c70da0c69b1560fa172735709866b375b6eba294e1ce8b46fba798ba380080b4bf9603998cac199d9cd46e30ae8da9e7f
e = 3

m = randrange(n)
c = pow(m, e, n)

beta = 1
epsilon = beta^2/7

nbits = n.nbits()
kbits = floor(nbits*(beta^2/e-epsilon))
mbar = m & (2^nbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (nbits-kbits, nbits)

PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c

print m
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n
print mbar + x0

运行结果：upper 1658 bits (of 2048 bits) is given

这个例子中 e=3，公式kbits = floor(nbits*x)其中x最大不超过0.25 至少要已知1536个字符

例题

广外rsa2

已知n，p的高位576位，要求出完整的p

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from sage.all import *
n = 0xeb4f8c45336c229371fd73a252b24dd3bf8b3cdc1bb1864f140fd63c88d47c44ba228bebe223fe53c7eaf88678b780821a6660b2726506216554990a5dda178ee04a47c7f1974fc8f8268d081bbb2be7e7353ccf36fecfce5f5f82722d064928f2d60844373c52b4d1db9dc41f7f16807c5b4356c4d2290811e25c51ef1227aa6e893d37dd8743e391fa638d77d0c55e4fb331576602128333d4be95f06523521e7511b39fc20111c88f2635b67e3531684d58ea6574179b5e63a862d073241f5ff91c97a45aa3d8e3287d8161a97728d2e19d72669f39f9e6ad10677bb563bdef30d0dcfa719c2f1836bd02b73d21dbecc11717b54c45d415d3f423ce6dfd8dL
p2 =0xfb2151c701f7667b53822fe625b95edee00c3a947b234eca47903ef62fb128d813a9c1acb328f3f7181d24ce31814cd1a69ac4b61b269e2b0eb7fbaabe9633d33a36d0715b4cd386L

e = 0x10001
pbits = 1024

kbits = 448
p2 = p2 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p2
roots = f.small_roots(X=2^kbits, beta=0.4)

if roots:        
    p = p2+int(roots[0]) 
    print "n: ", n   
    print "p: ", p
    print "q: ", n/p

如果已知位数不足576位，可以爆破所缺位的二进制，达到576位了再用算法恢复完整的p

高校运维

题目给了enc,n,e

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from flag import FLAG
from Crypto.Util.number import *
import os
import gmpy2

p = getPrime(2048)
q = gmpy2.next_prime(bytes_to_long(os.urandom(32)*8))
n = p*q
e = 65537

m = bytes_to_long(FLAG)
enc = pow(m,e,n)

with open("enc","wb") as f:
    f.write(str(enc)+"\n")
    f.write(str(n)+"\n")

爆破减去 next_prime的产生的偏移，os.urandom(32)得到的32字节是mod p方程的小根

已知bytes_to_long(os.urandom(32)*8)会是bytes_to_long(('\x00'*31+'\x01')*8)的倍数，设t = bytes_to_long(('\x00'*31+'\x01')*8)

通过小根求出来的r和i=1452，得到p=(r*t+1452)，monic表示首一

1
2
3
4
5
6
7
8
9
10
11
n=120807710153113702551615579080626349972702435654213602643278178850601270671946229285821528380336690426317604059622034599839001416930715968066016772516322170847232613450387418879151680919583407733398280475244970196660246303755390654445483988806163997943960045202300170321033632884706732013873256539789027552900587666422370948750842536533923935656875965991272731558533581897633592458155859972323709278905289729445241014357315813048740496355157322217479024997808766708783034169626351658483634985294355975778256304622956911622334081421352132051371869608818591717661111189285407351900021893457439899221542567630909004930602528901255429064258255953091799356807896508016798627878778491866567622281528441807056062152648122769596905617532839645811871242955534491003544450002957748265702306031022676181061669831693628120952508570252446308607118097142440911574131249381253267168309302968966178203572103064042325655007707720847432033652545364390235670894288288369956445797446648862192044259720010703057599068467348014822871417162946598110099990800849922664801383108437169282005803013729663209291895365964487113632471631243676196750054390014101920098216264290734689252677221687512705895162185620154778448467145374612676883160397044672382343419867
t=bytes_to_long(('\x00'*31+'\x01')*8)
K = Zmod(n)
P.<x> = PolynomialRing(K)
for i in range(1452,1453):
    f= x * t +i
    r =f.monic().small_roots(beta=0.45)
    if r:
        print i,r
        p = r * t + i
        print p

sage运行得到

1
1452 [25097212148084861298779072266686287643405205222520917844564707998487462593163]

Author：J2c

原文链接：https://j2c.gitee.io/geekblog/2020/11/06/RSA%E6%94%BB%E5%87%BB%E6%96%B9%E5%BC%8F%E6%B1%87%E6%80%BB/

发表日期：November 6th 2020, 1:20:42 am

更新日期：November 6th 2020, 1:39:48 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 明文攻击
    1. 1.1. 小明文攻击
    2. 1.2. 分段加密明文
  2. 2. 分解N
    1. 2.1. 暴力分解
    2. 2.2. p&q不当
    3. 2.3. p+1/p-1光滑
    4. 2.4. q = next_prime(t * p)
  3. 3. 模不互素
    1. 3.1. n1,n2
    2. 3.2. c1,c2,c3,c4,…
  4. 4. 多素因子
  5. 5. 共模攻击
  6. 6. 低加密指数攻击
  7. 7. 低加密指数广播攻击
  8. 8. d泄露攻击
  9. 9. 低解密指数攻击
    1. 9.1. Wiener Attack
    2. 9.2. Boneh and Durfee attack
  10. 10. Coppersmith相关攻击
    1. 10.1. Known high in plaintext
    2. 10.2. Factoring with High Bits Known
    3. 10.3. Partial Key Exposure Attack
    4. 10.4. Coppersmith’s short-pad attack
  11. 11. dp&dq泄露(RSA_CRT leaks)
  12. 12. dp泄露
  13. 13. Least-Significant-Bit Oracle Attack
  14. 14. Related Message Attack(e=3)
    1. 14.1. Coppersmith’s short-pad attack（e!=3)
  15. 15. e与phi(n)不互素
    1. 15.1. RSA衍生算法-Rabin算法
      1. 15.1.1. p,q模4不余3
    2. 15.2. n次同余方程
    3. 15.3. e = prime * 2^k
    4. 15.4. 素数因子较小
    5. 15.5. e与φ(n)不互素时
    6. 15.6. e整除N的欧拉函数(p-1)和(q-1)
  • 外部资料
    1. 1. 使用SageMath尝试Coppersmith’s Attack
      1. 1.1. p的高位或低位已知时
      2. 1.2. 当秘密密钥d的低位已知时
      3. 1.3. 当知道明文m的高位或低位时
    2. 2. 例题
      1. 2.1. 广外rsa2
      2. 2.2. 高校运维
    • Total : 1
    2020
    crypto rsa