Consignes

Le TP est à rendre, avant le ??????...

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.

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 :

Liens utiles

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 renomer. Ce fichier contient une fonction appelée test(). Cette fonction est appelée lorsque vous lancer l'executable avec l'argument -T. Dans le fichier fourni, cette fonction contient un test pour la question 1. Vous devez de 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 galois.o galois.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 utils.o lcg.o lfsr.o galois.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
    ./albus-dumbledore -g galois <t1> ... <tn>        generate random numbers using a Galois LFSR
  In all cases, the option -s <seed> allows to choose the seed (default: 1)
  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                             execute the 'test' function

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

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

Inverse modulo

Écrivez la fonction 

long invert_mod(long a, long m);

qui renvoie l'inverse d'un nombre modulo un autre. Vous pouvez utiliser la fonction (fournie) pgcd_bezout qui calcule un PGCD avec les nombre de Bezout associés.

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

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

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

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 equations exprimant a et c en fonction de m, x1, x2 et x3.

Programmez la fonction 

int LCG_crack(int nb, long unsigned *random, long unsigned* a, long unsigned* c, long unsigned* 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) mod m 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 yk+1 yk-1 - yk2 est un multiple de m.

  3. Le nombre m est donc un diviseur commun de tous les nombres yk yk-2 - yk-12. Le nombre m est en fait le pgcd de tous les nombres yk yk-2 - yk-12 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 et renvoyez 1 lorsque les valeurs trouvées permettent bien de regénérer la suite, et -1 dans tous les autres cas.

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

$ ./albus-dumbledore -c LCG 476701654 1778738775 130368836 1085367853
???
$ ./albus-dumbledore -c LCG 476701654 1778738775 130368836 1085367853 209217378
???
$ ./albus-dumbledore -c LCG 476701654 1778738775 130368836 1085367853 209217378 1452282099
???
$ ./albus-dumbledore -c LCG 476701654 1778738775 130368836 1085367853 209217378 1452282099 259223984 1592473641 1845073838 1578158415
???
$ ./albus-dumbledore -c LCG 476701654 1778738775 130368836 1085367853 209217378 1452282099 123 234 345 456 678
???

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

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 unsigned long). 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 = 1

sera représenté par le tableau d'entiers 

unsigned long 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. on positionne en ligne i une ligne (de numéro entre i et nb_equations) avec un bit non nul en colonne i

  2. on remplace chaque ligne qui contient un 1 en colone 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 des bits 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 parcequ'il n'a pas de solution, soit parce qu'il en a une infinité).

Écrivez la fonction 

int gauss(long unsigned *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 à registre 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 t1 ⊕ ... ⊕ bn tn = bn+1
b2 t1 ⊕ ... ⊕ bn+1 tn = bn+2
...
bn t1 ⊕ ... ⊕ bn+1 t2n-1 = b2n

Il suffit alors de resoudre 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.

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        => t5

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

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 resoudre 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.

Écrivez la fonction 

int LFSR_crack(int nb, int *random, unsigned long* 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 !