0ctf - DoubleRSA

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:

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 by

  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 bobs 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.