easymath

解这题目怎么感觉回到了高中

easymath.py

先解出三个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:
        continue

ss0HURT

题目

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)