FCSC 2026: Virtual machine

Table of contents

The virtual machine described on this page is used for the following tests:

These challenges share three files:

  • machine.py: the Python file that evaluates the instructions for this machine.
  • assembly.py: an assembler described below.
  • crypto_accelerator.py: This file contains an implementation of Montgomery modular arithmetic.

The Provably Secure Signature and This is not a Bellcore tests also use the following file:

  • machine_faulted.py: This file contains a subclass of the machine to simulate errors (instructions replaced by NOP).

Assembler

A basic assembler written in Python is provided (assembly.py) to generate the machine code that will be interpreted (bytecode). This assembler supports label recognition to facilitate jumps within the code. The character for comments is ;.

Virtual Machine Description

The machine contains 16 registers that can hold any number. The registers are numbered from 0 to F. A hexadecimal system is used to designate the registers (RA instead of R10, for example).

During its initialization, the machine expects to receive:

  1. Initial values ​​in its input registers, according to the tests.
  2. A sequence of instructions that will be the code interpreted by the machine. This sequence is divided into 16-bit words in an array, with the first word at index 0 of the array.

The machine behaves like a small processor, the list of supported operations of which is given in the following summary table.

Virtual Machine Execution

The virtual machine interprets the sequence starting with the first 16-bit word located at address 0 of the sequence. The virtual machine always sets the program counter (PC) to the next instruction after an instruction is loaded and decoded. After this loading, the instruction is executed, updating the machine’s register values.

Debugging

Locally, it is possible to debug the virtual machine by setting the optional debug argument of the runCode method to True.

This method displays the machine’s state for each instruction. Users are free to redirect this output to a file, or modify the function to step through the program’s execution.

Instruction List

Summary Table

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, coded on a signed byte
  • cst = [0-9]+, 0x[0-9a-fA-F]+

After a # a number must be represented on at most 16 bits.

Special registers:

  • RC is used as exponent
  • RD is used as module
  • RE is used as Link Register
  • RF is used as Program Counter

Code example

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

Instructions details

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

Updates two booleans Z and C :

  • Z = True if Rm == Rn, else Z = False
  • C = False if Rm< Rn, else C = True

MUL Ro, Rm, Rn

Ro = Rm*Rn

Updates a boolean Z :

  • Z = True if Rm == 0 or Rn == 0, else Z = False

DIV Ro, Rm, Rn

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

if Rn == 0, it creates an error (that stops the program).

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 of size Rj bits (at most 4096 bytes)

If Rj == 0, it creates an error (that stops the program).

CMP Rj, Ri

Updates two booleans Z and C :

  • Z = True if Rj == Ri, else Z = False
  • C = False if Rj< Ri, else C = True

MOVCW Rj

Rj = @Rj

Reads 1 word (2 bytes) from adress Rj. The word at address Rj is the most significant word of the value.

MOVC Rj, Ri

Rj = @Rj

Ri indicates the number of words to read from address Rj. The word at address Rj is the most significant word of the value.

JZA dest

PC = dest if Z = True

JNZA dest

PC = dest if Z = False

JZR dest

PC += dest if Z = True

JNZR dest

PC += dest if Z = False

JCA dest

PC = dest if C = True

JNCA dest

PC = dest if C = False

JCR dest

PC += dest if C = True

JNCR dest

PC += op2 if C = False

JA dest

PC = dest

JR dest

PC += dest

CA op2

LR = return address (PC)
PC = dest

CR dest

LR = return address (PC)
PC += dest

RET

PC = LR

STP

Program end

EDIV Ro, Rm, Rn

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

If Rn == 0 or if Rm is not a multiple of Rn, it generates an error (that stops the program).

MR Rj

Updates boolean Z:

  • Z = True if Rj is probably prime numner, else Z = False

FP Rj, Ri

Initializes a hardware coprocessor dedicated to Montgomery arithmetic calculations. The value of Rj is copied into an internal register designated FPmodule. The value of Ri indicates the minimum working size, in bits. The working size is a multiple of 64 bits, and 3 bits of margin are taken from the minimum size passed as input. The actual working size is therefore: WorkingSize = 64*[(Ri+3)//64].

At initialization, two constants are calculated: an internal constant and the constant RR, which is equal to 4**WorkingSize mod FPmodule. RR is the modulo square of the constant R.

The modulo value must be odd. The working size is limited to 65536 bits.

FPRR Ro, Rm, Rn

Similar to the FP function, but where the value RR is already known, passed as input, and therefore does not need to be calculated. Ro contains the value RR, Rm contains the modulus, and Rn the minimum working size.

MOVRR Rj

Copies the value RR to the Rj register. If the coprocessor has not been initialized, this generates an error (which stops the program).

MM Ro, Rm, Rn

Ro = Rm*Rn/R mod FPmodule

Calculates the Montgomery product of Rm by Rn. If the coprocessor has not been initialized, this generates an error (which stops the program).

MM1 Rj, Ri

Rj = Ri/R mod FPmodule

Calculates the Montgomery product of Ri by 1. If the coprocessor has not been initialized, this generates an error (which stops the program).

MPOW Rj, Ri

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

Performs exponentiation using Montgomery products and the exponent stored in the RC register. If the coprocessor has not been initialized, this generates an error (which terminates the program).