Remerciez-le!

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

Quelques éléments de Cryptographie SageMath et Python (3OCmath) Cruptos (χρυπτo

Quelques éléments de Cryptographie SageMath et Python (3OCmath) Cruptos (χρυπτoς) : caché, dissimulé Graphein (γραφϵιν) : écrire Jean-Philippe Javet www.javmath.ch Table des matières 1 Un doigt d’algorithmique, intro à SageMath 1 1.1 Algorithmes, pseudo-code, SageMath . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Variables et listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Opérations sur les variables du type nombre . . . . . . . . . . . . . . . . . . 4 1.2.2 Opérations sur les variables du type liste . . . . . . . . . . . . . . . . . . . . 6 1.2.3 Opérations sur les variables du type string . . . . . . . . . . . . . . . . . . . 7 1.3 Les boucles for... ou while... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Les conditions : if... ou if... else... . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 Aﬃchage avancé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6 Une fonction qui en appelle une autre . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.7 Pour aller un peu plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Nombres premiers 15 2.1 Quoi de plus simple qu’un nombre premier ? . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Test de primalité d’un nombre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Le crible d’Ératosthène . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Pour aller un peu plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Chiﬀrement de César et congruence 25 3.1 Trois exercices en guise d’introduction . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Quelques éléments sur la congruence . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 La cryptographie, le chiﬀrement de César . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 Pour aller un peu plus loin au sujet de la congruence . . . . . . . . . . . . . . . . . 34 3.5 Et la division modulo n ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4 Chiﬀrement aﬃne, algorithmes d’Euclide et Bézout 41 4.1 Le chiﬀrement aﬃne (début) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2 PGDC, Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3 L’égalité de Bézout (ou identité de Bézout) . . . . . . . . . . . . . . . . . . . . . . . 46 4.4 Le chiﬀrement aﬃne (suite) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.5 Un exemple de cryptanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.6 Un exemple de chiﬀrement polyalphabétique . . . . . . . . . . . . . . . . . . . . . . 54 I II 5 La cryptographie à clé publique : RSA 57 5.1 Quelques nouveaux outils mathématiques . . . . . . . . . . . . . . . . . . . . . . . . 57 5.2 La cryptographie à clé publique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.3 La cryptographie et les transactions bancaires (WEB) . . . . . . . . . . . . . . . . . 65 5.4 Il n’y a pas que la base 10 dans la vie. . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.5 Quelques bases utilisées dans le passé ou actuellement : . . . . . . . . . . . . . . . 68 5.6 Conversion d’une base vers une autre : . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.7 Les opérations en binaire (ou toute autre base. . . ) : . . . . . . . . . . . . . . . . . . 70 A Bibliographie 73 A Quelques éléments de solutions I A.1 Un doigt d’algorithmique avec SageMath . . . . . . . . . . . . . . . . . . . . . . . . I A.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VI A.3 Codage de César et congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . XII A.4 Codage aﬃne, algorithmes d’Euclide et Bézout . . . . . . . . . . . . . . . . . . . . . XVIII A.5 La cryptographie à clé publique : RSA . . . . . . . . . . . . . . . . . . . . . . . . . XXV Malgré le soin apporté lors de sa conception, le polycopié que vous avez entre les mains contient certainement quelques erreurs et coquilles. Merci de participer à son amélioration en m’envoyant un mail : jeanphilippe.javet@vd.educanet2.ch Merci ;-) 1 Un doigt d’algorithmique, intro à SageMath 1.1 Algorithmes, pseudo-code, SageMath Introduction: Al Khuwarizmi (env. 780 - 850) Projet Pseudo-code Algorithme(s) Programmation dans un langage à choisir Produit ﬁni Un algorithme est un moyen pour un humain de présenter la réso- lution par calcul d’un problème à une autre personne physique (un autre humain) ou virtuelle (un calculateur). En eﬀet, un algorithme est un énoncé dans un langage bien déﬁni d’une suite d’opérations permettant de résoudre par calcul un problème. Les algorithmes, dont on a retrouvé des descriptions exhaustives, ont été utilisés dès l’époque des Babyloniens (env. 1500 av. J-C.) pour des calculs concernant le commerce et les impôts. L’algorithme le plus célèbre est celui qui se trouve dans le livre 7 des Éléments d’Euclide. Il permet de trouver le plus grand diviseur uploads/S4/ occrypto.pdf