HITCONCTF2023 Scoreboard

During this competition, we can learn a lot from maple3142!

echo(284 pts, 20 solve)

challenge description

A secure, cryptographically signed echo-as-a-service.

You can use choice 1 to sign a msg with the form: echo {quote(msg)}.

And choice 2 can execute the cmd which you should get its signature.

sign is implemented by RSA(512).

# `give` is a compiled binary that will output flag if you execute `./give me flag please`

my solution

At first, we don’t know about the pub parameters of rsa.

I want to compute the modulus n by GCD, like

m0=m ; m1=m0*k ; m2=m1*k; m3=m2*k
n = GCD(m3*m1-m2**2,m2*m0-m1**2)

But there is a problem with this. When you quote a msg with utf-8,there will be ' at the front and back.

echo '1 '
      +
      echo '1'

the code:

from Crypto.Util.number import *
from shlex import quote
msg = "1 "
cmd = f"echo {quote(msg)}".encode()
print(cmd)
a1 = bytes_to_long(cmd)
for i in range(256):
    t = i*256+256**9+1
    try:
        m = long_to_bytes(t*a1)
        m.decode()
        print(i)
        print(m)
    except:
        continue

We can get the n by this way.

After that , I want to get e or d but it’s too difficult. I want to do something in the cmd.

./give me flag please can get flag, so I try to construct

cmd = (./give me flag please&' + anything + ') ; sign(cmd) = kn;

anything should be all bytes in [0,128], LLL can do this.

ezrsa(327 pts, 11 solve)

challenge description

I am out of ideas, so why not just make a challenge from a random paper.

a implementation of this paper, but there is a problem in compute_u,which is different with paper’s.

def compute_u(self, a, p, u, v):
    s = gmpy2.powmod(a, (p - 1) // 4, p)
    if s == 1:
        return -u
    elif s == p - 1:
        return u
    elif s * v % p == u:
        return v
    else:
        return -v

my solution

1. gcd to get n
2. y^2=x^3%n ⇒ dlp to get 4th condition’s d
3. continued fraction d/(n+1) to get e,cuz e<N^0.125
4. use d and e , the 4th condition a's curve can let u compute the GCD(phi_factor*C,n)==p with a probability 1/16.
5. compute two square of p and q to get priv
6. solve the last prob

Share(222 pts, 47 solve)

challenge description

I hope I actually implemented Shamir Secret Sharing correctly this year. I am pretty sure you won’t be able to guess my secret even when I give you all but one share.

class SecretSharing:
    def __init__(self, p: int, n: int, secret: int):
        self.p = p
        self.n = n
        self.poly = [secret] + [getRandomRange(0, self.p - 1) for _ in range(n - 1)]

    def evaluate(self, x: int) -> int:
        return (sum([self.poly[i] * pow(x, i, self.p) for i in range(len(self.poly))])% self.p)

    def get_shares(self) -> List[int]:
        return [self.evaluate(i + 1) for i in range(self.n)]

if __name__ == "__main__":
    signal.alarm(30)
    secret = bytes_to_long(os.urandom(32))
    while True:
        p = int(input("p = "))
        n = int(input("n = "))
        if isPrime(p) and 13 < n < p:
            shares = SecretSharing(p, n, secret).get_shares()
            print("shares =", shares[:-1])
        else:
            break
    if int(input("secret = ")) == secret:
        print(open("flag.txt", "r").read().strip())

my solution

getRandomRange(0, self.p - 1) the max of this function is p-2, so we can choose small prime p and n=p-1, then we brute the only one value of secret%p which make the other coefficients ∈ [0,p-2].

then crt the value with prod(p_i) > 256 bit. but you should one time send a lot of p and n, cuz the time of interaction.

like this

def get_data(p,n):
    for _ in range(5):
         io.sendline(str(p).encode())
         io.sendline(str(n).encode())
    sharess= []
    for _ in range(5):
         io.recvuntil(b'shares =')
         sharess.append(eval(io.recvline().strip()))
    return sharess

Random Shuffling Algorithm(321 pts, 12 solve)

challenge description

I think you already know what is this challenge about after seeing the challenge name :)

m0,m1,m2 random choose, m3 = flag^m0^m1^m2, msg = [m0,m1,m2]

get 100 pubs (pub(1024 bit) = p*q).

cts = []
for pub in pubs:
    random.shuffle(msgs)
    cur = []
    for m in msgs:
        a = getRandomRange(0, pub)
        b = getRandomRange(0, pub)
        c = pow(a * m + b, 11, pub)
        cur.append((a, b, c))
    cts.append(cur)

give pubs and cts.

my solution

then you can crt the to get a polynomial

we know , by coppersmith’s bound, we can compute

beta = 1.0,delta = 44, X = 2**1016; =>1017 = (1024n)(1/44-epsilon), n <= 100;

we choose n=100,epsilon = 0.0125, small root the by flatter, about 15 mins to get the 4 small roots.