DASCTF 八月赛 Crypto 部分Writeup

 

前言

由于比赛的时间和上课的时间冲突了，只抽空做了一下crypto3。赛后有把没有做的题做了一下，不得不说安恒月赛的水平越来越高，比某guo赛强很多(吹一波师傅们)。

 

strange_LSB

首先分析一下源码：

def get_N():
    BITS = 128
    bits = 70
    power = 4
    while 1:
        r_p, r_q = randint(1 << bits, 1 << bits + 1), randint(1 << bits, 1 << bits + 1)
        p = randint(1 << BITS, 1 << BITS + 1) ** power + r_p
        q = randint(1 << BITS, 1 << BITS + 1) ** power + r_q
        N = p * q

        if isPrime(p) == True and isPrime(q) == True:

            return r_p, r_q, p * q

m = bytes_to_long(flag)
e = 0x20002
r_p, r_q, N = get_N()
c = pow(m, e, N)

print(r_p, r_q)
print(N)
print(c)

我们发现p和q都是形如x^4+a其中x是128位的数，而a是70位的数。假设p=x^4+a，q=y^4+b很容易得到n=p*q=(x*y)^4+a*y^4+b*x^4+a*b

由于a和b过小，如果对n直接开四次方根，可以得到n^(1/4) == x*y,验证代码如下：

from gmpy2 import *
from Crypto.Util.number import isPrime
from random import randint
def test():
    BITS = 128
    bits = 70
    power = 4
    while 1:
        r_p, r_q = randint(1 << bits, 1 << bits + 1), randint(1 << bits, 1 << bits + 1)
        x = randint(1 << BITS, 1 << BITS + 1)
        y = randint(1 << BITS, 1 << BITS + 1)
        p = x** power + r_p
        q = y ** power + r_q
        N = p * q
        tmp = iroot(N,4)[0]
        print(x*y == tmp)
        if isPrime(p) == True and isPrime(q) == True:
            return r_p, r_q, p * q
test()

于是可以根据n^(1/4) == x*y以及p=x^4+a，q=y^4+b求解x和y其中a,b均已知，使用sage求解方程：

# Product = 
Product = 213145517693473276472741453960288533380429305903664848348709095184411519973440
r_p,r_q = 2328957326808590967503,1461823189315446122067
n = 2063976825250272595388593010902135884890103500050668819831297298752625852801511751408065791793019547189652146900555099774958963484251389843293161492169372162099883268521841628059721206917183539122495978771222844176897602295938111287844515247614001317395469781055421827261855002882782439392377329027883959379213
# (x*y) == iroot(n,4)[0]
# (x^4+a)*(y^4+b) == n
var('x,y')
eq1 = x*y == Product
eq2 = (x^4+r_p)*(y^4+r_q) == n
solve([eq1,eq2],[x,y])
#x = 411149993498066384380477696729089782688
#y = 518413039192899046033157413963674073130

于是可以分解n，得到p,q，不过需要注意的是gcd(e,phi) == 2，我们只需要构造出 m^(2*0x10001*b) mod n即可，其中有0x1001*b = 1 mod phi然后对得到m^2 mod n开二次方根,最终脚本如下：

from gmpy2 import *
r_p,r_q = 2328957326808590967503,1461823189315446122067
n = 2063976825250272595388593010902135884890103500050668819831297298752625852801511751408065791793019547189652146900555099774958963484251389843293161492169372162099883268521841628059721206917183539122495978771222844176897602295938111287844515247614001317395469781055421827261855002882782439392377329027883959379213
c = 1547619272568821977924291607912472468030540633498046405850444894565247157649485437790107315326889134051033004979821144414033498309691970259960647249579974375705070385006255462150657629039234264256644150151347889353513962706887104364057437209020689956808789043545320455581507831694598090423468743540228515368341
x = 411149993498066384380477696729089782688
y = 518413039192899046033157413963674073130
p = x**4+r_p
q = y**4+r_q
assert is_prime(q) and is_prime(q) and p*q == n
phi = (p-1)*(q-1)
e = 0x20002
# dd*(e//2) = 1 mod phi ==> dd*0x10001 = 1 mod phi
dd = invert(e//2,phi)
# c == m^e
# m^(e*dd) mod n ==> n^(2*0x10001*dd) mod n ==> m^2 mod n
M = pow(c,dd,n)
assert iroot(M,2)[1] == True
flag = iroot(M,2)[0]
print(bytes.fromhex(hex(flag).strip("0xL")))

math_stream

个人认为本次比赛最难的一题，题面如下：

from Crypto.Util.number import isPrime, getPrime, bytes_to_long
from random import randint

flag = b'DASCTF{********************************}'

def generate():
    n = getPrime(1024)
    a, c = randint(1, n), randint(1, n)
    b = a + 1
    return a, b, c, n


def get_stream(target):
    stream = []
    for i in range(target + 1):
        if i < 2:
            t = randint(1, n)
            stream.append(t)
        else:
            stream.append((a * stream[i - 2] + b * stream[i - 1] + c) % n)
        if i > 300 and i < 307:
            print(stream[i])
    return stream

target = 2**1024
a, b, c, n = generate()
print((a,b,c,n))
stream = get_stream(target)

plain = bytes_to_long(flag)
cipher = plain ^ stream[target]

print(cipher)

这道题有两个考点，第一个考点就是如何恢复参数a,b,c,n，第二个难点是target过大，如果使用题目种的方法计算会爆内存。

恢复参数

熟悉LCG的选手应该对此类参数恢复认识比较深刻，不过次题稍微有所变化。我们发现s[i] = a*s[i-2]+b*s[i-1]+c mod n有四个未知参数，且每一项与其前两项相关。如果我们将n恢复出来，剩下的问题就迎刃而解了。那么如何恢复n呢？？考虑两个同余式，t1 = mod n以及t2 = 0 mod n，我们对其稍加变化得到t1 = k1*n,t2 = k2*n，此时我们对t1,t2求解最大公因数，可以得到n 或者k*n，对于k*n我们只需要分解它即可得到n。那么我们需要利用连续的6个s[i]构造出至少两个模n同余0的整数，然后对其求最大公因数，便可以得到n进而得到a,b,c

不妨设六个输出分别为x1,x2,x3,x4,x5,x6，由于x[i] = a*x[i-2]+b*x[i-1] +c mod n，其中 b = a+1,于是有

x[i] = a*x[i-2] + a*x[i-1] + x[i-1] +c mod n即x[i] - x[i-1] = a*x[i-2] + a*x[i-1] + c mod n

令yi分别为

y1 = x3-x2 = a(x1+x2)+c
y2 = x4-x3 = a(x2+x3)+c
y3 = x5-x4 = a(x3+x4)+c
y4 = x6-x5 = a(x4+x5)+c

令zi分别为

z1 = y2 - y1 = a(x3-x1)
z2 = y3 - y2 = a(x4-x2)
z3 = y4 - y3 = a(x5-x3)

令ti分别为

t1 = z1*(x4-x2) = a(x3-x1)(x4-x2)
t2 = z2*(x3-x1) = a(x3-x1)(x4-x2)
t3 = z2*(x5-x3) = a(x5-x3)(x4-x2)
t4 = z3*(x4-x2) = a(x5-x3)(x4-x2)

求gcd(t1-t2,t3-t4)可以的kn，幸运的是题目中的数据求出的k恰好为1。恢复得到n后，可以利用z1的等式求a,同样的可以求得c（需要注意的是不能直接用z1 * inverse(x3-x1) mod n求a，必须将z1转换成(x4+x2-2*x3)然后求解）

计算s[target]

由于target过大，我们无法通过递推式直接求解，笔者这里使用了coin师傅的做法，即使用矩阵快速幂快速求解s[target]

根据递推关系式有 s[i] = a*s[i-2]+b*s[i-1]+c mod n 我们将其转化成矩阵的形式,可以得到

由于是递推的形式，于是有

也就是说，我们只需要将系数矩阵进行k次运算便可以得到最终结果的系数矩阵，然后与原始矩阵相乘便可以得到s[target]

最终的exp如下：

from Crypto.Util.number import *


x1 = 123702839015756050884261730350882737708358949223717439499184803586403380580917033774031115610745320766887583414238651786366942713037837183155670218651008201659397071753885966029204756119524199815830117337679903000409946531282131341544499373725768763177481236458288527526859422459135345981831473247316555618560
x2 = 53924539754438007029501782029367518619266978487508630921932520518338714507664032847344261722536853774745396939590212348751300654791168048424611586167435934594214127893014772880318410947388412139484910911558913354881832668949036424760411326983813389804113790149675585445672972740198653398937213550096612898644
x3 = 63167700157587157707659591399396856546372104423703909698033441469110658576803656359757694321232303912965997844863919208184964899691086676221424510238937996039639020372184420079106454203010811220417415790732729673830907444478937628707872186593129029778616120328244635824580198884662150104071084993653737914022
x4 = 60900060027375388502954968533962551010895369320035053843073456747137873661715722305461794383581233299465108460448730880547665937249092184288347189085393775979063774890144837289588709330708116910722986763529852613180587935929862087569945164722421961012524239918061319269183814829620043095252880283996001514164
x5 = 67113877662673866233083488077860646719333535770452193680770137339822227232411855308016162556072517267428842392157280102333021460946927124183519015361915428846609475511896652480835848461061078559069446935766782858959584622772958271986367572980550469374057939856055426306880686615182779562168848708759248213327
x6 = 35321475740169398933875140842714262960904281331750205573172983410230385562745162356815900214941351338686778803036306575637404857858578337229023073873912358708980334069653782813016210177757649710822363593438233897497585809695658043901986740902609804765459645039370188002526182350951413827277418881541889614752
cipher = 6257754829567986763892047832635830335816090670173191750751645793632788077917375687942054101544041498378086719313412925093077211368386033569497742486801694329756989184534154729709541023134576678323307630303652989589994288555559228966732861033813909078153507299492167442982631897158564781706799632969673086582


from gmpy2 import *
y1 = x3-x2
y2 = x4-x3
y3 = x5-x4
y4 = x6-x5

z1 = y2 - y1
z2 = y3 - y2
z3 = y4 - y3

A = z1*(x2-x4)
B = z2*(x1-x3)
C = z2*(x3-x5)
D = z3*(x2-x4)

n = gcd(A-B,C-D)
assert is_prime(n)


a = (x4+x2-2*x3)*inverse(x3-x1,n)%n
b = a + 1

c = (x3-a*x1-b*x2)%n

assert x4 == (a*x2+b*x3+c)%n
assert x5 == (a*x3+b*x4+c)%n
assert x6 == (a*x4+b*x5+c)%n

target = 2**1024


def recover(a,c,n,now,pre,limit=301):
    b = a+1
    while limit:
        now,pre = pre,((now-c-b*pre)*inverse(a,n))%n
        limit -= 1
    return int(pre),int(now)
a0,a1 = recover(a,c,n,x2,x1)


# 矩阵乘法
def mul(A,B,n):
    C = [[0,0,0],[0,0,0],[0,0,0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                C[i][j] = (C[i][j]+A[i][k]*B[k][j])%n
    return C
# 矩阵快速幂
def matrix_pow(A,k):
    I = [
        [1,0,0],
        [0,1,0],
        [0,0,1]
    ]
    while k>0:
        if k&1:
            I = mul(I,A,n)
        A = mul(A,A,n)
        k //=2
    return I
# 原始矩阵，这里笔者将初始的s[0],s[1] 恢复了出来
origin = [
    [a1,a0,1],
    [0,0,0],
    [0,0,0]
]
# 系数矩阵
coff = [
    [b,1,0],
    [a,0,0],
    [c,0,1]
] 
# 目标的系数矩阵 可以通过矩阵快速求解
COFF = matrix_pow(coff,target-1)
# 最终的结果
RES = mul(origin,COFF,n)

stream = int(RES[0][0])%n
flag = cipher^stream
print(long_to_bytes(flag))

 

Game114514

这道题是源自nsucrypto 2020上的一道改编题，有兴趣的读者可以自行google。题面如下：

from Crypto.Util.number import *
from secret import flag

def genKey():
    p, q, r = getStrongPrime(512), getStrongPrime(512), getStrongPrime(512)
    n = p * q * r
    N = getRandomNBitInteger(2048) + 114514
    h = pow(11, 2020, N) * (p**2) + pow(45, 2020, N) * (q**2) + pow(14, 2020, N) * (r**2)
    h %= N
    prikey = p, q, r
    pubkey = n, h, N
    return prikey, pubkey

def leak():
    prikey, pubkey = genKey()
    print(prikey[-1])
    print(pubkey)
    print(long_to_bytes(pow(bytes_to_long(flag), 0x10001, pubkey[0])))

leak()

'''
10239306894596345639236857549916052649308185323518947210543117431020838518896685928967228477542397559834309548973113911963605527905768865151004026488002001
(950011144706585173040346411219364953625466585615355410255812718691071135788174403542375786631101982145942591776585786129800305449594376958613054582994092738689865963264366583306474256168938125436839905240527193347815308291717160425478107410162284856407031175529497870108531319160329226235433600642949059132425064084520547134426901012063053260740485712639947158958018914357078515205544835414225928650602816394134098408766194935057220248610138255820083487975177841, 21845857294867800253967572483849436586466097787581764670569338069105518885425999674533902361247100300133107524692755731302138893826828614419216743419929405090066603853587168841953460023313440967804760511172469644482888563447311330068029693264636332400460522015544196045907743566376516760896674109539257774660389303282381801472315963493071381982569866891274109528852684214970613999327587661933693311084291006897450171519933769360217856463636671441159748185690007577600849938135435924224682264445569689364902460389631331260563904831314100885117032357972432445404061393038108841617572136921335397901954583048372618097362, 31965147293888675740203439764799829784520227891846963591296575627972550910339878090903426907141529767159158546614829904656311989936505471896532096094193238298363694007139459659240391801384569276567972248458362985516106174346014641864342582173706703805542459282608624826403810815975179476327863662631681133966307722920056337352630101824259669740913078488217166961256232508892213581337616407618268731068455619843843314400038408252281146580404528613374235502102493763026383481939170053271778897261922170229088391513609980189281611652128299008626921592268614012904719221701040158989306699509941421276613062052254533708176)
b'\x19D$\xc1\x16\xb5\xdd\xd4\xca`f\x94P0\x1eAP}\x9d\xb2\x16\x13+\xbfe\xc6\xae\xb7YWur\xae\xdc[\x08\xa1T\xd2\xd0\xc8i;\xbf\xed3\x05\xce\xd4\xa9\xf0\x80\xbdV-\xac\xc3\xf3\x80\xa5\xb8lV\t\xf3\xf6\xac\x06\x14\x9e<\xb5T}?\xc6\xdc\x90\xbeD\x19\xef8\xf8\x06\x08\xa4\xf1\xdb\xbe\xea}\xc9\xdeg\x14\x96\xfa\xce\x16*G \x8f\x8e\x7f\x9a\xf3.\x94\x00n2o]\x11\xb5\xb1\xa7\xcb4\x0e\xd8\x81\x16\x88\xf5XY\x9a\xd6l\x90\x16J1\xd9\x9a\xa1\xe2e\x0cC\xe3\xe0\xb50\xb1\x18\x1b\x82),l)*\xf5\xdf;(n|\xe5\x91\xbf\x86\xde"\xcb\xc0v\xb4\xb3\xbc\xbe%\xa9aqk\xa0\x85,\xcck\x1e(\x10\xa7\xd51\x02'
'''

我们发现n是三素数组合的模数，其中素数r已经给出，于是可以将题目化简为：

构造如下同余式

则有

于是有向量(a1,a2)在如下的格中

通过格基规约，可以得到较小的向量(a1,a2)

且k的范围比较小，这里没有具体推出，大概-20 ~ 20 就够了

最终脚本如下：

from Crypto.Util.number import *
from sage.all import *
r = 10239306894596345639236857549916052649308185323518947210543117431020838518896685928967228477542397559834309548973113911963605527905768865151004026488002001
n,h,N = (950011144706585173040346411219364953625466585615355410255812718691071135788174403542375786631101982145942591776585786129800305449594376958613054582994092738689865963264366583306474256168938125436839905240527193347815308291717160425478107410162284856407031175529497870108531319160329226235433600642949059132425064084520547134426901012063053260740485712639947158958018914357078515205544835414225928650602816394134098408766194935057220248610138255820083487975177841, 21845857294867800253967572483849436586466097787581764670569338069105518885425999674533902361247100300133107524692755731302138893826828614419216743419929405090066603853587168841953460023313440967804760511172469644482888563447311330068029693264636332400460522015544196045907743566376516760896674109539257774660389303282381801472315963493071381982569866891274109528852684214970613999327587661933693311084291006897450171519933769360217856463636671441159748185690007577600849938135435924224682264445569689364902460389631331260563904831314100885117032357972432445404061393038108841617572136921335397901954583048372618097362, 31965147293888675740203439764799829784520227891846963591296575627972550910339878090903426907141529767159158546614829904656311989936505471896532096094193238298363694007139459659240391801384569276567972248458362985516106174346014641864342582173706703805542459282608624826403810815975179476327863662631681133966307722920056337352630101824259669740913078488217166961256232508892213581337616407618268731068455619843843314400038408252281146580404528613374235502102493763026383481939170053271778897261922170229088391513609980189281611652128299008626921592268614012904719221701040158989306699509941421276613062052254533708176)
h = (h-pow(14, 2020, N) * (r**2))%N


def Solve(n,m,h):
    inv = (45**2020)*inverse(11**2020,m)
    lattice = Matrix([
        [1,inv],
        [0,m]
    ])
#     d = lattice.det()
    res = lattice.LLL()
    a1 = int(res[0,0])
    a2 = int(res[0,1])

    if a1<0:
        a1,a2 = -a1,-a2%m


    tmp = int(a1*inverse(11**2020,m)*h)%m
#     right = a1*p**2+a2*q**2
    var('x')
    var('y')
    n2 = n*n
    for i in range(-20,20):
        print(i)
        cur = tmp + i*m
        eq1 = x*y==n
        eq2 = a2*x*x-cur+a1*y*y == 0
        res = solve([eq1,eq2],x,y)
        print(res)

# Solve(int(n//r),int(N),h)

p = 9552641813064463415650665555944096831861275975583818855746766413412522449762636601729318577145972252465103719236901124310326500069446467666916681091584951
q = 9712580837261650323984493004818315148376274544819233079130439582789536502614676519614339721770095880812234709221612563734970622138908361546042552704780391

phi = (p-1)*(q-1)*(r-1)
d = inverse(65537,phi)
c = bytes_to_long(b'\x19D$\xc1\x16\xb5\xdd\xd4\xca`f\x94P0\x1eAP}\x9d\xb2\x16\x13+\xbfe\xc6\xae\xb7YWur\xae\xdc[\x08\xa1T\xd2\xd0\xc8i;\xbf\xed3\x05\xce\xd4\xa9\xf0\x80\xbdV-\xac\xc3\xf3\x80\xa5\xb8lV\t\xf3\xf6\xac\x06\x14\x9e<\xb5T}?\xc6\xdc\x90\xbeD\x19\xef8\xf8\x06\x08\xa4\xf1\xdb\xbe\xea}\xc9\xdeg\x14\x96\xfa\xce\x16*G \x8f\x8e\x7f\x9a\xf3.\x94\x00n2o]\x11\xb5\xb1\xa7\xcb4\x0e\xd8\x81\x16\x88\xf5XY\x9a\xd6l\x90\x16J1\xd9\x9a\xa1\xe2e\x0cC\xe3\xe0\xb50\xb1\x18\x1b\x82),l)*\xf5\xdf;(n|\xe5\x91\xbf\x86\xde"\xcb\xc0v\xb4\xb3\xbc\xbe%\xa9aqk\xa0\x85,\xcck\x1e(\x10\xa7\xd51\x02')
m = pow(c,d,n)
print(long_to_bytes(m))

 

White_Album

一道简单的coopersmith,题面如下：

from gmpy2 import *
from Crypto.Util.number import *
from secret import secret
from random import *

e = 3

def generate(nbits):
    while 1:
        p = getPrime(nbits)
        if gcd(p - 1 , e) == 1:
            return p

p = generate(1024)
q = generate(1024)
r = generate(1297)
n = p * q * r

phi = (p-1) * (q-1) * (r-1)
assert gcd(phi , e) == 1
d = invert(e , phi)

m = bytes_to_long(secret)
c = pow(m ,e , n)

print('n =' , n)
print('c =' , c)
print('r =' , r)
print(pow(d , e , n))


#n = 40922607845571974639094308742839206224146242389200435546826449471547649318068202214315052746164700327884669920807873877153302365891057342964514972877830721839970583360181044952369529567877302250138627214156134324273006643743832782064762132241047824323326123112192584240095197926174334750362517226526895187416227397380891562008947088379640163835124837990827356906632844228753638684872217058005131262474768812560438298637695988660070178861609979328159041878343033363917985727840578526808892108373956636957114175952508811309317306118491533574932356699953256247834452547959548582730790458569189430889763614562381519010410402538498577496011072255925614032581014922736616684083563289722400846219599806133230800588239147160296752730116141191660418633382192636140044298733658684284938485029286103007107468609777892180250933472775790364225946138197236365379495695466008946936792522060717058044119933541902711163141980459067895658615062695484187688189996012075196840428862584331863913156531842723169921683221419730779
#c = 16676601131640655901342475969601337427286047597894727986067634116374589317621488654936562674556939585073850506354311834188829167562314091530089729249241688846569843558050420213958740311495135405543058339072725568714794743716386272697451778782821412367266489621066033418919772438167447846823060498863512632501986187983681481596348645501898397496124518261389750934408610820155987555796538021543359578003516813238600102768032404674440745599008436141834047379385255425272931290260904247882222634163480612880777600472827370294704757732130709966916443072347694301981918818620790654070949303144137945575568957467973992949730723090235277308941670839844509297374785398835235141122711766038463688262284420990305596960213756532391745361750898410276253711347610603772566889503001086791753760157250537857744447020338598500236461014133988456123805771079149267109142498336132221781737705105764070319353600566896855117027707381557563329857414974839310224902928169034177606817293688819170102103063041402067687398857611223462
#r = 1951216713210018899072913679877701984078605632816373140227957101795900768239459107199874527189474823683383498008030776033549165133365653412351458620727235480453823134172160962540008901165017593735888357448256342395844179252479046810866700841754419223240634425419941442213721047770479637605796828670180505163496149394679917056738825503018637176104418635597247740210544365148128056698191028571
#8310794526722831422025862174782419467814572143076434807348959394543712375769358046893867668084816009827666871252046250502451022247234160334735565602425204559045395593077102172207134933653174076554848866377062913033297398670128178741693276180212787995705792487024509194814961992282104341794192635824703991272313169555841845797451689247134611047656314757778140969122487234324858755963613738964977785225064012943722300767038694060309596438021657190082884494828180991225519268103496277082496776375417914617430941621234906625836888763117628925401803514478708592440089100844931175896263835556884776144952649237993043351606175711382730866878599470601660002715546011453356093999160898493128506112688531655531176100426473426696420351337216970070733591918418387370199614148316519366419200524903876915224232772089364428318748335704360010034537030492937111459811332811905071689712704884979478752829387806305614976609708077805372670232810255758846635821864952554944100289923658545086911236237627781057825840037501334429

n由三个素数构成，其中r已经给出，于是又

e*d = 1 mod phi即 e*d = 1 + k*phi，其中k恒为2，可以得到e*d = 1+2*(p-1)*(q-1)*(r-1),化简后有

e*d = 1+K(N-s+1)其中K = 2*(r-1),N = p*q,s = p+q，此时已经将其转换成了单元多项式，且其中的根s很小(1024位)

由于给出了d^e mod n 我们很容易计算(e*d)^e mod n 此时我们得到了一个多项式 f(x) = (1+K(N-x+1))^e -C其中C = (e*d)^e mod n,使用最终脚本如下：

from Crypto.Util.number import *
n = 40922607845571974639094308742839206224146242389200435546826449471547649318068202214315052746164700327884669920807873877153302365891057342964514972877830721839970583360181044952369529567877302250138627214156134324273006643743832782064762132241047824323326123112192584240095197926174334750362517226526895187416227397380891562008947088379640163835124837990827356906632844228753638684872217058005131262474768812560438298637695988660070178861609979328159041878343033363917985727840578526808892108373956636957114175952508811309317306118491533574932356699953256247834452547959548582730790458569189430889763614562381519010410402538498577496011072255925614032581014922736616684083563289722400846219599806133230800588239147160296752730116141191660418633382192636140044298733658684284938485029286103007107468609777892180250933472775790364225946138197236365379495695466008946936792522060717058044119933541902711163141980459067895658615062695484187688189996012075196840428862584331863913156531842723169921683221419730779
c = 16676601131640655901342475969601337427286047597894727986067634116374589317621488654936562674556939585073850506354311834188829167562314091530089729249241688846569843558050420213958740311495135405543058339072725568714794743716386272697451778782821412367266489621066033418919772438167447846823060498863512632501986187983681481596348645501898397496124518261389750934408610820155987555796538021543359578003516813238600102768032404674440745599008436141834047379385255425272931290260904247882222634163480612880777600472827370294704757732130709966916443072347694301981918818620790654070949303144137945575568957467973992949730723090235277308941670839844509297374785398835235141122711766038463688262284420990305596960213756532391745361750898410276253711347610603772566889503001086791753760157250537857744447020338598500236461014133988456123805771079149267109142498336132221781737705105764070319353600566896855117027707381557563329857414974839310224902928169034177606817293688819170102103063041402067687398857611223462
r = 1951216713210018899072913679877701984078605632816373140227957101795900768239459107199874527189474823683383498008030776033549165133365653412351458620727235480453823134172160962540008901165017593735888357448256342395844179252479046810866700841754419223240634425419941442213721047770479637605796828670180505163496149394679917056738825503018637176104418635597247740210544365148128056698191028571
t = 8310794526722831422025862174782419467814572143076434807348959394543712375769358046893867668084816009827666871252046250502451022247234160334735565602425204559045395593077102172207134933653174076554848866377062913033297398670128178741693276180212787995705792487024509194814961992282104341794192635824703991272313169555841845797451689247134611047656314757778140969122487234324858755963613738964977785225064012943722300767038694060309596438021657190082884494828180991225519268103496277082496776375417914617430941621234906625836888763117628925401803514478708592440089100844931175896263835556884776144952649237993043351606175711382730866878599470601660002715546011453356093999160898493128506112688531655531176100426473426696420351337216970070733591918418387370199614148316519366419200524903876915224232772089364428318748335704360010034537030492937111459811332811905071689712704884979478752829387806305614976609708077805372670232810255758846635821864952554944100289923658545086911236237627781057825840037501334429
k = 2*(r-1)
e = 3
PR.<x> = PolynomialRing(Zmod(n))
left = (t*27)%n
N = n//r
f = (1+k*(N-x+1))^e - left
print(f.monic().small_roots(X=2^1025,beta=1,epsilon = 0.04))

求得x == p+q后解二次方程得到p,q最终可以得到结果。

 

参考链接

crack_lcg

strange_lsb

nsucrypto

LLL and RSA