MOwORN's blog

2025ISCTF_Crypto

发布于 2025-12-16 | 22分钟 | 4397字数

2025ISCTF - Crypto

easy_RSA

加密源码比较短，主要就是有这个：（式1）

ct2≡msgp+q  mod Nct2 \equiv msg^{p+q}\ \ mod\ N

依据欧拉定理知：

msg(p−1)(q−1)≡1  mod Nmsg^{(p-1)(q-1)} ≡ 1\ \ mod\ N

因此有：（式2）

msgN−(p+q)+1≡1  mod Nmsg^{N-(p+q)+1} ≡ 1\ \ mod\ N

由式1和式2可知：

msgN+1≡ct2  mod Nmsg^{N+1} ≡ ct_2\ \ mod\ N

同时知道：

msge≡ct1  mod Nmsg^{e} ≡ ct_1\ \ mod\ N

而根据扩展欧几里得算法可知，存在整数a和整数b使得：（式3）

a(N+1)+b⋅e=gcd((N+1),e)=1a(N+1)+b·e=gcd((N+1), e)=1

由此构造：

{msga(N+1)≡ct2a  mod Nmsgb⋅e≡ct1b  mod N\begin{cases} msg^{a(N+1)} ≡ ct_2^a\ \ mod\ N\\ msg^{b·e} ≡ ct_1^b\ \ mod\ N \end{cases}

于是有：

msga(N+1)+b⋅e≡ct2a⋅ct1b  mod Nmsg^{a(N+1)+b·e} ≡ ct_2^a·ct_1^b\ \ mod\ N

因此根据式3可得：

msg≡ct2a⋅ct1b  mod Nmsg ≡ ct_2^a·ct_1^b\ \ mod\ N

解密脚本：

from Crypto.Util.number import long_to_bytes
from gmpy2 import *

N = 17630258257080557797062320474423515967705950026415012912087655679315479168903980901728425140787005046038000068414269936806478828260848859753400786557270120330760791255046985114127285672634413513991988895166115794242018674042563788348381567565190146278040811257757119090296478610798393944581870309373529884950663990485525646200034220648901490835962964029936321155200390798215987316069871958913773199197073860062515329879288106446016695204426001393566351524023857332978260894409698596465474214898402707157933326431896629025197964209580991821222557663589475589423032130993456522178540455360695933336455068507071827928617
ct1 = 5961639119243884817956362325106436035547108981120248145301572089585639543543496627985540773185452108709958107818159430835510386993354596106366458898765597405461225798615020342640056386757104855709899089816838805631480329264128349465229327090721088394549641366346516133008681155817222994359616737681983784274513555455340301061302815102944083173679173923728968671113926376296481298323500774419099682647601977970777260084799036306508597807029122276595080580483336115458713338522372181732208078117809553781889555191883178157241590455408910096212697893247529197116309329028589569527960811338838624831855672463438531266455
ct2 = 11792054298654397865983651507912282632831471680334312509918945120797862876661899077559686851237832931501121869814783150387308320349940383857026679141830402807715397332316601439614741315278033853646418275632174160816784618982743834204997402866931295619202826633629690164429512723957241072421663170829944076753483616865208617479794763412611604625495201470161813033934476868949612651276104339747165276204945125001274777134529491152840672010010940034503257315555511274325831684793040209224816879778725612468542758777428888563266233284958660088175139114166433501743740034567850893745466521144371670962121062992082312948789

e = 65537
c = N + 1

_, b, a = gmpy2.gcdext(e, c)
m = (powmod(ct1, b, N) * powmod(ct2, a, N)) % N
print(long_to_bytes(m))
image-20251204201049388

Power tower

首先分析加密代码：

from Crypto.Util.number import *
import random
from numpy import number

m = b'ISCTF{****************}'
flag = bytes_to_long(m)
n = getPrime(256)       # 256位随机数
t = getPrime(63)        # 63位随机数
l = pow(2,pow(2,t),n)       # l是2的(2的t次方)模n
c = flag ^ l        # 异或过后的flag
print(t)
print(n)
print(c)

'''
t = 6039738711082505929
n = 107502945843251244337535082460697583639357473016005252008262865481138355040617
c = 114092817888610184061306568177474033648737936326143099257250807529088213565247
'''

由于异或的异或还是其自身，因此到这边我还在想，“不就异或一下的事吗？那多简单”

因此写出了下面的脚本：

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

t = 6039738711082505929
n = 107502945843251244337535082460697583639357473016005252008262865481138355040617
c = 114092817888610184061306568177474033648737936326143099257250807529088213565247

m = c ^ (pow(2,pow(2,t),n))

print(long_to_bytes(m).decode(errors='ignore'))

然而，上面这个脚本有个问题：由于t实际上很大，因此 pow(2,t) 难以在有限时间内算出。

因此这边就得用到题目提示的 扩展欧拉定理 ：

存在：

ma  mod nm^a\ \ mod\ n

假如 m和n互质 ，则有：

ma≡ma  mod φ(n)  mod nm^a\equiv m^{a\ \ mod\ φ(n)}\ \ mod\ n

这样能够解决某些大指数的模幂运算问题。

因此先用factordb分解一下n：

image-20251201143117072

这样我们能求出其欧拉函数值。

然后修改一下脚本：

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

t = 6039738711082505929
n = 107502945843251244337535082460697583639357473016005252008262865481138355040617
c = 114092817888610184061306568177474033648737936326143099257250807529088213565247
assert gcd(2, n) == 1

phi_n = 126*841705194006*1005672644717572752052474808610481144121914956393489966622615552

m = c ^ (powmod(2, powmod(2, t, phi_n), n))

print(long_to_bytes(m).decode(errors='ignore'))

运行可得flag：

image-20251201143149844

小蓝鲨的LFSR系统

首先分析一下脚本：

import secrets
import binascii

def simple_lfsr_encrypt(plaintext, init_state):
    mask = [random.randint(0,1) for _ in range(128)]        # mask是随机的128位数
    
    state = init_state.copy()
    for _ in range(256):
        feedback = sum(state[i] & mask[i] for i in range(128)) % 2      # mask和state每一位对位做与运算，相加后模2
        state.append(feedback)      # 上面的运算重复256次（这边LFSR代码貌似有问题，忘记抽掉state的第一位了）
    
    key = bytes(int(''.join(str(bit) for bit in mask[i*8:(i+1)*8]), 2)      # 每8位2进制转10进制，再转字节流。最终应该是16字节
               for i in range(16))
    
    keystream = (key * (len(plaintext)//16 + 1))[:len(plaintext)]       # 密钥流的生成就是循环填充key直到和明文一样长
    return bytes(p ^ k for p, k in zip(plaintext, keystream)), mask     # 返回明文和密钥流异或的结果，并且返回mask

于是我们可以先获取移位前的128位state和移位后的128位state，拼成256位的二进制串：

initState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
outputState = [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1]

stream = ''

for i in range(128):
    stream += str(initState[i])

for i in range(128):
    stream += str(outputState[i])

print(stream)

然后就可以套用下面sage脚本来求解出flag：

def solve_lfsr_direct(sequence, length=128):
    F = GF(2)

    # 构建线性方程组
    A = []
    b = []

    for i in range(length):
        # 每个方程对应 sequence[i+length] = sum(mask[j] * sequence[i+j])
        row = sequence[i:i + length]
        A.append(row)
        b.append(sequence[i + length])

    A_matrix = matrix(F, A)
    b_vector = vector(F, b)

    try:
        mask_solution = A_matrix.solve_right(b_vector)
        return mask_solution
    except:
        return None


F = GF(2)
bits = [F(int(i)) for i in '0101100110000100100011100110110100101010010110101111111101101001101010000011010100011111110110101001111001111010110100000011010000011000001010010011110111000110010001011111011001010110111011001000011000001011011010000100001000000000111100100110110110000011']  # 两段输出流拼起来

# 使用直接求解
mask_vector = solve_lfsr_direct(bits)
if mask_vector is not None:
    mask_str = ''.join(str(int(bit)) for bit in mask_vector)
    print(mask_str)
image-20251201190150449

然后我们可以把这段mask转为密钥流，和密文做异或得到明文：

from pwn import *

mask = '00000010011010001010001000110001111001101101101110000001101100000100100111111010101011100010100111011101001110110101001000101101'
ciphertext = bytes.fromhex('4b3be165a0a0edd67ca8f143884826725107fd42d6a6')

key = bytes(int(''.join(str(bit) for bit in mask[i * 8:(i + 1) * 8]), 2) for i in range(16))        # 每8位2进制转10进制，再转字节流。最终应该是16字节

keystream = (key * (len(ciphertext) // 16 + 1))[:len(ciphertext)]
for i in range(len(ciphertext)):
    print(xor(ciphertext[i], keystream[i]).decode(), end='')
image-20251216163325091

小蓝鲨的RSA密文

首先分析一下代码：（这边直接把output.txt结合进来了）

import json, secrets
from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

e = 3       # 可能可以利用
N = getPrime(512) * getPrime(512)
# N = 121288600621198389662246479277632294800423697823363188896668775456771641807233781416525282234787873435904747571468452950479817935684848143651716343606633656969395065588423982440884464542428742861388200306417822228591316703916504170245990423925894477848679490979364923848426643149659758241239900845544537886777

LOW_BITS = 16       # 这个位数比较少，65537，可以爆破，可以假设a2已知
a2_high = a2 >> LOW_BITS
# a2_high = 9012778

aes_key = secrets.token_bytes(16)      # m貌似不大
m = bytes_to_long(aes_key)

f = a2 * (m * m) + 621315 * m + 452775142

c = (pow(m, e) + f) % N
# c = 3756824985347508967549776773725045773059311839370527149219720084008312247164501688241698562854942756369420003479117 ，这边C的位数也异常的少，看来是设计过的

iv = secrets.token_bytes(16)
# iv = bf38e64bb5c1b069a07b7d1d046a9010
cipher = AES.new(aes_key, AES.MODE_CBC, iv=iv)
ct = cipher.encrypt(pad(FLAG, 16))
# ct = 8966006c4724faf53883b56a1a8a08ee17b1535e1657c16b3b129ee2d2e389744c943014eb774cd24a5d0f7ad140276fdec72eb985b6de67b8e4674b0bcdc4a5

首先发现，模数N是1024位的，但由于密钥m仅有128位，导致生成的密文c 远小于N（这也就是为什么c看上去比N小那么多，大概率还是没模上），于是可忽略模运算。

然后，题目中的a2只有低16位未知，不大，可以爆破。

然后针对每一个可能的a2，看能不能解出整数的m，如果是，就试试看，做成AES密钥解密密文。

写脚本解密：

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from sympy import *
from tqdm import tqdm

m = symbols('m')
for a2_low in tqdm(range(0, 65536)):
    res = solve((m * m * m + ((9012778 << 16) + a2_low) * (m * m) + 621315 * m + 452775142 - 3756824985347508967549776773725045773059311839370527149219720084008312247164501688241698562854942756369420003479117), (m))
    if res[0].is_integer:       # 假如得到整数解
        print(f"a2_low={a2_low}, m={res[0]}")
        break

iv = bytes.fromhex('bf38e64bb5c1b069a07b7d1d046a9010')
aes_key = long_to_bytes(res[0])
ct = bytes.fromhex('8966006c4724faf53883b56a1a8a08ee17b1535e1657c16b3b129ee2d2e389744c943014eb774cd24a5d0f7ad140276fdec72eb985b6de67b8e4674b0bcdc4a5')
cipher = AES.new(aes_key, AES.MODE_CBC, iv=iv)
message = cipher.decrypt(ct)
print(message.decode(errors='ignore'))

爆破一段时间后获得flag：

image-20251216115333047

小蓝鲨的密码箱

说是规律题，于是我先做了一点尝试。

首先是，a、b、c都不能等于0，可能是为了规避某些漏洞。

然后，我做了下面尝试：

image-20251204150749525
image-20251204150804608
image-20251204150842538
image-20251204151025338

这边能观察到第一个结论：

当a=b=1时，所有密文的值必然非负且小于c！

那我暂且就定c为256了，两个十六进制位能表示的最多就256个数，正好。

然后我做了下面尝试：

image-20251204151129750
image-20251204151148856

观察到更多结论：

加密是逐字符的
单个字符的加密结果与其处在明文中的位置无关

这边突发奇想写入了ASCII码33~126的字符：

image-20251204151326877

于是得出关键结论：

密文就是明文逐字符取ASCII码再加1

于是提取上面这个flag密文直接做解密：

c = '4a544455477c6365313a316365352e323962322e3562663a2e39333a652e6467653166383731396333627e'

for i in range(0, len(c), 2):
    temp = int(c[i:i+2], 16) - 1
    print(chr(temp), end='')
image-20251204152056572

小蓝鲨的费马谜题

代码分析大致如下：

import random
import math

p = get_prime(1024)
q = get_prime(1024)
n = p * q
e = 65537

m = bytes_to_long(flag)
c = pow(m, e, n)
# 到这边都是普通RSA加密流程

bases = get_primes_up_to(100)       # 这边貌似是生成一个元素很多的列表，列表中的元素都是100以内的素数，元素可能重复出现

hints = []
for i in range(len(bases)):
    for j in range(i+1, len(bases)):
        hint_value = (pow(bases[i], p-1, n) + pow(bases[j], p-1, n)) % n        # 从素数列表中选取两个素数，分别附加(p-1)指数并模n然后相加
        hints.append((bases[i], bases[j], hint_value))      # 这边的内容在txt中展示了

这边通过观察txt可发现，一共有50组hint。并且在txt末尾有一个提示，提示我们通过分解n的方式来解这道题。

这边hint的结构大致是这样的：

hint≡(b1p−1 % n)+(b2p−1 % n)  mod nhint\equiv (b_1^{p-1}\ \%\ n) + (b_2^{p-1}\ \%\ n)\ \ mod\ n

这边出现了 p-1 ，此处由于p是素数，因此 p-1 = φ(p) ，因此可进一步联想到欧拉定理：

1≡aφ(b)  mod b1\equiv a^{φ(b)}\ \ mod\ b

所以此处有：

1≡ap−1  mod p1\equiv a^{p-1}\ \ mod\ p

然而此处差了一点火候。原hint表达式中，每个这样的构造在原式末尾中没有模p，而是模n。接下来简单描述一下这样可能造成的影响。

假设现在有一个数 12.5 ：

1 1 1 1 1 1 1 1 1 1 1 1 0.5

那么我们暂且把它想象成 12.5 块切糕吧，然后每一刀切分出的切糕都用一个单独的字母表示。这边先是以模1为刀，可切出：

A B C D E F G H I J K L 0.5

最后能切得剩 0.5 块切糕。

现在我们让模1变为模3，模拟模p变为模n的其中一种可能情况，则可切出：

A A A B B B C C C D D D 0.5

最后还是剩下 0.5 块切糕。

因此这边可以得到第一个结论：

a的(p-1)次方，模p的结果和模n的结果可能相同。

现在我们让模1变为模5再试一下，可切出：

A A A A A B B B B B 1 1 0.5

这回不一样了，最后剩下 2.5 块切糕。

因此这边得出结论：

a的(p-1)次方，模p的结果和模n的结果既可能相同，也可能不同。

现场有50组hint，可能存在其中一组会出现如下情况：

hint≡(b1p−1 % n)+(b2p−1 % n)≡(b1p−1 % p)+(b2p−1 % p)≡1+1≡2  mod nhint\equiv (b_1^{p-1}\ \%\ n) + (b_2^{p-1}\ \%\ n)\equiv (b_1^{p-1}\ \%\ p) + (b_2^{p-1}\ \%\ p)\equiv 1+1\equiv 2\ \ mod\ n

于是有：

hint−2≡0  mod nhint-2\equiv 0\ \ mod\ n

所以下面关系成立：

n ∣ (hint−2)n\ |\ (hint-2)

所以：

gcd(n,(hint−2))≠1gcd(n,(hint-2))≠1

那么这个时候我们就能通过求最大公因数的方式来分解n。

所以我们可以把50个 (hint-2) 都拿出来尝试跟 n 求最大公约数，看能不能成功分解。如果成功分解就可以去解密文。

解密脚本：

from gmpy2 import *
from Crypto.Util.number import *
import re

n = 16926747183730811445521182287631871095235807124637325096660759361996155369993998745638293862726267741890840654094794027600177564948819372030933079291097084177091863985749240756085243654442374722882507015343515827787141307909182820013354070321738405810257107651857739607060274549412692517140259717346170524920540888050323066988108836911975466603073034433831887208978130406742714302940264702874305095602623379177353873347208751721068498690917932776984190598143704567665475161453335629659200748786648288309401513856740323455946901312988841290917666732077747457081355853722832166331501779601157719722291598787710746917947
e = 65537
c = 7135669888508993283998887257526185813831780208680788333332044930342125381561919830084088631920301623909949443002073193381401761901398826719665411432016217400457613545308262831975564456231165114091904748808206330488231569773162745696602366468753664188261933014198218922459715972876740957260132243927549037840265753282534565674280908439875550179801788711737901632349136780584007599655055605772651127003711138512998683145763743839326460319440186099818507078433271291685194944254795690424327192625258701835654639832285402990995662846426561789508331799972329711410217802657682842382105869446853207634070295959281375484933

with open('./output.txt', 'r') as f:
    tmp = f.read()

hints = re.findall('Hint \d+: \d+, \d+, (\d+)', tmp)
hints_sub2 = [int(i)-2 for i in hints]

for i in hints_sub2:
    if gcd(i, n) != 1:
        p = gcd(i, n)
        q = n // p
        phi = (p-1) * (q-1)
        d = invert(e, phi)
        m = powmod(c, d, n)
        print(long_to_bytes(m).decode(errors='ignore'))
        break
image-20251216162745365

沉迷数学的小蓝鲨

首先简单看一下题目附件：

y² = x³ + 3x + 27 (mod p)

Q(0xa61ae2f42348f8b84e4b8271ee8ce3f19d7760330ef6a5f6ec992430dccdc167, 0x8a3ceb15b94ee7c6ce435147f31ca8028d1dd07a986711966980f7de20490080)

k= ?

最终flag请将解出k值的16进制转换为32位md5以ISCTF{}包裹提交

首先点Q应该是基点G标量乘k得到的。但这道题麻烦就麻烦在很多条件感觉都给得很隐晦，得猜……比如这边既不给基点G，也不给p值。

但是题目有提到 广泛应用于区块链技术 ，上网搜索能了解到是 secp256k1 曲线（其实问AI它也会这样告诉你的）。

image-20251216165043882

然后再去搜相关的介绍，能找到一些参数：

image-20251216165158816

因此这边我们代入参数，就尝试验证的时候就会发现不管是点G还是点Q都不在题目给的曲线上。用于测试的sage代码：

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Q_x = 0xa61ae2f42348f8b84e4b8271ee8ce3f19d7760330ef6a5f6ec992430dccdc167
Q_y = 0x8a3ceb15b94ee7c6ce435147f31ca8028d1dd07a986711966980f7de20490080

E1 = EllipticCurve(GF(p), [3, 27])
print(E1(G_x, G_y))
print(E1(Q_x, Q_y))
image-20251216171546042

而这道题的提示一直在很隐晦地告诉我们，曲线的参数有问题。

于是这边暂且猜测参数b有问题，于是尝试重新计算参数b，然后代入点验证，sage脚本如：

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Q_x = 0xa61ae2f42348f8b84e4b8271ee8ce3f19d7760330ef6a5f6ec992430dccdc167
Q_y = 0x8a3ceb15b94ee7c6ce435147f31ca8028d1dd07a986711966980f7de20490080

new_b = (G_y**2 - G_x**3 - G_x * 3) % p
E = EllipticCurve(GF(p), [3, new_b])

print(E(G_x, G_y))      # 能正常输出，说明在曲线上
print(E(Q_x, Q_y))      # 能正常输出，说明也在曲线上
image-20251216172000045

这边能看到两个点都能正常输出，因此两个点都在这条新曲线上，所以这才是我们要用的曲线。

于是接下来直接尝试解离散对数问题开出k：

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Q_x = 0xa61ae2f42348f8b84e4b8271ee8ce3f19d7760330ef6a5f6ec992430dccdc167
Q_y = 0x8a3ceb15b94ee7c6ce435147f31ca8028d1dd07a986711966980f7de20490080

new_b = (G_y**2 - G_x**3 - G_x * 3) % p
E = EllipticCurve(GF(p), [3, new_b])

G = E(G_x, G_y)
Q = E(Q_x, Q_y)

k = discrete_log(Q, G, operation='+')
print(f"k = {k}")
image-20251216172932264

这边得到 k = 954761 。

于是这边接着按照题目要求，把k转为十六进制然后取32位md5值。更新sage脚本：

import hashlib

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Q_x = 0xa61ae2f42348f8b84e4b8271ee8ce3f19d7760330ef6a5f6ec992430dccdc167
Q_y = 0x8a3ceb15b94ee7c6ce435147f31ca8028d1dd07a986711966980f7de20490080

new_b = (G_y**2 - G_x**3 - G_x * 3) % p
E = EllipticCurve(GF(p), [3, new_b])

G = E(G_x, G_y)
Q = E(Q_x, Q_y)

k = discrete_log(Q, G, operation='+')
print(f"k = {k}")

hex_k = hex(k)[2:]
print(f"ISCTF{{{hashlib.md5(hex_k.encode()).hexdigest()}}}")

运行后获得flag：

image-20251216173523529

baby_math

（赛后参考其他师傅的wp，优化了做法）

首先简单看一下代码：

from Crypto.Util.number import bytes_to_long

print(len(flag))		# 这句对应的输出结果本质上没有给出
R = RealField(1000)		# 定义一个精度为1000位的实数环
a,b = bytes_to_long(flag[:len(flag)//2]),bytes_to_long(flag[len(flag)//2:])		# 将flag拆为两段，并分别转为大素数
x   = R(0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557302303874143106908193100)		# x是环R上的一个值

enc = a*cos(x)+b*sin(x)		# 经过这个运算，应该是得到了下面注释的结果

#1.24839978408728580181183027675785982784764821592156892598136000363397267152291738689909414790691435938223032351375697399608345468567445269769342300325192248438038963977207296241971217955178443170598629648414706345216797043374408541203167719396818925953801387623884200901703606288664141375049626635852e52

这题出现了几个要素，首先是抽象代数（面目可憎群环域（））；然后是需要求解大数或高精度数值；最后是已知条件量比较有限。

因此，我们可以考虑用格密码相关知识来解决这个问题，很明显，这样很可能涉及LLL算法的使用。

那么首先是，我们要处理数据为整数，以便于LLL算法处理。

根据代码，存在：

enc=a⋅cos(x)+b⋅sin(x)enc = a·cos(x)+b·sin(x)

两边都存在高精度浮点数，因此可以同乘一个大到一定程度的数。这边写sage脚本简单估计一下这样的数需要达到的数量级：

R = RealField(1000)
x = R(0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557302303874143106908193100)

a = cos(x)
b = sin(x)
print(a)
print(b)
print(len(str(a)) - 2)      # 求小数位数
print(len(str(b)) - 2)
image-20251216225630980

因此我们需要在等式两边乘上 10的300次方 。

因此这边有：

a⋅cos(x)⋅10300+b⋅sin(x)⋅10300−enc⋅10300=0a·cos(x)·10^{300}+b·sin(x)·10^{300} - enc·10^{300} = 0

据此，这边暂且能构造出这样的含矩阵表达式：

(a,b,−1)(cos(x)⋅10300sin(x)⋅10300enc⋅10300)=(0)\begin{pmatrix} a,b,-1 \end{pmatrix} \begin{pmatrix} cos(x)·10^{300} \\ sin(x)·10^{300} \\ enc·10^{300} \end{pmatrix} = \begin{pmatrix} 0 \end{pmatrix}

根据LLL算法的特点，我们要在等式右侧放上我们想要求解的a和b。于是继续构造：

(a,b,−1)(cos(x)⋅1030010sin(x)⋅1030001enc⋅1030000)=(0,a,b)\begin{pmatrix} a,b,-1 \end{pmatrix} \begin{pmatrix} cos(x)·10^{300} & 1 & 0 \\ sin(x)·10^{300} & 0 & 1 \\ enc·10^{300} & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0,a,b \end{pmatrix}

所以此时理论上我们对下面矩阵做LLL，即可得到行向量 (0 a b) ：

(cos(x)⋅1030010sin(x)⋅1030001enc⋅1030000)\begin{pmatrix} cos(x)·10^{300} & 1 & 0 \\ sin(x)·10^{300} & 0 & 1 \\ enc·10^{300} & 0 & 0 \end{pmatrix}

据此可写sage脚本：

from Crypto.Util.number import *

R = RealField(1000)

x = R(0.75872961153339387563860550178464795474547887323678173252494265684893323654606628651427151866818730100357590296863274236719073684620030717141521941211167282170567424114270941542016135979438271439047194028943997508126389603529160316379547558098144713802870753946485296790294770557302303874143106908193100)

sin_x = int(R(sin(x)) * 10^300)     # 这边套一个int把科学计数法转换为正常显示，这样才算处理掉了小数
cos_x = int(R(cos(x)) * 10^300)

enc = R(1.24839978408728580181183027675785982784764821592156892598136000363397267152291738689909414790691435938223032351375697399608345468567445269769342300325192248438038963977207296241971217955178443170598629648414706345216797043374408541203167719396818925953801387623884200901703606288664141375049626635852e52)
enc = int(enc * 10^300)

M = Matrix(ZZ, [
    [cos_x, 1, 0],
    [sin_x, 0, 1],
    [enc, 0, 0],]).LLL()

a = long_to_bytes(abs(int(M[0, 1]))).decode()
b = long_to_bytes(abs(int(M[0, 2]))).decode()
print(f"{a}{b}")
image-20251216232623593

至此成功求解出flag。

2025ISCTF_OSINT&病毒分析 下一篇
已运行:
浏览数: 次 | 访客数: 人
0%