one hint

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
\#!/usr/bin/env python3

def vigenere(pt,key):

res = ""

for i in range(len(pt)):

if pt[i] in "LITCTF{_}":

res += pt[i]

continue

res += chr((ord(pt[i])+ord(key[i%len(key)])-2*ord('a'))%26+ord('a'))

return res

def power(pt,n):

a = pt

for i in range(n):

a = vigenere(a, vigenere(a, a))

return a

flag = "LITCTF{redacted}"

print("hint 1: " + power(flag, 2345))
1
hint 1: LITCTF{fkxlafg_plk_qkuxbkgp_hucknkxk_khkx}

题目给出了自定义的 Vigenere 变种加密函数和一个迭代加密函数

vigenere函数:

  • 对不在 "LITCTF{_}" 中的字符进行加密
  • 加密公式:c = (pt_char + key_char - 2*'a') % 26 + 'a'
  • 等价于:c = (pt_char_index + key_char_index) % 26(字母索引计算)

power函数:

  • 进行n次迭代加密
  • 每次迭代:a = vigenere(a, vigenere(a, a))
  • 分析发现:vigenere(a, a) 相当于每个字符索引翻倍(模26)
  • 因此一次迭代相当于:a_next[i] = (3 * a[i]_index) % 26 + 'a'
  • n次迭代后:每个字符变换为 (3^n * original_index) % 26

对于2345次迭代:

  • 计算 3^2345 mod 26
  • 由于 3^3 = 27 ≡ 1 mod 26,阶为3
  • 2345 ÷ 3 = 781 * 3 + 2,余数为2
  • 所以 3^2345 ≡ 3^2 ≡ 9 mod 26

加密变换为乘以9(模26),因此解密需要乘以9的逆元:

  • 9 * x ≡ 1 mod 26
  • 9 * 3 = 27 ≡ 1 mod 26,所以逆元为3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def decrypt_power(hint, n_iterations=2345):

# 计算加密乘因子: 3^n_iterations mod26

# 由于3^3=1 mod26,所以乘因子 = 3^(n_iterations % 3) mod26

​ exp_factor = pow(3, n_iterations, 26) # 这等于9

# 然后求逆元

# 找x使得 (exp_factor * x) %26=1

# 对于9,逆元是3(因为9*3=27=1 mod26)

​ inv_mult = None
for x in range(26):
if (exp_factor * x) %26 ==1:
​ inv_mult = x
break
if inv_mult is None:
raise ValueError("No inverse found")

​ res = ""
for c in hint:
if c in "LITCTF{_}":
​ res += c
else:
​ idx_ct = ord(c) - ord('a')
​ idx_pt = (idx_ct * inv_mult) %26
​ res += chr(idx_pt + ord('a'))
return res

hint = "LITCTF{fkxlafg_plk_qkuxbkgp_hucknkxk_khkx}"
flag = decrypt_power(hint)
print(flag)

sign

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
\#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long as btl

from Crypto.Util.Padding import pad as hashing

from flag import flag

p = getPrime(1024)

q = getPrime(1024)

n = p*q

e = 65537

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

d = pow(e, -1, t)

print(f"{e = }")

print(f"{n = }")

flag = flag.encode()

enc = pow(btl(flag), e, n)

print(f"{enc = }")

sign = pow(btl(hashing(flag, 256)), d, n)

print(f"{sign = }")

这里考察的是RSA中的签名

签名过程

先是对flag进行填充

1
hashing(flag, 256)

然后对填充字节转为整数

1
btl(hashing(flag, 256))

最后是用私钥进行签名

1
sign = pow(btl(hashing(flag, 256)), d, n)

签名计算就是如下等式

1
sign = (pad(flag, 256))^d mod n

根据欧拉定理 (me)d mod  n = me * d mod  n = m1 + k * φ(n) mod  n = m mod  n 所以

1
sign^e = (pad(flag, 256))^(d*e) = pad(flag, 256) mod n

因此,计算m = sign^e mod n即可得到填充后的消息pad(flag, 256)

最后去除填充即可得到原始flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import long_to_bytes

from Crypto.Util.Padding import unpad

e = 65537

n = 28720310163698579785590409431244488502590518896114002560615035101872706254575673226701273452266044763379371347175490772833687557638193161203442701390842338726680883158060043516615180759468749002859934101042225109339060841430076215460950001496422014817369538803906181940671644497607497588494548107578139030246710304659121835681466614082387895636652987625506231425635937025960541486880824071903428563319272223449602650009455406871550491147456125891228766395361048688453313744200332284228661669385987688182529904303370060855844163590429388043008170533746319606379457862846257781629063966348729803646974228947658975816397

enc = 28622274173454751770425162522510657578255182655076851217407818429087697323190577802242456771214850549746446507706653313042057593379659705765532892268852740105589258308684132958276551073639787381340659764512440431614091062678114371089265383600952938737174680538339955267319021442184851847628241496769952842522557307346991056557448136450999928593799714420370025506694266924139490626538253626051572437799338532577579795987845669725423644191131632856219518165150234626040583326103289158950261130615392010672381664407880524072421107969847707990340309409099437843249519731209835667579473831944170863554281708120873440754999

sign = 13347520343804927847619065202065217836879984453006249407611353191409157302332065972903532015282229744284677309671725411375707706894638641694057135257768299781877077021376667459594883760258356475573151469487363169214012061817199685037363785333516662036329205820120312268834684818014608203312923165179884189461072393686643809307452885991065622646622558149438096015921040528472490412757534851295013865651002130260213027431057502650933677854772978321133895346051674016006963172506825876634054025209746366903230914159762719784407670815205227721887604953882373776567997690485937876918420481954105325928897076354153411410671

\# 计算 m = sign^e mod n

m = pow(sign, e, n)

\# 将m转换为字节串

padded_flag = long_to_bytes(m)

\# 去除PKCS#7填充(块大小为256字节)

flag = unpad(padded_flag, 256)

print(flag.decode())

lcgcg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
\#!/usr/bin/env python3

\# inferior rngs

from random import SystemRandom

random = SystemRandom()

from Crypto.Util.number import getPrime

p = getPrime(64)

class LCG:

def __init__(self, a, b, x):

self.a = a

self.b = b

self.x = x

self.m = p

def next(self):

self.x = (self.a * self.x + self.b) % self.m

​ ret = self.x

return ret

class LCG2:

def __init__(self, baselcg, n=100):

self.lcg = baselcg

for i in range(n):

​ a = self.lcg.next()

​ b = self.lcg.next()

​ x = self.lcg.next()

self.lcg = LCG(a,b,x)

def next(self):

return self.lcg.next()

a = random.randint(1, 2**64)

b = random.randint(1, 2**64)

x = random.randint(1, 2**64)

lcg = LCG(a, b, x)

lcg2 = LCG2(lcg)

print(p)

for x in range(3):

print(lcg2.next())

from Crypto.Cipher import AES

from Crypto.Util.number import long_to_bytes as l2b

from Crypto.Util.Padding import pad

from os import urandom

r = lcg.next()

k = pad(l2b(r**2), 16)

iv = urandom(16)

cipher = AES.new(k, AES.MODE_CBC, iv=iv)

print(iv.hex())

f = open("flag.txt",'rb').read().strip()

enc = cipher.encrypt(pad(f,16))

print(enc.hex())
1
2
3
4
5
6
15471456606036645889
3681934504574973317
4155039551524372589
9036939555423197298
6c9315b13f092fbc49adffbf1c770b54
af9dc7dfd04bdf4b61a1cf5ec6f9537819592e44b4a20c87455d01f67d738c035837915903330b67168ca91147299c422616390dae7be68212e37801b76a74d4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class LCG:

def __init__(self, a, b, x):

self.a = a

self.b = b

self.x = x

self.m = p

def next(self):

self.x = (self.a * self.x + self.b) % self.m

​ ret = self.x

return ret

class LCG2:

def __init__(self, baselcg, n=100):

self.lcg = baselcg

for i in range(n):

​ a = self.lcg.next()

​ b = self.lcg.next()

​ x = self.lcg.next()

self.lcg = LCG(a,b,x)

def next(self):

return self.lcg.next()

给了两个线性同余生成器,这里的LCG2是一个嵌套的 LCG

我们要做的是恢复参数求出r即可解密flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110


from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import pad, unpad



def inverse(a, m):
return pow(a, -1, m)

# 根据 LCG 的三个连续输出来恢复其参数 a, b

def recover_params(o1, o2, o3, p):

# o2 = (a * o1 + b) % p

# o3 = (a * o2 + b) % p

# o3 - o2 = a * (o2 - o1) % p

# a = (o3 - o2) * modInverse(o2 - o1) % p

# b = (o2 - a * o1) % p

​ diff1 = (o2 - o1 + p) % p
​ diff2 = (o3 - o2 + p) % p

​ a = (diff2 * inverse(diff1, p)) % p
​ b = (o2 - a * o1) % p
return a, b

# 根据 LCG 的参数和第一个输出来恢复其种子 x

def recover_seed(a, b, o1, p):

# o1 = (a * x + b) % p

# x = (o1 - b) * modInverse(a) % p

​ seed = ((o1 - b + p) % p * inverse(a, p)) % p
return seed

# --- 从程序的输出中获取这些值 ---

# 示例值,请替换为你的实际输出

p = 15471456606036645889 # 第一行输出
outputs = [
3681934504574973317,
4155039551524372589,
9036939555423197298 # 第四行输出
]
iv_hex = "6c9315b13f092fbc49adffbf1c770b54" # 加密 iv 的 hex
enc_hex = "af9dc7dfd04bdf4b61a1cf5ec6f9537819592e44b4a20c87455d01f67d738c035837915903330b67168ca91147299c422616390dae7be68212e37801b76a74d4" # 加密 flag 的 hex

# ------------------------------------

# `outputs` 当前是 lcg_100 的前三个输出

current_outputs = outputs

# 循环 100 次,从 lcg_100 回溯到 lcg_0

for i in range(100):

# 恢复 lcg_{100-i} 的参数 a 和 b

​ a_i, b_i = recover_params(current_outputs[0], current_outputs[1], current_outputs[2], p)


# 恢复 lcg_{100-i} 的种子 x

​ x_i = recover_seed(a_i, b_i, current_outputs[0], p)


# lcg_{100-i} 的参数 a, b 和种子 x 是 lcg_{99-i} 的三个连续输出

​ current_outputs = [a_i, b_i, x_i]

# 循环结束后, current_outputs 是 lcg_0 的前三个输出

out1_lcg0, out2_lcg0, out3_lcg0 = current_outputs

# 恢复 lcg_0 的参数 a_0 和 b_0

a_0, b_0 = recover_params(out1_lcg0, out2_lcg0, out3_lcg0, p)

# lcg_0 在生成前三个输出后,其内部状态为 out3_lcg0

# 计算 lcg_0 的第四个输出 r,它被用作加密密钥

r = (a_0 * out3_lcg0 + b_0) % p

# 使用 r 生成 AES 密钥

k = pad(long_to_bytes(r**2), 16)
iv = bytes.fromhex(iv_hex)
enc = bytes.fromhex(enc_hex)

# 解密

cipher = AES.new(k, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(enc), 16)

print(f"[*] Recovered a_0: {a_0}")
print(f"[*] Recovered b_0: {b_0}")
print(f"[*] Recovered r: {r}")
print(f"[*] AES Key (k): {k.hex()}")
print(f"[*] Flag: {flag.decode()}")

encryption two ways

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from Crypto.Util.number import long_to_bytes as ltb, bytes_to_long as btl, getPrime

import os

p = getPrime(1024)

q = getPrime(1024)

flag = btl(b'LITCTF{[redacted]}' + os.urandom(32))

print("Xor cipher:")

print(flag^p)

print(flag^q)

print("RSA:")

e = 65537

N = p*q

print(e,N)

print(pow(flag, e, N))

flag ^ p = 108045183697150150388387022354644400710478293913561934644429795432215423775530425605908182580593052688767602845916543591389876983482042029936174739737106705637912307780034509466169441898226514099166553884646148238091201176833192660464799051971513299469099698642852622112851519420837770557753663006410171424954

flag ^ q = 162425027220271125112526550171672938857893430024995932152889092099422586505033382180804478364393931237258447320092961243322668725158329284375314631413196322424161078014098879996836910267428123607993248647460893768237405563780856627795204647838831725719393299863570484674672516697933717612728478431715684934592

n = 17549241903028807175848697296476902180173000665558251909525417072566389777554685273914493627088689101480604403676280727929113896976807159352508389369627695539558624802791339988787869402402630026664052058891704214906198713997370416403885783996622003881424532493528115742721432687906907253783461267540168556557474688342693447888469393204411905072363126771586961835579420717423443143174165744502775543261555553300815721003846650007143264701287458594708569998427388990790314519857410381171087321730943418024966767600200818019264395953839395615095086827909298793968510748073265397345829272224944838568259203556901938490251

c = 15771531968759255206472217913622670911079136848159367178271327606545875119033854273178826969494590977340221396142610245587819870438040088763642130539085898823155632887807140504582510904126243920797047908446371848070010831250500867803653544089236908734881494176567631239714888177579409037101004801324365329294451645055770640691767024180084714636110900526184856411276742567769773926457049290824684230273083289562143369775700813949916517084557583295679402702854150346124209715938583306569988576420229217836860768395518641691096169891458896583547743891498844372591813522456434048363032013126358398207594342936230289578536

给了两个等式

1
2
3
flag ^ p = 108045183697150150388387022354644400710478293913561934644429795432215423775530425605908182580593052688767602845916543591389876983482042029936174739737106705637912307780034509466169441898226514099166553884646148238091201176833192660464799051971513299469099698642852622112851519420837770557753663006410171424954

flag ^ q = 162425027220271125112526550171672938857893430024995932152889092099422586505033382180804478364393931237258447320092961243322668725158329284375314631413196322424161078014098879996836910267428123607993248647460893768237405563780856627795204647838831725719393299863570484674672516697933717612728478431715684934592

我们将两式异或可以得到

1
flag^p^flag^q=p^q

然后用剪枝算法求出p,q即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
p_ = 108045183697150150388387022354644400710478293913561934644429795432215423775530425605908182580593052688767602845916543591389876983482042029936174739737106705637912307780034509466169441898226514099166553884646148238091201176833192660464799051971513299469099698642852622112851519420837770557753663006410171424954

q_ = 162425027220271125112526550171672938857893430024995932152889092099422586505033382180804478364393931237258447320092961243322668725158329284375314631413196322424161078014098879996836910267428123607993248647460893768237405563780856627795204647838831725719393299863570484674672516697933717612728478431715684934592

p_q = p_ ^ q_

n = 17549241903028807175848697296476902180173000665558251909525417072566389777554685273914493627088689101480604403676280727929113896976807159352508389369627695539558624802791339988787869402402630026664052058891704214906198713997370416403885783996622003881424532493528115742721432687906907253783461267540168556557474688342693447888469393204411905072363126771586961835579420717423443143174165744502775543261555553300815721003846650007143264701287458594708569998427388990790314519857410381171087321730943418024966767600200818019264395953839395615095086827909298793968510748073265397345829272224944838568259203556901938490251

c = 15771531968759255206472217913622670911079136848159367178271327606545875119033854273178826969494590977340221396142610245587819870438040088763642130539085898823155632887807140504582510904126243920797047908446371848070010831250500867803653544089236908734881494176567631239714888177579409037101004801324365329294451645055770640691767024180084714636110900526184856411276742567769773926457049290824684230273083289562143369775700813949916517084557583295679402702854150346124209715938583306569988576420229217836860768395518641691096169891458896583547743891498844372591813522456434048363032013126358398207594342936230289578536

import sys

import gmpy2

sys.setrecursionlimit(3000)

gift = p_q

N = n

def findp(p,q):

if len(p) == 1024:

​ pp = int(p,2)

if N % pp == 0:

print("p = ",pp)

print("q = ",N // pp)



else:

​ l = len(p)

​ pp = int(p,2)

​ qq = int(q,2)

if (pp ^ qq) % (2 ** l) == gift %(2**l) and pp * qq %(2 ** l) == N % (2**l):

​ findp('1' + p,'1' + q)

​ findp('1' + p,'0' + q)

​ findp('0' + p,'1' + q)

​ findp('0' + p,'0' + q)

findp('1','1')

p = 108045183697150150388387022354644400710478293913561934644429795432215423775530425605908182580593052688767602845916543591389876983486365655433122184730638261805104817521990528440087160333620946042644532377495148124034395624084891184068389351273643076713603146320842702638033574169713784743740616625029744269901

q = 162425027220271125112526550171672938857893430024995932152889092099422586505033382180804478364393931237258447320092961243322668725162648364707802747415904697459860150694631370547480969861302019742765437290474761611392061846348666931019756117786729418306582157981576014548722349380873871951268540431460375255351

e = 65537

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

d = gmpy2.invert(e,phi)

m = pow(c,d,N)

print(bytes.fromhex(hex(m)[2:]))

plug and chug

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from Crypto.Util.number import bytes_to_long, getPrime

n = getPrime(1024)

a = getPrime(1024)

tries = 0

def guess():

global n

ans = int(input("What is n? "))

if ans == n:

with open("flag.txt", "r") as f:

print(f"flag: {f.read()}")

else:

print("Wrong")

exit(0)

while tries < 10:

inp = input("Gimme a number (or type 'guess' to guess): ")

if inp == "guess":

​ guess()

else:

​ x = int(inp)

if x**2 < 996491788296388609:

print("Too small")

continue

print(pow(a, x, n))

​ tries += 1

print("You have used your ten guesses.")

guess()

题目代码不难看懂

生成两个1014位的素数a,n

1
2
3
n = getPrime(1024)

a = getPrime(1024)

我们可以输入x,保证 x2 >  = 996491788296388609 然后得到pow(a, x, n)

这里我们最多能查询10次

所以想要求得flag,就要在10次之内用返回结果求出n

我们可以利用指数的倍数关系,建立关于模数 n 的方程 a2x mod  n = (ax ⋅ ax) mod  n = ((ax mod  n) ⋅ (ax mod  n)) mod  n 换句话说,如果我们知道 y = ax mod  n,那么 a2x mod  n 就等于 y2 mod  n

解密流程是这样的

1、首先我们选择一个x发送给服务器

2、服务器返回给我们y = ax mod  n

3、我们再发送给服务器2*x

4、服务器返回z = a2x mod  n

根据上面的推导我们知道y^2 和 z 在模 n 下同余

也就是 y2 ≡ z (mod  n) 所以n就是y^2-z的因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from pwn import *
import math


p = remote('litctf.org', 31789)

# 满足 x^2 >= 996491788296388609 的最小 x

# sqrt(996491788296388609) = 998244353

min_x = 998244353

# --- 第一次交互,获取 D1 ---

x1 = min_x
x2 = 2 * x1

log.info(f"Sending x1 = {x1}")
p.sendlineafter(b"Gimme a number (or type 'guess' to guess): ", str(x1).encode())
y1 = int(p.recvline().strip())
log.success(f"Received y1 = {y1}")

log.info(f"Sending x2 = {x2}")
p.sendlineafter(b"Gimme a number (or type 'guess' to guess): ", str(x2).encode())
y2 = int(p.recvline().strip())
log.success(f"Received y2 = {y2}")

# 计算 D1 = y1^2 - y2

D1 = y1**2 - y2
log.info(f"Calculated D1 = y1^2 - y2")

# --- 第二次交互,获取 D2 ---

# 选择一个不同的 x 来生成另一组关系

x3 = min_x + 1
x4 = 2 * x3

log.info(f"Sending x3 = {x3}")
p.sendlineafter(b"Gimme a number (or type 'guess' to guess): ", str(x3).encode())
y3 = int(p.recvline().strip())
log.success(f"Received y3 = {y3}")

log.info(f"Sending x4 = {x4}")
p.sendlineafter(b"Gimme a number (or type 'guess' to guess): ", str(x4).encode())
y4 = int(p.recvline().strip())
log.success(f"Received y4 = {y4}")

# 计算 D2 = y3^2 - y4

D2 = y3**2 - y4
log.info(f"Calculated D2 = y3^2 - y4")

# --- 计算 n 并提交 ---

# n 是 D1 和 D2 的最大公约数

n_guess = math.gcd(D1, D2)
log.success(f"Found potential n: {n_guess}")

log.info("Sending 'guess' command")
p.sendlineafter(b"Gimme a number (or type 'guess' to guess): ", b"guess")

log.info(f"Submitting final guess for n: {n_guess}")
p.sendlineafter(b"What is n? ", str(n_guess).encode())

# 接收 flag

flag = p.recvline().decode()
log.success(f"Flag: {flag.strip()}")

p.close()

rng5050

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import bytes_to_long as btl, long_to_bytes as ltb

from random import random

import os

key = b"LITCTF{[redacted]}"

keyLen = len(key)

keyInt = btl(key)

def getRand():

​ copy = keyInt

​ res = ""

for _ in range(keyLen*8):

​ bit = copy % 2

​ copy >>= 1

​ add = int(random() / random() + 0.5) % 2

​ res += str(bit ^ add)

​ res = res[::-1]

return res

for _ in range(1000):

print(getRand())

print(ltb(int(getRand(), 2) ^ btl(key)).hex())

求出来的flag是LITCTF{n0t_4_c0!n[fliP…c66f2b}

不知道哪里出了问题交不上