Remerciez-le!

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

Cryptographie Plan  Introduction  Le chiffrement de César  Le Chiffrement mo

Cryptographie Plan  Introduction  Le chiffrement de César  Le Chiffrement mono-alphabétique  Le chiffrement de Vigenère  La machine Enigma et les clés secrètes  La cryptographie à clé publique  L'arithmétique pour RSA  Le chiffrement RSA  L’avenir: la cryptographie quantique 2 •Cryptographie : Ensemble des techniques permettant de rendre un message inintelligible (kruptos : caché, graphein : écrire) •Cryptologie : Science des écritures secrètes •Chiffrement : Transformation d’un texte « clair » en texte « chiffré » à l’aide d’une clé •Décryptement : Rétablissement du texte clair sans connaissance de la clé (ou cryptanalyse) •Cryptogramme : Message secret Quelques définitions Introduction 3 • La même clé est utilisée pour chiffrer ET déchiffrer ; • Il faut garder la clé totalement confidentielle ; • Mise en œuvre complexe s’il y a un grand nombre de participants. 4 Chiffrement symétrique • Inventé pour résoudre le problème de l’échange des clés ; • Deux clés : publique pour le chiffrement ; privée pour le déchiffrement. • La clé publique est mise à disposition de tous (eg. Public Key Server) ; • Le message ne peut être déchiffré qu'avec la clé privée que le destinataire garde précieusement ; 5 Chiffrement asymétrique • Fonction qui permet de calculer pour un ensemble très grand un résultat précis (eg. chaine de caractères de taille fixe) ; • Souvent utilisé pour calculer des empreintes de gros fichiers ; • Représentation ou empreinte plus simple à manipuler en mémoire que le fichier source ; • Fonction à sens unique →opération inverse impossible ; • Est souvent utilisée pour garantir l’intégrité (non modification par une tierce personne). 6 Fonction de hachage •La substitution : Remplacement de chaque lettre du texte clair par des signes conventionnels (lettres, nombres, symboles), sans changer l’ordre. •La transposition : Modification de l’ordre des lettres (idem anagramme). Les deux principes du chiffrement Introduction 7 •Stéganographie : Art de dissimuler les messages secrets (steganos : opaque, graphein : écrire) •Exemples : Encre sympathique, dos de timbre. Le Dormeur du val (Arthur Rimbaud) – dernier tercet Les parfums ne font pas frissonner sa narine ; Il dort dans le soleil, la main sur sa poitrine, Tranquille. Il a deux trous rouges au côté droit. Une technique complémentaire : la stéganographie Introduction 8 • première trace de procédé de dissimulation intentionnel ; Principe : • destinataire et émetteur ont deux bâtons strictement identiques ; • l’émetteur enroule une courroie autour du bâton ; • l’émetteur écrit le message puis déroule la courroie ; • le destinataire n’a qu’à enrouler la courroie autour de son bâton pour lire le message ! • Message chiffré : KTMIOILMDLONKRIIRGNOHGWT 9 La scytale lacédémonienne Substitution : le chiffre de CESAR (1/9) César, pour ses communications importantes à son armée, cryptait ses messages. Ce que l’on appelle le chiffrement de César est un décalage des lettres : pour crypter un message, A devient D, B devient E, C devient F,... En vert c’est la partie du message à laquelle tout le monde a accès (ou qui pourrait être intercepté), c’est donc le message crypté. En rouge c’est la partie du message confidentiel, c’est le message en clair. 10 Pour prendre en compte aussi les dernières lettres de l’alphabet, il est plus judicieux de représenté l’alphabet sur un anneau. Ce décalage est un décalage circulaire sur les lettres de l’alphabet. Pour déchiffrer le message de César, il suffit de décaler les lettres dans l’autre sens, D se déchiffre en A, E en B,... Substitution : le chiffre de CESAR (2/9) 11 Substitution : le chiffre de CESAR (3/9) Des chiffres et des lettres Il est plus facile de manipuler des nombres que des lettres, aussi nous passons à une formulation mathématique. Nous associons à chacune des 26 lettres de A à Z un nombre de 0 à 25. En termes mathématiques, nous définissons une bijection : f : {A, B, C, ….Z} {0, 1, 2, ….25} Ainsi "A L E A" devient "0 11 4 0". Le chiffrement de César est un cas particulier de chiffrement mono alphabétique, c’est-à-dire un chiffrement lettre à lettre. Quel est l’intérêt ? Nous allons voir que le chiffrement de César correspond à une opération mathématique très simple. 12 Modulo Rappelons la notion de congruence et l’ensemble ℤ/26 ℤ. Soit n≥2 un entier fixé Définition 1 On dit que a est congru à b modulo n, si n divise (b-a). On note alors: a ≡ b (mod n). Pour nous n = 26. Ce qui fait que 28 ≡2 (mod 26), car (28-2) est bien divisible par 26. De même 85 = 3*26 + 7 donc 85 ≡7 (mod 26). Plus généralement ℤ/n ℤcontient n éléments. Pour un entier a ϵ ℤ quelconque, son représentant dans {0, 1, 2, . . . , n-1} s’obtient comme le reste k de la division euclidienne de a par n : a = bn + k. De sorte que a≡k(mod n) et 0 ≤ k < n. Substitution : le chiffre de CESAR (4/9) 13 De façon naturelle l’addition et la multiplication d’entiers se transposent dans ℤ/n ℤ. Addition Pour (a, b)ϵ ℤ/n ℤ, on associe (a + b) ϵ ℤ/n ℤ. Exemples: Dans ℤ/26 ℤ, 15+13 égale 2 15+13=28≡2 (mod26) Dans ℤ/26 ℤ, que vaut (133+ 64)? (133+ 64)=197=7x26+15 ≡15 (mod 26) 133=5x26+3 ≡3 (mod 26) 64=2x26+12 ≡12 (mod 26) 133+64≡(3+12) (mod26) Substitution : le chiffre de CESAR (5/9) 14 De façon naturelle l’addition et la multiplication d’entiers se transposent dans ℤ/n ℤ. Multiplicatin Pour (a, b)ϵ ℤ/n ℤ, on associe (a x b) ϵ ℤ/n ℤ. Exemples: Dans ℤ/26 ℤ, 3 x12 est congru à 10 modulo 26 3x12=36=1x26+10≡10 (mod26) Dans ℤ/26 ℤ, que vaut (3x27)? (3 x 27)=81=3x26+3 ≡3 (mod 26) 3=0x26+3 ≡3 (mod 26) 27=1x26+1 ≡1 (mod 26) 3 x 27≡(3x1) (mod26) Substitution : le chiffre de CESAR (6/9) 15 Chiffrer et déchiffrer Le chiffrement de César est simplement une addition dans ℤ/26 ℤ! Fixons un entier k qui est le décalage et définissons la fonction de chiffrement de César de décalage k qui va de l’ensemble Z=26Z dans lui-même : Pour déchiffrer, rien de plus simple ! Il suffit d’aller dans l’autre sens, c’est- à-dire ici de soustraire. La fonction de déchiffrement de César de décalage k est Substitution : le chiffre de CESAR (7/9) 16 Exemple Alice veut envoyer des messages secrets à Bruno. Ils se sont d’abord mis d’accord sur une clé secrète k, par exemple k = 11. Substitution : le chiffre de CESAR (8/9) 17 Combien existe-t-il de possibilités de chiffrement par la méthode de César ? Il y a 26 fonctions Ck différentes, k = 0,1, . . . ,25. Encore une fois, k appartient à ℤ/26 ℤ, car par exemple les fonctions C29 et C3 sont identiques. Le décalage k s’appelle la clé de chiffrement, c’est l’information nécessaire pour crypter le message. Il y a donc 26 clés différentes et l’espace des clés est ℤ/26 ℤ. Espace des clés et attaque Il est clair que ce chiffrement de César est d’une sécurité très faible. Si Alice envoie un message secret à Bruno et que Chloé intercepte ce message, il sera facile pour Chloé de tester ce que donne chacune des 26 combinaisons possibles et de reconnaître parmi ces combinaisons laquelle donne un message compréhensible. Substitution : le chiffre de CESAR (9/9) 18 Transposition: 1er exemple (1/2) IONDE NSIAS UIETA EVMOM RUDSI REUNION DES AMIS DU VISIATOME 19 Transposition: 2ème exemple (2 /2) C E S T S U P E R 20 Chiffrement mono-alphabétique (1/5) Nous avons vu que le chiffrement de César présente une sécurité très faible, la principale raison est que l’espace des clés est trop petit : il y a seulement 26 clés possibles, et on peut attaquer un message chiffré en testant toutes les clés à la main. Au lieu de faire correspondre circulairement les lettres, on associe maintenant à chaque lettre une autre lettre (sans ordre fixe ou règle générale). Exemple: ETRE OU NE PAS ETRE TELLE EST LA QUESTION XGKX DR SX OFV XGKX GXWWX XVG WF ZRXVGPDS 21 Avantage : nous allons voir que l’espace des clés est gigantesque et qu’il n’est plus question d’énumérer toutes les possibilités. Inconvénients : la clé à retenir est beaucoup plus longue, puisqu’il faut partager la clé constituée des 26 lettres "FQBMX...". Mais surtout, nous allons voir que finalement ce protocole de chiffrement est assez simple à « craquer ». Espace des clés Mathématiquement, le choix d’une clé revient au choix d’une bijection de l’ensemble {A, B, . . . , Z} vers le même ensemble {A, B, . . . , Z}. Il y a 26!=4 x1026 clés possibles. Si un ordinateur pouvait tester 1 000 000 de clés par seconde, il lui faudrait alors 12 millions d’années pour tout énumérer. Chiffrement mono-alphabétique (2/5) 22 Attaque statistique: La principale faiblesse du chiffrement mono alphabétique est qu’une même lettre est toujours chiffrée de la même façon. Par exemple, ici E devient X. Dans les textes uploads/Finance/ cours-cryptographie-etudiant.pdf