Fractional RSA

COMP2633 Week 8 Homework B

12. Preface

Challenge authored by Tom Yueng, Firebird Core member.

14 solves. First blood in 24 minutes.

13. Analysis

The challenge implements a variation of RSA, so called “Fractional RSA”. Normally the setup for RSA uses:

A public key $(𝑛, 𝑒)$ , where $𝑛 = 𝑝 \cdot 𝑞$ the product of two large distinct primes and $𝑒$ is an integer coprime to $𝑛$ .
Encryption
$𝑐 = 𝑚^{𝑒} mod 𝑛$
Decryption, where $𝑑$ is the modular inverse of $𝑒 mod 𝜑 (𝑛)$
$𝑚 = 𝑐^{𝑑} mod 𝑛$
$𝜑 (𝑛)$ is the number of integers smaller than n that are coprime to it. For $𝑛 = 𝑝 \cdot 𝑞$ , we can show that $𝜑 (𝑛) = (𝑝 - 1) (𝑞 - 1)$ .

However, in this challenge:

$𝑛$ is the product of 10 distinct primes, each 256 bits.
The public exponent is set to $𝑒 = 65537$ .
We are given the ciphertext $𝑐 = 𝑚^{𝑒} mod 𝑛$ , where $𝑚$ is the flag.
The server offers an oracle with two operations:
1. Encrypt with $𝑒 = 2$ , i.e returns $𝑚^{2} mod 𝑛$ .
2. Decrypt with $𝑑 = \frac{1}{2}$ , i.e returns $\sqrt{𝑐} mod 𝑛$ .

Furthermore, the modulus $𝑛$ is hidden, and we are only allowed 20 queries.

14. The Vulnerability

RSA depends on $𝑛$ being difficult to factor, thus it is difficult to compute $𝜑 (𝑛)$ and you cannot determine $𝑑 \equiv 𝑒 mod 𝜑 (𝑛)$ for decryption.

However, if we have all the 10 factors,

𝑛 = 𝑎 \cdot 𝑏 \cdot 𝑐 \cdot 𝑑 \cdot 𝑒 \cdot 𝑓 \cdot 𝑔 \cdot ℎ \cdot 𝑖 \cdot 𝑗

Then we know that,

𝜑 (𝑛) = (𝑎 - 1) (𝑏 - 1) (𝑐 - 1) (𝑑 - 1) (𝑒 - 1) (𝑓 - 1) (𝑔 - 1) (ℎ - 1) (𝑖 - 1) (𝑗 - 1)

Since the servers oracle allows us to compute the square root of integers $mod 𝑛$ , we can exploit this to factor $𝑛$ .

15. The Attack Vector

15.1. Step 1: Recover N

The encryption oracle computes $𝑐 \equiv 𝑚^{2} mod 𝑛$ , so for large random $𝑚$ :

𝑚^{2} - 𝑐 = 𝑘 \cdot 𝑛

Thus we can compute $𝑎 = 𝑚^{2} - 𝑐$ for several random $𝑚$ .

Then take the $gcd (𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑘})$ to recover $𝑛$ .

This is because $𝑘 \cdot 𝑛$ will likely be different for each $𝑚$ .

If $gcd (𝑘_{1}, 𝑘_{2}, \dots, 𝑘_{𝑘}) = 1$ , then $gcd (𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑘}) = 𝑛$ .

15.2. Step 2: Factoring N

Now that we have $𝑛$ , we can use the decryption oracle to factor it.

It may not seem obvious that we need to do this, however if you look at how the decryption oracle works

def sqrt_mod_n(a, ps):
    residues = []
    for p in ps:
        q = nthroot_mod(a, 2, p)
        if q is None:
            return -1
        else:
            residues.append(q)
    return int(crt(ps, residues)[0])

$𝑝 𝑠$ is the list of prime factors of $𝑛$ . Thus, the decryption oracle is actually computing the square root $mod$ each prime factor of $𝑛$ and then combining them using the Chinese Remainder Theorem.

This gives the hint that we can use the square root oracle to factor n.

To factor $𝑛$ , we will start with the following approach:

Pick a large random $𝑥$ .
Locally compute $𝑐 = 𝑥^{2} mod 𝑛$ .
Query the oracle for the decryption of $\sqrt{𝑐}$

Why query the oracle for decryption?

Encryption with $𝑒 = \frac{1}{2}$ means $𝑐 = \sqrt{𝑚} mod 𝑛$ .

So instead when we input $\sqrt{𝑐}$ , then $\sqrt{𝑐} \equiv \sqrt{𝑚} mod 𝑛$ .

Let $𝑦 = \sqrt{𝑚}$ , then we know that $𝑦^{2} \equiv 𝑐 \equiv 𝑥^{2} mod 𝑛$ . And further,

\begin{aligned} 𝑦^{2} & \equiv 𝑥^{2} mod 𝑛 \\ 𝑦^{2} \cdot 𝑥^{-} 2 & \equiv 1 mod 𝑛 \\ {(𝑦 \cdot 𝑥^{-} 1)}^{2} & \equiv 1 mod 𝑛 \end{aligned}

Let $𝑠 = 𝑦 \cdot 𝑥^{- 1}$ , then

\begin{aligned} 𝑠^{2} & \equiv 1 mod 𝑛 \\ 𝑠^{2} - 1 & \equiv 0 mod 𝑛 \\ (𝑠 - 1) (𝑠 + 1) & \equiv 0 mod 𝑛 \end{aligned}

Now we have two factors of $𝑛$ , we can further make use GCD to determine the prime factors,

gcd (𝑠 + 1, 𝑛) and gcd (𝑠 - 1, 𝑛)

This is because for each prime $𝑝_{𝑖} | 𝑛$ , since $𝑠^{2} mod 𝑝_{𝑖} \equiv 1$ , $𝑠 mod 𝑝_{𝑖}$ is either $\pm 1$ .

If $𝑠 \equiv 1 mod 𝑝_{𝑖}$ , then $𝑝_{𝑖} | (𝑠 - 1)$
If $𝑠 \equiv - 1 mod 𝑝_{𝑖}$ , then $𝑝_{𝑖} | (𝑠 + 1)$

So, $gcd (𝑠 + 1, 𝑛)$ will be the product of all $𝑝_{𝑖} | (𝑠 - 1)$ , while $gcd (𝑠 - 1, 𝑛)$ will be the product of all $𝑝_{𝑖} | (𝑠 + 1)$ .

Since we can split $𝑛$ into two composite factors, by repeating this process we but instead taking the gcd against the composite factors of n, we can factorize $𝑛$ into its 10 prime factors.

In the ideal case, we would need ${log}_{2} (10) \approx 4$ queries to fully factor $𝑛$ . So accounting for randomness we can expect to factor $𝑛$ within 8-12 queries.

15.2.1. The Edge Case

You may notice that if $𝑠^{2} = 1$ , i.e. $𝑥^{2} \equiv 𝑦^{2} mod 𝑛$ then this won’t work.

This doesn’t matter much as we can prove that it is quite rare that $𝑥^{2} \equiv 𝑦^{2} mod 𝑛$ by looking at the code of the square root oracle.

Since the square root oracle takes the square root of our input modulo each prime factor.

For each prime factor $𝑝_{𝑖}$ , $𝑎^{2}$ would have two roots $\pm 𝑎 mod 𝑝$ .

When we combine these via CRT, there are $2^{10} = 1024$ possiblities of $𝑦^{2} mod 𝑛$

So there is a $\frac{1}{1024} \approx 0.1 %$ chance that $𝑦^{2} \equiv 𝑥^{2} mod 𝑛$

16. Decrypting the flag

As we said earlier, $𝜑 (𝑛) = (𝑝_{1} - 1) (𝑝_{2} - 1) \dots (𝑝_{10} - 1)$ .

We just need to compute $𝑑 \equiv 𝑒^{- 1} mod 𝜑 (𝑛)$ .

Then we can trivially decrypt the flag with

𝑚 = 𝑐^{𝑑} mod 𝑛