2025HNCTF - Crypto

Crypto

lcgp

题目：

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 = seedself.a = aself.b = bself.m = mdef generate(self):self.seed = (self.a * self.seed + self.b) % self.mreturn self.seedlcg = 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=604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059

思路：

LCG | DexterJie'Blog，利用 Gröbner基 解 LCG 问题，可以还原出 c，然后再解一个 DLP 问题

exp：

from Crypto.Util.number import *
import gmpy2output = [11250327355112956284720719987943941825496074893551827972877616718074592862130806975889275745497426515405562887727117008818863728803549848574821067056997423443681347885027000632462241968640893471352200125748453396098854283137158609264944692129301617338233670002547470932851350750870478630955328653729176440142198779254117385657086615711880537380965161180532127926250520546846863536247569437, 1289730679860726245234376434590068355673648326448223956572444944595048952808106413165882424967688302988257332835229651422892728384363094065438370663362237241013242843898967355558977974152917458085812489310623200114007728021151551927660975648884448177346441902806386690751359848832912607313329587047853601875294089502467524598036474193845319703759478494109845743765770254308199331552085163360820459311523382612948322756700518669154345145757700392164795583041949318636, 147853940073845086740348793965278392144198492906678575722238097853659884813579087132349845941828785238545905768867483183634111847434793587821166882679621234634787376562998606494582491550592596838027522285263597247798608351871499848571767008878373891341861704004755752362146031951465205665840079918938797056361771851047994530311215961536936283541887169156535180878864233663699607369701462321037824218572445283037132205269900255514050653933970174340553425147148993214797622395988788709572605943994223528210919230924346860415844639247799805670459, 7426988179463569301750073197586782838200202717435911385357661153208197570200804485303362695962843396307030986052311117232622043073376409347836815567322367321085387874196758434280075897513536063432730099103786733447352512984165432175254784494400699821500026196293994318206774720213317148132311223050562359314735977091536842516316149049281012797103790472349557847649282356393682360276814293256129426440381745354969522053841093229320186679875177247919985804406150542514337515002645320320069788390314900121917747534146857716743377658436154645197488134340819076585888700553005062311578963869641978771532330577371974731136, 10389979373355413148376869524987139791217158307590828693700943753512488757973725227850725013905113587408391654379552713436220790487026223039058296951420273907725324214990441639760825661323514381671141482079783647253661594138658677104054180912818864005556386671430082941396497098166887200556959866845325602873713813206312644590812141400536476615405444030140762980665885244721798105034497461675317071497925846844396796854201566038890503298824928152263774446268093725702310124363765630370263370678902342200494544961012407826314577564991676315451785987248633724138137813024481818431889574317602521878974976264742037227074]
N = 604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059
e = 2024R.<a,b> = PolynomialRing(ZZ)f1 = output[0]*a + b - output[1]
f2 = output[1]*a + b - output[2]
f3 = output[2]*a + b - output[3]
f4 = output[3]*a + b - output[4]F = [f1,f2,f3,f4]
# 使用F构建一个理想的Ideal。
ideal = Ideal(F)
# 计算Ideal的Gröbner基I
I = ideal.groebner_basis()a = ZZ(-I[0].univariate_polynomial()(0))
b = ZZ(-I[1].univariate_polynomial()(0))
n = ZZ(I[2])print(a)
print(b)
print(n)enc = (output[0] - b) * inverse(a,n) % nm = discrete_log(enc ,mod(e, N))
print(long_to_bytes(m))

flag：H&NCTF{7ecf4c8c-e6a5-45c7-b7de-2fecc31d8511}

哈基coke

题目：

import matplotlib.pyplot as plt
import cv2
import numpy as np
from PIL import Image
def arnold_encode(image, shuffle_times, a, b):""" Arnold shuffle for rgb imageArgs:image: input original rgb imageshuffle_times: how many times to shuffleReturns:Arnold encode image"""arnold_image = np.zeros(shape=image.shape)h, w = image.shape[0], image.shape[1]N = hfor time in range(shuffle_times):for ori_x in range(h):for ori_y in range(w):new_x = (1*ori_x + b*ori_y)% Nnew_y = (a*ori_x + (a*b+1)*ori_y) % Narnold_image[new_x, new_y, :] = image[ori_x, ori_y, :]image = np.copy(arnold_image)cv2.imwrite('en_flag.png', arnold_image, [int(cv2.IMWRITE_PNG_COMPRESSION), 0])return arnold_imageimg = cv2.imread('coke.png')
arnold_encode(img,6,9,1)

思路：

一个猫脸变换的加密，直接解密即可

import matplotlib.pyplot as plt
import cv2
import numpy as np
from PIL import Imagedef arnold_decode(image, shuffle_times, a, b):""" decode for rgb image that encoded by ArnoldArgs:image: rgb image encoded by Arnoldshuffle_times: how many times to shuffleReturns:decode image"""# 1:创建新图像decode_image = np.zeros(shape=image.shape, dtype=np.uint8)# 2：计算Nh, w = image.shape[0], image.shape[1]N = h  # 或N=w# 3：遍历像素坐标变换for time in range(shuffle_times):for ori_x in range(h):for ori_y in range(w):# 按照公式坐标变换new_x = ((a * b + 1) * ori_x + (-b) * ori_y) % Nnew_y = ((-a) * ori_x + ori_y) % Ndecode_image[new_x, new_y, :] = image[ori_x, ori_y, :]image = np.copy(decode_image)cv2.imwrite('flag.png', decode_image, [int(cv2.IMWRITE_PNG_COMPRESSION), 0])return decode_imageimage = cv2.imread('en_flag.png')
arnold_decode(image, 6, 9, 1)
# H&NCTF{haji_coke_you_win}

flag：H&NCTF{haji_coke_you_win}

数据处理

题目：

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 ** 512m = random.randint(2, n - 1) | 1c = pow(m, int(new_flag), n)
print('m = ' + str(m))
print('c = ' + str(c))
# m = 5084057673176634704877325918195984684237263100965172410645544705367004138917087081637515846739933954602106965103289595670550636402101057955537123475521383
# c = 2989443482952171039348896269189568991072039347099986172010150242445491605115276953489889364577445582220903996856271544149424805812495293211539024953331399

思路：

先根据离散对数求出 new_flag ，然后再爆破 uppercase，再去逆推爆破出 table ，最后还原 flag

from Crypto.Util.number import *
import gmpy2
import itertoolsm = 5084057673176634704877325918195984684237263100965172410645544705367004138917087081637515846739933954602106965103289595670550636402101057955537123475521383
c = 2989443482952171039348896269189568991072039347099986172010150242445491605115276953489889364577445582220903996856271544149424805812495293211539024953331399
n = 2 ** 512new_flag = discrete_log(c, mod(m, n))num = '0123456789'
lowercase = '0123456789'
# uppercase = '2***7****0' # 生成所有可能的替换表
for i in itertools.product(num, repeat=3):for j in itertools.product(num, repeat=4):uppercase = '7' + ''.join(i) + '4' + ''.join(j) + '5'table = ''.maketrans(uppercase, lowercase) m = str(new_flag).translate(table)flag = long_to_bytes(int(m))if b'H&NCTF{' in flag and b'}' in flag:print(f'uppercase = {uppercase}, flag = {flag}')

flag：H&NCTF{cut_cut_rrioajtfijrwegeriogjiireigji}

three vertical lines

题目：

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)breake = 65537
print(pow(bytes_to_long(flag), e, p * q))
#72063558451087451183203801132459543552092564094711815404066471440396765744526854383117910805713050240067432476705168314622044706081669935956972031037827580519320550326077291392722314265758802332280697884744792689996718961355845963752788234205565249205191648439412084543163083032775054018324646541875754706761793307667356964825613429368358849530455220484128264690354330356861777561511117
#2864901454060087890623075705953001126417241189889895476561381971868301515757296100356013797346138819690091860054965586977737630238293536281745826901578223

思路：

审计代码得：

$$3p^5+4q^5=k$$

那么：

$$p^5\equiv -\frac{4}{3}{q}^5(\mathrm{mod}k)$$

两边同时开 5 次方，有：

$$\begin{gathered} p\equiv t\cdot q(\mathrm{mod}k) \\ {t}^5\equiv -\frac{4}{3}(\mathrm{mod}k) \end{gathered}$$

先求出 $t$ ，因为 $t^5\equiv -\frac{4}{3}(\mathrm{mod}k)$。也就是说，我们需要在模 $k$ 下计算 $-\frac{4}{3}$ 的逆元，然后找到一个 $t$ 使得它的五次方等于这个值。

根据模运算的定义，这等价于存在整数 $s$ 使得

$$t^5=-\frac{4}{3}+s\cdot k$$

为了消除分数，两边同时乘以 3：

$$\begin{gathered} 3t^5=-4+3m\cdot k \\ 3t^5\equiv -4(\mathrm{mod}k) \end{gathered}$$

然后求出 $t^5$，我们要先找到 3 在模 $k$ 下的逆元，假设位 $x=\text{ gmpy2.invert}(3,k)$：则有

$$\begin{gathered} 3x\equiv 1(\mathrm{mod}k) \\ 3x\cdot t^5\equiv -4x(\mathrm{mod}k) \\ {t}^5\equiv -4x(\mathrm{mod}k) \end{gathered}$$

然后就能求出 $t^5\mathrm{mod}k$ 的值

$$t^5\mathrm{mod}k=(-4)\times \text{ gmpy2.invert}(3,k)\mathrm{mod}k$$

然后就是模 $k$ 下寻找五次方根，利用 sage 就行

R = Zmod(n)
roots = []
try:roots = R(c).nth_root(5, all=True)print("Roots:", roots)
except ValueError:print("No fifth roots found.")exit()

‍

求出 t 后，有：

$$p=n-tq$$

然后造格，并应用 LLL 算法进行格基规约，找到满足条件的 p，q

$$\left(\begin{array}{ll}1& p\end{array}\right)\left(\begin{array}{ll}1& t\\ 0& k\end{array}\right)=\left(\begin{array}{ll}q& p\end{array}\right)$$

exp：

from Crypto.Util.number import *n = 72063558451087451183203801132459543552092564094711815404066471440396765744526854383117910805713050240067432476705168314622044706081669935956972031037827580519320550326077291392722314265758802332280697884744792689996718961355845963752788234205565249205191648439412084543163083032775054018324646541875754706761793307667356964825613429368358849530455220484128264690354330356861777561511117
ciphertext = 2864901454060087890623075705953001126417241189889895476561381971868301515757296100356013797346138819690091860054965586977737630238293536281745826901578223
e = 65537# 计算 -4/3 mod n
c = (-4) * inverse_mod(3, n) % n# 在模n下寻找五次方根
R = Zmod(n)
roots = []
try:roots = R(c).nth_root(5, all=True)
except ValueError:print("No fifth roots found.")exit()found = False
for t in roots:t = int(t)# 构造格M = matrix(ZZ, [[1, t], [0, n]])L = M.LLL()# 检查每一行向量for row in L:q, p = row# 取绝对值处理可能的负值q_abs = abs(q)p_abs = abs(p)if q_abs == 0 or p_abs == 0:continue# 检查是否为素数且满足方程if is_prime(q_abs) and is_prime(p_abs) and 3*p_abs**5 + 4*q_abs**5 == n:print(f"Found p = {p_abs}, q = {q_abs}")found = Truebreakif found:breakif not found:print("Failed to find p and q.")exit()N = p_abs * q_abs
phi = (p_abs - 1) * (q_abs - 1)
d = inverse_mod(e, phi)
plaintext = pow(ciphertext, d, N)
print("flag:", long_to_bytes(plaintext))

flag：H&NCTF{You_learned_the_code_well}

为什么出题人的rsa总是ez

题目：

#part 1def 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 < nc = 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 2from 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

思路：

第一部分：

就是强网杯 2024-apbq 这题 2024-强网杯-wp-crypto | 糖醋小鸡块的blog

已知：

$$\begin{gathered} h1=p+b\ast q \\ h2=a\ast p+q \end{gathered}$$

exp：

from Crypto.Util.number import *c = 13148687178480196374316468746303529314940770955906554155276099558796308164996908275540972246587924459788286109602343699872884525600948529446071271042497049233796074202353913271513295267105242313572798635502497823862563815696165512523074252855130556615141836416629657088666030382516860597286299687178449351241568084947058615139183249169425517358363928345728230233160550711153414555500038906881581637368920188681358625561539325485686180307359210958952213244628802673969397681634295345372096628997329630862000359069425551673474533426265702926675667531063902318865506356674927615264099404032793467912541801255735763704043
n = 13718277507497477508850292481640653320398820265455820215511251843542886373380880887850571647060788265498378060163112689840208264538965960596605641194331300743676780910818492860412739541418029075802834265712602393103809065720527365081016381358333378953245379751008531500896923727040455566953960991908174586311899809864209624888469263612475732913062035036254077225370843701146080145441104733074178115602425412116325647598625157922655504918118208783230138448694045386019901732846478340735331718476554208157393418221315041837392020742062275999319586357229583509788489495876723122993592623230858393165458733055504467513549
h2 = 6992022576367328281523272055384380182550712894467837916200781058620282657859189270338635886912232754034211897894637971546032107000253692739473463119025570291091085702056938901846349325941043398928197991115231668917435951127329817379935880511925882734157491821315858319170121031835598580384038723788681860763814776365440362143661999054338470989558459179388468943933975861549233231199667742564080001256192881732567616103760815633265325456143601649393547666835326272408622540044065067528568675569233240785553062685974593620235466519632833169291153478793523397788719000334929715524989845012633742964209311952378479134661
h1 = 16731800146050995761642066586565348732313856101572403535951688869814016691871958158137790504490910445304384109605408840493227057830017039824412834989258703833576252634055087138315434304691218949240382395879124201923060510497916818961571111218224960267593032380037212325935576750663442553781924370849537501656957488833521657563900462052017695599020610911371304659875887924695896434699048696392210066253577839887826292569913713802634067508141124685789817330268562127695548527522031774601654778934513355315628270319037043809972087930951609429846675450469414212384044849089372435124609387061864545559812994515828333828939
e = 0x10001brute = 2
for i in range(2^brute):for j in range(2^brute):L = Matrix(ZZ, [[1,0,0,2^brute*h1],[0,1,0,2^brute*h2],[0,0,2^(1024-brute),h1*i+h2*j-h1*h2],[0,0,0,n]])L[:,-1:] *= nres = L.LLL()[0]p = 2^brute*abs(res[0])+iif(n % p == 0):print(p)q = n//pphi = (p-1)*(q-1)d = inverse_mod(e, phi)print(long_to_bytes(pow(c, d, n)))print(pow(c, d, n))

flag{e_is_xevaf-cityf-fisof-ketaf-metaf-disef-nuvaf-cysuf-dosuf-getuf-cysuf-dasix,bubbleBabble}

古典密码 bubbleBabble 解一下得到 e

xevaf-cityf-fisof-ketaf-metaf-disef-nuvaf-cysuf-dosuf-getuf-cysuf-dasix

第二部分

就是 Common Prime RSA 笔记 | 独奏の小屋，这里我不知道为啥不能直接在这个脚本中直接去计算 rsa 一直解不出来，想了半天不知道为啥，害，最后要单独把 p，q 取出来才能解密，参考 强网杯 2024-EasyRSA 2024-强网杯-wp-crypto | 糖醋小鸡块的blog

from sage.groups.generic import bsgs
from Crypto.Util.number import *
from sage.all import ZZ, Zmod, ceil
import gmpy2N=10244621233521168199001177069337072125430662416754674144307553476569744623474797179990380824494968546110022341144527766891662229403969035901337876527595841503498459533492730326942662450786522178313517616168650624224723066308178042783540825899502172432884573844850572330970359712379107318586435848029783774998269247992706770665069866338710349292941829996807892349030660021792813986069535854445874069535737849684959397062724387110903918355074327499675776518032266136930264621047345474782910332154803497103199598761422179303240476950271702406633802957400888398042773978322395227920699611001956973796492459398737390290487
g=2296316201623391483093360819129167852633963112610999269673854449302228853625418585609211427788830598219647604923279054340009043347798635222302374950707
c=7522161394702437062976246147354737122573350166270857493289161875402286558096915490526439656281083416286224205494418845652940140144292045338308479237214749282932144020368779474518032067934302376430305635297260147830918089492765917640581392606559936829974748692299762475615766076425088306609448483657623795178727831373194757182797030376302086360751637238867384469269953187938304369668436238848537646544257504724753333177938997524154486602644412199535102323238852958634746165559537630341890450666170836721803871120344373143081664567068672230842855208267929484000179260292518351155693154372172449820053764896414799137097e = 81733668723981020451323print(N.bit_length())
print(g.bit_length())nbits = N.bit_length()
gamma = 500/(1024*2)
cbits = ceil(nbits * (0.5 - 2 * gamma))M = (N - 1) // (2 * g)
u = M // (2 * g)
v = M - 2 * g * u
GF = Zmod(N)
x = GF(2)  
y = x ** (2 * g)c = bsgs(y, y ** u, (2**(cbits - 1), 2**(cbits + 1)))ab = u - c
apb = v + 2 * g * c# 定义多项式并求解根
P.<x> = ZZ[]
f = x^2 - apb * x + ab
a_roots = f.roots()if a_roots:a, b = a_roots[0][0], a_roots[1][0]p = 2 * g * a + 1q = 2 * g * b + 1print(p)print(q)assert p * q == Nphi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

from Crypto.Util.number import long_to_bytes, isPrime
import gmpy2p=114223230692329221233593176873809300402703143063931397822580003361438712054166147412606967205124955861521969519047697209787311806459638088623102779532442176190528211946769436968799761724667716082655997119572158947882963880778970164432326393480858337150525471346874196183962785321409039116916910681846888186947
q=89689471847596377741222144429998037990667180177357564376140367776414308387012923411995322262858328353318533567758158657166891766790825298883408932478365300323143798943782413227199460096726803837011408747331311614322911225425264615177532865042145570988661750629687056545931523546752474174278821175282246381821
c=7522161394702437062976246147354737122573350166270857493289161875402286558096915490526439656281083416286224205494418845652940140144292045338308479237214749282932144020368779474518032067934302376430305635297260147830918089492765917640581392606559936829974748692299762475615766076425088306609448483657623795178727831373194757182797030376302086360751637238867384469269953187938304369668436238848537646544257504724753333177938997524154486602644412199535102323238852958634746165559537630341890450666170836721803871120344373143081664567068672230842855208267929484000179260292518351155693154372172449820053764896414799137097
n=p*q
e=81733668723981020451323
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

flag：flag{I wish you success in your cryptography career}

ez-factor

题目：

from Crypto.Util.number import *
import uuidrbits = 248
Nbits = 1024p = 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

思路：

已知：

$$hint=k\ast p+r$$

其中 k 是 512 位，r 只有 248 位，r 远远⼩于 hint，那么有

$$hint-r\equiv 0\mathrm{mod}p$$

r 是⼀个小根，使⽤ CopperSmith 慢慢调参数即可，这里一开始 epsilon 开到 0.01 很慢，然后慢慢加 0.015​ 会快一点，这里也可以使用 flatter 加速⼀下（会快好多，这里同时把 epsilon 设置成 0.015 只需要 3 秒），用大佬的脚步即可 （SEETF 2023 WriteUps | 廢文集中區）

exp：

from Crypto.Util.number import *
import gmpy2N = 155296910351777777627285876776027672037304214686081903889658107735147953235249881743173605221986234177656859035013052546413190754332500394269777193023877978003355429490308124928931570682439681040003000706677272854316717486111569389104048561440718904998206734429111757045421158512642953817797000794436498517023
hint = 128897771799394706729823046048701824275008016021807110909858536932196768365642942957519868584739269771824527061163774807292614556912712491005558619713483097387272219068456556103195796986984219731534200739471016634325466080225824620962675943991114643524066815621081841013085256358885072412548162291376467189508
c = 32491252910483344435013657252642812908631157928805388324401451221153787566144288668394161348411375877874802225033713208225889209706188963141818204000519335320453645771183991984871397145401449116355563131852618397832704991151874545202796217273448326885185155844071725702118012339804747838515195046843936285308
e = 0x10001R = 2^248 # r 的上界
P.<x> = PolynomialRing(Zmod(N))
f = hint - x
f = f.monic()
r = f.small_roots(X=R, beta=0.495, epsilon=0.015)[0]
print(r)p = gmpy2.gcd(int(hint - r), int(N))
q = int(N)// p
phi = (p - 1) * (q - 1)
d = inverse_mod(e, int(phi))
m = pow(c, d, N)
print(long_to_bytes(m))

from sage.all import *
from Crypto.Util.number import *
from subprocess import check_output
from re import findall
import gmpy2def flatter(M):# compile https://github.com/keeganryan/flatter and put it in $PATHz = "[[" + "]\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=1.0, epsilon=None, **kwds):from sage.misc.verbose import verbosefrom sage.matrix.constructor import Matrixfrom sage.rings.real_mpfr import RRN = 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 / 8verbose("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 LLLg = [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)])  # hB = 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**jB = flatter(B)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**betareturn [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]N = 155296910351777777627285876776027672037304214686081903889658107735147953235249881743173605221986234177656859035013052546413190754332500394269777193023877978003355429490308124928931570682439681040003000706677272854316717486111569389104048561440718904998206734429111757045421158512642953817797000794436498517023
hint = 128897771799394706729823046048701824275008016021807110909858536932196768365642942957519868584739269771824527061163774807292614556912712491005558619713483097387272219068456556103195796986984219731534200739471016634325466080225824620962675943991114643524066815621081841013085256358885072412548162291376467189508
c = 32491252910483344435013657252642812908631157928805388324401451221153787566144288668394161348411375877874802225033713208225889209706188963141818204000519335320453645771183991984871397145401449116355563131852618397832704991151874545202796217273448326885185155844071725702118012339804747838515195046843936285308
e = 0x10001R = 2^248 # r 的上界
P.<x> = PolynomialRing(Zmod(N))
f = hint - x
f = f.monic()
rs = small_roots(f, X=R, beta=0.499, epsilon=0.015)
print(rs)
if rs:r = rs[0]p = gmpy2.gcd(int(hint - r), int(N))q = int(N)// pphi = (p - 1) * (q - 1)d = inverse_mod(e, int(phi))m = pow(c, d, N)print(long_to_bytes(m))

ez-factor-pro

题目：

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 = 1024p = 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

思路：

这题的关键依旧是求 $r$，求出后，$p，q，leak$ 等关键的参数都能求出。但是这里 $r$ 的位数到了 252，一直解不出，所以可以尝试爆破几位，可以学习 SEETF 2023 WriteUps | 廢文集中區，这题，

我们上面 248 位可以解出，所以这里爆 4 位即可

‍

exp：

from sage.all import *
from Crypto.Util.number import *
from subprocess import check_output
from re import findall
import gmpy2
import timedef flatter(M):# compile https://github.com/keeganryan/flatter and put it in $PATHz = "[[" + "]\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=1.0, epsilon=None, **kwds):from sage.misc.verbose import verbosefrom sage.matrix.constructor import Matrixfrom sage.rings.real_mpfr import RRN = 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 / 8verbose("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 LLLg = [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)])  # hB = 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**jB = flatter(B)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**betareturn [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]N = 133196604547992363575584257705624404667968600447626367604523982016247386106677898877957513177151872429736948168642977575860754686097638795690422242542292618145151312000412007125887631130667228632902437183933840195380816196093162319293698836053406176957297330716990340998802156803899579713165154526610395279999
hint = 88154421894117450591552142051149160480833170266148800195422578353703847455418496231944089437130332162458102290491849331143073163240148813116171275432632366729218612063176137204570648617681911344674042091585091104687596255488609263266272373788618920171331355912434290259151350333219719321509782517693267379786
c = '476922b694c764725338cca99d99c7471ec448d6bf60de797eb7cc6e71253221035eb577075f9658ac7f1a40747778ac261787baad21ee567256872fa9400c37'
c = bytes.fromhex(c)rbits = 252
high_bits = 4 #爆破⾼位
X = 2 ^ (rbits - high_bits) - 1# 爆破 4 位⾼位
for i in range(1 << high_bits, -1, -1):r_high = i << (rbits - high_bits)# 构建多项式，hint - (r_high + z) = 0 mod pP.<x> = PolynomialRing(Zmod(N))f = hint - (r_high + x)f = f.monic()# 计算多项式的根X = 2 ** (252 - 4)beta = 0.499eps = 0.015rs = small_roots(f, X=X, beta=beta, epsilon=eps)if rs:r_low = rs[0]r = r_high + r_lowprint(r)break

参考大佬的爆破写法

def copp_factor(N, hint, leak=4):for tb in range(1 << leak)[::-1]:print("copp", tb, int(time.time()))shift = 252 - leakP = Zmod(N)["x"]x = P.gen()f = (hint - (tb << shift) - x).monic()X = 2 ** (252 - leak)beta = 0.499eps = 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])r = copp_factor(N, hint, 4)
print(r)
p = gmpy2.gcd(int(hint - r), int(N))
q = int(N) // p
print(p*q == N)

然后再解 sm4

from Crypto.Util.number import *
import gmpy2
from hashlib import sha256
from gmssl.sm4 import CryptSM4, SM4_ENCRYPT, SM4_DECRYPTN = 133196604547992363575584257705624404667968600447626367604523982016247386106677898877957513177151872429736948168642977575860754686097638795690422242542292618145151312000412007125887631130667228632902437183933840195380816196093162319293698836053406176957297330716990340998802156803899579713165154526610395279999
hint = 88154421894117450591552142051149160480833170266148800195422578353703847455418496231944089437130332162458102290491849331143073163240148813116171275432632366729218612063176137204570648617681911344674042091585091104687596255488609263266272373788618920171331355912434290259151350333219719321509782517693267379786
c = '476922b694c764725338cca99d99c7471ec448d6bf60de797eb7cc6e71253221035eb577075f9658ac7f1a40747778ac261787baad21ee567256872fa9400c37'
c = bytes.fromhex(c)r = 7166351305785506670352015492214713707534657162937963088592442157834795391917p = gmpy2.gcd(int(hint - r), int(N))
q = int(N)// p
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_DECRYPT)
decrypted = crypt_sm4.crypt_cbc(iv, c)
print(decrypted)

flag：H&NCTF{ac354aae-cb6b-4bd1-a9cd-090812b8f93e}

‍