crypto_caulingo

Crypto Caulingo

Description

Well you've done it, you're now an admin of the Cookie World Order. The clandestine organisation that seeks to control the world through a series of artfully placed tasty treats, bringing folks back in to their idea of what a utopian society would look like. Strangely enough, the webcam data is being fed to understand the properties of the entities you had originally seen. They seem to be speaking back into the camera (an unadvertised microphone) but it's hard to understand what they want. You must- if nothing else ever was important in your life, you must make contact with these beautiful creatures! Also, what exactly is a "cauliflower"?

Attachment

Solution

The zip file contains two files msg.txt and project_dc.pdf. The msg.txt contains an encrypted message as well as some RSA parameters (n and e). The pdf describes how the values p and q were chosen:

| A * P | - | B * Q | <= 10'000

The absolute difference of A * P and B * Q is less than 10'000. A and B are both smaller than 1'000. Rewriting the equation from above gives:

A * p = B * q
= A / B * p = q
= A / B = q / p
= A / B = q / (n / q)
= A / B = q^2 / n
= A * n / B = q^2

Note that both sides are only equal with an error of 10'000. Taking the square root on both sides reduces the error to sqrt(10'000) which is 100.

Now we can enumerate all values of A and B and calculate q as sqrt(A * n / B):

n = 17450892350509567071590987572582143158927907441748820483575144211411640241849663641180283816984167447652133133054833591585389505754635416604577584488321462013117163124742030681698693455489404696371546386866372290759608301392572928615767980244699473803730080008332364994345680261823712464595329369719516212105135055607592676087287980208987076052877442747436020751549591608244950255761481664468992126299001817410516694015560044888704699389291971764957871922598761298482950811618390145762835363357354812871474680543182075024126064364949000115542650091904557502192704672930197172086048687333172564520657739528469975770627

for a in range(1, 1000):
  for b in range(1, 1000):
    q0 = isqrt(n * a / b)

    for diff in range(-100, 100):
       q = q0 + diff
       p = n // q
       if (p * q == n):
          print (p, q)
       

After a few minutes we find valid values for p and q:

(151086174643947302290817794140091756798645765602409645643205831091644137498519425104335688550286307690830177161800083588667379385673705979813357923016141205953591742544325170678167010991535747769057335224460619777264606691069942245683132083955765987513089646708001710658474178826337742596489996782669571549253, 115502906812186413716028212900548735990904256575141882752425616464266991765240920703188618324966988373216520827723741484031611192826120314542453727041306942082909556327966471790487878679927202639569020757238786152140574636623998668929044300958627146625246115304479897191050159379832505990011874114710868929959)

The following code decrypts the message:

public static void main(String[] args) {
    BigInteger p = new BigInteger("151086174643947302290817794140091756798645765602409645643205831091644137498519425104335688550286307690830177161800083588667379385673705979813357923016141205953591742544325170678167010991535747769057335224460619777264606691069942245683132083955765987513089646708001710658474178826337742596489996782669571549253");
    BigInteger q = new BigInteger("115502906812186413716028212900548735990904256575141882752425616464266991765240920703188618324966988373216520827723741484031611192826120314542453727041306942082909556327966471790487878679927202639569020757238786152140574636623998668929044300958627146625246115304479897191050159379832505990011874114710868929959");
    BigInteger n = new BigInteger("17450892350509567071590987572582143158927907441748820483575144211411640241849663641180283816984167447652133133054833591585389505754635416604577584488321462013117163124742030681698693455489404696371546386866372290759608301392572928615767980244699473803730080008332364994345680261823712464595329369719516212105135055607592676087287980208987076052877442747436020751549591608244950255761481664468992126299001817410516694015560044888704699389291971764957871922598761298482950811618390145762835363357354812871474680543182075024126064364949000115542650091904557502192704672930197172086048687333172564520657739528469975770627");
    BigInteger c = new BigInteger("50fb0b3f17315f7dfa25378fa0b06c8d955fad0493365669bbaa524688128ee9099ab713a3369a5844bdd99a5db98f333ef55159d3025630c869216889be03120e3a4bd6553d7111c089220086092bcffc5e42f1004f9888f25892a7ca007e8ac6de9463da46f71af4c8a8f806bee92bf79a8121a7a34c3d564ac7f11b224dc090d97fdb427c10867ad177ec35525b513e40bef3b2ba3e6c97cb31d4fe3a6231fdb15643b84a1ce704838d8b99e5b0737e1fd30a9cc51786dcac07dcb9c0161fc754cda5380fdf3147eb4fbe49bc9821a0bcad98d6df9fbdf63cf7d7a5e4f6cbea4b683dfa965d0bd51f792047e393ddd7b7d99931c3ed1d033cebc91968d43f", 16);

    decrypt(q, p, n, c);
}

private static void decrypt(BigInteger p, BigInteger q, BigInteger n, BigInteger c) {
    BigInteger z = p.subtract(new BigInteger("1"))
            .multiply(q.subtract(new BigInteger("1")));

    BigInteger e = new BigInteger("2").pow(16).add(new BigInteger("1"));
    BigInteger d = e.modInverse(z);

    System.out.println(new String(c.modPow(d, n).toByteArray()));
}

Running it prints:

Hey there!

If you are able to decrypt this message, you must a life form with high intelligence!

Therefore, we would like to invite you to our dancing party! 

Here???s your invitation code: CTF{017d72f0b513e89830bccf5a36306ad944085a47}

Therefore the flag is CTF{017d72f0b513e89830bccf5a36306ad944085a47}.