A Generalized Attack on the Multi-primePower RSA

以SICTF的一道题为例对论文进行分析

[进阶]easy_or_baby_RSA?

论文地址：https://wwt.lanzout.com/i7lU01omy8uf 轮子地址：https://github.com/zarismine/small-private-d-RSA/blob/main/solve.sage 感谢糖醋小鸡快师傅的博客参考：https://tangcuxiaojikuai.xyz/post/678d5ec.html#more

task

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
from Crypto.Util.number import *
import gmpy2
from enc import flag


m = bytes_to_long(flag)
p = getPrime(256)
q = getPrime(256)
n = (p**5)*(q**3)
phi = (p-1)*(q-1)*p**4 * q**2
d = getPrime(1380)
e = gmpy2.invert(d,phi)
p1 = gmpy2.next_prime(p)
q1 = gmpy2.next_prime(q)
c = pow(m,65537,p1*q1)

print(f"c = {c}")
print(f"n = {n}")
print(f"e = {e}")

'''
c = 6027704939934795526809476320408984749353451163184148193613218899917989403800738729505135647560822568147775955030636790796412038749080589962404088890138
n = 2345049742327685796181532105032554795628696111708534285951012187089560814230641663133312117797131139088986342455315166062482479446527815702735474197358418746066993291802284464812612727625991647573889402281825863578807474887341632160586307943897790827019291411639756252138594856687013363652094621849674259604512491449809337670874218320926522274379234396955495643125680407916326561528774056618181536326260093822819468635513422755218190798616168156924793527386350080400722536575372660262573683231490166520738579903818495107264328324326819989553511070207494208500239603511665056894947107356065440333537271115434438827753
e = 1560967245790387854530279132085915310737094193704812456970549221459036227794862560384548159924112528879771688534015861357630951162558357151823378870345945435342412220708167081427844035498174919749839232806280901968067512188264340755833308035745702731211924571583963089915893479992177245815565483658484702813753029786985027579475059989141119719224961817402605977566829967197490932672021566512826377376988752959467389833419735737545201988916590880487156074463948048461415870071893002222885078350961871888123567241990517365430474025391208925638731208820904957752596249597885523540692851123131898267246576902438472358221

'''

本题利用到多项式

根据题意我们可以分析得出本文中有

结合代码易得r=5,s=3

再根据公式

可计算出

由于d = getPrime(1380)

参照论⽂构造small_roots的多项式和改造格的多项式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
small private d RSA with moduli N=p^r*q^s,that d < 1-(3*r+s)/(r+s)^2 - eps
the eps is 
((15*s+1)*r^4-(2*s^2-10*s)*r^3-(s^3-6*s^2+8*s)*r^2+(2*s^3-12*s^2+6*s)*r+s^4-4*s^3+s^2)
/(4*m*(r-s)*(r+s)^3) in theory,by this we can choose the proper m which is lower than theory.
return : one factor of N.you can factor N by this
for example:
p,q : 256
r,s : 5,3
d : 1300,m = 9
d : 1350,m = 14
d : 1360,m = 20
d : 1370,m = 30
d > 1370,m = 40 # spend long time to do this(2800s)
you can choose the larger m to approach the theory solution
'''

所以我们能够根据d而确定m=40

接下来，构造res=small_roots(f, 2^edge,r,s,N,m)这样的一个格并计算

其中small_roots函数如下：

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
def small_roots(f, bound,r,s,N,m):
    t1 = int((r*(r+s-2))/((r-1)*(r+s))*m)
    t2 = m
    bounds = [bound ,1]
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    x = f.variables()[0]
    for k in range(t2+1):
        for i in range(t2+1-k):
            d=max([0,ceil((r-1)*(t1-k)/r),ceil((s-1)*(t2-k)/s)])
            base=N ^ d * f ^ k * x ^ i
            G.append(base)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
#     B = flatter(B)
    '''
    another question is can't use flatter because flatter not support 
    the matrix that its row far greater than its cols
    '''
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        for i in h.coefficients():
            if gcd(i,N)!=1 and gcd(i,N)!=N:
                return gcd(h.coefficients()[0],N)
    return 0

d > 1370,m = 40 # spend long time to do this(2800s) 代码运行约50分钟

得到pq后，根据公式可算出d，从而求解flag

所以全部代码如下:

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
72
73
74
from Crypto.Util.number import *
import gmpy2

def small_roots(f, bound,r,s,N,m):
    '''
    small private d RSA with moduli N=p^r*q^s,that d < 1-(3*r+s)/(r+s)^2 - eps
    the eps is 
    ((15*s+1)*r^4-(2*s^2-10*s)*r^3-(s^3-6*s^2+8*s)*r^2+(2*s^3-12*s^2+6*s)*r+s^4-4*s^3+s^2)
    /(4*m*(r-s)*(r+s)^3) in theory,by this we can choose the proper m which is lower than theory.
    return : one factor of N.you can factor N by this
    for example:
    p,q : 256
    r,s : 5,3
    d : 1300,m = 9
    d : 1350,m = 14
    d : 1360,m = 20
    d : 1370,m = 30
    d > 1370,m = 40 # spend long time to do this(2800s)
    you can choose the larger m to approach the theory solution
    '''
    t1 = int((r*(r+s-2))/((r-1)*(r+s))*m)
    t2 = m
    bounds = [bound ,1]
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    x = f.variables()[0]
    for k in range(t2+1):
        for i in range(t2+1-k):
            d=max([0,ceil((r-1)*(t1-k)/r),ceil((s-1)*(t2-k)/s)])
            base=N ^ d * f ^ k * x ^ i
            G.append(base)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
#     B = flatter(B)
    '''
    another question is can't use flatter because flatter not support 
    the matrix that its row far greater than its cols
    '''
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        for i in h.coefficients():
            if gcd(i,N)!=1 and gcd(i,N)!=N:
                return gcd(h.coefficients()[0],N)
    return 0

c = 6027704939934795526809476320408984749353451163184148193613218899917989403800738729505135647560822568147775955030636790796412038749080589962404088890138
N = 2345049742327685796181532105032554795628696111708534285951012187089560814230641663133312117797131139088986342455315166062482479446527815702735474197358418746066993291802284464812612727625991647573889402281825863578807474887341632160586307943897790827019291411639756252138594856687013363652094621849674259604512491449809337670874218320926522274379234396955495643125680407916326561528774056618181536326260093822819468635513422755218190798616168156924793527386350080400722536575372660262573683231490166520738579903818495107264328324326819989553511070207494208500239603511665056894947107356065440333537271115434438827753
e = 1560967245790387854530279132085915310737094193704812456970549221459036227794862560384548159924112528879771688534015861357630951162558357151823378870345945435342412220708167081427844035498174919749839232806280901968067512188264340755833308035745702731211924571583963089915893479992177245815565483658484702813753029786985027579475059989141119719224961817402605977566829967197490932672021566512826377376988752959467389833419735737545201988916590880487156074463948048461415870071893002222885078350961871888123567241990517365430474025391208925638731208820904957752596249597885523540692851123131898267246576902438472358221
r,s= 5,3
edge = 1380

if(0):
    a= -int(inverse(e,N)) %N
    PR.<x,y> = PolynomialRing(Zmod(N))
    f=a-x
    m=40
    res=small_roots(f, 2^edge,r,s,N,m)
    print(res) #3880841886154333953773650424963616396441043690868788265611642694520916610789745536631157643368280831495777902173955747450998897753151868119085453880516169

q= gmpy2.iroot(int(res),2)[0]
p=int(gmpy2.iroot(N//q^3,5)[0])
assert N==p^5*q^3

p1 = gmpy2.next_prime(p)
q1 = gmpy2.next_prime(q)
d=inverse(65537,(p1-1)*(q1-1))
print(long_to_bytes(ZZ(pow(c,d,p1*q1))))

本文标题:A Generalized Attack on the Multi-primePower RSA

文章作者:

发布时间:2024年02月20日 - 16时07分

最后更新:2024年02月25日 - 22时05分

原始链接:https://averbeih.github.io/2024/02/20/A-Generalized-Attack-on-the-Multi-primePower-RSA/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. [进阶]easy_or_baby_RSA?
  • task
  • 本题利用到多项式
  • 根据题意我们可以分析得出本文中有
  • 结合代码易得r=5,s=3
  • 再根据公式
  • 可计算出
  • 由于d = getPrime(1380)
    1. 参照论⽂构造small_roots的多项式和改造格的多项式
  • 所以我们能够根据d而确定m=40
  • 接下来，构造res=small_roots(f, 2^edge,r,s,N,m)这样的一个格并计算
  • d > 1370,m = 40 # spend long time to do this(2800s) 代码运行约50分钟
  • 得到pq后，根据公式可算出d，从而求解flag
    • ,