ezrsa

from Crypto.Util.number import *

c= 11850797596095451670524864488046085367812828367468720385501401042627802035427938560866042101544712923470757782908521283827297125349504897418356898752774318846698532487439368216818306352553082800908866174488983776084101115047054799618258909847935672497139557595959270012943240666681053544905262111921321629682394432293381001209674417203517322559283298774214341100975920287314509947562597521988516473281739331823626676843441511662000240327706777269733836703945274332346982187104319993337626265180132608256601473051048047584429295402047392826197446200263357260338332947498385907066370674323324146485465822881995994908925
n= 21318014445451076173373282785176305352774631352746325570797607376133429388430074045541507180590869533728841479322829078527002230672051057531691634445544608584952008820389785877589775003311007782211153558201413379523215950193011250189319461422835303446888969202767656215090179505169679429932715040614611462819788222032915253996376941436179412296039698843901058781175173984980266474602529294294210502556931214075073722598225683528873417278644194278806584861250188304944748756498325965302770207316134309941501186831407953950259399116931502886169434888276069750811498361059787371599929532460624327554481179566565183721777
p_bq= 4780454330598494796755521994676122817049316484524449315904838558624282970709853419493322324981097593808974378840031638879097938241801612033487018497098140216369858849215655128326752931937595077084912993941304190099338282258345677248403566469008681644014648936628917169410836177868780315684341713654307395687505633335014603359767330561537038768638735748918661640474253502491969012573691915259958624247097465484616897537609020908205710563729989781151998857899164730749018285034659826333237729626543828084565456402192248651439973664388584573568717209037035304656129544659938260424175198672402598017357232325892636389317
ap_q= 9819969459625593669601382899520076842920503183309309803192703938113310555315820609668682700395783456748733586303741807720797250273398269491111457242928322099763695038354042594669354762377904219084248848357721789542296806917415858628166620939519882488036571575584114090978113723733730014540463867922496336721404035184980539976055043268531950537390688608145163366927155216880223837210005451630289274909202545128326823263729300705064272989684160839861214962848466991460734691634724996390718260697593087126527364129385260181297994656537605275019190025309958225118922301122440260517901900886521746387796688737094737637604
jie=2
for i in range(2^jie):
    for j in range(2^jie):
        L = Matrix(ZZ, [
            [1,0,0,2^jie*p_bq],
            [0,1,0,2^jie*ap_q],
            [0,0,2^(1024-jie),p_bq*i+ap_q*j-p_bq*ap_q],
            [0,0,0,n3]
        ])
        L[:,-1:] *= n3
        res = L.LLL()[0]

        p = 2^jie*abs(res[0])+i
        if(n3 % p == 0):
            print(p)
p=124189847121659504689131596141558047777470804493599644420296555116734410602128548952870025238352452050389498094816555251171494633173056599030097009589059426642394227134903947124256903019712657426771434047124620967038284130366066946770546558623405351933778765398347798146994796514331421532950278418230985309907
q=n//p
e=0x10001
d=pow(e,-1,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(m))

flag{3z_r5a_15_r34lly_345y_w1sh_u_c0uld_g3t_f14g}

tArScR

参考论文 New Attacks on RSA with Small Secret CRT-Exponents

https://www.iacr.org/archive/pkc2006/39580001/39580001.pdf

from copy import deepcopy
from Crypto.Util.number import *

mod_N = 61857467041120006957454494977971762866359211220721592255304580940306873708357617802596067329984189345493420858543581027612648626678588277060222860337783377316655375278359169520243355170247177279595812282793212550819124960549824278287538977769728573023023364686725321548391592858202718446127851076431000427033
exp_e = 22696852369762746127523066296087974245933137295782964284054040654103039210164173227291367914580709029582944005335464668969366909190396194570924426653294883884186299265660358589254391341147028477295482787041170991166896788171334992065199814524969470117229229967188623636764051681654720429531708441920158042161
alpha_val = log(exp_e, mod_N)
beta_val = 0.30  
delta_val = 0.10

PolyRing.<X_var, Y_var, Z_var> = PolynomialRing(ZZ)

X_const = ceil(2 * mod_N^(alpha_val + beta_val + delta_val - 1)) 
Y_const = ceil(2 * mod_N^beta_val)
Z_const = ceil(2 * mod_N^(1 - beta_val))

def func_f(X_var, Y_var):
    return X_var * (mod_N - Y_var) + mod_N

def transform_func(f_poly):
    exp_tuples = f_poly.exponents(as_ETuples=False)
    poly_g = 0
    for exp_tuple in exp_tuples:
        power_list = list(exp_tuple)
        monom = X_var ^ power_list[0] * Y_var ^ power_list[1] * Z_var ^ power_list[2]
        coeff_tmp = f_poly.monomial_coefficient(monom)
        min_power = min(power_list[1], power_list[2])
        power_list[1] -= min_power
        power_list[2] -= min_power
        coeff_tmp *= mod_N ^ min_power
        coeff_tmp *= X_var ^ power_list[0] * Y_var ^ power_list[1] * Z_var ^ power_list[2]
        poly_g += coeff_tmp
    return poly_g

deg_m = 5
tau_val = ((1 - beta_val) ^ 2 - delta_val) / (2 * beta_val * (1 - beta_val))
sigma_val = (1 - beta_val - delta_val) / (2 * (1 - beta_val))

s_val = ceil(sigma_val * deg_m)
t_val = ceil(tau_val * deg_m)

poly_list = []
for i in range(deg_m + 1):
    for j in range(deg_m - i + 1):
        poly_gij = transform_func(exp_e ^ (deg_m - i) * X_var ^ j * Z_var ^ s_val * func_f(X_var, Y_var) ^ i)
        poly_list.append(poly_gij)

for i in range(deg_m + 1):
    for j in range(1, t_val + 1):
        poly_hij = transform_func(exp_e ^ (deg_m - i) * Y_var ^ j * Z_var ^ s_val * func_f(X_var, Y_var) ^ i)
        poly_list.append(poly_hij)

known_terms = set()
transformed_polys = []
basis_monomials = []

while poly_list:
    for idx in range(len(poly_list)):
        poly_f = poly_list[idx]
        curr_monomials = set(X_var ^ tx * Y_var ^ ty * Z_var ^ tz for tx, ty, tz in poly_f.exponents(as_ETuples=False))
        delta_terms = curr_monomials - known_terms
        if len(delta_terms) == 1:
            new_basis_term = list(delta_terms)[0]
            basis_monomials.append(new_basis_term)
            known_terms |= curr_monomials
            transformed_polys.append(poly_f)
            poly_list.pop(idx)
            break
    else:
        raise Exception('No unique monomial found')

poly_list = deepcopy(transformed_polys)

num_rows = len(poly_list)
num_cols = len(basis_monomials)
L_matrix = [[0 for _ in range(num_cols)] for _ in range(num_rows)]

for i in range(num_rows):
    scaled_poly = poly_list[i](X_const * X_var, Y_const * Y_var, Z_const * Z_var)
    for j in range(num_cols):
        L_matrix[i][j] = scaled_poly.monomial_coefficient(basis_monomials[j])

for i in range(num_rows):
    diag_elem = L_matrix[i][i]
    power_N = 1
    while diag_elem % mod_N == 0:
        power_N *= mod_N
        diag_elem //= mod_N
    L_matrix[i][i] = diag_elem
    for j in range(num_cols):
        if j != i:
            L_matrix[i][j] = (L_matrix[i][j] * inverse_mod(power_N, exp_e ^ deg_m))

L_matrix = Matrix(ZZ, L_matrix)
num_rows = L_matrix.nrows()
L_matrix = L_matrix.LLL()

reduced_polys = []
for i in range(num_rows):
    poly_gl = 0
    for j in range(num_cols):
        poly_gl += L_matrix[i][j] // basis_monomials[j](X_const, Y_const, Z_const) * basis_monomials[j]
    reduced_polys.append(poly_gl)

ideal_list = [Y_var * Z_var - mod_N] + reduced_polys
ideal_list = [ideal.change_ring(QQ) for ideal in ideal_list]

for i in range(len(ideal_list), 3, -1):
    sol_set = Ideal(ideal_list[:i]).variety(ring=ZZ)
print(sol_set)

得到结果后将Y_var作为n的因子解rsa即可。

c = 41862679760722981662840433621129671566139143933210627878095169470855743742734397276638345217059912784871301273620533442249011607182329472311453700434692358352210197988000738272869600692181834281813995048665466937302183039555350612260646428575598237960405962714063137455677605629008760761743568236135324015278
p = 144996003362760405215910388196517232449311004246441924325936847006315296003811348342536838359
q = N // p
fn=(p-1)*(q-1)
d = pow(e, -1, fn)
m = pow(c, d, N)
print(long_to_bytes(int(m)))

babyenc

本题flag分为两部分

第一部分

c[i]=pow(tmp,e[i],n),已知c[i] and e[i]

已知n = next_prime(m << shift)

现在想要求flag1就要求出m1，要解m1要先解n

之后将n小范围爆破再向右移动shift位

from Crypto.Util.number import *
e = [43, 37, 53, 61, 59]
import gmpy2
c1 = [304054249108643319766233669970696347228113825299195899223597844657873869914715629219753150469421333712176994329969288126081851180518874300706117, 300569071066351295347178153438463983525013294497692191767264949606466706307039662858235919677939911290402362961043621463108147721176372907055224, 294806502799305839692215402958402593834563343055375943948669528217549597192296955202812118864208602813754722206211899285974414703769561292993531, 255660645085871679396238463457546909716172735210300668843127008526613931533718130479441396195102817055073131304413673178641069323813780056896835, 194084621856364235027333699558487834531380222896709707444060960982448111129722327145131992393643001072221754440877491070115199839112376948773978]
x1=pow(c1[0],37)-pow(c1[1],43)
x2=pow(c1[2],61)-pow(c1[3],53)
n=gmpy2.gcd(x1,x2)
print(n)
n=312246073793634738336797238973383686069608357320504281244915809376146746877615304143136570336999218383069369602336776078145547720220248077500917
for i in range(-2000,2000):
    num=n-i
    m=num>>310
    flag=long_to_bytes(m)
    if b'flag'  in flag:
        print(flag)
        break

第二部分：已知n , c2=[c1,c2]

$$
c1=m^p(modn),c2=m^q(modn)\所以c1=m(modp),c2=m(modq)\c1=m+k1p,c2=m+k2q\c1c2=m^2+(k2q+k1p)m(modn)\将c1=m+k1p,c2=m+k2q代入:\c1c2=m^2+(c2-m+c1-m)m(modn)
$$

from Crypto.Util.number import *
n = 16175064088648626038689748434699435826247716579187475966092822028609536761351820951820375552440329596553448265674841223230257463367834546091974959931391707199002842774795702094681528411058318007858638798643010942408552063479863545047616823056802010158288409527763686086960916160949496083789920012040215745627854092010308869223489833074860062054019221397227691063339148923860987250696934050122115972982286012688955816234717242567815830341836031567275888691320640526306946586793028267588302696611724356566003447616419092371914903382944112125852939011729294400479171568234647164730191643282793224422368321464125847020067
c2 = [12053085469218650692076937068797478047679005585690696222988148891925249697123080938461512785257424651119325211991331622346111396522606463631848519999574540677285771456451798811902760319940781754940936484802949729402283626052963389539032949160905330315285409948932070460455535716223838438994608837585387741418172014634472651248450564788332400265295308803291229281839428962457585593065595521459963501453576128172245723315811398209056633738967993602668795794847967331946516181453804430961308142497659799416125763566765485760600358126127595222197324155943818136202233758771243043559460620477085689770403810190118485243364, 13878717704635179949812987989626985689079485417345626168168664941124566737996226347895779823781042724620099437593856913505609774929187720381745418166924229828643565384137488017127800518133460531729559408120123922005898834268035918798610962941606864727966963354615441094676621013036726097763695675723672289505864372820096404707522755617527884121630784469379311199256277022770033036782130954108210409787680433301426480762532000133464370267551845990395683108170721952672388388178378604502610341465223041534665133155077544973384500983410220955683686526835733853985930134970899200234404716865462481142496209914197674463932]
cc1=c2[0]
cc2=c2[1]
PR.<m>=PolynomialRing(Zmod(n))
f=m^2+m*(cc2+cc1-2*m)-cc1*cc2
f=f.monic()
ret=f.small_roots(X=2^(200))
print(ret)
m2=146436625375651639081292195233290471195543268962429
print(long_to_bytes(int(m2)))

PolyPrime

参考文章https://tangcuxiaojikuai.xyz/post/6144f326.html

from Crypto.Util.number import *
n = 659401821142664131364043958430747314465977448744532421905138184036743766362324320051729418680079590835903781525157600055608268591994754328563246418114269690475272262915661210669701969695314157602927462228079044905276064391615467601628466982949165371933147600418057089432876120807721483665788557812323607370950442342057254926375842684430119320789097029996211564275310819486004520088130146630452262340185192110066151930586956190499953220051855668474863659201165952231016814569364299000130323859609047687714260776467149437031397019411599103716200258382231589757031469168245396061619327867355414287059363691024984066070128364157490336808211223714816668548049472199794493895870662970541167490686648385211854469386812214775829776376273299648505880034651930322294605482489225723014758138525637864689594748771025870209444029669477294995691067669374491852721622469656239730320092112222948718027850386898461208936333788173263904607181823233002355650353116486156927403178510412091666951574340730799316032588099237
c = 455042981325030540026829365098432813829591020497037525707600104817313008442900331256387443469027825344761381076471749826547710666806180999603254398722965179851898391700090501419875562919365894255855734276825027850795202733875071307773598881254863911398285400038957998385685292965812925607278232164067624548120378758414574370042945538632864154772437639053907149514588502689277630450575630168099810584842881257614115970132960679023265157277718654731105815060916800751033956715430930381384344469220951638102432198422350425390757155267143393385221465041749156153517556389417033187856017198907366720281408810250981776112815100319814215140919133440637395953567624057248002125277569474190364142291136361144552953540727462623677375371327473687508344483184466522697912317252462246054471196345909304668083637177166153036111122244170846815657389873986264187766636830907458940128844256504176917204131708083105093700023335939233711693409336968008112511482237441198116493965744903995545941700742865846469036763734618
e = 0x10001

k = 5
R = Zmod(n)["x"]
while True:
    Q = R.quo(R.random_element(k))
    p = gcd(ZZ(list(Q.random_element() ^ n)[1]), n)
    if p != 1:
        q = sum([p**i for i in range(k)])
        r = n // (p * q)
        assert n == p * q * r
        break
phi = (p - 1) * (q - 1) * (r - 1)
d = inverse(e,phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))