CSACTF2025

ezCrypto

首先，这道题前几天我做过类似的：CryptoHack – Modular Arithmetic - Modular Binomials

化简：

\[\begin{cases} c_1 \equiv (7p+2q)^{e_1} & (\operatorname{mod}N) \\ c_2 \equiv (5p+3q)^{e_2} & (\operatorname{mod}N) \end{cases} \Longrightarrow \begin{cases} c_1 \equiv (7p)^{e_1}+(2q)^{e_1} & (\operatorname{mod}N) \\ c_2 \equiv (5p)^{e_2}+(3q)^{e_2} & (\operatorname{mod}N) \end{cases} \Longrightarrow \begin{cases} c_1^{e_2}5^{e_1e_2} \equiv (35p)^{e_1e_2}+(10q)^{e_1e_2} & (\operatorname{mod}N) \\ c_2^{e_1}7^{e_1e_2} \equiv (35p)^{e_1e_2}+(21q)^{e_1e_2} & (\operatorname{mod}N) \end{cases}\]

\[ \Longrightarrow d = (21^{e_1e_2}-10^{e_1e_2})q^{e_1e_2} \equiv 7^{e_1e_2}c_2 ^{e_1}-5^{e_1e_2}c_1^{e_2} (\operatorname{mod}N)\]

所以只需要计算\(gcd(d,N)\)即可得到\(q\).

payload:

import hashlib
import itertools
import string
import re
import gmpy2
import math
from pwn import *
import numpy as np
from math import isqrt, gcd
from fractions import Fraction
from Crypto.Util.number import long_to_bytes, bytes_to_long
import sympy
from Crypto.Cipher import AES
from Crypto.Util.number import *

e1 = 9993078339649918633394551494432099987489636970426459609511857467341547586587525392554182350765642296219526020856710856746033936605501022624688690300688439
e2 = 9862231551884468205315488646474297306588640159481717035401356860971981714476971478488573347081320483033055786493180165517487943548799848155409701594695241

c  = 55901802262435214617666003592762988475817677710371853541720344698764787306707874639847782579629332096055942013026505176416985974919479004417458085456394043275360903171536103053583251790628518753952543060780848158606515610299846413376493573042907292759220155160589910184410059973310831818961560671734593013630
c1 = 40229355340269257739770896034955847330470882389629386052431564363238466271625576412466245834179497302499769847960940723672643383320214407820912062076710617921419054040241577412851511347542787094945856317937066896047259364036219750643961105485688761317530941590187661063644339339132904752238067549935799782571
c2 = 108652869706106291871386712591832466805988235376235028871549478999408715358581148050182998755845373693039547262558657853346202467672844967103554943949936653904766808010459876413771263811562198412823905652758929593346690671565576513949878548572013852099780538278374113587286504177003549471221734542094445566120
N  = 123839153520968617938577833129088685928809498127935146762079913125478804855691345286939880475076303747964774752204834042336906860535767909827360494225337089627632868095483264748780029629372118516765073006866472031753085514995841735096285162728251392742484862333235342283728891342849728490662261106037625078371
d0 = pow(7,e1*e2,N)*pow(c2,e1,N) - pow(5,e1*e2,N)*pow(c1,e2,N)

p = gcd(d0,N)
q = N//p
print(f"{p},{q}")
e = 65537
assert gmpy2.is_prime(p)
assert gmpy2.is_prime(q)
assert p * q == N

phi = (p-1)*(q-1)

d = gmpy2.invert(e,phi)
m = pow(c,d,N)
print(m)
flag = long_to_bytes(m)
print(flag)
# 然后丢到cyberchef里面！！！犯傻了错失三血

flag: CSACTF{Go0d_JoB!_We1C0mE_t0_oUR_csACtF_2o25!}

babyRSA

先看problem：

Problem

from Crypto.Util.number import *
from secret import flag
import gmpy2

m = bytes_to_long(flag[:19])

p = getPrime(1024)
q = getPrime(1024)
N = p * q
phin = (p - 1) * (q - 1)
e = 0x10001
d = gmpy2.invert(e, phin)
print(d - p)
print(pow(m, e, N))
print(N)
# 2551756296230556455153461142256558662892670316950235756205055813974596327809845104526723991103791519643650309481773430116596445056621314003219883178059757998882818276435859354707327583130042659575327825768326628051521469996692935342698707595506169488367250369701727437051651180572487178040011110411554700942787226887828691419928759312983854249497569715361729302927781514981880654479059321530075054979991662440146179410101287675885973372091690923001774040638576268604000902523671010492732048209337569176535938725020523648350397601225455506699505240572770233601345289329527790660324779363188244080506367846538941254260
# 15971309396256835362531485951128166983206687537714027537858621542505837518266962953113283078076889299992766766084018288988406699208913051384679790264007098624219450206475206014672536932788204025908959226423862863105445190794751238955057213166812828836859124836604576681535267728522357997298297456365207788184878644031601919916837973507434190104725947258940723229288878807644645051813848097692257981034447284379832096671294140741904947037566307085602107241375721489415120904300455359620297677533606229298114263489015021336257788565359759312693790170999715775553831478938083873456866209473156243356364882697055947038033
# 17154010912510203959523272425896818657297869993021602292995255193399642992683743831712781844801434487935779088368754260903824107054650841709818595121602457685176250013619541956042068706082019261523054643284318619613556526738461883634674858927755444636283155962574839577603247863491547049667474422304037381854670052998349971200044078692166792550323925980836302324144231971216224668698971348394532478457497878076908606080048700669391473735992839985369965723367504239067817263161028103823044373957891549372409108859137498344836594151291454836621683376821160950429180536440623985341901524194163420366533633759132239742143


m = bytes_to_long(flag[19:])

p = getStrongPrime(1024)
q = gmpy2.next_prime(p ^ ((1 << 900) - 1))
n = p * q
e = 0x10001

c = pow(m, e, n)
print(hex(n))
print(hex(c))
# 0x979b0d5014e3e0b01091d5cd145c5c62f027da4592f71dbbcf114e9e94d56632832fb57a0e27d581bd86be6ef5a019781edef8e35dab664eb46efa67bdcf1b3abf5de2f21d125d6559493d7b7460f33387fc1c38329fd60c9e69803f74bb645cf11d674585b86ad9c966d0ca6fafdcf8c0c7eaddca396ab5b3a21a8ae261fa7e1915f618593352f2d7efd8eba8d1fd80074fbd66999e86bc8417761daecf2a9c446a9db93e691f277cffe870d2b781c305a9ceb71bd4191cb733f6377b7d123aa7e86e0519b484e347fb0307fc468c8006a66452a5ae90046a43ecb17fe4480aa39ca7674cbd88d837c0902c32a109b67a3d91e5ffa4cd3fbeaf305335fae207
# 0x82f76dce83c5156bfb205e173372c9bc074155f0548975b0bd1ea4b258e2262e8612a29331602f952e598439c6651b27d7d75822040101994fcae8120f3fe5cc2df49f221843dd02c1b14c91ea24ad51cdf7cbcd8e4961c2e03045642257365dfabeb873de2a7ea4c1e1c69e975d644fa015f0dbb149bbe99b7c592465ae5effd3cc0405ebe7dde2ec401d19d73d4c41259fc7823c060af95c20e3f553b075b7a29af786957917a45bcf5ac9196ddb87e3e78bf63f9b9d705676759effe111301b8b23d8f4aeafd8f5a337a7cc982ed306f0fb2132078a8da3de543ad14a15d74c9cc19a4a57818f9611681e023919da1832dc883d1bac97130c4dbb7b60dda

两个部分分别分析：

writeup-sage

from Crypto.Util.number import long_to_bytes

X1 = 2551756296230556455153461142256558662892670316950235756205055813974596327809845104526723991103791519643650309481773430116596445056621314003219883178059757998882818276435859354707327583130042659575327825768326628051521469996692935342698707595506169488367250369701727437051651180572487178040011110411554700942787226887828691419928759312983854249497569715361729302927781514981880654479059321530075054979991662440146179410101287675885973372091690923001774040638576268604000902523671010492732048209337569176535938725020523648350397601225455506699505240572770233601345289329527790660324779363188244080506367846538941254260
C1 = 15971309396256835362531485951128166983206687537714027537858621542505837518266962953113283078076889299992766766084018288988406699208913051384679790264007098624219450206475206014672536932788204025908959226423862863105445190794751238955057213166812828836859124836604576681535267728522357997298297456365207788184878644031601919916837973507434190104725947258940723229288878807644645051813848097692257981034447284379832096671294140741904947037566307085602107241375721489415120904300455359620297677533606229298114263489015021336257788565359759312693790170999715775553831478938083873456866209473156243356364882697055947038033
N1 = 17154010912510203959523272425896818657297869993021602292995255193399642992683743831712781844801434487935779088368754260903824107054650841709818595121602457685176250013619541956042068706082019261523054643284318619613556526738461883634674858927755444636283155962574839577603247863491547049667474422304037381854670052998349971200044078692166792550323925980836302324144231971216224668698971348394532478457497878076908606080048700669391473735992839985369965723367504239067817263161028103823044373957891549372409108859137498344836594151291454836621683376821160950429180536440623985341901524194163420366533633759132239742143
e = 0x10001

print("[*] 正在破解第一部分...")
R.<p> = PolynomialRing(ZZ)
for k in range(1, e):
    f = (e + k)*p^2 + (e*X1 - k*N1 - k - 1)*p + k*N1
    roots = f.roots()
    if roots:
        p_val = int(roots[0][0])
        print(p_val)
        if N1 % p_val == 0:
            d1 = int(inverse_mod(e, (p_val-1)*(N1//p_val-1)))
            m1 = pow(C1, d1, N1)
            part1 = long_to_bytes(int(m1))
            print(f"Part 1: {part1.decode()}")
            break

print("[*] 正在破解第二部分...")

from Crypto.Util.number import long_to_bytes

N2 = 0x979b0d5014e3e0b01091d5cd145c5c62f027da4592f71dbbcf114e9e94d56632832fb57a0e27d581bd86be6ef5a019781edef8e35dab664eb46efa67bdcf1b3abf5de2f21d125d6559493d7b7460f33387fc1c38329fd60c9e69803f74bb645cf11d674585b86ad9c966d0ca6fafdcf8c0c7eaddca396ab5b3a21a8ae261fa7e1915f618593352f2d7efd8eba8d1fd80074fbd66999e86bc8417761daecf2a9c446a9db93e691f277cffe870d2b781c305a9ceb71bd4191cb733f6377b7d123aa7e86e0519b484e347fb0307fc468c8006a66452a5ae90046a43ecb17fe4480aa39ca7674cbd88d837c0902c32a109b67a3d91e5ffa4cd3fbeaf305335fae207
C2 = 0x82f76dce83c5156bfb205e173372c9bc074155f0548975b0bd1ea4b258e2262e8612a29331602f952e598439c6651b27d7d75822040101994fcae8120f3fe5cc2df49f221843dd02c1b14c91ea24ad51cdf7cbcd8e4961c2e03045642257365dfabeb873de2a7ea4c1e1c69e975d644fa015f0dbb149bbe99b7c592465ae5effd3cc0405ebe7dde2ec401d19d73d4c41259fc7823c060af95c20e3f553b075b7a29af786957917a45bcf5ac9196ddb87e3e78bf63f9b9d705676759effe111301b8b23d8f4aeafd8f5a337a7cc982ed306f0fb2132078a8da3de543ad14a15d74c9cc19a4a57818f9611681e023919da1832dc883d1bac97130c4dbb7b60dda
mask = (1 << 900) - 1

# 在模 2^900 下寻找 p
# 由于 q = p ^ mask + k (k很小)，在低位 mask 内，p ^ mask 等价于 mask - p (当 p 的位全为0时)
# 实际上位运算规律为：p * (p ^ mask + k) = n mod 2^900
# 在模 2 下，这可以简化为关于 p 的二次方程

import math
from Crypto.Util.number import long_to_bytes

def main(n, c):
    e = 0x10001
    base = 2**900
    N_low = n % base

    found = False
    p_val = None
    q_val = None

    for k in range(1, 10000, 2):
        solutions = [1]
        for m in range(2, 901):
            new_solutions = []
            for b0 in solutions:
                f_val = b0*b0 + b0*(1 - k) + N_low
                if f_val % (2**(m-1)) != 0:
                    continue
                c_val = f_val // (2**(m-1))
                if c_val % 2 == 0:
                    new_solutions.append(b0)
                    new_solutions.append(b0 + 2**(m-1))
            solutions = new_solutions
            if not solutions:
                break

        if not solutions:
            continue

        for b in solutions:
            d = base - 1 - b + k
            C = b * d - n
            D = (base - 1 + k)**2 - 4 * C
            root = math.isqrt(D)
            if root * root != D:
                continue
            A = (- (base - 1 + k) + root) // 2
            if A % base != 0:
                continue
            p = A + b
            if n % p == 0:
                p_val = p
                q_val = n // p
                found = True
                break
        if found:
            break

    if not found:
        print("Failed to factor n")
        return

    phi = (p_val - 1) * (q_val - 1)
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    print(flag.decode())

if __name__ == '__main__':
    main(N2, C2)

babyLFSR

本来只是想习惯性地打开CTF Wiki学一下这个LFSR（实则是NFSR，前几天看到这个知识点但来不及学了）

结果谁知道writeup是现成的（摊手）：

非线性反馈移位寄存器 - CTF Wiki

【复现】强网杯-StreamGame3-Writeup – Rhy7hm

与2018强网杯的题目甚至是一样的，就不重复写了.