复现了一下后面的几道题目,前面的题写的时间有点久远了,
主要是我懒
Ezmatirx
题干 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
52from Crypto.Util.number import *
from secret import FLAG,secrets,SECERT_T
assert len(secrets) == 16
assert FLAG == b'moectf{' + secrets + b'}'
assert len(SECERT_T) <= 127
class LFSR:
def __init__(self):
self._s = list(map(int,list("{:0128b}".format(bytes_to_long(secrets)))))
for _ in range(8*len(secrets)):
self.clock()
def clock(self):
b = self._s[0]
c = 0
for t in SECERT_T:c ^= self._s[t]
self._s = self._s[1:] + [c]
return b
def stream(self, length):
return [self.clock() for _ in range(length)]
c = LFSR()
stream = c.stream(256)
print("".join(map(str,stream))[:-5])
# 11111110011011010000110110100011110110110101111000101011001010110011110011000011110001101011001100000011011101110000111001100111011100010111001100111101010011000110110101011101100001010101011011101000110001111110100000011110010011010010100100000000110
LFSR
问题 考虑使用BM算法
来恢复抽头Secret_T
,板子如下 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
37def berlekamp_massey(s):
n = len(s)
c, b = [0] * n, [0] * n
c[0], b[0] = 1, 1
l, m, d = 0, -1, 0
for i in range(n):
d = s[i]
for j in range(1, l + 1):
d ^= c[j] & s[i - j]
if d == 1:
t = c.copy()
p = [0] * n
for j in range(n - i + m):
if j < len(b):
p[j + i - m] = b[j]
c = [c[k] ^ p[k] for k in range(n)]
if 2 * l <= i:
l, m, b = i + 1 - l, i, t
return [i for i, bit in enumerate(c[:l + 1]) if bit]
1 | def xor(state,taps): |
1 | b'e4sy_lin3ar_sys!' |
moectf{e4sy_lin3ar_sys!}
这是我们自己的方法
官方也给了用矩阵思路来求解的wp
话说标题都是Matrix确实该这样做的)
这里我们分析这个128位的线性反馈寄存器 把问题拓宽 在一个
a_{i+n}=^{n-1}{k=0}a{i+k}c_{k+1}
S_i=(a_i,a_{i+1},,a_{i+n-1})
S_{i+1}=(a_{i+1},a_{i+2},,a_{i+n})
= (a_{i+1}, a_{i+2}, , a_{i+n})
S_{i}C = S_{i+1}
a_{i+n}=S_i*(c_{1},c_{2},,c_{n})^{T}
(c_{1},c_{2},,c_{n})
a_{1}a_{2n}
\[
显然左边是满秩的,乘逆矩阵就能计算出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# sage
F = GF(2)
V = VectorSpace(F,n)
vec = V(list(map(int, list(output[n:]))))# 这里应该保证output刚好有2n位,不然配不齐
M = []
for i in range(n-1,2*n-1):
m = []
for j in range(n):
m.append(output[i-j])
M.append(m)
M = Matrix(F,M)
print(M.rank())
sol = M.solve_right(vec)
print(len(sol))
taps = [idx for idx, val in enumerate(sol) if val == 1]
print("taps:", taps)
print("len(taps):", len(taps))
S_{i-1}=S_{i}C^{-1}
$$ 美美运算找回初态,板子如下 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17poly = list(sol)
B = Matrix(F,n,n)
for i in range(n):
B[i,n-1] = poly[n-1-i]
for i in range(n-1):
B[i+1,i] = 1
B_inv = B**(-1)
t = V(list(map(int,list(output[:n]))))
print(long_to_bytes(int("".join(map(str,t*B_inv**(n))),2)))
说实话推导向右移
放最低位的也是类似的思路,这里就不多写了主要是懒
EzPack
1 | from Crypto.Util.number import * |
背包问题 题目加密流程为把flag
编码为二进制01串
k_i>k_{i-1}+k_{i-2}++k_1
s=^{n}_{i=1}m_ik_i
c;7^{s};mod;p
$$ 那么很显然,我们先想办法解决这个离散对数问题,求解p-1
进行分解,结果如下
1
factors = [2, 2, 2, 3, 7, 636277, 677857, 682777, 735809, 860059, 903949, 908441, 954851, 1017139, 1032341, 1163131, 1190737, 1227157, 1341323, 1395671, 1463611, 1556201, 1569401, 1713749, 1930931, 2219563, 2476283, 2477281, 2590633, 2756587, 2833643, 3095713, 3281449, 3688063, 4008793, 4285993, 5443981, 5720053, 5822981, 6201869, 6892217, 7093841, 7319857, 8227237, 9381107, 9477463, 10078729, 10084297, 10764907, 12416167, 14095651, 14294663, 14788051]
1
2
3
4
5
6
7
8
9
10
11c = 1210552586072154479867426776758107463169244511186991628141504400199024936339296845132507655589933479768044598418932176690108379140298480790405551573061005655909291462247675584868840035141893556748770266337895571889128422577613223452797329555381197215533551339146807187891070847348454214231505098834813871022509186
p = 2050446265000552948792079248541986570794560388346670845037360320379574792744856498763181701382659864976718683844252858211123523214530581897113968018397826268834076569364339813627884756499465068203125112750486486807221544715872861263738186430034771887175398652172387692870928081940083735448965507812844169983643977
g = 7
R = GF(p)
x = R(c).log(g)
print("解得的 x =", x)1
2
3
4
5
6
7
8
9
10
11
12
13
14F = GF(p)
a = F(7)
X = F(cipher)
n = a.order()
primes = [2^3,3,7,636277,677857,682777,735809,860059,903949,908441,954851, 1017139, 1032341, 1163131, 1190737, 1227157, 1341323, 1395671, 1463611, 1556201, 1569401, 1713749, 1930931, 2219563, 2476283, 2477281, 2590633, 2756587, 2833643, 3095713, 3281449, 3688063, 4008793, 4285993, 5443981, 5720053, 5822981, 6201869, 6892217, 7093841, 7319857, 8227237, 9381107, 9477463, 10078729, 10084297, 10764907, 12416167, 14095651, 14294663,14788051] dlogs = []
for fac in primes:
t = int(n//fac)
dlog = discrete_log(X**t, a**t)
dlogs += [dlog]
print("factor:"+str(fac)+",Discrete Log:"+str(dlog))
nc = crt(dlogs,primes)
print(nc)
assert pow(7,nc,p) == cipher
1 | def solve_knapsack(key, target): |
OneMoreBit
1 |
|
这里用的是getStrongPrime
来生成的素数,具体就是
$$ 也是大素数 而 Boneh-Durfee
攻击方法 mimoo/RSA-and-LLL-attacks:
attacking RSA via lattice reductions (LLL) (github.com) sir,this way
梭一下脚本就能轻松解出d了,但是呢实际上标答使用的是The Verheul and van Tilborg attack
论文在这里 0811.0063
(arxiv.org) 可见就算是泄露私钥位数也是非常非常危险的
EzLCG
1 | from sage.all import * |
k_{i}s_{i};(z_{i}+r_{i};;x);mod;q
k_{i+1}s_{i+1};(z_{i+1}+r_{i+1};;x);mod;q
k_{i+1};ak_{i}+b;mod;q
k_{i};ak_{i-1}+b;mod;q
k_{i+1}-k_{i};;a(k_{i}-k_{i-1});mod;q
k_{i};s_{i}^{-1}(z_{i}+r_{i};;x);mod;q
s_{i+1}{-1}(z_{i+1}+r_{i+1};;x);-s_{i}{-1}(z_{i}+r_{i}x);;a(s_{i}{-1}(z_{i}+r_{i};;x);-s_{i-1}{-1}(z_{i-1}+r_{i-1}x));mod;q
$$ 我们把所有和
呃呃,好像不是这样构造的,看一下wp, $$
(k_{i+2}-k_{i+1})(k_{i}-k_{i-1});;(k_{i+1}-k_{i})^{2};mod;q
k_{i} ;;u_{i}+v_{i}x;mod;p
(u_{i+2}-u_{i+1}+(v_{i+2}-v_{i+1})x)((u_{i}-u_{i-1}+(v_{i}-v_{i-1})x));;((u_{i+1}-u_{i}+(v_{i+1}-v_{i})x))^2;mod;p
$$ 取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
91from random import getrandbits, randint
from secrets import randbelow
from Crypto.Util.number import getPrime,isPrime,inverse
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha1
g = 81569684196645348869992756399797937971436996812346070571468655785762437078898141875334855024163673443340626854915520114728947696423441493858938345078236621180324085934092037313264170158390556505922997447268262289413542862021771393535087410035145796654466502374252061871227164352744675750669230756678480403551
h = 13360659280755238232904342818943446234394025788199830559222919690197648501739683227053179022521444870802363019867146013415532648906174842607370958566866152133141600828695657346665923432059572078189013989803088047702130843109809724983853650634669946823993666248096402349533564966478014376877154404963309438891
q = 1303803697251710037027345981217373884089065173721
p = 135386571420682237420633670579115261427110680959831458510661651985522155814624783887385220768310381778722922186771694358185961218902544998325115481951071052630790578356532158887162956411742570802131927372034113509208643043526086803989709252621829703679985669846412125110620244866047891680775125948940542426381
msg = [b'I\xf0\xccy\xd5~\xed\xf8A\xe4\xdf\x91+\xd4_这里用格子反而很麻烦不是很大告诉了一个$', b'~\xa0\x9bCB\xef\xc3SY4W\xf9Aa\rO', b'\xe6\x96\xf4\xac\n9\xa7\xc4\xef\x82S\xe9 XpJ', b'3,\xbb\xe2-\xcc\xa1o\xe6\x93+\xe8\xea=\x17\xd1', b'\x8c\x19PHN\xa8\xbc\xfc\xa20r\xe5\x0bMwJ']
sigs = [(913082810060387697659458045074628688804323008021, 601727298768376770098471394299356176250915124698), (406607720394287512952923256499351875907319590223, 946312910102100744958283218486828279657252761118), (1053968308548067185640057861411672512429603583019, 1284314986796793233060997182105901455285337520635), (878633001726272206179866067197006713383715110096, 1117986485818472813081237963762660460310066865326), (144589405182012718667990046652227725217611617110, 1028458755419859011294952635587376476938670485840)]
iv = b'M\xdf\x0e\x7f\xeaj\x17PE\x97\x8e\xee\xaf:\xa0\xc7'
ct = b"\xa8a\xff\xf1[(\x7f\xf9\x93\xeb0J\xc43\x99\xb25:\xf5>\x1c?\xbd\x8a\xcd)i)\xdd\x87l1\xf5L\xc5\xc5'N\x18\x8d\xa5\x9e\x84\xfe\x80\x9dm\xcc"
z=[]
for m in msg:
z.append(int.from_bytes(sha1(m).digest(), 'big'))
# print(z)
r=[]
s=[]
for (i,j) in sigs:
r.append(i)
s.append(j)
# print(s)
# print(r)
u=[]
v=[]
for i in range(len(msg)):
u.append((inverse(s[i],q)*z[i]))
v.append((inverse(s[i],q)*r[i]))
F=GF(q)
R.<x>=Zmod(q)[]
f = (u[3]-u[2]+(v[3]-v[2])*x)*((u[1]-u[0]+(v[1]-v[0])*x))-((u[2]-u[1]+(v[2]-v[1])*x))**2
f=f.monic()
xx = f.roots()
print(xx)
for i in xx:
x=i[0]
key = sha1(str(x).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC,iv)
flag=cipher.decrypt(ct)
print(flag)
# b'moectf{w3ak_n0nce_is_h4rmful_to_h3alth}\t\t\t\t\t\t\t\t\t'
babelifting
1 | from Crypto.Util.number import * |
ed;;1;mod;(n)
ed;=1+k(p-1)(q-1);,(k<e)
ed_{l};;1+k(p-1)(q-1);mod;2^{400}
ed_{l};;1+k(p-1)(-1);mod;2^{400}
kp{2}+(ed_{l}-1-k(n+1))p+kn;;0;mod;2{400}
$$ 我们枚举所有可能的
1 | p = 2 |
官方的脚本貌似有点小问题,我这里跑的话会炸内存,没法按照预期跑出来,我的exp修改后如下
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# sage 10.6
from Crypto.Util.number import *
from tqdm import trange
n, e = (53282434320648520638797489235916411774754088938038649364676595382708882567582074768467750091758871986943425295325684397148357683679972957390367050797096129400800737430005406586421368399203345142990796139798355888856700153024507788780229752591276439736039630358687617540130010809829171308760432760545372777123, 4097)
cipher = 14615370570055065930014711673507863471799103656443111041437374352195976523098242549568514149286911564703856030770733394303895224311305717058669800588144055600432004216871763513804811217695900972286301248213735105234803253084265599843829792871483051020532819945635641611821829176170902766901550045863639612054
dl = 1550452349150409256147460237724995145109078733341405037037945312861833198753379389784394833566301246926188176937280242129
# Initialize list for potential p values
mp = []
def find_p(pl, n,e):
R.<y> = PolynomialRing(Zmod(n), implementation='NTL')
g = y*2^400 + pl # Changed from 398 to 400 to match your original approach
g = g.monic()
try:
# Adjusted parameters
gg = g.small_roots(X=2^112, beta=0.5, epsilon=0.05)
if gg:
for root in gg:
p_candidate = int(root)*2^400 + int(pl)
if n % p_candidate == 0: # Verify it's a factor
q = n // p_candidate
phi = (p_candidate-1)*(q-1)
try:
d = inverse_mod(e, phi)
m = pow(cipher, d, n)
print(long_to_bytes(int(m)))
mp.append(p_candidate)
except ValueError:
continue
except Exception as e:
print(f"Error in small_roots: {e}")
return
# Main loop
for k in trange(1, e+1):
try:
# Using solve_mod properly
R_mod = Zmod(2^400)
x_mod = R_mod['x'].gen()
poly = k*x_mod^2 + (e*dl - 1 - (n+1)*k)*x_mod + k*n
roots = poly.roots(multiplicities=False)
for pl in roots:
find_p(int(pl), n,e)
except Exception as e:
print(f"Error in k={k}: {e}")
continue
print("Found p candidates:", mp)
# b'moectf{7h3_st4rt_0f_c0pp3rsmith!}'
HiddenPoly
1 | from Crypto.Util.Padding import pad |
给你了 $$
f={15}{i=0}a{i};root{i}
f;0;mod;q
{15}{i=0}a{i};root{i};;0;mod;q
=(a_0,a_1,,a_{15},0)
$$
我们可以给格向量最后一列配一个大一点的系数,来使得右边落在最小向量中
实验一下你取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
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from Crypto.Cipher import AES
root = 122536272320154909907460423807891938232
q = 264273181570520944116363476632762225021
k = 2^9
M = matrix(ZZ, 17, 17)
for i in range(16):
M[i,i]=1
M[i,16]=k*root^i
M[16,16]=k*q
L=M.LLL()
# print(L)
key = b'\x0f!r\x1a\x071c8Qtjf\x05C\x1e\x1d'
iv = b'Gc\xf2\xfd\x94\xdc\xc8\xbb\xf4\x84\xb1\xfd\x96\xcd6\\'
ciphertext = 'd23eac665cdb57a8ae7764bb4497eb2f79729537e596600ded7a068c407e67ea75e6d76eb9e23e21634b84a96424130e'
ciphertext = bytes.fromhex(ciphertext)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
print("Decrypted plaintext (raw):", plaintext)
b'moectf{th3_first_blood_0f_LLL!@#$}\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'