TD de cybersécurité

Sécurité

td n

◦2 Introduction à la cryptographie

Exercice 1. Introduction au modulo

Imaginons un monde où n’existeraient que les nombres de 1 à 12, comme sur une horloge. Après

12, on retrouve 1, 2, 3 ... Le 12 se confond avec le 0. L’arithmétique serait particulière. Le résultat des opérations serait compris entre 0 et 11 . On peut effectuer l’addition, la soustraction et la

multiplication comme d’habitude.

1.1 Effectuez dans cette arithmétique les opérations suivantes

1+3 |7+7 |3x2 |6x5 |8/4 |28/2

Cette arithmétique est appelée arithmétique modulo 12.

Exercice 2. Arithmétique modulo

Définissons l’arithmétique modulo m :

Zm symbolise l’ensemble d’entiers 0, ..., m-1 muni de deux opérations + et *. Par exemple, Z12

symbolise le calcul sur les heures.

2.1 Par quel Zm sont symbolisés :

1. le calcul sur les jours de la semaine : lundi, mardi, etc...

2. le calcul sur les mois

3. le calcul angles en degrés

Exercice 3. Inverse et opposé modulo

L’addition dans Zm fonctionne exactement comme l’addition usuelle, excepté le fait que tous les

résultats sont réduits modulo m.

Supposons par exemple que l’on veuille calculer 11 + 13 dans Z16. Comme entiers ordinaires, on

a 11 + 13 = 24. Pour réduire 24 modulo 16, on fait une division euclidienne : 24 = 1 ∗ 16 + 8,

donc 24 modulo 16 = 8, et, donc, 11 + 13 = 8 dans Z16.

Sécurité (td n

◦2)

L’opposé de tout a appartenant à Zm est m − a. L’opposé vérifie a + (m − a) = (m − a) + a = 0

(sauf pour a = 0 qui est son propre opposé)

L’inverse modulo n de b est le nombre entier b

−1

tel que b ∗ b

−1 modulo n = 1.

3.1 Calculez les opposés et les inverses de 3 dans Z26 et dans Z11

Dans les exercices suivants, les lettres de l’alphabet sont codées de 0 à 25 pour respectivement

de a à z. Donc par exemple le s est codé 18. Les calculs ont donc lieu dans Z26

A B C D E F G H I J K L M

0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z

13 14 15 16 17 18 19 20 21 22 23 24 25

Exercice 4. Chiffrement par décalage

Le

...