Down the Rabinhole

6 minutos de lectura

Se nos proporciona un código en Python para cifrar la flag, y el correspondiente archivo out.txt:

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

En primer lugar, vemos que el programa coge un número primo de 128 bits llamado coefficient para generar otros números primos y . Sea el valor de coefficient, entonces los números primos y se calculan como:

Donde y son números primos de 512 bits. Usando este método extraño, tenemos dos módulos: y . Por tanto, seremos capaces de encontrar el valor de porque es común a ambos módulos. Sean y , entonces:

Nótese que:

Como tenemos y , entonces , por lo que

Genial, ahora vamos a ver cómo se calculan los textos cifrados y (el procedimiento es el mismo para y ). Sea la primera mitad de la flag:

La función pad añade más bytes al mensaje de manera predecible (PKCS7). Por ejemplo, si un mensaje de 12 bytes se rellena hasta 16 bytes, el relleno serán 4 bytes \x04. Aquí hay algunos ejemplos:

$ 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'

Podemos expresar la función pad en términos matemáticos como sigue, siendo la longitud del mensaje:

Y (el relleno) sigue la siguiente expresión. Por motivos de simplificación, sea :

Que es la suma de una progressión geométrica, que equivale a

Por tanto, podemos expresar como

Ahora podemos mover algunos términos:

Vamos a definir como

Podemos olvidarnos de si restamos :

En este punto, podemos despejar :

Y ya tenemos todo listo, ahora solo tenemos que programarlo. Este es un script en Python que soluciona el reto:

#!/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:(}'

El script completo se puede encontrar aquí: solve.py.