Documentation succinte de gener1 (4 Février 2002) ---------------- Objectif : -------- gener1 permet de construire des clé publiques sous formes de systèmes d'équations booléennes, pour le système HFE de J. PATARIN. Le fichier de sortie unique s'appelle systHFE.txt. On travaille sur GF(2) et GF(2^n) uniquement. Il devrait être facilement réutilisable et modifiable Prérequis --------- Cette version est écrite pour Windows et utilise au minimum les appels à l'OS. Quel que soit l'OS utilisé ilfaut charger NTL v 5.1a (librairie C++). On trouvera sur la page web de NTL tout ce qu'il faut pour le faire. J'ai utilisé Microsoft Visual C++ de Visual Studio v 6.0 , un pentium 2 à 200 Mhz et 64 Mo de RAM. Pour porter sous Unix il suffit de prendre garde aux ouvertures de fichiers j'ai utilisé les iostream et la variable chemin (en tête du programme) qui devra désigner votre repertoire de travail. Contexte -------- J'ai développé très rapidement (2 jours) ce petit programme à partir de nombreux autres qui m'ont servi pour divers tests sur HFE. Je n'ai pas eu le temps de le vérifier gener1 sérieusement. Prudence donc. Tester d'abord sur de petits degrés. J'espère qu'il sera utile au moins comme exercice d'utilisation (élémentaire) de NTL et surtout comme base pour d'autres tests. Les donnees d'entrée : -------------------- Des données sont entrées interactivement (à l'écran) : Le nombre de variables : c'est le degré du corps fini sur F2 qui sera utilisé. L'option de saisie du polynôme secret. Le degré du polynôme : on doit impérativement le rentrer. D'autres données sont stockées sur un fichier texte. Le polynome secret : il y a deux façons de rentrer ce polynome 1/en le stockant sous forme de fichier dans polyHFE.txt 2/en laissant le programme générer automatiquement un polynôme aléatoire (option) du degré que vous avez indiqué D'autres données sont en dur dans le programme (certaines options par exemple). Voir plus bas le paragraphe Options. Les resultats : ------------- Ils apparaissent à l'écran et sont stockés sur le fichier systHFE.txt en mode "ajout". Chaque exécution du programme ajoutera donc ses resultats au fichier de sortie. Le format devrait être réutilisable dans des outils de calcul formel. J'ai simplement respecté (presque) le format des systèmes donnés par J. PATARIN dans son challenge1. On trouvera en plus le polynome correspondant au systeme perturbé Il manque le terme constant qui n'est autre que celui du système J'espere que la présentation est claire. Format de données pour le polynome secret : ----------------------------------------- Le corps fini GF(2^n) est défini par le nombre de variables n entré par l'utilisateur. NTL génère lui même un polynome irréductible I(X) convenable. La base utilisée sera fixe = 1,X, X^2, X^3,... On utilise le format de NTL pour designer les polynome ou les elements de GF(2^n). [0 0 1 0 1] désigne donc le polynome X^3+X^5. Cela peut être un élément d'un corps fini ou un polynôme binaire selon le contexte. On n'ecrit pas les 0 inutiles . Le vecteur precédent peut donc représenter un élément d'un corps de degré 10 par exemple. Il est inutile d'écrire les 10 coordonnées. Il est indispensable, pour comprendre le source et le modifier, de lire les documentations de NTL concernant les quelques librairies utilisées (voir l'en-tête du programme). Un côté désagréable de NTL est la nécessité de multiples conversions entre les types. Le format précédent ne convient pas pour représenter les polynomes quasiquadratiques qui peuvent avoir des degrés très importants. On utilise donc la représentation matricielle des polynôme quasiquadratiques. Je décris cette représentation brièvement ici. Pour plus de détails reportez vous à mon document "Etude de HFE". Si P est quasiquadratique il existe une matrice M a coefficients m_ij dans son corps de définition et une constante C du même corps, qui verifie : P(X)= (X X^2 X^4....X^2^(n-1)). M. transp(X X^2 X^4....X^2^(n-1)) + C Un polynôme quasiquadratique est donc stocké comme un couple : M (matrice) et C (terme constant). Exemple : Pour définir le polynome 1+X+X^3+X^6 dans GF(2^4)[X], on ecrira dans le fichier polyHFE.txt les données suivantes [1] [1] [] [1] [] [] [1] qui correspondent aux coeff des monômes quasiquadratiques par degré croissant. Le programme rangera ces coeff dans la matrice M [[[][1] [] []] [[][] [1] []] [[][][][]] [[][][][1]] ] et mettra [1] dans la variable correspondant au terme constant du polynome. Options : ------- différentes variables d'option dans le programme permettent 1/permet de générer des polynomes secrets aleatoires . On utilise donc pas le fichier polyHFE.txt. Cette option est entrée interactivement à l'écran. Nom de la variable : option_P Valeurs : 1 :entrée du polynôme par fichier texte (polyHFE.txt) de l'utilisateur 2 :génération automatique aléatoire d'un polynome de degré donné interactivement à l'écran. 2/ de désactiver la génération des polynomes de perturbation à droite et à gauche 3/ de désactiver les perturbations affines. Ces options 2/ et 3/ nécessitent de lire le source et de le modifier et donc de recompiler. Je n'ai pas eu le temps de passer les options dans un fichier texte par exemple, ou en arguments du programme. Nom de variable pour 2/ et 3/ :option_droite , option_gauche Valeurs : 0 elles désactivent les perturbation gauche ou droite. 1 perturbation aleatoire vectorielle 2 perturbation aleatoire affine. Extensions du programmes : ------------------------ Le programme est une esquisse qui devrait êtret facilement modifiable selon les besoins de chacun. Par exemple, on a souvent besoin d'introduire des boucles pour générer des séries de systèmes à fin de tests divers. Le programme n'utilise en rien les ressources du C++ (mais NTL si!). On n'a pas cherché à optimiser quoique ce soit. Manques : ------- On ne trouvera pas : 1/ de routines pour passer en base normale 2/ de routines de resolution des equations algébriques sur un corps fini (c'est dans NTL). 3/ de routine d'importation d'un système (ou d'un polynôme) donné sous forme d'un fichier texte (par exemple récupération du challenge1 de Patarin). 4/ de routine pour fixer des perturbations gauche et droite (facile à faire) 5/ vérification : il serait souhaitable d'écrire de routines d'auto-vérification. Je n'ai pas eu le temps de le faire pour gener1. La méthode de calcul du système associé utilisée dans gener1 est la plus ancienne de celles que j'ai utilisées. Je n'ai pas eu le temps d'intégrer les nouvelles manières par soucis de faire la chose de rapidement. Il y a plus agréable en utilisant la matrice discriminante. 1/2/3/4/ on déjà été écrits. Si vous en avez besoin ... demandez. Tests et Limites ---------------- On peut utiliser des degrés >=1 mais toujours avec une ecriture binaire de poids >=2. Par exemple de degré 7 n'est pas accepté. Des dimensions de corps arbitraires sur GF2, compatibles avec la memoire disponible. Les temps de calculs permettent de travailler au moins sur 80 variables (par exemple). Encore une fois il est important de faire des tests. Pour cela : prendre des petits corps et des petits degrés, car les calculs manuels deviennent très vite infaisables. Version future : -------------- A bientot pour gener2 si cela vous est utile ? Je compte sur vos remarques (indulgentes) Version actuelle : ---------------- gener1.cpp polyHFE.txt (exemple de fichier pour entrer un polynome secret fixé par l'utilisateur) systHFE.txt (exemple de sortie)