Solution de byhlel pour Poète

intro hardware

21 décembre 2025

Table des matières

Analyse du Challenge

Le but est de fournir un bytecode en hexadécimal pour une machine virtuelle personnalisée. Ce programme doit effectuer la même tâche que le fichier proof-of-elapsed-time.asm fourni, mais avec une contrainte de taille stricte : 14 octects soit maximum 28 caractères hexadécimaux.

Objectif du code

Le script de validation proof-of-elapsed-time.py teste le code avec la logique suivante :

  1. Initialise $R5 = k$ (le nombre d’itérations).
  2. Initialise $R6 = M$ (le message).
  3. Initialise l’exposant interne à 2 (c.exponent = 2).
  4. Vérifie que le code calcule bien $R6 = M^{2^k} \pmod N$.

Cela correspond à une boucle qui élève $R6$ au carré $k$ fois.

Contraintes et Problèmes

Le code assembleur fourni en exemple utilise des instructions coûteuses en espace :

  • MOV R2, #0 et MOV R2, #1 : Dans cette VM, charger une constante immédiate (MOV Rj, #imm) prend 2 mots (4 octets).
  • Le code original fait environ 20 octets, ce qui dépasse la limite de 14 octets.

Il faut donc ruser pour :

  1. Générer la constante $1$ sans utiliser d’immédiat.
  2. Gérer la boucle et la condition d’arrêt ($k=0$) de manière très compacte.

Construction de la solution

Nous disposons de 7 instructions (mots) exactement pour tout faire.

1. Générer la constante 1 (2 instructions)

Nous ne pouvons pas faire MOV R1, #1 (trop long). Cependant, nous savons via le script de test que le registre interne exponent (accessible via l’index 12, soit RC dans cette VM) est initialisé à 2.

Nous pouvons utiliser cela :

  • BTL R1, RC : Bit Length. Stocke la taille en bits de RC (qui vaut 2) dans R1.

    • En effet, 2 en bit est 10 (en base 2) ainsi sa taille est bien 2

  • DIV R1, R1, R1 : Divise R1 par lui-même. $R1 = 2 / 2 = 1$

Ces instructions ne prennent qu’un mot chacune (Opcode + registres compressés sur 16 bits).

2. La boucle optimale (4 instructions)

Pour gérer le cas $k=0$ et la décrémentation, nous utilisons l’instruction SUB. Dans cette VM (machine.py), SUB a, b met à jour le flag Carry (C) :

  • $C = \text{True}$ si $a \ge b$ (pas d’underflow).
  • $C = \text{False}$ si $a < b$ (underflow).

L’idée est de soustraire 1 à $k$ (R5).

  • Si $k \ge 1$, le résultat est positif, $C$ est True $\to$ On continue.
  • Si $k = 0$, $0 - 1$ provoque un underflow, $C$ est False $\to$ On sort.

La boucle en assembleur :

init:
    BTL     R1, RC      ; R1 = 2
    DIV     R1, R1, R1  ; R1 = 1

loop:
    SUB     R5, R5, R1  ; R5 = k - 1. Met à jour le flag C.
    JNCR    fin         ; Si C est False (k valait 0), on saute à la fin (Jump No Carry).
    POW     R6, R6      ; R6 = R6^2 mod N (Car l'exposant interne RC est 2).
    JR      loop        ; Saut relatif vers le début de la boucle.

fin:
    STP                 ; Stop.

Encodage du Bytecode

Il faut traduire ces instructions en hexadécimal en suivant la logique de assembly.py et machine.py.

  1. BTL R1, RC
  • Format 0x01 + registres. RC est l’index 12 (0xC).
  • Encodage : 0x0100 + (Src << 4) + Dst
  • Calcul : 0x0100 + 0xC0 + 0x01 = 01C1
  1. DIV R1, R1, R1
  • Format arithmétique 0x50 avec registres < 8.
  • Encodage : 0x5000 + (Op2 << 6) + (Op1 << 3) + Dst
  • Calcul : 0x5000 + (1<<6) + (1<<3) + 1 = 0x5000 + 0x40 + 0x08 + 0x01 = 5049
  1. SUB R5, R5, R1
  • Format arithmétique 0x4C.
  • Op2 (R1) = 1, Op1 (R5) = 5, Dst (R5) = 5.
  • Encodage : 0x4C00 + (Op2 << 6) + (Op1 << 3) + Dst
  • Calcul : 0x4C00 + 0x40 + 0x28 + 0x05 = 4C6D
  1. JNCR +2 (Sauter par-dessus POW et JR)
  • Instruction JNCR (Jump relative if No Carry). Opcode famille 0xCD.
  • Saut de 2 mots vers l’avant (pour sauter POW et JR).
  • Calcul : 0xCD00 + 0x02 = CD02
  1. POW R6, R6
  • Format 0x03.
  • Encodage : 0x0300 + (Src << 4) + Dst
  • Calcul : 0x0300 + 0x60 + 0x06 = 0366
  1. JR -4 (Retourner au SUB)
  • Instruction JR (Jump Relative). Opcode famille 0xCF.
  • On doit remonter de : JR lui-même (-1), POW (-2), JNCR (-3), SUB (-4).
  • Saut de -4. En complément à 2 sur 8 bits : (0xFC).
  • Calcul : 0xCF00 + 0xFC = CFFC
  1. STP
  • Opcode 0x14.
  • Calcul : 1400

Solution Finale

En concaténant les morceaux calculés, nous obtenons la chaîne hexadécimale suivante :

01C150494C6DCD020366CFFC1400

Pour avoir:

Enter your bytecode in hexadecimal:
>>> 01C150494C6DCD020366CFFC1400
[+] Testing correctness
[+] Congrats! Here is the flag: FCSC{REDACTED}