This was an unusual sort of crypto challenge, and it probably gave us more trouble than it should have (partially because we failed at understanding an assert statement in the code; oops!).

In this challenge, they give us the python implementation of an algorithm that encrypts the flag as follows:

#!/usr/bin/python import gmpy import random, os from Crypto.Util.number import * from Crypto.Cipher import AES from secret import flag, q, p1, p2, h assert (gmpy.is_prime(q) == 0) + (q-1) % p1 + (q-1) % p2 + (p2 - p1 > 10**8) + (pow(h, 1023*p1*p2, q) == 1) == 0 key = os.urandom(128) IV = key[16:32] mode = AES.MODE_CBC aes = AES.new(key[:16], mode, IV=IV) flag_enc = aes.encrypt(flag) rand = bytes_to_long(key) benc = bin(bytes_to_long(flag_enc))[2:] A = [] for b in benc: try: r = gmpy.next_prime(random.randint(3, q-2)) s = gmpy.invert(r, q-1) if b == '0': a = pow(h, r*r*p1, q)*q*rand + rand + 1 else: a = pow(h, s*s*p2, q)*q*rand + rand + 1 A.append(str(int(a))) rand += 1 except: print 'Failed' fenc = open('enc.txt', 'w') fenc.write('\n'.join(A)) fenc.close()

- Generates a random key , and encrypts the flag via AES using this key (and a similarly random IV, also part of ) to get the encrypted flag .
- The encryption algorithm also has access to a secret prime ; we are told in the assertion that the totient of has two prime factors and , who are within of each other (we originally misread this assertion as asserting that they are at least far away from each other; this cost us some time.). The algorithm is also given an element of whose order is not divisible by or .
- For the th bit in , output a number of the form if and a number of the form if , where and are a randomly generated prime and its inverse (really, all that matters is that they are relatively prime to and , though). Let equal the power of modulo generated in this step.

To break this cryptosystem, we’ll try to recover the many parameters one by one.

- To start, note that is divisible by . Therefore, divides (and probably equals) the GCD of all of these numbers. We can check that we have the correct by checking that is prime.
- Next, note that if we have , we can recover modulo by computing . It turns out that , so this is the true value of ; we can check this by verifying that divides for all .
- To find and , we first factor out all small primes from ; it turns out the only small prime dividing is , and in fact . We are left with a semiprime whose two factors and are within of each other; we can factor this and retrieve these primes by doing trial division starting at the integer square root of this semiprime.
- Finally, instead of finding (which would require solving some tricky discrete log problem), we will directly compute which of the two cases was generated in via the following observation; if and , then ; likewise, if , then (by Fermat’s little theorem). We can therefore compute by raising to both of these powers modulo and seeing which computation results in . Note that we don’t know which of or was originally which, so we may have to invert the bits that we get.
- From the s and , we can decrypt the AES encoded flag, and obtain the original flag.

Here is some python code implementing this solution:

from Crypto.Util.number import * from Crypto.Cipher import AES def isqrt(n): x = n y = (x + 1) // 2 while y < x: x = y y = (x + n // x) // 2 return x A = map(int, [line for line in open('enc.txt')]) # find q qmults = [A[i]-A[i-1]-1 for i in xrange(1, len(A))] q = qmults[0] for qmult in qmults[1:]: q = GCD(q, qmult) assert isPrime(q) # find initial value of rand rand = A[0]%q - 1 assert all([(A[i]-1)%(rand+i) == 0 for i in xrange(len(A))]) # find p1 and p2 semip = (q-1)/2 # turns out phi(q) has no small prime factors besides 2 ind = 1 st = isqrt(semip) while ind < 10**8: if semip%(st+ind) == 0: p1, p2 = st+ind, semip/(st+ind) ind = 10**8 ind += 1 # distinguish b=0 case from b=1 case modpows = [(a-rand-i-1)/(q*(rand+i)) for i, a in enumerate(A)] def get_bit(mpow): if pow(mpow, 2*p1, q) == 1: return 0 elif pow(mpow, 2*p2, q) == 1: return 1 else: assert False benc = [get_bit(mpow) for mpow in modpows] # decrypt everything lenc = sum([b*(2**i) for i, b in enumerate(reversed(benc))]) flag_enc = long_to_bytes(lenc) key = long_to_bytes(rand) aes = AES.new(key[:16], AES.MODE_CBC, IV=key[16:32]) flag_dec = aes.decrypt(flag_enc) print flag_dec # ** SharifCTF{10ED2D76BCC417D9C48BE67F6790AF70}**

Advertisements