CRYPTOGRAPHIE SYMETRIQUE
Contents
1. sage R inject_variables sage f BooleanFunction x0 x1 x2 sage f algebraic_normal_form x0 x1 x2 La troisi me fa on de d finir une fonction bool enne utilise sa forme po lynomiale La fonction bool enne de n variables est vue comme la trace d un polyn me univari coefficients dans une extension de GF 2 de degr n sage K lt a gt GF 273 name a sage P lt x gt K x sage f BooleanFunction x 7 a x 1 Il n existe pas dans SAGE de m thode pour calculer la forme polynomiale d une fonction bool enne Une impl mentation d une forme polynomiale sans unicit de la repr sentation est propos e sage def polynomial_form f i n f nvariables K lt a gt GF 2 n a P lt x gt K x return K x lagrange_polynomial K P Integer i Derai digits 2 GF 2 f i for i in range 2 n sage p polynomial_form f print p x 7 a 2 a x 4 a 2 x72 a x 1 sage f BooleanFunction p True On remarque que le polyn me trouv n est pas unique En effet a3 a 1 0 implique at a a Comme 2 et 4 appartiennent la m me classe cyclotomique binaire modulo 2 1 7 on voit que Tr a x xt Tr a x x On en d duit Chapitre 6 Manipulation de fonctions bool ennes avec SAGE 18 que Tr x ax 1 Tr x a a x a2x ax 1 sage K modulus x73 x 1 On peut v rifier que la table de v rit de Tr p est bien la table de v rit de2. atoire v rifiant une relation de r currence lin aire Un LFSR de n bits peut tre repr sent par un polyn me de degr n dont les coefficients d finissent la relation de r currence Il existe deux repr sentations possibles le polyn me de r troaction 1 cix Dans ce cas la relation de r currence est s Y c s _ mod2 et en par ticulier sn D Cis _ mod2 Par exemple le polyn me de r troaction 1 x x de coefficients c1 c2 63 ca 0 0 1 1 d finit un LFSR de 4 bits de relation de r cur rence st S43 St 4 On a en particulier s4 81 50 le polyn me caract ristique DE Ga x Dans ce cas la relation de r currence est s se CiSt_n4 mod2 et en particulier sn Not cis mod2 Par exemple le polyn me caract ristique 1 x xt de coefficients Co C1 C2 63 1 1 0 0 d finit un LFSR de 4 bits de relation de r cur rence 8 8 _4 8 _ 3 On a en particulier s4 S 51 Le polyn me caract ristique est le polyn me inverse du polyn me de r troaction La suite pseudo al atoire produite est sg 81 82 L tat interne l instant t est St 8 41 St n_1 Du fait des propri t s statistiques obtenues et de l optimalit en terme de p riode et de complexit lin aire taille du plus petit LFSR quivalent les polyn mes de r troaction utilis s sont primitifs On peut facilement obtenir des polyn mes primitifs avec SAGE sage def all_primitiv
3. de l AES d finie par la fonction inverse trans formation inversible pr s sur le corps GF 256 vu comme l anneau quotient GF 2 x zx8 x x34 x 1 Une g n ralisation param trable de l algorithme AFS est impl ment dans SAGE et on peut obtenir la la S Box AES de la mani re suivante sage sr mq SR 10 4 4 8 AES 10 tours avec une matrice 4 4 sur le corps GF 278 sage S sr sbox S est la Sbox AES de GF 2 8 vers GF 278 sage print S 99 124 119 128 242 107 111 197 48 1 103 48 254 215 171 118 202 130 201 125 250 89 71 240 173 212 162 175 156 164 114 192 183 253 147 38 54 63 247 204 52 165 229 241 113 216 49 21 4 199 35 195 24 150 5 154 7 18 128 226 235 39 178 117 9 131 44 26 27 110 90 160 82 59 214 179 41 227 47 132 83 209 0 237 32 252 177 91 106 203 190 57 74 76 88 207 208 239 170 251 67 77 51 133 69 249 2 127 80 60 159 168 81 163 64 143 146 157 56 2465 188 182 218 33 16 255 243 210 205 12 19 236 95 151 68 23 196 167 126 61 100 93 25 115 96 129 79 220 34 42 144 136 70 238 184 20 222 94 11 219 224 50 58 10 73 6 36 92 194 211 172 98 145 149 228 121 231 200 Chapitre 3 Manipulation de S Box avec SAGE 9 55 109 141 213 78 169 108 86 244 234 101 122 174 8 186 120 37 46 28 166 180 198 232 221 116 31 75 189 139 138 112 62 181 102 72 3 246 14 97 53 87 185 134 193 29 158 225 248 152 17 105 217 142 148 155 30 135 233 206 85 40 223 140 161 137 13 191 230 66 104 65 153 45 15 176 84 187 22 On peut aussi g n r
4. en polyn me est possible mais pas n cessaire pour les corps GF 2 avec k lt 16 librairie givaro sage K R 37 digits 2 K R I1 0 1 0 0 11 a 5 a 2 1 a 5 a 2 1 Cette conversion interm diaire en polyn me est obligatoire pour les corps GF 2F avec k gt 16 impl mentation ntl et GF p avec p 2 impl menta tion pari sage K GF 2 16 name a sage K 37 digits 2 Type rror unable to coerce sage R K x sage K R 37 digits 2 a 5 a 2 1 R ciproquement pour transformer un l ment d un corps fini GF 2 en un entier ou une liste de bits de GF 2 on convertit un l ment d un corps fini en liste de bits de GF 2 gr ce la m thode vector_space puis ventuellement en entier sage V K vector_space sage list V a 5 a72 1 ZZ list V a 5 a 2 1 2 1 0 1 0 O 1 0 0 37 Tl est noter que la librairie givaro utilise la repr sentation logarithmique et des tables de Zech Un corps non premier GF p avec p premier pour givaro p 2 et k gt 1 pour givaro k lt 16 peut tre repr sent par l anneau quotient des polyn mes de GF p zx modulo un polyn me primitif de degr k Il peut aussi tre repr sent par GF a o tout l ment non nul de GF a est une puis sance de a L l ment a appel g n rateur est une racine du polyn me primitif Avec cette repr sentation logarithmique la multiplication s crit af x a atti et l addit
5. f sage p K P Integer i digits 2 trace for i in range 2 n list f truth_table format int True L entr e d une fonction bool enne n variables peut tre un entier ou un binaire sur n bits en little endian bit de poids faible gauche f 1 f 1 0 01 True La sortie de la fonction bool enne est un bool en qui peut tre converti en l ment de GF 2 print f 0 GF 2 0 True 1 print f 1 GF 2 f 1 False 0 print f 0 f 1 1 Tl existe plusieurs op rations sur les fonctions bool ennes compl ment ad dition multiplication concat nation La premi re op ration est le compl ment de la table de v rit sage print f truth_table format int 15 007 05004 Lg Ly Lt sage print f truth_table format int 0 1 1 1 O O O 0 sage print polynomial_form f x 7 a 2 a x 4 a72xx72 axx 1 sage print polynomial_form f x 7 a72 a x 4 a72xx72 axx La deuxi me op ration est l addition de fonctions bool ennes correspondant l addition des tables des formes alg briques normales ou des formes polyno miales sage f f truth_table format int sage 1 1 1 1 1 1 1 1 sage g BooleanFunction x 7 sage h BooleanFunction a x 1 sage polynomial_form g h x 7 a 2 a x 4 a 2 x72 axx 1 La troisi me op ration est la multiplication de fonctions bool ennes corres pondant la multiplic
6. que l li 3 ordre lexicographique invers gradu degrevlex zlo l lt lo la lt gt V li lt Y l ou si S l Y L gt l pour le plus grand i tel que l l Tl existe plusieurs m thodes pour d finir un anneau polynomial multivari 1 On peut d finir des variables en les passant en param tre au constructeur PolynomialRing ou BooleanPolynomialRing sage R lt x y z k gt PolynomialRing GF 2 x y z k ou sage R lt x y z k gt BooleanPolynomialRing x y z k 2 On peut d finir des variables indic es automatiquement par exemple 10 variables zo zg auquelles on acc de par la notation 0 x 9 Les va riables sont alors ordonn es par ordre d croissant xg gt z gt gt Tg L ordre monomial est optionnel Attention la classe PolynomialRing uti lise l ordre monomial lexicographique invers gradu par d faut alors que la classe BooleanPolynomialRing utilise l ordre monomial lexicographique par Chapitre 4 Manipulation d anneaux polynomiaux multivari s avec SAGE 11 d faut sage R PolynomialRing GF 2 10 x order degrevlex sage x R gens sage p x 1 2 x 0 x 1 print p 1t leading term xOxx1 sage p x 1 3 x 4 x 3 2 x 4 2 x 2 4 print p x274 x173 x4 x372 x472 sage R term_order Degree reverse lexicographic term order sage R BooleanPolynomialRing 10 x order degrevlex sage x R gens sage p
7. 2 Pour affecter plusieurs variables il faut passer un dictionnaire variables va leurs en param tre de la m thode subs sage equations _filled_ list p subs k000000 0 k000001 0 for p in equations_list On peut galement construire un id al partir d une liste de polyn mes sage I R ideal equations_ list Pour tre complet les commandes Infinite Boolean PolynomialRing et Infinite Boolean PolynomialRing donnent respectivement la documen tation et le code source de la classe mais ne d taillent pas les m thodes im pl ment es Le manuel de r f rence permet d acc der la liste des fonctions et en fournit une description d taill e mais il vaut mieux avoir une id e du nom recherch Les documentations et sources respectives sont accessibles par les commandes suivantes 1 sage rings polynomial multi_polynomial_ring 2 sage rings polynomial infinite_polynomial_ring 3 sage rings polynomial pbori 13 Chapitre 4 Manipulation d anneaux polynomiaux multivari s avec SAGE La liste des m thodes disponibles peut aussi tre obtenue rapidement en cr ant un anneau polynomial R puis en utilisant la compl tion de ligne de commande Tl suffit alors de taper R et d appuyer sur la touche tabulation Chapitre 5 Manipulation de LFSR avec SAGE Un registre d calage r troaction lin aire ou Linear Feedback Shift Regis ter LFSR permet d engendrer une suite pseudo al
8. Chapitre 6 Manipulation de fonctions bool ennes avec SAGE Une fonction bool enne est une fonction f GF 2 gt GF 2 Elle peut tre repr sent e sous trois formes diff rentes 1 table de v rit x f x GF 2 2 forme alg brique normale fonction polynomiale de n variables coefficients dans GF 2 Cette criture comme somme de mon mes est unique f x 5 au T x QUec Ay Y fv uEeGF 2 r 1 v lt u 3 forme polynomiale trace d un polyn me univari coefficients dans GF 2 Cette criture peut tre unique sous la forme trace suivante f x 5 Tr a x e 1 21 iEn avec anensemble des repr sentants des classes cyclotomiques binaires mod 2 1 O i le cardinal de la classe cyclotomique de i wt f mod 2 Les fonctions bool ennes se d finissent dans SAGE l aide du constructeur Boolean Function sage from sage crypto boolean_function import BooleanFunction Les documentations et sources sont disponibles respectivement par la com mande BooleanFunction et BooleanFunction Il existe naturellement trois m thodes pour d finir une fonction bool enne La premi re utilise une table de v rit la liste des images des 2 l ments de GF 2 rang s dans l ordre des entiers qu ils repr sentent en little endian bit de poids faible gauche sage n 3 sage truth_table 0 1 0 0 0 0 0 0 sage f BooleanFunction t
9. LFSR est unique si et seule ment si la longueur de la suite est double de la taille du LFSR Attention dans SAGE la fonction lfsr_connection_polynomial donne le polyn me de r troaction alors que la fonction berlekamp_massey donne le polyn me carac t ristique Voici un exemple toujours avec le polyn me caract ristique 1 x x et de r troaction 1 x x sage sage sequence lfsr_sequence coefficients initial_state 2 l print berlekamp_massey sequence x 4 x 1 sage lfsr_connection_polynomial sequence XIA x 73 1 Pour des raisons de simplifications on propose une nouvelle impl mentation du calcul des bits de sortie d un LFSR partir directement de l expression de son polyn me de r troaction et de son tat initial sage def lfsr_output feedback_polynomial initial_state n new_state GF 2 i for i in initial _statel k len initial_ state c feedback_polynomial reverse coeffs 0 k L T for i in range n old_state copy new_state new_state new_state 1 k new_state append sum c i old_state i for i in range k l L append old_state 0 return L Voici un exemple avec le polyn me de r troaction 1 X X4 sage sage x GF 2 x gen print lfsr_output 1 x 8 x 4 1 0 1 1 n 1 O0 1 1 1 1 O O 05 1 O O 1 1 0 sage print lfsr_sequence coefficients initial_ state n lfsr_output 1 x 8 x 4 initial _state n True
10. MP ECM pour la factorisation des entiers en utilisant des courbes elliptiques une librairie cryptographique g n raliste Libg crypt ECLib pour l num ration des courbes elliptiques le logiciel de cryptogra phie OpenCDK ou une librairie Python de cryptographie Python Cryptography Tollkit PyCrypto impl mentant notamment des fonctions de hachage et les algorithmes cryptographiques cl publique Par ailleurs des fonctions de ha chage comme MD5 et la famille SHA sont fournies avec la librairie standard de Python Le logiciel SAGE offre galement une interface avec les logiciels propri taires Magma Maple et Mathematica Chapitre 1 Pr sentation du logiciel SAGE 4 La liste compl te des composants de SAGE est disponible l adresse suivante http sagemath org links components html 1 7 Utilisation de SAGE en cryptographie SAGE a t utilis d s sa cr ation comme outil d exp rimentation au profit de la recherche en cryptographie Ainsi M Albrecht a impl ment sur SAGE son attaque alg brique contre le Toy Cipher de N Courtois S Maitra et S Sarkar ont utilis le module de th orie des nombres de SAGE pour compl ter l ensemble des exposants RSA faibles Un autre exemple est le travail r alis avec SAGE par G Bertoni et al pour proposer le candidat Keccak comme famille de fonctions de hachage SHA 3 D autres travaux cryptographiques pour lesquels SAGE a t utilis ont t r alis s par M Albrecht et C C
11. Yannick Renard MANUEL D UTILISATION SAGE POUR LA CRYPTOGRAPHIE SYMETRIQUE d cembre 2010 Table des mati res Chapitre 1 Pr sentation du logiciel SAGE Lib Introduction ea e Gor aaa lat pa d TR Rage ARA a NOA 8 AT 0 UE 123 Contexte dede err C VD R S ND NEE b ROE 22 D RES do ASS NE ZE 24 Jigi ISTOTIQUE 0 15 26526 ritan Pan inaa rto rb en Cbr v nd Pa the an ARE tr nt 1 4 Modes d utilisation 1 5 Langage de programmation 1 6 Composants de SAGE 1 7 Utilisation de SAGE en cryptographie 1 8 Extension de SAGE pour la cryptographie Chapitre 2 Manipulation des corps finis avec SAGE Chapitre 3 Manipulation de S Box avec SAGE Chapitre 4 Manipulation d anneaux polynomiaux multivari s avec SAGE us Sels Mastaa GR mn D 6 NAATA e ARORA TT 2 2 Chapitre 5 Manipulation de LFSR avec SAGE Chapitre 6 Manipulation de fonctions bool ennes avec SAGE Bibliographies x 3 pass te Mae mets aile due ce te ar 4 O U S ND D ND N 10 14 16 20 Chapitre 1 Pr sentation du logiciel SAGE 1 1 Introduction Le logiciel Software for Algebra and Geometry Experimentation SAGE est un logiciel de math matiques qui rassemble de nombreux programmes et biblio th ques libres dans une interface commune bas e sur le langa
12. alRing 4 x order degrevlex sage R inject_variables Defining x0 x1 x2 x3 sage f BooleanFunction x0 x2 x3 x1 x2 x0 sage print f algebraic_normal_form x0 x1 x3 x1 x2 x3 Bibliographie 1 Y Renard Exp rimentations cryptographiques avec SAGE Th se professionnelle de Mast re sp cialis S curit des Syst mes Informatiques et des R seaux Telecom Paristech 2010 2 SAGE Mathematical Software version 4 4 4 http www sagemath org 3 P Zimmermann et al Calcul math matique avec SAGE 2010 http sagebook gforge inria fr
13. ation des tables des formes alg briques normales ou des formes polynomiales sage fx f truth_table format int 0 0 0 0 0 0 0 0 sage polynomial_form g h Chapitre 6 Manipulation de fonctions bool ennes avec SAGE 19 x 7 a 2 a x 4 a 2 x 2 a x On note que x x ax 1 ax x sur GF 23 et qu on a a toujours Tr a a x zt Tr a x x sur GF 23 GF 2 x lt z3 x 1 gt Enfin on peut aussi concat ner des fonctions bool ennes correspondant la concat nation des tables sage print g truth_table format int 0 1 1 1 1 1 1 1 sage print h truth_table format int 1 1 1 1 0 0 0 0 sage print glh truth_table format int 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 Attention bien que ce ne soit pas pr cis dans la documentation il existe une limite pour le nombre de variables d une fonction bool ennes li e la m moire de la machine sage R BooleanPolynomialRing 38 s sage s R gens sage print BooleanFunction s 0 Boolean function with 38 variables sage R BooleanPolynomialRing 39 s sage s R gens sage print BooleanFunction s 0 MemoryError Par ailleurs les fonctions impl ment es dans SAGE sont implicitement pr vues pour un ordre monomial lexicographique l ordre monomial par d faut du constructeur Boolean PolynomialRing Elles ne donnent pas le r sultat at tendu pour un autre ordre monomial sage R BooleanPolynomi
14. e n return p for p in GF 2 x polynomials siii of_degree n if p is_primitive True sage all_primitive 4 x 4 x 1 x74 x73 1 sage def primitive n generator p for p in GF 2 x 1 polynomials of_degree n if p is_primitive True pie return generator next sage primitive 100 x7100 x725 x724 x722 x720 x719 x718 x717 x716 x715 x714 x713 x712 x711 x710 x79 x78 x77 x76 x75 x74 x73 x72 x 1 Dans SAGE la fonction 1fsr_sequence key fill nb produit les nb bits de sortie s09 81 8Sn56 1 d un LFSR de taille n d fini par les n coefficients celui de z n est pas compt de son polyn me caract ristique key et par son tat _initial so s1 Sn_1 fill repr sent par une liste de n l ments de GF 2 La documentation et les sources sont accessibles respectivement par Chapitre 5 Manipulation de LFSR avec SAGE 15 les commandes sage crypto lfsr et sage crypto lfsr Voici un exemple avec le polyn me caract ristique 1 x x sage coefficients GF 2 i for i in list 1100 cO c1 c2 c3 sage initial _ state GF 2 i for i in list 1011 s0 s1 s2 s3 sage l len coefficients nombre de bits du LFSR sage n 2 1 1 p riode du LFSR sage print lfsr_sequence coefficients initial_state n Ld 0 21 45 Lo dr 0505 07 1757 05 07 a 01 L algorithme de Berlekamp Massey donne le polyn me de r troaction du LFSR de taille minimale engendrant une suite Le
15. e_rings element_givaro 2 sage rings finite_rings element_ntl_gf2e 7 7 3 sage rings finite_rings finite_field_ext_pari La liste des m thodes disponibles peut aussi tre obtenue rapidement en cr ant un corps fini K puis en utilisant la compl tion de ligne de commande Il suffit alors de taper K et d appuyer sur la touche tabulation Chapitre 3 Manipulation de S Box avec SAGE Une bo te de substitution ou S Box est un l ment de base de la crypto graphie sym trique Elle prend m bits en entr e et renvoie n bits en sortie La repr sentation enti re est souvent utilis e de sorte qu une S Box est d crite par sa table qui est une liste de ses images c est dire 2 entiers appartenant l ensemble 0 2 1 Dans SAGE le module sage crypto mq sbox py permet de construire fa cilement des S Box partir d un tuple d entiers sage S mq SBox 0 1 3 6 5 2 4 7 Par d faut la repr sentation de la S Box vue comme une fonction bool enne vectorielle est big endian le bit de poids faible est droite sage print S 3 S 0 1 11 6 1 1 0 La commande suivante est quivalente sage S mq SBox 0 1 3 6 5 2 4 7 big_endian True sage print S 3 S 0 1 11 6 1 1 0 On peut aussi pr ciser la repr sentation little endian le bit de poids faible est gauche sage S mq SBox 0 1 3 6 5 2 4 7 big_endian False sage print S 3 S 1 1 01 6 0 1 1 On peut consid rer la S Box
16. ence manual global module index Chapitre 2 Manipulation des corps finis avec SAGE Les corps finis se d finissent dans SAGE l aide du constructeur FiniteField ou GF On peut construire les corps premiers GF p avec p premier sage GF 11 Finite Field of size 11 sage x for x in GF 11 0 1 2 3 4 5 6 7 8 9 10 On peut aussi construire les corps compos s GF q avec q p p premier et k gt 1 un entier Un corps non premier GF p avec p premier et k gt 1 est isomorphe l anneau quotient des polyn mes de GF p x modulo un polyn me unitaire et irr ductible de degr k Dans ce cas il faut pr ciser outre le nombre d l ments le nom du g n rateur du corps sage K lt a gt GF 2 8 name a K K gen Finite Field in a of size 278 a sage K order K characteristic K degree 256 2 8 sage K modulus x78 x74 x73 x 2 1 Notons que l criture suivante est valide mais ne permet pas de cr er des l ments du corps comme polyn me en le g n rateur a sage K GF 2 8 name a sage y a 8 a 4 a 73 a 1 NameError name a is not defined Le polyn me irr ductible permettant de d crire le corps fini est choisi par d faut par SAGE On peut aussi le pr ciser lors de la cr ation du corps en ayant au pr alable d fini l anneau polynomial GF p x sage R lt x gt GF 2 x sage K lt a gt GF 2 8 name a mod
17. er des S Box al atoires Pour cela on d finit un uplet d entiers sage SBox_table tuple randint 0 15 for i in range 16 sage print SBox_table T 24 145 114 787 192 14 41 6 8 L 1 13 154 95 11 On d finit alors la S Box partir de sa table sage SBox mq SBox SBox_table On affiche les images de la S Box sage print SBox i for i in range 16 7 2 14 11 8 12 14 1 6 8 1 1 13 15 9 11 On peut aussi g n rer des permutations al atoires Pour cela on d finit une permutation sage permutation Permutations 16 random_ element sage print permutation 8 14 7 2 13 1 4 12 6 11 16 15 5 8 10 9 On d finit alors la S Box sage SBox mq SBox tuple i 1 for i in permutationl On affiche les images de la S Box sage print SBox 7 13 6 1 12 O0 3 11 5 10 15 14 4 2 9 8 Chapitre 4 Manipulation d anneaux polynomiaux multivari s avec SAGE Les anneaux polynomiaux multivari s se d finissent dans SAGE l aide des constructeurs PolynomialRing ou InfinitePolynomialRing ou Boolean PolynomialRing Pour les corps finis SAGE propose une seule interface et utilise plusieurs impl mentations de mani re transparente pour l utilisateur en fonction de la caract ristique et du degr Ce n est pas le cas pour les anneaux polyno miaux multivari s Par exemple un anneau polynomial multivari sur GF 2 d fini avec PolynomialRing utilise l impl men
18. ermes de la GNU General Public License GPL version 2 ou ult rieure Cette derni re autorise la copie l tude la modification l am lioration et la distribution de SAGE et de son code source SAGE int gre la plupart des logiciels open source et offre galement une interface avec les logiciels propri taires Magma Maple et Mathematica Une comparaison de SAGE avec entre autres Mathematica Maple et Matlab est disponible dans la th se de M V Nguyen Chapitre 1 Pr sentation du logiciel SAGE 3 1 3 Historique Le projet SAGE est r cent et a commenc en 2004 2005 sous l impulsion de W Stein professeur de l universit de Washington Des administrations comme le minist re am ricain de la d fense des entreprises comme Microsoft Google ou Sun ainsi que des donateurs priv s ont particip financi rement La premi re version SAGE 1 0 a t pr sent e lors des SAGE Days de San Diego en f vrier 2006 Actuellement le logiciel SAGE connait une nouvelle version toutes les une deux semaines enrichi par de nombreux d veloppeurs 1 4 Modes d utilisation Le logiciel SAGE a plusieurs modes d utilisation 1 Il peut tre utilis en ligne de commande 2 Tl peut ex cuter des programmes interpr t s ou compil s avec un compilateur Cython via un fichier py ou via un fichier spyx 3 Le mode le plus convivial est l interface graphique notebook Ce mode no tebook fonctionne avec un m canisme client serveur
19. et s utilise avec un na vigateur web Ce dernier permet de partager les ressources d une machine ou d changer des feuilles de calcul worksheet Il offre la possibilit d valuer directement des expressions comme de programmer des fonctions 1 5 Langage de programmation Au lieu de faire appel un langage sp cifique le logiciel SAGE utilise un lan gage de programmation quasiment identique au Python Les seules diff rences concernent les symboles de l exponentiation ou en SAGE en Python et de la division 2 3 est une fraction rationnelle en SAGE 2 3 est une division enti re en Python Le Python est un langage de programmation interpr t open source et tr s r pandu Il offre de nombreux avantages concernant l enregistrement d objets la gestion de la m moire la disponibilit de nombreux packages la portabilit le d bogage et le profilage Certaines parties du code et des biblioth ques devant fonctionner rapidement sont crites en langage compil 1 6 Composants de SAGE SAGE rassemble une grande quantit de logiciels et de biblioth ques sp cia lis es sous une m me interface Il int gre notamment le logiciel d alg bre GAP le langage de calcul Octave le logiciel de statistique R le logiciel d arithm tique pari GP le logiciel pour l alg bre commutative et non commutative et de manipulation de polyn mes multivari s Singular le logiciel de calcul formel Maxima Tl comprend aussi le logiciel G
20. ge de programma tion Python Il a pour ambition de devenir une alternative libre aux logiciels propri taires comme Magma Maple Mathematica ou Matlab Tl couvre un champ le plus vaste possible comme l alg bre l analyse la th orie des groupes la th orie des graphes la th ories des nombres l analyse et la cryptographie Les principaux objectifs de SAGE sont d une part de faciliter l exp rimenta tion d objets math matiques avec un logiciel rapide convivial bien document et open source et d autre part de favoriser la coop ration et la mise en commun des d veloppements r alis s 1 2 Contexte SAGE s inscrit dans un environnement de logiciels d di s aux math matiques d j nombreux que l on peut classer en trois cat gories 1 Logiciels propri taires payants a Mathematica http www wolfram com b Maple http www maplesoft com c Magma http magma maths usyd edu au magma d Matlab http www mathworks com 2 Logiciels propri taires gratuits a Kash Kant http www math tu berlin de kant b CoCoA http cocoa dima unige it 3 Logiciels open source a GAP http www gap system org b Macaulay2 http www math uiuc edu Macaulay2 c Maxima http maxima sourceforge net d Octave http www octave org e Pari GP http pari math u bordeaux fr f Singular http www singular uni kl de La particularit de SAGE est d tre distribu sous licence libre selon les t
21. id Y Aner G V Bard D J Bernstein et al D Boneh et al V Velichkov et al et R Weinmann 1 8 Extension de SAGE pour la cryptographie L un des objectifs de SAGE est de favoriser la coop ration et la mise en com mun des d veloppement r alis s Les fonctionnalit s de th orie des nombres corps finis et courbes elliptiques ont t impl ment es par l quipe de d velop pement de SAGE Sage Development Team en s appuyant sur les composants existants de SAGE Plusieurs modules d di s la cryptographie et r alis s par d autres d veloppeurs ont ensuite compl t les classes disponibles dans SAGE Ainsi la plupart des fonctionnalit s orient es cryptographie jusque dans la version 3 4 incluse du 11 mai 2009 ont t impl ment es par D Kohel Les classes sage crypto mq sbox et sage crypto mq sr permettant de manipuler des S box et de param trer AES ont t r alis es par M Albrecht La classe sage crypto block_cipher miniaes pour une variante simplifi e de PAES appel e mini A ES a t d velopp e par M V Nguyen La classe sage crypto boolean_function BooleanFunction permettant d tudier l immunit alg brique et le spectre de Walsh de fonctions bool ennes a t r alis e par Y Laigle Chapuy Tous ces apports au logiciel SAGE sont tr s r cents ils datent de 2009 et 2010 La liste compl te des classes SAGE et leur description est disponible dans le lo giciel SAGE en mode notebook par le chemin help refer
22. ion s crit a af a 1 a0V a x a707 o les valeurs de Z i Chapitre 2 Manipulation des corps finis avec SAGE 7 ont t mises en table appel e table de Zech sage y K _cache _element_log_repr a 5 a 2 1 y 36 sage y a 36 y a 5 a 2 1 On mentionne galement l existence des m thodes suivantes de la librairie givaro mais on pr f rera celles pr c demment voqu es dans un cadre plus g n ral et qui sont valables pour les trois impl mentations givaro ntl et pari sage K lt a gt GF 2 8 name a sage y Integer K _cache _element_int_repr a 5 a72 1 y 37 sage y K _cache _element_poly_repr a 5 a72 1 y a 5 a 2 1 Pour tre complet la documentation et le code source de la classe Finite FieldFactory sont obtenues respectivement par les commandes GF et GF qui ne d taillent pas les m thodes impl ment es Le manuel de r f rence permet d acc der la liste des fonctions et en fournit une description d taill e mais il vaut mieux avoir id e du nom recherch En fait SAGE utilise trois impl mentations diff rentes des corps finis selon leur caract ristique et leur degr 1 caract ristique 2 et degr lt 16 impl mentation givaro 2 caract ristique 2 et degr gt 16 impl mentation ntl 3 caract ristique 2 impl mentation pari Les documentations et sources respectives sont accessibles par les commandes suivantes 1 sage rings finit
23. ruth_ table sage print i f i for i in range 2 n 0 False 1 True 2 False 3 False 4 False 5 False 6 False 7 False l On peut v rifier la repr sentation little endian bit de poids faible gauche des entiers sage def rpad x n sn return Integer x digits 2 padto n sage print rpad i n f rpad i n for i in range 2 n Chapitre 6 Manipulation de fonctions bool ennes avec SAGE 17 0 0 0 False 1 0 01 True 0 1 01 False 1 1 0 False 0 0 11 False 1 0 1 False 0 1 1 False 1 1 1 False La table de v rit d une fonction bool enne de n variables peut aussi tre mise sous la forme d une cha ne de 2 caract res hexad cimaux rang s dans l ordre inverse de la table de v rit pr c dente sage f_hex BooleanFunction al1 sage f_int BooleanFunction 1 0 0 0 0 1 0 11 sage f_hex f_int True Tl existe donc plusieurs formats de repr sentation de la table de v rit sage print f truth_table format bin False True False False False False False False sage print f truth_table format int 0 1 O O 0 O O 0 sage print f truth_table format hex 02 On note bien l ordre invers entre le format hex et le format int La deuxi me fa on de d finir une fonction bool enne de n variables utilise sa forme alg brique normale un polyn me bool en n variables sage R BooleanPolynomialRing 3 x
24. tation LIBSINGULAR alors que BooleanPolynomialRing utilise la librairie C POLYyBORI La deuxi me classe infinite_polynomial_ring est moins efficace que la premi re polynomial_ring mais est plus souple d utilisation En effet elle permet de d finir un anneau polynomial avec un nombre d ind termin es qui augmente suivant les besoins ou avec plusieurs familles de variables La der ni re pbori est une impl mentation optimis e pour les anneaux de polyn mes bool ens Le constructeur PolynomialRing permet de d finir K z1 2 En o K est un corps alors que le constructeur BooleanPolynomialRing permet de d finir l anneau quotient GF 2 1 n lt x 1 xn gt Cela impliquera notamment que pour r soudre sur GF 2 un syst me de polyn mes multivari s d finis avec BooleanPolynomialRing il n est pas n cessaire de ra jouter les polyn mes x x1 2 Tn Un anneau polynomial multivari peut tre associ une relation d ordre total sur ses mon mes appel e ordre monomial La d finition de l ordre mono mial d pend de l ordre des variables On consid re ici comme dans SAGE que Xo gt 1 gt gt q Les principaux ordres monomiaux sont 1 ordre lexicographique lex A lt lo la lt gt l lt l pour le plus petit i tel que l l 2 ordre lexicographique gradu deglex LOL ARE lt lo ala lt gt d lt Y l ou si St V l lt l pour le plus petit i tel
25. ultivari s avec SAGE 12 Infinite polynomial ring in x y zZ k over Finite Field of size 2 4 Une quatri me m thode repose sur la cr ation d une liste de variables ob tenue en manipulant les cha nes de caract res puis pass e en param tre au constructeur PolynomialRing ou BooleanPolynomialRing sage def variable name round bit variable _list for i in range round for j in range bit variable _list append s4034 03d name i j return variable _list sage variable list variable k 2 3 print variable_ list L k000000 k000001 k000002 k001000 k001001 k001002 sage R ou PolynomialRing GF 2 variable_list order degrevlex sage R BooleanPolynomialRing len variable list variable _list order degrevlex sage R inject_variables Il faut noter que l ordre de la liste est important puisqu il d finit l ordre des variables qui peut influer par la suite sur la r solution de syst mes po lynomiaux multivari s Par ailleurs cette m thode est avantageuse en terme de lisibilit des variables mais pas en terme de temps d ex cution Une fois l anneau polynomial cr on peut instancier des polyn mes et affecter des valeurs connues certaines variables sage equations list k000000 k000001 k000000 k001002 sage equations _filled_ list p subs k000000 0 for p in equations _list sage print equations_filled_list k000001 k00100
26. ulus x 8 x 4 x 8 x 1 sage K modulus b aate x74 x73 x 1 On peut maintenant consid rer des lements du corps GF p sage y a 8 a74 a7 3 a 1 y 0 sage z K random_element z a 7 a 6 a 3 a sage p x75 x 2 1 K p a 5 a 2 1 Attention le modulus est d fini la cr ation du corps fini et l isomorphisme avec un anneau quotient GF p x modulo un autre polyn me irr ductible de Chapitre 2 Manipulation des corps finis avec SAGE 6 degr k n est pas impl ment sous SAGE sage L lt b gt GF 2 8 name b modulus x 8 x 4 x 3 x 2 1 sage L a 7 a 6 a73 a 1 TypeError unable to coerce from a finite field other than the prime subfield impossible de passer du corps K au corps L N anmoins on peut consid rer avec SAGE l isomorphisme canonique entre GF p et GF p Lorsque p 2 on pourra choisir pour GF p une repr sentation enti re ou binaire Pour transformer un entier ou une liste de bits de GF 2 en l ment d un corps fini GF 2 on convertit un entier en liste de bits puis en un l ment d un Corps fini sage R lt x gt GF 2 x K lt a gt GF 278 name a sage K 37 digits 2 K 1 0 1 0 0 11 a 5 a 2 1 a 5 a 2 1 sage K 37 1 Attention SAGE utilise ici la repr sentation little endian Par ailleurs K 37 renvoie 37 modulo la caract ristique du corps K et pas a a 1 Une conversion interm diaire
27. x 1 2 x 0 x 1 sage print p x1 xO0 x1 sage print p lt x1 x0 Il faut noter que la ligne x R gens est obligatoire pour pouvoir ma nipuler les variables sage R PolynomialRing GF 2 10 x sage print p x 0 x 1 TypeError x must have length self ngens La d finition suivante n est pas valide non plus sage R lt x gt PolynomialRing GF 2 10 x IndexError the number of names must equal the number of generators Si on veut manipuler les variables par la notation xi plus concise que x i il faut utiliser la m thode inject_variables sage p x2 print p NameError global name x2 is not defined sage R inject_variables Defining x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 p x2 print p x2 3 Une troisi me m thode consiste en la d finition d un anneau polynomial multivari avec un nombre d ind termin es qui augmente suivant les besoins sage R lt x y z k gt InfinitePolynomialRing GF 2 implementation sparse sage p x 0 x 1 x 2 print p x_2 x_1 x_0 sage p y 0 y 1 y 2 print p y_ 2 y_1 y_0 N anmoins ce type d anneau polynomial n est pas pris en compte par l im pl mentation de la mise en quation alg brique de S Box sage S mq SBox 7 6 0 4 2 5 1 3 sage S polynomials y 0 y 11 y 211 x 01 x 1 x 21 NotImplementedError Echelon form not implemented over Chapitre 4 Manipulation d anneaux polynomiaux m
Download Pdf Manuals
Related Search