# Single Hint RSA

- Status: solved and submitted
- Flag: `tkbctf{I_do_understand_the_risk_of_leaking_plaintext_by_giving_additional_information_in_the_RSA_and_really_want_to_provide_n%m}`

## Challenge

The generator leaks:

```python
n = p * q
c = pow(m, e, n)
hint1 = n % m
```

Let:

```text
n = k * m + hint1
```

for some small quotient `k`. Since the plaintext is 120 bytes and `n` is 1024 bits, `k` is about 64 bits.

From `m = (n - hint1) / k` and `c = m^e mod n`, we get:

```text
((n - hint1) / k)^e ≡ c (mod n)
(-hint1)^e ≡ c * k^e (mod n)
c * k^e + hint1^e ≡ 0 (mod n)
```

So `k` is a small modular root of:

```text
f(x) = c*x^e + hint1^e  mod n
```

Because `k < n^(1/e)`, Coppersmith's small-roots method recovers it directly.

## Reproduction

```bash
sage -c '
n=106355772659701345964318417143394651063207428456215453439002897507959529597434886809900091569966425277511938767801980714938398649158388112317710373391834663525304231863666383091470134532442609738641279822679588058405512137402630292338680201169977752096539561076464502681405533276738762606253695333486635300117
e=11
c=57709889892302481730604978456569407865866089984321485829668848041279746593625646867358726055884587571542026961018063222927783667255209992837359953872022080880950318593445249622351520650827684714014441718458985647744543454058728562449684598363921005049148443778614680659575826505490809066816806157858025523873
h=54090058252804218553770902127609841718548664220987085177964232538368049188447317574459229022955503639171581148196516877285398714054794498098761794789311951957865082652646501644947370300536353612069166697135782197061383589516041765932064632491262789467798239447500141545602675069866142902
R=Zmod(n); P.<x>=PolynomialRing(R)
a=(h^e)*inverse_mod(c,n)
print((x^e + a).small_roots(X=2^80, beta=0.4))
'
```

This returns:

```text
[38077737063170302331]
```

Then recover the plaintext:

```bash
python3 - <<'PY'
from Crypto.Util.number import long_to_bytes
n=106355772659701345964318417143394651063207428456215453439002897507959529597434886809900091569966425277511938767801980714938398649158388112317710373391834663525304231863666383091470134532442609738641279822679588058405512137402630292338680201169977752096539561076464502681405533276738762606253695333486635300117
h=54090058252804218553770902127609841718548664220987085177964232538368049188447317574459229022955503639171581148196516877285398714054794498098761794789311951957865082652646501644947370300536353612069166697135782197061383589516041765932064632491262789467798239447500141545602675069866142902
k=38077737063170302331
m=(n-h)//k
print('tkbctf{' + long_to_bytes(m).decode() + '}')
PY
```