notes de cours - Institut Fourier
Contents
1. entiers 2 adiques avec v 0 oo dans tous les cas avec a and b unit s dans Rom d finir Ta Ram Rom par JUR CAE CO CO A EE Y o z 2 9 y signifie x 2 9 z dans Rom Propri t s Ta est bijectif Ta b 1 2Rom 2Rom et T 2Rom 1 2Rom Tab est d ordre 2 si et seulement si v a 1 gt 2 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 26 al a et cryptographie avec point de vue dynamique Propri t s suppl mentaires Rappel lat a Cd ne Xs o e Faits l mentaires La formule x d finit T sur Zo mais ici 2 9 5 signifie de d caler le d veloppement binaire de Hensel de x de v x digits i e BOOT Os 2g 0 T ais By os Joie op cs Notons cp cp 1 92122 Z2 cg Ck 1 0 X amp 1 un cylindre typique de Z de taille k Si v a 1 gt 2 alors Tap agit comme une permutation circulaire sur l ensemble des cylindres de taille k elle se superpose la permutation correspondante sur l ensemble des cylindres de taille k 1 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 2T al a et cryptographie avec point de vue dynamique Cons quences Theorem P L non publi Supposons v 1 a gt 2 La transformation Tap Z Zo est continue uniquement ergodique de mesure invariante la mesure de Haar elle2. partir de A V et de variables bool ennes de sorte que le nombre de signes op ratoires soit polynomial en nombre de portes en version c bl e D finition Yao Le g n rateur G de type h est dit pseudo al atoire polynomial non uniforme si 1 il existe une algorithme qui calcule G x pour x k donn en entr e x LUN B us E 2 pour toute famille C de circuits bool ens la suite des probabilit s uj UnoG est indistinguable aux moyens des circuits de C de la distribution uniforme Uj n pour tout t gt 1 ig s 1 U lC 1 a pour tout n assez grand P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 41 al a et cryptographie avec point de vue dynamique Construire des g n rateurs de nombres cryptographiquement s r Revient en pratique construire des applications sens unique EN er au sens algorithmique tant donn e une valeur image y G x al atoire la valeur de x ne peut pas tre calcul e au moyen d un algorithme polynomial en la longueur de y P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 42 al a et cryptographie avec point de vue dynamique Exemple 1 le g n rateur RSA Initialisation Choisir deux grands nombres premiers p et q et calculer n grand signifie gt 1024 digits et 9 p 1 q 1 Choisir e 1 e par exemple e 3 pour faciliter les
3. Randomness and cryptography with a dynamical point of view Pierre LIARDET en collaboration avec Alexis BONNECAZE Universit d Aix Marseille Partie 1 tirer au hasard v nement impr visible al a Partie 2 G n rateurs de nombres al atoires RNG P L amp A B Grenoble juin 2014 Workshop dynamics and number theory al a et cryptographie avec point de vue dynamique 1 tirer au hasard v nement impr visible al a Usages e au quotidien jeux de hasard loteries roulettes de casino d s cartes chantillonnages e simulation num rique analyse calcul num rique m thode quasi Monte Carlo tests de validit de certains algorithmes e algorithmes stochastiques am lioration it rative recuit simul algorithmes g n tiques des fourmis e distribution uniforme pr assign e e g n rateurs de nombres P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 2 al a et cryptographie avec point de vue dynamique D finitions de l al a a mots al atoires effectif Complexit de Kolmogorov K w d un mot binaire w plus petit programme qui calcule w sur une machine de Turing Kolmogorov 1965 Chaltin 1966 Martin Lof 1966 Plus pr cis pour une machine universelle de Turing U K w est la plus petite longueur de l entr e d un mot binaire e dans U 4 code de la table des transitions qui donne en sortie w K
4. EST gt avec t T i 0 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 30 al a et cryptographie avec point de vue dynamique Construction arithm tique Soit K l extension de Q non ramifi e de degr m et A son anneau des entiers Alors GR 2 m A 2 K est l extension cyclotomique d ordre 2 1 de Q les repr sentants non nuls 2 de Teichm ller sont les racines 2 1 i mes de l unit Avantage de cette construction GR 2 m est une approximation du groupe compact A des entiers de K utile pour une approche dynamique se g n ralise tout corps de nombres local k extension non ramifi e de corps r siduel isomorphe une extension donn e du corps r siduel de k P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 31 al a et cryptographie avec point de vue dynamique Construction fondamentale Fonction inversive sur les anneaux de Galois R GR 2 m Tout l ment de R s crit 2 x avec 0 lt e l et x R groupe des inversibles Construction Q9 R 5 R o 2 r 2 ax b et 0 avecacJT etbe T Suites engendr es les orbites suivant Point de vue dynamique On fait tendre l vers l infini capture de l anneau local A l application se prolonge en une transformation Ta AA Th or me P Liardet non publi La transformation T est uniquement ergodique isomorph
5. a A S ensemble des symboles de sortie T E S fonction de sortie Fonctionnement associer tout mot w w1 w A le symbole fo w T O by 0 0 hy eo P L amp A B Grenoble juin 2014 Workshop dynamics and number theory T al a et cryptographie avec point de vue dynamique L application fa A gt S est dit automatique d automate a Plusieurs automates a d finissent la m me fonction automatique f fa Il est int ressant de minimiser le nombre d tats de o e Caract risation fa A S est automatique si la relation d quivalence de Nerode sur A ww Vv A fa wv fa w v n a qu un nombre fini de classe w fa est alors automatique pour l automate minimal a A A 7 o A est la classe du mot vide d w wa et T w falw Th or me de la pr diction A Broglio P L La suite c de symboles de S JLS q est q normale si et seulement si pour tout automate a d alphabet S on a QS EU 0S ken fa ri ok k 1 n n q li P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 8 al a et cryptographie avec point de vue dynamique Normalit et pr diction Le th or me pr c dent dit qu une suite o de q symboles est q normale s il n existe pas de fonction automatique f S S qui puisse pr dire les digits suivants plus pr cis ment Tr Tox 1 re Hk 0 Sk lt n falai
6. s dans un tableau T de 4 lignes en 4 colonnes m me d coupage K pour la clef en 4 lignes de 4 6 ou 8 colonnes selon la taille de la clef un octet correspond un l ment du GF 2 espace vectoriel GF 2 GF 2 X X X X X 1 L AES effectue plusieurs tours 10 12 ou 14 selon la taille de la clef constitu s de transformations l mentaires SubBytes SB T ShiftRows SR T MixColumns MC T AddRoundKey ARK T K KeysExpansion KE K P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 62 al a et cryptographie avec point de vue dynamique Initiation entr e du message en tableau T et de la clef en tableau K ex cution sur K de KE puis ARK sur T K premier tour SB SR MC ARK r p tions du premier tour jusqu l avant dernier dernier tour SB SR ARK e La transformation SubBytes n est pas lin aire c est elle qui nous int resse elle compose une fonction inversion g chaque octet x dans GF 25 non nul de T est remplac par son inverse g x l octet nul est conserv g 0 0 une fonction affine f x Az c R sultat sur chaque octet h x gt A g x c En pratique courante h est donn e par une table Sbox e Les transformations ShiftRows MixColumns AddRoundKey sur T sont lin aires P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 63 al a et crypt
7. 1 G n rateur congruentiel lin aire f Z mZ Z mZ f x ax c En 1 An c mod m avec c m 1 le plus ancien et le mieux connu facile programmer temps d ex cution court Probl mes sensible au choix des param tres a c rn inutilisable en cryptographie live mainly in planes W Givens Mais int ressant d un point de vue dynamique P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 18 al a et cryptographie avec point de vue dynamique Th or me classique La p riode de f est m maximum si et seulement si les trois conditions suivantes sont v rifi es i pgcd c m 1 ii Si p premier divise m alors p a 1 iii Si m est un multiple de 4 alors 4 a 1 Cons quence dynamique Notons Z l anneau des entiers p adiques et soit p Zp gt 0 1 l application de Monna en base p y ao 01 02 Yop SE Corollaire Soit p premier et a c entiers tels que p c pla 1sipz2et4 a 1 si p 2 alors la transformation T Zp gt Z d finie par T x ax c est uniquement ergodique et pour tout o Zp la discr pance de la suite n gt p T 5 est d ordre minimal N Duli lt C slagiV P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 19 al a et cryptographie avec point de vue dynamique Exemple 2 Registre d calage Construire pour gt 1 donn des suites
8. 2012 e Au lieu de repr senter GF 25 par GF 2 G X Q avec le polyn me R X X44 X X 1 on randomise la construction de GF 2 en des tours d extensions une extension biquadratique fix e suivie d extensions quadratiques GF 2 GF 2 Q 4 P 2 Il y a3 polyn mes biquadratiques irr ductibles sur GF 2 dont deux primitifs P z z yz A irr ductible sur GF 2 Q 2 il y en a 120 Le calcul de l inverse se fait en soft avec ou sans l aide d une table peu encombrante inversion dans GF 2 Q le calcul de l inverse de x fait intervenir le calcul de la norme de x dans l extension GF 25 GF 2 Q e La construction de GF 2 revient construire une base crite dans la repr sentation GF 2 X R sous la forme LEY 5y y y 9 1 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 66 al a et cryptographie avec point de vue dynamique e Les valeurs des normes sont mal distribu es dans cette randomisation on les masque en rempla ant xr par xm m thode 1 m uv sans couvrir tous les cas mais suffisamment m thode 2 m est choisi al atoirement dans un syst me complet de repr sentants des classes cyclotomiques la norme est constante sur ces classes e La m thode a t implant e sur carte puce et test e statistiquement pour deux types classiques d attaque par entropie par corr lation en co
9. S t k v c est un t v k 1 design P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 50 al a et cryptographie avec point de vue dynamique Exemple d un Syst me de Steiner Bas sur le code binaire de Golay Go les octades blocs sont les mots du code de poids 8 les 8 sous ensembles Tout vecteur binaire de longueur 24 v 24 de poids 5 5 sous ensemble est recouvert par exactement une octade de 654 Le code de Golay construit donc un syst me de Steiner S 5 8 24 Ici Y 1 24 et les blocs sont les parties de Y construites partir des positions indices des 1 dans les octades Illustration Un 5 ensemble 010000010010100000000100 L octade le recouvrant 010010010010110001000100 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 51 al a et cryptographie avec point de vue dynamique Groupes des automorphismes de G24 C est le groupe de Mathieu M4 Mo4 210 33 23 11 7 5 Il est 5 transitif sur les octades Il est engendr par 4 permutations op rant sur les 24 coordonn es du vecteur code index e sur l espace projectif F23 U oo S thHitl Voie E W oo 00 0 oo W i i 2 si i est un r sidu quadratique modulo 23 W i 2i sinon P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 52 al a et cryptographie avec point de vue dynamique Marche al
10. calculs d exponentiation G n rateur D BUT 1 Choisir au hasard zo 1 lt zo lt n 2 Calculer successivement 5 43 mod l 4 L d BOPUT 23 234 00000 2 p m p mod 3 FIN La s curit du g n rateur repose sur l impossibilit actuelle de factoriser n en un temps polynomial en log n P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 43 al a et cryptographie avec point de vue dynamique Exemple 2 le BBS d j vu C est un RSA avec ade e p et q sont congrus 3 modulo 4 e r5 est un carr BBS est Consid r comme cryptographiquement s r mais comme le RSA e il est lent m me en utilisant le th or me des restes chinois e certaines valeurs initiales sont liminer comme par exemple zo 1 e La longueur de p riode T x des sorties z x mod 2 est un diviseur de A A n o A est la fonction de Carmichael APE pit ppem Z 2 Z Z pt Z Z p Z e Si 2 est d ordre A A n modulo A n 2 et si x est d ordre A n 2 modulo m alors To e AA P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 44 al a et cryptographie avec point de vue dynamique Alternatives aux algorithmes e Utiliser des propri t s physiques notamment les sources d al as produites par des architectures lectroniques sur silicium ou les tats instables des donn es d entr e et de communications internes dans un o
11. est donc pas al atoire au sens de Knuth P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 10 al a et cryptographie avec point de vue dynamique Test statistiques D finition pragmatique d une suite binaire finie al atoire Suite qui passe les tests du NIST National Institut of Standards and Technol ogy Soit T un test sur l ensemble des suites binaires finies de longueur L muni de la probabilit uniforme Ur Alors T est une variable al atoire T 10 11 eR Elle d termine une loi de probabilit Pr sur R Une suite finie tester x 0 1 est vue comme un chantillonnage issue d une suite de variables al atoires ind pendantes X i 1 L valeurs dans 0 1 et de loi uniforme Il s agit de fixer les conditions pour que la valeur T x1 appartienne un intervalle validant le test hypoth se nulle la suite test e est alors d clar e al atoire pour le test P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 11 al a et cryptographie avec point de vue dynamique Liste des tests 1 Monobit test D termine si la fr quence des 0 est celle statistiquement attendue pour une suite al atoire vraie Recommandation longueur de la suite gt 100 Description poser X 27 1 Calculer Sn X H Xn Calculer la statistique T Es Calculer la probabilit FECN T a ee et dt fonction erreur du co
12. N 2V2np 1 p R gle de d cision si PR x lt 0 01 le test n est pas r ussi la suite est non al atoire P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 14 al a et cryptographie avec point de vue dynamique Les autres tests 4 Test for the Longest Run of Ones in a Block 5 Binary Matrix Rank Test matrices 32 x 32 construites par les suites de blocs de longueur 32 de la suite x 6 Discrete Fourier Transform Spectral Test 7 Non overlapping Template Matching Test 8 The Overlapping Template Matching Test 9 Maurer s Universal Statistical Test 10 The Linear Complexity Test 11 The Serial Test 12 The Approximate Entropy Test 13 The Cumulative Sums Cusums Test 14 The Random Excursions Test 15 The Random Excursions Variant Test 16 Lempel Ziv compression P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 15 al a et cryptographie avec point de vue dynamique 2 G n rateurs de nombres al atoires Essentiellement deux types de g n rateurs les pseudos ou algorithmiques les vrais ou physiques G n rateur de nombres pseudo al atoires PRNG D finition Cas binaire algorithme d terministe qui prend en entr e un mot binaire de longueur graine et donne en sortie un mot binaire de longueur L grand devant qui apparait comme tant al atoire selon les applications recherch es test de validat
13. Ok Sj Op i n TL q Cette condition peut tre affaiblie D finition Une suite o n S est dite pr dicable si elle v rifie pour une application automatique f ne d pendant que des derniers digits ox_p11 0k pour k gt Th or me c est q normale si et seulement si pour tout elle n est pas pr dicable P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 9 al a et cryptographie avec point de vue dynamique Normalit et al a e Peut on d finir une suite al atoire sur q symboles comme une suite q normale D apr s D Knuth ce n est pas un bon choix On aimerait que la suite o v rifie R gle R5 Toute suite extraite o i calculable de o i e il existe un algorithme effectif A tel que s k 1 2 2 n A n o1 04 1 est q normale Il suffit en fait de supposer plus simplement que chaque symbole appara t dans os x avec la fr quence 1 q D finition de D Knuth Une suite c de q symboles est dite al atoire si pour tout algorithme effectif qui d termine une suite infinie d entiers tn positifs distincts comme fonction de n et des valeurs pr c dentes o4 04 la suite c1 n v rifie la r gle R5 Ainsi soit x une suite binaire 2 normale et soit x d finie par p si n n est pas une puissance de 2 x n 0 sinon La suite x est encore 2 normale mais elle ne v rifie pas la r gle R5 elle n
14. atoire sur un groupe fini G Elle est donn e par e un probabilit Q Q g gE G e Une chaine de Markov homog ne espace des tats G probabilit initiale Q matrice de transition T p Q gh La marche M est construite au moyen d une suites de variables al atoires i i d valeurs dans G de loi Q Mn 1 XnMn Faits Si 19 Q g gt 0 engendre G la cha ne est irr ductible et sa distribution stationnaire est la probabilit uniforme U G sur G si la chaine est irr ductible et ap riodique i e m langeante la loi de distribution de M converge pour la variation totale vers U G vitesse exponentielle P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 53 al a et cryptographie avec point de vue dynamique Probl mes Trouver une majoration effective de cette rapidit de convergence Si le groupe est gros avec un syst me E de g n rateurs petit et s il op re sur un ensemble M pas trop gros alors on peut g n ralement r pondre de mani re satisfaisante au probl me pr c dent en effectuant une marche markovienne homog ne sur un ensemble fini M avec un ensemble E de bijections Y de M La marche est sym trique si E est stable en passant aux bijections r ciproques Posons u M X FE La matrice de transition stochastique sym trique est 1 T Y X YEE o Y est la matrice repr se
15. binaires p riodiques de p riode T telles que les mots de longueur apparaissent avec une fr quence 1 2 donc T gt 2 Exemple de construction La suite p riodique cherch e est vue comme un mot circulaire de De Bruijn Sa longueur est 2 On construit en fait un mot circulaire de longueur 2 1 o tous les mots de longueur sauf 0 apparaissent on ins re ensuite un 0 en bonne place e M thode Choisir un polyn me P X irr ductible de degr sur le corps F2 D veloppement en s rie formelle 1 a X a ay Fo P X La suite des ax v rifie une relation de r currence lin aire d ordre Un bloc B de l coefficients successifs d termine tous ceux qui suivent P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 20 al a et cryptographie avec point de vue dynamique 7 e e d Si T est la p riode de la suite a il y a T blocs B cons cutifs distincts et BY est un polyn me sur F Donc les racines C de P v rifie 7 1 En prenant P X polyn me primitif les racines sont d ordre maxi 2 1 dans le groupe cyclique Fe on obtient une suite ao a1 cherch e Ilya eG polyn mes primitifs sur F de degr e R alisation registre d calage lin aire Il s agit de calculer les a d une suite r currente lin aire ai aj ih 1 d ag gril aj cho associ e a
16. carr L inverse de z z sur les carr s est alors p 1 q 1 4 8 E mod n choisir un zo r sidu quadratique modulo n construire une suite x telle que x x4_ mod n sortir la suite binaire b bob b2 d finie par b Tj mod 2 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 34 al a et cryptographie avec point de vue dynamique Floril ge de g n rateurs G n rateurs reposant sur la th orie des codes correcteurs e Ils sont comme le BBS trop lents pour tre utilis s dans de nombreuses applications pratiques cartes puces G n rateurs bas s sur les algorithmes de chiffrement par bloc DES AES fonctions de Hachage Multiples combinaisons litt rature abondante N cessit de prot ger le code de l algorithme ou ses impl mentations hard contre les attaques par canaux cach s qui analysent de possibles fuites d information au cours du fonctionnement attaques par consommation de puissance par injections de fautes sur transfert de bits locaux Diabolisation Les algorithmes de chiffrement doivent aussi tre prot g s masquage des donn es trait es par l algorithme au moyen d un bon g n rateur qui doit lui m me tre prot g par P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 39 al a et cryptographie avec point de vue dynamique Partie 3 G n rateurs de nombres al at
17. ctades de mani re sym trique en utilisant l action des automorphismes pris al atoirement dans Peleo LV WW Param tres u 759 octades x 8 E k 7 D o explicitement d 292 1117 e P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 57 al a et cryptographie avec point de vue dynamique Algorithme G5 24 N INPUT N OUTPUT un vecteur binaire de poids 5 de longueur 24 a choisir une octade m b remplacer m par m par mise O des 3 premiers 1 c faire agir al atoirement sur m les l ments de E d r p ter N fois et sortir le mot m Pour la mis en oeuvre de l algorithme on a utilis le g n rateur BBS P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 58 al a et cryptographie avec point de vue dynamique N f 100 60 40 20 25 Le diagramme suivant repr sente les r sultats statistiques obtenus avec une marche tr s courte N f est le nombre d octades obtenues f fois au cours de 7590 marches de longueur 11 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 59 al a et cryptographie avec point de vue dynamique Autres exemples G n rateur 5 parmi 12 On utilise le code de Golay ternaire code sur GF 3 de param tre 12 6 6 Il conduit un 5 12 6 1 design permettant de construire par la m thode d crite un g n rateur 5 parmi 12 L tude de l actio
18. e permet de d terminer la complexit pr fixe K P w de Kolmogorov le mot binaire infini z zgzi2z2 est al atoire si iem K P xo Bde duca n TU 1 Dans ce cas x passe tous les tests statistiques tels que 1 i elim 7 Dien Ti 3 e x est k quir partie pour tout k gt 1 donc est 2 normal P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 5 al a et cryptographie avec point de vue dynamique Solution 2 Passer par la notion de sous ensemble A de 0 1 Martin L f mesurable de mesure de Lebesgue 1 L intersection M de tous ces sous ensembles est encore Martin L f mesurable de mesure 1 Les l ments de M sont dits al atoires au sens de Martin L f P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 6 al a et cryptographie avec point de vue dynamique c D finition statistique th orique Source uniforme sur q symboles D finition G n rateur de suite o 010203 de symboles o pris dans un ensemble S de q symboles telle que les mots a am S apparaissent dans c avec la fr quence q distribution uniforme Une telle suite est dite q normale Caract risation par automates Rappels Automate a sur un alphabet A 0 1 r 1 a E e0 6 T S avec E espace des tats en nombre fini avec s lection d un tat initial eo o ensemble des instructions E EF
19. e l odom tre x gt x 1 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 32 al a et cryptographie avec point de vue dynamique Pour en savoir plus sur les RNG Les exemples donn s ci dessus ont t choisis parmi une large famille de g n rateurs en usage dont LCG Linear generator SRG shift register generator ICG Inversive Congruential Generator EICG Explicit Inversive Congruential Generator Pour une description d taill e de nombreux types de g n rateurs de nombres et leurs propri t s leur codes en C les tests statistiques usuels et des liens utiles sur ce sujet consulter le site http random mat sbg ac at certains de ces g n rateurs se pr tent bien la construction de transformations uniquement ergodiques engendrant des suites dans 0 1 bien quir parties mod 1 de faible discr pance P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 33 al a et cryptographie avec point de vue dynamique Du c t cryptographie que choisir Plusieurs solutions ont t propos es cas binaire La plus classique G n rateur pseudo al atoire Blum Blum Shub BBS prouv s r cela sera expliqu dans le prochain expos D finition choisir deux grands nombres premiers p et q congrus 3 modulo 4 2 n pq Motivation si z a a une solution mod n alors il y en a 4 et une seule est un
20. eld Constructions Designs Codes ans Cryptography 2012 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 70
21. est m triquement conjugu e l odom tre x gt x 1 Preuve Bas e sur l observation suivante toute 2 i me racine de l unit est valeur propre de l isom trie sur L Z2 u associ e Tab de fonction propre 25 1 z L tude pr c dente donne Corollaire Pour tout x Zo la suite n p T x est bien quir partie mod 1 de discr pance en O log N N P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 28 al a et cryptographie avec point de vue dynamique Elargissement du domaine de construction Il existe une classe d anneaux incluant ZA et Fom e L anneau de Galois G R 2 m Mise en place Unique extension de Galois de degr m de l anneau Zo Il est de caract ristique 2 de taille 2 Exemples GR 2 1 Zu GR 2 m Foam Objet alg brique naturel pour tudier les r currences lin aires sur Zo P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 29 al a et cryptographie avec point de vue dynamique Construction pratique GR 2 m Za X h X o h X est irreductible unitaire de degr m relev d un polyn me de F2 X e R GR 2 m est un anneau local d id al maximal 2 de corps r siduel R 2 Fom Les repr sentants dit de Teichm ller des classes de ce quotient sont T 0 1 2 21 avec racine de h Tout x R admet un unique d veloppement 2 adique
22. ion Applications concr tes 1 cryptographie cl s pour chiffrement flots 2 valuation num rique m thode Quasi Monte Carlo 3 optimisation explorations al atoires guid es 4 simulation volution de syst mes math matiques ou physiques P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 16 al a et cryptographie avec point de vue dynamique Principe g n ral Pour un ensemble donn E construire une application f E E telle que E soit l unique orbite de f Pour tout a E E f a 0 k lt 4E Modele Soit A un alphabet fini D finition g n rale Soit h N N une suite croissante telle que h n gt n pour tout n Un g n rateur al atoire de type h est une application G A A telle que la restriction Gj de G A not e Gn soit valeurs dans A pour tout n N Il est alors habituel de mettre sur chaque ensemble A la loi de probabilit uniforme Um L objectif est que G induise sur les A des distributions D qui asymptotiquement s approchent de la distribution uniforme Uj suivant un cahier de charges sp cifiques passer une batterie de tests D ne peut tre distingu e de la distribution uniforme U par un algorithme de complexit polynomiale P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 17 al a et cryptographie avec point de vue dynamique Exemple
23. mparant quatre mise en oeuvre des tours d extensions Impl mentations sur AVR 8 bits AT mega 256 processsor Resultats comparaison entre la m thode par une tour d extensions TFC la randomisation par 4 tours d extensions RTFC 4 la randomisation avec 512 tours d extensions RTFC 512 et la randomisation 4 tours masquage des normes type 1 RTFC 4 Method 1 Cette derni re est la plus performante P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 67 al a et cryptographie Guessed entropy avec point de vue dynamique 200 RTFC 4 RTFC 512 x RTFC 4 Method1 150 MM 88 Ga6 g08 na 00000000 60ga00l 100 50 0 0 50 100 150 200 250 300 350 400 450 500 Number of curves Side channel attacks using guessed entropy P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 68 al a et cryptographie avec point de vue dynamique First order success rate 0 50 100 150 200 250 300 350 400 450 500 Side channel attacks using guessedfirst order success rate metrics P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 69 al a et cryptographie avec point de vue dynamique R FERENCES A Bonnecaze et P Liardet Uniform Generators and Combiatorial Designs International J on Advances in Networks and Services vol 4 No 1 amp 2 2011 A Bonnecaze P Liardet et A Vinelli AES Side Channel Countermeasure using Random Tower Fi
24. mpl ment pour la loi normale R gle de d cision si FECN T lt 0 01 le test n est pas r ussi la suite est non al atoire P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 12 al a et cryptographie avec point de vue dynamique 2 Frequency Test within a Block Recommandation longueur de la suite gt 100 Description Subdiviser la suite x1 x en N N M blocs disjoints B de longueur M Calculer la proportion p des 1 dans M Calculer la statistique T x 4M D Pi 1 2 Calculer FECG N 2 T 2 o FECG a 0 a e 4 dt fonction erreur du compl ment pour la loi de param tre a R gle de d cision si FECG N 2 T 2 lt 0 01 le test n est pas r ussi la suite est non al atoire P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 13 al a et cryptographie avec point de vue dynamique 3 Runs test Un run de longueur k dans x est une suite ininterrompue de k bits identiques et de longueur maximale Le test d termine si le nombre de runs de 0 et de 1 est celui statistiquement attendu pour une suite al atoire Recommandation longueur n gt 100 Description Calculer la fr quence des 1 p J a Si p 1 2 gt 2 n le test a chou Sinon calculer la statistique V x 1 3 4 l r k r k 0 si xy zg41 et r k 1 sinon 7 _ Vn z 2np 1 p Calculer PRU FEC
25. n du groupe des automorphismes donne xy 8 k 6 la vitesse de convergence vers la distribution uniforme est donn e par d 146 837 e77 G n rateur 2 parmi 31 Ce g n rateur est bas sur un 2 31 7 7 design et utilise un g n rateur 2 parmi 7 gr ce un 2 7 3 1 d sign G n rateur 3 parmi 16 Il utilise un 3 16 12 55 design Dans ce cas x 8 et amp 6 et d 148 837 e77 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 60 al a et cryptographie avec point de vue dynamique Contre mesure pour l AES L AES Advanced Encryption Standard Laur at 2000 du concours AES Algorithme sym trique de chiffrement propos par J Daemon et V Rijmen input output blocs de 128 bits clefs de 128 192 ou 256 bits ce jour attaque exhaustive hors d atteinte utilis dans de nombreux syst mes embarqu s nombreux travaux sur les contre mesures pour les attaques par canaux cach s side channel attacks Les m thodes classiques de contre mesures consistent randomiser les r sultats interm diaires P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 61 al a et cryptographie avec point de vue dynamique Description rapide de l AES e Le chiffrement des 128 bits Input output message d coup en blocs de 128 bits Chaque bloc tat est d coup en octets 8 bits plac
26. ntant la bijection Y sur la base canonique de R e La matrice T a u valeurs propres 1 lt Ay 1 lt lt Ar p lt o 1 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 54 al a et cryptographie avec point de vue dynamique Th or me On a 2 K K 1 x o amp est le plus petit nombre de pas n cessaire pour aller de tout tat dans M a 2 hs Ayi GHe oe LS X tout autre tat La premi re in galit est facile la seconde est laborieuse tablir Mode d emploi Introduisons pour deux probabilit s p p sur M la distance variation totale dp 5 D elm v m meM Soit U M la probabilit uniforme sur M et P la distribution de la marche issue de m apr s n pas et posons d n lt E 1 ct P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 55 al a et cryptographie avec point de vue dynamique Ou encore pour mettre en vidence la vitesse exponentielle d ab by e avec 1 a z log 4 log 2 et P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 56 al a et cryptographie avec point de vue dynamique Cas du Golay Il conduit l approximation de la distribution uniforme de 5 parmi 24 Le groupe Mo est trop gros On remplace la marche sur le groupe par son image sur les blocs du syst me de Steiner S 5 8 24 La marche markovienne s effectue sur les o
27. ographie avec point de vue dynamique Petit inventaire des attaques par canaux cach s pour une carte puce Attaques passives e Consommation de courant simple diff rentielle clair choisi ou connu e missions lectromagn tiques temp rature de fonctionnement e Temps de calcul Attaques actives e nvasives semi invasive non invasives e Injection de fautes M thodes statistiques mises en oeuvre traitement du signal e M thode diff rentielle DPA Kocher 1999 e Par coefficients de corr lation CPA Brier 2004 e Entropie attaque par information mutuelle MIA Gierlichs 2008 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 64 al a et cryptographie avec point de vue dynamique Proc dures g n rales de masquage BUT masquer les calculs unifier leur temps d ex cution randomiser les valeurs interm diaires v par une combinaison v C v m o m est une valeur al atoire En g n ral C v m c m dans le corps GF 2 Probl me l issue des tours revenir la vraie valeur de sortie Pas de difficult pour une transformation lin aire F F v amp m o F m F v Pour SB les travaux rivalisent d imagination P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 65 al a et cryptographie avec point de vue dynamique Notre proposition pour masquer SB A Bonnecaze P Liardet A Venelli
28. oires pour Cryptographes seulement Partie 4 Applications P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 36 al a et cryptographie avec point de vue dynamique 3 G n rateurs de nombres al atoires pour Cryptographes seulement La source id ale est une suite de g n rateurs al atoires qui met des suites de symboles de S S q de longueur finie n avec la distribution uniforme Un G n rateur cryptographiquement s r Rappel Un g n rateur al atoire de type h sur S est une application G S S telle que la restriction G de G 5 not e Gy soit valeurs dans G pour tout n N Ici n gt h n est suppos e tre une suite strictement monotone d entiers croissance polynomiale et h 1 gt 1 D finition de g n rateur pseudo al atoire cryptographiquement s r d apr s M Blum et S Micali 1982 Algorithme qui met des suites de symboles dont la distribution est indistinguable de la distribution uniforme au moyen de tout algorithme polynomial probabiliste P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 37 al a et cryptographie avec point de vue dynamique Pr cisons distribution indistinguable Soit n une suite strictement croissante d entiers naturels D finition Une suite de probabilit s Jim sur S est dite indistinguable polynomialement si pour tout algorithme probabili
29. oisir un puis un autre algorithme probabiliste bas sur l algorithme de m lange de Fisher Yates algorithme RANKSB de Nijenhuis and Wilf 1978 Ces algorithmes conduisent un biaisage important vis vis de la distribution uniforme Solution propos e A Bonnecaze et P Liardet 2011 Bas e sur certains codes correcteurs Essentiellement pour tous codes admettant des designs voir plus loin dans le cas de syst mes de Steiner associ s La m thode fait usage d une marche al atoire sur le groupe des automorphismes du code P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 49 al a et cryptographie avec point de vue dynamique Un exemple explicite e Le code de service code binaire de Golay tendu G24 c est un code parfait de longueur 24 de dimension 12 de poids minimal 8 poids des mots 0 8 12 ou 24 e pour construire un g n rateur 5 parmi 24 Rappels brefs sur les codes et designs Un code binaire lin aire C de longueur n est un sous espace vectoriel de F5 Les param tres de C sont n k d o k est la dimension vectorielle et d le plus petit poids de Hamming non nul Soit Y un v ensemble ensemble de v l ments e Un v k design est un ensemble de k sous ensembles les blocs de Y tel que tout t sous ensemble de Y est recouvert par exactement A blocs Syst me de Steiner
30. pe Las Vegas 2 Approcher arbitrairement un g n rateur pseudo al atoire q aire par un g n rateur pseudo al atoire binaire aux moyens de chaines de Markov Ou troisi me solution utiliser une dynamique non inversible d entropie strictement positive machine fractale Une quatri me B Dans l implantation d un processus cryptographique n cessit de mettre en place des contre mesures pour contrer les attaques par canaux cach s eee Comme applications nous allons examiner deux cas typiques P L amp A B Grenoble juin 2014 Workshop dynamics and number theory AT al a et cryptographie avec point de vue dynamique 4 Applications Architecture client serveurs et marches al atoires sur groupes Le probl me client serveur e Le serveur seul est un point faible peut tre corrompu victime d attaque par d ni de service probl mes de pannes diverses hardware ou software e Comment se pr munir de ces checs une solution simple utiliser plusieurs serveurs disons n renforcer la s curit en faisant intervenir al atoirement k serveurs parmi les n R alisation Par la construction d un g n rateur al atoire k parmi n au moyen d un g n rateur binaire P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 48 al a et cryptographie avec point de vue dynamique Solutions possibles Nombreuses par exemple en ch
31. rdinateur But extraire de l entropie partir de bruitages agitation thermique flicker Exemple mod lisation sur silicium Syst me quivalent un circuit CR int grant un g n rateur de tension V t w suppos tre une version continue d un bruit blanc une tension d entr e Ve une tension de sortie Vz L tat du circuit est classiquement donn par le syst me d quations a Ve Vs Ri V t w Vs q C pe P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 45 al a et cryptographie avec point de vue dynamique Solution La partie stochastique NN LU Bu exp RO V u w du repr sente la contribution des sources de bruit N cessit de traiter le signal de sortie d biaisage et de valider la vol e le bon fonctionnement du g n rateur hard d tection des pannes Techniques d avenir P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 46 al a et cryptographie avec point de vue dynamique Dans les applications A On dispose habituellement d un g n rateur binaire natif Probl me dans de nombreux cas pratiques on recherche un g n rateur sur un nombre q de symboles qui peut ne pas tre une puissance de deux Solutions de deux types 1 Transformer un g n rateur pseudo al atoire binaire en un g n rateur pseudo al atoire q aire aux moyens d algorithmes ty
32. ste polynomial A sortant 0 ou 1 et pour toutt gt 1 ona Is LAC 1 Ui AQ DI pour tout n assez grand P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 38 al a et cryptographie avec point de vue dynamique Par comparaisons avec la q normalit caract ris e par la non pr diction par automates cours I on a Caract risation L5 est indistinguable de la distribution uniforme si pour tout algorithme probabiliste valeurs dans S 85 q il n existe pas d entier t gt 1 tel que 1 1 uk A s1 gt Se k 1 a Sek gt q T Kk pour une infinit de k P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 39 al a et cryptographie avec point de vue dynamique D finition d un g n rateur pseudo al atoire de nombres en cryptogra phie Algorithme polynomial d terministe G S S tel que pour toute entr e w de longueur w la sortie G w est de longueur G w h w et de plus la suite des distributions u d termin es par G sur S est indistinguable de la distribution uniforme P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 40 al a et cryptographie avec point de vue dynamique e En 1982 Yao mat rialise cette notion dans le cas binaire S 0 1 Pour cela il se restreint aux familles C de tests statistiques bool ens Cy 1 2 3 C est une fonction bool enne construite
33. u polyn me compagnon h X X h 4X 1 ho rappel on est dans F2 donc 1 1 avec h X irr ductible P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 21 al a et cryptographie avec point de vue dynamique Qj 41 tt Qi T a4 g t1 Qj 1 Cn avec 0 0 0 ho 1 0 0 hi Ch 0 1 0 ho 0 0 1 hei Exemple 4 h X X X 1 hug em d em hg ha 0 et 0 0 0 1 1 0 0 1 C l0 1 0 0 0 0 1 0 Periode 2 1 initialisation ao a1 a a3 4 0 0 0 0 registre ue i i i sortie Ry P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 22 al a et cryptographie avec point de vue dynamique Construction g n rale E 0 1 f E E de la forme T bersim Gt DUE rna sion avec g E 0 1 On fixe une graine a1 4m puis par r currence An 1 Od his 0 0 1 Bor En cryptographie g est choisie non lin aire Au mieux g est une fonction bool enne courbe P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 23 al a et cryptographie avec point de vue dynamique Exemple 3 G n rateurs de type inversif Int r t ils ne sont pas lin aires ils utilisent la structure multiplicative des corps finis ou des anneaux de Galois l inversion dans F s est la partie non lin aire de l algorithme de chiffrement AES le standard actuel qui remplace le DES e G n rate
34. urs inversifs sur les corps finis Eichenhauer et Lehn 1986 en caract ristique deux application o Fom Foam d finie par p t aot bo si t 0 et o 0 bo Suites engendr es germe to et 441 tn P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 24 al a et cryptographie avec point de vue dynamique e G n rateurs inversifs sur les anneaux Z 2 Z des entiers modulo 2 Eichenhauer Hermann et Grothe 1992 Difficult principale inverser des diviseurs de z ro Un bel exemple issue des g n rateurs congruentiels de type inversif Introduit vers 1987 par Eichenauer et Lehn Les acteurs un corps fini K et son projectif P1 K une homographie f xr ae xEP1 ad bc 0 f w a c L ICG n f xo zo Pi f est suppos e d ordre P K le polyn me caract ristique de la matrice compagnon est primitif e Nombreuses variations cas multidimensionnel F Griffin H Niederreiter et Shparlinski 1998 2001 Modulo M H Niederreiter A Winterhof E El Mahassni 2001 2005 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 25 al a et cryptographie avec point de vue dynamique e Pour notre construction on part de l ICG introduit par J Eichenaueur et H Grothe 1992 Anneau Rom Z 2 Z notation v valuation 2 adique sur Z ou Rom ou Zo lim Rom anneau des lt
35. w d pend de U mais il est d fini une constante additive pr s On a toujours K x w longueur du mot D finition Un mot est al atoire au sens de Kolmogorov si K w gt wl complexit maximale parmi celles des mots de m me longueur On peut affaiblir en supposant seulement K w gt w c mot c al atoire Cons quence rassurante pour m assez grand le mot 0 n est pas al atoire P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 3 al a et cryptographie avec point de vue dynamique Le calcul de K w est fonction de K il est d fini une constante additive pr s ind pendante de w Le probl me est al atoire au sens de Kolmogorov est ind cidable Si on restreint les ressources en calcul exemple calcul en au plus n tapes successives pour une entr e de longueur n la complexit qui en r sulte est effectivement calculable Exemple de calcul K entier n en binaire lt log n O 1 P L amp A B Grenoble juin 2014 Workshop dynamics and number theory 4 al a et cryptographie avec point de vue dynamique b Suites binaires al atoires effectif La d finition de Kolmogorov ne se prolonge pas aux suites infinies Martin L f Solution 1 remplacer la machine de Turing universelle par une machine de Turing pr fixe P si P calcule P e et si e est pr fixe de e alors P calcule P e et P e P
Download Pdf Manuals
Related Search