# bi0sCTF 2024 Writeup
我有種被打回兩年前第一次打ISSC的感覺，真的只會簽到題。
## lalala

from random import randint
from re import search

flag = "bi0sctf{%s}" % f"{randint(2**39, 2**40):x}"

p = random_prime(2**1024)
unknowns = [randint(0, 2**32) for _ in range(10)]
unknowns = [f + i - (i%1000)  for i, f in zip(unknowns, search("{(.*)}", flag).group(1).encode())]

output = []
for _ in range(100):
    aa = [randint(0, 2**1024) for _ in range(1000)]
    bb = [randint(0, 9) for _ in range(1000)]
    cc = [randint(0, 9) for _ in range(1000)]
    output.append(aa)
    output.append(bb)
    output.append(cc)
    output.append(sum([a + unknowns[b]^2 * unknowns[c]^3 for a, b, c in zip(aa, bb, cc)]) % p)

print(f"{p = }")
print(f"{output = }")

我們會發現 unknowns[b]^2 * unknowns[c]^3 只有100種可能，他又給我們100個式子，所以解線性方程就能得出所有結果。當b和c取一樣的時候，我們可以有 unknowns[b]^5 ，但是因為p-1是5的倍數，所以我用coppersmith。然後我也不知道為什麼那個output直接放在sage裡有問題，所以我先用python處理完在丟進去sage算。

import pickle
p = 22164857548872153350792863287126662739346790382724883568469825455088689119474784066358095106688985128245096556482593315395509994112330842037731896432716074587916002372658113733392392830971642878227300074751441475110802528284293674049241201403401496426351459462195992798867652944173025546970871261462401766951
output = #很長的東西

aas = [output[i] for i in range(0, len(output), 4)]
bbs = [output[i] for i in range(1, len(output), 4)]
ccs = [output[i] for i in range(2, len(output), 4)]
ress = [output[i] for i in range(3, len(output), 4)]

result = []
mat = []

for aa, bb, cc, res in zip(aas, bbs, ccs, ress):
    res -= sum(a for a in aa)
    res %= p
    tmp = [0] * 100
    for b, c in zip(bb, cc):
        tmp[b * 10 + c] += 1
    mat.append(tmp)
    result.append(res)

with open("mat.pickle", "wb") as f:
    pickle.dump(mat, f)
with open("result.pickle", "wb") as f:
    pickle.dump(result, f)

from sage.all import *
from Crypto.Util.number import *
import pickle
p = 22164857548872153350792863287126662739346790382724883568469825455088689119474784066358095106688985128245096556482593315395509994112330842037731896432716074587916002372658113733392392830971642878227300074751441475110802528284293674049241201403401496426351459462195992798867652944173025546970871261462401766951

with open("mat.pickle", "rb") as f:
    mat = pickle.load(f)
with open("result.pickle", "rb") as f:
    result = pickle.load(f)


mat = Matrix(GF(p), mat)
result = vector(GF(p), result)

sol = mat.solve_right(result)
ans = []

for i in range(10):
    P.<x> = PolynomialRing(GF(p))
    f = x^5 - sol[i * 10 + i]
    k = f.small_roots()[0]
    ans.append(int(k))
    print(k^5 % int(p) == sol[i * 10 + i])

flag = b"bi0sctf{"
for i in ans:
    flag += long_to_bytes(i % 1000)
flag += b"}"
print(flag)

## challengegame

from ecdsa.ecdsa import Public_key, Private_key
from ecdsa import ellipticcurve
from hashlib import md5
import random
import os
import json

flag = open("flag", "rb").read()[:-1]

magic = os.urandom(16)

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = ###REDACTED###
b = ###REDACTED###
G = ###REDACTED###

q = G.order()

def bigsur(a,b):
    a,b = [[a,b],[b,a]][len(a) < len(b)]
    return bytes([i ^ j for i,j in zip(a,bytes([int(bin(int(b.hex(),16))[2:].zfill(len(f'{int(a.hex(), 16):b}'))[:len(a) - len(b)] + bin(int(b.hex(),16))[2:].zfill(len(bin(int(a.hex(), 16))[2:]))[:len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:])][i:i+8], 2) for i in range(0,len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:]),8)]) + b)])

def bytes_to_long(s):
    return int.from_bytes(s, 'big')

def genkeys():
    d = random.randint(1,q-1)
    pubkey = Public_key(G, d*G)
    return pubkey, Private_key(pubkey, d)

def sign(msg,nonce,privkey):
    hsh = md5(msg).digest()
    nunce = md5(bigsur(nonce,magic)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nunce))
    return json.dumps({"msg": msg.hex(), "r": hex(sig.r), "s": hex(sig.s)})

def enc(privkey):
    x = int(flag.hex(),16)
    y = pow((x**3 + a*x + b) % p, (p+3)//4, p)
    F = ellipticcurve.Point('--REDACTED--', x, y)
    Q = F * privkey.secret_multiplier
    return (int(Q.x()), int(Q.y()))

pubkey, privkey = genkeys()
print("Public key:",(int(pubkey.point.x()),int(pubkey.point.y())))
print("Encrypted flag:",enc(privkey))

nonces = set()

for _ in '01':
    try:
        msg = bytes.fromhex(input("Message: "))
        nonce = bytes.fromhex(input("Nonce: "))
        if nonce in nonces:
            print("Nonce already used")
            continue
        nonces.add(nonce)
        print(sign(msg,nonce,privkey))
    except ValueError:
        print("No hex?")
        exit()

這題是ecdsa的題目，他有給兩個點，橢圓曲線很好求。然後他可以簽兩個訊息，而且能用Nonce去指定k，只是他會和未知的16 bytes通過bigsur運算。試了一些東西後會發現，當Nonce是b'\x00\x00\x00\x01'和b'\x00\x00\x01\x03'的時候，不管配任何東西k都會相等，至於驗證就看送兩個訊息進去r有沒有相等就好。既然可以有兩個相同的k，那d就很好求出來了。至於他加密flag的方式是將flag作為x所得出的點乘上d，雖然他有稍微混淆一下不過用簡單的數學推導能得出他一定在橢圓曲線上。那接下來就是一個橢圓曲線開根號的問題。先說一個我覺得可能可以做到但我不會做的方法，因為他模數是p，所以應該可以用類似Smart's attack的方式把他映射到Qp上，然後用簡單的模運算求出來後再射回去。不過因為他的階是質數，所以其實直接求出d的模逆元就可以了。

from sage.all import *
from pwn import *
import json
from Crypto.Util.number import *
from hashlib import md5


p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff

r = remote("13.201.224.182", int(30773))
mat = []
res = []
r.recvuntil(b": (")
x, y = map(int, r.recvuntil(b")").decode()[:-1].split(", "))
pubkey = (x, y)
mat.append([x, 1])
res.append(y^2 - x^3)
r.recvuntil(b": (")
x, y = map(int, r.recvuntil(b")").decode()[:-1].split(", "))
ciphertext = (x, y)
mat.append([x, 1])
res.append(y^2 - x^3)

mat = Matrix(GF(p), mat)
res = vector(GF(p), res)
a, b = mat.solve_right(res)
E = EllipticCurve(GF(p), [a, b])
q = E.order()

r.sendlineafter(b"Message: ", b"\x00\x00\x00\x01".hex().encode())
r.sendlineafter(b"Nonce: ", b'\x00\x00\x00\x01'.hex().encode())
recv = json.loads(r.recvline().decode().strip())
msg1, r1, s1 = recv["msg"], int(recv["r"][2:], 16), int(recv["s"][2:], 16)
r.sendlineafter(b"Message: ", b"\x00\x00\x00\x02".hex().encode())
r.sendlineafter(b"Nonce: ", b'\x00\x00\x01\x03'.hex().encode())
recv = json.loads(r.recvline().decode().strip())
msg2, r2, s2 = recv["msg"], int(recv["r"][2:], 16), int(recv["s"][2:], 16)

msg1 = bytes_to_long(md5(bytes.fromhex(msg1)).digest())
msg2 = bytes_to_long(md5(bytes.fromhex(msg2)).digest())

d = (msg2 * s1 - msg1 * s2) % q * pow(r1 * s2 - r2 * s1, -1, q) % q
print((msg1 + d * r1) * s2 % q == (msg2 + d * r2) * s1 % q)




G = E(pubkey)
Q = E(ciphertext)


k = pow(int(d), -1, int(E.order()))
x = Q * int(k)
print(x * int(d) == Q)
flag = int((Q * int(k)).xy()[0])
print(long_to_bytes(flag))