ACSC Quals 2024

RSA stream 2

chal_redacted.py

from Crypto.Util.number import getPrime
import random
import re


p = getPrime(512)
q = getPrime(512)
e = 65537
n = p * q
d = pow(e, -1, (p - 1) * (q - 1))

m = random.randrange(2, n)
c = pow(m, e, n)

text = open(__file__, "rb").read()
ciphertext = []
for b in text:
    o = 0
    for i in range(8):
        bit = ((b >> i) & 1) ^ (pow(c, d, n) % 2)
        c = pow(2, e, n) * c % n
        o |= bit << i
    ciphertext.append(o)


open("chal.py.enc", "wb").write(bytes(ciphertext))
redacted = re.sub("flag = \"ACSC{(.*)}\"", "flag = \"ACSC{*REDACTED*}\"", text.decode())
open("chal_redacted.py", "w").write(redacted)
print("n =", n)

# flag = "ACSC{*REDACTED*}"
#n = 106362501554841064194577568116396970220283331737204934476094342453631371019436358690202478515939055516494154100515877207971106228571414627683384402398675083671402934728618597363851077199115947762311354572964575991772382483212319128505930401921511379458337207325937798266018097816644148971496405740419848020747

This is how encryptation work:

First bit of chall file (which contains the flag) xor with , $(m\mod n)\mod 2$, the second bit xor with

$(2*m \mod n) \pmod 2$, $…$

Then chall file redacted flag

So we can only get last bit of $ m \pmod n$, $(2 * m \pmod n)$, … but it is enough to get $m$ this is because 2 $*$ m always even so if it mod n - odd number two cases appear:

• If result is even which mean m $ \leq $ n/2
• Else m $>$ n/2

n.bit_length() = 1024, we only need 128 chars to search

So that, I use binary search to find m ; however, the actual $m’$ is near it.

RSA lsb attack

solve.py

import random
from Crypto.Util.number import getPrime
from output import n
from tqdm import*

text = open("chal_redacted.py", "rb").read()
ctext = open("chal.py.enc", "rb").read()
check=""
for b, c in zip(text, ctext):
    o = 0
    for i in range(8):
        bit = ((b >> i) & 1) ^ ((c>>i)&1)
        check += str(bit)

k=1
lb, ub = 0, n
for i in trange(n.bit_length()):
    if check[k]=="1":
        lb = (ub+lb)//2
        k+=1
    else:
        ub = (ub+lb)//2
        k+=1

for bound in trange(-2000, 2000):
    m = ub+bound
    ciphertexts = []
    ctext = open("chal.py.enc", "rb").read()
    for c in ctext:
        o = 0
        for i in range(8):
            bit = ((c >> i) & 1) ^ ((m) % 2)
            m = (2*m)%n
            o |= bit << i
        ciphertexts.append(o)


    if b"ACSC{" in bytes(ciphertexts):
        print(f"{bound = }")
        open("chal_solve.py", "wb").write(bytes(ciphertexts))
        break