geekctf 2024

Posted on 2024-05-15

HNP

task

from Crypto.Util.number import *
from hashlib import sha256
from random import seed, choice
from secret import flag
from signal import signal, alarm, SIGALRM
from string import ascii_letters, digits

def handler(signum, frame):
    print('Time out!')
    raise exit()

def proof_of_work():
    seed(getRandomRange(1, 2**128))
    proof = ''.join([choice(ascii_letters + digits) for _ in range(20)])
    digest = sha256(proof.encode('latin-1')).hexdigest()
    print('sha256(XXXX + {}) == {}'.format(proof[4: ], digest))
    print('Give me XXXX:')
    x = input()
    if x != proof[: 4]:
        return False
    return True

n = 8
A = 2048
B = A // n
MASK1 = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
MASK2 = 0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000000000000000000000000000000000000000000000000000000000000000000000000000000007ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc0000000000000000000000000000000000000000000000000000000000000000000000000000000000001fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

def challenge():
    N = getPrime(A)
    X = getRandomRange(1, N)
    Y = [getRandomRange(1, N) for _ in range(n)]
    Z = [X * Y[_] % N for _ in range(n)]
    print(N)
    for _ in range(n):
        X_ = Z[_]
        Y_ = [(Y[_] >> (__ * B)) & MASK1 for __ in range(n)]
        Z_ = [(X_ * Y_[__] % N) & MASK2 for __ in range(n)]
        print(Z_)
    alarm(5)
    G = int(input('X:'))
    alarm(30)
    if G == X:
        return 1
    else:
        return 0

signal(SIGALRM, handler)
alarm(60)

if not proof_of_work():
    exit()

for _ in range(3):
    if not challenge():
        print('Wrong!')
        exit()
    else:
        print('Good!')

print(flag)

我们要求那个

，首先肯定要求

，对于一个

，我们能得到 8 个形如

这样的式子. 其中

是取出了

的 256 个连续 bit 得到。这是一个 HNP 问题，但由于 MASK2 只有 1700 个 bit，所以 e 本来是非常大的，但 MASK2 的 LSB 都是 1，所以可以除

，转换成经典的 HNP，用之前 L3HCTF 的一个 HNP 题的脚本来跑就能把

都求出来，然后我们就能求出

。剩下求

，同样利用

这个形式的方程，此时我们有 64 组，全部拿出来当经典的 HNP 做就行了，时限问题可以用 flatter 解决。

babypairing

task

import os
from Crypto.Util.number import long_to_bytes,bytes_to_long
p = 74952228632990620596507331669961128827748980750844890766694540917154772000787
a = 7527668573755289684436690520541820188297794210531835381305219764577170135028
b = 23620438740221081546022174030845858657033205037887915215836562897142269481377
F_p = GF(p)
F_p2 = GF(p^2)
a,b = F_p2(a),F_p2(b)
E=EllipticCurve(F_p2,[a,b])
g=E.random_element()
sk=F_p.random_element()
pk=g*sk

def load_element(x1,x2):
    is_positive=(x1<p)
    x = F_p2([x1,x2])
    y2 = x^3+a*x+b
    if y2^((p^2-1)//2)==F_p2(-1):
        return None
    else :
        tmp = y2.square_root()
        #print((int(tmp)>(p-1)//2),is_positive)
        if (int(tmp[0])>(p-1)//2) ^^ is_positive : return E(x,tmp)
        else: return E(x,-tmp)

def compress_element(P):
    x,y=P.xy()
    return (int(x[0]),int(x[1])) if int(y[0])<=(p-1)//2 else (int(x[0])+p,int(x[1]))

def int_to32(x,l=17):
    b32dict="0123456789abcdefghijklmnopqrstuv"
    ret = ""
    while x>0:
        ret = b32dict[x%32]+ret
        x=x//32
    return "0"*max(0,l-len(ret))+ret

def enc_element(P):
    r = F_p.random_element()
    c2 = g*r
    c1 = pk*r+P
    ce1,ce2 = compress_element(c1),compress_element(c2)
    return "%065x%065x%065x%065x\n"%(*compress_element(c1),*compress_element(c2))
    #return int_to32(ce1[0])+int_to32(ce1[1])+int_to32(ce2[0])+int_to32(ce2[1])

def enc_str(s):
    enc_map,ret = {},""
    for c in s :
        if c in enc_map:
            cF_p2=enc_map[c]
        else :
            prefix = os.urandom(29)+bytes(c,encoding='ascii')
            x1 = int(F_p.random_element())
            for i in range(256):
                cF_p2 = load_element(x1,bytes_to_long(prefix+bytes([i])))
                if cF_p2!=None:
                    enc_map[c]=cF_p2
                    break
        ret = ret+enc_element(cF_p2)
    return ret

def dec_element(ct):
    c11,c12,c21,c22=[ct[i*65:i*65+65] for i in range(4)]
    C1,C2=load_element(int("0x"+c11,16),int("0x"+c12,16)),load_element(int("0x"+c21,16),int("0x"+c22,16))
    P=C1-C2*sk
    return (compress_element(P)[1]&0xffff)>>8

print("g = load_element(*"+str(compress_element(g))+")")
print("pk = load_element(*"+str(compress_element(pk))+")")
#g = load_element(*(29278822809335293856257839032454656006652898948724335358857767737708161772420, 4396426956433009559948787995869502944693089612343852188342374458334039665950))
#pk = load_element(*(148673571405127568767045322546948264768210305253661849398897382818523458361167, 23902769016595610010920651447268476259469689719718232568266731055385481225779))

with open("test_passage.txt","r") as f:
    s = f.readline().strip()

with open("ciphertext",'w') as f:
    f.write(enc_str(s))

这个题做法很简单，题目描述说是压缩了一段话，而且直接解 ECDLP 不现实，所以就是去判断两个 cipher_text 是不是同一个字母，然后替换密码用 qiupqiup 解。而这个同类判断就是两个 cipher 的 point 相减，变成一个类 DDH 问题。这个搜论文可以直接拿

解，所以就没了。

SpRAse

这个题就是还原一个 RSA 密钥文件。做法也很简单，把已知数据提取出来，我们能知道的值，的若干 bit，爆搜低位，用已知信息剪枝，高位直接用 copper smith 解就好了。然后我被提取数据时长度会有 1 byte 左右偏差这个点卡了一天，哭了。