Tags: rsa 

Rating:

# Lost key (crypto, 334p, 10 solved)

Unfortunately we were unable to finish this task, but we managed to get the first part - recovery of `N`, and just for future reference we're include this part in a writeup.

## Overview

In the task we get [source code](chall.py).
We can connect to a service and we get back RSA encrypted flag.
We can also send our own payload and get it encrypted as well.
Our payload has restricted length and always includes prefix `X: `.

## General approach

The general method for recovering `N` in such case, is to obtain some multiples of `N` and calcuate their GCD.
If we had total control over the payload we could simply ask for encryption of `A` and of `A^2` and calculate `(A^e mod N)^2 - ((A^2)^e mod N)`.
Such difference, by definition, has to be a multiple of `N`, because you can shift the exponentiation order and move modulo:

```
(A^e mod N)^2 mod N = (A^e)^2 mod N = (A^e mod N)^2 mod N = (A^e)^2 mod N = (A^2)^e mod N`
```

So if we apply `mod N` to `(A^e mod N)^2` we should get the same value as in `((A^2)^e mod N)` therefore it has to be `((A^2)^e mod N) + k*N` and if we subtract `((A^2)^e mod N)` we'll get plain `k*N`.

However, we don't control the payload so much, it has the prefix!

## Modulus recovery

The idea for modulus recovery is just as above - we want to get from the server a pair of different ciphertexts which `mod N` would have the same value.
Subtracting them will yield `k*N`.

We are going to leverage homomorphic property of textbook RSA:

```
A^e mod N * B^e mod N = (A*B)^e mod N
```

Let's assume we have 4 different values such that: `A*B = C*D` and each of those values is a valid plaintext with the appropriate prefix.

If we encrypt those values separately with textbook RSA and combine them the property will still hold, so:

```
(A^e mod N * B^e mod N) mod N = (A*B)^e mod N
(C^e mod N * D^e mod N) mod N = (C*D)^e mod N

and since

A*B = C*D

then

(A*B)^e mod N == (C*D)^e mod N
```

However, the values `(A^e mod N) * (B^e mod N)` and `(C^e mod N) * (D^e mod N)` without applying the `mod N` operation on the product will not be the same!

This is exactly the property we're looking for.
So the goal is to find values `A, B, C, D` we could use.

The idea we came up with is to create each one of them as a combination of 2 other values in a way that:

```
A = x*y
B = z*v
C = x*v
D = y*z
```

This way obviously `A*B = x*y*z*v = C*D`.

Now we need to make sure each of the values matches the prefix.
In order to do that we figured we can factor the prefix into primes, and then create `x,y,z,v` as combination of some factors, so that each of `A, B, C, D` will contain full set of factors.

Of course values `A, B, C, D` have to be different, so we need to include also some random padding at the end of each of them:

```python
prefix = bytes_to_long("X: ")
factors, _ = factor(prefix)
random.shuffle(factors)
base1 = multiply(factors[:len(factors) / 2])
base2 = multiply(factors[len(factors) / 2:])
assert base1 * base2 == prefix
```

Now with those base values we can do:

```python
shift = 5
x = base1 * 256 ** shift + 0
y = base2 * 256 ** shift + 0
z = base1 * 256 ** shift + 1
v = base2 * 256 ** shift + 1

A = x * y
B = z * v
C = x * v
D = y * z
assert (A * B == C * D == x * y * z * v)
```

And we have the plaintexts we wanted.
Now we just need to encrypt them and calculate `(CTA * CTB) - (CTD * CTC)` to get a multiple of `N`.

After that the only thing left is to calculate gcd over those values to recover `N`: `28152737628466294873353447700677616804377761540447615032304834412268931104665382061141878570495440888771518997616518312198719994551237036466480942443879131169765243306374805214525362072592889691405243268672638788064054189918713974963485194898322382615752287071631796323864338560758158133372985410715951157`

This value can easily be factored into:

```
p = 531268630871904928125236420930762796930566248599562838123179520115291463168597060453850582450268863522872788705521479922595212649079603574353380342938159
q = 52991530070696473563320564293242344753975698734819856541454993888990555556689500359127445576561403828332510518908254263289997022658687697289264351266523
```

Unfortunately we were unable to recover `e` and finish the challenge.
Solver for the described part is [here](modulus.py)

We only managed to come up with an idea that calculating modular sqrt can tell us the LSB of `e`, and it worked, we know it's a odd number :)

Original writeup (https://github.com/p4-team/ctf/tree/master/2019-10-12-hitcon/lost_key).