ÉCOLE POLYTECHNIQUE ÉCOLE SUPÉRIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES
CONCOURS D'ADMISSION 2009
Filière MP - option physique et sciences de lingénieur filière PC
COMPOSITION D'INFORMATIQUE
(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
Chiffrement par blocs
Notation. Dans tout l'énoncé, désigne l'ensemble des entiers naturels supérieurs ou égaux à et strictement inférieurs à .
Lorsque l'on souhaite communiquer des données confidentielles, il convient de chiffrer ces données, c'est-à-dire de les rendre inintelligibles. Les algorithmes étudiés ici relèvent du chiffrement symétrique : une transformation de chiffrement donnée est identifiée par une clé (un entier), qui la désigne et permet également le déchiffrement.
Dans une approche simplifiée du chiffrement par blocs, le chiffrement d'un message de taille arbitraire est effectué d'abord en découpant le message en blocs de taille fixée puis en chiffrant chaque bloc. Nous nous limitons ici au chiffrement d'un bloc considéré indépendamment des autres. Dans ce modèle, on se donne un entier , dit taille (en pratique est une puissance de deux). Un bloc (clair ou chiffré) est un entier de , et un algorithme de chiffrement est une application de dans . Pour permettre le déchiffrement, cette application doit être une permutation de (autrement dit une bijection).
Important. Dans tout le problème, on suppose que le langage de programmation utilisé possède certaines propriétés.
Les programmes agissent sur des entiers (naturels) «de taille arbitraire» c'est-à-dire que l'on ignore toutes les questions liées à la taille finie des entiers machine. Autrement dit, on considère que les opérations usuelles (, etc.) sont celles des entiers naturels.
Il existe deux fonctions rem et quo calculant respectivement le reste et le quotient de la division euclidienne de par . Il est rappelé que l'égalité et la condition définissent et . Autrement dit, si , alors il existe un unique quotient et un unique reste , dont les valeurs sont données précisément par les fonctions quo et rem.
Certaines des fonctions demandées sont spécifiées comme renvoyant un tableau ou une liste. Tableau ou liste sont au choix du candidat. En cas de doute, le candidat est invité à définir les primitives dont il juge avoir besoin et à les employer de façon cohérente dans tout le problème.
I. Approche naïve
On cherche à désigner (dans un premier temps) une application arbitraire de (ensemble à éléments) dans lui-même. Le nombre total de telles applications est .
Considérons un entier (une clé) pris dans . L'entier s'écrit de manière unique sous la forme :
où chaque coefficient vérifie (c'est l'écriture de en base ). On considère que représente l'application de dans lui-même définie par , etc.
Question 1 Écrire la fonction DecomposerBase( ) qui prend en arguments la taille , une clé de , et qui renvoie la décomposition de en base . En pratique, DecomposerBase renvoie donc le tableau ou la liste des , dans l'ordre des croissants.
En réalité nous nous intéressons aux permutations de . On sait qu'il existe permutations d'un ensemble de éléments. Dans la suite logique de la question précédente, considérons donc une clé prise dans . On admet que s'écrit de manière unique sous la forme :
où les coefficients vérifient . L'écriture ci-dessus est dite décomposition sur la base factorielle. Par exemple, pour et , on a .
Question 2 Écrire la fonction DecomposerFact qui prend en argument la taille et une clé de , et qui renvoie la décomposition de sur la base factorielle.
Une fois décomposée sur la base factorielle, la permutation de représentée par se calcule comme suit. En premier lieu, on considère la séquence à éléments. Cette séquence est modifiée au fur et à mesure que les valeurs prises par la permutation sont calculées.
La première valeur calculée est , égal au -ième élément de (c'est-à-dire à . Une fois calculé, cet entier est retiré de , qui ne contient plus que entiers.
La seconde valeur calculée est , égal au -ième élément de . Une fois calculé, cet entier est retiré de . Le procédé est répété jusqu'au calcul de , égal à l'unique élément de restant.
Par exemple, dans le cas on a : , et devient . Ensuite , et devient . Ensuite , et pour finir .
Question 3 Écrire la fonction Retirer qui prend en argument un tableau à éléments, et qui renvoie un tableau de taille . Le tableau renvoyé est une copie du tableau dans laquelle le -ème élément a été retiré.
Question 4 Écrire la fonction EcrirePermutation qui prend en arguments la taille , la clé de , et qui renvoie la permutation . La permutation sera représentée par le tableau ou la liste des , dans l'ordre des croissants.
Question 5 Écrire les fonctions et , qui prennent en arguments la taille , la clé et un bloc . La fonction Chiffrer renvoie , tandis que la fonction Dechiffrer renvoie l'unique bloc tel que .
II. Réseau de Feistel
Nous prenons ici le parti de fabriquer des permutations particulières. Notre motivation ici est double : (1) réduire la taille des clés (un entier de dans la partie précédente) et (2) effectuer des calculs peu coûteux lors du chiffrement et du déchiffrement.
On commence par fixer la taille à la valeur . Un bloc est donc un entier de . L'ingrédient essentiel du chiffrement est le réseau de Feistel. Un réseau de Feistel est une suite de plusieurs opérations, appelées tours. Un tour est décrit par la figure 1. Sur la figure, l'entrée est le bloc , la sortie est .
Fig. 1: Un tour de réseau de Feistel
La figure peut aussi se lire comme définisssant égal à , et égal à . Le symbole désigne ici une opération appelée xor. Cette fonction est associative, commutative, et vérifie pour tout couple d'entiers ( ). On suppose que la fonction xor est disponible dans le langage de programmation utilisé, accessible sous le nom xor. Le symbole désigne une application sur , paramétrée par une clé . Par la suite, on suppose donnée une fonction qui calcule .
Question 6 Écrire la fonction FeistelTour qui prend en argument une clé et un bloc ( est un certain , et est un certain ), et renvoie la sortie (notée ci-dessus) du tour qui utilise la clé .
Question 7 Écrire la fonction FeistellnverseTour qui réalise l'application inverse de la fonction précédente, c'est-à-dire qui calcule et renvoie en fonction de .
Question 8 Écrire la fonction Feistel ( ) qui prend en entrée le bloc , et renvoie la sortie d'un réseau de Feistel à tours. Plus précisément, l'entrée du premier tour est , puis l'entrée d'un tour est la sortie du tour précédent. Enfin, la sortie du réseau est la sortie du dernier tour. Chaque tour utilise une clé différente. Les clés sont fournies (dans l'ordre) par le tableau de taille . Indépendamment du langage de programmation considéré, on supposera qu'un tableau est un argument standard et que ses indices sont les entiers de .
Question 9 Écrire la fonction Feistellnverse qui effectue l'opération inverse de la fonction précédente. Cette opération inverse est le déchiffrement, et l'identité suivante doit être vérifiée pour tout bloc .
III. Vérification de propriétés statistiques
Dans cette partie la taille est fixée à la valeur , comme dans la partie précédente. On explore la mise en œuvre de critères de qualité du chiffrement. Certains tests couramment employés sont des tests statistiques effectués sur les message chiffrés. Ces tests servent à mettre en évidence des biais indésirables.
On considère le message clair (infini) formé de la séquence des blocs . Pour une permutation de chiffrement des blocs , le message chiffré est donc la séquence des blocs
Les tests portent sur le message chiffré vu comme une séquence de bits, un bit étant un chiffre en base 2, soit 0 ou 1 . En fonction d'une longueur paramétrable , nécessairement multiple de 64, la séquence étudiée est la séquence
où par convention, l'écriture binaire (complète) d'un entier de , est la séquence (le bit «le plus significatif» apparaît en premier).
Dans tout ce qui suit, on considère que la permutation étudiée est fixée, et calculée par une fonction , qui prend en entrée un entier de et renvoie un entier de .
Question 10 Écrire la fonction Sequence(n) qui construit la séquence ci-dessus, sous la forme d'un tableau de taille ou d'une liste (on rappelle que est un multiple de 64). L'ordre des éléments du tableau ou de la liste sera évidemment l'ordre des bits de défini précédemment.
Un premier critère consiste à tester dans quelle mesure les bits 0 et 1 apparaissent avec une fréquence suffisamment proche. Sur un total de bits ( ), on calcule pour cela la valeur , où et représentent respectivement le nombre de bits 0 et 1 dans la séquence de bits considérée. En fonction de cette valeur , des tables permettent de dire si un biais statistique est visible.
Question 11 Écrire la fonction CalculerV1(n) qui détermine la valeur correspondant à la séquence . Attention, on observera que n'est pas un entier, il sera représenté en machine par un nombre flottant.
Un second critère généralise le précédent en considérant les séquences de deux bits. Pour bits ( ), on calcule la valeur donnée par :
où désignent respectivement le nombre d'occurrences des séquences . On notera qu'on autorise les séquences de deux bits à se recouper. Ainsi la séquence de cinq bits 01100 contient exactement une fois chacune des quatre séquences de deux bits possibles.
Question 12 Écrire la fonction CalculerV2(n) qui détermine la valeur correspondant à .
Polytechnique Informatique Commune MP PC 2009 - Version Web LaTeX | WikiPrépa | WikiPrépa
