An RSA challenge where the encryption is performed by both Alice and Bob with some extra noise, and we have different information on each one and some oracle calls. The solution relies on efficient DLP computation and some tricks to increase the success probability.

## Challenge Description

We have two main actors, `alice`

and `bob`

. After passing a simple proof of work, we are asked to provide two `512`

bit primes `p`

and `q`

, that will constitute the private key for `bob`

. `alice`

is instantiated at random, but we are given her public key `(alice.e, alice.n)`

; we are not given `bob.e`

, which is also random. Then an `lcg`

is generated and given to us. The secret is created and `alice`

encrypts it. Here we have our first oracle calls: on each call we send a plaintext which get noisy-encrypted by both `alice`

and `bob`

:

1
2
3
4
5
6
7

def noisy_enc(self, m, r = 1):
if r:
self.refresh()
return pow(m, self.e ^ self.l.next(), self.n)
def refresh(self):
self.e = (self.e ^ self.l.next()) % (2**E_BITS)

This also updates the `lcg`

, which is shared among `bob`

and `alice`

. We are then given the `ciphertext`

. After this we are given `bob.noisy_enc(secrets_ct)`

, where `secrets_ct`

is the `alice`

encrypted secret. Here notice that `e`

is updated any time, but `d`

is not. After this, `lcg`

is reset and sent to us again, and the `e`

of `bob`

is generated again. Then we have a second oracle, to which we send a ciphertext, `alice`

decrypts it and `bob`

noisy encrypts it. Finally we are asked the original `secret`

to get the flag.

## Solution

The main idea is that we need to use encryptions of known plaintexts to recover `bob.e`

in both phases. We exploit the fact that we can encrypt as `alice`

, and hence we always know what is passed to `bob`

. Anyway, recovering `e`

requires a dlp, so we need to make sure `p`

and `q`

are smooth. The solution works as follows:

- first we generate two \(2^{40}\)-smooth primes, to be sure we can solve the dlp in
`Zmod(n)`

; - here come the first small trick (huge thanks to maple3142): calling
`pari.addprimes(p)`

and`pari.addprimes(q)`

we tell`sage`

how to factor`n`

through all the execution, saving a lot of effort; - then we send a random plaintext, and since we know
`alice.e`

,`alice.n`

and`lcg`

we know how is it encrypted by`alice`

; - solving (efficiently due to smoothness) the dlp on the ciphertext we get, we know
`bob.e`

but only up to the multiplicative order of the plaintext; - since
`l.next()`

that is xored with`e`

is big, we can still recover the actual`e`

by1 2 3

M = Zmod(p*q)(pt).multiplicative_order() guess_k = round((l_res_2 - guess_e) / M) guess_bob = (guess_e + guess_k * M)

- we can compute the inverse of
`e`

using`lb = carmichael_lambda(p*q)`

; this has a slightly higher probability of success than`phi`

(there is no guarantee that`e`

has an inverse here) - if it works, we get
`bob`

encrypted secret and revert to`alice`

encrypted secret; - then we send it to the second oracle, and we get
`bob`

encrypted original secret; - do the same trick as before to get
`bob`

s new`e`

(here we use something we know how`alice`

will decrypt); - if it works (same caveat as before), we get the original secret and the flag.

The full solution script can be found here.