Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Partiel S´ eCrypt - Info 3 Les copies des transparents, et notes, de cours et d

Partiel S´ eCrypt - Info 3 Les copies des transparents, et notes, de cours et de travaux dirig´ es sont autoris´ ees. Veuillez justiﬁer vos r´ eponses de fa¸ con rigoureuse. Exercice 1 : Relations d’ordre & treillis (Politique de s´ ecurit´ e) 1. La relation binaire suivante sur E = {0, 1, 2, 3, 4, 5} est-elle une relation d’ordre ? 0 ≤ x ∀x ∈{0, 1, 2, 3, 5} , 1 ≤ 3 3 ≤ 5 1 ≤ 5 2 ≤ 4 . 2. Si la relation pr´ ec´ edente n’est pas une relation d’ordre, quelle information faut-il ajouter pour qu’elle le devienne ? 3. Avec l’information ajout´ ee (question pr´ ec´ edente), la relation d’ordre obtenue est-elle totale ? 4. On consid` ere la relation binaire suivante sur E = {0, 1, 2, 3, 4, 5}. 0 ≤ x ∀x ∈E , 1 ≤ 3 3 ≤ 5 1 ≤ 5 2 ≤ 4 . Calculer inf{x, y} pour tous x, y ∈E. 5. La relation introduite ` a la question pr´ ec´ edente est-elle un treillis ? 6. Dans le cas o` u la r´ eponse ` a la question pr´ ec´ edente est non, pouvez-vous ajouter une (ou des) information(s) aﬁn d’en faire un treillis ? 7. On consid` ere trois cat´ egories top secret, sensible, d´ eclass´ ee ordonn´ ees par la relation top secret ≥sensible ≥d´ eclass´ ee. On suppose que les niveaux d’ha- bilitation des utilisateurs et les niveaux de classiﬁcation des objets sont l’une de ces cat´ egories. Imaginez une politique de contrˆ ole d’acc` es dans laquelle aucune fuite d’information n’est possible d’un niveau donn´ e vers un niveau qui lui est inf´ erieur. Exercice 2 : Groupes pour la cryptographie 1. Expliquer en quelques mots l’importance des groupes en cryptographie ; 2. Soit G = {1, 2, 3, 4} muni de l’op´ eration ∗donn´ ee par la table de “ multiplication ” suivante ∗ 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1 1 (a) G est-il un groupe ? (b) L’op´ eration ∗est-elle commutative ? 3. Soit N l’ensemble {0, 1, 2, · · · } des entiers naturels. Cet ensemble N avec la multi- plication (usuelle) est-il un groupe ? Mˆ eme question avec l’addition (usuelle). 4. On consid` ere Z26 avec la multiplication modulo vingt-six. Cet ensemble est-il un groupe (pour la multiplication) ? (Indication : un ´ el´ ement quelconque de Z26 est-il inversible ?) Exercice 3 : Le carr´ e de Polybe On consid` ere un carr´ e 5 × 5. On choisit un mot qui n’a que des lettres distinctes (c’est- ` a-dire qu’une lettre n’apparaˆ ıt qu’au plus une fois dans ce mot ; par exemple, “ mot ” et contre-exemple : “ chiﬀrement ” o` u il y a deux “ f ” et deux “ e ”) et qui ne contient pas la lettre “ j ”. Pour chiﬀrer un message (´ ecrit sans accents, sans ponctuation ni espaces et en majuscules), on commence par placer dans l’ordre (de la gauche vers la droite et de haut en bas) la clef secr` ete dans le tableau en commen¸ cant par la case (1, 1) (premi` ere ligne et premi` ere colonne). On compl` ete ensuite ce carr´ e en inscrivant les lettres de l’alphabet (dans l’ordre alphab´ etique) qui n’apparaissent pas dans le mot choisit comme clef, en omettant la lettre “ J ”. Le cryptogramme est obtenu de la fa¸ con suivante : on consid` ere un message dans lequel la lettre “ J ” n’apparaˆ ıt pas. On chiﬀre chaque lettre du texte clair par les coordonn´ ees not´ ee “ij” (i : num´ ero de la ligne, j : num´ ero de la colonne, i=1,..., 5 et j=1,..., 5) de la case (dans le carr´ e) dans laquelle la lettre apparaˆ ıt. 1. Soit le mot clef “ POLYBE ”. (a) Construire le carr´ e 5 × 5 comme indiqu´ e dans l’´ enonc´ e ; (b) Chiﬀrer le message “ CENOMESTGRECBIENSUR”. 2. D´ echiﬀer le cryptogramme suivant obtenu avec la clef “ CRYPTO ”. 23122252215221514522522555151221515225412223214343251225142143452523214211215112 2232251421511241224551341525. Exercice 4 : Syst` eme cryptographique produit Une des notions introduites par Shannon en 1949 est l’id´ ee de combiner des syst` emes cryptographiques en formant leur “ produit ”. Cette id´ ee joue un rˆ ole fondamental dans la conception des syst` emes cryptographiques actuels tels le DES. Supposons que l’on ait deux proc´ ed´ es de chiﬀrement S1 et S2. On suppose que les en- sembles de message clairs et de chiﬀr´ es de Si, i = 1, 2 sont tous identiques. On note K(i) l’espace des clefs du syst` eme Si (i = 1, 2) et pour K ∈K(i), on note D(i) K et E(i) K les fonc- tions de d´ echiﬀrement et de chiﬀrement de S(i) (i = 1, 2). On d´ eﬁnit le syst` eme produit S1 × S2 par la r` egle de chiﬀrement EK1,K2(x) := E(2) K2(E(1) K1(x)) pour x un message clair, Ki ∈K(i). Il r´ esulte que l’espace des clefs de S1 × S2 n’est rien d’autre que le produit cart´ esien K(1) × K(2). 1. Expliquer, en fran¸ cais, le fonctionnement de cette m´ ethode de chiﬀrement ; 2 2. Donner le nombre de clefs de S1 × S2 en fonction des nombres de clefs de S1 et de S2 ; 3. D´ eduire de la d´ eﬁnition de la r` egle de chiﬀrement, la m´ ethode de d´ echiﬀrement de S1 × S2 ; 4. Montrer (en utilisant la propri´ et´ e de d´ echiﬀrement vue en cours) que l’on a D(1) K1(D(2) K2(y)) = x quel que soit le message clair x et son chiﬀr´ e y = EK1,K2(x), et quelles que soient les clefs K1 ∈K(1) et K2 ∈K(2) ; 5. Montrer que le proc´ ed´ e de chiﬀrement aﬃne (vu en TD) peut ˆ etre d´ ecrit comme un proc´ ed´ e produit S1 × S2 (o` u l’un des facteurs Si est le proc´ ed´ e de chiﬀrement par d´ ecalage, tandis que l’autre facteur est un proc´ ed´ e que vous devrez imaginer). Exercice 5 : Conﬁdentialit´ e parfaite Soit un syst` eme cryptographique dans lequel P = {a, b, c}, K = {K1, K2, K3} et C = {1, 2, 3, 4}. Supposons que la r` egle de chiﬀrement soit d´ eﬁni par la table suivante a b c K1 1 2 3 K2 2 3 4 K3 3 4 1 On suppose que la probabilit´ e PK est la probabilit´ e uniforme, et, PP(a) = 1 2, PP(b) = 1 3 et PP(c) = 1 6. 1. Calculer les probabilit´ es conditionnelles P(x|y) pour tout x ∈P et y ∈C ; 2. La conﬁdentialit´ e parfaite est-elle assur´ ee par ce cryptosyst` eme ? Exercice 6 : Structure de Feistel g´ en´ eralis´ ee Soient X, K deux ensembles ﬁnis. Soit les applications B : X × X →X telle que B(x′, B(x, x′)) = x quels que soient x, x′ ∈X et f : X × K →X . Soit enﬁn l’application F : (X × X) × K → X × X ((x1, x2), k) 7→ (x2, B(x1, f(x2, k))) . Montrer que quel que soit k ∈K ﬁx´ e, la fonction (x1, x2) 7→(x2, B(x1, f(x2, k))) est inversible. (Inspirez-vous de la d´ emonstration vue en cours du fait qu’une structure de Feistel est inversible.) 3 Exercice 7 : Proc´ ed´ e de chiﬀrement multiplicatif On consid` ere l’anneau Z30 = {0, 1, 2, · · · , 29} des entiers modulo 30. Rappelons qu’un ´ el´ ement a ∈Z30 est inversible (c’est-` a-dire qu’il existe b ∈Z30 tel que ab = 1 mod 30 ; dans la suite vous noterez “ a−1 ” l’inverse de a) si, et seulement si, pgcd(a, 30) = 1 (c’est-` a-dire le seul multiple commun entre a et 30 est 1). 1. ´ Enum´ erer tous les ´ el´ ements de Z30 qui sont inversibles ; 2. Calculer l’inverse dans Z30 des ´ el´ ements trouv´ es ` a la question pr´ ec´ edente ; 3. On d´ eﬁnit le proc´ ed´ e de chiﬀrement multiplicatif sur Z30 de la fa¸ con suivante : les messages clairs et chiﬀr´ es sont des ´ el´ ements de Z30 et l’espace des clefs est donn´ e par K := {a ∈Z30 : pgcd(a, 30) = 1}. La fonction de chiﬀrement est donn´ e par Ea(x) := ax mod 30 avec a ∈K. (a) Calculer le nombre de clefs possibles ; (b) D´ ecrire la fonction de d´ echiﬀrement Da pour a ∈K ; (c) On suppose que les letters sont cod´ ees comme d’habitude par A ↔0, ..., Z ↔25, puis ` A↔26, ˆ E↔27, ´ E↔28 et le caract` ere blanc (l’espace) ↔29. Chiﬀrer le message suivant avec la uploads/Litterature/ examen-partiel.pdf