Lost (crypto)

Do you know the feeling of losing a part of you !!

The encryption code is given below.

from random import getrandbits
from Crypto.Util.number import getPrime, bytes_to_long
from SECRET import FLAG

e = 2
p = getPrime(256)
q = getPrime(256)
n = p * q

m = bytes_to_long(FLAG)
cor_m = m - getrandbits(160)

if __name__ == "__main__":
    c = pow(m, e, n)
    print("n = {}\nc = {}\ncor_m = {}".format(n, c, cor_m))
    
# n = 5113166966960118603250666870544315753374750136060769465485822149528706374700934720443689630473991177661169179462100732951725871457633686010946951736764639
# c = 329402637167950119278220170950190680807120980712143610290182242567212843996710001488280098771626903975534140478814872389359418514658167263670496584963653
# cor_m = 724154397787031699242933363312913323086319394176220093419616667612889538090840511507392245976984201647543870740055095781645802588721

This challenge involves the Coppersmith attack. The flag is converted into a number m, and encrypted using pow(m, e, n) (which is RSA). We then generate 160 random bits, and subtract this from m to obtain cor_m.

Next, we observe that cor_m is 441 bits long. Expressing m as $m = b_nb_{n-1}...b_1b_0$, if we have a $b_i$ where $i >= 160$ that is 1, then for the smallest $i$ that fulfils this criteria, $b_nb_{n-1}b_{n-2}...b_{i + 1}$would be the same in m and cor_m.

Hence cor_m should give us the unchanged leftmost 200+ bits of m. Indeed, when we rightshift cor_m by 176 bits, we get the first half of the message:

from Crypto.Util.number import long_to_bytes

# cor_m is 441 bits long
n = 5113166966960118603250666870544315753374750136060769465485822149528706374700934720443689630473991177661169179462100732951725871457633686010946951736764639
c = 329402637167950119278220170950190680807120980712143610290182242567212843996710001488280098771626903975534140478814872389359418514658167263670496584963653
cor_m = 724154397787031699242933363312913323086319394176220093419616667612889538090840511507392245976984201647543870740055095781645802588721

print(long_to_bytes(cor_m >> 176)) # AKASEC{c0pp3r5m17h_4774ck_1n_1ov3
print(len(long_to_bytes(cor_m >> 176))) # 33

We now know the first half of the code, and we can successfully use the Coppersmith attack to retrieve the entire flag. Since I didn't know the length of the flag, I tried a range of lengths. Below is the full solve script (in sage):

from Crypto.Util.number import long_to_bytes, bytes_to_long
from sage.all import *
from tqdm import tqdm

e,N = (2, 5113166966960118603250666870544315753374750136060769465485822149528706374700934720443689630473991177661169179462100732951725871457633686010946951736764639)

c = 329402637167950119278220170950190680807120980712143610290182242567212843996710001488280098771626903975534140478814872389359418514658167263670496584963653

for flag_length in tqdm(range(20, 30)):
    m = bytes_to_long(b'AKASEC{c0pp3r5m17h_4774ck_1n_1ov3' + (flag_length) * b'\x00')
    P.<x> = PolynomialRing(Zmod(N), implementation='NTL')
    pol = (m + x)^e - c
    roots = pol.small_roots(epsilon=1/20)
    print("Potential solutions:")
    for root in roots:
        print(long_to_bytes(int(m+root))) 
# AKASEC{c0pp3r5m17h_4774ck_1n_1ov3_w17h_5m4ll_3xp0n3nts}