好久没更了 水一下...
# 2021 年陕西省大学生网络安全技能大赛
# Give me num
无附件,只有打题目,连上之后是 看到 LCG,
然后随机输数字 都没有其他变化 只有 什么什么 Num 的东西,但是你可以弄到 n 次 猜测他是 给你数字然后去预测他的接下去的数
用一个脚本去爆破发现成立 并且给了个 it's true
还是啥的接近这个意思,然后去反复尝试 发现会断掉 那就是收到了不同的东西 开 debug 模式 30 层之后 发现是 related message attack 直接就上脚本 就出了。
from Crypto.Util.number import *
from pwn import *
from functools import reduce
if __name__ == "__main__":
p = remote("129.226.4.186",7000)
context.log_level = 'debug'
data = []
for i in range(6):
p.recvuntil("num:")
p.sendline("1")
data.append(int(p.recvuntil("\n")[:-1]))
delta = [d1 - d0 for (d0, d1) in zip(data, data[1:])]
m_mul = [d0 * d2 - d1 * d1 for (d0, d1, d2) in zip(delta, delta[1:], delta[2:])]
m = reduce(GCD, m_mul)
m0,m1,m2,m3 = data[:4]
a = (m2 - m1) * inverse(m1 - m0 , m) % m
b = (m1 - a * m0) % m
for i in range(30):
p.recvuntil("num:")
data.append((a*data[-1]+b)%m)
p.sendline(str(data[-1]))
p.interactive()
拿到:
it is true
30
cipher1=pow(m,e,n):
0x10652cdfaa84742a301254ad38685682db0723ead4a9696a391186333d2e18f1b1205385f3658c27818bcfb0bdb8b84f17b26ef267f93d08b9eef9791a7ce8ad98d4d0393b0df6696d9568caa712e5a2645ed74f758b378fd7f6f37e70248e46cd814d8b03da3287cea21a3f42a371adb565L
cipher2=pow(m+1,e,n):
0x10652cdfaa84742a301254ad38685682db0723ead4a9696a391186333d2e18f1b1205385f3660717240e2fd0a5b4a66b71329cab62c2cf4d5f3a706aeefd13c05993ce41f119bff6039327bd36bee9a01181bd366d4118ce3d8ce118dc84a3eb7e5497fa611a2c7c4811fa835faf4c1925f8L
N:
86556158206673268412999351099391537818771292689555971866425305353742222745803154706209551717854578357455003375422313884956087927511235887012764481212450066610311227919903117972157504258058310749942009463761100652057157343578534551749795505001379235681472026344861535746921918227188061252683055822118537612609
E:
3
接下去用 sagemath 就可以跑出来 m 了
def related_message_attack(c1, c2, diff, e, n):
PRx.<x> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+diff)^e - c2
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
return -gcd(g1, g2)[0]
if __name__ == '__main__':
n = 86556158206673268412999351099391537818771292689555971866425305353742222745803154706209551717854578357455003375422313884956087927511235887012764481212450066610311227919903117972157504258058310749942009463761100652057157343578534551749795505001379235681472026344861535746921918227188061252683055822118537612609
e = 3
c1 =0x10652cdfaa84742a301254ad38685682db0723ead4a9696a391186333d2e18f1b1205385f3658c27818bcfb0bdb8b84f17b26ef267f93d08b9eef9791a7ce8ad98d4d0393b0df6696d9568caa712e5a2645ed74f758b378fd7f6f37e70248e46cd814d8b03da3287cea21a3f42a371adb565
c2 = 0x10652cdfaa84742a301254ad38685682db0723ead4a9696a391186333d2e18f1b1205385f3660717240e2fd0a5b4a66b71329cab62c2cf4d5f3a706aeefd13c05993ce41f119bff6039327bd36bee9a01181bd366d4118ce3d8ce118dc84a3eb7e5497fa611a2c7c4811fa835faf4c1925f8
diff = 1
m1 = related_message_attack(c1, c2, diff, e, n)
print("m1:", m1)
m1: 13040004482825757166149747768424026334639325666603913967492907164094589547731068248503236733
long_to_bytes 之后就拿到了 flagflag{ffa5eaae11394fc8044a21fa920c19f8}
# 2021CISCN
# Move
根据题目可以看出是一个 copper 的...(bushi! 上次虎符也卡在这里了,不过写过一次 wp, 我做了一会才发现这样子的。那就直接开始造格子
我们可以直接通过这个格基规约就得到了 x,y 剩下的看之前的 wp,就能解出来了,用的也是一种费马小定理的思想
[HFCTF2021Crypto Wp - d33b4t0's blog](https://d33b4t0.com/2021/04/09/HFCTF 2021 Crypto WP/)
from Crypto.Util.number import* | |
def add(p1, p2): | |
if p1 == (0, 0): | |
return p2 | |
if p2 == (0, 0): | |
return p1 | |
if p1[0] == p2[0] and (p1[1] != p2[1] or p1[1] == 0): | |
return (0, 0) | |
if p1[0] == p2[0]: | |
tmp = (3 * p1[0] * p1[0]) * inverse(2 * p1[1], n) % n | |
else: | |
tmp = (p2[1] - p1[1]) * inverse(p2[0] - p1[0], n) % n | |
x = (tmp * tmp - p1[0] - p2[0]) % n | |
y = (tmp * (p1[0] - x) - p1[1]) % n | |
return (int(x), int(y)) | |
def mul(n, p): | |
r = (0, 0) | |
tmp = p | |
while 0 < n: | |
if n & 1 == 1: | |
r = add(r, tmp) | |
n, tmp = n >> 1, add(tmp, tmp) | |
return r | |
def factor(K,N): | |
l = 0 | |
r = K | |
for i in range(518): | |
s = (l+r)//2 | |
v = s*s - (9*s*s*(K-1-s)*(K-1-s)//(round(N**0.25)*round(N**0.25))) | |
if v < 4*N: | |
l = s | |
else : | |
r = s | |
return r | |
def gets(): | |
return [352349739892292322999330613117511489276791137416050590322561272098135764509812116210543232353192946492907441641899508311181782397967869533800138447935440769558784357373166666205853969428654899524304252899588626355058283586558885888,406850608655407486298019095013146348847805975120061760929682791882948049742096195978800022454159691659865169100330308708576847735609146508679126419372034710027124703842712262177437006326228856546452636094881051757653949488135598409] | |
''' | |
M = Matrix(ZZ,[[2**512,e],[0,-n]]) | |
M.LLL()[0] | |
''' | |
def getK(): | |
x = (-s[0])//(2**512) | |
y = (e*x+s[1])//n | |
K = (e*x-n*y)//y | |
return K | |
if __name__ == "__main__": | |
n = 80263253261445006152401958351371889864136455346002795891511487600252909606767728751977033280031100015044527491214958035106007038983560835618126173948587479951247946411421106848023637323702085026892674032294882180449860010755423988302942811352582243198025232225481839705626921264432951916313817802968185697281 | |
e = 67595664083683668964629173652731210158790440033379175857028564313854014366016864587830963691802591775486321717360190604997584315420339351524880699113147436604350832401671422613906522464334532396034178284918058690365507263856479304019153987101884697932619200538492228093521576834081916538860988787322736613809 | |
c = (6785035174838834841914183175930647480879288136014127270387869708755060512201304812721289604897359441373759673837533885681257952731178067761309151636485456082277426056629351492198510336245951408977207910307892423796711701271285060489337800033465030600312615976587155922834617686938658973507383512257481837605, 38233052047321946362283579951524857528047793820071079629483638995357740390030253046483152584725740787856777849310333417930989050087087487329435299064039690255526263003473139694460808679743076963542716855777569123353687450350073011620347635639646034793626760244748027610309830233139635078417444771674354527028) | |
s = gets() | |
K = getK() | |
S = factor(K,n) | |
d = inverse(e,n+1+S) | |
c = mul(d,c) | |
print(long_to_bytes(c[0])+long_to_bytes(c[1])) |
# ImageEncrypt
观察题目,我们可以得知
那么接下去,我们就可以根据这个得到 plain 的前 256 位,之后就可以推得 ch 的大概 和 key 的大概取值, 一共出现了四个 我们发现其中两个互为补数,那么就可以得到对应的 key1,key2, 去爆破一下很小的范围的 r, 于是我们可以爆破八次 来排列组合,得到 key1 = 169,key2 = 78 , 于是得到了 r = 1.2 , 之后可以得知,random.random 函数出来的是 (0,1) 的六位小数,爆破一下也很快,出来 x = 0.840264 , 那么就直接可以发现 encrypt 函数其实是和 decrypt 函数一模一样,直接拿来用,就能得到 flag
import hashlib | |
test = [205, 237, 6, 158, 24, 119, 213, 32, 74, 151, 142, 186, 57, 28, 113, 62, 165, 20, 190, 37, 159, 137, 196, 44, 97, 37, 7, 222, 220, 95, 4, 66, 0, 28, 199, 142, 95, 105, 119, 232, 250, 215, 60, 162, 91, 211, 63, 30, 91, 108, 217, 206, 80, 193, 230, 42, 221, 71, 136, 115, 22, 176, 91, 57, 61, 3, 87, 73, 250, 121, 51, 72, 83, 120, 77, 199, 236, 190, 249, 116, 45, 6, 134, 110, 149, 94, 214, 232, 153, 213, 119, 98, 81, 203, 240, 114, 240, 29, 122, 188, 156, 53, 128, 185, 40, 147, 245, 204, 47, 101, 80, 229, 41, 150, 28, 195, 25, 235, 119, 6, 192, 8, 73, 255, 159, 172, 77, 94, 254, 104, 236, 219, 141, 91, 195, 162, 97, 56, 252, 173, 163, 43, 167, 214, 50, 73, 115, 190, 254, 53, 61, 77, 138, 192, 15, 4, 190, 27, 37, 108, 101, 135, 90, 215, 106, 243, 112, 111, 106, 89, 143, 150, 185, 142, 192, 176, 48, 138, 164, 185, 61, 77, 72, 0, 17, 203, 210, 71, 186, 49, 162, 250, 218, 219, 195, 63, 248, 220, 155, 180, 219, 132, 219, 94, 144, 247, 211, 95, 70, 227, 222, 31, 69, 24, 13, 216, 185, 108, 137, 57, 186, 211, 55, 27, 158, 241, 223, 21, 134, 106, 152, 127, 187, 245, 246, 131, 176, 177, 228, 100, 112, 11, 84, 61, 193, 42, 41, 69, 229, 145, 254, 138, 3, 153, 123, 31] | |
enc1 = [131, 92, 72, 47, 177, 57, 131, 118, 4, 38, 192, 19, 119, 82, 63, 143, 235, 165, 15, 140, 209, 223, 117, 133, 47, 148, 81, 144, 138, 246, 173, 235, 177, 181, 110, 39, 9, 192, 57, 166, 180, 153, 141, 19, 234, 157, 142, 80, 234, 197, 151, 152, 249, 143, 176, 155, 147, 17, 57, 194, 191, 254, 13, 144, 140, 85, 25, 248, 172, 208, 154, 249, 5, 201, 27, 137, 69, 23, 175, 34, 156, 72, 208, 32, 195, 16, 127, 65, 207, 131, 57, 203, 7, 98, 89, 36, 65, 75, 211, 21, 45, 132, 214, 239, 102, 58, 68, 130, 97, 204, 225, 76, 152, 216, 74, 149, 79, 165, 198, 72, 150, 94, 7, 177, 46, 226, 252, 247, 79, 62, 69, 106, 60, 21, 106, 236, 47, 145, 170, 28, 18, 101, 14, 152, 131, 7, 37, 15, 168, 99, 115, 27, 220, 150, 89, 82, 232, 170, 107, 221, 212, 46, 235, 129, 36, 66, 217, 222, 36, 15, 217, 192, 247, 192, 113, 230, 129, 196, 13, 247, 148, 228, 225, 86, 71, 133, 132, 238, 236, 127, 11, 83, 107, 141, 114, 150, 182, 146, 213, 250, 141, 53, 114, 16, 198, 70, 133, 17, 247, 173, 136, 73, 236, 78, 188, 150, 239, 58, 199, 136, 11, 122, 134, 77, 47, 167, 137, 188, 55, 195, 41, 49, 245, 92, 160, 213, 254, 0, 85, 205, 193, 69, 2, 140, 143, 155, 127, 236, 179, 199, 168, 35, 85, 40, 45, 174] | |
enc2 = [198, 143, 247, 3, 152, 139, 131, 84, 181, 180, 252, 177, 192, 25, 217, 179, 136, 107, 190, 62, 4, 6, 90, 53, 105, 238, 117, 44, 5, 116, 132, 195, 214, 171, 113, 209, 18, 31, 194, 174, 228, 212, 196, 14, 27, 41, 211, 56, 139, 135, 225, 214, 89, 122, 178, 212, 185, 231, 204, 150, 204, 212, 160, 142, 213, 173, 186, 166, 65, 238, 5, 32, 45, 31, 25, 189, 148, 38, 78, 79, 33, 56, 227, 48, 103, 163, 31, 189, 37, 124, 106, 249, 86, 188, 86, 233, 41, 250, 89, 7, 212, 234, 111, 104, 245, 102, 227, 96, 160, 67, 181, 13, 26, 192, 214, 210, 188, 84, 216, 215, 243, 72, 233, 2, 122, 166, 107, 251, 70, 128, 94, 190, 185, 210, 34, 85, 77, 29, 182, 77, 115, 208, 228, 252, 73, 198, 151, 70, 10, 97, 138, 235, 21, 117, 239, 102, 129, 2, 253, 80, 53, 61, 184, 220, 41, 82, 37, 140, 23, 143, 179, 53, 153, 113, 213, 211, 111, 197, 248, 65, 60, 69, 1, 81, 48, 254, 251, 89, 195, 8, 93, 190, 66, 174, 97, 175, 210, 191, 66, 112, 123, 128, 33, 230, 237, 104, 16, 192, 239, 173, 44, 10, 120, 231, 114, 151, 140, 63, 103, 44, 243, 222, 242, 73, 51, 46, 98, 137, 163, 152, 147, 95, 223, 3, 15, 112, 85, 215, 133, 131, 240, 239, 224, 195, 140, 124, 70, 156, 221, 241, 37, 245, 1, 99, 9, 157, 99, 150, 47, 118, 225, 16, 13, 141, 135, 99, 18, 119, 63, 160, 6, 247, 27, 68, 45, 199, 86, 193, 252, 21, 135, 32, 42, 103, 114, 241, 49, 249, 182, 52, 18, 155, 157, 61, 4, 246, 158, 52, 118, 242, 195, 54, 139, 232, 100, 31, 11, 233, 58, 100, 101, 137, 83, 145, 209, 7, 241, 96, 57, 148, 207, 29, 237, 124, 177, 166, 161, 20, 116, 122, 61, 71, 46, 82, 18, 157, 253, 130, 112, 66, 94, 57, 221, 243, 222, 192, 147, 5, 130, 201, 174, 26, 160, 16, 188, 103, 187, 11, 238, 182, 144, 4, 137, 33, 84, 100, 7, 239, 219, 83, 112, 189, 166, 58, 93, 141, 30, 198, 220, 196, 118, 172, 5, 45] | |
s = [] | |
for i in range(16*16): | |
s.append(test[i]^enc1[i]^enc2[i]) | |
keys = [] | |
for i in range(256): | |
keys.append(((enc2[i]^s[i])&0xff)) | |
key1 = 169#78#177 | |
key2 = 78#86#169 | |
ch = '' | |
for i in range(256): | |
if keys[i] == key1: | |
ch = ch + '00' | |
elif keys[i] == (~key1)&0xff: | |
ch = ch + '01' | |
elif keys[i] == key2: | |
ch = ch + '10' | |
elif keys[i] == (~key2)&0xff: | |
ch = ch + '11' | |
bin_x = [] | |
for i in range(16): | |
bin_x.append(int(ch[i*16:i*16+16],2)) | |
print(bin_x) | |
def generate(x): | |
return round(r*x*(3-x),6) | |
tmp1 = bin_x[0] | |
tmp2 = bin_x[1] | |
''' | |
for i in range(0,20): | |
r = i/10 | |
x0 = str(tmp1 / 22000)[:8] | |
for j in range(-10,10): | |
tmpx = float(x0)+j/1000000 | |
tmpx = float(str(tmpx)[:8]) | |
x2 = generate(tmpx) | |
if int(x2*22000) == tmp2: | |
print(i) | |
print(tmpx) | |
''' | |
r = 1.2 | |
def encrypt(pixel,key1,key2,x0,m,n): | |
num = m*n//8 | |
seqs = [] | |
x = x0 | |
bins = '' | |
tmp = [] | |
for i in range(num): | |
x = generate(x) | |
tmp.append(x) | |
seqs.append(int(x*22000)) | |
for x in seqs: | |
bin_x = bin(x)[2:] | |
if len(bin_x) < 16: | |
bin_x = '0'*(16-len(bin_x))+bin_x | |
bins += bin_x | |
assert(len(pixel) == m*n) | |
cipher = [ 0 for i in range(m) for j in range(n)] | |
for i in range(m): | |
for j in range(n): | |
index = n*i+j | |
ch = int(bins[2*index:2*index+2],2) | |
pix = pixel[index] | |
if ch == 0: | |
pix = (pix^key1)&0xff | |
if ch == 1: | |
pix = (~pix^key1)&0xff | |
if ch == 2: | |
pix = (pix^key2)&0xff | |
if ch == 3: | |
pix = (~pix^key2)&0xff | |
cipher[index] = pix | |
return cipher | |
''' | |
for i in range(10**6): | |
s = encrypt(test,key1,key2,i/1000000,16,16) | |
if enc1== s: | |
print(i) | |
''' | |
x0 = 840264/1000000 | |
image = encrypt(enc2,key1,key2,x0,24,16) | |
print(image) | |
data = ''.join(map(chr,image)) | |
print(data) | |
# 用 py2 的 md5 计算 data |
# HOMO
观察题目,第一步就是过随机数,猜测后一位是啥,他给了 512 次机会,但是得 200 次才能过,同时 getrandbits (64) 得到的是两组 随机数, 并且先出现的在后面 后来出现的在前面,那么我们就可以通过这个去 Crack 过掉这个。
import math | |
from pwn import* | |
from randcrack import RandCrack | |
from Crypto.Util.number import* | |
q = 2**54 | |
n = 1024 | |
t = 83 | |
T = 100 | |
l = math.floor(math.log(q,t)) | |
delta = math.floor(q/t) | |
mu = 0 | |
sigma = 1 | |
def get_homo_data(): | |
pk0 = io.recvline()[:-1] | |
pk0 = [int(item) for item in pk0.strip(b'[]').split(b',')] | |
pk1 = io.recvline()[:-1] | |
pk1 = [int(item) for item in pk1.strip(b'[]').split(b',')] | |
ct0 = io.recvline()[:-1] | |
ct0 = [int(item) for item in ct0.strip(b'[]').split(b',')] | |
ct1 = io.recvline()[:-1] | |
ct1 = [int(item) for item in ct1.strip(b'[]').split(b',')] | |
return pk0,pk1,ct0,ct1 | |
def pass_random(): | |
io.recv() | |
io.sendline("1") | |
data = [] | |
io.recv() | |
for i in range(312): | |
io.sendline('0') | |
io.recvuntil("is ") | |
data.append(int(io.recvuntil("\n")[:-1])) | |
io.recv() | |
data2 = [] | |
rc = RandCrack() | |
for i in range(312): | |
r = bin(data[i])[2:].zfill(64) | |
rc.submit(int(r[32:],2)) | |
rc.submit(int(r[:32],2)) | |
for i in range(200): | |
dataa = (rc.predict_getrandbits(64)) | |
io.sendline(str(dataa)) | |
io.recv() |
接下去,就要去过掉这个 Homo 同态加密的东西... 看了看 我们可以构造 ct0 和 ct1 使得他 decry 出来就是 flag,那就可以使得 ct0+q,ct1 也 + q,那么想法成立
def pass_homo(): | |
io.sendline("2") | |
ct00 = '' | |
ct10 = '' | |
for i in range(len(ct0)): | |
ct00 = ct00 + str(ct0[i]+q) + ',' | |
for i in range(len(ct1)): | |
ct10 = ct10 + str(ct1[i]+q) + ',' | |
ct00 = ct00[:-1] | |
ct10 = ct10[:-1] | |
io.recv() | |
io.sendline(ct00) | |
io.recv() | |
io.sendline(ct10) | |
flag = io.recvline()[:-1] | |
flag = [int(item) for item in flag.strip(b'[]').split(b',')] | |
return flag | |
if __name__ == "__main__": | |
io = remote("124.71.224.99",21556) | |
pk0,pk1,ct0,ct1 = get_homo_data() | |
ssas = 47250135711800236243968330988950393827359446311214202975868194501939952447572268820856256117222966332956624906884328096423030618437170852480308637038075184731534034015103327181044504218075090965826320006738450109936180577663749111150190257135657273887365560219600637489061420461374674626281886506172665209012 | |
print(long_to_bytes(ssas)) | |
''' | |
pass_random() | |
flag = pass_homo() | |
print(flag) | |
s = '' | |
for i in range(len(flag)): | |
s =s +str(flag[i]) | |
''' |
# XCTF Final 2021:
# GSA
lower 是 d 的下界, upper 是 d 的上界 d 是随机生成 514 位.
已知 n ,e 求 d 设 p2+q2 = x*n x 从 2 开始遍历到 7 q=6p 时候差最大 为 n=6p2 q2+p2=37p2 ≈6n 所以大概上界为 7n
from Crypto.Util.number import * | |
import gmpy2 | |
from hashlib import sha1,sha256 | |
from pwn import* | |
import string | |
table = string.ascii_letters + string.digits | |
def lianfenshu(n,e):#连分数 | |
s=[] | |
while n >0: | |
k=e//n | |
s.append(k) | |
e1=e | |
n1=n | |
n=e1-k*n | |
e=n1 | |
return s | |
def convergents(e):##e 为连分数的 [] | |
d = [] | |
n = [] | |
for i in range(len(e)): | |
if i == 0: | |
di = e[i] | |
ni = 1 | |
elif i == 1: | |
di = e[i]*e[i-1] + 1 | |
ni = e[i] | |
else: # i > 1 | |
di = e[i]*d[i-1] + d[i-2] | |
ni = e[i]*n[i-1] + n[i-2] | |
n.append(ni) | |
d.append(di) | |
return n,d | |
def pow(st,sha): | |
for i in table: | |
for j in table: | |
for k in table: | |
s = i+j+k | |
sing = s+st | |
shasha = sha256(sing.encode()).hexdigest() | |
if shasha == sha: | |
io.sendline(s) | |
return | |
if __name__ == "__main__": | |
io = remote("",) | |
io.recvuntil('XXX+') | |
st = io.recvuntil(")")[:-1].decode() | |
io.recvuntil("== ") | |
sha = io.recvuntil("\n")[:-1].decode() | |
io.recv() | |
pow(st,sha) | |
io.recvuntil(b'n = ') | |
n = int(io.recvline()[:-1]) | |
io.recvuntil(b'e = ') | |
e = int(io.recvline()[:-1]) | |
k = 6 | |
print(n) | |
print(e) | |
x = 2 | |
dd=[] | |
while x<=8: | |
N = n*n - x*n | |
nn=convergents(lianfenshu(N,e))[0] | |
ee=convergents(lianfenshu(N,e))[1] | |
for i in range(len(nn)): | |
if i==0: | |
i=1 | |
d=nn[i] | |
k=ee[i] | |
if (d*e-1)%k==0 and (d*e-1)>0: | |
phi=(d*e-1)//k | |
if phi%2==0: | |
if len(bin(d))>513 and len(bin(d))<517: | |
dd.append(d) | |
x = x+1 | |
d = dd[0] | |
s = (d*e-1)//(n*n) +1 | |
a = -((d*e-1 )//s - (n*n) -1 )#p^2+q^2 | |
pp_qq = gmpy2.iroot(a**2-4*(n*n),2)[0]#p^2-q^2 | |
p = gmpy2.iroot((pp_qq+a)//2,2)[0] | |
q = gmpy2.iroot((a-pp_qq)//2,2)[0] | |
if p>q: | |
p = q | |
print(sha1(long_to_bytes(p)).hexdigest()) | |
io.recv() | |
io.sendline("2") | |
io.recv() | |
io.sendline(sha1(long_to_bytes(p)).hexdigest()) | |
io.interactive() |