深刻的让我意识到了自己搜索能力的不足+数学菜鸡

fl@g

源码

from Crypto.Util.number import *
from sympy import *
from tqdm import *
from secret import flag
from itertools import *
from math import factorial
import string

table = string.ascii_letters + string.digits + "@?!*"

def myprime():
    num = 0
    for i in tqdm(permutations(table) , total=factorial(len(table))):
        temp = "".join(list(i))
        if("flag" in temp or "FLAG" in temp or "f14G" in temp or "7!@9" in temp or "🚩" in temp):
            num += 1
    return nextprime(num)

m = bytes_to_long(flag)
n = myprime()*getPrime(300)
c = pow(m,65537,n)

print("n =",n)
print("c =",c)


'''
n = 10179374723747373757354331803486491859701644330006662145185130847839571647703918266478112837755004588085165750997749893646933873398734236153637724985137304539453062753420396973717
c = 1388132475577742501308652898326761622837921103707698682051295277382930035244575886211234081534946870195081797116999020335515058810721612290772127889245497723680133813796299680596
'''

排列组合，需要注意一下 flag 和 f14G ，FLAG 和 f14G 是不能进行组合的

所以一共就九种组合

flag 、f14G 、FLAG 、7!@9 、flag 和 FLAG 、flag 和 7!@9 、FLAG 和 7!@9 、f14G 和 7!@9 、flag 和FLAG和7!@9

这其实就是一个容斥定理

容斥原理核心的计数规则可以记为一句话：奇加偶减

所以：

1	f = factorial(63)4 - factorial(60)4 + factorial(57)

exp：

import libnum
from sympy import nextprime
from math import factorial

f = factorial(63)*4 - factorial(60)*4 + factorial(57)
p = f
p = nextprime(p)

e = 65537
n = 10179374723747373757354331803486491859701644330006662145185130847839571647703918266478112837755004588085165750997749893646933873398734236153637724985137304539453062753420396973717
c = 1388132475577742501308652898326761622837921103707698682051295277382930035244575886211234081534946870195081797116999020335515058810721612290772127889245497723680133813796299680596

q = n//p
phi = (p-1)*(q-1)
d = libnum.invmod(e,phi)
print(libnum.n2s(pow(c,d,n)))

# WKCTF{How_long_does_it_take_to_run_directly?}

easy_random

源码

import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

flag = b'WKCTF{}'
pad_flag = pad(flag,16)
key = random.randbytes(16)
cipher = AES.new(key,AES.MODE_ECB)
print(cipher.encrypt(pad_flag))
# b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'
with open('random.txt','w') as f:
    for i in range(2496):
        f.write(str(random.getrandbits(8))+'\n')

移步我的另一篇博客：

MT19937 实战 | W’Blog (wbuildings.github.io)

Meet me in the summer

源码

from random import choice, randint
from Crypto.Util.number import isPrime, sieve_base as primes, getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5

flag = b'WKCTF{}'
flag = pad(flag,16)
def myPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

def encrypt(key, message):
    return pow(65537, message, key)

p = myPrime(512)
q = getPrime(512)
N = p * q
m = [getPrime(512) for i in range(1024)]
enc = [encrypt(N, _) for _ in m]

a = [randint(1,2 ** 50) for i in range(70)]
b = [randint(1,2 ** 50) for i in range(50)]
secret = randint(2**119, 2**120)

ra = 1
rb = 1
for i in range(120):
    if(i < 70):
        if (secret >> i) & 1:
            ra *= a[i]
            ra %= p
    else:
        if (secret >> i) & 1:
            rb *= b[i-70]
            rb %= q


key = md5(str(secret).encode()).hexdigest()[16:].encode()
cipher = AES.new(key,AES.MODE_ECB)

with open("output.txt","w") as f:
    f.write(f'c = {cipher.encrypt(flag).hex()}\n')
    f.write(f'm = {m}\n')
    f.write(f'enc = {enc}\n')
    f.write(f'a = {a}\n')
    f.write(f'b = {b}\n')
    f.write(f'ra = {ra}\n')
    f.write(f'rb = {rb}\n')

先求N

原理：

My-CTF-Challenges/ImaginaryCTF/Round 26/no_modulus/README.md at master · maple3142/My-CTF-Challenges · GitHub

对于

$enc_i = 65537^{m_i} \bmod N $

我们总可以找到一组线性组合

$\sum_{i=0}^{n-1} a_ie_i=0$

令

$\prod_{i=0}^{n-1}c^{a_i}=m^{e_ia_i}=m^0 = 1 \pmod N$

构建格子：

$(a_0~~a_1~~\dots~~a_{n-1})\begin{bmatrix} 1 & & & & Ke_0\\ & 1 & & & Ke_1 \\ & & \ddots & &\vdots \\ & & & 1 & Ke_{n-1} \end{bmatrix}=(a_0~~a_1~~\dots~~a_{n-1}~~0)$

K 取足够大即可

$a_i$有正有负，甚至负数居多，所以

$\prod_{i=0}^{n-1}c^{a_i}$

会是个有理数，可用分数$\frac{x}{y}$表示，那么就存在：

$\frac{x}{y} \equiv1 \pmod N => x-y \equiv 0 \pmod N$

找到两个 a 就有 $N = \gcd(x_0-y_0,x_1-y_1)$

with open('output.txt','r') as f:
    f = f.readlines()

m = eval(f[1].strip().split('=')[-1])
enc = eval(f[2].strip().split('=')[-1])

# 数取少点，减少运算量
m = m[:100]
enc = enc[:100]

n = len(m)
L = Matrix(ZZ,n,n+1)
K = 2^512
for i in range(n):
    L[i,i] = 1
    L[i,-1] = K*m[i]

L = L.LLL()

# 最后一个数不取
xx = product([ZZ(y) ^ x for x, y in zip(L[0][:-1], enc)])
yy = product([ZZ(y) ^ x for x, y in zip(L[1][:-1], enc)])

N = gcd(xx.numer() - xx.denom(), yy.numer() - yy.denom())
print(N)

# 3365950545896839807600753681439061096312578337873460615427103468443333055935222147455641892341798604350037357999848711970084367398055755047567367304166808830853176966914407772226194410114093800191521813038405295729046243670270181161836427221727870133145321390846488824416000038564306005700271206427983462394735137

根据 p 的构造方式，可知 p -1 光滑，可以分解 N

import gmpy2

N = 3365950545896839807600753681439061096312578337873460615427103468443333055935222147455641892341798604350037357999848711970084367398055755047567367304166808830853176966914407772226194410114093800191521813038405295729046243670270181161836427221727870133145321390846488824416000038564306005700271206427983462394735137

def Pollards_p_1(N):
    a = 2
    n = 2
    while True:
        a = pow(a, n, N)
        res = gmpy2.gcd(a - 1, N)
        if res != 1 and res != N:
            return res
        n += 1

p = Pollards_p_1(N)
q = N // p
print(f"p = {p}")
print(f"q = {q}")
"""
p = 266239931579101788237217833822346198682539336616234011732898866661722928035386747695230192006141430294833011494452114878744414084025005167432139516382471637567
q = 12642545864299817932696528548195775137854645688987690739317393212595731628016420449974358672452504599152386464349500792607469701592216257829464295238775711

"""

求 secret的低位

密码学学习笔记之 knapsack | Van1sh的小屋 (jayxv.github.io)

因为 p-1 光滑，所以对于解决 dlp 问题有利，既如此，此题我们可以通过 dlp 将乘法背包映射成加法背包，需要注意的是，取对数之后模数应该变为 p-1

$ra=a_0k_{69}·a_1k_{68}· ~~~ \dots ~~ ·a_{69}k_0 \pmod p，k_i\in(0,1)$

随便取一个生成元 g ，两边取对数

$\log_{g}{ra} = \log_{g}{a_0k_{69}}+\log_{g}{a_1k_{68}}+\dots+\log_{g}{a_{69}k_{0}} \pmod{p-1}，k_i\in(0,1)$

就是我们常见的加法背包了

构造格子，优化：

$(k_{69}~~k_{69}~~\cdots~~k_0~~l~~-1)=\begin{bmatrix} 2 & 0 & \dots & 0 & 0 & \log_{g}{a_0}\\ 0 & 2 & \dots & 0 & 0 & \log_{g}{a_1}\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & \dots & 2 & 0 & \log_{g}{a_{69}}\\ 0 & 0 & \dots & 0 & 1 & p-1\\ 1 & 1 & \dots & 1 & 1 & \log_{g}{ra} \end{bmatrix}=(2k_{69}-1 ~~ 2k_{69}-1~~\cdots~~ 2k_0-1~~l-1~~ 0)$

a = [810922431519561, 446272766988725, 167807402211751, 137130339017755, 214986582563833, 141074297736993, 1116944910925939, 827779449967114, 887541522977945, 698795918391810, 180874459256817, 42309568567278, 148563974468327, 43541894027392, 369461465628947, 226728238060977, 902554563386031, 369980733296039, 495826170604031, 202556971656774, 1124261777691439, 533425503636189, 393536945515725, 242107802161603, 506637008093239, 846292038115984, 686372167052341, 923093823276073, 557898577262848, 719859369760663, 51513645433906, 946714837276014, 24336055796632, 302053499607130, 970564601798660, 1082742759743394, 499339281736843, 13407991387893, 667336471542364, 38809146657917, 29069472887681, 420834834946561, 1044601747029985, 854268790341671, 918316968972873, 737863884666895, 1036231016223653, 792781009835942, 142149344663288, 828341073371968, 186470549619656, 279923049419811, 487848895651491, 737257307326881, 1065005635075133, 628186519179693, 554767859759026, 606623194910240, 497855707815081, 88176594691403, 278020899501967, 440746393631841, 921270589876795, 800698974218498, 437669423813782, 717945417305277, 191204872168085, 791101652791845, 772875127585562, 174750251898037]
ra = 215843182933318975496532456029939484729806294336845406882490936458079210569046120528327121994744424727894554328344229010979127024288283698486557728305231262446
p = 266239931579101788237217833822346198682539336616234011732898866661722928035386747695230192006141430294833011494452114878744414084025005167432139516382471637567

F = GF(p)
g = F.primitive_element() 	#获取原根g

tmp = discrete_log(mod(ra,p),mod(g,p))
n = len(a)
A = [discrete_log(mod(a[i],p),mod(g,p)) for i in range(n)]

d = n / log(max(A), 2)
print(CDF(d))
assert CDF(d) < 0.9408

L = Matrix(ZZ,n+2,n+2)
for i in range(n):
    L[i,i] = 2
    L[i,-1] = A[i]
    L[-1,i] = 1

L[-1,-2] = 1
L[-2,-2] = 1
L[-2,-1] = p-1
L[-1,-1] = tmp

for line in L.BKZ(block_size = 30):    # LLL 也行，
    if line[-1] == 0:
        t = ''
        for i in line[:-2]:
            if i == 1:
                t+= '0'   # 我以为这里是+1呢，可以反过来试试
            if i == -1:
                t+= '1'
    if len(t) == 70:
        print(t[::-1])
        break

# 1100100011000011000001010101000010111110000001000010101010100100011011

再求secret的高位

这次使用中间相遇攻击（MITM），顺带学习了波字典的用法

这是一种思想，并不固定于某个板子，，移步

中间相遇攻击 - MITM - CTF Wiki (ctf-wiki.org)

练习题： （2024国赛 hash）

2024CISCN | DexterJie’Blog

同上：

$rb=b_0k_{49}·b_1k_{48}· ~~~ \dots ~~ ·b_{49}k_0 \pmod q，k_i\in(0,1)$

记

$t_1 = b_0k_{49}·b_1k_{48}· ~~~ \dots ~~ ·b_{24}k_{25} \pmod q$ $t_2 = b_{25}k_{24}·b_{26}k_{23}· ~~~ \dots ~~ ·b_{49}k_{0} \pmod q$

那么 $rb = t_1*t_2 \bmod q $

我们可以通过验证 $rb*t_2^{-1}$ 是否等于 $t_1$ 来进行中间相遇攻击

$rb*t_2^{-1}=t_1 \bmod q$

from tqdm import *
from Crypto.Util.number import *

q = 12642545864299817932696528548195775137854645688987690739317393212595731628016420449974358672452504599152386464349500792607469701592216257829464295238775711
rb = 3498090364718786308911989083689617571932166777012900779070629523727655934582351599924963383902292211754876835801399401170701861988033911802302715724060488
b = [919042075929804, 731196114348957, 780418394368709, 3413259132589, 766847233992470, 297211103941610, 500281126810865, 849501916345269, 117720599611510, 551153334471840, 1072866601658568, 829727438821072, 179087882377496, 934984220634910, 670865352770561, 153859069714096, 600663927005680, 540242857915696, 553340712407662, 1113968197194611, 272342861356660, 1117828067970844, 796048575670909, 454054034318932, 654225458148223, 183717820875099, 1064983259059879, 737236143792316, 565414872646761, 550812923748544, 467970413493147, 764197477914194, 572611266860917, 74578187275404, 462057895458922, 594841925406302, 178813973628003, 607180532395162, 455598995678785, 227757559710253, 178207804255926, 982118016357442, 286821935441865, 947088152152874, 592190023483880, 686189038585889, 701809424042029, 610206451919836, 189925081438758, 108664403267133]

print(b[0].bit_length())   # 50

dic = {}

for secret in trange(2**24,2**25):
    t1 = 1
    for i in range(25):
        if (secret >> i) & 1:
            t1 *= b[i]
            t1 %= q
    dic[t1] = secret

for secret in trange(2 ** 24, 2 ** 25):
    t2 = 1
    for i in range(25):     
        if (secret >> i) & 1:
            t2 *= b[i+25]
            t2 %= q
            
    tmp = rb * inverse(t2,q) % q    # mod q
    if tmp in dic.keys():
        print('low_25 = ',bin(dic[tmp])[2:])
        print('high_25 = ',bin(secret)[2:])
        break

# low_25 =  1011111010011011011100010
# high_25 =  1100010001001011111001111

AES

from hashlib import md5
from Crypto.Cipher import AES

c = 'dc6ba0123102f13a60ec4488d917a53a3c9b61372f39b977e93027fcb735eac38ceea2c0a7d5d6baf3570eea05200ce0'
low = '1100100011000011000001010101000010111110000001000010101010100100011011'
low_25 = '1011111010011011011100010'
high_25 = '1100010001001011111001111'

high = high_25+low_25
secret = int(high+low,2)
c = bytes.fromhex(c)

key = md5(str(secret).encode()).hexdigest()[16:].encode()
cipher = AES.new(key,AES.MODE_ECB)
print(cipher.decrypt(c))

# WKCTF{Hell0_CTFer_Th1s_the_5ignin_fl4g.}

Faas

源码

from Crypto.Util.number import *

flag = b''
p = getPrime(256)
q = getPrime(256)
n = p*q
e = 0x10001
# print(p,q)
print(n)
print(pow(bytes_to_long(flag), e, n))

'''
6307087428677736357497034459737970959152896262793715778296915427469297166787112126441383726582076126245773277476143478349256813717514008533538716513810511
5311161002667378270287698542067235931405307317925963294522517859778084164120335331513838215353575415471218414362372788855224259598970138214133452539914210
'''

什么？这题要花六百块才能拿到flag！？

听话，花钱的flag咱不要

算了，标记一下，万一以后有需求呢

GitHub - eniac/faas: Factoring as a Service

reference

WKCTF2024 | Zimablue’ Blog

WKCTF | DexterJie’Blog

W'Blog

WKCTF 2024