前言

这次出了ez_lattice, LFSR_Signin和Pollard & Williams三个题以及一个ez_lattice的revenge。（lattice出得依托，以后再也不出了）

LFSR_Signin

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
flag = b"whuctf{}"

flag = list(bin(bytes_to_long(flag))[2:])
assert(len(flag) == 255)

for i in range(len(flag)):
    flag[i] = int(flag[i])

for i in range(2025):
    flag.append(flag[i] ^ flag[i+20] ^ flag[i+25] ^ flag[i+250] ^ flag[-1])
    print(flag[-1], end="")

#110000011011110000010101100011111101011011111111111111101011000111001010111000101111101100011011000110011000100010011111110111010110000111111111111101111011011101000000010011110010111000110100110011101110101010110001110100111001100011100001001000000011010011001101001000000000110110100101000110000011011100011100001000010001110000111110000110010001110001101011101110100011010000101101000000000001101111111001010100011110110001101010010100011010011010010110010110100011001100010010010110110010010001111010111100011101100001111111110101011010011111110101000110010000101011011101000000111000001011010010001010101101111111001100010001001011100100111000010100011001001111011110111111101100111001011100001110110110100010011010011111110010111001101000011000011111001101100111001111000010011110011111001010001111110001010100100011001000100011001010010111010000011101011001111111010010010101001010011010000010000100001010111000000000010011011110110001101010010101001010100100010110001001000101000001011111010110101110111100101001100101011000010000101010001010111010111010010110001111010000001101101100101111001010010010011010101110001101001111011010001000010111010011010001011011011000111101010001101110000100100011010011111110110000001101100010011000110100010101010010101100101011001001100010100111011101111100010111100010001101100101100111110101001111101000010110110011000111100110101001111001100110111100111111000101101101000011110011001101100111100111001001001001100101111101110111011111110110101000001100010110101101100100001110100110101100101011010101101101100011011000001111001010001110000110001001011001001110111110000001000011000011000101010101010010010100010011011000011100111011101111110100101111111001011010110010010011101011001011110001101110110110111110100000100001111100101000001101010000011001001100100010101111010100000010110010010111000000010010101001011001011001111001000100010100101000011110110101001011111011111001010111101111000001101101100101111010101100110000111011101100100000011001110011000110110100101010100

思路&exp

非常简单的LFSR，给出flag长度为255，所以在模2下有以下等式：

x[i+255]=x[i]+x[i+20]+x[i+25]+x[i+250]+x[i+254] x[i+255] = x[i] + x[i+20] + x[i+25] + x[i+250] + x[i+254]

变换得：

(x[i]+x[i+255])+x[i+255]=x[i]+x[i+20]+x[i+25]+x[i+250]+x[i+254]+(x[i]+x[i+255])即x[i]=x[i+20]+x[i+25]+x[i+250]+x[i+254]+x[i+255] (x[i] + x[i+255]) + x[i+255] = x[i] + x[i+20] + x[i+25] + x[i+250] + x[i+254] + (x[i] + x[i+255])\\ 即 x[i] = x[i+20] + x[i+25] + x[i+250] + x[i+254] + x[i+255]

根据生成的值即可还原flag。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *

flaglist = list("110000011011110000010101100011111101011011111111111111101011000111001010111000101111101100011011000110011000100010011111110111010110000111111111111101111011011101000000010011110010111000110100110011101110101010110001110100111001100011100001001000000011010011001101001000000000110110100101000110000011011100011100001000010001110000111110000110010001110001101011101110100011010000101101000000000001101111111001010100011110110001101010010100011010011010010110010110100011001100010010010110110010010001111010111100011101100001111111110101011010011111110101000110010000101011011101000000111000001011010010001010101101111111001100010001001011100100111000010100011001001111011110111111101100111001011100001110110110100010011010011111110010111001101000011000011111001101100111001111000010011110011111001010001111110001010100100011001000100011001010010111010000011101011001111111010010010101001010011010000010000100001010111000000000010011011110110001101010010101001010100100010110001001000101000001011111010110101110111100101001100101011000010000101010001010111010111010010110001111010000001101101100101111001010010010011010101110001101001111011010001000010111010011010001011011011000111101010001101110000100100011010011111110110000001101100010011000110100010101010010101100101011001001100010100111011101111100010111100010001101100101100111110101001111101000010110110011000111100110101001111001100110111100111111000101101101000011110011001101100111100111001001001001100101111101110111011111110110101000001100010110101101100100001110100110101100101011010101101101100011011000001111001010001110000110001001011001001110111110000001000011000011000101010101010010010100010011011000011100111011101111110100101111111001011010110010010011101011001011110001101110110110111110100000100001111100101000001101010000011001001100100010101111010100000010110010010111000000010010101001011001011001111001000100010100101000011110110101001011111011111001010111101111000001101101100101111010101100110000111011101100100000011001110011000110110100101010100")
for i in range(len(flaglist)):
    flaglist[i] = int(flaglist[i])

for i in range(255):
    flaglist.insert(0,flaglist[20-1] ^ flaglist[25-1] ^ flaglist[250-1] ^ flaglist[253] ^ flaglist[254])

temp = flaglist[:255]
for i in range(len(temp)):
    temp[i] = str(temp[i])
print(long_to_bytes(int("".join(temp),2)))

Pollard & Williams

题目

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
from Crypto.Util.number import *
import os

flag = b'whuctf{}'
blen = 256


def rsa(p, q, message):
    n = p * q
    e = 65537

    pad_length = n.bit_length() // 8 - len(message) - 2
    message += os.urandom(pad_length)
    m = bytes_to_long(message)
    return n, pow(m, e, n)


def part1(message1, message2):
    while True:
        p1 = getPrime(blen)
        p2 = (p1 - 1) // 2
        if isPrime(p2):
            break

    q1 = getPrime(blen)
    q2 = getPrime(blen)

    return rsa(p1, q1, message1), rsa(p2, q2, message2)


def part2(message1, message2):
    while True:
        p1 = getPrime(blen)
        p2 = (p1 + 1) // 2
        if isPrime(p2):
            break

    q1 = getPrime(blen)
    q2 = getPrime(blen)

    return rsa(p1, q1, message1), rsa(p2, q2, message2)


assert len(flag) == 44
l = len(flag) // 4
m1, m2, m3, m4 = [flag[i * l: i * l + l] for i in range(4)]
c1, c2 = part1(m1, m2)
c3, c4 = part2(m3, m4)

print(f'{c1 = }')
print(f'{c2 = }')
print(f'{c3 = }')
print(f'{c4 = }')

# c1 = (6053032598894343876848386724367478876865502990878797490385487692233771017587839889683279773931697102081210221515871925626229356354906807395177342943323369, 4066195854081844630643812355140109730178549671457699640787009592379117222130777528564788537029636082768525403919530491221982157867347461546035515101540809)
# c2 = (3881600892538209342174115382004433032693183438455968854185245139152150453077746028435728337685187304179257593974737056409431270271087770400534952463611803, 3170419555737452151768856928448822332346045957475336562622244748908867061340721719260259808765271614258250388620180512676045609008728482012225062330421389)
# c3 = (12299016617136978588548772285625358530978334196485520160172325214608426825374255755330322407319092229940503630270734074076341447314630647646764214262929507, 318163940794629731124968470499655451861010987042419720693423620230895540439020747998494269609254222775880714679954773027280497632868550785421041286883861)
# c4 = (4549315768074822845197072475333248869579555413221208949230121240611191001190288208256119819724334902434536556333152862828649067092565476816480268615884657, 1882968780168858989700488482275734089425710600149658668167954773629584030303631176914870357507995175067079535271674721507969999430710585448040194277936142)

思路&exp

part 1

已知：

n1=p1q1n2=p2q2p2=p1−12可以想到费马小定理:ap−1≡1  (mod  p)因此有：a2n2≡1  (  mod  p1)所以有p1=gcd(a2n2−1,n1)  在模n1下成立，从而分解n1,n2 n_1 = p_1q_1 \\ n_2 = p_2q_2 \\ p_2 = \frac{p_1-1}{2}\\ 可以想到费马小定理:a^{p-1} \equiv 1\;(mod\;p)\\ 因此有：a^{2n_2}\equiv 1\;(\;mod\;p_1)\\ 所以有p_1=gcd(a^{2n_2} - 1, n_1)\;在模n_1下成立，从而分解n_1, n_2

注意到这其实就是pollard p-1的本质思想，即通过小的质因子相乘得到R，若满足(p-1)|R即可通过R分解n。 exp:

1
2
3
4
5
6
7
8
9
10
11
def solve_part1(n1, c1, n2, c2):
    p1 = gcd(power_mod(2, 2 * n2, n1) - 1, n1)
    p2 = (p1 - 1) // 2
    q1 = n1 // p1
    q2 = n2 // p2

    d1 = inverse_mod(e, (p1 - 1) * (q1 - 1))
    d2 = inverse_mod(e, (p2 - 1) * (q2 - 1))
    m1 = power_mod(c1, d1, n1)
    m2 = power_mod(c2, d2, n2)
    return long_to_bytes(m1), long_to_bytes(m2)

part2

n1=p1q1n2=p2q2p2=p1+12跟part1唯一不同的是p1−1变成了p1+1，容易由此联想到Williamp+1算法。n_1 = p_1q_1\\ n_2=p_2q_2\\ p_2=\frac{p_1+1}{2}\\ 跟part1唯一不同的是p_1-1变成了p_1+1，容易由此联想到William p+1算法。\\

对于如下的Lucas序列：

V0=2V1=AVn=AVn−1−Vn−2设D=A2−4,若p∤D时有p∣(Vm−2,n),其中p−(Dp)∣m，(Dp)为勒让德符号。若D不是p的二次剩余，则(Dp)=−1，所以m只要是p+1的倍数即可分解n。对于计算V2n2，O(n)的递推太慢，因此考虑采用矩阵快速幂加速（类似斐波那契数列的计算）。V_0=2\\ V_1=A\\ V_n=AV_{n-1}-V_{n-2}\\ 设D=A^2-4, 若p \nmid D时有p \mid (V_m-2, n),其中p - (\frac{D}{p}) \mid m， (\frac{D}{p})为勒让德符号。\\ 若D不是p的二次剩余，则(\frac{D}{p})=-1，所以m只要是p+1的倍数即可分解n。\\ 对于计算V_{2n_2}，O(n)的递推太慢，因此考虑采用矩阵快速幂加速（类似斐波那契数列的计算）。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def lucas_v(a, n):
    v0 = 2
    v1 = a
    R = a.base_ring()
    M = matrix(R, [[a, -1], [1, 0]])
    v = M ** (n - 1) * vector(R, [v1, v0])
    return v[0]


def solve_part2(n1, c1, n2, c2):
    for a in range(2, 10):
        p1 = ZZ(gcd(lucas_v(Mod(a, n1), 2 * n2) - 2, n1))
        if 1 < p1 < n1:
            break
    p2 = (p1 + 1) // 2
    q1 = n1 // p1
    q2 = n2 // p2
    d1 = inverse_mod(e, (p1 - 1) * (q1 - 1))
    d2 = inverse_mod(e, (p2 - 1) * (q2 - 1))
    m1 = power_mod(c1, d1, n1)
    m2 = power_mod(c2, d2, n2)
    return long_to_bytes(m1), long_to_bytes(m2)

ez_lattice & Siesta's revenge

全是非预期 这题出的实在是有点难绷了（）

题目

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
from Crypto.Util.number import *
flag = b"whuctf{}"
blen = 512

l = len(flag) // 4
n = 2
X = []
a = [bytes_to_long(flag[i * l: i * l + l]) for i in range(2)]
b = 0
p = getPrime(blen)

for i in range(2):
    X.append(getRandomNBitInteger(blen))
    b = (a[i] * X[i]) % p
    assert b.bit_length() < 110

print("p =", p)
print("X =", X)

# p = 12478746590758967738992827236548867094406642228843048782158822830242432957850861746109083849369751421558416546441433265483311369062332823391326650330844473
# X = [4370703796271085517745653374714633557060694569231794372714420305839580193452505356598920188429238758568075323630107438853033389535935767953293146851021439, 5636765597544539887670148818611437395262628189014720546978418282055551396918915796702935478309173130501906553399905160951176701403838275497327658585404887]

n = 2
X = []
a = [bytes_to_long(flag[i * l: i * l + l]) for i in range(2, 4)]
print(a)
p = getPrime(blen)

for i in range(n):
    X.append(getRandomNBitInteger(blen))
    b = (a[i] * X[i]) % p
    assert b.bit_length() <= 55

s = getRandomNBitInteger(55)
P = p - s

print("P =", P)
print("X =", X)

# P = 8064317391291915578249751043887298750752952396481901402238164933671762816998644264248732894561122039999833298392825353792148892469165631966482732750535761
# X = [6042201174605160506707043360458329015685676206288676104013330039569480295420873678739841513174948925787517746114885517054730046775608073287427260847787072, 6232867934334525782602291010514616748943593081406115516232887372014738839717093295759414233886061184914495957664550361507367497641317336980894814940037711]

思路&exp

part1

这部分其实没什么好说的，显然a, b都是小量，可以由如下等式构造格：

∑i=1naiXi+kp=b(a1,a2,k)(10X101X200p)=(a1,a2,b)记为A∗M=B注意到σ(M)≈n+1p1n+1∣∣B∣∣≈n+1max(ai)因此满足max(ai)≤O(p1n+1)即可 \sum^{n}_{i=1}a_iX_i + kp = b\\ (a_1, a_2, k) \left( \begin{array}{cccc} 1 & 0 & X_1\\ 0 & 1 & X_2\\ 0 & 0 & p\\ \end{array} \right) = (a_1, a_2, b)\\ 记为A*M=B\\ 注意到\sigma(M)\approx \sqrt{n+1}p^{\frac{1}{n+1}}\\ ||B|| \approx \sqrt{n+1}max(a_i)\\ 因此满足max(a_i)\leq O(p^{\frac{1}{n+1}})即可

exp:

1
2
3
4
5
6
7
8
p = 12478746590758967738992827236548867094406642228843048782158822830242432957850861746109083849369751421558416546441433265483311369062332823391326650330844473
X = [4370703796271085517745653374714633557060694569231794372714420305839580193452505356598920188429238758568075323630107438853033389535935767953293146851021439, 5636765597544539887670148818611437395262628189014720546978418282055551396918915796702935478309173130501906553399905160951176701403838275497327658585404887]
M = Matrix([
    [1, 0, X[0]],
    [0, 1, X[1]],
    [0, 0, p]
])
print((long_to_bytes(abs(int(M.LLL()[0][0])))+long_to_bytes(int(M.LLL()[0][1]))).decode())

part2 & Siesta's revenge

这部分我本来是想考类似于extend wiener attack的造格方法的，但是因为flag取的太短导致了第一次的非预期，然后第二次s取的有点问题导致了第二次的非预期（烂完了）但是还是讲一下预期解的思路 我们有：

a1X1≡b1  (mod  P+s)a2X2≡b2  (mod  P+s) a_1X_1\equiv b_1 \;(mod\;P+s)\\ a_2X_2\equiv b_2 \;(mod\;P+s)

拆开得到：

a1X1+k1P=b1−k1s  ①a2X2+k2P=b2−k2s  ② a_1X_1 + k_1P = b_1 - k_1s\;①\\ a_2X_2 + k_2P = b_2 - k_2s\;②

然而由于未知数的个数过多，难以像part1那样构造线性的方程，因此需要想方法构造更多等式。我们可以先看一下①*②的式子如何：

①∗②=X1X2a1a2+X1Pa1k2+X2Pa2k1+P2k1k2注意到未知数仅有a1a2,a1k2,a2k1,k1k2四个，且对于①∗k2和②∗k1，构造的未知数不会比上式多。 ①*② = X_1X_2a_1a_2 + X_1Pa_1k_2 + X_2Pa_2k_1 + P^2k_1k_2\\ 注意到未知数仅有a_1a_2,a_1k_2,a_2k_1,k_1k_2四个，且对于①*k_2和②*k_1，构造的未知数不会比上式多。\\

因此可以想到如下的方程构造：

1.k1k2=k1k22.①∗k2得到  X1a1k2+Pk1k2=k2(b1−sk1)3.①∗k2−②∗k1得到  X1a1k2−X2a2k1=b1k2−b2k14.X1X2a1a2+X1Pa1k2+X2Pa2k1+P2k1k2=(b1−k1s)(b2−k2s)1. k_1k_2=k_1k_2\\ 2. ①*k_2得到\;X_1a_1k_2+Pk_1k_2=k_2(b_1-sk_1)\\ 3. ①*k_2-②*k_1得到\; X_1a_1k_2-X_2a_2k_1=b_1k_2-b_2k_1\\ 4. X_1X_2a_1a_2 + X_1Pa_1k_2 + X_2Pa_2k_1 + P^2k_1k_2=(b_1-k_1s)(b_2-k_2s)

于是有：

(k1k2,a1k2,a2k1,a1a2)(1P0P20X1X1X1P00−X2X2P000X1X2)=(k1k2,k2(b1−sk1),b1k2−b2k1,(b1−k1s)(b2−k2s))根据短向量即可反求a1a2。(k_1k_2,a_1k_2,a_2k_1,a_1a_2) \left( \begin{array}{cccc} 1 & P & 0 & P^2\\ 0 & X_1 & X_1 & X_1P\\ 0 & 0 & -X_2 & X_2P\\ 0 & 0 & 0 & X_1X_2 \end{array} \right)\\ = (k_1k_2, k_2(b_1-sk_1), b_1k_2-b_2k_1,(b_1-k_1s)(b_2-k_2s))\\ 根据短向量即可反求a_1a_2。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
P = 8064317391291915578249751043887298750752952396481901402238164933671762816998644264248732894561122039999833298392825353792148892469165631966482732750535761
X = [6042201174605160506707043360458329015685676206288676104013330039569480295420873678739841513174948925787517746114885517054730046775608073287427260847787072, 6232867934334525782602291010514616748943593081406115516232887372014738839717093295759414233886061184914495957664550361507367497641317336980894814940037711]
M = Matrix([
    [1, -P, 0, P*P],
    [0, X[0], -X[0], -X[0]*P],
    [0, 0, X[1], -X[1]*P],
    [0, 0, 0, X[0]*X[1]]
])
L = M.LLL()[0]
v = vector(ZZ, L)
x = v * M**(-1)
p = int(x[1]/x[0]*X[0])
M1 = Matrix([
    [1, X[0]],
    [0, p]
])
M2 = Matrix([
    [1, X[1]],
    [0, p]
])
print((long_to_bytes(abs(int(M1.LLL()[0][0])))+long_to_bytes(abs(int(M2.LLL()[0][0])))).decode())