2023-XHB-Crypto-WP

Crypto:

lift:

题目：

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
'''

思路：先看题目构造

q = gx_1+1\ p = gx_2+1\ N = p^{5}q\ phi = p^{4}(p-1)*(q-1)\ d.bit_length() == 256\ E = d^{-1}*g(modphi)\ hint = g

差不多就这样，因为e的位数无论如何都比较大，所以就从以下开始考虑：

ed =1 (modphi)\ 展开:ed-1-kphi=0\ 继续代入参数展开：\ ed-1-kp^{4}(p-1)(q-1)=0\ 代入参数N化简：\ ed-1-kN*(q^{-1}*p{-1})(p-1)(q-1)=0\ 代：ed-1-kNg^{2}*(q{-1}p^{-1})(x_1x_2)=0\ 其实到这步已经够了，看得出来了\ ed-1=0(modNg^{2})\ e的比特位数很大，构造的格的界也很大，直接求小根就好.

import itertools
from Crypto.Util.number import *

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

E = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
N = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
g = 251
e = E//g
tmp = N*(g)
PR.<d> = PolynomialRing(Zmod(tmp))
f = e*d-1
roots = f.monic().small_roots(X =2^300, beta =0.4)

print(roots)
#[39217838246811431279243531729119914044224429322696785472959081158748864949269]

此时我们得到的d是e的逆元！不是E的逆元，

解密易得：m^{251}=c{d}(modN)\ 换模:m^{251}=c{d}(modp^{5})\ 直接考虑有限域开方

所以最后可以通过以下exp得:

from sympy.ntheory.residue_ntheory import nthroot_mod
c = 65942580064916339360370107869124805065379278407453423807322070174933076533175126747570263707923877730828981200462382452332851764309132627867196012329998008639862606922074733109347253946308226346992240834103573312752632998287455123587460568157234254421846676210189
N = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
e_ = 251
q =  69367143733862710652791985332025152581988181
p = 67842402383801764742069883032864699996366777
c = c%(q**5)
for i in (nthroot_mod(c,251,(q**5))):
    tmp =  long_to_bytes(i)
    if b'flag' in tmp :
        print(tmp)
#b'flag{4b68c7eece6be865f6da2a4323edd491}\x9d\xcf\xdc\xcb\xb8\xbdd\xec\xadh\xa6C\x99\xa0)7\xfb\x02\xba\x90q8\x10+\x7f}'

strange_hash:

不是，你怎么知道我拿了二血？

题目：

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 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:
            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()

直接看题，发现是数据经过矩阵的一系列变换后，校验最后结果的最后一位是否为零，考虑逆向求解矩阵之后直接提交答案就好，虽然题目说要求输入的数组第三位不为零，但是没有限制数组的长度！那么只要我们提交好自己构造的式子，然后多填一个位就好。

exp(这是我自己本地调试的脚本):

from os import urandom
from Crypto.Util.number import *
import random
from hashlib import sha256
import string

p = 18446744073709551557
M = [[8, 56, 280], [18446744073709551543, 18446744073709551467, 18446744073709551123], [7, 35, 155]]
M_inv = [[9511602413006487524, 10376293541461622753, 4611686018427387891], [720575940379279356, 5188146770730811374, 6917529027641081833], [8214565720323784678, 2882303761517117431, 6917529027641081834]]
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 reduce(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 recover(R,X):
    Z = [0, 0, 0]
    for r in range(R-1,-1,-1):
        UM = reduce(X,Con[(2*r+1)%10])
        U = multiply(UM,M_inv)

        for i in range(3):
            Z[i] = pow(U[i],3,p)

        YM = reduce(Z,Con[2*r%10]) 
        Y = multiply(YM,M_inv)

        for i in range(3):
            X[i] = pow(Y[i],Inv,p)
        P = reduce(X,ConInv)
    return P


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

def demo(P):#用来调试的函数
    X = add(P, ConInv)
    Y = [0, 0, 0]
    Z = [0, 0, 0]
    U = [0, 0, 0]
    for r in range(2):
        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

test = [5329202944861711021, 10075872277090249537, 6598944197421011167,0]
result = Rescue_Prime(2,test)
print(f'result = {result}')#用来多次调试校验结果
test = [1,1,0]
tmp = recover(2,test)#得到答案
print(tmp)
'''
result = [1, 1, 0]
[5329202944861711021, 10075872277090249537, 6598944197421011167]
'''

可以发现一切都是那么合理那么符合题意，直接过掉验证码交上test的数值就完了:

proof:

from pwn import *
import itertools
import string
import hashlib
from Crypto.Util.number import *
#context.log_level="debug"

def proof(io):
    io.recvuntil(b"XXXX + ")
    suffix = io.recv(16).decode("utf8")
    print(suffix)
    io.recvuntil(b"== ")
    cipher = io.recvline().strip().decode("utf8")
    print(cipher)
    for i in itertools.product(string.ascii_letters+string.digits, repeat=4):
        x = "{}{}{}{}".format(i[0],i[1],i[2],i[3])
        proof=hashlib.sha256((x+suffix.format(i[0],i[1],i[2],i[3])).encode()).hexdigest()
        if proof == cipher:
            break
    print(x)
    io.sendlineafter(b"XXXX:",x.encode())
#nc 39.106.48.123 31687
io = remote('39.106.48.123',31687)
proof(io)
io.interactive()

#提交的数据:
#5329202944861711021, 10075872277090249537, 6598944197421011167