fact_or.md

Writeup Fact!Or?

Description:

RSA is the safest cryptographic primitive that we know.
That is FACT! Or is it?

In this challenge, the user is given the following file and a output that contains the encrypted flag.

import os

# pip install pycryptodome
from Crypto.Util.number import bytes_to_long

import secret_numbers

assert secret_numbers.CONSTANT_1 < 1200 and secret_numbers.CONSTANT_2 < 1200
assert secret_numbers.CONSTANT_1 > 5 and secret_numbers.CONSTANT_2 > 5


def gen_mod(i: int, j: int):
    return pow(2, i) * pow(2, j) \
        - pow(3, i-1) * pow(2, j) \
        + pow(5, i-5) * pow(2, j) \
        - pow(2, j) \
        - pow(2, i) * pow(3, j-1) \
        + pow(3, i-1) * pow(3, j-1) \
        - pow(5, i-5) * pow(3, j-1) \
        + pow(3, j-1) \
        + pow(2, i) * pow(5, j-5) \
        - pow(3, i-1) * pow(5, j-5) \
        + pow(5, i-5) * pow(5, j-5) \
        - pow(5, j-5) \
        - pow(2, i) \
        + pow(3, i-1) \
        - pow(5, i-5) \
        + 1


def main() -> int:
    FLAG = bytes_to_long(os.getenv("FLAG", "ACSC{DUMMY_FLAG}").encode())
    e = 0x10001
    N = gen_mod(secret_numbers.CONSTANT_1, secret_numbers.CONSTANT_2)

    CT = pow(FLAG, e, N)
    assert pow(FLAG, e) > N

    print(f"{N = }")
    print(f"{e = }")
    print(f"{CT = }")

    return 0


if __name__ == "__main__":
    raise SystemExit(main())

The modulus N is being computed by calling the function gen_mod which takes two integers j and j using the following formular:
$2^{i} * 2^{j} - 3^{i-1} * 2^{j} + 5^{i-5} * 2^{j} - 2^{j} - 2^{i} * 3^{j-1} + 3^{i-1} * 3^{j-1} - 5^{i-5} * 3^{j-1} + 3^{j-1} + 2^{i} * 5^{j-5} - 3^{i-1} * 5^{j-5} + 5^{i-5} * 5^{j-5} - 5^{j-5} - 2^{i} + 3^{i-1} - 5^{i-5} + 1$
Since a lot of terms repeat, it's safe to assume that this term can be factorized to make it a bit nicer. Factorizing can be done in the following way. At first we are pulling out all $2^{j}$, $3^{j-1}$ and $5^{j-5}$ terms.
$(2^{i} - 3^{i-1} + 5^{i-5} - 1)* 2^{j} - (2^{i} - 3^{i-1} + 5^{i-5} - 1)* 3^{j-1} + (2^{i} - 3^{i-1} + 5^{i-5} - 1) * 5^{j-5} - (2^{i} + 3^{i-1} - 5^{i-5} + 1) * 1$
Now we can see that the term $2^{i} - 3^{i-1} + 5^{i-5} - 1$ repeats three times, so we can simplify the fomlar as follows
$(2^{i} - 3^{i-1} + 5^{i-5} - 1)* (2^{j} - 3^{j-1} + 5^{j-5} - 1)$

We now know that the each number is build by providing a exponent $2^{i} - 3^{i-1} + 5^{i-5} - 1$. Since we know in what range the exponents are, we can use this knowledge to factor the modulus.

This can be done by using the GCD (greatest common divisor)

for i in range(5, 1200):
    number = pow(2, i) - pow(3, i-1) + pow(5, i-5) - 1

    if math.gcd(N, number) != 1:
        p = number
        q = N // number
        break

After the two primes have been recovered, we can calculate the private exponent using Euler's totient function and decrypt the flag.

The full exploit can be seen below

import math

# uses pycryptodome (https://pypi.org/project/pycryptodome/)
from Crypto.Util.number import long_to_bytes

N = 159641220142841049909800973348468546822484624049295141216611828530002131521414690099252320537474674764135524129797880337188787043767064854322237657702953217054551676449481223818490100860533681216637237380208917122226715204077719593229008010066416524337683609428341888098230111152202466190805520747016352101528899877119191504737094526470808265328000862922205298369823033937556525243479721172745331685380477337487740532651557880009604336677258283561309453272210330686170927688472782915710253481748137911265910200602217858651418417935588742023245281747904293037274398895087880776181289509692467036406859098898563354456425685374359239265671441250615000075513604485395266338996328238292958192899500402111111521660739362610712383414972041755326437292625873084635784472670442507477803313668322850518385760308583815333409
e = 65537
CT = 32413816172646413452462934358767781134996024169947364675991110290681668227773881621441006013124612075351322087743116933371556928705520175746297371036295629004460404319645676668310343326295112324331541598698273043952968973300307417759502435069340755553095194245343586866772264220158983878811964145427525038458952199086220693815220728820903504749390167863732499721478549091058861966675316739096721664671623955015163357344050267140266155133330698834338278980044490121649776738212016150345059521468933873862552586306396458903631461652550483834718143497033081360670726829699615355268984220765939978092448447239325812407225534258919177057202100140764393773663225340687697416806847238779714058204887964614325205397857127085886389380202958826578526872749356643321813086691697316866687503863037756603163597833917944902258


def main() -> int:

    for i in range(5, 1200):
        number = pow(2, i) - pow(3, i-1) + pow(5, i-5) - 1

        if math.gcd(N, number) != 1:
            p = number
            q = N // number
            break

    phi_n = (p-1) * (q-1)
    d = pow(e, -1, phi_n)
    PT = pow(CT, d, N)

    print(f"Flag: {long_to_bytes(PT)}")

    return 0


if __name__ == "__main__":
    raise SystemExit(main())