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 :

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

  1. l'architecture de votre programme (code découpé en fonctions etc.),

  2. la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),

  3. la présence de commentaires aux endroits appropriés,

  4. la présence de documentation pour vos fonctions.

Liens utiles

Estimation du temps

1. Préliminaires

Le code fourni

L'archive fournie contient tout le code nécessaire pour tester vos fonctions. La fonction main est fournie et vous ne devez pas la modifier. Le seul fichier que vous devez modifier est le fichier albus-dumbledore.c, que vous devrez renommer. Ce fichier contient une fonction appelée perform_tests(). Cette fonction est appelée lorsque vous lancer l'exécutable avec l'option -T et prend un argument du type char*. Le fichier tests-albus-dumbledore.c (fourni) contient un test pour la question 1. Vous devez la compléter pour tester votre code pour les questions suivantes.

Par exemple : 

$ make
gcc -Wall -std=c99 -Wextra -pedantic -Werror -c -o utils.o utils.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -c -o lcg.o lcg.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -c -o lfsr.o lfsr.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -c -o main.o main.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -c -o albus-dumbledore.o albus-dumbledore.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror -c -o tests-albus-dumbledore.o tests-albus-dumbledore.c
gcc -Wall -std=c99 -Wextra -pedantic -Werror utils.o lcg.o lfsr.o main.o albus-dumbledore.o -o albus-dumbledore
$ ./albus-dumbledore -h
  Usage:

  As a generator:
    ./albus-dumbledore -g LCG <a> <c> <m>             generate random numbers using an LCG
    ./albus-dumbledore -g LFSR <t1> ... <tn>          generate random numbers using an LFSR
  and the option -n <nb> allows to specify how many numbers will be generated (default: 10)

  To crack a generator:
    ./albus-dumbledore -c LCG <r1> <r2> ...           attempt to recover the LCG from the sequence of integers r1,r2,...
    ./albus-dumbledore -m <m> -c LCG <r1> <r2> ...    attempt to recover the LCG from the sequence of integers r1,r2,... with modulus m
    ./albus-dumbledore -c LFSR <r1r2...>              attempt to recover the LFSR from the sequence of bits r1,r2,...

  Internal tests:
    ./albus-dumbledore -T <ARG>                       execute the 'test' function

$ ./albus-dumbledore -T 1
TESTS
-----

inverse modulo (question 1)
L'inverse de 12345 modulo 2147483647 est 1417217438
Vérification: 12345 * 1417217438 = 1 (mod 2147483647)

Le fichier fourni contient 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 :

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

  1. vérifier que le PGCD de a et m est égal à 1,

  2. trouvez les nombre x et y vérifiant a*x + m*y == 1,

  3. renvoyer le nombre x.

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

Pour faire ceci, vous devrez utiliser la fonction (fournie) gcd_bezout qui calcule un PGCD avec les nombre de Bezout associés: 

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

Cette fonction prend en arguments deux entiers a et b et calcule :

  • leur PGCD g,

  • deux nombres x et y qui vérifient a*x + b*y == g.

N'oubliez pas de tester votre fonction en utilisant la fonction perform_tests() : 

  $ ./albus-dumbledore -T 1
  TESTS
  -----

  inverse modulo (question 1)
  L'inverse de 12345 modulo 2147483647 est 1417217438
  Vérification: 12345 * 1417217438 = 1 (mod 2147483647)

Attention, l'opération "modulo" du C (notée avec "%") peut renvoyer un nombre négatif. Pour éviter ceci (dans les tests) il est utile de définir une fonction pour calculer le modulo "mathématique" qui est toujours positif. 

int64_t mod(int64_t x, int64_t m) {
    return ((x%m) + m) % m;
}

Cette fonction est déjà définie dans le fichier utils.c et il n'est pas nécessaire de la redéfinir...

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 xn = a xn-1 + c (mod m), ou, en C, 

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

Lorsque le nombre m (le module du générateur) est connu (et que le générateur est de période maximale), il est possible de retrouver a et c à partir des nombres x1, x2, x3...

Retrouvez les équations exprimant a et c en fonction de m, x1, x2 et x3. Pour ceci, vous pouvez ignorer les "modulo m" en vous concentrant sur la résolution d'un système de 2 équations linéaires a deux inconnues. (Il faudra juste ne pas oublier de faire les calculs "modulo m" dans votre fonction...)

Programmez la fonction 

int LCG_crack(int nb, int64_t *random, int64_t* a, int64_t* c, int64_t* m);

qui calcule a et c à partir d'un tableau random de nombres nb nombres aléatoires générés par un LCG de module *m.

Attention : le paramètre m est un pointeur car la fonction LCG_crack sera étendue pour pouvoir retrouver le module m en plus des nombres a et c.

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. 

  $ ./albus-dumbledore -m 2147483648 -c LCG 1103527590 377401575 662824084
  crack successfull:

  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:

  1. si x1, ... xn sont des nombres consécutifs donnés par le générateur, ils vérifient xk = a xk-1 + c (mod m).

  2. Les différences successives yk = (xk+1 - xk) vérifient yk+1 = a yk (mod m) et donc yk+1 = a2 yk-1 (mod m).

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

    Autrement dit, chacun des nombres zk = yk+1 yk-1 - yk2 est un multiple de m.

  3. Le nombre m est donc un diviseur commun de tous les nombres zk. Le nombre m est en fait le pgcd de tous les nombres zk avec une très forte probabilité.

Ajoutez le code nécessaire à la fonction LCG_crack pour qu'elle cherche le module m en plus des nombres a et c: lorsque l'argument *m est à 0, la fonction doit le calculer, sinon elle utilise la valeur *m donnée en argument...

Utilisez la méthode décrite ci dessus. Attention, répondez aux questions suivantes avant de tester votre code.

Votre fonction devra terminer en testant que les valeurs obtenue pour m, a et c permettent bien de retrouver toutes les valeurs du tableau random. Dans ce cas, la fonction renverra 1. Si ce n'est pas le cas, alors votre fonction devra renvoyer -1.

Testez votre fonction sur les exemples suivants (et d'autres plus simples): 

$ ./albus-dumbledore -c LCG 476701654 1778738775 130368836 1085367853
???           # pas assez de valeur pour trouver m
$ ./albus-dumbledore -c LCG 476701654 1778738775 130368836 1085367853 209217378
???           # pas assez de valeurs pour trouver m
$ ./albus-dumbledore -c LCG 476701654 1778738775 130368836 1085367853 209217378 1452282099
???           # OK, on peut calculer m
$ ./albus-dumbledore -c LCG 476701654 1778738775 130368836 1085367853 209217378 1452282099 259223984 1592473641 1845073838 1578158415
???           # OK, on peut calculer m
$ ./albus-dumbledore -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 -1 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 bn = bn-i ⊕ bn-j ⊕ ... ⊕ bn-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:

b1,1 x1 ⊕ ... ⊕ b1,n xn = c1
b2,1 x1 ⊕ ... ⊕ b2,n xn = c2
...
bn,1 x1 ⊕ ... ⊕ bn,n xn = cn

où chaque coefficient bi,j ou ck est soit 0 soit 1.

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

b1,1 b1,2 ... b1,n c1
b2,1 b2,2 ... b2,n c2
...
bn,1 bn,2 ... bn,n cn

Comme nous n'aurons 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

x1 ⊕ x2 ⊕ x3 ⊕ x4 ⊕ x5 = 0
x2 ⊕ x3 ⊕ x4 = 1
x1 ⊕ x2 ⊕ x4 = 0
x3 ⊕ x4 ⊕ x5 = 0
x2 ⊕ x3 ⊕ x4 ⊕ x5 = 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,

  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

  2. 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 -1, 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.

N'hésitez pas à utiliser la fonction print_M pour afficher (en binaire) la matrice M et déboguer votre fonction...

Testez votre fonction sur la matrice M donnée plus haut. Vous devriez obtenir, après le pivot de Gauss, la matrice suivante : 

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

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 ti = 1 lorsque i est un des taps du générateurs et ti = 0 sinon, et si b1, ..., b2n sont les premiers bits générés, on a

b1 tn ⊕ ... ⊕ bn t1 = bn+1
b2 tn ⊕ ... ⊕ bn+1 t1 = bn+2
...
bn tn ⊕ ... ⊕ b2n-1 t1 = b2n

Il suffit alors de résoudre le système pour trouver les valeurs de t1, ..., tn, 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é :

b1 b2 ... bn bn+1
b2 b3 ... bn+1 bn+2
...
bn bn+1 ... b2n-1 b2n

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

Les solutions donnent les taps inversés : le tap t1 se trouve sur la dernière ligne, le tap t2 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 bn = bn-3 ⊕ bn-1.

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

  1. 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 b0, b1, ..., bn. Si c'est le cas on a trouvé un générateur approprié. Sinon, on passe à la taille suivante.

  2. 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 b0, b1, ..., bn. Si c'est le cas on a trouvé un générateur approprié. Sinon, on passe à la taille suivante.

  3. 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 b0, b1, ..., bn. Si c'est le cas on a trouvé un générateur approprié. Sinon, on passe à la taille suivante.

  4. etc.

Si on ne trouve aucune taille permettant de générer la suite b0, b1, ..., bn, 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, int *random, 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.

La fonction devra renvoyer 1 en cas de succès et -1 en cas d'échec.

N'oubliez pas de tester votre fonction !