Consignes

Le rendu de TP se fera uniquement à travers l'interface web TPLab. Vous devrez fournir un unique fichier .c contenant le code des fonctions demandées. (Votre fichier de tests ne sera pas utilisé...)

Vous pouvez utiliser le fichier Makefile fournit pour faciliter la compilation.

Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans votre fichier principal.

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

votre fichier devra s'appeler "nom.c",
chaque fichier devra comporter un commentaire au début avec vos nom, prénom, filière et numéro du TP,
votre code doit compiler avec les options -Wall -Werror -Wextra -pedantic -std=c99 qui sont définies dans le fichier Makefile. (Vous pouvez également ajouter les options -Wno-unused-parameter -Wno-unused-function.)

Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

l'architecture de votre programme (code découpé en fonctions etc.),
la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),
la présence de commentaires aux endroits appropriés,
la présence de documentation pour vos fonctions.

Liens utiles

l'archive contenant les fichiers du TP

Suite aux demandes répétées de nombreux étudiants, voici un petit tutoriel sur les fichiers Makefile (lien local : Makefile).

Je vous conseille le lire de fichier et de suivre les étapes décrites à l'intérieur. (À un autre moment que pendant le TP !)

1. Préliminaires

Utilisation du code

Le code fourni contient une fonction main dans un fichier main.c que vous ne devez pas modifier. Cette fonction permet de lancer le programme compilé depuis la ligne de commande.
Votre code devra être écrit dans le fichier albus-dumbledore.c. (Sauf les tests, qui seront dans tests-albus-dumbledore.c.)
Une des options disponibles est -T qui permet d'exécuter la fonction perform_tests du fichier test-albus-dumbledore.c. La fonction fournie gère un ou deux tests. À vous de l'étendre de manière pertinente.
Le code définit une fonction DEBUG qui s'utilise comme la fonction printf. Elle a simplement un premier argument supplémentaire qui permet de contrôler l'affichage :
- si cet argument est à 0, le message est toujours affiché,
- si cet argument est à 1, le message est seulement affiché si le programme est lancé avec l'option -v,
- si cet argument est à 2, le message est seulement affiché si le programme est lancé avec l'option -vv,
- etc.
L'exécutable propose d'autres options qui permettent de tester directement certaines fonctions (lcg_crack_ac, lcg_crack_m, etc.).

Voila un exemple d'exécution :

$ make
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function -c -o utils.o utils.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function -c -o lcg.o lcg.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function -c -o lfsr.o lfsr.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function -c -o main.o main.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function -c -o correction.o correction.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function -c -o tests-correction.o tests-correction.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -Wno-unused-parameter -Wno-unused-function utils.o lcg.o lfsr.o main.o correction.o tests-correction.o -o prng
$
$ ./prng -h
  Usage:

  As a generator:
    ./prng -g LCG A C M             generate random numbers using an LCG
    ./prng -g LFSR T1 ... Tn        generate random numbers using an LFSR
  In all cases, the option -s seed allows to choose the seed, in decimal (default: 1)
  and the option -n NB allows to choose how many numbers will be generated (default: 10)

  To crack a generator:
    ./prng -c LCG X1 X2 ...         attempt to recover the LCG from the sequence of integers X1,X2,...
    ./prng -m M -c LCG X1 X2 ...    attempt to recover the LCG from the sequence of integers X1,X2,... with modulus M
    ./prng -c LFSR BB...            attempt to recover the LFSR from the sequence of bitS BB,...

  Internal tests:
    ./prng -T ARG                   execute the 'test' function

$
$ ./prng -T invert 12345 2147483647
the inverse of 12345 modulo 2147483647 is 1417217438
check: 12345 * 1417217438 = 1 (mod 2147483647)
$

Inverse modulo

Écrivez la fonction

int64_t invert_mod(int64_t a, int64_t m);

qui renvoie l'inverse d'un nombre modulo un autre.

Pour inverser a modulo m, il faut

vérifier que le PGCD de a et m est égal à 1 et trouver les nombres x et y vérifiant a*x + m*y == 1. Vous pouvez faire ceci en utilisant la fonction gcd_bezout (fournie),
renvoyer le nombre x.

En effet, si a*x + m*y == 1, on a alors (a*x + m*y) % m == (a*x) % m == 1 !

Le prototype de gcd_bezout est

void gcd_bezout(int64_t *g, int64_t *x, int64_t *y, int64_t a, int64_t b);

Elle prend en arguments deux entiers a et b et calcule :

leur PGCD g,
deux nombres x et y vérifiant a*x + b*y == g.

N'oubliez pas de tester votre fonction. Par exemple :

$ ./prng -T invert 12345 2147483647
the inverse of 12345 modulo 2147483647 is 1417217438
check: 12345 * 1417217438 = 1 (mod 2147483647)

Attention, l'opération "modulo" du C (notée avec "%") peut renvoyer un nombre négatif. Pour éviter ceci vous pouvez utiliser la fonction suivante (définie dans utils.c) qui calcule le modulo "mathématique".
```
int64_t mod(int64_t x, int64_t m) {
    return ((x%m) + m) % m;
}
```
Attention, faire un modulo 0 (avec % ou via la fonction mod) provoque l'erreur floating point exception.

2. Craquer un générateur congruentiel linéaire

Les générateurs congruentiels linéaires (LCG) sont les plus simples. Chaque nombre aléatoire x est généré à partir du précédent en utilisant la formule x_n = a x_n-1 + c (mod m), ou, en C,

x = (a*x + c) % m;

Lorsque le nombre m (le module du générateur) est connu, il est en général possible de retrouver a et c à partir des nombres x₀, x₁, x₂.

Pour retrouvez a et c en fonction de m, x₀, x₁ et x₂ il faut résoudre un système de 2 équations linéaires a deux inconnues :

x₁ = a × x₀ + c

x₂ = a × x₁ + c

Résolvez ce système au brouillon en ignorant les modulo, et programmez la fonction

int LCG_crack_ac(int nb, const int64_t *X, int64_t m, int64_t *a, int64_t *c);

en utilisant les formules trouvées.

Cette fonction calcule a et c à partir des premiers nombres du tableau X (qui contient nb nombres aléatoires générés par un LCG de module *m).

Points importants :

les additions, soustractions et multiplication "modulo m" se font avec les opérations habituelles : +, - et *, et un modulo. La division devra utiliser la fonction invert_mod de la question 1. En effet, diviser par d revient à multiplier par l'inverse de d,
n'oubliez pas de renvoyer 1 lorsque vous avez calculé a et c et 0 si le calcul ne peut pas se faire.

Testez votre fonction, par exemple, sur les 3 nombres 1103527590, 377401575 et 662824084; avec 2147483648 comme module. Le résultat devrait être a=1103515245 et c=12345.

  $ ./prng -m 2147483648 -c LCG 1103527590 377401575 662824084
  crack successful:

  x_n = 1103515245.x_n-1 + 12345  (mod 2147483648)

Retrouver le module d'un LCG

Lorsque le module m du générateur congruentiel est inconnu, il faut faire un peu plus de calculs:

si x₀, ... x_n-1 sont des nombres consécutifs donnés par le générateur, ils vérifient x_k = a x_k-1 + c (mod m).
Les différences successives y_k = (x_k+1 - x_k) vérifient y_k+1 = a y_k (mod m) et donc y_k+1 = a² y_k-1 (mod m).

On peut déduire de tout ça que y_k+1 y_k-1 - y_k² = 0 (mod m).

Autrement dit, chacun des nombres z_k = y_k+1 y_k-1 - y_k² est un multiple de m.
Le nombre m est donc un diviseur commun de tous les nombres z_k. Le nombre m est en fait le pgcd de tous les nombres z_k avec une très forte probabilité.

Écrivez la fonction LCG_crack_m qui cherche le module m en utilisant la méthode décrite ci dessus.

Attention, répondez aux questions suivantes avant de tester votre code.

Combien de nombres y_k y a t'il ?
Combien de nombres z_k y a t'il ?

Testez votre fonction :

  $ ./prng -c LCG 476701654 1778738775 130368836 1085367853 209217378 1452282099
  crack successful:

  x_n = 1103515245.x_n-1 + 12345  (mod 2147483648)

Si vous ne disposez pas de suffisamment de nombres, la valeur trouvée pour m n'est pas forcément la bonne. Écrivez la fonction LCG_crack_check qui vérifie que a, c et m sont compatibles avec les valeurs du tableau X. Si ce n'est pas le cas, alors votre fonction devra renvoyer 0. (Elle doit renvoyer 1 si ça marche.)

Testez votre fonction sur les exemples suivants (et d'autres que que vous pourrez générer avec ./prng -g LCG A C M):

$ ./prng -c LCG 476701654 1778738775 130368836
???           # pas assez de valeur pour trouver m, le test échoue !
$ ./prng -c LCG 476701654 1778738775 130368836 1085367853
???           # pas assez de valeur pour trouver m, le test échoue !
$ ./prng -c LCG 476701654 1778738775 130368836 1085367853 209217378
???           # pas assez de valeurs pour trouver m
$ ./prng -c LCG 476701654 1778738775 130368836 1085367853 209217378 1452282099
???           # OK, on peut calculer m
$ ./prng -c LCG 476701654 1778738775 130368836 1085367853 209217378 1452282099 259223984 1592473641 1845073838 1578158415
???           # OK, on peut calculer m
$ ./prng -c LCG 476701654 1778738775 130368836 1085367853 209217378 1452282099 123 234 345 456 567
???           # pas de solution pour générer ces valeurs

Attention, dans le dernier exemple, votre fonction doit renvoyer 0 car la suite ne vient pas d'un générateur congruentiel linéaire !

3. Craquer un générateur à registre à décalage et rétroaction linéaire

Les générateurs à régistre à décalage et rétroaction linéaire permettent de générer une suite de bits aléatoires en utilisant une formule du style b_n = b_n-i ⊕ b_n-j ⊕ ... ⊕ b_n-k. Les nombres i, j, ..., k sont appelés des taps.

Pivot de Gauss

Une étape préliminaire pour craquer un générateur à registre à décalage et rétroaction linéaire est de pouvoir résoudre un système de n équations booléennes linéaires à n variables:

b_0,0 x₀ ⊕ ... ⊕ b_0,n-1 x_n-1 = c₀

b_1,0 x₀ ⊕ ... ⊕ b_1,n-1 x_n-1 = c₁

...

b_n-1,0 x₀ ⊕ ... ⊕ b_n-1,n-1 x_n-1 = c_n-1

où chaque coefficient b_i,j ou c_k est soit 0 soit 1.

Un tel système est représenté par la matrice booléenne suivante

b_0,0	b_0,1	...	b_0,n-1	c₀
b_1,0	b_1,1	...	b_1,n-1	c₁
...
b_n-1,0	b_n-1,1	...	b_n-1,n-1	c_n-1

Comme nous ne manipulerons pas de système avec plus de 63 variables, chaque ligne de la matrice peut être codée sur un entier 64 bits (type word, défini dans tp2.h comme un synonyme de uint64_t). Par exemple, le système

x₀ ⊕ x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄	=	0
x₁ ⊕ x₂ ⊕ x₃	=	1
x₀ ⊕ x₁ ⊕ x₃	=	0
x₂ ⊕ x₃ ⊕ x₄	=	0
x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄	=	0

sera représenté par le tableau d'entiers

word M[5] = {
  0x3e ,          //111110 en hexa
  0x1d ,          //011101 en hexa
  0x34 ,          //110100 en hexa
  0xe  ,          //001110 en hexa
  0x1e            //011110 en hexa
};
print_M(M,5);

qui donne effectivement

1 1 1 1 1 0
0 1 1 1 0 1
1 1 0 1 0 0
0 0 1 1 1 0
0 1 1 1 1 0

La méthode usuelle pour résoudre un système d'équations linéaire est de diagonaliser la matrice en utilisant le pivot de Gauss. Le cas booléen est encore plus simple que la méthode habituelle:

pour i variant de 0 à nb_equations-1,

si la ligne i ne contient pas un 1 en position i, on cherche une ligne k >= i contenant un 1 en position i et on remplace la ligne i par son XOR avec la ligne k
on remplace chaque ligne qui contient un 1 en colonne i, sauf la ième, par son XOR avec la ligne i : toutes les valeurs sur la colonne i deviennent égales à 0, sauf celle de la ligne i qui vaut 1.

Lorsqu'on a terminé et que tout c'est bien passé, on obtient donc une matrice diagonale avec les bits de la solution dans la dernière colonne (bit de poids faible de chaque ligne).

Si la première étape dans la boucle (recherche d'une ligne avec un bit 1 en position i) échoue, c'est que le système n'est pas diagonalisable (soit parce qu'il n'a pas de solution, soit parce qu'il en a une infinité).

Après l'étape i=5, la matrice doit ressembler à :

1 0 0 0 0 ? ? ? ? ? ?
0 1 0 0 0 ? ? ? ? ? ?
0 0 1 0 0 ? ? ? ? ? ?
0 0 0 1 0 ? ? ? ? ? ?
0 0 0 0 1 ? ? ? ? ? ?
0 0 0 0 0 ? ? ? ? ? ?
0 0 0 0 0 ? ? ? ? ? ?
0 0 0 0 0 ? ? ? ? ? ?
0 0 0 0 0 ? ? ? ? ? ?
0 0 0 0 0 ? ? ? ? ? ?

Après la dernière étape, la matrice ressemble donc à :

1 0 0 0 0 0 0 0 0 0 ?
0 1 0 0 0 0 0 0 0 0 ?
0 0 1 0 0 0 0 0 0 0 ?
0 0 0 1 0 0 0 0 0 0 ?
0 0 0 0 1 0 0 0 0 0 ?
0 0 0 0 0 1 0 0 0 0 ?
0 0 0 0 0 0 1 0 0 0 ?
0 0 0 0 0 0 0 1 0 0 ?
0 0 0 0 0 0 0 0 1 0 ?
0 0 0 0 0 0 0 0 0 1 ?

Attention, la colonne i contient le bit numéro i en partant de la gauche. Comme le bit de poids faible est à droite, on accède à la colonne i de la ligne k avec BIT(nb_equations-i, M[k]).

Écrivez la fonction

int gauss(word *M, int nb_equations);

qui applique le pivot de Gauss sur la matrice M.

Si la matrice M n'est pas diagonalisable, la fonction devra renvoyer 0, sinon, elle devra renvoyer 1. Dans les 2 cas, la matrice M est modifiée par la fonction et la matrice M finale sera diagonale lorsque c'est possible.

Testez votre fonction sur la matrice M donnée plus haut.

  $ cat matrix.txt 
  111110
  011101
  110100
  001110
  011110
  $
  $ ./prng -T gauss < matrix.txt
  pivot de Gauss sur la matrice
  1 1 1 1 1 0
  0 1 1 1 0 1
  1 1 0 1 0 0
  0 0 1 1 1 0
  0 1 1 1 1 0

  résultat:
  1 0 0 0 0 0
  0 1 0 0 0 0
  0 0 1 0 0 1
  0 0 0 1 0 0
  0 0 0 0 1 1

Attention, la fonction gauss ne doit faire aucun affichage sur stdin. Vos tests doivent être faits dans le fichier test-albus-dumbledore.c. Vous pouvez utiliser (dans vos tests) la fonction print_M pour afficher la matrice M en binaire et déboguer votre fonction.

Vous perdrez des points si cette consigne n'est pas respectée !

Algorithme de Massey-Berlekamp

Lorsque la taille de l'état d'un générateur à registres est connu (cette taille correspond au plus grand tap utilisé par ce générateur), retrouver les taps est facile. Si la taille du générateur est n, il suffit d'avoir 2n bits générés.

Si on note t_i = 1 lorsque i est un des taps du générateurs et t_i = 0 sinon, et si b₁, ..., b_2n sont les premiers bits générés, on a

b₀ t_n ⊕ ... ⊕ b_n-1 t₁	=	b_n
b₁ t_n ⊕ ... ⊕ b_n t₁	=	b_n+1
...
b_n t_n ⊕ ... ⊕ b_2n-1 t₁	=	b_2n

Il suffit alors de résoudre le système pour trouver les valeurs de t₁, ..., t_n, et donc retrouver les taps utilisés par le générateur. Pour cela, on utilise la fonction précédente sur la matrice M approprié :

b₀	b₁	...	b_n-1	b_n
b₁	b₂	...	b_n	b_n+1
...
b_n-1	b_n	...	b_2n-2	b_2n-1

et on récupère les bits de poids faible de la matrice M obtenue.

Les solutions donnent les taps inversés : le tap t₁ se trouve sur la dernière ligne, le tap t₂ sur l'avant dernière, etc.

Pour l'exemple précédent, la matrice diagonale

1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 1        => t3
0 0 0 1 0 0
0 0 0 0 1 1        => t1

signifie que les taps sont 3 et 1 et que le générateur est donc de la forme b_n = b_n-3 ⊕ b_n-1.

L'algorithme de Massey-Berlekamp permet de retrouver le générateur, y compris sa taille: si b₀, b₁, ..., b_n sont des bits générés, on recherche la plus petite taille, et les taps correspondants qui génèrent la suite b₀, b₁, ..., b_n:

on essaie de résoudre le système correspondant à taille=1.
- si le système n'est pas diagonalisable, on passe à la taille suivante.
- si le système est diagonalisable, on vérifie que le tap trouvé permet bien de générer toute la suite b₀, b₁, ..., b_n. Si c'est le cas on a trouvé un générateur approprié. Sinon, on passe à la taille suivante.
on essaie de résoudre le système correspondant à taille=2
- si le système n'est pas diagonalisable, on passe à la taille suivante.
- si le système est diagonalisable, on vérifie que les taps trouvés permettent bien de générer toute la suite b₀, b₁, ..., b_n. Si c'est le cas on a trouvé un générateur approprié. Sinon, on passe à la taille suivante.
on essaie de résoudre le système correspondant à taille=3
- si le système n'est pas diagonalisable, on passe à la taille suivante.
- si le système est diagonalisable, on vérifie que les taps trouvés permettent bien de générer toute la suite b₀, b₁, ..., b_n. Si c'est le cas on a trouvé un générateur approprié. Sinon, on passe à la taille suivante.
etc.

Si on ne trouve aucune taille permettant de générer la suite b₀, b₁, ..., b_n, c'est qu'il n'existe pas de générateur unique qui permet de retrouver la suite.

Le seul cas où cet algorithme ne peut pas répondre est lorsque la suite de bits "aléatoire" est 0000000000000000.... Dans le cas, la matrice n'est jamais diagonalisable, même s'il est possible d'utiliser n'importe quelle taille et n'importe quelle suite de taps. (Dans tous les cas, l'état interne 000...000 génère la suite constante 000....)

Écrivez la fonction

int LFSR_crack(int nb, const int *X, word *taps);

qui essaie de craquer un générateur à registre à décalage et rétroaction linéaire en utilisant l'algorithme de Massey-Berlekamp.

L'argument X contient nb bits : X[0] contient le premier bit, X[1] le deuxième, etc.

Votre fonction devra calculer le mot (entier 64 bits) taps qui contient des 1 en positions des taps (càd, la dernière colonne de la matrice après le pivot de Gauss).

La fonction devra renvoyer 1 en cas de succès et 0 en cas d'échec. (Vous devrez vérifier que les taps que vous avez trouvé génèrent bien les nombres donnés !)

N'oubliez pas de tester votre fonction !

Attention, le pointeur taps n'est pas un tableau, mais simplement un pointeur vers un mots.

Vous pouvez tester sur des exemples générés avec ./prng -g LFSR T1 T2 ...):

  $ ./prng -g LFSR -n 50 1 3 17

  b_n = b_n-1 + b_n-3 + b_n-17 (taps: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1)

  current state: 0x1 (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)

  11010011101001111110011000011111111101101001011000

Pour information, mon code commenté fait 64 lignes.
Pour vérifier que les taps trouves génèrent les bits donnés, vous pouvez utiliser les fonctions suivantes du code fourni (fichier lfsr.c):
- LFSR_init(taps) pour instancier le générateur avec les taps donnés,
- LFSR_seed(seed) pour initialiser le générateur avec la graine donnée,
- LFSR_random_bit() pour récupérer un nouveau bit génère par le générateur.

TP2 : craquer les générateurs aléatoires linéaires

info-602 : mathématiques pour l'informatique

Hivers 2023

Consignes

Liens utiles

1. Préliminaires

Utilisation du code

Inverse modulo

2. Craquer un générateur congruentiel linéaire

Retrouver le module d'un LCG

3. Craquer un générateur à registre à décalage et rétroaction linéaire

Pivot de Gauss

Algorithme de Massey-Berlekamp