Dried Up Crypto (ictf Round 56)

RSA Branch and prune

Challenge Overview

In this CTF challenge, we are given the following encryption script:

from Crypto.Util.number import getPrime, bytes_to_long
from secrets import randbits

flag = b'ictf{REDACTED}'

p,q = getPrime(1024),getPrime(1024)
assert((p-1) % e != 0)
assert((q-1) % e != 0)
e = 0x10001

M1,M2 = randbits(1024) | randbits(1024) ,randbits(1024) | randbits(1024)

P,Q = p & M1, q & M2

n = p*q
c = pow(bytes_to_long(flag),e,n)

print(f"c = {c}")
print(f"n = {n}")
print(f"M1 = {M1}")
print(f"M2 = {M2}")
print(f"P = {P}")
print(f"Q = {Q}")

as well as the output:

c = 8727199524595926705764225400506509289328151131514216250729515468155056218121221736963201841068215034487098098953821401326608386786346273720157155314820322698467429532461275463492599870550737132469369170204135115917482423036582822051988921146256688643845978757358407310854847663288337574501668030413804655286776436934536537698538527143491308805754764317305745181888684722727299988112034122487006667085647945475968191154669980943257738894146053667458797138697522920065140999462467096217712503505631649242142240435841977317598886490888750486215707059341912936564463860839090693276780817194811851886409356689470673107532
n = 10644244264245763932368979306576292154978169307980875431845848585515469979129741395711953185867051023317557615618234242176875251628599522772285258093327797679006324429376013569137018200577185349745003553221219229088693373960547344593762243714560234819514388391843307341206257538676824211613659149855441367734883320000869003833119510179206721701295702803923970241717612194010327944659540526556778579813186112749725822081690619963415418470255547473934066594150396804785237389851791915432015775405773476289374397136777722281258153565989398760008739331917818507905928387120867159103459386796293552147742130942785387667101
M1 = 88914640319156584554519907036301003224288784208184838268121846462159927955700945270283676500515406136279062455494762039147468454696771001133686799200482356740310590971170822957938953133862391626427210893445970048978263432949487046574710938280744537191675594575399501647648365744088495505838716001393025318711
M2 = 80710645955732183961498834296041390466353463350909365967073721088344234170831463482355150027971590908133797348848447302046512581471517653450640672441875363390417692734403220383748851502073357434012901646484453882427070643197703826675885986584075167513954328971199897226577585871016371987052379150617824721747
P = 1454713629297571001528363141111343262783446611248718929759592692372410193692959981391616314247878825643517231716578815166717528906295323061858760318849863325461174191466111073232730195560930748935209775742509843564017912569158094461170983358891473208999861629367188907727554105902252420135214355007297361937
Q = 23026771663186153673881188958499640470803688134356820454731962008947492131018559717122163720894546472163872899425608926369661262023609393522302590736445675570962275851657015555698875694838166833166542306554507099577746272183034587942732263335474963112075217970257365953713038351465989425740093838238205086529

This is a classic RSA setup. We are given some partial information of the prime factors $p$ and $q$.

Recovering the prime factors

The encryption script generates two bit-masks $M_{1}$ and $M_{2}$. The bit-masks are generated by OR-ing two series of random bits:

M1 = randbits(1024) | randbits(1024)
M2 = randbits(1024) | randbits(1024)

Our hints are then generated by AND-ing the prime factors with the bit-masks:

P = p & M1
Q = q & M2

Because $M_{1}$ and $M_{2}$ are generated using OR, around 75% of the prime factors’ bits are leaked. The prime factors can be recovered using a branch-and-prune method. For this, we can utilize the implementation of the good old reliable https://github.com/jvdsn/crypto-attacks/.

p_part = PartialInteger(P, M1, bitlen)
q_part = PartialInteger(Q, M2, bitlen)
p, q = factorize_pq(n, p_part, q_part)

After recovering the prime factors, decryption is trivial.

ictf{4_p4r714l_1nf0rm4710n_r54_w17h0u7_l4771c35}

solve.sage

class PartialInteger:
    def __init__(self, value, mask, bits):
        self.v, self.m, self.bit_length = int(value), int(mask), bits
    def to_bits_le(self):
        return [str((self.v >> i) & 1) if (self.m >> i) & 1 else '?'
                for i in range(self.bit_length)]

def _branch_and_prune_pq(N, p, q, p_, q_, i):
    if i == len(p):     
        yield p_, q_
    else:
        c1 = ((N - p_ * q_) >> i) & 1
        p_prev, q_prev = p[i], q[i]
        for p_bit in (0, 1) if p_prev is None else (p_prev,):
            for q_bit in (0, 1) if q_prev is None else (q_prev,):
                if p_bit ^^ q_bit == c1:
                    p[i], q[i] = p_bit, q_bit
                    yield from _branch_and_prune_pq(
                        N, p, q,
                        p_ | (p_bit << i),
                        q_ | (q_bit << i),
                        i + 1)
        p[i], q[i] = p_prev, q_prev 

def factorize_pq(N, p_part, q_part):
    p_bits = [None if b == '?' else int(b) for b in p_part.to_bits_le()]
    q_bits = [None if b == '?' else int(b) for b in q_part.to_bits_le()]
    for p_val, q_val in _branch_and_prune_pq(N, p_bits, q_bits, 1, 1, 1):
        if p_val * q_val == N:
            return p_val, q_val

e  = 0x10001
c  = 8727199524595926705764225400506509289328151131514216250729515468155056218121221736963201841068215034487098098953821401326608386786346273720157155314820322698467429532461275463492599870550737132469369170204135115917482423036582822051988921146256688643845978757358407310854847663288337574501668030413804655286776436934536537698538527143491308805754764317305745181888684722727299988112034122487006667085647945475968191154669980943257738894146053667458797138697522920065140999462467096217712503505631649242142240435841977317598886490888750486215707059341912936564463860839090693276780817194811851886409356689470673107532
n  = 10644244264245763932368979306576292154978169307980875431845848585515469979129741395711953185867051023317557615618234242176875251628599522772285258093327797679006324429376013569137018200577185349745003553221219229088693373960547344593762243714560234819514388391843307341206257538676824211613659149855441367734883320000869003833119510179206721701295702803923970241717612194010327944659540526556778579813186112749725822081690619963415418470255547473934066594150396804785237389851791915432015775405773476289374397136777722281258153565989398760008739331917818507905928387120867159103459386796293552147742130942785387667101
M1 = 88914640319156584554519907036301003224288784208184838268121846462159927955700945270283676500515406136279062455494762039147468454696771001133686799200482356740310590971170822957938953133862391626427210893445970048978263432949487046574710938280744537191675594575399501647648365744088495505838716001393025318711
M2 = 80710645955732183961498834296041390466353463350909365967073721088344234170831463482355150027971590908133797348848447302046512581471517653450640672441875363390417692734403220383748851502073357434012901646484453882427070643197703826675885986584075167513954328971199897226577585871016371987052379150617824721747
P  = 1454713629297571001528363141111343262783446611248718929759592692372410193692959981391616314247878825643517231716578815166717528906295323061858760318849863325461174191466111073232730195560930748935209775742509843564017912569158094461170983358891473208999861629367188907727554105902252420135214355007297361937
Q  = 23026771663186153673881188958499640470803688134356820454731962008947492131018559717122163720894546472163872899425608926369661262023609393522302590736445675570962275851657015555698875694838166833166542306554507099577746272183034587942732263335474963112075217970257365953713038351465989425740093838238205086529

bitlen = 1024   
p_part = PartialInteger(P, M1, bitlen)
q_part = PartialInteger(Q, M2, bitlen)
p, q = factorize_pq(n, p_part, q_part)

phi = (p - 1)*(q - 1)
d   = pow(e, -1, phi)
print(bytes.fromhex(f"{pow(c, d, n):x}").decode())
# ictf{4_p4r714l_1nf0rm4710n_r54_w17h0u7_l4771c35}