R1R2
Last updated
Was this helpful?
Last updated
Was this helpful?
Catégorie: Cryptanalyse - Difficulté: Facile
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 :