2024 蜀道山 crypto-wp
xorsa
from Crypto.Util.number import *
from gmpy2 import *
import uuid
flag='LZSDS{'+str(uuid.uuid4())+'}'
while True:
p=getPrime(512)
if p.bit_length()==512:
break
mask=??????
q=p^mask
hint1=p^q
hint2=q
n=p*q
e=2026
m=bytes_to_long(flag.encode())
c=pow(m,e,n)
print("c =",c)
print("n =",n)
print("hint1 =",hint1)
print("hint2 =",hint2)
'''
c = 13760578729891127041098229431259961120216468948795732373975536417751222443069805775693845560005881981622202089883866395577154701229046245882282127054969114210307175116574178428823043817041956207503299220721042136515863979655578210499512044917781566303947681251248645504273995402630701480590505840473412765662
n = 14247038211821385209759067256846232227444163173099199085257790370590450749665206556163364754269182255358084948354345827898987234756662133974633117062902370811855466665351784027125333112663075085395676501121759786699720149098576433141817737564928779420725539793335830274229206316999461309927000523188222801659
hint1 = 8938538619961731399716016665470564084986243880394928918482374295814509353382364651201249532111268951793354572124324033902502588541297713297622432670722730
hint2 = 1493298155243474837320092849325750387759519643879388609208314494000605554020636706320849032906759121914762492378489852575583260177546578935320977613050647
'''
一道经典的e和phi不互素
import gmpy2
import libnum
c = 13760578729891127041098229431259961120216468948795732373975536417751222443069805775693845560005881981622202089883866395577154701229046245882282127054969114210307175116574178428823043817041956207503299220721042136515863979655578210499512044917781566303947681251248645504273995402630701480590505840473412765662
n = 14247038211821385209759067256846232227444163173099199085257790370590450749665206556163364754269182255358084948354345827898987234756662133974633117062902370811855466665351784027125333112663075085395676501121759786699720149098576433141817737564928779420725539793335830274229206316999461309927000523188222801659
hint1 = 8938538619961731399716016665470564084986243880394928918482374295814509353382364651201249532111268951793354572124324033902502588541297713297622432670722730
p = 1493298155243474837320092849325750387759519643879388609208314494000605554020636706320849032906759121914762492378489852575583260177546578935320977613050647
q=n//p
e=2026
n = p * q
phi = (p - 1) * (q - 1)
_gcd = gmpy2.gcd(e, phi)
d = gmpy2.invert(e // _gcd, phi)
m_gcd = gmpy2.powmod(c, d, n)
m = gmpy2.iroot(m_gcd, _gcd)
flag = libnum.n2s(int(m[0]))
print(flag)
Something like coppersmith
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import hashlib
from secret import flag
p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
g = 37
x = getRandomRange(1, p)
key = hashlib.md5(str(x).encode()).digest()
aes = AES.new(key=key, mode=AES.MODE_ECB)
print(f"y = {pow(g, x, p)}")
print(f"xl = {x & (2**404 - 1)}")
print(f"enc = {aes.encrypt(pad(flag, 16))}")
"""
y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376
enc = b'\x08[\x94\xc1\xc2\xc3\xb9"C^\xd6P\xf9\x0c\xbb\r\r\xaf&\x94\x8cm\x02s\x87\x8b\x1c\xb3\x92\x81H\xe7\xc6\x190a\xca\x91j\xc0@(\xc5Fw\x95\r\xee'
"""
本题给出了ygp和x的低404位
题目名字交类coppersmith
很明显要用到sage来爆破
应为x是小于p的，所以我们分解以下p试试，分解不了，尝试p-1
发现有几个因子相乘后的位数加上404接近p的位数，之后小范围爆破一下即可
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
from sage.all import *
encrypted_data = b'\x08[\x94\xc1\xc2\xc3\xb9"C^\xd6P\xf9\x0c\xbb\r\r\xaf&\x94\x8cm\x02s\x87\x8b\x1c\xb3\x92\x81H\xe7\xc6\x190a\xca\x91j\xc0@(\xc5Fw\x95\r\xee'
g = 37
p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376
tt1, tt2, tt3 = 193166780451443059, 3881671740574461385603964379125531, 77364837756797328321829387679372821139010103152781295726133301368685957
tt = tt1 * tt2 * tt3
Fp = GF(p)
dlp = discrete_log(Fp(pow(y, tt, p)), Fp(pow(g, tt, p)), operation="*", ord=(p - 1) // tt)
x = crt([xl, dlp], [2**404, (p - 1) // tt])
for i in range(2**10):
candidate = x + i * lcm([2**404, (p - 1) // tt])
if (candidate > p - 1):
break
key = hashlib.md5(str(candidate).encode()).digest()
aes = AES.new(key=key, mode=AES.MODE_ECB)
print(aes.decrypt(encrypted_data))
签到!?
import hashlib
import gmpy2
from Crypto.Util.number import *
flag = b''
m = bytes_to_long(flag)
a = getPrime(1024);b = getPrime(1024);c = getPrime(1024);d = getPrime(128);n = getPrime(1024)
y = 0
for i in range(n+1):
x = a*i+b
y += (x//c)*i
if isPrime(y):
pass
else:
y = gmpy2.next_prime(y)
tmp = hashlib.md5(str(y).encode()).hexdigest()
cc = pow(d,int(tmp,16),n)
e = 52595
c3 = pow(m,e,y)
c4 = pow(a*m+b,e,y)
print('a =',a)
print('b =',b)
print('c =',c)
print('d =',d)
print('n =',n)
print('cc =',cc)
print('c3 =',c3)
print('c4 =',c4)
# a = 111406501658261575231314234156049408466629183228824951940397996549233343837444378602865612803520661162092930300450227752136992834681100817745708350750328806415942948297139334928206997684336812509277385194519252428443612078118898709910123899406877252165189871184174372173644257644751683554571917518602985248103
# b = 105754676330138681072874983469472331489357433467464632569519728162042635815478944541148477139634812590504509864018789141646023167940434519693396156652820504954321975234632684842726055170039476517204102162821838097200563406354332901840869790790015364563201564244853988381159598703692897790765599565893345380553
# c = 170600113386807592462858319531540617567133570960670217596634485327958954420566724690918464046407772634147753234450737353193173923873879958589824005123545638184186453602233634037809629812111243183450002707175703333920828461245731172668838771751457387207779427008047454548463398397079552688864699792002976130047
# d = 229823065384822950015724955215847476631
# n = 169428502732446427714165121824913735747920403586738853921495983139840483604966163669399379093896888954652663456556496947292418676356981468237136780175047349167561875551277606897449804926885192045760368051311243166090981061101913245493065268528634952461907634111084108803207099139506693313918834075542826388183
# cc = 105324189115602620621800798531371526317853537119154266873657796691360779628410005302892575043351618666760506544724245300953227618282253336044824499240524905915476071538182232622771476344880513465689824790881603214009332398038930113198889292160815386819010434380814610557831376377280232817587639852364108539892
# c3 = 791801877941025556812260671377895956461402542450910806211264471681160334454968210834058573374802678147030803278793623022600774676606263064237697305258809520983007689647782562591531551137322198839457388757360504835352506363286012791482381915207800512880078672338934869429374580298570299136345411005736381918329554791587303420005844148692211002120828912548145333101329366616120459060822278273689238720580513363138874807500470690610311215233669314430430554144017703130663205211791135140813550629558977548476426876112982216083736966681702987597722820852894624586687261277977164491919429492650781084296080288020330875247574855906390404509845311187888602482142661083771230000178356724801659025002251056321173755782500071361114235931347064100961296562902176010402092225439511324625249209554560052627349307173707304259200397468217911136832133364420684914378754649851955359890480612161233059263522713390654506714661592991514955637304
# c4 = 101923921400007092267790478161024103799892954880859052793422615329222813129835333442478632220182544724530301816393072530672763263645022408189547815923383906565611606888926097135400527299006862907781058931838804887994883095683814203452663467235776407572822082944022133476409878374663555627258035317631489173719410785629090255417861686081571376756906799938593870745471956936393066774907988124411318124604178920755698887086399177650502004883860844187365911953472980921213184639411672503691612418437276530896198002610276732906004741692286470538565288852344158830229580771834123582320782258698392853262935944858898937999647004599668060425461150846652642931397311468425476235056756761805933421643525566845928057238991458469113290576159465234243274971982913939709869951907061169493132309863852016682533998299893705859834844325876890511405664336001308600133946440998690503095156964687645597227368993047211862703399858777949126471093
类欧几里得算法加多项式欧几里得算法
先求y
from Crypto.Util.number import *
import hashlib
import gmpy2
def f(a,b,c,N):
if(a == 0):
return (N+1)*(b//c)
elif(a >= c or b >= c):
return (N*(N+1)//2)*(a//c) + (N+1)*(b//c) + f(a%c, b%c, c, N)
else:
M = (a*N+b)//c
return N*M - f(c, c-b-1, a, M-1)
def g(a,b,c,N):
if(a == 0):
return (N+1)*(b//c)^2
elif(a >= c or b >= c):
return g(a%c, b%c, c, N) + 2*(a//c)*h(a%c, b%c, c, N) + 2*(b//c)*f(a%c, b%c, c, N) +\
(N*(N+1)*(2*N+1)//6)*(a//c)^2 + N*(N+1)*(a//c)*(b//c) + (N+1)*(b//c)^2
else:
M = (a*N+b)//c
return N*M*(M+1) - f(a, b, c, N) - 2*h(c, c-b-1, a, M-1) - 2*f(c, c-b-1, a, M-1)
def h(a,b,c,N):
if(a == 0):
return (N*(N+1)//2)*(b//c)
elif(a >= c or b >= c):
return h(a%c, b%c, c, N) + (N*(N+1)*(2*N+1)//6)*(a//c) + (N*(N+1)//2)*(b//c)
else:
M = (a*N+b)//c
return (M*N*(N+1) - g(c, c-b-1, a, M-1) - f(c, c-b-1, a, M-1))//2
def calc(a, b, c, N):
F, G, H = 0, 0, 0
if(a == 0):
F = (N+1)*(b//c)
G = (N+1)*(b//c)^2
H = (N*(N+1)//2)*(b//c)
elif(a >= c or b >= c):
ff, gg, hh = calc(a%c, b%c, c, N)
F = (N*(N+1)//2)*(a//c) + (N+1)*(b//c) + ff
G = gg + 2*(a//c)*hh + 2*(b//c)*ff +\
(N*(N+1)*(2*N+1)//6)*(a//c)^2 + N*(N+1)*(a//c)*(b//c) + (N+1)*(b//c)^2
H = hh + (N*(N+1)*(2*N+1)//6)*(a//c) + (N*(N+1)//2)*(b//c)
else:
M = (a*N+b)//c
ff, gg, hh = calc(c, c-b-1, a, M-1)
F = N*M - ff
G = N*M*(M+1) - f(a, b, c, N) - 2*hh - 2*ff
H = (M*N*(N+1) - gg - ff)//2
return [F, G, H]
a = 111406501658261575231314234156049408466629183228824951940397996549233343837444378602865612803520661162092930300450227752136992834681100817745708350750328806415942948297139334928206997684336812509277385194519252428443612078118898709910123899406877252165189871184174372173644257644751683554571917518602985248103
b = 105754676330138681072874983469472331489357433467464632569519728162042635815478944541148477139634812590504509864018789141646023167940434519693396156652820504954321975234632684842726055170039476517204102162821838097200563406354332901840869790790015364563201564244853988381159598703692897790765599565893345380553
c = 170600113386807592462858319531540617567133570960670217596634485327958954420566724690918464046407772634147753234450737353193173923873879958589824005123545638184186453602233634037809629812111243183450002707175703333920828461245731172668838771751457387207779427008047454548463398397079552688864699792002976130047
d = 229823065384822950015724955215847476631
n = 169428502732446427714165121824913735747920403586738853921495983139840483604966163669399379093896888954652663456556496947292418676356981468237136780175047349167561875551277606897449804926885192045760368051311243166090981061101913245493065268528634952461907634111084108803207099139506693313918834075542826388183
cc = 105324189115602620621800798531371526317853537119154266873657796691360779628410005302892575043351618666760506544724245300953227618282253336044824499240524905915476071538182232622771476344880513465689824790881603214009332398038930113198889292160815386819010434380814610557831376377280232817587639852364108539892
c3 = 791801877941025556812260671377895956461402542450910806211264471681160334454968210834058573374802678147030803278793623022600774676606263064237697305258809520983007689647782562591531551137322198839457388757360504835352506363286012791482381915207800512880078672338934869429374580298570299136345411005736381918329554791587303420005844148692211002120828912548145333101329366616120459060822278273689238720580513363138874807500470690610311215233669314430430554144017703130663205211791135140813550629558977548476426876112982216083736966681702987597722820852894624586687261277977164491919429492650781084296080288020330875247574855906390404509845311187888602482142661083771230000178356724801659025002251056321173755782500071361114235931347064100961296562902176010402092225439511324625249209554560052627349307173707304259200397468217911136832133364420684914378754649851955359890480612161233059263522713390654506714661592991514955637304
c4 = 101923921400007092267790478161024103799892954880859052793422615329222813129835333442478632220182544724530301816393072530672763263645022408189547815923383906565611606888926097135400527299006862907781058931838804887994883095683814203452663467235776407572822082944022133476409878374663555627258035317631489173719410785629090255417861686081571376756906799938593870745471956936393066774907988124411318124604178920755698887086399177650502004883860844187365911953472980921213184639411672503691612418437276530896198002610276732906004741692286470538565288852344158830229580771834123582320782258698392853262935944858898937999647004599668060425461150846652642931397311468425476235056756761805933421643525566845928057238991458469113290576159465234243274971982913939709869951907061169493132309863852016682533998299893705859834844325876890511405664336001308600133946440998690503095156964687645597227368993047211862703399858777949126471093
y = calc(a,b,c,n)[2]
if isPrime(y):
pass
else:
y = gmpy2.next_prime(y)
print(y)
half-gcd
from Crypto.Util.number import *
import sys
def HGCD(a, b):
if 2 * b.degree() <= a.degree() or a.degree() == 1:
return 1, 0, 0, 1
m = a.degree() // 2
a_top, a_bot = a.quo_rem(x^m)
b_top, b_bot = b.quo_rem(x^m)
R00, R01, R10, R11 = HGCD(a_top, b_top)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
q, e = c.quo_rem(d)
d_top, d_bot = d.quo_rem(x^(m // 2))
e_top, e_bot = e.quo_rem(x^(m // 2))
S00, S01, S10, S11 = HGCD(d_top, e_top)
RET00 = S01 * R00 + (S00 - q * S01) * R10
RET01 = S01 * R01 + (S00 - q * S01) * R11
RET10 = S11 * R00 + (S10 - q * S11) * R10
RET11 = S11 * R01 + (S10 - q * S11) * R11
return RET00, RET01, RET10, RET11
def GCD(a, b):
print(a.degree(), b.degree())
q, r = a.quo_rem(b)
if r == 0:
return b
R00, R01, R10, R11 = HGCD(a, b)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
if d == 0:
return c.monic()
q, r = c.quo_rem(d)
if r == 0:
return d
return GCD(d, r)
sys.setrecursionlimit(500000)
y=1058691400650411107338563871293034249253757519724937258393060987487332260147460138473533532509357188557547254962698109960245427354184885781590338193358890025040339639579292088032213906061999224135871760070447152982296671303650810623208882800555352227585253208789508990897236956635228597520993270350780770107693925922466603798038839165456678217318233228389699190137491433213120560655703957159536212187563081152988284398583474911873534286347956423011502671880752013241978165468524688913251118311129214272828861103088872973848958582916317827669887290868460213045051274271425061716061148875982337430904752172290777445126869367531723361731961139243123555237304279553720727399012312205448445243128530507464750031280471957962143184387929209372126891106882649827918707061158976650202867203551134867043636515934927110651530796378200820757129067901845685987688631831351951997029672350127306564880564997200097204669137936287009502711397
e=52595
c3 = 791801877941025556812260671377895956461402542450910806211264471681160334454968210834058573374802678147030803278793623022600774676606263064237697305258809520983007689647782562591531551137322198839457388757360504835352506363286012791482381915207800512880078672338934869429374580298570299136345411005736381918329554791587303420005844148692211002120828912548145333101329366616120459060822278273689238720580513363138874807500470690610311215233669314430430554144017703130663205211791135140813550629558977548476426876112982216083736966681702987597722820852894624586687261277977164491919429492650781084296080288020330875247574855906390404509845311187888602482142661083771230000178356724801659025002251056321173755782500071361114235931347064100961296562902176010402092225439511324625249209554560052627349307173707304259200397468217911136832133364420684914378754649851955359890480612161233059263522713390654506714661592991514955637304
c4 = 101923921400007092267790478161024103799892954880859052793422615329222813129835333442478632220182544724530301816393072530672763263645022408189547815923383906565611606888926097135400527299006862907781058931838804887994883095683814203452663467235776407572822082944022133476409878374663555627258035317631489173719410785629090255417861686081571376756906799938593870745471956936393066774907988124411318124604178920755698887086399177650502004883860844187365911953472980921213184639411672503691612418437276530896198002610276732906004741692286470538565288852344158830229580771834123582320782258698392853262935944858898937999647004599668060425461150846652642931397311468425476235056756761805933421643525566845928057238991458469113290576159465234243274971982913939709869951907061169493132309863852016682533998299893705859834844325876890511405664336001308600133946440998690503095156964687645597227368993047211862703399858777949126471093
a = 111406501658261575231314234156049408466629183228824951940397996549233343837444378602865612803520661162092930300450227752136992834681100817745708350750328806415942948297139334928206997684336812509277385194519252428443612078118898709910123899406877252165189871184174372173644257644751683554571917518602985248103
b = 105754676330138681072874983469472331489357433467464632569519728162042635815478944541148477139634812590504509864018789141646023167940434519693396156652820504954321975234632684842726055170039476517204102162821838097200563406354332901840869790790015364563201564244853988381159598703692897790765599565893345380553
R.<x> = PolynomialRing(Zmod(y))
f = x^e - c3
g = (a*x+b)^e - c4
res = GCD(f,g)
m = -res.monic().coefficients()[0]
print(m)
flag = long_to_bytes(int(m))
print(flag)
tips这道题出题有一个漏洞，我们发现e和y-1互素，将y当作单质数，发现可以更快解出本题
转载
分享
0 条评论
可输入 255 字
发布投稿
