只作几个简单小题，感觉有点难啊，等WP，不过一般是等不到。
determined
from Crypto.Util.number import bytes_to_long, long_to_bytes
from itertools import permutations
from SECRET import FLAG, p, q, r
def inputs():
print("[DET] First things first, gimme some numbers:")
M = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
]
try:
M[0][0] = p
M[0][2] = int(input("[DET] M[0][2] = "))
M[0][4] = int(input("[DET] M[0][4] = "))
M[1][1] = int(input("[DET] M[1][1] = "))
M[1][3] = int(input("[DET] M[1][3] = "))
M[2][0] = int(input("[DET] M[2][0] = "))
M[2][2] = int(input("[DET] M[2][2] = "))
M[2][4] = int(input("[DET] M[2][4] = "))
M[3][1] = q
M[3][3] = r
M[4][0] = int(input("[DET] M[4][0] = "))
M[4][2] = int(input("[DET] M[4][2] = "))
except:
return None
return M
def handler(signum, frame):
raise Exception("[DET] You're trying too hard, try something simpler")
def fun(M):
def sign(sigma):
l = 0
for i in range(5):
for j in range(i + 1, 5):
if sigma[i] > sigma[j]:
l += 1
return (-1)**l
res = 0
for sigma in permutations([0,1,2,3,4]):
curr = 1
for i in range(5):
curr *= M[sigma[i]][i]
if curr != 0:
print(sigma) #看看都有谁
res += sign(sigma) * curr
return res
def main():
print("[DET] Welcome")
M = inputs()
if M is None:
print("[DET] You tried something weird...")
return
res = fun(M)
print(f"[DET] Have fun: {res}")
if __name__ == "__main__":
main()
题目给了一个稀疏矩阵，里边有一部分值可以输入，还有3个位置分别藏着p,q,r当然r没啥用。然后将0-4的全排列来分别乘矩阵，并将和输出。最后是求RSA。
所有目的就是通过输入的内容来得到p或q。
上边print(sigma)是我加的，就是看看都有哪些参与到最后的加法。其实这个乘法可以看到矩阵乘,假设全排列中的[4,3,2,1,0]对应以下矩阵，那么与题目中M相乘就是对应位置的相乘，通过调整输入的内容，使结果只有1种组合不为0，并且落到p、q就能得到分解了。
测试结果是这样。
M=[[2, 0, 1, 0, 1], [0, 0, 0, 1, 0], [1, 0, 1, 0, 0], [0, 17, 0, 5, 0], [1, 0, 0, 0, 0]]
M[3][1] = 17
fun(M)
(4, 3, 2, 1, 0)
17按照这个样子手工输入就能拿到q
[DET] Welcome
[DET] First things first, gimme some numbers:
[DET] M[0][2] = 1
[DET] M[0][4] = 1
[DET] M[1][1] = 0
[DET] M[1][3] = 1
[DET] M[2][0] = 1
[DET] M[2][2] = 1
[DET] M[2][4] = 0
[DET] M[4][0] = 1
[DET] M[4][2] = 0
[DET] Have fun: 12538849920148192679761652092105069246209474199128389797086660026385076472391166777813291228233723977872612370392782047693930516418386543325438897742835129
p = 12538849920148192679761652092105069246209474199128389797086660026385076472391166777813291228233723977872612370392782047693930516418386543325438897742835129
q = n//p
>>> long_to_bytes(pow(c,invert(65535,(p-1)*(q-1)),n))
b'uiuctf{h4rd_w0rk_&&_d3t3rm1n4t10n}'*Groups
没找到方向。要求输入1个不小于512位的伪素数c。并能完成50次费小检验。然后求模 c的DLP.
找伪素数不难用(6p+1)(12p+1)(18p+1)，但怎么找到光滑的伪素数？由于这里的p一般都比较大这个因子算不了。
from random import randint
from math import gcd, log
import time
from Crypto.Util.number import *
def check(n, iterations=50):
if isPrime(n):
return False
i = 0
while i < iterations:
a = randint(2, n - 1)
if gcd(a, n) == 1:
i += 1
if pow(a, n - 1, n) != 1:
return False
return True
def generate_challenge(c):
a = randint(2, c - 1)
while gcd(a, c) != 1:
a = randint(2, c - 1)
k = randint(2, c - 1)
return (a, pow(a, k, c))
def get_flag():
with open('flag.txt', 'r') as f:
return f.read()
if __name__ == '__main__':
c = int(input('c = '))
if log(c, 2) < 512:
print(f'c must be least 512 bits large.')
elif not check(c):
print(f'No cheating!')
else:
a, b = generate_challenge(c)
print(f'a = {a}')
print(f'a^k = {b} (mod c)')
k = int(input('k = '))
if pow(a, k, c) == b:
print(get_flag())
else:
print('Wrong k')*Key in Haystack
也比较短，key是40位素数，提示是key*prod([getPrime(1024) for _ in range(300)])
怎么从一个巨大的数中分解出key，如果数字比较小不行用yafu分解两分钟断掉就能看到那个小素数。但这个数太大了30万位，yafu会直接死掉。
看了网上一个WP，是爆破每次gcd去掉些因子，剩下key，这题有proof而且本身getPrime生成的素数并不容易重复，所以没着了。
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import md5
from math import prod
import sys
from secret import flag
key = getPrime(40)
haystack = [ getPrime(1024) for _ in range(300) ]
key_in_haystack = key * prod(haystack)
enc_flag = AES.new(
key = md5(b"%d" % key).digest(),
mode = AES.MODE_ECB
).encrypt(pad(flag, 16))
sys.set_int_max_str_digits(0)
print(f"enc_flag: {enc_flag.hex()}")
print(f"haystack: {key_in_haystack}")
exit(0)
Naptime
from random import randint
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import numpy as np
def get_b(n):
b = []
b.append(randint(2**(n-1), 2**n))
for i in range(n - 1):
lb = sum(b)
found = False
while not found:
num = randint(max(2**(n + i), lb + 1), 2**(n + i + 1))
if num > lb:
found = True
b.append(num)
return b
def get_MW(b):
lb = sum(b)
M = randint(lb + 1, 2*lb)
W = getPrime(int(1.5*len(b)))
return M, W
def get_a(b, M, W):
a_ = []
for num in b:
a_.append(num * W % M)
pi = np.random.permutation(list(i for i in range(len(b)))).tolist()
a = [a_[pi[i]] for i in range(len(b))]
return a, pi
def enc(flag, a, n):
bitstrings = []
for c in flag:
# c -> int -> 8-bit binary string
bitstrings.append(bin(ord(c))[2:].zfill(8))
ct = []
for bits in bitstrings:
curr = 0
for i, b in enumerate(bits):
if b == "1":
curr += a[i]
ct.append(curr)
return ct
def dec(ct, a, b, pi, M, W, n):
# construct inverse permuation to pi
pii = np.argsort(pi).tolist()
m = ""
U = pow(W, -1, M)
ct = [c * U % M for c in ct]
for c in ct:
# find b_pi(j)
diff = 0
bits = ["0" for _ in range(n)]
for i in reversed(range(n)):
if c - diff > sum(b[:i]):
diff += b[i]
bits[pii[i]] = "1"
# convert bits to character
m += chr(int("".join(bits), base=2))
return m
def main():
flag = 'uiuctf{I_DID_NOT_LEAVE_THE_FLAG_THIS_TIME}'
# generate cryptosystem
n = 8
b = get_b(n)
M, W = get_MW(b)
a, pi = get_a(b, M, W)
# encrypt
ct = enc(flag, a, n)
# public information
print(f"{a = }")
print(f"{ct = }")
# decrypt
res = dec(ct, a, b, pi, M, W, n)
if __name__ == "__main__":
main()为题有点长，不过还算容易，flag接字节加密，这种情况无需关心它怎么加的，直接爆破就行，一共才100多个字符
dic = []
for i in range(128):
bits = bin(i)[2:].zfill(8)
curr = 0
for i, b in enumerate(bits):
if b == "1":
curr += a[i]
dic.append(curr)
>>> bytes([dic.index(i) for i in ct])
b'uiuctf{i_g0t_sleepy_s0_I_13f7_th3_fl4g}'Without a trace
import numpy as np
from Crypto.Util.number import bytes_to_long
from itertools import permutations
from SECRET import FLAG
def inputs():
print("[WAT] Define diag(u1, u2, u3. u4, u5)")
M = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
]
for i in range(5):
try:
M[i][i] = int(input(f"[WAT] u{i + 1} = "))
except:
return None
return M
def handler(signum, frame):
raise Exception("[WAT] You're trying too hard, try something simpler")
def check(M):
def sign(sigma):
l = 0
for i in range(5):
for j in range(i + 1, 5):
if sigma[i] > sigma[j]:
l += 1
return (-1)**l
res = 0
for sigma in permutations([0,1,2,3,4]):
curr = 1
for i in range(5):
curr *= M[sigma[i]][i]
res += sign(sigma) * curr
return res
def fun(M):
f = [bytes_to_long(bytes(FLAG[5*i:5*(i+1)], 'utf-8')) for i in range(5)]
F = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
]
for i in range(5):
F[i][i] = f[i]
try:
R = np.matmul(F, M)
return np.trace(R)
except:
print("[WAT] You're trying too hard, try something simpler")
return None
def main():
print("[WAT] Welcome")
M = inputs()
if M is None:
print("[WAT] You tried something weird...")
return
elif check(M) == 0:
print("[WAT] It's not going to be that easy...")
return
res = fun(M)
if res == None:
print("[WAT] You tried something weird...")
return
print(f"[WAT] Have fun: {res}")
if __name__ == "__main__":
main()
这题和第1题类似，flag分5段每段5字符到对角阵上。然后要求输入一个对角阵，相乘后返回迹。
这里有好多方法，一种是取两次，第1次全1，第2次某一位取负，这样两次相减再除以2就得到其中1段。另一种是每位乘个权，但求和时不互相覆盖就能直接得到flag
'''
M = [
[2**160, 0, 0, 0, 0],
[0, 2**120, 0, 0, 0],
[0, 0, 2**80, 0, 0],
[0, 0, 0, 2**40, 0],
[0, 0, 0, 0, 1],
]
'''
└─$ ncat --ssl without-a-trace.chal.uiuc.tf 1337
[WAT] Welcome
[WAT] Define diag(u1, u2, u3. u4, u5)
[WAT] u1 = 1461501637330902918203684832716283019655932542976
[WAT] u2 = 1329227995784915872903807060280344576
[WAT] u3 = 1208925819614629174706176
[WAT] u4 = 1099511627776
[WAT] u5 = 1
[WAT] Have fun: 737006739132955681102064872106410124129955329734542561190269
long_to_bytes(737006739132955681102064872106410124129955329734542561190269)
#uiuctf{tr4c1ng_&&_mult5!}xmarket
签到题，key长度8字节，异或后可以通过flag头和尾得到全部key
from itertools import cycle
flag = b"uiuctf{????????????????????????????????????????}"
# len(flag) = 48
key = b"????????"
# len(key) = 8
ct = bytes(x ^ y for x, y in zip(flag, cycle(key)))
with open("ct", "wb") as ct_file:
ct_file.write(ct)print(xor(xor(ct[:7],b'uiuctf{') + xor(ct[-1:],b'}'),ct))