Fractional RSA
COMP2633 Wk8 HwB

1. Preface

Challenge authored by Tom Yueng, Firebird Core member.

14 solves. First blood in 24 minutes.

2. Analysis

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

• A public key , where the product of two large distinct primes and is an integer coprime to .

• Encryption

• Decryption, where is the modular inverse of

• is the number of integers smaller than n that are coprime to it. For , we can show that .

However, in this challenge:

• is the product of 10 distinct primes, each 256 bits.
• The public exponent is set to .
• We are given the ciphertext , where is the flag.

• The server offers an oracle with two operations:

  1. Encrypt with , i.e returns .
  2. Decrypt with , i.e returns .

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

3. The Vulnerability

RSA depends on being difficult to factor, thus it is difficult to compute and you cannot determine for decryption.

However, if we have all the 10 factors,

Then we know that,

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

4. The Attack Vector

4.1. Step 1: Recover N

The encryption oracle computes , so for large random :

Thus we can compute for several random .

Then take the to recover .

This is because will likely be different for each .

If , then .

4.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 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 .
• Query the oracle for the decryption of

Why query the oracle for decryption?

Encryption with means .

So instead when we input , then .

Let , then we know that . And further,

Let , then

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

This is because for each prime , since , is either .

• If , then
• If , then

So, will be the product of all , while will be the product of all .

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 queries to fully factor . So accounting for randomness we can expect to factor within 8-12 queries.

4.2.1. The Edge Case

You may notice that if , i.e. then this won’t work.

This doesn’t matter much as we can prove that it is quite rare that 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 , would have two roots .

When we combine these via CRT, there are possiblities of

So there is a chance that

5. Decrypting the flag

As we said earlier, .

We just need to compute .

Then we can trivially decrypt the flag with