# SharifCTF 7 – Unterscheide

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()

1. Generates a random key $R$, and encrypts the flag $f$ via AES using this key (and a similarly random IV, also part of $R$) to get the encrypted flag $f_{enc}$.
2. The encryption algorithm also has access to a secret prime $q$; we are told in the assertion that the totient $\phi(q) = q-1$ of $q$ has two prime factors $p_1$ and $p_2$, who are within $10^8$ of each other (we originally misread this assertion as asserting that they are at least $10^8$ far away from each other; this cost us some time.). The algorithm is also given an element $h$ of $\mathbb{Z}/q\mathbb{Z}$ whose order is not divisible by $p_1$ or $p_2$.
3. For the $i$th bit $b_i$ in $f_{enc}$, output a number of the form $(h^{r^2p_1} \bmod q)q(R+i) + (R+i) + 1$ if $b=0$ and a number of the form $(h^{s^2p_2} \bmod q)q(R+i) + (R+i) + 1$ if $b=1$, where $r$ and $s$ are a randomly generated prime and its inverse (really, all that matters is that they are relatively prime to $p_1$ and $p_2$, though). Let $m_i$ equal the power of $h$ modulo $q$ generated in this step.

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

1. To start, note that $a_{i} - a_{i-1} - 1 = (k_i(R+i) - k_{i-1}(R+(i-1))q$ is divisible by $q$. Therefore, $q$ divides (and probably equals) the GCD of all of these numbers. We can check that we have the correct $q$ by checking that $q$ is prime.
2. Next, note that if we have $q$, we can recover $R$ modulo $q$ by computing $(a_0 - 1) \bmod q$. It turns out that $R < q$, so this is the true value of $R$; we can check this by verifying that $(R+i)$ divides $a_i - 1$ for all $i$.
3. To find $p_1$ and $p_2$, we first factor out all small primes from $q-1$; it turns out the only small prime dividing $q-1$ is $2$, and in fact $q = 2p_1p_2 + 1$. We are left with a semiprime whose two factors $p_1$ and $p_2$ are within $10^8$ of each other; we can factor this and retrieve these primes by doing trial division starting at the integer square root of this semiprime.
4. Finally, instead of finding $h$ (which would require solving some tricky discrete log problem), we will directly compute which of the two cases $a_i$ was generated in via the following observation; if $b_i = 0$ and $m_i = h^{r^2p_1} \bmod q$, then $m_i^{2p_2} \equiv h^{r^2\phi(q)} \equiv 1 \bmod q$; likewise, if $b_i = 1$, then $m_i^{2p_1} \equiv h^{s^2\phi(q)} \equiv 1 \bmod q$ (by Fermat’s little theorem). We can therefore compute $b_i$ by raising $m_i$ to both of these powers modulo $q$ and seeing which computation results in $1$. Note that we don’t know which of $p_1$ or $p_2$ was originally which, so we may have to invert the bits $b_i$ that we get.
5. From the $b_i$s and $R$, 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}**