糖醋小鸡块的blog
0%

2023-香山杯-wp-crypto

发表于 更新于 分类于 Valine：

*代表赛中未解出的题目

lift

题目：

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
import os
import gmpy2
from Crypto.Util.number import *
import random
from secrets import flag
def pad(s,l):
    return s + os.urandom(l - len(s))
def gen():
    g = getPrime(8)
    while True:
        p = g * random.getrandbits(138) + 1
        if isPrime(p):
            break
    while True:
        q = g * random.getrandbits(138) + 1
        if isPrime(q):
            break
    N = p ** 5 * q
    phi = p ** 4 * (p - 1) * (q - 1)
    d = random.getrandbits(256)
    e = inverse(d, phi)
    E = e * g
    hint = gmpy2.gcd(E, phi)
    return N, E, hint

flag = pad(flag,64)
m = bytes_to_long(flag)
n,e,hint = gen()
c = pow(m,e,n)
print(f'hint = {hint}')
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
# hint = 251
# n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
# e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
# c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162

首先要弄清楚gen()函数返回的几个参数究竟是什么：

其中，p、q参数生成方式如下：

即表明phi与g不互素，接下来进入题目分析：

首先有：

所以hint一定是g的整数倍，而251本身就是素数，因此得到g=251。

而由于题目是多素数n且d为256比特，因此可以考虑采用coppersmith找到d，原理如下(此处的e为gen内部的小写e，而非大写E)，由于：

所以由同余性质：

因此把d看作未知小量，使用coppersmith即可求解模n的参数p^4下的小根。求解出d后，求解gcd(ed-1,n)即可得到p^4，进而还原出p、q。

还原出p、q后，由于密文c是由以下方式得到：

而由于g与phi不互素，因此只能先用d求解出：

然后继续使用同余性质，将问题转化到模p、q下：

使用AMM算法可以得到：

但是由于题目将flag填充到了512比特，因此直接做中国剩余定理，只能得出模 p*q 下的解，位数是不够的。

可能这个时候会想，为什么刚才AMM算法不直接转到模p^5下开根，而只能转到模p下开根？事实上是因为AMM算法一般只适用于模数为素数时的有限域开根，因此这里只能得到模p下的解，而无法直接得到模p^5下的解。

那么该怎么办呢？有一种专门用于将模p^k下的解提升至模p^(k+i)下的解的方法，称作Hensel Lifting。而这正好与题目名字相对应。这里有一篇比较好理解的文章：

Hensel’s lemma (1) - 知乎 (zhihu.com)

大概了解到，Hensel Lifting一般用于解高次多项式同余方程，而在本题中，我们恰好有一个高次多项式同余方程如下(c1如何得来见前方推导)：

仍然使用同余定理把他转到模p^5下:

显然，明文m就是这个高次多项式的根，而模p^5下的根m已经满足了512比特的要求，因此我们只需要使用Hensel Lifting，将刚才AMM求得的模p下的所有可能根提升到模p^5下，并根据flag头进行判别即可。

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
from Crypto.Util.number import *
from gmpy2 import *
from sympy.ntheory.modular import crt
import random

def onemod(e, q):
    p = random.randint(1, q-1)
    while(pow(p, (q-1)//e, q) == 1):  # (r,s)=1
        p = random.randint(1, q)
    return p

def AMM_rth(o, r, q):  # r|(q-1
    assert((q-1) % r == 0)
    p = onemod(r, q)

    t = 0
    s = q-1
    while(s % r == 0):
        s = s//r
        t += 1
    k = 1
    while((s*k+1) % r != 0):
        k += 1
    alp = (s*k+1)//r

    a = pow(p, r**(t-1)*s, q)
    b = pow(o, r*a-1, q)
    c = pow(p, s, q)
    h = 1

    for i in range(1, t-1):
        d = pow(int(b), r**(t-1-i), q)
        if d == 1:
            j = 0
        else:
            j = (-math.log(d, a)) % r
        b = (b*(c**(r*j))) % q
        h = (h*c**j) % q
        c = (c*r) % q
    result = (pow(o, alp, q)*h)
    return result

def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr*m) % q
        # assert(pow(r, e, q) == cq)
        mp.append(r)
    return mp


def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = pow(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li

hint = 251
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162

#find d
g = hint
P.<x> = PolynomialRing(Zmod(n))
f = (e//g) * x - 1
d = int(f.monic().small_roots(X=2**256,beta=0.66)[0])

#find p,q,c1
pr = GCD(e//g*d-1,n)
p = int(iroot(pr,4)[0])
q = int(n // (p**5))
phi = int(p ** 4 * (p - 1) * (q - 1))
c1 = pow(c,d,n)

#AMM
cp = c1 % p
mp = AMM_rth(cp, g, p)
rt1 = ALL_ROOT2(g, p)
amp = ALL_Solution(mp, p, rt1, cp, g)

# hensel lifting(sage求有点问题，不知道原因)
b = 5
for m in amp:
    m = int(m)
    for i in range(1, b):
        _dx = -inverse(g*m**(g-1),p) % p**(i+1)
        mod_temp = (m**g-c1)//(p**i) % p**(i+1)
        t = _dx * mod_temp % p
        m = m + p**i*t % (p**(i+1))
    if(b"flag" in long_to_bytes(m)):
        print(long_to_bytes(m))
        break

但是呢，sage在实现这个自己写的Hensel Lifting时一直报错，脑子也不太清醒，暂时没找出原因。所以最后还需要手动把AMM求出的所有可能根粘贴出来，用python实现Hensel Lifting。

因此最终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
from Crypto.Util.number import *
import gmpy2
import random

g = 251
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162

#Copper解方程得到这些数值
p = 69367143733862710652791985332025152581988181
q = 67842402383801764742069883032864699996366777
phi = p ** 4 * (p - 1)*(q-1)
d = gmpy2.invert(e//g, phi)
dp = d % (p - 1)
c1 = 65942580064916339360370107869124805065379278407453423807322070174933076533175126747570263707923877730828981200462382452332851764309132627867196012329998008639862606922074733109347253946308226346992240834103573312752632998287455123587460568157234254421846676210189

#AMM求出的根，满足 amp[i] = m % p，过长就不粘贴了
amp = 

# hensel lifting
b = 5
for m in amp:
    for i in range(1, b):
        _dx = -inverse(g*m**(g-1),p) % p**(i+1)
        mod_temp = (m**g-c1)//(p**i) % p**(i+1)
        t = _dx * mod_temp % p
        m = m + p**i*t % (p**(i+1))
    if(b"flag" in long_to_bytes(m)):
        print(long_to_bytes(m))
        break

#flag{4b68c7eece6be865f6da2a4323edd491}



*strange_hash

题目：

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
from os import urandom
import socketserver
from Crypto.Util.number import *
import random
from hashlib import sha256
import string
from secret import flag


p = 18446744073709551557
M = [[8, 56, 280], [18446744073709551543, 18446744073709551467, 18446744073709551123], [7, 35, 155]]
ConInv = [0x39a3f978106bac2d,0x2940e055f4a33725,0xfda9a7a293fb5bc9]
Con = [[0x9c52c2de7a9373c4,0xf2135cb886d0fa21,0x957df7f3cd4879e9], [0xd54f837d2738d717,0x400ddf1ffaae436d,0xc2abb601d9a26b07], [0x1904359f1deb3495,0xc21aa09ba52b157b,0x3d45525db1b19a0c], [0xed66cf26a65afc73,0x1cee569b29ffa476,0x3da45abf4304849], [0x1c1a642fa0f3d96d,0x59a1c4fbb96aec86,0xa18e9ca93163f63d], [0x9621ec9fbcb402be,0xd69468353c31bee0,0x50655b3f20fee3b8], [0x109cde7a61c2c195,0x5ebbd9e98be60c59,0x334d2d15f6e43190], [0x47af2b0d63901977,0x67ace097bf8c6f34,0xb87da3296b70d64b], [0x52d6344b38f49899,0xad5773add31420e1,0xecd0b7480f8c8095], [0xe2afb6d20f5decda,0xb1767d8be7d1371,0x902fd6806a0ef4db]]
assert len(Con) == 10
Inv = inverse(3, p-1)
Round = 2

def add(x, y):
    return [(a + b)%p for a, b in zip(x, y)]

def multiply(x, M):
    result = []
    for i in range(len(M[0])):
        temp = 0
        for j in range(len(x)):
            temp += x[j] * M[j][i]
        result.append(temp%p)
    return result

def Rescue_Prime(R, P):
    X = add(P, ConInv)
    Y = [0, 0, 0]
    Z = [0, 0, 0]
    U = [0, 0, 0]
    for r in range(R):
        for i in range(3):
            Y[i] = pow(X[i], 3, p)
            
        Z = add(Con[2*r%10], multiply(Y, M))
        
        for i in range(3):
            U[i] = pow(Z[i], Inv, p)

        X = add(Con[(2*r+1)%10], multiply(U, M))
    return X


class Task(socketserver.BaseRequestHandler):
    encrypt_history = []

    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)

    def proof_of_work(self):
        random.seed(urandom(8))
        proof = ''.join([
            random.choice(string.ascii_letters + string.digits)
            for _ in range(20)
        ])
        digest = sha256(proof.encode()).hexdigest()
        self.send_line(
            str.encode(("sha256(XXXX + %s) == %s" % (proof[4:], digest))))
        self.send_line(str.encode('Give me XXXX:'))
        x = self.request.recv(10)
        x = (x.strip()).decode("utf-8")
        if len(x) != 4 or sha256(
                (x + proof[4:]).encode()).hexdigest() != digest:
            return False
        return True

    def send_line(self, msg):
        try:
            self.request.sendall(msg + b'\n')
        except:
            pass

    def read_line(self):
        body = b""
        while True:
            ch = self.request.recv(1)
            if ch == b"\n":
                break
            body = body + ch
        return body

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def handle(self):
        try:
            if not self.proof_of_work():
                self.dosend(b'You must pass the PoW!')
                self.request.close()
            self.send_line(b'Send your input:')
            input_str = self.read_line().decode()
            num_tuple = tuple(map(int, input_str.strip('()').split(',')))  
            if num_tuple[-1] != 0:
                self.send_line(b'The third number is not zero!')
                self.request.close()
            output = Rescue_Prime(Round, num_tuple)
            if output[-1] == 0:
                self.send_line(b'congratulate! Here is the flag:')
                self.send_line(flag)
            else:
                self.send_line(b'Oops! Find collision failed.')
                self.request.close()
        except:
            self.send_line(b'What\'s wrong???')
            self.request.close()


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


HOST, PORT = '0.0.0.0', 9999
server = ThreadedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()

题目的大致要求如下：

  • 通过proof
  • 提供一组输入(x,y,0)，要求该输入通过自定义哈希函数Rescue_Prime后，生成的输出是(x’,y’,0)。也就是说，要求哈希函数的输入输出的最后一位均为0

其中，自定义的哈希函数Rescue_Prime生成过程如下(其中三次方意义是三元组的每一个数字进行三次方，是为了方便而这样表示)：

看上去似乎很复杂，不过仔细一看，这怎么会是个哈希函数呢？因为哈希函数具有单向性，而他进行的每一步都是可逆的。比如如果加Con向量，逆操作就是对应减回去；如果是右乘M，逆操作就是对应解一个矩阵方程；如果是乘3次方或者-3次方，逆操作就是对应乘指数逆元。

因此，我们完全可以自定义一个输出，就定为(1,1,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
def minus(x, y):
    return [(a - b)%p for a, b in zip(x, y)]
   
def reveal(R,P):
    X = minus(P,Con[3])
    print(X)
    X = [1515850589463500072, 12720000879441077924, 13358055339402620049]
    Y = []
    for i in X:
        temp = pow(i,3,p)
        Y.append(temp)
    Y = minus(Y,Con[2])
    print(Y)
    Y = [3174461340829758314, 3934956789177085137, 11015113952396946596]
    Z = []
    for i in Y:
        temp = pow(i,Inv,p)
        #print(pow(temp,3,p) == i)
        Z.append(temp)
    Z = minus(Z,Con[1])
    print(Z)
    Z = [17548701131591609521, 14710429855691795808, 236055829718743711]
    X = []
    for i in Z:
        temp = pow(i,3,p)
        #print(pow(temp,3,p) == i)
        X.append(temp)
    X = minus(X,Con[0])
    print(X)
    X = [1356636556594689318, 3037182169075815915, 14113359553476699425]
    Y = []
    for i in X:
        temp = pow(i,Inv,p)
        Y.append(temp)
    Y = minus(Y,ConInv)
    print(Y)

R = 2
In = (1,1,0)
reveal(2,In)

其中，每个矩阵是由sage解矩阵方程解的，如下：

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

p = 18446744073709551557
M = [[8, 56, 280], [-14, -90, -434], [7, 35, 155]]
Inv = inverse(3, p-1)
Round = 2

#当前需解的右向量
c = [11785826738904333038, 1444931144810824421, 13360052317957358486]
c = vector(GF(p),c)
m = matrix(GF(p),3,3,M)
a1 = m.solve_left(c)
print(a1)

所以我们可以得到如下关系：

1
2
Input = [5329202944861711021, 10075872277090249537, 6598944197421011167]
Rescue_Prime(R,Input) = (1,1,0)

但是题目要求需要传入一个末尾为0的输入才行，这怎么办呢？比赛中也就停在这里了，不知道如何解决这个问题。

然后赛后有师傅告诉了我思路，问题出在这里(估计不是预期解)：

1
2
3
4
5
6
7
8
9
10
self.send_line(b'Send your input:')
input_str = self.read_line().decode()
num_tuple = tuple(map(int, input_str.strip('()').split(',')))  
if num_tuple[-1] != 0:
    self.send_line(b'The third number is not zero!')
    self.request.close()
output = Rescue_Prime(Round, num_tuple)
if output[-1] == 0:
    self.send_line(b'congratulate! Here is the flag:')
    self.send_line(flag)

这是题目的交互部分，非常仔细的看的话，可以看出，他没有限制输入长度，而只对输入输出的-1项进行是否为0的检查，也就是说，我们可以把刚才反解(1,1,0)得到的输入：

1
[5329202944861711021, 10075872277090249537, 6598944197421011167]

写成这种形式传给服务器：

1
(5329202944861711021, 10075872277090249537, 6598944197421011167,0)

这样就能满足最后一项为0的检查，算出来的输出自然也是(1,1,0)，就能得到flag了。

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
from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
import string
from hashlib import sha256
from gmpy2 import powmod

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX + ")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("59.110.231.185",38630)
proof_of_work()
r.recvuntil(b" input:")
r.sendline("(5329202944861711021, 10075872277090249537, 6598944197421011167,0)".encode())
temp = r.recvline()
temp = r.recvline()
temp = r.recvline()
print(temp)

………………

确实有一点无语，不过确实也怪自己不够细心。这个赛题提供的宝贵经验就是：一定要先检查交互部分本身有没有漏洞，有可能就能直接跳过一个很复杂的问题！