# Dynamic RSA

## Overview

### Original Version

The server generates two $200$-bits primes and encrypts the flag $m$ by $$c = m^{65537} \pmod{n}$$ Unlike standard RSA, we are only given $c$ and other two operations to do.

1. For our input $d$, the server returns the value $c^d \pmod{n}$ and terminate the process.
2. For any input $s$, produce a encryption key $\bar{e}$ and give us $s^{\bar{e}} \pmod{n}$. Moreover, the least significant bits of quotients in Euclidean GCD are leaked.

Note that the seed for random is fixed, so the encryption key is known.

### Updated

As the original problem can be solved without using leaked LSBs ... Authors decided to add random number to the input $s$.

## Exploit

### Unique Residue (Intended)

Key Observation. **There are at most $2 * p$ different LSB sequences for $gcd(p, a)$**

:::success
By definition, $gcd(p, a)$ = (0 or 1) + $gcd(a \% p, p)$. Now, as there are only $p$ possible values of $a \% p$, the conclusion follows.
:::

Hence, we may expect some LSB sequences uniquely determince the residue of $\phi(n)$ divided by $p$. Here is a simple experiment for justification.

| Prime $p$ | Unique LSB Sequences $k$ | Ratio $\frac{k}{2p}$ |
|:-----:|:-----:|:-----:|
| 37 | 20 | 0.270 |
| 97 | 68 | 0.351 |
| 239 | 86 | 0.180 |
| 431 | 146 | 0.169 |
| 599 | 178 | 0.149 |
| 1543 | 398 | 0.129 |
| 2179 | 490 | 0.112 |
| 5749 | 922 | 0.080 |
| 12239 | 1852 | 0.076 |
| 30253 | 3884 | 0.064 |

Although the ratio becomes smaller when the modulus becomes larger, it's enough for us to solve this problem. We query the oracle and check whether the LSB sequence uniquely determine the residue of $\phi$ divided by the encryption key. After collecting enough pairs of primes and residues, we can apply CRT to recover $\phi(n)$.

from pwn import *
import random
from sympy import *
from Crypto.Util.number import *

def conn():

	c = remote("litctf.live", 31792)
	return c

def gcd(a, b, res = ""):
	if(a == 0):
		return res;
	if(b == 0):
		return res;
	res += ".,"[(b // a) & 1]

	return gcd(b % a, a, res);

def get_phi(c):

	random.seed(65537)
	P = 1
	primes = []
	residues = []
	for i in range(5000):
		test_e = nextprime(random.randint(1, 100000))
		c.sendline("2")
		c.recvuntil("Loading")
		_ = c.recvline().decode().strip()
		res = []
		for r in range(test_e + 1, 2 * test_e + 1):
			if gcd(test_e, r) == _:
				res += [r % test_e]
		if len(res) == 1 and test_e not in primes:
			P *= test_e
			primes += [test_e]
			residues += [res[0]]
			print("+")
			print(P.bit_length())
		c.sendline("1")

		if P.bit_length() > 400:
			print("enough")
			break

	phi = 0
	for p, r in zip(primes, residues):
		phi += r * pow(P//p, -1, p) * (P//p) % P
		phi %= P
	
	for p, r in zip(primes, residues):
		assert phi % p == r

	return phi

def solve(c, phi):

	c.sendline("1")
	d = pow(65537, -1, phi)
	c.sendline(str(d))
	c.interactive()

c = conn()
phi = get_phi(c)
solve(c, phi)

### Broadcast Attack (Unintended)

At first glance, because the flag is encrypted by multiple RSA, I came up with Hastad Broadcast. Then the only thing we need is to recover the modulus. There are two ways to find out $n$

1. *Common Aprroach. Find multiples of modulus and take GCD of them*

As the range of possible encrpytion keys is small, it's very likely to have duplicate keys. Then we query the oracle to get $2^{\bar{e}} \pmod{n}, 4^{\bar{e}} \pmod{n}$, and compute a multiple of $n$: $$(2^{\bar{e}} \pmod{n})^2 - 4^{\bar{e}} \pmod{n}$$

2. *Be Lucky. Get only one multiple of modulus and drop small factors*

This perhaps works for updated version, we don't even use the second operation! Just ask the server to compute $c^{2} \pmod{n}$. Again, $(c \pmod{n})^{2} - c^2 \pmod{n}$ is multiple of $n$. After dropping small factors, we can check whether it's indeed phi by its bit size.

Remark. This solution will make too many connections to server, so it just conceptual solution.