1
from Crypto.Util.number import *
#小鼎，24岁。网安专业old star.最近入坑ctf，想体验一把梭的感觉。于是他的朋友给他找来了cahtylin先生。cahtylin先生听闻，欣然写下此题。
falg = '?????'
m = bytes_to_long(falg)
print(m)
'''
m =365570067986928236989573788230270407130085464313909252527513197832758480604817399268366313889131551088558394832418649150417321940578277210433329648095352247884911033780856767602238960538520312352025465812228462858158997175162265505345470937926646520732298730237509998898024691120409770049168658027104966429925920045510148612448817
'''
#什么年代了还在做低加密指数的传统RSA？我就猜出题人在100以内找个d然后模拟出e加密的。
签道题，只提供了n c，没有给e d，题目暗示私钥指数很小，所以直接枚举d：在一个小范围内挨个计算以下公式，然后判断结果是不是可读的明文，Python中使用 pow(c, d, n) 就可以高效完成。结果转换成字节序列再观察flag格式。私钥指数d过小，整个穷举过程才七次。
题解
from Crypto.Util.number import long_to_bytes
n = 0x846d39bff2e430ce49d3230c7f00b81b23e4f0c733f7f52f6a5d32460e456e5f
c = 0x4eeec51849a85e5a6566f8d73a74b1e64959aa893f98e01c1e02c3120496f8b1
for d in range(12):
pt_bytes = long_to_bytes(pow(c, d, n))
print(f"d = {d} => {pt_bytes}")
2
from Crypto.Util.number import *
from sympy import *
def givemeprime(x):
''' x < 502'''
p = getPrime(x)
print(p)
while (p).bit_length() <= 512:
p = nextprime(p*2**10)
return p
p = givemeprime(10)
q = givemeprime(10)
n = p*q
flag=b'?????'
m = bytes_to_long(flag)
e=2**32+1
c=pow(m,e,n)
print('n=',n)
print('c=',c)
'''
n= 9007989895621669259301762739598643626213892494330778168383286295463641223987867033273111296978959160408689408884183780314498828688143466136060628598819311509949865018608092450964012727526450914131409697944090166113416984201622940137239452703698919890772056684013237404520834408811118739546684092365102406400768733
c= 3155015611586304247269005826733691392085437186284673630268852999607965592611252562808748872502491405722341353019602057980123546192900359248245073985988035982837057433789538035295585235536446429172802713235552248615722281314286849930993306403034865999074888279573724168174433746677852218329931104122667029131804586
'''
题目中给的素数是通过10bit开始，反复执行相同的扩展和取下一素数步骤来得到的，这个过程是固定的，所以按照同样的方式去生成并验证每一个可能的候选值。
对于每个 10 bit 的素数，用题目给出的生成逻辑不断放大取下一素数，一直得到大约512位长度的候选值。要是把这个候选值与密文模数做最大公因数运算，结果不是1且也不是本身就能判断这就是我们要找的素数。找到其中一个素数后就能直接用它去除掉模数来得到另一个素数，最后用这两个素数计算出私钥再把密文还原成明文。
题解
from sympy import isprime, nextprime, gcd, invert
from Crypto.Util.number import long_to_bytes
n =
c =
e = 2**32 + 1
ten_bit_primes = [x for x in range(2**9, 2**10) if isprime(x)]
p_found = None
for base_prime in ten_bit_primes:
candidate = base_prime
while candidate.bit_length() <= 512:
candidate = nextprime(candidate * 2**10)
g = gcd(n, candidate)
if 1 < g < n:
p_found = int(g)
break
p = p_found
q = n // p
phi = (p-1)*(q-1)
d = int(invert(e, phi))
m = pow(int(c), d, int(n))
flag = long_to_bytes(m)
print(flag)
3
21892299583455516902678177407943098723020343792737269219307899917648316295261201016328488524278932283999750824537049252476708912581411433116481435169820171800812269837405200686395697568215005205362068960832774807526976480752697635422484817926191507531940434634990099905635630699300684624818348075269761353018523447067460493194043463499009990512649370320429973934883223194043463499009990592737269219307899917677787420494356677625885484473810535422484817926191507531940434634990099905927372692193078999176777874204913530185234470674604948075269764356677625885484473810583621143489848422977218922995834555169026218922995834555169026777874204959425114757512643212875125=I2GWRFMO33EWUZM
一眼斐波那契数列，题目是由很多Fibonacci数拼接起来的。先把很多项斐波那契数列算了再转成字符串存到一个结构里，整一个字符串到index的映射。从数字串左侧开始尝试用可能长度去匹配看是不是哪个斐波那契的字符串，如果匹配成功就截掉把项号存下来。匹配了就在数字串中向后移动指针接着匹配，直到完全处理完。一般这种类型的题最后把数列中的下标当作ASCII 码来映射，完事。
为什么要用最长匹配？⭠斐波那契数越到后面越长，如果先用短匹配就容易错误解析。
题解
fib = [0, 1]
for i in range(2, 1000):
fib.append(fib[-1] + fib[-2])
fib_str_map = {}
for index, value in enumerate(fib):
fib_str_map[str(value)] = index
giant_str = " " # 题目
i = 0
indices = []
while i < len(giant_str):
matched = False
for length in range(100, 0, -1):
segment = giant_str[i:i+length]
if segment in fib_str_map:
indices.append(fib_str_map[segment])
i += length
matched = True
break
if not matched:
print("no")
break
decoded_flag = ''.join(chr(idx) for idx in indices)
print(decoded_flag)
4
from random import shuffle
from secret import secret_msg
ALPHABET = '0123456789abcdef'
class Cipher:
def __init__(self, key):
self.key = key
self.n = len(self.key)
self.s = 7
def add(self, num1, num2):
res = 0
for i in range(4):
res += (((num1 & 1) + (num2 & 1)) % 2) << i
num1 >>= 1
num2 >>= 1
return res
def encrypt(self, msg):
key = self.key
s = self.s
ciphertext = ''
for m_i in msg:
c_i = key[self.add(key.index(m_i), s)]
ciphertext += c_i
s = key.index(m_i)
return ciphertext
plaintext = b'The secret message is:'.hex() + secret_msg.hex()
key = list(ALPHABET)
shuffle(key)
cipher = Cipher(key)
ciphertext = cipher.encrypt(plaintext)
print(ciphertext)
# output:
# 85677bc8302bb20f3be728f99be0002ee88bc8fdc045b80e1dd22bc8fcc0034dd809e8f77023fbc83cd02ec8fbb11cc02cdbb62837677bc8f2277eeaaaabb1188bc998087bef3bcf40683cd02eef48f44aaee805b8045453a546815639e6592c173e4994e044a9084ea4000049e1e7e9873fc90ab9e1d4437fc9836aa80423cc2198882a
做不出来，只知道是xor运算，没有思路所以扔给了月薪20美金的gpt。
这是一个利用异或与打乱排列构造的简单自同步加密。加密流程中，程序会先将 0123456789abcdef 打乱成某个未知的排列 key，随后依次取明文中的每个十六进制字符，用其在 key 里的索引与上一步存储的状态 s 做异或，再到 key 里查找对应字符输出为密文。这样一来，解密时如果能恢复出这套排列 key 以及异或时使用的状态变化规则，就能还原整个明文。
因为一部分明文（“The secret message is:”）是已知的，它的明文与密文就形成了一系列足以约束整个排列的方程：每个明文字符在 key 里的位置与相应的密文字符在 key 里的位置之间通过异或关系关联。只要编写一个回溯或约束求解的脚本，就能在有限的 16 个字符打乱排列里快速唯一地确定 key 的完整映射。有了正确的 key 和异或规则，便可对全部密文做反向运算，拿到完整明文，其中就包括真正的 Flag。
题解(0人工)
import string
from collections import deque
ALPHABET = '0123456789abcdef'
CIPHERTEXT = "85677bc8302bb20f3be728f99be0002ee88bc8f..." # 题目中给出的长串
known_ascii = b"The secret message is:"
known_hex = known_ascii.hex() # '54686520736563726574206d6573736167652069733a'
known_len = len(known_hex)
# K[x] = 某个hex字符, X[ch] = x
K = [None]*16
X = {ch: None for ch in ALPHABET}
# 初始状态 (i, s, K, X)
init = (0, 7, K, X)
stack = deque()
stack.append(init)
solutions = []
def copy_mapping(K_, X_):
return (K_[:], dict(X_))
while stack:
i, s, K_current, X_current = stack.pop()
if i == known_len:
solutions.append((K_current, X_current))
continue
p_i = known_hex[i] # 明文字符
c_i = CIPHERTEXT[i] # 密文字符
xp = X_current[p_i] # 可能是 None(未知)或某个数字
xc = X_current[c_i]
# 约束：xc = xp ^ s
# 然后下轮 s' = xp
def try_fill(xp_val, xc_val, K_, X_):
# check conflicts
if xp_val < 0 or xp_val > 15: return None
if xc_val < 0 or xc_val > 15: return None
if (K_[xp_val] is not None and K_[xp_val] != p_i): return None
if (K_[xc_val] is not None and K_[xc_val] != c_i): return None
if (X_[p_i] is not None and X_[p_i] != xp_val): return None
if (X_[c_i] is not None and X_[c_i] != xc_val): return None
K_next, X_next = copy_mapping(K_, X_)
K_next[xp_val] = p_i
K_next[xc_val] = c_i
X_next[p_i] = xp_val
X_next[c_i] = xc_val
return (K_next, X_next)
if xp is not None and xc is not None:
# 二者都已知 -> 检查是否满足 xc == xp ^ s
if xc == (xp ^ s):
# ok
stack.append( (i+1, xp, K_current, X_current) )
elif xp is not None and xc is None:
want_xc = xp ^ s
candidate = try_fill(xp, want_xc, K_current, X_current)
if candidate:
k2, x2 = candidate
stack.append((i+1, xp, k2, x2))
elif xp is None and xc is not None:
want_xp = xc ^ s
candidate = try_fill(want_xp, xc, K_current, X_current)
if candidate:
k2, x2 = candidate
stack.append((i+1, want_xp, k2, x2))
else:
# xp, xc都没定
for guess_xp in range(16):
guess_xc = guess_xp ^ s
candidate = try_fill(guess_xp, guess_xc, K_current, X_current)
if candidate:
k2, x2 = candidate
stack.append((i+1, guess_xp, k2, x2))
print("[+] Found solutions:", len(solutions))
if len(solutions) > 0:
# pick first solution
K_solved, X_solved = solutions[0]
print("[+] Found a valid key mapping!")
# 用这个解来对 ciphertext 全部解密
def decrypt(ct, K_, X_):
s = 7
out_hex = []
for ch in ct:
# X(ch) = X(m) ^ s => X(m) = X(ch) ^ s
xp = X_[ch] ^ s
p_ch = K_[xp]
out_hex.append(p_ch)
s = xp
return "".join(out_hex)
plaintext_hex = decrypt(CIPHERTEXT, K_solved, X_solved)
plaintext_bytes = bytes.fromhex(plaintext_hex)
print("[+] Plaintext (ASCII):")
print(plaintext_bytes.decode('utf-8', errors='replace'))
5
from random import random
from Crypto.Util.number import *
from math import factorial
flag = b'ctfshow{******}'
def get_d(n):
d = 0
leak = 0
n_factorial = factorial(n) # n!
for x in range(1,11**111111111111111111111111111111111111111111111111111):
for y in range(1,11**11111111111111111111111111111111111111111111111111):
if (x + y) * n_factorial == x * y: # assert (x+y)N!=xy
d = (d + 1) % key
while True:
if isPrime(d):
break
else:
hint = getPrime(1111)
d += hint
leak += hint
return [d,leak]
p = getPrime(512)
q = getPrime(512)
n = p * q
phi_n = (p - 1) * (q - 1)
key = bytes_to_long(b'ctfshow' * 11)
d,leak = get_d(1111111)
e = inverse(d,phi_n)
c = pow(m,e,n)
print("n = {}".format(n))
print("c = {}".format(c))
print("leak = {}".format(leak))
n = 54574114381718620167617516254929393779619478308097113614916675753251123548928131184783684874283433005383416329333515148795542347110691860676572758697931909264778996887013262158676437681328356540522795904026051878217112848328807404132186855022441100415245863609800487131682707570632405183635021611108835267759
c = 6152360020770587319042211616230221955276231957369900018326509075246049533065274193822064664954312088370274199977933471629773286341632192578865475616294549753212257409853382739383167314755235136431546938621288480401985886224522239505956567272435201576625728864298081471539244545838583231944620511300185831132
leak = 16102974322718628332775750617032895793782360562291434204500149732571174230338263002384756014760949775420804601441832387500764784508882168206386996211671060761357982709828010115692143995397973526517421403555634084184433318856377393377764138389228581916413401245531536422259037376817202123767631518253694641004207511682233164891541552631514
错误思路
题目给出一个不可能计算完毕的函数，已知 n、密文 c 以及一个神秘的 leak 值，猜测leak 与 RSA 私钥有关，很可能是某种泄露。我猜测了常用的 e 值3，然后检查 leak 是否能被这些值整除。用65537除一下leak，有余数所以e不等于65537，用3试了发现leak能被3整除，我当时觉得leak就等于3，e=3
我用代码验证了 n = 5457411438171862016761751625492939377961947830809711361491667575…35267759 # (省略长整数) leak = 1610297432271862833277575061703289579378236056229143420450014973…52631514 # (省略长整数)
猜测 e = 3 并计算 d e = 3 d = leak / e print(d) 得到一个整数，验证 3*d确实与leak一致，得到d后利用RSA解密公式还原明文整数m，然后将整数转换为字节序列再解flag。
错误题解
from Crypto.Util.number import long_to_bytes
n = 54574114381718620167617516254929393779619478308097113614916675753251123548928131184783684874283433005383416329333515148795542347110691860676572758697931909264778996887013262158676437681328356540522795904026051878217112848328807404132186855022441100415245863609800487131682707570632405183635021611108835267759
c = 6152360020770587319042211616230221955276231957369900018326509075246049533065274193822064664954312088370274199977933471629773286341632192578865475616294549753212257409853382739383167314755235136431546938621288480401985886224522239505956567272435201576625728864298081471539244545838583231944620511300185831132
leak = 16102974322718628332775750617032895793782360562291434204500149732571174230338263002384756014760949775420804601441832387500764784508882168206386996211671060761357982709828010115692143995397973526517421403555634084184433318856377393377764138389228581916413401245531536422259037376817202123767631518253694641004207511682233164891541552631514
e = 3
d = leak // e # 整除得到 d
# 2. RSA 解密
m = pow(c, d, n)
plaintext = long_to_bytes(m)
try:
flag = plaintext.decode('utf-8')
except UnicodeDecodeError:
flag = plaintext.decode('utf-8', errors='ignore')
print("Recovered flag:", flag)
结果为 flag{ThiS__1s__7hE__Fun__0f__0000000000000000__4ND__1111111111111111}
正确思路
这里φ(n)未知，d = leak // e 是一个陷阱不符合RSA的正规原理，恰好在这道题的数据下可以解出一个伪造flag。。。应该是用了阶乘N!^2的约数个数的公式进行计算，通过计算每个质数在N!的阶乘因子中的指数，严格执行数论上的Legendre定理再利用计算出的d与leak构成私钥指数：d + leak。
题解
import math
from Crypto.Util.number import *
def generate_primes(n):
"""Generate all prime numbers up to n using the Sieve of Eratosthenes."""
sieve = [True] * (n + 1)
sieve[0:2] = [False, False]
for i in range(2, int(math.isqrt(n)) + 1):
if sieve[i]:
for multiple in range(i * i, n + 1, i):
sieve[multiple] = False
primes = [p for p, is_prime in enumerate(sieve) if is_prime]
return primes
def legendre_exponent(p, N):
"""Compute the exponent e_p of prime p in N! using Legendre's formula."""
exponent = 0
denom = p
while denom <= N:
exponent += N // denom
denom *= p
return exponent
def calculate_d(N, modulus=None):
"""Calculate d = τ(N!^2) = ∏(2e_p + 1) over all primes p ≤ N."""
primes = generate_primes(N)
d = 1
for p in primes:
e_p = legendre_exponent(p, N)
factor = 2 * e_p + 1
if modulus:
d = (d * factor) % modulus
else:
d *= factor
return d
N = 1111111
modulus = bytes_to_long(b'ctfshow' * 11)
d = calculate_d(N, modulus)
n = 54574114381718620167617516254929393779619478308097113614916675753251123548928131184783684874283433005383416329333515148795542347110691860676572758697931909264778996887013262158676437681328356540522795904026051878217112848328807404132186855022441100415245863609800487131682707570632405183635021611108835267759
c = 6152360020770587319042211616230221955276231957369900018326509075246049533065274193822064664954312088370274199977933471629773286341632192578865475616294549753212257409853382739383167314755235136431546938621288480401985886224522239505956567272435201576625728864298081471539244545838583231944620511300185831132
leak = 16102974322718628332775750617032895793782360562291434204500149732571174230338263002384756014760949775420804601441832387500764784508882168206386996211671060761357982709828010115692143995397973526517421403555634084184433318856377393377764138389228581916413401245531536422259037376817202123767631518253694641004207511682233164891541552631514
