Story
Adleman resigned from his job and left his documents in a locker. He had kept a secret password to open it.
He has sent some files to his co-workers and it contains the crucial information to identify the password.
Help the team to recover the password.
Solution
In the challenge, we get encryption code, encrypted flag, encrypted private key and encrypted public key.
The code is quite short and simple:
RSA key pair is generated in some secret way
Private RSA key is encrypted via AES-ECB
The flag is encrypted using public RSA key
Public key is encrypted using some online encrypter.
The goal seems clear - we need to somehow recover the private key from the public key and the AES-encrypted version of the private key.
For RSA decryption we need four parameters - ciphertext, d, prime factors p and q, and n. Since none of the values is provided we have to find those values.
From the question itself, it is clear that the password for decrypting the public key file is “Adleman”. The public key consists of two values n and e which can be extracted using the following code snippet.
public_key = RSA.importKey(open('pub.der', 'rb').read())
print(public_key.n)
print(public_key.e)
N = public_key.n
If we look closely at the private key, we can notice a very strange pattern at a certain point:
CB A7 07 94 26 F1 DE 69 2C 7D 73 38 81 D6 61 E4
4F F4 62 2D 73 17 72 84 BD 31 7B CB B9 2F C7 CC
CB A7 07 94 26 F1 DE 69 2C 7D 73 38 81 D6 61 E4
4F F4 62 2D 73 17 72 84 BD 31 7B CB B9 2F C7 CC
CB A7 07 94 26 F1 DE 69 2C 7D 73 38 81 D6 61 E4
4F F4 62 2D 73 17 72 84 BD 31 7B CB B9 2F C7 CC
CB A7 07 94 26 F1 DE 69 2C 7D 73 38 81 D6 61 E4
4F F4 62 2D 73 17 72 84 BD 31 7B CB B9 2F C7 CC
CB A7 07 94 26 F1 DE 69 2C 7D 73 38 81 D6 61 E4
4F F4 62 2D 73 17 72 84 BD 31 7B CB B9 2F C7 CC
CB A7 07 94 26 F1 DE 69 2C 7D 73 38 81 D6 61 E4
4F F4 62 2D 73 17 72 84 BD 31 7B CB B9 2F C7 CC
CB A7 07 94 26 F1 DE 69 2C 7D 73 38 81 D6 61 E4
4F F4 62 2D 73 17 72 84 BD 31 7B CB B9 2F C7 CC
CB A7 07 94 26 F1 DE 69 2C 7D 73 38 81 D6 61 E4
The private key is encrypted using AES ECB mode in which identical plain text blocks are encrypted using identical ciphertext blocks. We can notice that this particular piece of data falls into place where the first prime factor should be, plus-minus few bytes in the block before and block after.
This means that the prime factor has to have such a repeating pattern and the prime has to be something like X ABCD ABCD ABCD … Y.
We could also write this down as ABCD * 0x10001000… + S where S is the unknown part located in the non-repeating blocks.
And the pattern we obtained is
pattern = 0x10000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001
For now we have the value of n ,
N = p*q
p = k*pattern+S
Then,
N = p*q = (k*pattern+S)*q = k*pattern*q + S*q
N - S*q = k*pattern*q
(N-S*q)/pattern = k*q
Now let’s introduce a polynomial f(x) = (N-x)/pattern. From the above equation it’s clear that for x0 = S*q this polynomial reduces to 0 mod q because it would be a multiple of q. We also know that q is a factor of N.
However, we can’t directly use Coppersmith method here, because S*q is actually very big, it’s bigger than one of the factors, so at least N^1/2 and Coppersmith bound for this case would allow for finding roots about N^1/4.
But we can go one step further and make an approximation:
(N-S*q)/pattern ~= N/pattern - (S*q/pattern)
Now we can re-formulate the polynomial to f(x) = N/pattern - x, and since we’re now looking for x0 = (Sq/pattern) the bound for the root is, in fact, close to Sk, which we can hope is small.
We can look at this via a simple sanity check:
p = getPrime(2048)
k = random.randint(2 ** 255, 2 ** 256)
pattern = 0x10000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001
q = gmpy2.next_prime(k * pattern + random.randint(0, 2 ** 256))
S = q - k * pattern
N = p * q
print(math.log(N // pattern - k * p, 2))
This shows us that with this setup the root we would be looking for is about 512 bits long.
The solver for this problem is as described above:
def solve(N, pattern):
F.<x> = PolynomialRing(Zmod(N), implementation='NTL')
poly = x - N//pattern
roots = poly.small_roots(beta=0.4, X=2**600)
for root in roots:
val = root - N//pattern
q0 = gcd(N,val)
if q0 > 1:
print(int(root).bit_length())
print('q',q0)
print('p',int(N)//int(q0))
print(hex(int(N)//int(q0)))
return True
We will get the p and q value from this code.
There was one more thing to consider - the pattern might be shifted, since the blocks are not perfectly aligned. We don’t really know where is the first 1, so we check the shifts as well:
pattern = 0x10000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001
for i in range(16):
N = ...
if solve(N,pattern):
print(hex(pattern))
pattern >>=8
Now we have all the values required for decryption using RSA. Giving the p and q values to the following code will generate a flag.
p =
q =
e = 65537
def extended_gcd(a, b):
lastremainder, remainder = abs(a), abs(b)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient * x, x
y, lasty = lasty - quotient * y, y
return lastremainder, lastx * (-1 if a < 0 else 1), lasty * (-1 if b < 0 else 1)
def modinv(e, phi):
g, x, y = extended_gcd(e, phi)
if g != 1:
raise ValueError
return x % phi
# find the decryption key d.
d = modinv(e, (p - 1) * (q - 1))
data = open("flag.enc", 'rb').read()
print(long_to_bytes(pow(bytes_to_long(data), d, p * q)))
b’{Unb0x th1s f0r y0ur fl4g,juskizl{XSeVsIFDmAWoiK7BkUjrEI7zLCYYnERL}}’
Now juskizl{XSeVsIFDmAWoiK7BkUjrEI7zLCYYnERL} should be decrypted for the actual flag. It is clear that some substitution cipher is used and the pattern will consist of capital and small letters. Leaving the numbers behind apply a monoalphabetic substitution cipher to the random value obtained. As we know that juskizl will be domectf, we can actually figure out substitution used which is a monoalphabetic substitution cipher with a shift of 6 positions. And the final flag is:
domectf{RMyPmCZXgUQicE7VeOdlYC7tFWSShYLF}
