moectf-2025历程
MOECTF-2025
因为有点懒然后中途弃坑了(doge)
Crypto
Crypto入门指北
签到题，题目代码如下：
from Crypto.PublicKey import ElGamal
from Crypto.Random import get_random_bytes, random
from Crypto.Util.number import *
from random import *
from secret import flag
def generate_elgamal_keypair(bits=512):
p = getPrime(bits)
for _ in range(1000):
g = getRandomRange(2, 5)
if pow(g, (p - 1) // 2, p) != 1:
break
x = randrange(2, p - 1)
y = pow(g, x, p)
return p, g, y, x
key=generate_elgamal_keypair(bits=512)
p, g, y ,x= key
print("=== 公钥 (p, g, y) ===")
print("p =", p)
print("g =", g)
print("y =", y)
print()
k = randrange(1, p - 2)
m = bytes_to_long(flag)
c1 = pow(g, k, p)
c2 = (m * pow(y, k, p)) % p
print("=== 密文 (c1, c2) ===")
print("c1 =", c1)
print("c2 =", c2)
#不小心把x输出了()
print("x =", x)
"""
=== 公钥 (p, g, y) ===
p =
11540963715962144951763578255357417528966715904849014985547597657698304891044841099894993117258279094910424033273299863589407477091830213468539451196239863
g = 2
y =
8313424783366011287014623582773521595333285291380540689467073212212931648415580065207081449784135835711205324186662482526357834042013400765421925274271853
=== 密文 (c1, c2) ===
c1 =
6652053553055645358275362259554856525976931841318251152940464543175108560132949610916012490837970851191204144757409335011811874896056430105292534244732863
c2 =
2314913568081526428247981719100952331444938852399031826635475971947484663418362533363591441216570597417789120470703548843342170567039399830377459228297983
x =
8010957078086554284020959664124784479610913596560035011951143269559761229114027738791440961864150225798049120582540951874956255115884539333966429021004214
"""题目说是Elgamal加密，还给了ctf-wiki，学习了一下再看题目发现题目给出的x就是私钥，然后顺利解题，解题代码如下：
from Crypto.Util.number import *
import gmpy2
p = 11540963715962144951763578255357417528966715904849014985547597657698304891044841099894993117258279094910424033273299863589407477091830213468539451196239863
g = 2
y = 8313424783366011287014623582773521595333285291380540689467073212212931648415580065207081449784135835711205324186662482526357834042013400765421925274271853
c1 = 6652053553055645358275362259554856525976931841318251152940464543175108560132949610916012490837970851191204144757409335011811874896056430105292534244732863
c2 = 2314913568081526428247981719100952331444938852399031826635475971947484663418362533363591441216570597417789120470703548843342170567039399830377459228297983
x = 8010957078086554284020959664124784479610913596560035011951143269559761229114027738791440961864150225798049120582540951874956255115884539333966429021004214
d = inverse(gmpy2.powmod(c1, x, p), p)
m = c2 * d % p
print(long_to_bytes(m))
# b'moectf{th1s_1s_y0ur_f1rst_ElG@m@l}'ez_DES
题目描述是说分组密码？第二题就已经分组了？题目代码如下：
from Crypto.Cipher import DES
import secrets
import string
flag = 'moectf{???}'
characters = string.ascii_letters + string.digits + string.punctuation
key = 'ezdes'+''.join(secrets.choice(characters) for _ in range(3))
assert key[:5] == 'ezdes'
key = key.encode('utf-8')
l = 8
def encrypt(text, key):
cipher = DES.new(key, DES.MODE_ECB)
padded_text = text + (l - len(text) % l) * chr(len(text))
data = cipher.encrypt(padded_text.encode('utf-8'))
return data
c = encrypt(flag, key)
print('c =', c)
# c = b'\xe6\x8b0\xc8m\t?\x1d\xf6\x99sA>\xce \rN\x83z\xa0\xdc{\xbc\xb8X\xb2\xe2q\xa4"\xfc\x07'看了一眼，这跟分组没半毛钱关系哈，就只需要把key爆破出来就好了，没什么技术含量，解题代码如下：
from Crypto.Cipher import DES
import secrets
import string
characters = string.ascii_letters + string.digits + string.punctuation
key_head = 'ezdes'
c = b'\xe6\x8b0\xc8m\t?\x1d\xf6\x99sA>\xce \rN\x83z\xa0\xdc{\xbc\xb8X\xb2\xe2q\xa4"\xfc\x07'
for ch1 in characters:
for ch2 in characters:
for ch3 in characters:
key = key_head + ch1 + ch2 + ch3
key = key.encode('utf-8')
m = DES.new(key, DES.MODE_ECB).decrypt(c)
if b'moectf' in m:
print(m)
# b'moectf{_Ju5t envmEra+e.!}\x19\x19\x19\x19\x19\x19\x19'baby_next
题目描述说很好分解，应该指的是n很好被分解，看到题目中的next就猜测是next_prime了，题目代码如下：
from Crypto.Util.number import *
from gmpy2 import next_prime
from functools import reduce
from secret import flag
assert len(flag) == 38
assert flag[:7] == b'moectf{'
assert flag[-1:] == b'}'
def main():
p = getPrime(512)
q = int(reduce(lambda res, _: next_prime(res), range(114514), p))
n = p * q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'{n = }')
print(f'{c = }')
if __name__ == '__main__':
main()
"""
n = 96742777571959902478849172116992100058097986518388851527052638944778038830381328778848540098201307724752598903628039482354215330671373992156290837979842156381411957754907190292238010742130674404082688791216045656050228686469536688900043735264177699512562466087275808541376525564145453954694429605944189276397
c = 17445962474813629559693587749061112782648120738023354591681532173123918523200368390246892643206880043853188835375836941118739796280111891950421612990713883817902247767311707918305107969264361136058458670735307702064189010952773013588328843994478490621886896074511809007736368751211179727573924125553940385967
"""只需要知道 $p < \sqrt{n} < q$ 即可，所以可以从 $\sqrt{n}$ 开始往后找114514个素数，其中必然包含q，然后完成分解，解题代码如下：
from Crypto.Util.number import *
from gmpy2 import next_prime
from tqdm import tqdm
import gmpy2
n = 96742777571959902478849172116992100058097986518388851527052638944778038830381328778848540098201307724752598903628039482354215330671373992156290837979842156381411957754907190292238010742130674404082688791216045656050228686469536688900043735264177699512562466087275808541376525564145453954694429605944189276397
c = 17445962474813629559693587749061112782648120738023354591681532173123918523200368390246892643206880043853188835375836941118739796280111891950421612990713883817902247767311707918305107969264361136058458670735307702064189010952773013588328843994478490621886896074511809007736368751211179727573924125553940385967
e = 65537
q, _ = gmpy2.iroot(n, 2)
for _ in tqdm(range(114514)):
q = next_prime(q)
if n % q == 0:
break
p = n // q
assert n == p * q
phi = (p-1) * (q-1)
d = inverse(e, phi)
m = gmpy2.powmod(c, d, n)
print(long_to_bytes(m))
# b'moectf{vv0W_p_m1nu5_q_i5_r34l1y_sm4lI}'ezBSGS
该题目就是要求解 $13^x \equiv 114514 \mod 100000000000099$，flag就是x，题目还强调了BSGS(Baby-Step Giant-Step)算法
BSGS算法主要是在求解离散对数问题时将时间和空间降到$\sqrt{n}$的算法($n$是群阶)
原理：
在求解$g^x \equiv y \mod p$ 中 $x$ 的最小正整数解时，用$x = i \times m + j$将x拆成两个部分，将一部分的值先存入哈希表(baby step) ，再用另一部分去逐步匹配(giant step)
核心思路： 目标：求解$g^x \equiv y \mod p$中 $x$ 的最小正整数解
- 令$x = i \times m + j$，$n$为群阶$(p-1)$，则$m = \lceil \sqrt{n} \rceil$，且 $i, j < m$ 以确保$i\times m + j$覆盖所有可能的$x$
- 等式变形为 $g^j \equiv y * (g^{-m})^i \mod p$，将 $g^j$ 的所有可能取值存入字典，用查哈希表的方式遍历所有 $i$ 的取值，若 $x$ 存在就一定能找到
解题代码如下：
import gmpy2
def BSGS(g, y, p):
n = p - 1
m = int(gmpy2.iroot(n, 2)[0]) + 1 # 取上整
table = {}
val = 1
# baby steps
for j in range(m):
table[val] = j
val = (val * g) % p
# giant steps
gamma = y % p
inv = gmpy2.invert(gmpy2.powmod(g, m, p), p)
for i in range(m):
if gamma in table:
x = i * m + table[gamma]
return x % n
gamma = (gamma * inv) % p
return None # 没有解
p = 100000000000099
y = 114514
g = 13
print(BSGS(g, y, p))
# 18272162371285
# flag:moectf{18272162371285}ez_square
题目描述说是基本的数学变形，题目代码如下：
from Crypto.Util.number import *
from secret import flag
assert len(flag) == 35
assert flag[:7] == b'moectf{'
assert flag[-1:] == b'}'
def main():
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
hint = pow(p + q, 2, n)
print(f'{n = }')
print(f'{c = }')
print(f'{hint = }')
if __name__ == '__main__':
main()
"""
n = 83917281059209836833837824007690691544699901753577294450739161840987816051781770716778159151802639720854808886223999296102766845876403271538287419091422744267873129896312388567406645946985868002735024896571899580581985438021613509956651683237014111116217116870686535030557076307205101926450610365611263289149
c = 69694813399964784535448926320621517155870332267827466101049186858004350675634768405333171732816667487889978017750378262941788713673371418944090831542155613846263236805141090585331932145339718055875857157018510852176248031272419248573911998354239587587157830782446559008393076144761176799690034691298870022190
hint = 5491796378615699391870545352353909903258578093592392113819670099563278086635523482350754035015775218028095468852040957207028066409846581454987397954900268152836625448524886929236711403732984563866312512753483333102094024510204387673875968726154625598491190530093961973354413317757182213887911644502704780304
"""我尝试过直接通过hint和n直接化成phi(n)，很快发现并不行，于是还是老老实实求出p和q
我们令
$$
\begin{cases}
s = p + q \cr
\delta = |p - q|
\end{cases}
$$
，则
$$
\begin{cases}
p = \frac{s+\delta}{2} \cr
q = \frac{s-\delta}{2}
\end{cases}
$$
(可能是负数，稍微调一下就好)
接着观察hint，可以看出$hint=(p+q)^2\equiv p^2+q^2\equiv s^2\equiv \delta^2 \mod n$，然后可以得出$hint=\delta^2$的结论，从而解出题目，简要证明：
由于$$2^{k-1}\leq p,q < 2^k \Rightarrow 2^{2k-2} \leq n < 2^{2k}$$又 $\delta = |p-q| ，$ 可得$$ 0 < \delta^2 < 2^{2k-2} <n$$
即 $hint,\delta^2 \in(0,n)$，结合$hint\equiv \delta^2\mod n$，即可推出 $$hint=\delta^2$$ 再通过 $s=\sqrt{\delta^2 + 4n}$ 即可求出s
解题代码如下：
from Crypto.Util.number import *
import gmpy2
n = 83917281059209836833837824007690691544699901753577294450739161840987816051781770716778159151802639720854808886223999296102766845876403271538287419091422744267873129896312388567406645946985868002735024896571899580581985438021613509956651683237014111116217116870686535030557076307205101926450610365611263289149
c = 69694813399964784535448926320621517155870332267827466101049186858004350675634768405333171732816667487889978017750378262941788713673371418944090831542155613846263236805141090585331932145339718055875857157018510852176248031272419248573911998354239587587157830782446559008393076144761176799690034691298870022190
hint = 5491796378615699391870545352353909903258578093592392113819670099563278086635523482350754035015775218028095468852040957207028066409846581454987397954900268152836625448524886929236711403732984563866312512753483333102094024510204387673875968726154625598491190530093961973354413317757182213887911644502704780304
e = 65537
delta, square = gmpy2.iroot(hint, 2)
# print(square) # Ture
s = gmpy2.iroot(pow(delta, 2) + 4 * n, 2)[0]
p = (s + delta) // 2
q = n // p
phi = (p-1) * (q-1)
d = inverse(e, phi)
m = gmpy2.powmod(c, d, n)
print(long_to_bytes(m))
# b'moectf{Ma7hm4t1c5_is_@_k1nd_0f_a2t}'ezAES
题目描述说和普通的AES也没什么不同罢，我信你个gui()，题目代码如下：
from secret import flag
rc = [0x12, 0x23, 0x34, 0x45, 0x56, 0x67, 0x78, 0x89, 0x9a, 0xab, 0xbc, 0xcd, 0xde, 0xef,0xf1]
s_box = [
[0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76],
[0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0],
[0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15],
[0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75],
[0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84],
[0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf],
[0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8],
[0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2],
[0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73],
[0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb],
[0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79],
[0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08],
[0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a],
[0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e],
[0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf],
[0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16]
]
s_box_inv = [
[0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb],
[0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb],
[0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e],
[0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25],
[0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92],
[0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84],
[0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06],
[0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b],
[0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73],
[0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e],
[0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b],
[0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4],
[0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f],
[0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef],
[0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61],
[0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d]
]
def sub_bytes(grid):
for i, v in enumerate(grid):
grid[i] = s_box[v >> 4][v & 0xf]
def shift_rows(grid):
for i in range(4):
grid[i::4] = grid[i::4][i:] + grid[i::4][:i]
grid =grid[0::4]+grid[1::4]+grid[2::4]+grid[3::4]
def mix_columns(grid):
def mul_by_2(n):
s = (n << 1) & 0xff
if n & 128:
s ^= 0x1b
return s
def mul_by_3(n):
return n ^ mul_by_2(n)
def mix_column(c):
return [
mul_by_2(c[0]) ^ mul_by_3(c[1]) ^ c[2] ^ c[3], # [2 3 1 1]
c[0] ^ mul_by_2(c[1]) ^ mul_by_3(c[2]) ^ c[3], # [1 2 3 1]
c[0] ^ c[1] ^ mul_by_2(c[2]) ^ mul_by_3(c[3]), # [1 1 2 3]
mul_by_3(c[0]) ^ c[1] ^ c[2] ^ mul_by_2(c[3]), # [3 1 1 2]
]
for i in range(0, 16, 4):
grid[i:i + 4] = mix_column(grid[i:i + 4])
def key_expansion(grid):
for i in range(10 * 4):
r = grid[-4:]
if i % 4 == 0: # 对上一轮最后4字节自循环、S-box置换、轮常数异或，从而计算出当前新一轮最前4字节
for j, v in enumerate(r[1:] + r[:1]):
r[j] = s_box[v >> 4][v & 0xf] ^ (rc[i // 4] if j == 0 else 0)
for j in range(4):
grid.append(grid[-16] ^ r[j])
return grid
def add_round_key(grid, round_key):
for i in range(16):
grid[i] ^= round_key[i]
def encrypt(b, expanded_key):
# First round
add_round_key(b, expanded_key)
for i in range(1, 10):
sub_bytes(b)
shift_rows(b)
mix_columns(b)
add_round_key(b, expanded_key[i * 16:])
# Final round
sub_bytes(b)
shift_rows(b)
add_round_key(b, expanded_key[-16:])
return b
def aes(key, msg):
expanded = key_expansion(bytearray(key))
# Pad the message to a multiple of 16 bytes
b = bytearray(msg + b'\x00' * (16 - len(msg) % 16))
# Encrypt the message
for i in range(0, len(b), 16):
b[i:i + 16] = encrypt(b[i:i + 16], expanded)
return bytes(b)
if __name__ == '__main__':
key = b'Slightly different from the AES.'
enc = aes(key, flag)
print('Encrypted:', enc)
#Encrypted: b'%\x98\x10\x8b\x93O\xc7\xf02F\xae\xedA\x96\x1b\xf9\x9d\x96\xcb\x8bT\r\xd31P\xe6\x1a\xa1j\x0c\xe6\xc8'看了一眼，其实不一样的地方应该是shift_rows那个函数那里，每一次都对矩阵进行了重新的排列，于是就自己写了逆向解密的脚本,AES原理的学习可以参考这篇文章
解题代码如下：
rc = [0x12, 0x23, 0x34, 0x45, 0x56, 0x67, 0x78, 0x89, 0x9a, 0xab, 0xbc, 0xcd, 0xde, 0xef,0xf1]
s_box = [
[0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76],
[0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0],
[0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15],
[0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75],
[0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84],
[0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf],
[0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8],
[0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2],
[0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73],
[0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb],
[0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79],
[0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08],
[0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a],
[0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e],
[0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf],
[0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16]
]
s_box_inv = [
[0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb],
[0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb],
[0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e],
[0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25],
[0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92],
[0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84],
[0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06],
[0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b],
[0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73],
[0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e],
[0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b],
[0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4],
[0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f],
[0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef],
[0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61],
[0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d]
]
def inv_sub_bytes(grid):
for i, v in enumerate(grid):
grid[i] = s_box_inv[v >> 4][v & 0xf]
def inv_shift_rows(grid):
for i in range(4):
inv_grid = ['0'] * 16
for j in range(4):
for k in range(4):
inv_grid[4 * j + k] = grid[j + 4 * k]
grid = inv_grid
grid[i::4] = grid[i::4][:i] + grid[i::4][i:]
def inv_mix_columns(grid):
def gf256_mul(a, b) :
res = 0
while b > 0 :
if b & 1 :
res ^= a
a <<= 1
if a & (1 << 8) :
a ^= 0x1b
b >>= 1
return res & 0xff
def inv_mix_column(column):
return[
gf256_mul(0x0E, column[0]) ^ gf256_mul(0x0B, column[1]) ^ gf256_mul(0x0D, column[2]) ^ gf256_mul(0X09, column[3]),
gf256_mul(0x09, column[0]) ^ gf256_mul(0x0E, column[1]) ^ gf256_mul(0x0B, column[2]) ^ gf256_mul(0x0D, column[3]),
gf256_mul(0x0D, column[0]) ^ gf256_mul(0x09, column[1]) ^ gf256_mul(0x0E, column[2]) ^ gf256_mul(0x0B, column[3]),
gf256_mul(0x0B, column[0]) ^ gf256_mul(0x0D, column[1]) ^ gf256_mul(0x09, column[2]) ^ gf256_mul(0x0E, column[3])
]
for i in range(0, 16, 4):
grid[i:i + 4] = inv_mix_column(grid[i:i + 4])
def key_expansion(grid):
for i in range(10 * 4):
r = grid[-4:]
if i % 4 == 0:
for j, v in enumerate(r[1:] + r[:1]):
r[j] = s_box[v >> 4][v & 0xf] ^ (rc[i // 4] if j == 0 else 0)
for j in range(4):
grid.append(grid[-16] ^ r[j])
return grid
def sub_round_key(grid, round_key):
for i in range(16):
grid[i] ^= round_key[i]
def decrypt(b, expended_key):
sub_round_key(b, expended_key[-16:])
inv_shift_rows(b)
inv_sub_bytes(b)
for i in range(9, 0, -1):
sub_round_key(b, expended_key[i * 16:])
inv_mix_columns(b)
inv_shift_rows(b)
inv_sub_bytes(b)
sub_round_key(b, expended_key)
return b
def aes_decrypt(key, enc):
expended = key_expansion(bytearray(key))
enc = bytearray(enc)
for i in range(0, len(enc), 16):
enc[i:i + 16] = decrypt(enc[i:i + 16], expended)
return bytes(enc)
if __name__ == '__main__':
key = b'Slightly different from the AES.'
enc = b'%\x98\x10\x8b\x93O\xc7\xf02F\xae\xedA\x96\x1b\xf9\x9d\x96\xcb\x8bT\r\xd31P\xe6\x1a\xa1j\x0c\xe6\xc8'
print(aes_decrypt(key, enc))
# b'moectf{Th1s_1s_4n_E4ZY_AE5_!@#}\x00'GF(256)的乘法函数还是在学习
CINTA的时候学的，这里直接照搬了(doge)
ezlegendre
题目描述让我去找规律？可能是输出的规律吧，但是我没去看输出()
题目代码如下：
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
from random import randint
p = 258669765135238783146000574794031096183
a = 144901483389896508632771215712413815934
def encrypt_flag(flag):
ciphertext = []
plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
for b in plaintext:
e = getPrime(16)
d = randint(1,10)
n = pow(a+int(b)*d, e, p)
ciphertext.append(n)
return ciphertext
print(encrypt_flag(flag))
ciphertext = [102230607782303286066661803375943337852, 196795077203291879584123548614536291210, 41820965969318717978206410470942308653, 207485265608553973031638961376379316991, 126241934830164184030184483965965358511, 20250852993510047910828861636740192486, 103669039044817273633962139070912140023, 97337342479349334554052986501856387313, 159127719377115088432849153087501377529, 45764236700940832554086668329121194445, 35275004033464216369574866255836768148, 52905563179465420745275423120979831405, 17032180473319795641143474346227445013, 29477780450507011415073117531375947096, 55487351149573346854028771906741727601, 121576510894250531063152466107000055279, 69959515052241122548546701060784004682, 173839335744520746760315021378911211216, 28266103662329817802592951699263023295, 194965730205655016437216590690038884309, 208284966254343254016582889051763066574, 137680272193449000169293006333866420934, 250634504150859449051246497912830488025, 124228075953362483108097926850143387433, 232956176229023369857830577971626577196, 149441784891021006224395235471825205661, 118758326165875568431376314508740278934, 222296215466271835013184903421917936512, 49132466023594939909761224481560782731, 406286678537520849308828749751513339, 215122152883292859254246948661946520324, 81283590250399459209567683991648438199, 150395133067480380674905743031927410663, 5710878479977467762548400320726575491, 83627753774286426170934105100463456109, 164968224377869331545649899270867630850, 241057183685774160581265732812497247167, 109136287048010096863680430193408099828, 116313129605409961931811582899075031153, 202739016625709380026000805340243458300, 25408225921774957745573142542576755590, 151336258796933656160956289529558246702, 2947189044370494063643525166023973095, 228678413963736672394976193093568181979, 40627063032321835707220414670018641024, 55446789315226949622969082042881319148, 32219108726651509070669836923591948459, 134454924722414419191920784435633637634, 97952023967728640730045857104376826039, 20659076942504417479953787092276592682, 93281761173713729777326842152860901050, 133634773495582264000160065317239987936, 79976720152435218818731114555425458470, 234654694673289327542859971371886984118, 51332273108989067644245919615090753756, 134120280423303717489979349737802826605, 182001158305920226320085758522717203725, 98408798757865562737462169470346158516, 78200435603900368619334272308272773797, 232796357836930341547987600782979821555, 589106968861493082018132081244848952, 24186003230092331554886767628744415123, 236070626491251466741246103662922841423, 238699080882667864827094121849090696547, 141659873734297659078160283051728812410, 228977113517120063860252637394240795552, 236613527842969921794004708284265628300, 145522034982744654991661857596541755396, 249608374387044047328725156440984678776, 325110572051913836681821746093704556, 171492052199838424502681030556098576483, 156498865212994371079795360268866413702, 196747701509389071931992996873572785043, 70811811603137896158765356680364490781, 83672551582385607422240464086955462541, 117961603623637997457153763936550310698, 224448821395214505399297116719025174412, 4598815373009554321735225938200807251, 194892269604260726530091473301914449005, 127484628022155760909820605666827662175, 208706240846212140439291547368645656474, 14102286481104997303651684152195298336, 6129503335471304345451795609683770657, 103799668048593149396277157385628834185, 185813375481410513002496683918106238351, 233491689316882978147517340230794025796, 46274083097168831187719988888816378961, 119487551553664772614629936285345836934, 84340029922118279362389419277915602509, 88253743193124528032223101368846247085, 227895357640018330099501504941388167432, 92189947144174433744195727086236905626, 83114957902192791332190922428847199876, 173535754090441937731619031520699325122, 192309407933789484835602071782330798398, 255421921600128994923738650157598053776, 155535082468314012733563336837641958625, 49064798421022327310707074253263463055, 161216416471071644769301963857685054031, 252480348817188872515008985698620059851, 75854882798183185741756645038434215611, 256065006192683011190132982128640682537, 87507510173514424105732562474643251223, 163309795132131534875147566536485288212, 253583084320404985699510129361746869059, 253300112521651972637580307326576568313, 239027717080729650738678032571840680727, 117444657686971615526398894470673026034, 215470942802874046857958621181684551426, 58767098748728136687851735836323448020, 249357164697409977883764098879705065535, 174705348385893117518084017669958647345, 211108767177375215605155301209259781232, 57829566748907062397366819001461941421, 88265742700024922112974862134385921564, 80952107622167923709226013231566882261, 236078582132483864916117213281193714198, 193448482646563141692726575550417225891, 245972799166806058223048506073553726233, 10132977708896091601871557249244373666, 201785418152654519825849206312616081028, 15169816744048531212384271865884567710, 122545328290385950043826822277924297182, 202918646192255177261567701479991753600, 32696887488223731055835744711207261936, 88319352182963224921157305627381030375, 92381505322264045777004475690398861771, 189745654013352563126968415157143821842, 152254915005998949299817641843658795579, 198032433618991362619448347415342295581, 84073892809321676935569114878067118319, 82243805869584256211699602267760745768, 61994229948266781537191603999495995852, 253668765227759797787675352833142466255, 38865376724677211964966907748953557125, 134615436811268347303232550777225944929, 176932422465426107783498083830285780588, 207573742393618910694054452362826628208, 200033130835394442710748301293534928706, 127536063935293533700918451145963158658, 219125698281820710910675956971948816959, 179795893258398750139395156587561075767, 69649628109726874051635160004398498964, 241433717681314766463039563422535023524, 202664264135718511331695232476272832350, 205151096657425932591242432052912914182, 210305712465948130683966275157181140301, 196555690055906934925300527324955477733, 66817932643964538216259564711698986077, 95270796440975607179107356182889534333, 123226880424532374188134357659879826495, 53506495440223773538415807620524749240, 19253217887083870834249774316467647628, 165699356396365023442008488156823647206, 107809175498119862854792975070673056027, 250453989887421415931162217952559757164, 171492052199838424502681030556098576483, 133778166882550119563444625306816232463, 149009301604122447269581792013291889175, 9982418254629616281350713836647603294, 203486292122499140756846060502464655972, 157686696123400087437836943220926921848, 88338919773540412238116717043122711811, 113265824169274322024623493892867211478, 5549372099744960679418616304893848801, 12431828907518852062050349123660880165, 183957934738536914983862053251433028750, 42027289270308356303682029801998790750, 117406080036483925915502666019795783905, 154312255292300186042636734144948304054, 143706917273862261295046346995206133170, 50088136095338601440516112338120787526, 250634504150859449051246497912830488025, 8073010289877796888705519374892639903, 40049582814576788803483039836229025416, 227012342545923833983403067401561291645, 201776603581414625783054400184026088994, 55474945478884522762318445841998187357, 221515530211550293408010846844218019597, 172650752042211610909190315288155597255, 67046194931321172530462444254204111483, 207435868835185636819659137800256834557, 188063222224545200294767050268070647452, 58099349021260301211275261896736590564, 23598877596106927870697531042828774738, 58546308516383335224739442370238545000, 58125311541947998710088435169901475101, 238219925698115060748249043752036454438, 203910234934340893915761800653823457631, 190854889967769152565565000250829375099, 37573623890629846209257307181880876288, 226220240200270623843038279593586687278, 144246075981535671790438155977352345487, 14665770553338784222331493932533448756, 37992062606775322664977502677838074649, 47370175759976523832233910009306151684, 97047813247943880266351445874642842468, 237607444658797800072728280983357541134, 174853113478993738890584814806707459112, 17104608155861584438824639050715857607, 83639027011494777283064583268678718843, 237826165608708003941944469905843354705, 231707683915242052796886276983724691027, 146089830852925550139294146760718642221, 25604562707667550478623425477029052785, 108577663147976992047614498924706939204, 69040319834829375335287614995435269276, 169933229202934375632745753379104389929, 72693008284867494808267387710985847974, 158548279589965576940349068403862889270, 49458101234256610254825879149914255140, 24389558269688411084589654047215902968, 210567980379246548727819953025607019254, 110423375132252997825868399832298953831, 109589895677661968369424757992411668628, 66177577069199763925999718357846633613, 83602293803708828242273186265396676466, 172226271050176278536911356541786290551, 85799805809703976643034084477579915867, 179399990302447560847151603157937241688, 81687654752229170984692833277072534294, 160766441640281044008645821822296569868, 100306680611749750243920501921769642984, 42195187332833922597871030332905266026, 238918420772178508359295233180536910768, 221685929158944699801776621298532178665, 209349638787804999657456057184702655805, 183953393268431043006359511952782903516, 137364333131365794683132159746962959967, 15637689373906596015395350692459218048, 145956368418289159411911667337899986262, 197987711355277581048877821432652325207, 125421308989313724733467092345532539875, 90525081516582408488547894471421476595, 107405840115256692042814887586009104950, 71587500700172519801649824611045199280, 10155721246869986043302768283257682883, 100522792569358427133597834727509523742, 244473925018526409824670892423775482110, 50746138425761666610345252577572889037, 142188269919422432629363225167297071042, 8235113926890598897465093754260801947, 174540885017405784646782293055852044631, 171949847901434672429841435895697323702, 34391199559497599434575002007581170988, 7337868660819385932166025474594964373, 89608475952042154068811282935241824949, 162561097613906905390170334328135062933, 252566077272083954707900007055640560669, 4284637988579219107997224848114896904, 220026371387782427901244689037957398829, 86019060485320999498155965142619258089, 19304861731281576405798605142335886482, 123188238667151068575810494833929221938, 125089740978532716086813732154638565196, 252061524500088702951562270741214799294, 89528875472312768404823823905699760649, 63307407053590054220492282094909190524, 24389558269688411084589654047215902968, 43835777110183833958990705735152973942, 196543204310466258426232803779025620993, 225032412767857179129234169288824097261, 50292890880286260984317361296226049436, 64928956886509273090981701066528078331, 25408225921774957745573142542576755590, 235921667882292842303120860570747218086, 217132603855089441017750752624514343437, 11106129204256119599329380588789107048, 147501327490657927610543345089238991876, 158091159632919983870444592039392730373, 254215886971254771885657857148535673338, 129869106474614345624950211566868568809, 10425702332274469498479699675668087022, 136595953187315682777976356839442311764, 1607792140397737044118662059498732982, 23710000155612873207506044342091514799, 118571340370877720354330132780832828911, 194624784476702188629452374731837038856, 51332273108989067644245919615090753756, 240921043405288511960365826273938845156, 158670188709175825212687487436006138030, 133641825913283256858340618209700716053, 43054466484232130048301271684438593412, 20361972967806283315536154125012604660, 135700832615866572032111395529532615300, 160609169788639387827865051539103507016, 100576279475451993660766480883708996211, 215424685541583305069271024253690375127, 60018956375784961551937423504137141702, 107997941230633604720421526632224279451, 219482010609171816035007605036664317041, 22173526221024380740269311947729076493, 249746554302052221287371350978970766087, 93207359085331319264650563354951254906, 221421697282310997113867048083058096452, 61834092635779365101011109381392037516, 162215218701897689647766394615098617152, 141856131587452385513407955541400099703, 177910903795887762773545874929605680469, 228832704523723308335513552177377803295, 229427981969125094398744034150988525118, 217938760689082034514008764751385239765, 3238055163645731541423094980789895030, 42308449860804765793467328093112118974, 254764518926620089428032312378507653680, 215733901156118606036318409454786603209, 59640829345183339336712595595022506261, 33515071724475649656070325837411550208, 51175659069843551646353202764296812462, 211462959696081863041546889096760952490, 230559603938699838189391087728971115767, 85878911733601049548471257838175175563, 214134904074265214033878852207103328297, 160702405980652445507529591230654474171, 223755040649990285320102091954198427148, 166476753890268002826149533120107157745, 26283916639129998224675164834425763384, 232971495542024495583092055361321729894, 79741799146769724681649849525636816379, 228506526471280046809909301748098760369, 167502422063741368765891061653686283332, 26984184590668253713951516794937308166, 105952393031190074432183821281493254, 113823192955281698937767041115166174652, 93264047694114869263275726820602569731, 55481974783112950660682138071588408040, 108961894273530837550182447112767144669, 47975793549419083945738147934068241928, 204024371586357035343484206754422857590, 251859351272989525849999231358507018068, 75939709807860493804628805619699991501, 129031774446142139804436921156668129187, 110764318451937254261883856778359218969, 246404864722813298477426808193494673610, 153818236564405157581869620439634140065, 246125932167584353084676586883038397451]这题跟cryptohack上的二次剩余题目基本一样，题目中提到勒让德指勒让德符号也是二次剩余，于是根据欧拉准则试了一下，果然
$$
a^{\frac{p-1}{2}}\equiv 1 \mod p
$$
发现a是p的二次剩余，所以就可以根据ciphertext中的数(令其为num)观察是否满足$num^{\frac{p-1}{2}} \equiv 1 \mod p$即可，若满足则b=0，否则b=1，把二进制数还原出来就可以解出题目了，解题代码如下：
from Crypto.Util.number import *
import gmpy2
p = 258669765135238783146000574794031096183
a = 144901483389896508632771215712413815934
# print(pow(a, (p-1)//2, p)) # 1
def decrypt(cipher):
plain_bits = []
for num in cipher:
if gmpy2.powmod(num, (p-1) // 2, p) == 1:
plain_bits.append('0')
elif gmpy2.powmod(num, (p-1) // 2, p) != 1:
plain_bits.append('1')
plaintext = ''.join(plain_bits)
flag_bytes = []
for i in range(0, len(plaintext), 8):
byte = plaintext[i:i+8] #注意前开后闭的特性
flag_bytes.append(int(byte, 2))
return bytes(flag_bytes)
ciphertext = [102230607782303286066661803375943337852, 196795077203291879584123548614536291210, 41820965969318717978206410470942308653, 207485265608553973031638961376379316991, 126241934830164184030184483965965358511, 20250852993510047910828861636740192486, 103669039044817273633962139070912140023, 97337342479349334554052986501856387313, 159127719377115088432849153087501377529, 45764236700940832554086668329121194445, 35275004033464216369574866255836768148, 52905563179465420745275423120979831405, 17032180473319795641143474346227445013, 29477780450507011415073117531375947096, 55487351149573346854028771906741727601, 121576510894250531063152466107000055279, 69959515052241122548546701060784004682, 173839335744520746760315021378911211216, 28266103662329817802592951699263023295, 194965730205655016437216590690038884309, 208284966254343254016582889051763066574, 137680272193449000169293006333866420934, 250634504150859449051246497912830488025, 124228075953362483108097926850143387433, 232956176229023369857830577971626577196, 149441784891021006224395235471825205661, 118758326165875568431376314508740278934, 222296215466271835013184903421917936512, 49132466023594939909761224481560782731, 406286678537520849308828749751513339, 215122152883292859254246948661946520324, 81283590250399459209567683991648438199, 150395133067480380674905743031927410663, 5710878479977467762548400320726575491, 83627753774286426170934105100463456109, 164968224377869331545649899270867630850, 241057183685774160581265732812497247167, 109136287048010096863680430193408099828, 116313129605409961931811582899075031153, 202739016625709380026000805340243458300, 25408225921774957745573142542576755590, 151336258796933656160956289529558246702, 2947189044370494063643525166023973095, 228678413963736672394976193093568181979, 40627063032321835707220414670018641024, 55446789315226949622969082042881319148, 32219108726651509070669836923591948459, 134454924722414419191920784435633637634, 97952023967728640730045857104376826039, 20659076942504417479953787092276592682, 93281761173713729777326842152860901050, 133634773495582264000160065317239987936, 79976720152435218818731114555425458470, 234654694673289327542859971371886984118, 51332273108989067644245919615090753756, 134120280423303717489979349737802826605, 182001158305920226320085758522717203725, 98408798757865562737462169470346158516, 78200435603900368619334272308272773797, 232796357836930341547987600782979821555, 589106968861493082018132081244848952, 24186003230092331554886767628744415123, 236070626491251466741246103662922841423, 238699080882667864827094121849090696547, 141659873734297659078160283051728812410, 228977113517120063860252637394240795552, 236613527842969921794004708284265628300, 145522034982744654991661857596541755396, 249608374387044047328725156440984678776, 325110572051913836681821746093704556, 171492052199838424502681030556098576483, 156498865212994371079795360268866413702, 196747701509389071931992996873572785043, 70811811603137896158765356680364490781, 83672551582385607422240464086955462541, 117961603623637997457153763936550310698, 224448821395214505399297116719025174412, 4598815373009554321735225938200807251, 194892269604260726530091473301914449005, 127484628022155760909820605666827662175, 208706240846212140439291547368645656474, 14102286481104997303651684152195298336, 6129503335471304345451795609683770657, 103799668048593149396277157385628834185, 185813375481410513002496683918106238351, 233491689316882978147517340230794025796, 46274083097168831187719988888816378961, 119487551553664772614629936285345836934, 84340029922118279362389419277915602509, 88253743193124528032223101368846247085, 227895357640018330099501504941388167432, 92189947144174433744195727086236905626, 83114957902192791332190922428847199876, 173535754090441937731619031520699325122, 192309407933789484835602071782330798398, 255421921600128994923738650157598053776, 155535082468314012733563336837641958625, 49064798421022327310707074253263463055, 161216416471071644769301963857685054031, 252480348817188872515008985698620059851, 75854882798183185741756645038434215611, 256065006192683011190132982128640682537, 87507510173514424105732562474643251223, 163309795132131534875147566536485288212, 253583084320404985699510129361746869059, 253300112521651972637580307326576568313, 239027717080729650738678032571840680727, 117444657686971615526398894470673026034, 215470942802874046857958621181684551426, 58767098748728136687851735836323448020, 249357164697409977883764098879705065535, 174705348385893117518084017669958647345, 211108767177375215605155301209259781232, 57829566748907062397366819001461941421, 88265742700024922112974862134385921564, 80952107622167923709226013231566882261, 236078582132483864916117213281193714198, 193448482646563141692726575550417225891, 245972799166806058223048506073553726233, 10132977708896091601871557249244373666, 201785418152654519825849206312616081028, 15169816744048531212384271865884567710, 122545328290385950043826822277924297182, 202918646192255177261567701479991753600, 32696887488223731055835744711207261936, 88319352182963224921157305627381030375, 92381505322264045777004475690398861771, 189745654013352563126968415157143821842, 152254915005998949299817641843658795579, 198032433618991362619448347415342295581, 84073892809321676935569114878067118319, 82243805869584256211699602267760745768, 61994229948266781537191603999495995852, 253668765227759797787675352833142466255, 38865376724677211964966907748953557125, 134615436811268347303232550777225944929, 176932422465426107783498083830285780588, 207573742393618910694054452362826628208, 200033130835394442710748301293534928706, 127536063935293533700918451145963158658, 219125698281820710910675956971948816959, 179795893258398750139395156587561075767, 69649628109726874051635160004398498964, 241433717681314766463039563422535023524, 202664264135718511331695232476272832350, 205151096657425932591242432052912914182, 210305712465948130683966275157181140301, 196555690055906934925300527324955477733, 66817932643964538216259564711698986077, 95270796440975607179107356182889534333, 123226880424532374188134357659879826495, 53506495440223773538415807620524749240, 19253217887083870834249774316467647628, 165699356396365023442008488156823647206, 107809175498119862854792975070673056027, 250453989887421415931162217952559757164, 171492052199838424502681030556098576483, 133778166882550119563444625306816232463, 149009301604122447269581792013291889175, 9982418254629616281350713836647603294, 203486292122499140756846060502464655972, 157686696123400087437836943220926921848, 88338919773540412238116717043122711811, 113265824169274322024623493892867211478, 5549372099744960679418616304893848801, 12431828907518852062050349123660880165, 183957934738536914983862053251433028750, 42027289270308356303682029801998790750, 117406080036483925915502666019795783905, 154312255292300186042636734144948304054, 143706917273862261295046346995206133170, 50088136095338601440516112338120787526, 250634504150859449051246497912830488025, 8073010289877796888705519374892639903, 40049582814576788803483039836229025416, 227012342545923833983403067401561291645, 201776603581414625783054400184026088994, 55474945478884522762318445841998187357, 221515530211550293408010846844218019597, 172650752042211610909190315288155597255, 67046194931321172530462444254204111483, 207435868835185636819659137800256834557, 188063222224545200294767050268070647452, 58099349021260301211275261896736590564, 23598877596106927870697531042828774738, 58546308516383335224739442370238545000, 58125311541947998710088435169901475101, 238219925698115060748249043752036454438, 203910234934340893915761800653823457631, 190854889967769152565565000250829375099, 37573623890629846209257307181880876288, 226220240200270623843038279593586687278, 144246075981535671790438155977352345487, 14665770553338784222331493932533448756, 37992062606775322664977502677838074649, 47370175759976523832233910009306151684, 97047813247943880266351445874642842468, 237607444658797800072728280983357541134, 174853113478993738890584814806707459112, 17104608155861584438824639050715857607, 83639027011494777283064583268678718843, 237826165608708003941944469905843354705, 231707683915242052796886276983724691027, 146089830852925550139294146760718642221, 25604562707667550478623425477029052785, 108577663147976992047614498924706939204, 69040319834829375335287614995435269276, 169933229202934375632745753379104389929, 72693008284867494808267387710985847974, 158548279589965576940349068403862889270, 49458101234256610254825879149914255140, 24389558269688411084589654047215902968, 210567980379246548727819953025607019254, 110423375132252997825868399832298953831, 109589895677661968369424757992411668628, 66177577069199763925999718357846633613, 83602293803708828242273186265396676466, 172226271050176278536911356541786290551, 85799805809703976643034084477579915867, 179399990302447560847151603157937241688, 81687654752229170984692833277072534294, 160766441640281044008645821822296569868, 100306680611749750243920501921769642984, 42195187332833922597871030332905266026, 238918420772178508359295233180536910768, 221685929158944699801776621298532178665, 209349638787804999657456057184702655805, 183953393268431043006359511952782903516, 137364333131365794683132159746962959967, 15637689373906596015395350692459218048, 145956368418289159411911667337899986262, 197987711355277581048877821432652325207, 125421308989313724733467092345532539875, 90525081516582408488547894471421476595, 107405840115256692042814887586009104950, 71587500700172519801649824611045199280, 10155721246869986043302768283257682883, 100522792569358427133597834727509523742, 244473925018526409824670892423775482110, 50746138425761666610345252577572889037, 142188269919422432629363225167297071042, 8235113926890598897465093754260801947, 174540885017405784646782293055852044631, 171949847901434672429841435895697323702, 34391199559497599434575002007581170988, 7337868660819385932166025474594964373, 89608475952042154068811282935241824949, 162561097613906905390170334328135062933, 252566077272083954707900007055640560669, 4284637988579219107997224848114896904, 220026371387782427901244689037957398829, 86019060485320999498155965142619258089, 19304861731281576405798605142335886482, 123188238667151068575810494833929221938, 125089740978532716086813732154638565196, 252061524500088702951562270741214799294, 89528875472312768404823823905699760649, 63307407053590054220492282094909190524, 24389558269688411084589654047215902968, 43835777110183833958990705735152973942, 196543204310466258426232803779025620993, 225032412767857179129234169288824097261, 50292890880286260984317361296226049436, 64928956886509273090981701066528078331, 25408225921774957745573142542576755590, 235921667882292842303120860570747218086, 217132603855089441017750752624514343437, 11106129204256119599329380588789107048, 147501327490657927610543345089238991876, 158091159632919983870444592039392730373, 254215886971254771885657857148535673338, 129869106474614345624950211566868568809, 10425702332274469498479699675668087022, 136595953187315682777976356839442311764, 1607792140397737044118662059498732982, 23710000155612873207506044342091514799, 118571340370877720354330132780832828911, 194624784476702188629452374731837038856, 51332273108989067644245919615090753756, 240921043405288511960365826273938845156, 158670188709175825212687487436006138030, 133641825913283256858340618209700716053, 43054466484232130048301271684438593412, 20361972967806283315536154125012604660, 135700832615866572032111395529532615300, 160609169788639387827865051539103507016, 100576279475451993660766480883708996211, 215424685541583305069271024253690375127, 60018956375784961551937423504137141702, 107997941230633604720421526632224279451, 219482010609171816035007605036664317041, 22173526221024380740269311947729076493, 249746554302052221287371350978970766087, 93207359085331319264650563354951254906, 221421697282310997113867048083058096452, 61834092635779365101011109381392037516, 162215218701897689647766394615098617152, 141856131587452385513407955541400099703, 177910903795887762773545874929605680469, 228832704523723308335513552177377803295, 229427981969125094398744034150988525118, 217938760689082034514008764751385239765, 3238055163645731541423094980789895030, 42308449860804765793467328093112118974, 254764518926620089428032312378507653680, 215733901156118606036318409454786603209, 59640829345183339336712595595022506261, 33515071724475649656070325837411550208, 51175659069843551646353202764296812462, 211462959696081863041546889096760952490, 230559603938699838189391087728971115767, 85878911733601049548471257838175175563, 214134904074265214033878852207103328297, 160702405980652445507529591230654474171, 223755040649990285320102091954198427148, 166476753890268002826149533120107157745, 26283916639129998224675164834425763384, 232971495542024495583092055361321729894, 79741799146769724681649849525636816379, 228506526471280046809909301748098760369, 167502422063741368765891061653686283332, 26984184590668253713951516794937308166, 105952393031190074432183821281493254, 113823192955281698937767041115166174652, 93264047694114869263275726820602569731, 55481974783112950660682138071588408040, 108961894273530837550182447112767144669, 47975793549419083945738147934068241928, 204024371586357035343484206754422857590, 251859351272989525849999231358507018068, 75939709807860493804628805619699991501, 129031774446142139804436921156668129187, 110764318451937254261883856778359218969, 246404864722813298477426808193494673610, 153818236564405157581869620439634140065, 246125932167584353084676586883038397451]
print(decrypt(ciphertext))
# b'moectf{Y0u_h@v3_ju5t_s01v3d_7h1s_pr0b13m!}'happyRSA
题目描述不语，只是一味的happy，这题其实有点痛苦的，题目代码如下：
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
from sympy import totient
from secret import flag
def power_tower_mod(a, k, m): # a↑↑k mod m
if k == 1:
return a % m
exp = power_tower_mod(a, k - 1, totient(m))
return pow(a, int(exp), int(m))
p = getPrime(512)
q = getPrime(512)
r = 123456
n = p * q
e = 65537
n_phi = p + q - 1
x = power_tower_mod(n_phi + 1, r, pow(n_phi, 3))
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"x = {x}")
'''
n = 128523866891628647198256249821889078729612915602126813095353326058434117743331117354307769466834709121615383318360553158180793808091715290853250784591576293353438657705902690576369228616974691526529115840225288717188674903706286837772359866451871219784305209267680502055721789166823585304852101129034033822731
e = 65537
c = 125986017030189249606833383146319528808010980928552142070952791820726011301355101112751401734059277025967527782109331573869703458333443026446504541008332002497683482554529670817491746530944661661838872530737844860894779846008432862757182462997411607513582892540745324152395112372620247143278397038318619295886
x = 522964948416919148730075013940176144502085141572251634384238148239059418865743755566045480035498265634350869368780682933647857349700575757065055513839460630399915983325017019073643523849095374946914449481491243177810902947558024707988938268598599450358141276922628627391081922608389234345668009502520912713141
'''对题中函数的分析
题目中的函数power_tower_mod实际上是在模的意义下进行幂塔运算，exp: $2\upuparrows 3 = 2^{2^2} = 16$
本身r=123456的幂塔是很难计算出来的，但是这是在模m下的，就可以应用欧拉定理，即 当 $\gcd(a, m) = 1$ 时有 $a^b\equiv a^{b\ mod\ \phi(m)} \mod m$
其实这个函数本身并不是解题重点，看懂在干啥就好
对多泄露的x进行解析
我们令$u=nphi$，则$x\equiv (u+1)^k \mod u^3$，其中$k=(u+1)\upuparrows (r-1)$是一个极大的正整数，在此题中可以直接视为正无穷
对上式进行多项式展开，然后直接将大于等于3次方的项约掉得到 $$x\equiv 1 + ku + \frac{k(k-1)}{2} u^2 \mod u^3$$
观察$ku$和$\frac{k(k-1)}{2} u^2 \mod u^3$还发现 $k\equiv 1\mod u$和 $k\equiv u+1 \mod u^2$，下面给出证明：
$$\because \forall t\in \mathbb{Z}:(u+1)^t\equiv 1^t\equiv 1 \mod u$$
$$\therefore k是(u+1)取幂得到的，即k\equiv 1 \mod u$$
$$\because \forall t\in \mathbb{Z}:(u+1)^t\equiv 1+tu\mod u^2$$
$$\therefore a_1=u+1\equiv u+1,\ a_2=(u+1)^{u+1}\equiv(u+1)u+1\equiv u+1，\cdots$$
$$\therefore k = (u+1)\upuparrows (r-1)\equiv u+1\mod u^2$$
得到上述结论后进一步得到$\begin{cases}k = tu+1\cr k=su^2+u+1\cr\end{cases}(t,s\in \mathbb{Z})$，则
$$
\begin{cases}ku= su^3+u^2+u\equiv u^2+u \mod u^3\cr
\frac{k(k-1)}{2} u^2=\frac{(ku+1)ku}{2}\equiv 0\mod u
\end{cases}
$$
故原式化简成$x\equiv u^2+u+1\mod u^3$，当$u\geq 2$时，$u^2+u+1<u^3$，故$x=u^2+u+1$
至此得到关于p,q的方程组，从而能解出p,q，解题代码如下：
from Crypto.Util.number import *
import sympy as sp
n = 128523866891628647198256249821889078729612915602126813095353326058434117743331117354307769466834709121615383318360553158180793808091715290853250784591576293353438657705902690576369228616974691526529115840225288717188674903706286837772359866451871219784305209267680502055721789166823585304852101129034033822731
e = 65537
c = 125986017030189249606833383146319528808010980928552142070952791820726011301355101112751401734059277025967527782109331573869703458333443026446504541008332002497683482554529670817491746530944661661838872530737844860894779846008432862757182462997411607513582892540745324152395112372620247143278397038318619295886
x = 522964948416919148730075013940176144502085141572251634384238148239059418865743755566045480035498265634350869368780682933647857349700575757065055513839460630399915983325017019073643523849095374946914449481491243177810902947558024707988938268598599450358141276922628627391081922608389234345668009502520912713141
# u = sp.symbols('u')
# eq = u ** 2 + u + 1 - x
# solution = sp.solve(eq, u)
# print(solution)
# [-22868426889861032781124012462674777755016542653263990991148930550942626182568649661622845168973125812949819632974369308680784443278135433344305388840858460, 22868426889861032781124012462674777755016542653263990991148930550942626182568649661622845168973125812949819632974369308680784443278135433344305388840858459]
u = 22868426889861032781124012462674777755016542653263990991148930550942626182568649661622845168973125812949819632974369308680784443278135433344305388840858459
# p, q = sp.symbols('p q')
# eq1 = p * q - n
# eq2 = p + q - 1 - u
# solution = sp.solve((eq1, eq2), (p, q))
# print(solution)
# [(9945129762728223239577902859697634331802808038804425181830911196951473687220829485821977589031820657309900258660386034425185489584350052547507906943390467, 12923297127132809541546109602977143423213734614459565809318019353991152495347820175800867579941305155639919374313983274255598953693785380796797481897467993), (12923297127132809541546109602977143423213734614459565809318019353991152495347820175800867579941305155639919374313983274255598953693785380796797481897467993, 9945129762728223239577902859697634331802808038804425181830911196951473687220829485821977589031820657309900258660386034425185489584350052547507906943390467)]
p = 9945129762728223239577902859697634331802808038804425181830911196951473687220829485821977589031820657309900258660386034425185489584350052547507906943390467
q = 12923297127132809541546109602977143423213734614459565809318019353991152495347820175800867579941305155639919374313983274255598953693785380796797481897467993
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# b'moectf{rsa_and_s7h_e1se}'Misc
Misc入门指北
就是在PDF中ctrl+F找到那一行隐形的字，复制粘贴出来就看到flag了
ez_LSB
从题目中就知道是LSB隐写了，直接上stegsolve找RGB为0的时候看就好，然后发现了flag
但是交上去发现不对，然后想了一下，这flag着实奇怪了点，然后就猜到是base64了，就扔到随波逐流上了，果然...
![]
SSTV
题目给了一个音频文件，打开一听挺刺耳的，应该就是加密音频了，结合题目可以知道是SSTV，于是下载了RX-SSTV再把音频一放直接就出flag了
捂住一只耳
题目给了一个音频文件，看题目和描述显然是分离声道，于是打开Audacity
打开多视图并分离立体声到单声道就得到
很明显上面那个声道有一段小音频，点开来听是摩斯密码的音频，就去在线网站解密得到flag
Enchantment
题目给了一个pcapng文件，然后提示说附魔台的文字似乎有问题，这八竿子打不着的附魔台从哪里来？
这是我第一次做流量分析题(doge)
用wireshark看看http，发现了一个png，立马警觉
追踪http流看ASCII，看到PNG头在很上面的位置，这个有点用
往下找PNG尾，也就是IEND，在红色段的末尾找到了
然后看原始数据，搜索8950，这是png文件头，发现有两个，第一个在前面，第二个则在数据末尾，结合刚刚看的PNG头的位置知道应该是第一个8950
然后整个png文件的16进制数据应该一直到红色段末的0d0a，因为这是png文件尾，而且位置也和刚刚看到的IEND位置相同
接下来我用winhex创建了一个空的16进制文件，然后把那一大段数据(从8950到0d0a)全部粘贴上去得到新文件，保存到桌面后加上png后缀，得到如下图片
（原来是MC附魔台...）加上题目提示的附魔台文字有问题，于是去网上找到了标准银河字母表
所以从上往下的内容翻译过来是：
1.the flag is below
2.now you have
3.mastered enchanting
故flag为moectf{now_you_have_mastered_enchanting}
ez_png
题目让我们注意某些数据段的长短似乎不太协调，看到这个第一反应就是检查IDAT，用tweakpng查看发现一个IDAT块很莫名其妙，可能有问题
觉得有问题但是也不会查，于是就去查AI了(感谢ds和gpt)，用zsteg工具检测了一下这个图片，发现IDAT块确实有异常，在zlib流后面还有别的数据
用命令将这个数据块提取出来(本人对zsteg命令一窍不通，AI神力)
输入命令判断数据类型：file extra.bin
返回为zlib压缩数据：extra.bin: zlib compressed data
那就直接上脚本zlib解压看看(别问脚本从哪来，看代码就知道)，也是顺利解出flag
import zlib
with open('extra.bin', 'rb') as f:
data = f.read()
try:
decompressed_data = zlib.decompress(data)
print("Decompressed data (hex):", decompressed_data.hex())
print("Decompressed data (raw):", decompressed_data)
except Exception as e:
print("Decompression error:", e)
# Decompressed data (hex): 6d6f656374667b68314464456e5f5034596c4f61445f494e2d496434547d
# Decompressed data (raw): b'moectf{h1DdEn_P4YlOaD_IN-Id4T}'reverse
逆向工程入门指北
在IDA中打开附件，先F5查看源代码，再shift+F12打开字符串模式就找到flag了
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 IceMarshal's Blog！
评论