EasyRSA

[题解分析]

Cry签到题，逐字节的RSA，且assert(e < 20000)，爆破即可

[exp]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = 
c = [...]
e = None
for _ in range(3, 20000):
    if pow(ord('f'), _, n) == c[0]:
        e = _
        break
# e = 11299
flag_char = [ord(_) for _ in '0123456789abcdef']
for c_char in c[5:-1]:
    for m_char in flag_char:
        if pow(m_char, e, n) == c_char:
            print(chr(m_char), end='')
            break
# caf94ef5f8400ae920c0bd79489f3791

HardRSA

[题解分析]

1
2
3
4
5
6
7
8
9
10
11
12
p = getPrime(510)
q = getPrime(510)
r = getPrime(510)
e = 7
m = bytes_to_long(os.urandom(30) + flag)
n = p * q * r
d = invert(e, (p - 1) * (q - 1) * (r - 1))
c = pow(m, e, n)
print(n // p)
print(p)
print(c)
print(hex(d % (1 << 540)))

$k(p-1)\rightarrow k’,qr\rightarrow n’,q+r\rightarrow s$

$ed_{0}\equiv 1+k’(n’-s+1)\quad mod\ 2^{d_{0}.nbits()}\quad (1)$

$q^{2}-sq+n’\equiv 0\quad mod\ 2^{d_{0}.nbits()}\quad (2)$

$q\cdot (1),k’\cdot (2)$，联立可得，$(ed_{0}-1-k’n’-k’)q+k’q^{2}+k’n’\equiv 0\quad mod\ 2^{d_{0}.nbits()}$

即求解同余方程可得q的低size(d0)位，本来是个partial d的coppersmith问题，但因为step1求解同余方程后得到的q已是完整的q，所以无需后续的copper

[exp]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_p(d0, kbits, e, n, p):
    X = var('X')
    for k in range(1, e + 1):
        k_dot = k * (p - 1)
        results = solve_mod([e * d0 * X - k_dot * X * (n - X + 1) + k_dot * n == X], 2^kbits)
        for x in results:
            q = ZZ(x[0])
            if n % q == 0:
                return q
    return None

n = ... # q * r
p = 
c = 
d0 = 
e = 7
kbits = d0.nbits()
q = find_p(d0, kbits, e, n, p)
phi = (p - 1) * (q - 1) * (n // q - 1)
d = inverse_mod(e, phi)
print(bytes.fromhex(hex(pow(c, d, p * n))[2:]))
# b'\xf3\xaa\x03~\xaesZ?\xb5\x84\x0b\t\xb7-\xd8\xa8\xca\x80\x18\xd4\x9eVm6\x8bU\xb6\xfb`\x8eflag{6809781d08e120627e623dcdafe26b8a}'

AliceHomework

[题解分析]

Merkle-Hellman的背包系统，Shamir’s Attack没自己实现过- -照例作格基约化

303维的子集和问题，已知明文flag{…}可以降维到256维，规模还是略大（但是赛后得知到这一步以后直接LLL能出，啊这）

由于flag内芯是32位小写md5，而0~f的二进制编码均为$0x1xxxxx$格式，因此能继续降维至256-32*2=192维

最后常规BKZ即可

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

pubkey = [...] # len(pubkey) == 303
c = 

prefix = [int(_) for _ in bin(bytes_to_long(b'flag{'))[2:]]
for i in range(len(prefix)):
    c -= prefix[i] * pubkey[i]

suffix = [int(_) for _ in bin(ord('}'))[2:].rjust(8, '0')]
n = len(pubkey)
for i in range(8):
    c -= pubkey[n - 8 + i] * suffix[i]
    
elements = []
for i in range(len(prefix), len(pubkey) - 8, 8):
    #c -= 0 * pubkey[i]
    elements.append(pubkey[i + 1])
    c -= 1 * pubkey[i + 2]
    for j in range(3, 8):
        elements.append(pubkey[i + j])
        
n = len(elements)
A = Matrix(ZZ, n + 1, n + 1)
for i in range(n):
    A[i, 0] = elements[i]
    A[i, i + 1] = 2
A[n, 0] = c
for i in range(1, n + 1):
    A[n, i] = 1
AL = A.BKZ()
mid = None
for line in AL:
    if all(line[i] == 1 or line[i] == -1 for i in range(1, n + 1)):
        if line[1] == 1:
            line = -line
        mid = line[1:]
        break

mid_str = ''
for _ in mid:
    if _ == -1:
        mid_str += '0'
    else:
        mid_str += '1'

flag = ''
j = 0
for i in range(32):
    flag += '0'
    flag += mid_str[j]
    j += 1
    flag += '1'
    for k in range(5):
        flag += mid_str[j]
        j += 1
print(long_to_bytes(int(flag, 2)))
# b'8130e8c14fe4df06558c0a7ebf06f272'

PolyCrypto

[题解分析]

NTRU CryptoSystem，赛中来不及- -

非标准的NTRU，且私钥已给出，直接decrypt即可

Enc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
I = Integers(q)
R = PolynomialRing(I, "x")
x = R.gen()
S = R.quotient(x ^ N - 1, "x")
F = S(randomseq(N)) # 本题randomseq无标准NTRU中的参数d...就直接[randint(-1, 1) for _ in range(N)]...很迷
f = p * F + 1
z = f ^ -1
g = S(randomseq(N))
h = p * z * g
# h => pubkey ; f => prikey
...
def encrypt_block(key, block ,S):
    out = []
    # transform number to polynomial
    for _ in range(N):
        out.append(block % 3 - 1)
        block -= block % 3
        block //= 3
    cipher = S(randomseq(N)) * key + S(out) # c = r * h + m
    return list(cipher)

$c=rh+m=rpzg+m\quad (mod\ q)$

$a=fc=rpg+fm\quad (mod\ q)$

标准的NTRU解密基于该步骤的$rpg+fm$在Zmod(q)与在ZZ上等价，否则在$a*inv_f$后得到的结果非m

而本题randomseq是个自写的函数…汉明重量不能保证上界，且$F=randpoly,f=p*F+1$，因此标准decrypt失败，再次化简上式可知，

$a=fc=rpg+pm*F+m$，因此在Zmod(p)上即为m

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

n = 61
q = 5039
p = 11
PR = PolynomialRing(ZZ, name = 'x')
x = PR.gen()
R = PR.quotient_ring(x ^ n - 1, names = 'y')
y = R.gen()
h = R([...])
f = R([...])
c = [[...], [...], ...]
c = [R(_) for _ in c]

def balance_mod(f, q):
    g = list(((f[i] + q // 2) % q) - q // 2 for i in range(n))
    return R(g)

def invert_mod_prime(f, p):
    T = R.base().change_ring(Integers(p)).quotient(x ^ n - 1)
    return R(1 / T(f))

def coef2num(coefs):
    num = 0
    for i in range(len(coefs)):
        num += coefs[i] * (3 ** i)
    return num

def decrypt(c, f):
    a = balance_mod(c * f, q)
    # m = balance_mod(a * invert_mod_prime(f, p), p)
    m = balance_mod(a, p)
    coefs = [_ + 1 for _ in m]
    return long_to_bytes(coef2num(coefs))

flag = b""
for _ in c:
    flag += decrypt(_, f)
print(flag)
# b'59d34a385e1b59c977eea74e92e0d9dc'

More

Fianl是内网综合渗透，队友带飞，舒适.jpg