FCSC 2023 : Machine virtuelle

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

• Comparaison intro
• Fibonacci hardware
• RSA Secure Dev (1/3) fault attacks
• RSA Secure Dev (2/3) fault attacks
• RSA Secure Dev (3/3) fault attacks

Ces cinq épreuves partagent deux fichiers :

• machine.py : le fichier Python évaluant les instructions de cette machine.
• assembly.py : un assembleur décrit plus bas.

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 (chaîne de lettres terminée par :) 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. Les registres d’entrées sont R5 à RC
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.

Pour les épreuves du RSA, sans garantie de l’intégrité des nombres:

1. un message sera placé dans le registre R5.
2. un nombre premier p sera placé dans le registre R6.
3. un nombre premier q sera placé dans le registre R7.
4. un nombre iq sera placé dans le registre R8 (iq = q**(-1) mod p).
5. un nombre dp sera placé dans le registre R9 (dp = e**(-1) mod (p-1)).
6. un nombre dq sera placé dans le registre RA (dq = e**(-1) mod (q-1)).
7. un nombre e sera placé dans le registre RB.
8. un nombre d sera placé dans le registre RC (d = e**(-1) mod (p-1)(q-1)).

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.

Liste des instructions

Tableau synthétique

Family	Operation	Assembler	Updates	Action	Error
Move	Move	MOV Rj, op2	-	Rj = op2
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
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
	GCD	GCD Ro, Rm, Rn	-	Ro = gcd(Rm,Rn)
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
Random	Random	RND Rj	-	Rj = rand < 2**(8*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 = dest	PC>=l ou PC < 0
Call (Relative)	Call	CR adest	-	LR = PC, PC += dest	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]\w+
• rdest = Ri, [a-zA-Z]\w+, \+[0-9]+, -[0-9]+
• adest = Ri, [a-zA-Z]\w+, #[0-9]+, #0x[0-9a-fA-F]+
• cst = [0-9]+, 0x[0-9a-fA-F]+
• l désigne le nombre de mots (de 16 bits) du code

Après un # le nombre doit pouvoir être représenté sur au plus 16 bits. Après un + le nombre doit pouvoir être représenté sur au plus 7 bits. Après un - le nombre x doit respecter l’encadrement : 0 < x <= 128 Si rdest = Ri, alors le 8e bit est signé (-128 au lieu de 128)

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

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

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

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

POW Rj, Ri

Rj = Ri**exponent mod module

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

GCD Ro, Rm, Rn

Ro = gcd(Rm,Rn)

INV Rj, Ri

Rj = Ri**(-1) mod module

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

RND Rj

Rj = random de taille Rj 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 adest

PC = adest si Z = True

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

JNZA adest

PC = adest si Z = False

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

JZR rdest

PC += rdest si Z = True

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

JNZR rdest

PC += rdest si Z = False

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

JCA adest

PC = adest si C = True

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

JNCA adest

PC = adest si C = False

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

JCR rdest

PC += rdest si C = True

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

JNCR rdest

PC += rdest si C = False

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

JA adest

PC = adest

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

JR rdest

PC += rdest

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

CA adest

LR = adresse de retour (PC)
PC = adest

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

CR rdest

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

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

RET

PC = LR

Si PC dépasse la taille du code ou est négatif, cela génère une erreur (qui arrête le programme).

STP

Fin du programme