2025 vnctf crypto方向题解
crypto
easymath
解这题目怎么感觉回到了高中
先解出三个n,再用crt
from sympy import symbols, expand, solve
# 定义符号
x = symbols('x')
# 多项式系数
# 给定的多项式: x^3 - 15264966144147258587171776703005926730518438603688487721465*x**2 + 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923*x - 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619
polynomial = x**3 - 15264966144147258587171776703005926730518438603688487721465*x**2 + 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923*x - 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619
# 求解多项式的根
roots = solve(polynomial, x)
# 输出根
print(f"Roots of the polynomial: {roots}")from sympy import symbols, expand
from Crypto.Util.number import long_to_bytes
from sage.all import crt
# 给定数据
c = 24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944
polynomial = symbols('x')**3 - 15264966144147258587171776703005926730518438603688487721465*symbols('x')**2 + 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923*symbols('x') - 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619
# 提取多项式系数
S = 15264966144147258587171776703005926730518438603688487721465
P = 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923
Q = 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619
# 使用SageMath求解三次方程的根
n0 =
n1 =
n2 =
primes = [n0, n1, n2]
N = n0 * n1 * n2
# 求解模平方根
def sqrt_mod_p(c, p):
if pow(c, (p-1)//2, p) != 1:
return []
return [pow(c, (p+1)//4, p), p - pow(c, (p+1)//4, p)]
roots = []
for p in primes:
roots_p = sqrt_mod_p(c, p)
roots.append(roots_p)
# 生成所有可能的组合并应用CRT
from itertools import product
for comb in product(*roots):
try:
m = crt([comb[0], comb[1], comb[2]], primes)
flag = long_to_bytes(m)
if b'flag{' in flag:
print("Flag found:", flag.decode())
break
except:
continuess0HURT
题目
from Crypto.Util.number import *
from flag import flag
class DaMie:
def __init__(self, flag , n = None):
self.m = ZZ(bytes_to_long(flag))
self.n = n if n else getPrime(1024)
self.P = Zmod(self.n)
print(f'n = {self.n}')
def process(self, x, y, z):
return vector([5 * x + y - 5 * z, 5 * y - z, 5 * z])
def Mat(self, m):
PR = self.P['x,y,z']
x,y,z = PR.gens()
if m != 0:
plana = self.Mat(m//2)
planb = plana(*plana)
if m % 2 == 0:
return planb
else:
return self.process(*planb)
else:
return self.process(*PR.gens())
def hash(self, A, B, C):
return self.Mat(self.m)(A, B, C)
if __name__ == '__main__':
Ouch = DaMie(flag)
result = Ouch.hash(2025,208,209)
print(f'hash(A,B,C) = {result}')Step 1: Calculate k = 5^m mod n
Step 2: Solve for m using the y-component equation
y-component equation: 208 * 5^m - 209 * m * 5^{m-1} = B mod n
Substituting k = 5^m, we get: 208*k - 209*m*(k/5) = B mod n
Simplify to: (208 - 209*m/5)*k = B mod n
Multiply both sides by 5 to eliminate division: (208*5 - 209*m)*k = 5*B mod n
Rearrange: 208*5*k - 209*m*k = 5*B mod n
solate m: 209*m*k = 208*5*k - 5*B mod n
m = (208*5*k - 5*B) * inverse(209*k, n) mod n
from Crypto.Util.number import long_to_bytes, inverse
# Given values from output.txt
n = 106743081253087007974132382690669187409167641660258665859915640694456867788135702053312073228376307091325146727550371538313884850638568106223326195447798997814912891375244381751926653858549419946547894675646011818800255999071070352934719005006228971056393128007601573916373180007524930454138943896336817929823
C = 93840121740656543170616546027906623588891573113673113077637257131079221429328035796416874995388795184080636312185908173422461254266536066991205933270191964776577196573147847000446118311985331680378772920169894541350064423243733498672684875039906829095473677927238488927923581806647297338935716890606987700071
B = 62503976674384744837417986781499538335164333679603320998241675970253762411134672614307594505442798271581593168080110727738181755339828909879977419645331630791420448736959554172731899301884779691119177400457640826361914359964889995618273843955820050051136401731342998940859792560938931787155426766034754760036
A = 17199707718762989481733793569240992776243099972784327196212023936622130204798694753865087501654381623876011128783229020278210160383185417670794284015692458326761011808048967854332413536183785458993128524881447529380387804712214305034841856237045463243243451585619997751904403447841431924053651568039257094910
# Step 1: Calculate k = 5^m mod n
z = 209
k = (C * inverse(z, n)) % n
# Step 2: Solve for m using the y-component equation
# y-component equation: 208 * 5^m - 209 * m * 5^{m-1} = B mod n
# Substituting k = 5^m, we get: 208*k - 209*m*(k/5) = B mod n
# Simplify to: (208 - 209*m/5)*k = B mod n
# Multiply both sides by 5 to eliminate division: (208*5 - 209*m)*k = 5*B mod n
# Rearrange: 208*5*k - 209*m*k = 5*B mod n
# Isolate m: 209*m*k = 208*5*k - 5*B mod n
# m = (208*5*k - 5*B) * inverse(209*k, n) mod n
a = (208 * 5 * k - 5 * B) % n
b = (209 * k) % n
m = (a * inverse(b, n)) % n
# Convert m to bytes to get the flag
flag = long_to_bytes(m)
print(flag)