[PDF] Le thème pour 2015 : la cryptographie ou lart de coder et décoder.

View - Download Le thème pour 2015 : la cryptographie ou lart de coder et décoder.

Previous PDF

Next PDF

Fête des mathématiques

Nouveau-Brunswick francophone, le 17 février 2015 Le thème pour 2015 ͗ la cryptographie, ou l'art de coder et décoder. L'algğbre modulaire et les nombres premiers font partie des mathématiques utilisées dans la cryptographie moderne, notamment dans les systèmes qui assurent la protection des donnĠes sur internet. Ces sujets s'ajoutent donc au thème de 2015. A. Cryptographie : La cryptographie est la science du codage. Ses activités principales sont la création de codes (trouver une méthode de codage pour écrire des messages secrets) et le décodage (essayer de déchiffrer les messages secrets). Un des codes les plus anciens était le code de Jules César, dans lequel chaque lettre Ġtait simplement dĠcalĠe de trois positions dans l'alphabet (Le A est par le A, le Y par le B et le Z par le C).

Code de César

1 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

2 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Ligne 1 ͗ l'alphabet normal

Par exemple pour envoyer le message " Veni Vidi Vinci » Jules César aurait écrit " Yhql Ylgl Ylqfl » Jules César était un général et homme politique romain important qui vivait et " Veni Vidi Vinci » est une phrase latine qui signifie " Je suis ǀenu. J'ai ǀu. J'ai vaincu.» Exercice 1 : Codez le message suivant en utilisant le code de César " J'arriǀe demain » Exercice 2 : Le message ci-dessous a été codé en utilisant le code de Jules César " Lov vrqw fxlwv »

Décodez-le.

Activité de groupe en classe : Inspirez-vous du code de Jules César pour créer un nouveau code et formez deux groupes, un qui écrit messages secrets. Pour les plus ǀieudž, l'actiǀitĠ peut ġtre complexifiée : le second groupe ne connait pas le et il doit trouver le code et décoder les messages.

Coder avec un mot clé ou une phrase clé

complexifier le dĠcodage, l'idĠe est ǀenu d'aǀoir un mot clé ou une phrase clé secrète. Par exemple, pour utiliser JULIUS CEASAR comme phrase clé, on commence par enlever les espaces et les lettres répétitives ( il reste JULISCAER). La clé consiste ă placer au dĠbut de l'alphabet le tedžte de la phrase clĠ et ensuite Le code avec la phrase clé Julius Ceasar (code JULIUS CEASAR)

1 a b c d e f g h i j k l m n o p q r s t u v w x y z

2 J U L I S C A E R T V W X Y Z B D F G H K M N O P Q

Ligne 1 ͗ l'alphabet normal

Exercice 3 : Codez le message suivant en utilisant le code obtenu avec le code

JULIUS CEASAR.

" demain dix heures » Exercice 4 : Le message ci-dessous a été codé en utilisant le code JULIUS CEASAR.

Décodez-le.

" BZFHS GKI ZYQS ESKFSG »

Activité en groupes de 2 :

Inventer un mot clé ou une phrase clé secrète et créer un nouveau code. En Pour complexifier le décodage, ne pas donner la clé au partenaire. B. Les nombres premiers : Les diǀiseurs propres d'un nombre sont les diviseurs de ce nombre sauf 1 et le nombre lui-même. Par exemple, les diviseurs de 6 sont 1, 2, 3 et 6. Les diviseurs propres de 6 sont 2 et 3. Les diviseurs propres de 10 sont 2 et 5. Le nombre 7 n'a pas de diǀiseurs propres, ses seuls diviseurs étant 1 et 7. Un nombre premier est un nombre Autrement dit, un nombre premier ne se divise que par 1 et par lui-même et

1 n'est pas un nombre premier (tous les nombres premiers ont deux

moins trois. Donc les nombres premiers sont ceux qui ont exactement deux diviseurs positifs distincts)

Les 10 premiers nombres premiers sont :

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Le crible d'rathostğne

Pour trouver dans une liste de nombre quels sont les nombres premiers, le mathématicien grec Érathostène (qui vivait dans le 3e siècle avant Jésus nombre n. Il fait la liste de tous les nombres premiers dont le carré est plus petit ou égal à n. a. Il commence en barrant le nombre 1 dans la liste. b. Puis en prenant ces nombres premiers un par un dans la liste, en commençant par le plus petit et en montant, il barre les multiples de ces nombres, mais pas ces nombres eux-mêmes.. Ensuite il barre les multiples de 3 plus grands que 3 qui ne sont pas déjà Puis il continue avec les autres nombres premiers de sa liste. Quand il a fini, les nombres premiers sont ceux qui ne sont pas barrés. Le plus grand nombre premier dont le carré ne dépasse pas 50 est 7 (72 =

49). Sa liste de nombres premiers est donc 2, 3, 5 et 7.

Il barre d'abord le 1.

Ensuite il barre les multiples de 2 plus grands que 2 : (4, 6, 8, 10, 12, 14, 16,

18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50)

Ensuite il barre les multiples de 3, plus grands que 3, qui ne sont pas déjà barrés : (9, 15, 21, 27, 33, 39, 45) Ensuite il barre les multiples de 5, plus grands que 5, qui ne sont pas déjà barrés : (25, 35) Finalement il barre les multiples de 7, plus grands que 7, qui ne sont pas déjà barrés : (49) Les nombres qui restent (les nombres non noircis dans le tableau ci- dessous) sont les nombres premiers entre 1 et 50

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Les nombres premiers plus petits ou égaux à 50 sont donc :

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 et 47. Il y en a quinze.

Exercice 5 : Combien y a-t-il de nombres premiers plus petits que 100? Faites-en la liste en utilisant le crible d'rathostğne. Exercice 5 : Combien y a-t-il de nombres premiers plus petits que 1000? Faites-en la liste en utilisant le crible d'rathostğne. Activité de groupe en classe, pour les plus vieux qui connaissent la programmation : Fabriquer un programme informatique qui va dire si un nombre donné (par exemple entre 1 et 1 000 000) est premier. On écrira par exemple que 17 modulo 7 est égal à 3, car si on divise 17 par reste. Un autre exemple simple : 27 modulo 5 est égal à 2. En effet, 27 divisé par 5 est égal à 5 reste 2.

18 modulo 4 = 2

21 modulo 6 = 3

31 modulo 10 = 1

9 modulo 4 = 1

Les heures sur une horloge à 24 heures sont un exemple de calcul modulo dans 12 heures, la rĠponse n'est pas 29 h (29 = 17 + 12) mais bien 5 h. En effet, si on divise 29 par 24, la réponse est 1 reste 5. Donc 29 modulo 24 est égal à 5 Sur la même horloge à 24 heures, s'il est maintenant 17 h, quelle heure sera-t-il dans 100 heures? Pour trouver la réponse, on cherche 117 modulo 24 (117 = 17 + 100). Pour trouver 117 modulo 24 on doit diviser 117 par 24 et ne retenir que le reste. Puisque 117 divisé par 24 est égal à 4 reste 21 (4 x 24 = 96, maintenant, dans 100 heures il sera 21 h. On pourrait également travailler avec une horloge à 12 heures en travaillant modulo 12. Par edžemple s'il est 10 h maintenant, quelle heure sera-t-il dans 30 heures? Puisque 30 + 10 = 40, on doit calculer 40 modulo 12. Puisque 40 divisé par 12 donne 3 reste 4, dans 30 heures il sera 4 h.

Exercice 7 : trouver les valeurs suivantes :

26 modulo 5 15 modulo 2 153 modulo 5

17 modulo 3 20 modulo 3 3456 modulo 10

14 modulo 7 14 modulo 5 2436 modulo 2

25 modulo 7 33 modulo 7 1234 modulo 11

Exercice 8 : Sur une horloge à 12 heures, il est maintenant 3 h 30. Quelle heure sera-t-il dans 41 heures et 15 minutes? Exercice 9 : En numérotant les jours (dimanche = 1, lundi = 2, mardi = 3, mercredi = 4, jeudi = 5, vendredi = 6, samedi = 7) on peut savoir quel jour sera un jour donnĠ si on calcule modulo 7. Si on est aujourd'hui mercredi, quel jour serons-nous dans 100 jours? Pour certains nombres on peut trouver les modulos rapidement sans avoir à diviser. Par exemple pour travailler modulo 2 il suffit de regarder si un nombre est pair ou impair. Tous les nombres pairs donnent 0 modulo 2 (exemple 46 modulo 2 les nombres impairs modulo 2 donnent 1 (exemple 37 modulo 2 = 1) puisque la diǀision d'un nombre impair par 1 donnera toujours un reste Ġgal ă 1. Exercice 10 : Trouvez une méthode pour calculer modulo 10 sans avoir

à diviser.

Exercice 11 : Trouvez une méthode pour calculer modulo 5 sans avoir

à diviser.

Exercice 12 : Trouvez une méthode pour calculer modulo 3 sans avoir

à diviser.

D La méthode RSA : La méthode RSA est ainsi nommĠe en l'honneur de ses trois inventeurs (Ronald Rivest, Adi Shamir, Léonard Adleman). C'est un procĠdĠ de cryptographie très utilisé sur internet, notamment pour les transactions commerciales qui demandent le secret (protéger le numéro de votre carte de crédit par exemple). Savoir utiliser cette méthode est facile et ne nécessite que la comprĠhension de l'algèbre modulaire et des nombres premiers. La sécurité de la méthode est basée sur les deux faits suivants :

1. Il est facile aujourd'hui pour un ordinateur de fabriquer de très grands

nombres premiers (par exemple un nombre premier à 150 chiffres)

2. Il est très difficile, voire impossible (calculs extrêmement longs) à un

ordinateur de mettre en facteur un nombre obtenu en multipliant deux très grands nombres premiers (par exemple un nombre de 300 chiffres obtenu en multipliant deux nombres premiers de 150 chiffres). Les gens qui écrivent des messages avec cette méthode utilisent une clé publique (produit ă partir d'un trğs grand nombre obtenu en multipliant des nombres premiers). Ceux qui doivent déchiffrer le message possèdent la clé privée (les facteurs premiers de la clé publique, impossible à trouver). Si on arrête un agent qui envoie des messages, il ne connait que la clé publique qui Méthode RSA : Voici comment on procède. Il faut des outils de calculs (un ordinateur par exemple, ou une bonne calculatrice. Cela ne se fait pas à la main).

1. On se donne un code numérique pour les lettres de l'alphabet (Ġǀentuellement

a b c d e f g h i j k l m

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

n o p q r s t u v w x y z

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

2. Supposons que le message à envoyer est la lettre " o »

Chaque message écrit est transformé en chiffre avec la correspondance donnée par le tableau ci-dessus (la lettre " o » devient le chiffre " 15 ». On procède lettre par lettre. Dans notre cas le message chiffré est le chiffre " 15 ».

3. On trouve ensuite les clés (on fabrique deux grands nombres premiers, P et Q,

qui resteront secrets). Prenons ici P = 3 et Q = 11

4. On calcule N = PQ (N est une clé publique). Ici N = 33

5. On calcule le nombre M = (P-1)(Q-1). Ici M = 2x10 = 20.

Ici e с 3 fait l'affaire, puisque les facteurs premiers de 20 sont 2 et 5 (différents de

3). Le nombre e est la clé de chiffrement (e et N permettent de coder).

7. On trouve un nombre d tel que e x d modulo M = 1.

Ici d с 7 fait l'affaire, car 3 x 7 = 21 et 21 modulo 20 = 1. Le nombre d est la clé de décodage. On ne peut pas trouver d si on connait N et e

(les clés publiques). Pour trouver d, il faut aussi connaître P et Q (les clés secrètes).

8. Pour coder : Si M est le message chiffré, on calcule C = Me modulo N

Ici on calcule C = 153 modulo 33. Donc C = 9 (153 = 102 x 33 + 9).

Le message codé chiffré est " 9 »

9. Pour décoder on calcule Cd modulo N. En raison de résultats importants de la

théorie des nombres, on a que M = Cd. Ici, on calcule 97 modulo 33. On vérifie bien que 97 modulo 33 = 4782969 modulo

33 = (144938 x 33 + 15) modulo 33 = 15.

Donc le message décodé est le chiffre " 15 ».

10. On vérifie que le chiffre 15 correspond à la lettre " o ». Le message décodé

est donc la lettre " o ». Exercice 13 : Utiliser le système RSA pour coder et décoder le message " DEF » en utilisant les clés utilisées ci-haut (P = 3, Q = 11, N = 33, M = 20, e = 3 et d = 7). Exercice 14: Vérifier que si P = 5 et Q = 7, alors e = 5 et d = 5 (d = e) font de bonnes clés pour le chiffrement (e = 5) et pour le décodage (d = 5). Avec ces nouvelles valeurs pour P, Q, N, M, e et d; codez et décodez le message " DEF » P et Q pas trop grands, pour lesquels vous pouvez trouver deux clés de codage et de décodage (e et d) qui sont distinctes. Avec ces nouvelles clés codez et décodez le message " DEF »

Problèmes supplémentaires

Exercice de groupe : Utilisez le code d'alphabet inǀersĠ pour coder et dĠcoder des a b c d e f g h i j k l m n o p q r s t u v w x y z z y x w v u t s r q p o n m l k j i h g f e d c b a Ainsi le mot " oui » codé avec l'alphabet inversé devient le mot " lfr » Exercice 15 : Certains nombres premiers sont des nombres impairs consécutifs. Par exemple 11 et 13 sont des nombres impairs consécutifs. Deux nombres premiers qui sont des impairs consécutifs sont dits des nombres premiers jumeaux. Trouvez toutes les paires de nombres premiers jumeaux qui sont inférieurs à 100. Vérifier que le nombre 5 est le seul qui ait deux jumeaux distincts. Exercice 16 : En mathématique une conjecture est un résultat qui semble vrai, mathématicien du 17e siècle) dit que tous les nombres pairs, à partir de 4, peuvent s'Ġcrire comme une somme de deudž nombres premiers (pas forcĠment distincts,

Par exemple : 4 = 2 + 2

6 = 3 + 3

8 = 3 + 5

10 = 3 + 7 = 5 + 5 (deux manières).

Exercice 17 : Quand on calcule un produit de deux entiers modulo un certain nombre entier, on peut faire le produit d'abord et calculer le modulo ensuite, ou encore on peut faire le modulo de chaque facteur et faire le produit ensuite des modulos. Par exemple si on veut calculer 7 x 12 modulo 5, on peut a) Calculer 7 x 12 = 84 et ensuite calculer 84 modulo 5 = 4 b) Calculer 7 modulo 5 = 2 et 12 modulo 5 = 2 puis ensuite calculer 2 x 2 modulo 5 = 4. Dans les deux cas, on obtient le même résultat (4). Calculez (27 x 31) modulo 4 sans faire le produit 27 x 31 Calculez (427 x 531) modulo 5 sans calculer le produit 427 x 531

Calculez (234567 x 3245678) modulo 5

Réponses :

1) M'DUULYH GHPDLY

2) ILS SONT CUITS

3) ISXJRY IRO ESKFSG

4) PORTE SUD ONZE HEURES

5) 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Il y a 25 nombres premiers inférieurs à 100

6) Il y a 168 nombres premiers inférieurs à 1000.

La liste peut être trouvée sur internet.

7) 26 mod 5 = 1 15 mod 2 = 1 153 mod 5 = 3

17 mod 3 = 2 20 mod 3 = 2 3456 mod 10 = 6

14 mod 7 = 0 14 mod 5 = 4 2436 mod 2 = 0

25 mod 7 = 4 33 mod 7 = 5 1234 mod 11 = 2

8) 8 h 45

9) Vendredi

10) C'est le dernier chiffre du nombre

Exemple 2345676543 mod 10 = 3

11) Si le dernier chiffre est plus petit que 5, c'est le dernier chiffre. Sinon c'est le

dernier chiffre moins 5. exemple : 2343 mod 5 = 3 exemple : 445 mod 5 = 0 (0 = 5 - 5)

12) Le nombre mod 3 est égal à la somme de ses chiffres mod 3. Au besoin on répète

la somme des chiffres. exemple : 7568 mod 3 = (7 + 5 + 6 + 8) mod 3 = 26 mod 3 = (2 + 6) mod 3 = 8 mod 3 = 2

13) D E F en chiffres est 4 5 6, Une fois codĠ c'est 31 26 18

14) Si P = 5 et Q = 7, alors (P-1) x (Q-1) = 4 x 6 = 24. Les facteurs premiers de 24 sont

2 et 3, donc 5 n'a pas de facteurs communs aǀec 25. 5 dž 5 с 25 et 25 mod 24 с 1.

D E F en chiffres est 4 5 6. Une fois codĠ c'est 9 10 6.

15) 3 et 5, 5 et 7, 11 et 13, 17 et 19, 29 et 31, 41 et 43, 59 et 61, 71 et 73

16) De 12 à 50. Une manière par nombre. Il y a plusieurs autres manières.

12 = 5 + 7, 14 = 7 + 7, 16 = 5 + 11, 18 = 7 + 11, 20 = 3 + 17, 22 = 5 + 17,

24 = 5 + 19, 26 = 3 + 23, 28 = 5 + 23, 30 = 13 + 17, 32 = 13 + 19, 34 = 17 + 17,

36 = 5 + 31, 38 = 19 + 19, 40 = 3 + 37, 42 = 5 + 37, 44 = 3 + 41, 46 = 5 + 41,

48 = 19 + 29, 50 = 19 + 31

17) (27 x 31) mod 4 = (3 x 3) mod 4 = 1

(427 x 531) mod 5 = (2 x 1) mod 5 = 2 (234567 x 3245678) mod 5 = (2 x 3) mod 5 = 1quotesdbs_dbs46.pdfusesText_46

[PDF] Le message crypté

[PDF] le message de la croix

[PDF] Le messager d’Athènes

[PDF] Le Métabolisme

[PDF] Le métabolisme cellulaire 2nd

[PDF] le métabolisme cellulaire est controlé par les conditions du milieu

[PDF] le métabolisme cellulaire tp

[PDF] Le metabolisme d'une cellule

[PDF] Le metabolisme de la cellule et le patrimoine génétique

[PDF] Le métabolisme des cellules

[PDF] Le métabolisme des cellules cancéreuses

[PDF] le metabolisme des cellules concereuses

[PDF] le métabolisme des cellules exercice svt

[PDF] le métabolisme énergétique et les besoins des cellules musculaires

[PDF] Le métabolisme et la génétique