Smooth Signatures

Challenge

Signature oracle challenge using a smooth modulus construction; recover factors and forge a valid signature for the flag query.

Solution

Key solve code:

p = remote("localhost",1337)
p.sendlineafter(b"Give the oracle a message to sign: ", b"hello world")
p.recvuntil(b"Your verification signature is (")
r, s = map(int, p.recvline().decode().strip()[:-1].split(", "))

msg = b"hello world"
h = bytes_to_long(sha256(msg).digest())
factors = []
for i in range(2**23, 2**24):
	if isPrime(i):
		if (pow(s % i, 65537, i) - pow(r % i, 65537, i) - h) % i == 0:
			factors.append(i)

n = 1
q = 1
for f in factors:
	n *= f
	q = lcm(q, f - 1)
d = pow(65537, -1, q)

newr, news = sign(n, b"What is the flag?", d)
p.sendlineafter(b"Give the verification signature: ", f"{newr},{news}".encode())

Flag

gigem{sm00th_numb3rs_4r3_345y_70_f4c70r}