R1R2

Catégorie: Cryptanalyse - Difficulté: Facile

2KB

encrypt.py

Open

Description:

Solution:

Ici il s'agit d'un chall assez simple où le flag a été chiffré avec la fonction encrypt_password :

Le but ici est de créer une fonction decrypt_password afin de lui donner notre flag et retrouver l'original. Avec les infos recueillies dans la fonction encrypt, le script inverse est assez simple à faire (avec un coup de pouce de ChatGPT si on veut aller plus vite) :

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import random as rd
from math import isqrt

# ----------------------------------------------------------------------
#  Construction d’un entier 1023 bits (fonction ci originale)
# ----------------------------------------------------------------------
def ci(z: int, info_1: int, info_2: int) -> int:
    assert info_1.bit_length() <= 511 and info_2.bit_length() <= 511
    return ((z & 1) << 1022) | ((info_1 & ((1 << 511) - 1)) << 511) | (info_2 & ((1 << 511) - 1))


# ----------------------------------------------------------------------
#  Chiffrement (identique au code fourni dans l’énoncé)
# ----------------------------------------------------------------------
def encrypt_password(password: str) -> bytes:
    a = b''
    b, c = password[::2], password[1::2]
    b = int.from_bytes(b.encode(), 'big')
    c = int.from_bytes(c.encode(), 'big')
    assert b > c
    d = b + c
    e = b * c
    r = []
    for _ in range(3):
        x = rd.randint(0, 2 ** b.bit_length())
        y = x * x - d * x + e
        z = y < 0
        t = ci(z, abs(y), x)
        r.append(t)
    for i in range(3):
        a += r[i].to_bytes((r[i].bit_length() + 7) // 8, 'big').rjust(128, b'\x00')
    return a


# ----------------------------------------------------------------------
#  Déchiffrement – partie demandée
# ----------------------------------------------------------------------
def _decode_block(block: bytes) -> tuple[int, int]:
    """Extrait (x, y) depuis un bloc de 128 octets issu de ci(...)."""
    if len(block) != 128:
        raise ValueError("Un bloc doit faire exactement 128 octets.")
    t = int.from_bytes(block, 'big')
    sign = (t >> 1022) & 1
    mask = (1 << 511) - 1
    abs_y = (t >> 511) & mask
    x = t & mask
    y = -abs_y if sign else abs_y
    return x, y


def decrypt_password(cipher: bytes) -> str:
    """
    Inverse encrypt_password.  Attend 384 octets (3 blocs de 128) et rend
    la chaîne de caractères du mot de passe en clair.
    """
    if len(cipher) != 3 * 128:
        raise ValueError("Le chiffré doit faire 384 octets (3 blocs).")

    # 1) extraction des triplets (xᵢ, yᵢ)
    blocks = [cipher[i * 128:(i + 1) * 128] for i in range(3)]
    xs, ys = zip(*(_decode_block(b) for b in blocks))
    x1, x2, x3 = xs
    y1, y2, y3 = ys

    # 2) résolution linéaire pour d et e :  y = x² − d·x + e
    num = (y1 - x1 * x1) - (y2 - x2 * x2)
    den = x2 - x1
    if den == 0 or num % den:
        raise ValueError("Blocs incohérents (division impossible).")
    d = num // den
    e = y1 - x1 * x1 + d * x1

    # 3) contrôle avec le 3ᵉ bloc
    if y3 != x3 * x3 - d * x3 + e:
        raise ValueError("Le troisième bloc ne colle pas : données corrompues ?")

    # 4) racines de t² − d·t + e = 0  →  b et c
    delta = d * d - 4 * e
    sqrt_delta = isqrt(delta)
    if sqrt_delta * sqrt_delta != delta:
        raise ValueError("Δ n'est pas un carré parfait – impossible de factoriser.")
    b = (d + sqrt_delta) // 2
    c = (d - sqrt_delta) // 2
    if b < c:                       # la convention imposait b > c
        b, c = c, b

    # 5) conversion int → bytes → str
    def int_to_bytes(n: int) -> bytes:
        return b'\x00' if n == 0 else n.to_bytes((n.bit_length() + 7) // 8, 'big')

    b_str = int_to_bytes(b).decode()
    c_str = int_to_bytes(c).decode()

    # 6) ré-entrelacement des caractères (pairs / impairs)
    pw_chars: list[str] = []
    for i in range(max(len(b_str), len(c_str))):
        if i < len(b_str):
            pw_chars.append(b_str[i])
        if i < len(c_str):
            pw_chars.append(c_str[i])
    return ''.join(pw_chars)


# ----------------------------------------------------------------------
#  Données fournies + démonstration
# ----------------------------------------------------------------------
ENCRYPTED_FLAG_HEX = (
    "40f1b6e577b2bb6aa703387a15d2738ad50c795972342bdbb4b32946bcf7b72f"
    "bbdfb41884883df6589bf0e1e73a01f4f0d13a60146ac87c146de846bb98407d8"
    "0000000000000000000000000000000000000000000000000000000000000000"
    "c4df9ca82064c5b97e3e5013732439d6139195456b94e581b7a22f1510f926c4"
    "117ca4ed6a10c5d37b5d400dca883d001564774dbbce5c198c5ff83fe7af851f"
    "c3820a17947e71689812f6113dd3893250a14320a8f49c46bde754a188efd300"
    "0000000000000000000000000000000000000000000000000000000000000000"
    "f6336ee243e9a18cd74b182ff23f87f8bbac8912b57cd3ab25faffcaa18ea394"
    "0d748f2696de5597ec5df6d12826fc2b37d8e926af7a39afe74cb0950460da1a"
    "33112d89029e1a9334ea4c19d36cab027d4b360f240139de4ebd58ebfb056818"
    "0000000000000000000000000000000000000000000000000000000000000002"
    "9e03851f31bd96e478b63347dc9a369a5d0569dc00ffe07cc3ad2d8293a9bf0"
)

if __name__ == "__main__":
    encrypted_flag = bytes.fromhex(ENCRYPTED_FLAG_HEX)
    flag_clear = decrypt_password(encrypted_flag)
    print(flag_clear)

Et voilà le résultat :

🚩FLAG

404CTF{B1p_bOuP_B6M!aU70d35crUt1oN_pR0g6aM_aC7Iv8t3d!321-B0om!}