This challenge implements ECDSA over a custom elliptic curve. The nonces that it generates for ECDSA are 512 bits long, while the order of the curve is 521 bits long. Therefore, the generated nonces are “small” compared to the order of the curve. We will use LLL to exploit this and recover the key. This is the code of the challenge:

def sign(msg, skey):
	h = bytes_to_long(sha512(msg).digest())
	k = getRandomNBitInteger(h.bit_length())
	P = k * G
	r = int(P.xy()[0]) % n
	s = pow(k, -1, n) * (h + r * skey) % n
	return (r, s)

def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, " Hey! To solve the Snails cryptography challenges one often needs", border)
	pr(border, " to perform meticulous bit by bit analysis to uncover loopholes  ", border)
	pr(border, " and ultimately extract the high value flag! Good luck ;) 🐌🐌🐌 ", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
	global flag, G, n
	skey = bytes_to_long(flag)
	p = 0x013835f64744f5f06c88c8d7ebfb55e127d790e5a7a58b7172f033db4afad4aca1ae1cdb891338cf963b30ff08d6af71327770d00c472c52290a60fb43f1d070025b
	a = 0x0109ec0177a5a57e7b7890993e11ba1bc7ba63c1f2afd904a1df35d1fda7363ea8e83f3291e25b69dac26d046dc5ba9a42ff74cd7e52c9df5dbe8d4d02755d26b111
	b = 0x0037c84047a6cc14e36d180f9b688fe9959cb63f4ac37b22eb24559e83cfc658ff0ab753540b8ab8d85a62dd67aa92f79dec20d28e453d4663ef2882c7b031ddc0b9
	n = 0x013835f64744f5f06c88c8d7ebfb55e127d790e5a7a58b7172f033db4afad4aca1aad8763fe2401b5189d1c449547a6b5295586ce30c94852845d468d52445548739
	x = 0x00339495fdbeba9a9f695d6e93effeb937609ce2e628958cd59ba307eb3a43c4c3a54b9b951cd593c876df93a9b0ed7d64df641af94668cb594b6a636ae386e1ac1b
	y = 0x00038389f29ad8c87e79a8b854e78310b72febb6b1840e360b0a43733933529ee6a04f6d7ea0d91104eb83d1162d55c410eca1c7b45829925fb2a9bf9c1232c32972
	E = EllipticCurve(GF(p), [a, b])
	G = E(x, y)
	m = '✔✔✔ My signature is the priority'.encode()
	while True:
		pr(f"{border} Options: \n{border}\t[S]ign message! \n{border}\t[Q]uit")
		ans = sc().decode().strip().lower()
		if ans == 's':
			pr(border, f'Please send your message: ')
			msg = sc().strip()
			if m in msg and len(msg) == 40:
				r, s = sign(msg, skey)
				pr(border, f'{r = }')
				pr(border, f'{s = }')
			else:
				die(border, 'Not valid message! Bye!!')
		elif ans == 'q':
			die(border, "Quitting...")
		else:
			die(border, "Bye...")

We note that the order of the curve is 521 bits long:

sage: n = 0x013835f64744f5f06c88c8d7ebfb55e127d790e5a7a58b7172f033db4afad4aca1aad8763fe2401b5189d1c449547a6b5295586ce30c94852845d468d52445548739
sage: n.bit_length()
521

In the sign function (which is properly implemented), the size of the nonces generated (usually called k) depend on the size of the output of the sha512 hash function, which is 512 bits. We can use LLL to exploit this size difference. First, rearrenge the signature expression (denoting $H$ as the sha512 function and $d$ as the secret key):

$$s \equiv k^{-1} (H(m) + rd) \implies sk \equiv H(m) + rd \implies k = s^{-1}H(m) + s^{-1}rd$$

This further implies that

$$\exists c \in \mathbb{Z} : k = s^{-1}H(m) + s^{-1}rd + cn$$

In matrix notation,

$$\begin{pmatrix}1 & d & c\end{pmatrix} \begin{pmatrix}s^{-1}H(m) \ s^{-1}r \ n\end{pmatrix} = k$$

Putting together a few of these equations from different signatures, we can construct a matrix and apply the LLL algorithm to it, to recover $d$. We can do that using this sagemath code:

n = 0x013835f64744f5f06c88c8d7ebfb55e127d790e5a7a58b7172f033db4afad4aca1aad8763fe2401b5189d1c449547a6b5295586ce30c94852845d468d52445548739
prefix = '✔✔✔ My signature is the priority'.encode()
io = process("./snails.sage")

def get_signatures(count):
    sigs = []
    
    for i in range(count):
        msg = prefix + b"AA"
        io.sendlineafter(b"[Q]uit\n", b"s")
        io.sendlineafter(b"message:", msg)
        
        io.recvuntil(b"r = ")
        r = int(io.recvline().strip())
        io.recvuntil(b"s = ")
        s = int(io.recvline().strip())
        
        h = bytes_to_long(sha512(msg).digest())
        sigs.append((r, s, h))
        
    return sigs

num_sigs = 100
sigs = get_signatures(num_sigs)

M = Matrix(QQ, num_sigs + 2, num_sigs + 2)
for i in range(num_sigs):
    r, s, h = sigs[i]
    sinv = pow(s, -1, n)
    A = (sinv * h) % n
    B = (sinv * r) % n
    
    M[i, i] = n
    M[num_sigs, i] = B
    M[num_sigs + 1, i] = A

M[num_sigs, num_sigs] = 1 
M[num_sigs + 1, num_sigs + 1] = n 

L = M.LLL()
for row in L:
    for val in [row[num_sigs], n - row[num_sigs], n + row[num_sigs]]:
        potential_skey = abs(int(val))
        if potential_skey > 0:
            flag = long_to_bytes(potential_skey)
            if b"CCTF{" in flag:
                success(f"Flag recovered: {flag}")