Down the Rabinhole

6 minutes to read

We are given a Python code to encrypt the flag, and the corresponding out.txt file:

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from Crypto.Util.Padding import pad
import os


FLAG = b"HTB{--REDACTED--}"


def getPrimes(coefficient):
    while True:
        a = getPrime(512)
        p = 3 * coefficient * a + 2
        if isPrime(p):
            break
    while True:
        b = getPrime(512)
        q = 3 * coefficient * b + 2
        if isPrime(q):
            break
    return p, q


def encrypt(message, coefficient):
    p, q = getPrimes(coefficient)
    n = p * q

    padded_message = bytes_to_long(pad(message, 256))
    message = bytes_to_long(message)

    c1 = (message * (message + coefficient)) % n
    c2 = (padded_message * (padded_message + coefficient)) % n
    return (n, c1, c2)


def main():
    coefficient = getPrime(128)
    out = ""

    message = FLAG[0:len(FLAG)//2]
    n1, c1, c2 = encrypt(message, coefficient)
    out += f"{n1}\n{c1}\n{c2}\n"

    message = FLAG[len(FLAG)//2:]
    n2, c3, c4 = encrypt(message, coefficient)
    out += f"{n2}\n{c3}\n{c4}\n"

    out += f"{len(FLAG)}"

    with open("out.txt", "w") as f:
        f.write(out)


if __name__ == '__main__':
    main()

19776862259930835769533075141648724317136726865325219582974628641663028757626265811083579217562652521882819442186121072998911507994180202653223643709290080839913395525826127153190928840827396123760992080649033993986933259414523207699646834981906819263319717393978144309193843291629147724979917210633945695963741292906203710063193032172565935616940163881309010593278779797311032854042143
18940449739373929782738747330951086701639920358124022449285915914681280430796481828627299763135820762855030234173393995786612606880441619894387463477558992819159868677736220547584576162287130594708254787956440732197673909613467337841562238900614238638819659960733399020443364866675611439229048487547611412841048501574753238490324081535533435151621545695715920828646120795059085207687562
8139131820890905559667838555211733555742225714065473904284826530490173193882559461890851501765452084252909412188575022633596512451349296562551141247433279875212083704533696867645657058965269748533381751261887853181791035505421692256731545740535452608088572835061213186774986415770477686449034066741760771862922788827235376073691257160953903839272893965131226612277505938410382901008254
26981290975895303933094134784682647576666219028610175215312705398803184876873073206073503314367717924247311343215620922642215797499997039996235807898656819655954778538207489354154710796202412578870511364360408739855039573753404337104901925571890067221867326539447741757218265017060345184819121122211405292705642802582423249795098475142694876497945367191724577275836649641722277321440333
11417442976137891276889457530453693512824297007151561589652706330477531354073557298919952168938641673547415923544612769937040826488039629275033613885416852757446100888628373584968290007182319967658770715301605453943639269415203462531753249668211460008832837924575003999865632991329309338991536326471187269457640505585240846158952935988441171094886116683100214189858525596159931001818615
18355127503780127719693553150263322113757549849264731376621241697648137569897555203319854095104524520716185245672659763235856966677160994023952943459682923666302498240656511471051133821432105321005228730688019003306690750456433049212247022010356640992865785005342800448602013572898416040572578635571772069565860571397553306232025854213437948953083273924864099046923310816080854899416432
186

First of all, we see that the program takes a 128-bit prime number called coefficient to generate other prime numbers and . Let be the value of coefficient, then the prime numbers and are computed as:

Where and are 512-bit prime numbers. Using this strange method, we have two modulus: and . Hence, we might be able to find the coefficient because it is common in the two modulus. Let and , then:

Notice that:

Since we have and , then , so

Alright, now let’s see how the ciphertexts and are computed (the procedure will be the same for and ). Let be the first half of the flag:

The pad function adds more bytes to the message in a predictable way. For example, if a message of 12 bytes long is padded up to 16 bytes, the padding will be 4 bytes \x04. These are some examples:

$ python3 -q
>>> from Crypto.Util.Padding import pad
>>> pad(b'A' * 12, 16)
b'AAAAAAAAAAAA\x04\x04\x04\x04'
>>> pad(b'A' * 10, 16)
b'AAAAAAAAAA\x06\x06\x06\x06\x06\x06'
>>> pad(b'A' * 1, 16)
b'A\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'

We can express the pad operation in mathematical terms like this, being the length of the message:

And (the actual padding) is the following expression. For simplification purposes, let :

Which is the sum of a geometric progression, which equals

Therefore, we can express as follows

Now we can move some things around:

Let’s define as

We can get rid of if we subtract :

At this point, we can isolate :

So we have everything, we only need to script it. This is a Python script that solves the challenge:

#!/usr/bin/env python3

import math


def main():
    with open('out.txt') as f:
        n1, c1, c2, n2, c3, c4, L = map(int, f.read().splitlines())

    C = math.gcd(n1 - 4, n2 - 4) // 3

    K = 256 - math.floor(L / 2)
    P = int(hex(K)[2:] * K, 16)

    X = (c2 - P ** 2 - P * C) * pow(256 ** K, -1, n1) % n1
    m1 = (X - 256 ** K * c1) * pow(2 * P + C - C * 256 ** K, -1, n1) % n1

    K = 256 - math.ceil(L / 2)
    P = int(hex(K)[2:] * K, 16)

    Y = (c4 - P ** 2 - P * C) * pow(256 ** K, -1, n2) % n2
    m2 = (Y - 256 ** K * c3) * pow(2 * P + C - C * 256 ** K, -1, n2) % n2

    print(bytes.fromhex(hex(m1)[2:] + hex(m2)[2:]))


if __name__ == '__main__':
    main()

$ python3 solve.py
b'HTB{You_were_supposed_to_find_the_gcd_trick_then_search_and_find_the_ACSC_writeup_learn_some_interesting_stuff_and_solve_the_challege_but_I_forgot_about_the_most_basic_thing_I_m_sorry:(}'

The full script can be found in here: solve.py.