队友的WP:
Crypto#
数据处理#
task
from Crypto.Util.number import bytes_to_long
import random
flag = b"H&NCTF{}"
btl = str(bytes_to_long(flag))
lowercase = '0123456789'
uppercase = '7***4****5'
table = ''.maketrans(lowercase, uppercase)
new_flag = btl.translate(table)
n = 2 ** 512
m = random.randint(2, n - 1) | 1
c = pow(m, int(new_flag), n)
print('m = ' + str(m))
print('c = ' + str(c))
# m = 5084057673176634704877325918195984684237263100965172410645544705367004138917087081637515846739933954602106965103289595670550636402101057955537123475521383
# c = 2989443482952171039348896269189568991072039347099986172010150242445491605115276953489889364577445582220903996856271544149424805812495293211539024953331399DLP+爆破，懒得写代码，直接扔给AI写。
exp
from sage.all import *
m = 5084057673176634704877325918195984684237263100965172410645544705367004138917087081637515846739933954602106965103289595670550636402101057955537123475521383
c = 2989443482952171039348896269189568991072039347099986172010150242445491605115276953489889364577445582220903996856271544149424805812495293211539024953331399
n = 2**512
F = Zmod(n)
c = F(c)
m = F(m)
c.log(m)
new_flag_str = "3282248010524512146638712359816289396373430161050484501341123570760619381019795910712610762203934445754701"
from Crypto.Util.number import bytes_to_long, long_to_bytes
import itertools
lowercase = '0123456789'
masked = '7***4****5'
new_flag = "3282248010524512146638712359816289396373430161050484501341123570760619381019795910712610762203934445754701" # 请输入你已知的new_flag
known_map = {}
for i, char in enumerate(masked):
if char != '*':
known_map[lowercase[i]] = char
unknown = [i for i, char in enumerate(masked) if char == '*']
unknown_digits = [lowercase[i] for i in unknown]
known_digits = [masked[i] for i in range(10) if masked[i] != '*']
digits_cands = [d for d in '0123456789' if d not in known_digits]
permutations_cands = itertools.permutations(digits_cands, len(unknown))
for perm in permutations_cands:
curr_map = known_map.copy()
for i, pos in enumerate(unknown):
curr_map[lowercase[pos]] = perm[i]
btl_cand = ""
for char in new_flag:
for k, v in curr_map.items():
if v == char:
btl_cand += k
break
else:
btl_cand += char
try:
smp = int(btl_cand)
flag = long_to_bytes(smp)
if flag.startswith(b"H&NCTF{") and flag.endswith(b"}") and all(32 <= b <= 126 for b in flag):
print("🎉🎉🎉")
print(f"{flag.decode()}")
except:
continue
# 🎉🎉🎉
# H&NCTF{cut_cut_rrioajtfijrwegeriogjiireigji}ezfactor#
task
from Crypto.Util.number import *
import uuid
rbits = 248
Nbits = 1024
p = getPrime(Nbits // 2)
q = getPrime(Nbits // 2)
N = p * q
r = getPrime(rbits)
hint = getPrime(Nbits // 2) * p + r
R = 2^rbits
e=0x10001
n=p*q
phi=(p-1)*(q-1)
flag = b'H&NCTF{' + str(uuid.uuid4()).encode() + b'}'
m=bytes_to_long(flag)
c=pow(m,e,n)
print("N=",N)
print("hint=",hint)
print(c)
# N= 155296910351777777627285876776027672037304214686081903889658107735147953235249881743173605221986234177656859035013052546413190754332500394269777193023877978003355429490308124928931570682439681040003000706677272854316717486111569389104048561440718904998206734429111757045421158512642953817797000794436498517023
# hint= 128897771799394706729823046048701824275008016021807110909858536932196768365642942957519868584739269771824527061163774807292614556912712491005558619713483097387272219068456556103195796986984219731534200739471016634325466080225824620962675943991114643524066815621081841013085256358885072412548162291376467189508
# c=32491252910483344435013657252642812908631157928805388324401451221153787566144288668394161348411375877874802225033713208225889209706188963141818204000519335320453645771183991984871397145401449116355563131852618397832704991151874545202796217273448326885185155844071725702118012339804747838515195046843936285308
ACD问题。r看一眼就知道是个mod p的小根，只不过界卡得蛮紧的。Coppersmith调epsilon到0.01，再用flatter加速一下格规约，R5 5600x上也能30s内出答案。
exp
from sage.all import *
from re import findall
from subprocess import check_output
from Crypto.Util.number import *
def flatter(M):
# compile https://github.com/keeganryan/flatter and put it in $PATH
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = check_output(["flatter"], input=z.encode())
return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
def small_roots(self, X=None, beta=0.5, epsilon=None, **kwds):
from sage.misc.verbose import verbose
from sage.matrix.constructor import Matrix
from sage.rings.real_mpfr import RR
N = self.parent().characteristic()
if not self.is_monic():
raise ArithmeticError("Polynomial must be monic.")
beta = RR(beta)
if beta <= 0.0 or beta > 1.0:
raise ValueError("0.0 < beta <= 1.0 not satisfied.")
f = self.change_ring(ZZ)
P, (x,) = f.parent().objgens()
delta = f.degree()
if epsilon is None:
epsilon = beta / 8
verbose("epsilon = %f" % epsilon, level=2)
m = max(beta**2 / (delta * epsilon), 7 * beta / delta).ceil()
verbose("m = %d" % m, level=2)
t = int((delta * m * (1 / beta - 1)).floor())
verbose("t = %d" % t, level=2)
if X is None:
X = (0.5 * N ** (beta**2 / delta - epsilon)).ceil()
verbose("X = %s" % X, level=2)
# we could do this much faster, but this is a cheap step
# compared to LLL
g = [x**j * N ** (m - i) * f**i for i in range(m) for j in range(delta)]
g.extend([x**i * f**m for i in range(t)]) # h
B = Matrix(ZZ, len(g), delta * m + max(delta, t))
for i in range(B.nrows()):
for j in range(g[i].degree() + 1):
B[i, j] = g[i][j] * X**j
print("[+] Starting flatter...")
B = flatter(B)
# B = B.LLL()
f = sum([ZZ(B[0, i] // X**i) * x**i for i in range(B.ncols())])
R = f.roots()
ZmodN = self.base_ring()
roots = set([ZmodN(r) for r, m in R if abs(r) <= X])
Nbeta = N**beta
return [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]
N = 155296910351777777627285876776027672037304214686081903889658107735147953235249881743173605221986234177656859035013052546413190754332500394269777193023877978003355429490308124928931570682439681040003000706677272854316717486111569389104048561440718904998206734429111757045421158512642953817797000794436498517023
hint = 128897771799394706729823046048701824275008016021807110909858536932196768365642942957519868584739269771824527061163774807292614556912712491005558619713483097387272219068456556103195796986984219731534200739471016634325466080225824620962675943991114643524066815621081841013085256358885072412548162291376467189508
c = 32491252910483344435013657252642812908631157928805388324401451221153787566144288668394161348411375877874802225033713208225889209706188963141818204000519335320453645771183991984871397145401449116355563131852618397832704991151874545202796217273448326885185155844071725702118012339804747838515195046843936285308
e = 0x10001
R = 2**248
P = PolynomialRing(Zmod(N), "x")
x = P.gen()
# y + (hint - R) % p == 0
g = hint - x
g = g.monic()
roots = small_roots(g, X=R, beta=0.499, epsilon=0.01)
if roots:
y0 = roots[0]
r = int(y0)
print("Recovered r:", r)
if isPrime(int(r)):
print("r is prime.")
p = gcd(N, hint - r)
if p > 1 and p < N:
q = N // p
print("Recovered p:", p)
print("Recovered q:", q)
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, N)
flag = bytes.fromhex(hex(m)[2:])
print("Flag:", flag)
else:
print("Failed to factor N.")
else:
print("r is not prime.")
else:
print("No roots found. Adjust parameters or try different epsilon.")ezfactor-pro#
task
from Crypto.Util.number import *
from Crypto.Util.Padding import *
from gmssl.sm4 import CryptSM4, SM4_ENCRYPT
from hashlib import sha256
from random import *
import uuid
rbits = 252
Nbits = 1024
p = getPrime(Nbits//2)
q = getPrime(Nbits//2)
N = p*q
r = getPrime(rbits)
hint = getPrime(Nbits// 2)*p+r
R = 2^rbits
flag = b'H&NCTF{'+str(uuid.uuid4()).encode()+b'}'
leak=p*q*r
r_bytes = long_to_bytes(leak)
iv = r_bytes[:16] if len(r_bytes) >= 16 else r_bytes + b'\0'*(16-len(r_bytes))
key = sha256(str(p + q + r).encode()).digest()[:16]
crypt_sm4 = CryptSM4()
crypt_sm4.set_key(key, SM4_ENCRYPT)
padded_flag = pad(flag, 16)
c = crypt_sm4.crypt_cbc(iv, padded_flag)
print("N=",N)
print("hint=",hint)
print(c)
#N = 133196604547992363575584257705624404667968600447626367604523982016247386106677898877957513177151872429736948168642977575860754686097638795690422242542292618145151312000412007125887631130667228632902437183933840195380816196093162319293698836053406176957297330716990340998802156803899579713165154526610395279999
#hint = 88154421894117450591552142051149160480833170266148800195422578353703847455418496231944089437130332162458102290491849331143073163240148813116171275432632366729218612063176137204570648617681911344674042091585091104687596255488609263266272373788618920171331355912434290259151350333219719321509782517693267379786
#c = 476922b694c764725338cca99d99c7471ec448d6bf60de797eb7cc6e71253221035eb577075f9658ac7f1a40747778ac261787baad21ee567256872fa9400c37跟上一题不同的点在于界更大了点。爆破几个bits再去Coppersmith就好。
exp
from sage.all import *
from re import findall
from subprocess import check_output
from Crypto.Util.number import *
import time
def flatter(M):
# compile https://github.com/keeganryan/flatter and put it in $PATH
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
env = os.environ.copy()
env['OMP_NUM_THREADS'] = '8' # MacBook上控制线程数量, 避免调度到小核上
ret = check_output(["flatter"], input=z.encode(), env=env)
return matrix(M.nrows(), M.ncols(), map(int, findall(rb"-?\d+", ret)))
def small_roots(self, X=None, beta=0.5, epsilon=None, **kwds):
from sage.misc.verbose import verbose
from sage.matrix.constructor import Matrix
from sage.rings.real_mpfr import RR
N = self.parent().characteristic()
if not self.is_monic():
raise ArithmeticError("Polynomial must be monic.")
beta = RR(beta)
if beta <= 0.0 or beta > 1.0:
raise ValueError("0.0 < beta <= 1.0 not satisfied.")
f = self.change_ring(ZZ)
P, (x,) = f.parent().objgens()
delta = f.degree()
if epsilon is None:
epsilon = beta / 8
verbose("epsilon = %f" % epsilon, level=2)
m = max(beta**2 / (delta * epsilon), 7 * beta / delta).ceil()
verbose("m = %d" % m, level=2)
t = int((delta * m * (1 / beta - 1)).floor())
verbose("t = %d" % t, level=2)
if X is None:
X = (0.5 * N ** (beta**2 / delta - epsilon)).ceil()
verbose("X = %s" % X, level=2)
# we could do this much faster, but this is a cheap step
# compared to LLL
g = [x**j * N ** (m - i) * f**i for i in range(m) for j in range(delta)]
g.extend([x**i * f**m for i in range(t)]) # h
B = Matrix(ZZ, len(g), delta * m + max(delta, t))
for i in range(B.nrows()):
for j in range(g[i].degree() + 1):
B[i, j] = g[i][j] * X**j
print("[+] Starting flatter...")
# 把Sagemath原版LLL换成flatter以加速
B = flatter(B)
# B = B.LLL()
f = sum([ZZ(B[0, i] // X**i) * x**i for i in range(B.ncols())])
R = f.roots()
ZmodN = self.base_ring()
roots = set([ZmodN(r) for r, m in R if abs(r) <= X])
Nbeta = N**beta
return [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]
def copp_factor(N, hint, leak=4):
for tb in range(1 << leak)[::-1]:
print("copp", tb, int(time.time()))
shift = 252 - leak
P = Zmod(N)["x"]
x = P.gen()
f = (hint - (tb << shift) - x).monic()
X = 2 ** (252 - leak)
beta = 0.499
eps = 0.01
# rs = f.small_roots(X=X, beta=beta, epsilon=eps)
rs = small_roots(f, X=X, beta=beta, epsilon=eps)
if len(rs):
return (tb << shift) + int(rs[0])
N = 133196604547992363575584257705624404667968600447626367604523982016247386106677898877957513177151872429736948168642977575860754686097638795690422242542292618145151312000412007125887631130667228632902437183933840195380816196093162319293698836053406176957297330716990340998802156803899579713165154526610395279999
hint = 88154421894117450591552142051149160480833170266148800195422578353703847455418496231944089437130332162458102290491849331143073163240148813116171275432632366729218612063176137204570648617681911344674042091585091104687596255488609263266272373788618920171331355912434290259151350333219719321509782517693267379786
copp_factor(N, hint, 4)
"""then we can get flag
"""
from Crypto.Util.number import *
from Crypto.Util.Padding import unpad
from gmssl.sm4 import CryptSM4, SM4_DECRYPT
from hashlib import sha256
r = 7166351305785506670352015492214713707534657162937963088592442157834795391917
N = 133196604547992363575584257705624404667968600447626367604523982016247386106677898877957513177151872429736948168642977575860754686097638795690422242542292618145151312000412007125887631130667228632902437183933840195380816196093162319293698836053406176957297330716990340998802156803899579713165154526610395279999
hint = 88154421894117450591552142051149160480833170266148800195422578353703847455418496231944089437130332162458102290491849331143073163240148813116171275432632366729218612063176137204570648617681911344674042091585091104687596255488609263266272373788618920171331355912434290259151350333219719321509782517693267379786
c = bytes.fromhex(
"476922b694c764725338cca99d99c7471ec448d6bf60de797eb7cc6e71253221035eb577075f9658ac7f1a40747778ac261787baad21ee567256872fa9400c37"
)
p = GCD(hint - r, N)
if p == 1 or p == N or N % p != 0:
raise ValueError("Failed to factorize N with given r")
q = N // p
leak = N * r
r_bytes = long_to_bytes(leak)
iv = r_bytes[:16] if len(r_bytes) >= 16 else r_bytes + b"\0" * (16 - len(r_bytes))
s = p + q + r
key = sha256(str(s).encode()).digest()[:16]
crypt_sm4 = CryptSM4()
crypt_sm4.set_key(key, SM4_DECRYPT)
decrypted = crypt_sm4.crypt_cbc(iv, c)
plaintext = unpad(decrypted, 16)
print("Decrypted Flag:", plaintext.decode())
赛后实验了一下发现我这种解法很overkill，Coppersmith参数开到0.006之后即使不用爆bits也能直接出🤣而在flatter的加持下，即使beta开到这么小用时也很短
为什么出题人的rsa总是ez#
task
#!/usr/bin/sage
#part 1
def pad(flag, bits=1024):
pad = os.urandom(bits//8 - len(flag))
return int.from_bytes(flag + pad, "big")
p = random_prime(2**1024)
q = random_prime(2**1024)
a = randint(0, 2**1024)
b = randint(0, 2**1024)
n = p * q
e = 0x10001
flag = b''
m = pad(flag)
assert m < n
c = pow(m, e, n)
print(f"c={c}")
print(f"n={n}")
print(f"h1={p + b * q}")
print(f"h2={a * p + q}")
# c=13148687178480196374316468746303529314940770955906554155276099558796308164996908275540972246587924459788286109602343699872884525600948529446071271042497049233796074202353913271513295267105242313572798635502497823862563815696165512523074252855130556615141836416629657088666030382516860597286299687178449351241568084947058615139183249169425517358363928345728230233160550711153414555500038906881581637368920188681358625561539325485686180307359210958952213244628802673969397681634295345372096628997329630862000359069425551673474533426265702926675667531063902318865506356674927615264099404032793467912541801255735763704043
# n=13718277507497477508850292481640653320398820265455820215511251843542886373380880887850571647060788265498378060163112689840208264538965960596605641194331300743676780910818492860412739541418029075802834265712602393103809065720527365081016381358333378953245379751008531500896923727040455566953960991908174586311899809864209624888469263612475732913062035036254077225370843701146080145441104733074178115602425412116325647598625157922655504918118208783230138448694045386019901732846478340735331718476554208157393418221315041837392020742062275999319586357229583509788489495876723122993592623230858393165458733055504467513549
# h1=6992022576367328281523272055384380182550712894467837916200781058620282657859189270338635886912232754034211897894637971546032107000253692739473463119025570291091085702056938901846349325941043398928197991115231668917435951127329817379935880511925882734157491821315858319170121031835598580384038723788681860763814776365440362143661999054338470989558459179388468943933975861549233231199667742564080001256192881732567616103760815633265325456143601649393547666835326272408622540044065067528568675569233240785553062685974593620235466519632833169291153478793523397788719000334929715524989845012633742964209311952378479134661
# h2=16731800146050995761642066586565348732313856101572403535951688869814016691871958158137790504490910445304384109605408840493227057830017039824412834989258703833576252634055087138315434304691218949240382395879124201923060510497916818961571111218224960267593032380037212325935576750663442553781924370849537501656957488833521657563900462052017695599020610911371304659875887924695896434699048696392210066253577839887826292569913713802634067508141124685789817330268562127695548527522031774601654778934513355315628270319037043809972087930951609429846675450469414212384044849089372435124609387061864545559812994515828333828939
#part 2
from Crypto.Util.number import *
from gmpy2 import *
a = random_prime()
b = random_prime()
g = random_prime()
h = 2*g*a*b+a+b
while not is_prime(h):
a = random_prime()
b = random_prime()
g = random_prime()
h = 2*g*a*b+a+b
N = 2*h*g+1
e from part1's flag
flag=b''
c=pow(bytes_to_long(flag),e,N)
print(N)
print(g)
print(c)
#N=10244621233521168199001177069337072125430662416754674144307553476569744623474797179990380824494968546110022341144527766891662229403969035901337876527595841503498459533492730326942662450786522178313517616168650624224723066308178042783540825899502172432884573844850572330970359712379107318586435848029783774998269247992706770665069866338710349292941829996807892349030660021792813986069535854445874069535737849684959397062724387110903918355074327499675776518032266136930264621047345474782910332154803497103199598761422179303240476950271702406633802957400888398042773978322395227920699611001956973796492459398737390290487
#g=2296316201623391483093360819129167852633963112610999269673854449302228853625418585609211427788830598219647604923279054340009043347798635222302374950707
#c=7522161394702437062976246147354737122573350166270857493289161875402286558096915490526439656281083416286224205494418845652940140144292045338308479237214749282932144020368779474518032067934302376430305635297260147830918089492765917640581392606559936829974748692299762475615766076425088306609448483657623795178727831373194757182797030376302086360751637238867384469269953187938304369668436238848537646544257504724753333177938997524154486602644412199535102323238852958634746165559537630341890450666170836721803871120344373143081664567068672230842855208267929484000179260292518351155693154372172449820053764896414799137097前半部分给了 ，其中 都是 1024 bits 的。 令
可知 ，展开后就有
因此有：
其中 已知，所以LLL一下大概就有p和q。
配平格比较麻烦，推荐用maple3142佬的lll_cvp ↗，好用爱用。
后半段是Common Prime RSA已知g的情况，有论文可参考但是我直接对着论文搓出来的exp炸内存了…
还是码力不足
检索一番发现几乎是MRCTF 2021 - Common Prime RSA的原题，去deebato的博客 ↗抄个exp回来就能解决。以及，出题人你没有发现你的代码写的是死循环吗😡
exp
from sage.all import *
from Crypto.Util.number import *
from lll_cvp import solve_inequality # https://github.com/maple3142/lll_cvp，好用爱用
c=13148687178480196374316468746303529314940770955906554155276099558796308164996908275540972246587924459788286109602343699872884525600948529446071271042497049233796074202353913271513295267105242313572798635502497823862563815696165512523074252855130556615141836416629657088666030382516860597286299687178449351241568084947058615139183249169425517358363928345728230233160550711153414555500038906881581637368920188681358625561539325485686180307359210958952213244628802673969397681634295345372096628997329630862000359069425551673474533426265702926675667531063902318865506356674927615264099404032793467912541801255735763704043
n=13718277507497477508850292481640653320398820265455820215511251843542886373380880887850571647060788265498378060163112689840208264538965960596605641194331300743676780910818492860412739541418029075802834265712602393103809065720527365081016381358333378953245379751008531500896923727040455566953960991908174586311899809864209624888469263612475732913062035036254077225370843701146080145441104733074178115602425412116325647598625157922655504918118208783230138448694045386019901732846478340735331718476554208157393418221315041837392020742062275999319586357229583509788489495876723122993592623230858393165458733055504467513549
h1=6992022576367328281523272055384380182550712894467837916200781058620282657859189270338635886912232754034211897894637971546032107000253692739473463119025570291091085702056938901846349325941043398928197991115231668917435951127329817379935880511925882734157491821315858319170121031835598580384038723788681860763814776365440362143661999054338470989558459179388468943933975861549233231199667742564080001256192881732567616103760815633265325456143601649393547666835326272408622540044065067528568675569233240785553062685974593620235466519632833169291153478793523397788719000334929715524989845012633742964209311952378479134661
h2=16731800146050995761642066586565348732313856101572403535951688869814016691871958158137790504490910445304384109605408840493227057830017039824412834989258703833576252634055087138315434304691218949240382395879124201923060510497916818961571111218224960267593032380037212325935576750663442553781924370849537501656957488833521657563900462052017695599020610911371304659875887924695896434699048696392210066253577839887826292569913713802634067508141124685789817330268562127695548527522031774601654778934513355315628270319037043809972087930951609429846675450469414212384044849089372435124609387061864545559812994515828333828939
L = matrix([[n, 0, 0, 0], [h1 * h2, 1, 0, 0], [-h2, 0, 1, 0], [-h1, 0, 0, 1]])
lb = [0, 1, 0, 0]
ub = [0, 1, 2**1024, 2**1024]
sol = solve_inequality(L, lb, ub)
_, _, p, q = map(int, sol)
assert p * q == n
phi = (p - 1) * (q - 1)
d = pow(0x10001, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
e2 = 81733668723981020451323 # #BubbleBabble编码
# Copied from deebato
# the king of Cryptography!
# https://d33b4t0.com/MRCTF2021WP/
from sage.all import *
from gmpy2 import iroot
n=10244621233521168199001177069337072125430662416754674144307553476569744623474797179990380824494968546110022341144527766891662229403969035901337876527595841503498459533492730326942662450786522178313517616168650624224723066308178042783540825899502172432884573844850572330970359712379107318586435848029783774998269247992706770665069866338710349292941829996807892349030660021792813986069535854445874069535737849684959397062724387110903918355074327499675776518032266136930264621047345474782910332154803497103199598761422179303240476950271702406633802957400888398042773978322395227920699611001956973796492459398737390290487
g=2296316201623391483093360819129167852633963112610999269673854449302228853625418585609211427788830598219647604923279054340009043347798635222302374950707
beta = 2*g
s = (n-1)//beta
u = s//beta
v = s% beta
# 原论文的界太宽了，对着搓的exp会炸内存
left = (2*int(sqrt(n))//beta-2-v)//beta
right = (3*int(sqrt(2)*sqrt(n))//(2*beta) - 2 - v )//beta
print(left)
print(right)
print(right-left)
print(iroot(right-left,2))
D = iroot(right - left , 2)[0] + 1
b = pow(2 , beta, n)
dic = {}
base = pow(b , left , n)
diff = pow(b , D , n)
for i in range(D+1):
temp = base & 0xfffffffffff
if temp in dic:
print(i)
dic[temp] = i
base *= diff
base %= n
print('baby step done')
base = pow(b , u , n)
diff = inverse(b , n)
for i in range(D + 1):
temp = base & 0xfffffffffff
if temp in dic:
print(i , dic[temp])
base *= diff
base %= n
c=left+91*D+705
xy = u - c
x_y = v + c * beta
temp = iroot(x_y**2 - 4 * xy , 2)[0]
x = (x_y +temp) // 2
y = (x_y - temp) //2
p = x * beta + 1
q = y * beta + 1
print(p,q)
assert isPrime(p) and isPrime(q)
print(p*q == n)
phi = (p-1)*(q-1)
d = inverse(e2, phi)
c = 7522161394702437062976246147354737122573350166270857493289161875402286558096915490526439656281083416286224205494418845652940140144292045338308479237214749282932144020368779474518032067934302376430305635297260147830918089492765917640581392606559936829974748692299762475615766076425088306609448483657623795178727831373194757182797030376302086360751637238867384469269953187938304369668436238848537646544257504724753333177938997524154486602644412199535102323238852958634746165559537630341890450666170836721803871120344373143081664567068672230842855208267929484000179260292518351155693154372172449820053764896414799137097
print(long_to_bytes(pow(c,d,n)))
# b'flag{I wish you success in your cryptography career}'事后看了la佬的博客 ↗，原来把网上已有的exp里gamma改成有理数就好了…赛中我直接取了两位小数一直打不通QQ
lcgp#
签到题，不想看也不想思考，扔给AI一把梭:P
task
from Crypto.Util.number import *
import gmpy2
import random
n = getPrime(1024)
flag = b'H&NCTF{' + str(uuid.uuid4()).encode() + b'}'
flag=bytes_to_long(flag)
e = 2024
c=pow(e, flag, n)
class LCG:
def __init__(self, seed, a, b, m):
self.seed = seed
self.a = a
self.b = b
self.m = m
def generate(self):
self.seed = (self.a * self.seed + self.b) % self.m
return self.seed
lcg = LCG(c, getPrime(256), getPrime(256), getPrime(2048))
random = [lcg.generate() for _ in range(5)]
print(random)
print("n=",n)
#[11250327355112956284720719987943941825496074893551827972877616718074592862130806975889275745497426515405562887727117008818863728803549848574821067056997423443681347885027000632462241968640893471352200125748453396098854283137158609264944692129301617338233670002547470932851350750870478630955328653729176440142198779254117385657086615711880537380965161180532127926250520546846863536247569437, 1289730679860726245234376434590068355673648326448223956572444944595048952808106413165882424967688302988257332835229651422892728384363094065438370663362237241013242843898967355558977974152917458085812489310623200114007728021151551927660975648884448177346441902806386690751359848832912607313329587047853601875294089502467524598036474193845319703759478494109845743765770254308199331552085163360820459311523382612948322756700518669154345145757700392164795583041949318636, 147853940073845086740348793965278392144198492906678575722238097853659884813579087132349845941828785238545905768867483183634111847434793587821166882679621234634787376562998606494582491550592596838027522285263597247798608351871499848571767008878373891341861704004755752362146031951465205665840079918938797056361771851047994530311215961536936283541887169156535180878864233663699607369701462321037824218572445283037132205269900255514050653933970174340553425147148993214797622395988788709572605943994223528210919230924346860415844639247799805670459, 7426988179463569301750073197586782838200202717435911385357661153208197570200804485303362695962843396307030986052311117232622043073376409347836815567322367321085387874196758434280075897513536063432730099103786733447352512984165432175254784494400699821500026196293994318206774720213317148132311223050562359314735977091536842516316149049281012797103790472349557847649282356393682360276814293256129426440381745354969522053841093229320186679875177247919985804406150542514337515002645320320069788390314900121917747534146857716743377658436154645197488134340819076585888700553005062311578963869641978771532330577371974731136, 10389979373355413148376869524987139791217158307590828693700943753512488757973725227850725013905113587408391654379552713436220790487026223039058296951420273907725324214990441639760825661323514381671141482079783647253661594138658677104054180912818864005556386671430082941396497098166887200556959866845325602873713813206312644590812141400536476615405444030140762980665885244721798105034497461675317071497925846844396796854201566038890503298824928152263774446268093725702310124363765630370263370678902342200494544961012407826314577564991676315451785987248633724138137813024481818431889574317602521878974976264742037227074]
#n=604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059exp
from sage.all import *
from Crypto.Util.number import long_to_bytes
import re
# 给定数据（替换为实际题目输出）
random = [11250327355112956284720719987943941825496074893551827972877616718074592862130806975889275745497426515405562887727117008818863728803549848574821067056997423443681347885027000632462241968640893471352200125748453396098854283137158609264944692129301617338233670002547470932851350750870478630955328653729176440142198779254117385657086615711880537380965161180532127926250520546846863536247569437, 1289730679860726245234376434590068355673648326448223956572444944595048952808106413165882424967688302988257332835229651422892728384363094065438370663362237241013242843898967355558977974152917458085812489310623200114007728021151551927660975648884448177346441902806386690751359848832912607313329587047853601875294089502467524598036474193845319703759478494109845743765770254308199331552085163360820459311523382612948322756700518669154345145757700392164795583041949318636, 147853940073845086740348793965278392144198492906678575722238097853659884813579087132349845941828785238545905768867483183634111847434793587821166882679621234634787376562998606494582491550592596838027522285263597247798608351871499848571767008878373891341861704004755752362146031951465205665840079918938797056361771851047994530311215961536936283541887169156535180878864233663699607369701462321037824218572445283037132205269900255514050653933970174340553425147148993214797622395988788709572605943994223528210919230924346860415844639247799805670459, 7426988179463569301750073197586782838200202717435911385357661153208197570200804485303362695962843396307030986052311117232622043073376409347836815567322367321085387874196758434280075897513536063432730099103786733447352512984165432175254784494400699821500026196293994318206774720213317148132311223050562359314735977091536842516316149049281012797103790472349557847649282356393682360276814293256129426440381745354969522053841093229320186679875177247919985804406150542514337515002645320320069788390314900121917747534146857716743377658436154645197488134340819076585888700553005062311578963869641978771532330577371974731136, 10389979373355413148376869524987139791217158307590828693700943753512488757973725227850725013905113587408391654379552713436220790487026223039058296951420273907725324214990441639760825661323514381671141482079783647253661594138658677104054180912818864005556386671430082941396497098166887200556959866845325602873713813206312644590812141400536476615405444030140762980665885244721798105034497461675317071497925846844396796854201566038890503298824928152263774446268093725702310124363765630370263370678902342200494544961012407826314577564991676315451785987248633724138137813024481818431889574317602521878974976264742037227074] # 替换为题目输出的随机数列表（5个整数）
n = 604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059 # 替换为题目输出的n值
# 步骤1：从5个连续输出恢复LCG参数
r0, r1, r2, r3, r4 = random
# 计算差分
d0 = r1 - r0
d1 = r2 - r1
d2 = r3 - r2
d3 = r4 - r3
# 计算T0和T1
T0 = d0*d2 - d1**2
T1 = d1*d3 - d2**2
# 计算gcd并取其绝对值
g = gcd(T0, T1)
g = abs(g)
# 检查并提取2048位的模数m
if g.nbits() == 2048 and g.is_prime():
m = g
else:
# 尝试从因子中提取2048位的素数
factors = factor(g)
m_candidates = [p for p, e in factors if p.nbits() == 2048 and p.is_prime()]
if not m_candidates:
raise ValueError("无法从gcd中提取2048位素数模数m")
m = m_candidates[0]
# 恢复参数a
denom = r1 - r0
if denom == 0:
raise ValueError("差分值为0，无法计算逆元")
inv_denom = inverse_mod(denom, m)
a = (r2 - r1) * inv_denom % m
# 恢复参数b
b = (r1 - a * r0) % m
# 恢复初始种子c
inv_a = inverse_mod(a, m)
c_seed = (r0 - b) * inv_a % m
c_val = c_seed % n # c = 2024^{flag} mod n
F = GF(n)
base = F(2024)
target = F(c_val)
n_minus_one = n - 1
flag = discrete_log(target, base, n_minus_one)
# 转换为字节并提取flag
flag_bytes = long_to_bytes(int(flag))
flag_str = flag_bytes.decode('latin1')
# 验证并格式化UUID
match = re.search(r'H&NCTF\{(.+?)\}', flag_str)
if match:
uuid_part = match.group(1)
if len(uuid_part) == 36: # UUID标准长度
print("Flag:", flag_str)
else:
print("提取到可能的flag，但UUID格式异常:", flag_str)
else:
print("未找到标准flag格式，原始字节:", flag_bytes)
# Flag: H&NCTF{7ecf4c8c-e6a5-45c7-b7de-2fecc31d8511}three vertical lines#
task
from Crypto.Util.number import *
from secret import flag
from rsa.prime import getprime
while(1):
p=getprime(256)
q=getprime(256)
if isPrime(3*p**5+4*q**5):
print(3*p**5+4*q**5)
break
e = 65537
print(pow(bytes_to_long(flag), e, p * q))
#72063558451087451183203801132459543552092564094711815404066471440396765744526854383117910805713050240067432476705168314622044706081669935956972031037827580519320550326077291392722314265758802332280697884744792689996718961355845963752788234205565249205191648439412084543163083032775054018324646541875754706761793307667356964825613429368358849530455220484128264690354330356861777561511117
#2864901454060087890623075705953001126417241189889895476561381971868301515757296100356013797346138819690091860054965586977737630238293536281745826901578223这题好巧不巧被我做过原题(niteCTF 2024 - R Stands Alone)，不过那题当时有非预期解🤣 预期解 ↗就是把方程放在mod r下考虑，两边开根后用格去打。
不过就算没做过原题应该也能想到降次处理，处理到一次的时候肯定会想格一格吧
exp
from sage.all import *
from Crypto.Util.number import *
r = 72063558451087451183203801132459543552092564094711815404066471440396765744526854383117910805713050240067432476705168314622044706081669935956972031037827580519320550326077291392722314265758802332280697884744792689996718961355845963752788234205565249205191648439412084543163083032775054018324646541875754706761793307667356964825613429368358849530455220484128264690354330356861777561511117
PF = Zmod(r)
PR = PolynomialRing(PF, "x")
x = PR.gen()
c = 2864901454060087890623075705953001126417241189889895476561381971868301515757296100356013797346138819690091860054965586977737630238293536281745826901578223
assert isPrime(r)
inv = PF(-4)/PF(3)
f = x**5 - inv
print(f.roots()[0][0])
root = 28358223922809039451505880360595032492037557754419108014959801704984387395382426909907912482965374099273724433198680793561600606585076434164429817050141934114840474173780015368231251414628380474645626388950791820425221750685303585771233699046750719260223373050767626613852520861630006889754101190475520645848050199609521840203573345117528059663889417248056598901189159660274791413041928
M = Matrix(ZZ, [
[1, root],
[0, r]])
print(M.LLL())
p = 106939296519048296066609095791824433210081775149307042159537637081687455851889
q = 88318396054969634676003916964315749322940927962528304238128738629965788358867
phi = (p-1)*(q-1)
d = inverse(65537, phi)
print(long_to_bytes(pow(c,d,p*q)))
# b'H&NCTF{You_learned_the_code_well}'Misc#
谁动了黑线#
给了个csv文件，像是区块链交易日志一类的东西。最后一列是base58，解码看出来中间有6位时间戳，按这个时间戳升序排列后再逐行提取最后一列的小写字母和符号即可。
不方便贴题目附件，也就不贴exp了:P
反正把prompt喂给AI也能一把梭