FCSC 2026 : Machine virtuelle

Table des matières

La machine virtuelle décrite dans cette page concerne les épreuves suivantes :

Ces épreuves partagent trois fichiers :

  • machine.py : le fichier Python évaluant les instructions de cette machine.
  • assembly.py : un assembleur décrit plus bas.
  • crypto_accelerator.py : le fichier contient une implémentation d’arithmétique modulaire de Montgomery.

Les épreuves Provably Secure Signature et Ceci n'est pas une Bellcore utilisent en plus le fichier suivant :

  • machine_faulted.py : le fichier contient une classe fille de la machine pour simuler des fautes (instruction remplacée par un NOP).

Assembleur

Un assembleur sommaire écrit en Python est fourni (assembly.py) afin de générer le code machine qui sera interprêté (bytecode). Cet assembleur supporte la reconnaissance des étiquettes afin de faciliter les sauts dans le code. Le caractère pour les commentaires est le ;.

Description de la machine virtuelle

La machine contient 16 registres pouvant contenir des nombres aussi grands qu’on le souhaite. Les registres sont numérotés de 0 à F. On utilise un système hexadécimal pour désigner les registres (RA au lieu de R10 par exemple).

Lors de son initialisation, la machine s’attend à recevoir :

  1. des valeurs initiales dans ses registres d’entrées, selon les épreuves.
  2. une séquence d’instructions qui sera le code interprété par la machine. Cette séquence est découpée en mots de 16 bits dans un tableau, le premier mot étant à l’indice 0 du tableau.

La machine se comporte comme un petit processeur, dont la liste d’opérations supportées est donnée dans le tableau synthétique suivant.

Exécution de la machine virtuelle

La machine virtuelle interprète la séquence en commençant par le premier mot de 16 bits qui se trouve à l’adresse 0 de la séquence.

La machine virtuelle positionne toujours le compteur du programme (PC) sur la prochaine instruction après le chargement et le décodage d’une instruction. Après ce chargement, l’instruction est exécutée, mettant à jour les valeurs des registres de la machine.

Débogage

En local, il est possible de déboguer la machine virtuelle en mettant l’argument optionnel debug de la méthode runCode à True. Cette méthode affiche l’état de la machine pour chaque instruction. Libre aux utilisateurs de rediriger cet affichage dans un fichier, ou de modifier la fonction pour faire du pas à pas sur l’exécution du programme.

Liste des instructions

Tableau synthétique

Family Operation Assembler Updates Action Error
Move Move MOV Rj, op2 - Rj = op2
Get RR from coprocessor MOVRR Rj - Rj = RR no prior FP
Load Move from code (1 word) MOVCW Rj - Rj = @Rj
Move from code (Ri words) MOVC Rj, Ri - Rj = @Rj
Logical AND AND Ro, Rm, Rn - Ro = Rm & Rn
OR OR Ro, Rm, Rn - Ro = Rm | Rn
XOR XOR Ro, Rm, Rn - Ro = Rm ^ Rn
Shift right SRL Ro, Rm, Rn - Ro = Rm >> Rn
Shift left SLL Ro, Rm, Rn - Ro = Rm << Rn Rn >= 2**13
Arithmetic Bit length BTL Rj, Ri - Rj = bit_length(Ri)
Add ADD Ro, Rm, Rn - Ro = Rm + Rn
Subtract SUB Ro, Rm, Rn Z C Ro = Rm - Rn
Comparison CMP Rj, Ri Z C Rj - Ri
Multiplication MUL Ro, Rm, Rn Z Ro = Rm * Rn
Division DIV Ro, Rm, Rn - Ro = Rm // Rn Rn=0
Exact Division EDIV Ro, Rm, Rn - Ro = Rm // Rn Rn=0 ou Rm!=0[Rn]
GCD GCD Ro, Rm, Rn - Ro = gcd(Rm,Rn)
Primality Test MR Rj Z Z=True if Rjis prime
Modular Modular reduction MOD Rj, Ri - Rj = Ri mod RD RD=0
Modular exponentiation POW Rj, Ri - Rj = Ri**RC mod RD RD=0
Modular inversion INV Rj, Ri - Rj = Ri**(-1) mod RD RD=0
Coprocessor initialisation FP Rj, Ri - FPmodule: Rj size: Ri Rj&1=0 ou Ri=0
Coprocessor initialisation FPRR Ro, Rm, Rn - RR:Ro FPmodule: Rm size: Rn Rm&1=0 ou Rn=0
Montgomery Multiplication MM Ro, Rm, Rn - Ro = Rm*Rn/R mod FPmodule no prior FP
Montgomery Multiplication MM1 Rj, Ri - Rj = Ri/R mod FPmodule no prior FP
Montgomery Exponentiation MPOW Rj, Ri - Rj = (Ri/R)**RC*R mod FPmodule no prior FP
Random Random RND Rj - Rj = rand < 2**(Rj) Rj=0
Branch (Absolute) Jump if Z set JZA adest - PC = adest if Z=True PC>=l ou PC < 0
Jump if Z not set JNZA adest - PC = adest if Z=False PC>=l ou PC < 0
Jump if C set JCA adest - PC = adest if C=True PC>=l ou PC < 0
Jump if C not set JNCA adest - PC = adest if C=False PC>=l ou PC < 0
Jump JA adest - PC = adest PC>=l ou PC < 0
Branch (Relative) Jump if Z set JZR rdest - PC += rdest if Z=True PC>=l ou PC < 0
Jump if Z not set JNZR rdest - PC += rdest if Z=False PC>=l ou PC < 0
Jump if C set JCR rdest - PC += rdest if C=True PC>=l ou PC < 0
Jump if C not set JNCR rdest - PC += rdest if C=False PC>=l ou PC < 0
Jump JR rdest - PC += rdest PC>=l ou PC < 0
Call (Absolute) Call CA adest - LR = PC, PC = adest PC>=l ou PC < 0
Call (Relative) Call CR rdest - LR = PC, PC += rdest PC>=l ou PC < 0
Return Return RET - PC = LR PC>=l ou PC < 0
End Stop STP -
Tabular allocate constants .word cst, ... -

Notations :

  • Ri = R[0-9A-F]
  • Rj = R[0-9A-F]
  • Rm = R[0-7]
  • Rn = R[0-7]
  • Ro = R[0-7]
  • op2 = Ri, #[0-9]+, #0x[0-9a-fA-F]+, =[a-zA-Z]+
  • dest = Ri, [a-zA-Z]+, #[0-9]+, #0x[0-9a-fA-F]+
  • 0 <= adest < 65536
  • -128 <= rdest < 128, codé sur un octet signé
  • cst = [0-9]+, 0x[0-9a-fA-F]+

Après un # le nombre doit pouvoir être représenté sur au plus 16 bits.

Registres Spéciaux:

  • RC est utilisé comme exposant
  • RD est utilisé comme module
  • RE est utilisé comme Link Register
  • RF est utilisé comme Program Counter

Code exemple

abc:                        ;entry point, as first byte of generated bytecode
    MOV     R0, #0x00       ;assign constant value 0 to R0
    MOV     R1, #1          ;assign constant value 1 to R1
    MOV     R2, R1          ;assign R1 to r2
    MOV     R3, =constants  ;assign address of the tabular to R3
    MOVCW   R3              ;read first word from 'constants' tabular
    JR      startLoop       ;jump to relative address startLoop (offset from PC)
loop:
    ADD     R0, R1, R0      ;Add R1 to R0, result in R0. Not updating flags
startLoop:
    SUB     R2, R2, R1      ;subtract R1 (worth 1 here) from R2. Update flags
    JCR     loop            ;relative jump if carry, may be out range of relative offset if body of the loop is too huge
    STP                     ;end of programm

constants:                  ;some constants values
    .word 0x1234, 0x5678, =loop

Détails des instructions

MOV Rj, op2

Rj = op2

MOV Rj, =label

Rj = @label

AND Ro, Rm, Rn

Ro = Rm & Rn

OR Ro, Rm, Rn

Ro = Rm | Rn

XOR Ro, Rm, Rn

Ro = Rm ^ Rn

SRL Ro, Rm, Rn

Ro = Rm >> Rn

SLL Ro, Rm, Rn

Ro = Rm << Rn

Rnest limité à moins de 8192.

BTL Rj, Ri

Rj = bit_len(Ri)

ADD Ro, Rm, Rn

Ro = Rm + Rn

SUB Ro, Rm, Rn

Ro = Rm - Rn

Met à jour deux booléens Z et C :

  • Z = True si Rm == Rn, sinon Z = False
  • C = False si Rm< Rn, sinon C = True

MUL Ro, Rm, Rn

Ro = Rm*Rn

Met à jour un booléen Z :

  • Z = True si Rm == 0 ou Rn == 0, sinon Z = False

DIV Ro, Rm, Rn

Ro = Rm//Rn = quotient(Rm,Rn)

Si Rn == 0, cela génère une erreur (qui arrête le programme).

MOD Rj, Ri

Rj = Ri mod module

POW Rj, Ri

Rj = Ri**exponent mod module

GCD Ro, Rm, Rn

Ro = gcd(Rm,Rn)

INV Rj, Ri

Rj = Ri**(-1) mod module

RND Rj

Rj = random de taille Rj bits (au plus 4096 octets)

Si Rj == 0, cela génère une erreur (qui arrête le programme).

CMP Rj, Ri

Met à jour deux booléens Z et C :

  • Z = True si Rj == Ri, sinon Z = False
  • C = False si Rj< Ri, sinon C = True

MOVCW Rj

Rj = @Rj

Lit 1 mot (2 octets) à partir de l’adresse Rj. Le mot à l’adresse Rj est le poids fort de la valeur considérée.

MOVC Rj, Ri

Rj = @Rj

Ri indique le nombre de mots à lire à partir de l’adresse Rj. Le mot à l’adresse Rj est le poids fort de la valeur considérée.

JZA dest

PC = dest si Z = True

JNZA dest

PC = dest si Z = False

JZR dest

PC += dest si Z = True

JNZR dest

PC += dest si Z = False

JCA dest

PC = dest si C = True

JNCA dest

PC = dest si C = False

JCR dest

PC += dest si C = True

JNCR dest

PC += op2 si C = False

JA dest

PC = dest

JR dest

PC += dest

CA op2

LR = adresse de retour (PC)
PC = dest

CR dest

LR = adresse de retour (PC)
PC += dest

RET

PC = LR

STP

Fin du programme

EDIV Ro, Rm, Rn

Ro = Rm//Rn = quotient(Rm,Rn)

Si Rn == 0 ou si Rm n’est pas un multiple de Rn, cela génère une erreur (qui arrête le programme).

MR Rj

Met à jour le booléen Z:

  • Z = True si Rj est un nombre probablement premier, sinon Z = False

FP Rj, Ri

Initialise un coprocesseur matériel dédié aux calculs sur l’arithmétique de Montogmery. La valeur de Rj est copiée dans un registre interne désigné par le nom FPmodule. La valeur de Ri indique la taille minimale de travail, en bits. La taille de travail est un multiple de 64 bits, et 3 bits de marge sont pris par rapport à la taille minimale passée en entrée. La taille de travail réelle est donc: WorkingSize = 64*[(Ri+3)//64].

À l’initialisation, deux constantes sont calculées. Une constante interne et la constante RR qui vaut 4**WorkingSize mod FPmodule. RR est le carré modulaire de la constante R.

La valeur du module doit être impair. La taille de travail est limitée à 65536 bits.

FPRR Ro, Rm, Rn

Similaire à la fonction FP, mais où la valeur RR est déjà connue, passée en entrée et n’a donc pas besoin d’être calculée. Ro contient la valeur RR, Rm contient le module et Rn la taille minimale de travail.

MOVRR Rj

Copie la valeur RR dans le registre Rj. Si le coprocesseur n’a pas été initalisé, cela génère une erreur (qui arrête le programme).

MM Ro, Rm, Rn

Ro = Rm*Rn/R mod FPmodule

Calcule le produit de Montgomery de Rm par Rn. Si le coprocesseur n’a pas été initalisé, cela génère une erreur (qui arrête le programme).

MM1 Rj, Ri

Rj = Ri/R mod FPmodule

Calcule le produit de Montogmery de Ri par 1. Si le coprocesseur n’a pas été initalisé, cela génère une erreur (qui arrête le programme).

MPOW Rj, Ri

Rj = R*(Ri/R)**exposant mod FPmodule

Effectue l’exponentiation avec des produits de Montgomery en utilisant l’exposant stocké dans le registre RC. Si le coprocesseur n’a pas été initalisé, cela génère une erreur (qui arrête le programme).