langevin@u1-110-7 : 12/16/16 _ _ _ _ _ __ _ _ __(_) |_| |__ _ __ ___ ___| |_(_) __ _ _ _ ___ / _` | '__| | __| '_ \| '_ ` _ \ / _ \ __| |/ _` | | | |/ _ \ | (_| | | | | |_| | | | | | | | | __/ |_| | (_| | |_| | __/ \__,_|_| |_|\__|_| |_|_| |_| |_|\___|\__|_|\__, |\__,_|\___| |_| --- travail personnel: requis utilisation du compte: libre commandes réseaux: interdites permission HOMEDIR : drwx------ Repondre aux questions directement dans l'enonce en utilisant des lignes de moins de 72 caracteres. Pour les sources, utiliser les noms de fichiers precises dans l'enonce. Les sources ne doivent pas contenir de commentaires, ni de codes inutiles. Tous les programmes, fichiers etc... devront etre places dans le repertoire d'examen : /home/perso/langevin/exam-tp-D13-2016-langevin Vous validerez votre travail par la commande : /home/partage/pl/validexam -m D13 --- ======================================================================= 1. RSA sur l'hote ======================================================================= [ a ] Quel repertoire contient les clefs utilisees par ssh ? $(HOME)/.ssh [ b ] Utiliser ssh-keygen pour creer une paire de clefs RSA dans les fichiers cle et cle.pub prompt>ssh-keygen -f cle [ c ] Utiliser la commande : openssl rsa -modulus -in cle -noout pour obtenir le module RSA. Quelle est la base utilisee ? prompt> openssl rsa -modulus -in cle -noout Modulus=A74F02A1837837982C2932F1E3BE1DAC6A9110... Le module est donne en base 16 [ d ] Donner la taille du module en base 10, 16 et 2. Penser a utiliser des commandes comme bc, tr, sed, wc, etc... prompt>x=$( openssl rsa -modulus -in cle -noout | sed 's/.*=//' ) prompt>bc <<< "obase=10;ibase=16;$x" | tr -cd '[A-Z0-9]' | wc -c 617 prompt>bc <<< "obase=16;ibase=16;$x" | tr -cd '[A-Z0-9]' | wc -c 512 prompt>bc <<< "obase=2;ibase=16;$x" | tr -cd '[A-Z0-9]' | wc -c 2048 [ e ] Quelle commande permet d'obtenir les parametres des cles en clair ? prompt>openssl rsa -text -in cle -noout [ f ] Quel est l'exposant de chiffrement ? Quel est son poids binaire ? prompt>openssl rsa -text -in cle -noout | grep Expo publicExponent: 65537 (0x10001) L'exposant de chiffrement 65537 = 2^16 + 1 est de poids 2. ======================================================================= 2. Chaine de Cunningham ======================================================================= Une chaine de Cunnigham de longueur n est une suite de n nombres premiers : p, 2p + 1, 2(2p + 1) + 1, ... Par exemple : 5, 11, 23, 47 est une chaine de longueur 4. [a] Ecrire un programme chaine.c prend un entier n sur la ligne de commande puis calcul une chaine de longueur n. #include #include #include "gmp.h" int main(int argc, char* argv[]) { mpz_t p,q; mpz_inits(p, q, NULL); mpz_set_str(p, argv[2], 10 ); int i, n=atoi(argv[1]); do { mpz_nextprime(p,p); mpz_set(q,p); i=0; while( mpz_probab_prime_p(q,30) !=0 ) { mpz_mul_ui(q,q,2); mpz_add_ui(q,q,1); i++; } } while ( i < n ); gmp_printf("chaine de longueur %d en %Zd\n", i, p); return 0; } [b] Ecrire un programme Cunnigham.c pour determiner une chaine de longueur aussi grande que possible. Inserer la plus longue chaine trouvee pendant la seance d'examen : Il fallait une boule infinie, en tache de fond... ======================================================================= 3. RSA ======================================================================= Il d'agit de completer la source rsabad.c pour obtenir un code qui prend en entree deux parametres t et w puis calcule une paire de clefs RSA. [a] Dans l'etat, le programme utilise deux options -t et -w. Preciser le role de ces options : role de t ? configure la taille des cles role de w ? configure le poids de l'exposant de chiffrement [b] Estimer la taille binaire du module en fonction de de la valeur du parametre t. 32 * t [c] Implanter int exposant( int w, mpz_t p, mpz_t q ) qui determine le plus petit exposant de chiffrement parmi les entiers de poids w. [ inserer le code de exposant ] int exposant(int w, mpz_t p, mpz_t q) { int e=1; mpz_t phi; // retourne un exposant chiffrement minimal // parmi les mots de poids w. mpz_init(phi); mpz_mul( phi, p, q ); mpz_sub( phi, phi, q ); mpz_sub( phi, phi, p ); mpz_add_ui( phi, phi, 1 ); while ( wt(e) != w || mpz_gcd_ui (NULL, phi, e) > 1 ) e++; return e; } [d] Implanter void clef( mpz_d, int e, mpz_t p, mpz_t q) qui calcule l'exposant de dechiffrement d. [ inserer le code de clef ] void clef(mpz_t d, int e, mpz_t p, mpz_t q) { mpz_t phi, tmp; mpz_inits(phi, tmp, NULL); mpz_mul( phi, p, q ); mpz_sub( phi, phi, q ); mpz_sub( phi, phi, p ); mpz_add_ui( phi, phi, 1 ); mpz_set_ui(tmp, e); mpz_invert (d, tmp, phi ); } [e] Donner un exemple de clefs, pour t=4, w=3. prompt> ./a.out -t4 -w3 n=17994832720196079043722316979840596787 e=11 d=13087151069233512025627820823675102179 [f] Pour quelle valeur de t, peut-on casser les clefs avec la commande factor ? Pour t < 4 . prompt> for t in {1..4}; do echo t=$t; source <( ./a.out -t$t -w3 | grep n= ) ; time factor $n; done t=1 2554392677: 50539 50543 real 0m0.003s user 0m0.000s sys 0m0.002s t=2 4489018601108298083: 2118730421 2118730423 real 0m0.060s user 0m0.057s sys 0m0.001s t=3 6833750950870566425543232143: 82666504406987 82666504406989 real 0m9.085s user 0m9.045s sys 0m0.000s ======================================================================= 4. Attaque ======================================================================= L'implantation rsabad.c porte bien son nom... L'objectif de l'exercice est d'ecrire un code pour casser les clefs produites par rsabad.c [ a ] Qu'est-ce que deux nombres premiers jumeaux ? p < q premiers sont dit jumeaux quand q - p = 2. [ b ] Afficher la difference q-p pour les premiers generes par rsabad.c. t=1 h=4 t=2 h=2 t=3 h=2 t=4 h=46 t=5 h=12 t=6 h=150 t=7 h=102 t=8 h=118 t=9 h=28 t=10 h=68 La difference est petite, de l'ordre de la taille des cles. [ c ] Ecrire un programme factor.c qui prend en entree un module rsa n, un parametre de distance h pour determiner une factorisation de n sous la forme : n = p q, et 0< q - p < h indication : il suffit de resoudre les equations : X^2 + r X - n ou r est un parametre entier inferieur a h. int solve( int h, mpz_t n ) { mpz_t x, y, d; mpz_init(d); mpz_add_ui(d, n, h*h); mpz_sqrt (d, d); mpz_init(x); mpz_sub_ui(x, d, h); mpz_init(y); mpz_add_ui(y, d, h); mpz_mul( d, x, y); if ( mpz_cmp( d, n) ) return 0; gmp_printf("\np=%Zd\nq=%Zd\n", x , y); return 1; } prompt> gcc -Wall factor.c -lgmp -o factor.exe prompt> ./rsa.exe -t10 -w3 n=5661620374072127619492487780454458933985517624380985589541795218109809321459015119224713509869 e=11 d=2573463806396421645223858082024754060902508011013862777276584017364797611726188775884384004391 h=68 prompt> ./factor.exe 5661620374072127619492487780454458933985517624380985589541795218109809321459015119224713509869 p=75243739766655189953627287830699906139534350071 q=75243739766655189953627287830699906139534350139