# Smooth Signatures Writeup

> From: TAMUctf 2024
> Tags: Cryptography
> Author: GoldenBushRobin
>
> I've heard signatures are pretty good tools for verifying the sender. Signatures are suposed to be personalized and unique, so surely this one is impossible to forge... right?
> Files: `smooth-signatures.zip`, which contains `smooth_signatures.py` and `solver-template.py`
>
> Solved by: Jackylkk2003

## The given files

`smooth_signatures.py`

from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from math import lcm,gcd
from secrets import randbelow
from hashlib import sha256

NUM_BITS = 2048

def getModulus(bits):
    n = 1
    primes = []
    while n.bit_length() < bits:
        p = getPrime(24)
        if p not in primes:
            n *= p
            primes.append(p)
    return n,primes

def sign(n,msg,d):
    h = bytes_to_long(sha256(msg).digest())
    k = randbelow(q-2)+1
    x = pow(h,k,n)
    r = pow(x,d,n)
    s = pow(h+x,d,n)
    return r,s

def verify(n,msg,e,r,s):
    h = bytes_to_long(sha256(msg).digest())
    v1 = pow(r,e,n)
    v2 = pow(s,e,n)
    return v2 == (v1 + h) % n

n,primes = getModulus(NUM_BITS)
q = 1
for p in primes:
    q = lcm(q,p-1)
msgs = []
e = 65537
d = pow(e,-1,q)

print(f"The modulus is ... a mystery left for you to unfold.")
print(f"Your verification exponent {e = }")
msg = input("Give the oracle a message to sign: ").encode()
msgs.append(msg)
r,s = sign(n,msg,d)
print(f"Your verification signature is ({r}, {s})")

msg = input("Give the oracle another message to sign: ").encode()
msgs.append(msg)
r,s = sign(n,msg,d)
print(f"Your second verification signature is ({r}, {s})")

comm = input("Ask the oracle a question: ").encode()
r,s = input("Give the verification signature: ").split(",")
r,s = int(r),int(s)

if comm in msgs:
    print("Hey, no cheating")
    exit()
if verify(n,comm,e,r,s):
    if comm == b"What is the flag?":
        print("The flag is: ",end="")
        with open("flag.txt","r") as flag:
            print(flag.read())
    else:
        print("Not the right question.")
else:
    print("Invalid signature")

`solver-template.py`

from pwn import *

context.log_level = "debug"
io = remote("tamuctf.com", 443, ssl=True, sni="smooth-signatures")
io.interactive(prompt="")

## Code Analysis

We first take a look at the code for encryption.

def getModulus(bits):
    n = 1
    primes = []
    while n.bit_length() < bits:
        p = getPrime(24)
        if p not in primes:
            n *= p
            primes.append(p)
    return n,primes

This getModulus function generates some distinct 24 bit primes and multiplies them to give $n$.

def sign(n,msg,d):
    h = bytes_to_long(sha256(msg).digest())
    k = randbelow(q-2)+1
    x = pow(h,k,n)
    r = pow(x,d,n)
    s = pow(h+x,d,n)
    return r,s

This function computes the signature of the message with $n$ as the modulo and a $d$ as private key. Some randomness is involved to generate $k$.

Some math to summarize the sign function:

$$h = SHA256(msg)$$ $$k = random([1, q-1])$$ $$x \equiv h^k (mod\ n)$$ $$r \equiv x^d \equiv h^{kd}\ (mod\ n)$$ $$s \equiv (h + x)^d \equiv (h + h^k)^d\ (mod\ n)$$

And we know only $r$, $s$ from the sign function.

def verify(n,msg,e,r,s):
    h = bytes_to_long(sha256(msg).digest())
    v1 = pow(r,e,n)
    v2 = pow(s,e,n)
    return v2 == (v1 + h) % n

This function verifies that whether a digital signature is valid for a given message.

Some math to summarize the verify function:

$$h = SHA256(msg)$$ $$v1 \equiv r^e\ (mod\ n)$$ $$v2 \equiv s^e\ (mod\ n)$$

And we should have $v2 \equiv v1 + h\ (mod\ n)$ in the case of valid signature.

Since the verification will use the $r$, $s$ from the sign function, we can substitute some variables with what we have in the sign function.

$$v1 \equiv h^{kde}\ (mod\ n)$$ $$v2 \equiv (h + h^k)^{de}\ (mod\ n)$$

n,primes = getModulus(NUM_BITS)
q = 1
for p in primes:
    q = lcm(q,p-1)
msgs = []
e = 65537
d = pow(e,-1,q)

$n$ is generated using the getModulus function to have at least 1024 bits. We also generate $q$ as the lcm of $p-1$ for all prime factors $p$ of $n$. Using Fermat's little theorem and Chinese remainder theorem, we can know that $a^q \equiv 1\ (mod\ n)$ for all integers $a \not\equiv 0\ (mod\ n)$.

A proof sketch would be:

By Fermat's little theorem, we know that $a^{p-1} \equiv 1\ (mod\ p)$, and so we know that $a^{(p-1)\cdot c} = 1$ for any constant integer $c$. Note that we can put $c = \frac{q}{p-1}$, and $\frac{q}{p-1}$ is an integer since $q$ is lcm of different $p-1$. So we have $a^q \equiv 1\ (mod\ p)$ for all the prime factors $p$ of $n$. Using Chinese remainder theorem, we know that $a^q \equiv 1\ (mod\ n)$.

So it is actually quite similar to what we have in an ordinary RSA despite having multiple primes.

Similar to what we have in ordinary RSA, we have $d \equiv e^{-1}\ (mod\ q)$.

print(f"The modulus is ... a mystery left for you to unfold.")
print(f"Your verification exponent {e = }")
msg = input("Give the oracle a message to sign: ").encode()
msgs.append(msg)
r,s = sign(n,msg,d)
print(f"Your verification signature is ({r}, {s})")

msg = input("Give the oracle another message to sign: ").encode()
msgs.append(msg)
r,s = sign(n,msg,d)
print(f"Your second verification signature is ({r}, {s})")

comm = input("Ask the oracle a question: ").encode()
r,s = input("Give the verification signature: ").split(",")
r,s = int(r),int(s)

if comm in msgs:
    print("Hey, no cheating")
    exit()
if verify(n,comm,e,r,s):
    if comm == b"What is the flag?":
        print("The flag is: ",end="")
        with open("flag.txt","r") as flag:
            print(flag.read())
    else:
        print("Not the right question.")
else:
    print("Invalid signature")

The remaining part is not very interesting. We can send 2 plaintexts for the sign function to sign, and then we have to sign the message "What is the flag?"

from pwn import *

context.log_level = "debug"
io = remote("tamuctf.com", 443, ssl=True, sni="smooth-signatures")
io.interactive(prompt="")

This simply provides the server for us to connect to. Nothing interesting.

## Important Observations

There are some important things that should be considered after reading the code.

* $n$ is large (2048 bits), but has many small prime factors (24 bits)
* How the signature works, that is, how come the digital signature still works when the signature involves randomness.

$$v2 \equiv (h + h^k)^{de} \equiv h + h^k \equiv h + v1\ (mod\ n) $$

* The messages are hashed using SHA256, so it is basically impossible for us to choose a special plaintext for some strange attacks since SHA256 is (currently assumed to be) secure.

## Factorization Preparation

The very first thought is to factorize $n$. However, $n$ is unknown in this problem.

To obtain more information about the parameters, we have to send a message. By the observation above, it does not matter what message we choose. For simplicity, we choose `b"1"` as the first message.

io.sendlineafter(b"Give the oracle a message to sign: ", b"1")
io.recvuntil(b"Your verification signature is (")
r1 = int(io.recvuntil(b",")[:-1])
s1 = int(io.recvuntil(b")")[:-1])

Before we proceed with using the information, how do we factorize $n$? Useful or not, let's first generate all primes from $2^{23}$ to $2^{24}$ (The getPrime function will only generate primes in this range). We can do this using a [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).

primes = []
is_prime = [True] * (2**24)
for i in range(2, 2**12):
    if is_prime[i]:
        for j in range(i * i, 2**24, i):
            is_prime[j] = False

for i in range(2**23, 2**24):
    if is_prime[i]:
        primes.append(i)

Now, the factorization problem becomes simpler. Instead of thinking how to factorize a large number $n$, we can think how to check whether a prime $p$ is a factor of $n$.

Assuming we have such a checking, then we can simply iterate through the list of primes (length 513708, and is 1077871 if you start from 2 instead of 2**23) and carry out the checking for each prime.

## How to do the checking?

From the [above](#The-given-files), we have found that the verify function checks whether $v1$ and $v2+h$ are the same when modulo $n$. In other words, $v2 \equiv v1 + h\ (mod\ n)$.

We can make use of this verify function to do the checking using one fact: If $v2 \equiv v1 + h\ (mod\ n)$ and $n \equiv 0\ (mod\ p)$, then we have $v2 \equiv v1 + h\ (mod\ p)$. This result is fairly easy to understand.

Don't worry if you don't understand. Consider some concrete examples. 49 and 89 are the same when modulo 40 (both 9). If we take modulo 8 instead of 40, they are still equal (both 1), or if we take modulo 5, they are again equal (both 4). This is because we are essentially just breaking the original groups of 40 into groups of 8 or 5, and we only need to handle the remainder, which is the same.

So what does this imply? We can use the verify function, but instead of inputting the unknown $n$, we input the prime $p$ that we want to check.

def verify(n,msg,e,r,s): # same as the one given in the challenge
    h = bytes_to_long(sha256(msg).digest())
    v1 = pow(r,e,n)
    v2 = pow(s,e,n)
    return v2 == (v1 + h) % n

for p in primes:
    if verify(p, b"1", e, r1, s1):
        n *= p
        q = lcm(q, p - 1)

d = pow(e, -1, q)

## Solution
Now we have got $n$, $d$, $q$. We can call the sign function and construct the digital signature.

msg = b"What is the flag?"
r, s = sign(n, msg, d)
io.sendlineafter(b"Ask the oracle a question: ", msg)
io.sendline(f"{r},{s}".encode())
print(io.recvall())

And turns out we can get the flag already.

from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from math import lcm,gcd
from secrets import randbelow
from hashlib import sha256
from pwn import *
context.log_level = "debug"
io = remote("tamuctf.com", 443, ssl=True, sni="smooth-signatures")

# Generate all primes from 2^23 to 2^24 using the sieve of Eratosthenes
primes = []
is_prime = [True] * (2**24)
for i in range(2, 2**12):
    if is_prime[i]:
        for j in range(i * i, 2**24, i):
            is_prime[j] = False

for i in range(2**23, 2**24):
    if is_prime[i]:
        primes.append(i)

io.sendlineafter(b"Give the oracle a message to sign: ", b"1")
io.recvuntil(b"Your verification signature is (")
r1 = int(io.recvuntil(b",")[:-1])
s1 = int(io.recvuntil(b")")[:-1])
io.sendlineafter(b"Give the oracle another message to sign: ", b"2")
io.recvuntil(b"Your second verification signature is (")
r2 = int(io.recvuntil(b",")[:-1])
s2 = int(io.recvuntil(b")")[:-1])

n = 1
q = 1
e = 65537
def verify(n,msg,e,r,s): # same as the one given in the challenge
    h = bytes_to_long(sha256(msg).digest())
    v1 = pow(r,e,n)
    v2 = pow(s,e,n)
    return v2 == (v1 + h) % n

for p in primes:
    if verify(p, b"1", e, r1, s1): # and verify(p, b"2", e, r2, s2):
        n *= p
        q = lcm(q, p - 1)

d = pow(e, -1, q)

def sign(n,msg,d): # same as the one given in the challenge
    h = bytes_to_long(sha256(msg).digest())
    k = randbelow(q-2)+1
    x = pow(h,k,n)
    r = pow(x,d,n)
    s = pow(h+x,d,n)
    return r,s

msg = b"What is the flag?"
r, s = sign(n, msg, d)
io.sendlineafter(b"Ask the oracle a question: ", msg)
io.sendline(f"{r},{s}".encode())
print(io.recvall())
io.close()

And we have the flag `gigem{sm00th_numb3rs_4r3_345y_70_f4c70r}`.

## Follow ups

### Wait, we can ask for the signature 2 times.

It turns out that the second time is ~~useless~~ redundant. But still, you can use it for double verification to ensure that there are no strange cases where `verify(p)` gives true but is not a factor of $n$. (Until now I don't have any proof that this case will not happen, but also haven't found any cases like this)

In the solution code above, we just wasted it. We can get the flag anyway.

### There are many primes, will the solution run very slowly?

From my experiment, the solution script takes 5s to run, and it takes 7s if we select all primes from $2$ rather than $2^{23}$.