Crypto - Notions de base

  • Published on
    30-Jun-2015

  • View
    1.803

  • Download
    1

Transcript

CryptographieDr. Naouel Ben Salem GratiPlan Gnral du cours Introduction Algorithmes standards de cryptographie Chiffrement symtrique Chiffrement de flux (Stream cipher) ( p ) Chiffrement par blocs (Block cipher) Chiffrement asymtrique Fonctions de hashage Intgrit et Authentification HMAC Signatures Gestion des cls Distribution des cls secrtes Gnration et distribution des certificats Protocoles de scurit et standards divers21Plan Gnral du cours Introduction Algorithmes standards de cryptographie Chiffrement symtrique Chiffrement de flux (Stream cipher) ( p ) Chiffrement par blocs (Block cipher) Chiffrement asymtrique Fonctions de hashage Intgrit et Authentification HMAC Signatures Gestion des cls Distribution des cls secrtes Gnration et distribution des certificats Protocoles de scurit et standards divers3Introduction Cryptographie: vient du grec kruptos ("cach") et graphein ("crire"). Vocabulaire: chiffrement : transformation l'aide d'une cl de chiffrement d'un message en clair (dit texte clair) en un message incomprhensible (dit texte chiffr) si on ne dispose pas d'une cl de dchiffrement (en anglais encryption) ; cryptogramme : message chiffr ; dcrypter : retrouver le message clair correspondant un message chiffr sans possder la cl de dchiffrement (terme que ne possdent pas les anglophones, qui eux cassent des codes secrets) ; cryptographie : tymologiquement criture secrte , devenue par extension l' l'tude de cet art; cryptanalyse : science analysant les cryptogrammes en vue de les dcrypter ; cryptologie : science regroupant la cryptographie et la cryptanalyse42Un peu dhistoire Le premier document chiffr connu remonte l'Antiquit. Il s'agit d'une tablette d'argile, retrouve en Irak, et datant du XVIe sicle av. J.-C. Un potier y avait grav sa recette secrte en supprimant des consonnes et en modifiant l orthographe des mots. l'orthographe mots La technique grecque: Entre le Xe et VIIe sicle av. J.-C. Technique de chiffrement par transposition, c'est--dire reposant sur le changement de position des lettres dans le message, en utilisant un bton de diamtre dtermin appele scytale. On enroulait en hlice une bande de cuir autour de la scytale avant d'y inscrire un message. Une fois droul, le message tait envoy au destinataire qui possdait un bton identique ncessaire au dchiffrement identique, dchiffrement.5Un peu dhistoire La technique des Hbreux: partir du Ve sicle av. J.-C., l'une des premires techniques de chiffrement est utilise dans les textes religieux par les Hbreux qui connaissent plusieurs procds. Le l L plus connu appel Atb h est une mthode de substitution l Atbash t th d d b tit ti alphabtique inverse. Elle consiste remplacer chaque lettre du texte en clair par une autre lettre de l'alphabet choisie de la manire suivante : A devient Z, B devient Y, etc. Nabuchodonosor: Aux alentours de -600, Nabuchodonosor, roi de Babylone, employait une mthode originale : il crivait sur le crne ras de ses esclaves, attendait que leurs cheveux aient repouss, et il les envoyait ses gnraux Il suffisait ensuite de raser nouveau gnraux. le messager pour lire le texte. Il s'agit toutefois de stganographie proprement parler et non pas de cryptographie : l'information est cache et non pas code. On remarque dans ce procd une certaine fiabilit : en effet l'interception du message par un tiers est tout de suite remarque.63Un peu dhistoire Les premiers vrais systmes de cryptographie: Il faut attendre -200 pour voir apparatre les premiers vrais systmes de cryptographie. Ce sont essentiellement des chiffrements par substitution. substitution Il existe diffrents types de substitutions : mono-alphabtique : remplace chaque lettre du message par une autre lettre de l'alphabet poly-alphabtique : utilise une suite de chiffres monoalphabtiques (la cl) rutilise priodiquement polygrammes : substitue un groupe de caractres dans le message par un autre groupe de caractres 7Un peu dhistoire Le code de Csar: Le code de Csar est la mthode cryptographique, par substitution mono-alphabtique, la plus ancienne (Ier sicle av. J.-C.). C tt mthode est utilise dans l'arme romaine et bien qu'elle soit Cette th d t tili d l' i t bi ' ll it beaucoup moins robuste que la technique Atbash, la faible alphabtisation de la population la rend suffisamment efficace. Mthode de chiffrement: Dcaler les lettres de l'alphabet d'un nombre n. Par exemple, si on remplace A par D (n=3), on remplace B par E, C par F... Le texte que nous souhaitons coder tant le suivant : dcaler les lettres de l'alphabet l tt s d l' l h b t Le texte cod est alors : ghfdohu ohv ohwwuhv gh o'doskdehw 84Un peu dhistoire Le code de Csar: Inconvnient: Ce systme est trs peu sr, puisqu'il n'y a que 26 lettres dans l'alphabet donc seulement 25 faons de chiffrer un message avec le code d C l d de Csar (on ne peut substituer une l tt par ( t b tit lettre elle-meme). Pourtant sa simplicit conduisit les officiers sudistes le remployer durant la guerre de Scession. L'arme russe en fit de mme en 1915. Un systme connu et pourtant Le code de Csar a t utilis sur des forums internet sous le nom de ROT13 (rot-ation de 13 lettres ou AN...). Le ROT13 n'a pas pour but de rendre du texte confidentiel, confidentiel mais plutt d empcher la lecture involontaire (d une d'empcher (d'une rponse une devinette, ou de l'intrigue d'un film, etc.). Son utilisation est simple : il suffit de re-chiffrer un texte, cod en ROT13, une deuxime fois pour obtenir le texte en clair.9Un peu dhistoire Le chiffre de Vigenre est un systme de chiffrement, labor par Blaise de Vigenre (1523-1596), diplomate franais du XVIe sicle. C'est un systme de substitution poly-alphabtique ou de chiffrement polyalphabtique Cela signifie qu il permet de polyalphabtique. qu'il remplacer une lettre par une autre qui n'est pas toujours la mme, contrairement au chiffre de Csar ou ROT13 qui se contentaient d'utiliser la mme lettre de substitution. C'est donc un systme relativement plus solide que ces deux systmes. Principe: Ce chiffrement introduit la notion de cl. Une cl se prsente gnralement sous la forme d'un mot ou d'une phrase. Pour p pouvoir chiffrer notre texte, chaque caractre nous utilisons une ff , q lettre de la cl pour effectuer la substitution. videmment, plus la cl sera longue et varie et mieux le texte sera chiffr. Il faut savoir qu'il y a eu une priode o des passages entiers d'uvres littraires taient utiliss pour chiffrer les plus grands secrets. Les deux correspondants n'avaient plus qu' avoir en leurs mains un exemplaire du mme livre pour s'assurer de la bonne comprhension 10 des messages.5Un peu dhistoire Table de Vigenre:11Un peu dhistoire Le chiffre de Vigenre: Pour chaque lettre en clair, on slectionne la colonne correspondante et pour une lettre de la cl on slectionne la ligne adquate, puis au croisement de la ligne et de la colonne on trouve la lettre chiffre. La lettre de la cl est prendre dans chiffre l'ordre dans laquelle elle se prsente et on rpte la cl en boucle autant que ncessaire. cl : MUSIQUE texte : j'adore ecouter la radio toute la journee j'adore ecouter la radio toute la journee M USIQU EMUSIQU EM USIQU EMUSI QU EMUSIQU | ||| | || Colonne O, ligne I : on obtient la lettre W. | | Colonne D, ligne S : on obtient la lettre V. | Colonne A, ligne U : on obtient la lettre U. Colonne J, ligne M : on obtient la lettre V.126Un peu dhistoire Le texte chiffr est alors : V'UVWHY IOIMBUL PM LSLYI XAOLM BU NAOJVUY. Si on veut dchiffrer ce texte, on regarde pour chaque lettre de la p cl rpte la ligne correspondante, et on y cherche la lettre chiffre. La premire lettre de la colonne que l'on trouve ainsi est la lettre dchiffre. V'UVWHY IOIMBUL PM LSLYI XAOLM BU NAOJVUY M USIQU EMUSIQU EM USIQU EMUSI QU EMUSIQU | ||| | || Ligne I, on cherche W: on trouve la colonne O I O. | | Ligne S, on cherche V: on trouve la colonne D. | Ligne U, on cherche U: on trouve la colonne A. Ligne M, on cherche V: on trouve la colonne J.13Un peu dhistoire Enigma est une machine lectromcanique portable d'origine allemande, faisant appel des rotors monts sur cylindres pour le chiffrement et le dchiffrement de l'information. Plus prcisment, Enigma est une famille de machines, car il en a exist de machines nombreuses et subtiles variantes. Enigma fut commercialise en Europe et dans le reste du monde ds le dbut des annes 1920. Elle fut aussi adapte pour une utilisation par les services militaires et diplomatiques de nombreuses nations. Son utilisation la plus fameuse fut celle de l'Allemagne nazie et de ses allis, avant et pendant la Seconde Guerre mondiale.147Un peu dhistoire Bien qu'elle ft considre avant la Seconde Guerre mondiale comme sre par ses utilisateurs, les cryptologues britanniques furent, plusieurs reprises et sur de longues dures, capables de dcrypter les messages protgs par ces machines Les informations machines. obtenues grce cette source leur donnrent un net avantage dans la poursuite de la guerre. Enigma chiffre les informations en ralisant le passage d'un courant lectrique travers une srie de composants. Le courant est transmis en pressant une lettre sur le clavier. Aprs sa traverse dans un rseau complexe de fils, une lampe indique la lettre chiffre. chiffre15Critres de scuritAlice Bob Confidentialit (confidentiality): garantie que seules les personnes autorises ont accs aux lments considrs. Intgrit des donnes (data integrity): garantie que les lments considrs sont exacts et complets. Authentification (authentication): possibilit de vrifier l'identit d'une entit (personne, ordinateur...), afin d'autoriser l'accs de cette entit des ressources (systmes rseaux, applications...). (systmes, rseaux applications ) Non-rpudiation (non-repudiation): la possibilit de vrifier que l'envoyeur et le destinataire sont bien les parties qui disent avoir respectivement envoy ou reu le message.168Critres de scurit Autres aspects importants Disponibilit (availability): garantie que ces lments considrs sont accessibles au moment voulu par les personnes autorises. Anonymat (privacy): garantie que l identit et/ou la localisation lidentit de lentit reste(nt) confidentielle(s). Un outil fondamental pour assurer la scurit est la cryptographie La cryptographie et la cryptanalyse sont des outils importants pour assurer la confidentialit d'une information (stocke ou transite), son intgrit (toute modification est dtectable), et l'identification de son origine (l'metteur peut tre identifi).17Types dattaquesPassiveAlice Eve BobEcouteAlice TrudyBobModificationAc ctiveAlice TrudyBobFabricationAlice TrudyBobRe-jeux189Primitives CryptographiquesArbitrary length hash functions Primitives sans cls One-way permutations Squences alatoires Chiffrement cl symtrique Arbitrary length hash functions (MACs) Primitives de scurit Primitives cl symtrique Signatures Squences Pseudoalatoires Primitives didentification Chiffrement cl publique Primitives cl publique Signatures Primitives didentification 19 Stream ciphers Block ciphersChiffrement Le nud S envoie le message m au noeud R via un canal non scuris. S chiffre m en utilisant un algorithme de chiffrement E et une cl de chiffrement K n l d hiff m nt K. EK(m) est le texte chiffr (ciphertext) m est le texte en clair (plaintext) R dcrypte le texte chiffr avec un algorithme de dchiffrement D et d'une cl de dchiffrement K2010Primitives CryptographiquesArbitrary length hash functions Primitives sans cls One-way permutations Squences alatoires Chiffrement cl symtrique Arbitrary length hash functions (MACs) Primitives de scurit Primitives cl symtrique Signatures Squences Pseudoalatoires Primitives didentification Chiffrement cl publique Primitives cl publique Signatures Primitives didentification 21 Stream ciphers Block ciphersK = KK KCryptographie symtrique Aussi appele cryptographie cl secrte Les algorithmes de chiffrement symtrique se fondent sur une mme cl pour chiffrer et dchiffrer un message. Le problme de cette t h i tt technique est que l cl, qui doit rester t t l t la l i d it t totalement t confidentielle, doit tre transmise au correspondant de faon sre. Exemples dalgorithmes de chiffrement symtrique trs utiliss : Chiffre de Vernam DES 3DES AES RC4 RC5 2211Cryptographie asymtrique Aussi appele cryptographie cl publique (et prive) Pour rsoudre le problme de l'change de cls, la cryptographie asymtrique a t mise au point dans les annes 1970. Elle se base sur l principe d d le i i de deux cls : l une publique, permettant le chiffrement ; une prive, permettant le dchiffrement. Comme son nom l'indique, la cl publique est mise la disposition de quiconque dsire chiffrer un message. Ce dernier ne pourra tre dchiffr qu'avec la cl prive, qui doit tre confidentielle. Quelques algorithmes de cryptographie asymtrique trs utiliss : Q q g yp g p y q RSA (chiffrement et signature); DSA (signature); Protocole d'change de cls Diffie-Hellman (change de cl); 23Cryptographie asymtrique Le principal inconvnient de RSA et des autres algorithmes cls publiques est leur grande lenteur par rapport aux algorithmes cls secrtes. RSA est par exemple 1000 fois plus lent que DES. En pratique, pratique dans le cadre de la confidentialit on s'en sert pour confidentialit, s en chiffrer un nombre alatoire qui sert ensuite de cl secrte pour un algorithme de chiffrement symtrique . C'est le principe qu'utilisent des logiciels comme PGP par exemple. La cryptographie asymtrique est galement utilise pour assurer l'authenticit d'un message. L'empreinte du message est chiffre l'aide de la cl prive et est jointe au message. Les destinataires dchiffrent ensuite le cryptogramme l'aide de la cl publique et l aide retrouvent normalement l'empreinte. Cela leur assure que l'metteur est bien l'auteur du message. On parle alors de signature ou encore de scellement.2412Fonctions de Hashage Une fonction de hachage est une fonction qui convertit un grand ensemble en un plus petit ensemble, l'empreinte. Il est impossible de la dchiffrer pour revenir l'ensemble d'origine, ce n'est donc pas une technique de chiffrement chiffrement. Quelques fonctions de hachage trs utilises : MD5 ; SHA-1 ; SHA-256 ; L'empreinte d un message ne dpasse gnralement pas 256 bits L empreinte d'un (maximum 512 bits pour SHA-512) et permet de vrifier son intgrit.25Plan Gnral du cours Introduction Algorithmes standards de cryptographie Chiffrement symtrique Chiffrement de flux (Stream cipher) ( p ) Chiffrement par blocs (Block cipher) Chiffrement asymtrique Fonctions de hashage Intgrit et Authentification HMAC Signatures Gestion des cls Distribution des cls secrtes Gnration et distribution des certificats Protocoles de scurit et standards divers2613Block Ciphers Le chiffrement par bloc (en anglais block cipher) est une mthode de chiffrements symtrique qui dcoupe le texte chiffrer en blocs de taille gnralement fixe. L taille d bl est comprise entre 32 et 512 bit La t ill de bloc t i t t bits Dans le milieu des annes 1990 le standard tait de 64 bits Depuis 2000 le standard est de 128 bits Les blocs sont ensuite chiffrs les uns aprs les autres. Il est possible de transformer un chiffrement de bloc en un chiffrement par flot en utilisant un mode d'opration d opration ECB (chaque bloc chiffr indpendamment des autres) CFB (on chane le chiffrement en effectuant un XOR entre les rsultats successifs).27Block CiphersElectronic Code Book mode (ECB): + : implementation simple - : un attaquant peut aisment remplacer un block Cipher FeedBack mode (CFB): x1 eK y1 y2 x1 eK y1 x2 ... x2 eK y2 x3 eK y3IVeKIV: Initial Vector But: chaque message cod devient unique Gnration: timestamp ou nombre alatoire (random number)2814Block CiphersCipher Block Chaining mode (CBC): IV= y0 eK y1 z1 eK x2 y1 y2 eK y2 z2 ... x1 x2 ...Output FeedBack mode (OFB): IV= z0 eK x129Stream Ciphers Le texte en clair est combin avec un keystream (un flot de cls de chiffrement pseudo-alatoire), gnralement en utilisant lopration exclusive-or (xor). 1 ti time pad: d3015Stream Ciphers Un synchronous stream cipher est un schma de chiffrement dans lequel le keystream est gnr indpendament du text en clair (plaintext) et du texte chiffr (ciphertext). 0 : tat initial (initial state) i i i l (i i i l ) f : Next-state function G : The function which produces the keystream zi H : Output function.31Stream Ciphers La plupart des schmas de chiffrement flot proposs dans la littrature sont additifs Definition: Un binary additive stream cipher est un synchronous stream cipher dans l t i h d lequel le keystream, le texte en clair et le texte ll k t l t t l i tl t t chiffr sont des donnes binaires, et le rsultat de la fonction h est une fonction XOR.3216Data Encryption Standard (DES) Cest LE schma de chiffrement symtrique par bloc Developp dans les annes 70 par IBM, standard ANSI en 1981 (ANSI X3.92) ( ) Largement utilis dans les transactions bancaires Nest plus considr comme suffisament robuste Principe: Plaintext: 64 bitsKey: 56 bitsDESCiphertext: 64 bits33DES Algorithm64 bits Plaintext 32 bits L0 IP 32 bits R0 K1 48 bitsR1 L0 f ( R 0 , K1 )fL1=R0fL2 =R1R 2 L1 f ( R 1 , K 2 )K2 48 bits K Key scheduler 56 bitsL15=R14R15 L14 f ( R14 , K15 )fK16 48 bitsR16 L15 f (R15, K16 )IP-1 Ciphertext 64 bitsL16=R15 IP: Initial Permutation 3417Initial PermutationIP58 60 62 64 57 59 61 63 50 52 54 56 49 51 53 55 42 44 46 48 41 43 45 47 34 36 38 40 33 35 37 39 26 28 30 32 25 27 29 31 18 20 22 24 17 19 21 23 10 12 14 16 9 11 13 15 2 4 6 8 1 3 5 7 40 39 38 37 36 35 34 33 8 7 6 5 4 3 2 1 48 47 46 45 44 43 42 41IP-116 15 14 13 12 11 10 9 56 55 54 53 52 51 50 49 24 23 22 21 20 19 18 17 64 63 62 61 60 59 58 57 32 31 30 29 28 27 26 25 Comme rsultat de la permutation initiale IP, le 58me bit devient le 1er, le 50me devient le second, IP-1 est la fonction inverse de la permutation initiale IP35Initial Permutation3618DES Algorithm64 bits Plaintext 32 bits L0 IP 32 bits R0 K1 48 bitsR1 L0 f ( R 0 , K1 )fL1=R0fL2 =R1R 2 L1 f ( R 1 , K 2 )K2 48 bits K Key scheduler 56 bitsL15=R14R15 L14 f ( R14 , K15 )fK16 48 bitsR16 L15 f (R15, K16 )IP-1 Ciphertext 64 bitsL16=R15 IP: Initial Permutation 37One Round of DES32 bits Li-1 32 bits Ri-1 32 bits Expansion permutation 48 bits Compr. permutation Shift 56 bits Key Shift48 bits S-Box Substitution 32 bits P-Box Permutation 32 bitsLiRiKey3819Expansion Permutation Function : 32-bit block input 48-bit block outputE32 4 8 12 16 20 24 28 1 5 9 13 17 21 25 29 2 6 10 14 18 22 26 30 3 7 11 15 19 23 27 31 4 8 12 16 20 24 28 32 5 9 13 17 21 25 29 1 The first three bits of E(R) are the bits in positions 32, 1 and 2 of R while the last 2 bits of E(R) are the bits in positions 32 and 1.39Expansion Permutation4020One Round of DES32 bits Li-1 32 bits Ri-1 32 bits Expansion permutation 48 bits Compr. permutation Shift 56 bits Key Shift48 bits S-Box Substitution 32 bits P-Box Permutation 32 bitsLiRiKey41S-Box Substitution4221S-Box Substitution Function : 6-bit block input 4-bit block output Given a 6-bit input, the 4-bit output is found by selecting: input the row using the outer two bits (the first and last bits), and the column using the inner four bits. For example, an input "011011" has outer bits "01" and inner bits "1101"; the corresponding output would be "1001"43One Round of DES32 bits Li-1 32 bits Ri-1 32 bits Expansion permutation 48 bits Compr. permutation Shift 56 bits Key Shift48 bits S-Box Substitution 32 bits P-Box Permutation 32 bitsLiRiKey4422P-Box Permutation The permutation function P yields a 32-bit output from a 32-bit input by permuting the bits of the input block.P16 29 1 5 2 32 19 22 7 12 15 18 8 27 13 11 20 28 23 31 24 3 30 4 21 17 26 10 14 9 6 2545P-Box Permutation4623DES Algorithm64 bits Plaintext 32 bits L0 IP 32 bits R0 K1 48 bitsR1 L0 f ( R 0 , K1 )fL1=R0fL2 =R1R 2 L1 f ( R 1 , K 2 )K2 48 bits K Key scheduler 56 bitsL15=R14R15 L14 f ( R14 , K15 )fK16 48 bitsR16 L15 f (R15, K16 )IP-1 Ciphertext 64 bitsL16=R15 IP: Initial Permutation 47One Round of DES32 bits Li-1 32 bits Ri-1 32 bits Expansion permutation 48 bits Compr. permutation Shift 56 bits Key Shift48 bits S-Box Substitution 32 bits P-Box Permutation 32 bitsLiRiKey4824Key Schedule in DES49Permuted ChoicePC-157 1 10 19 63 7 14 21 49 58 2 11 55 62 6 13 41 50 59 3 47 54 61 5 33 42 51 60 39 46 53 28 25 34 43 52 31 38 45 20 17 26 35 44 23 30 37 12 9 18 27 36 15 22 29 4 14 3 23 16 41 30 44 46 17 28 19 7 52 40 49 42PC-211 15 12 27 31 51 39 50 24 6 4 20 37 45 56 36 1 21 26 13 47 33 34 29 5 10 8 2 55 48 53 32CD5025Permuted Choice51Key Schedule in DES5226Left ShiftIteration 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Nb of LS 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1531 Left Shift (LS)1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 11 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1Plan Gnral du cours Introduction Algorithmes standards de cryptographie Chiffrement symtrique Chiffrement de flux (Stream cipher) ( p ) Chiffrement par blocs (Block cipher) Chiffrement asymtrique Fonctions de hashage Intgrit et Authentification HMAC Signatures Gestion des cls Distribution des cls secrtes Gnration et distribution des certificats Protocoles de scurit et standards divers5427Primitives CryptographiquesArbitrary length hash functions Primitives sans cls One-way permutations Squences alatoires Chiffrement cl symtrique Arbitrary length hash functions (MACs) Primitives de scurit Primitives cl symtrique Signatures Squences Pseudoalatoires Primitives didentification Chiffrement cl publique Primitives cl publique Signatures Primitives didentification 55 Stream ciphers Block ciphersK = KK KChiffrement asymtrique Confidentialit: Alice utilise la cl publique de Bob pour coder un message que seul Bob (en possession de la cl prive) peut dcoder Authentification: Bob utilise sa propre cl prive pour coder un message que Alice peut dcoder avec la cl publique Algorithmes de gnration de paires de cls Algorithme de chiffrement Algorithme de dchiffrement Examples: RSA ElGamal ECC5628RSA: introduction RSA: Rivest, Shamir et Adleman du MIT en 1977 Systme le + connu et le + largement rpandu 100 1000 fois plus lent que DES 00 000 fo s bas sur l'lvation une puissance dans un champ fini sur des nombres entiers modulo un nombre premier Le nombre dexponentiation prend environ O((log n)3) oprations facile emploie de grands nombres entiers (par exemple 1024 bits) scurit due au cot de factoriser de grands nombres Le nombre de factorisation prend environ O(e log n log log n) oprations difficile Usage : confidentialit, authentification57RSA: principe Choisir p et q, deux nombres premiers distincts et de taille peu prs gales Noter le module de chiffrement n=pq La longueur de n devrait tre entre 1024 et 2048 bits Calculer l'indicatrice d'Euler de : (n)=(p-1)(q-1) Choisir e, un entier premier avec (n), appel exposant de chiffrement (pgcd(e, (n))=1). Comme e est premier avec (n), il est, d'aprs le thorme de Bachet-Bzout inversible mod (n) c'estBachet Bzout, (n), c est -dire qu'il existe un entier d tel que ed1 mod (n). d est l'exposant de dchiffrement. Le couple (n,e) est appel cl publique d est appel cl prive.5829RSA Exemple Bob choisi p=61 et q=53 n=pq=3233 (n)=60x52=3120 Bob choisi e tel que pgcd((n),e)=1. On suppose que e=17 d=e-1 mod (n) = 2753 mod 3120 (cl prive) Bob publie n et e (cl publique) Chiffrement Dchiffrement : enc(X) = (X^e) mod n = (X^17) mod 3233 (X e) (X 17) : dec(X) = (X^d) mod n = (X^2753) mod 3233 enc(123) = (123^17) mod 3233 = 337587917446653715596592958817679803 mod 3233 = 85559RSA - Exemple dec(855) = (855^2753) mod 3233 = 504328889584160687344228991273944666314538783600355093155549675645010 556286120825599787442454281100543834986542893363849302464514415078517 20917966547826353070996380353873265008966860747718297458229503429504 07903581845940956377938586598936883808360284013250976862076697739667 0 9035818459409563 9385865989368838083602840132509 68620 669 3966 533250542826093475735137988063256482639334453092594385562429233017519 77190016924916912809150596019178760171349725439279215696701789902134307 1464689712796102771813783945869677289869342365240311693217089269617643 7265213156658331587124597598030425031440068378832461017848307175854745 47252069688925995892544366701432205469543174002285500923863694244485 597333306305160738530286321930291350374547194675777671357954965202919 790505781532871558392070303159585937493663283548602090830635507044556 5889631931801193412201782692334410133011648069633402407504695258866987 658669006224024102088466507530263953870526631933584734810948761562271 260373275973603752373883641480889484380961577570453800810794698006673 487779588375828998513279307035335512750904399481789790548993381217329 458535447413268056981087263348285463816885048824346588978393334662544 540066196452187666947955280230884124659482392751057704911332902568430 65052292561427303898320890070515110552506189941712317779515797942971179 5475296301837843862913977877661298207389072796767202350113992715819642 7307640741898919048686074812454931579537437712441601438765069145868196 402276027766869530903951314968319097324505452345944772565878876926933 60 539186923548185185424209230649964068221844901191357108854244285211207730RSA - Exemple3712238311054554312653073940759278908226060431711333957522660344516452 5976316184277459043201913452893299321613074405322274705728948121435868 31978415597276496357090901215131304157569209798518321041155969357848833 665315951327344675243940875769777890849012691532284208094963079297247 1304422194243906590308142893930291584830873687450789770869218452967411 463211556678655283381648067954559418910069509196589908545679807239237 0846302553545686919235546299571573587906227458619572172111078828657563 8597094190776320509783239571346411902500470208485604082175094910771655 3117652974738031767658205876731402889103288343185088447211644271939037 4041315564986995913736516210845113740224335185995766577539693628125425 3900685526245456141925880943740212888666974410972184534221817198089911 953707545542033911964539366461792968165342652234639936742330970183533 904623677693670380534264482173582384219251590438148524738896864244370 3186654199615377913969649003039587606549152449450436001359392771339521 0125192857209259788751160195962961569027116431894637342650023631004555 718003693586055264910000907245183786689564417164907278356281009708545 2413546966084481161338780654854515176167308605108065782936524108723263 6672280540038794108643482267500907782651210137281958316531396983090887 317417474535988684298559807185192215970046508106068445595364808922494 405427663296745923088984848684358654798505115428440164623526969317993 7784430217857019197098751629654665130278009966580052178208139317232379 0132324946826092008199810376848471678749891936949979148247163450609371 256541225019537951668976018550875993133677977939527822273233375295802 61 631226653589482055665152894663690320832876804323906115493509545909340RSA - Exemple667640225867084833760536998679410262047090571567447056531112428629073 548884929899835609996360921411284977458614696040287029670701478179490 248282907484160083680458666855076046192252094349804715745268818131850 8591501948527635965034581536416565493160130613304074344579651083803040 622402788980428251890947162922668980166844809636451980905109057965130 7570379245958074479752371266761011473878742144149154813591743927994969 56415653866883891715446305611805369728343470219206348999531917640161103 9249043917980339897549176539592360851180765318470647331801578207412764 787592739087492955716853665185912666373831235945891267870958380002245 150942445756487448408687753084539552173063669389170239403718478036277 46431714708558304919598951467762943921431002456130611142993700055775133 97172825491100560089408984196713197091181655429087610900832499783133824 078696157849234198629916800867749593407759306602207814943807854996798 945399364063685722697422361858411425048372451244655802708591797955910 865230997565198382779529457569965742455786883835444236857223681399021 2613637440821314784832035636156113462870198514239018429097416386202320 5103971218498335528630868518428263461502744187358639504042281512399505 995983653792227285847422071677836679451343638070865797742198535953931 66279988789721695963455346336497949221130176613162074772661131070123214 037138822702217232330854726795330150799806225383545894802482004314472 6191596190526034069061930939290724102849487001671729695177034679099794 409750637649296356755580071162182772760318292179035029048609097626628 5396627024392536890256337101471683274045045830602286763142158159900791 62 642627700054612322919219299716990769016902594646810414121420447240266131RSA - Exemple6582756805241668614733933226595912700645630447416085291672187007045144 649793226668732146346749041185886760836840306190695786990096521390675 2050197440767765104388515194161931847991913492438815282203846472926944 6084915299958818598855195149066307311777238132267516945882593638786107 24302565980914901032783848214011365567849341024315124828645291703141004 001201636482998532516634905605379458508942440385525245547779224010461 4890752745163425139921637383568141490479320374263373019878254056996191 6352019389698254478631309773749154478427634532593998741700138163198116 6453772089440028548500026968598264456218379411670215184772190933923218 5087775790959332676311413129619398495926138987901669710881027663862316 7694057295932538078643444100512138025081797622723797210352196773268441 9464861640296105989902771053257045701633261343107641770004323715247462 63939901189972784536294930363691490088106053123163000901015083933188011 6682151638931046666595137827498923745560511004016477716822716267270783 701224246551264878454923504185216742638318973333243467444903978001784 6897264054621480241241258338435017048853206014756878623180940900126324 1969092252022679880113408073012216264404133887392600523096072386158554 9651580010347461197921307672245438036718832537086067133113258199227975 522771848648475326124302804177943090938992370938053652046462551472678 8496152777327411926570911661358008414542148768731039444105479639308530 896880365608504772144592172500126500717068969428154627563704588389042 19177398190648731908014828739058159462227867277418610111027632479729041 2221199411738820452633570175909067862815928151998221457652796853892517 63 21872009007038913856284000733225850759048534804656454349837073287625RSA - Exemple935891427854318266587294608072389652291599021738887957736477387265746 1040082255112418272009616818882849389467881046884731265541726209789056 7845810965179753008730631546490302112133528180847612299040957642785731 636412488093094977073956758842296317115846456984202455109029882398517 953684125891446352791897307683834073696131409745229856386682726910433 5751767712889452788136862396506665408989439495161912002160777898876864 7364818378253248466991683072812203107919356466684015914858269999337442 7677252275403853322196852298590851548110402296579163382573855133148234 5959163328144581984361459630602499361753097925561238039014690665163673 718859582772525683119989984646027216462797640770570748164064507697798 6995510618004647193780822325014893407851137833251073753823403466269553 2926088138438957840998041704104177760846306286261061405961520706669524 3018438575031762939543026312673774069364047058960834626018859111843675 3252984588804084971092299919565539701911191919188327308603766775339607 7224556321135065721910675875118681278634419757239219526333385653838824 0057190102564949233944519659592039923922174002472341471909709645621082 99547746193228981181286055565880938518988118129056142740858091687657119 1122476328865871275538928438126611991937924624112632990739867854558756 6524530561975098911457811473577128360755400177426866096509330517210272 306663573946233413638045914237759965220309418558880039496755829711258 3616218901403595423493042474905369399277611426179640710012764328042870 6083531594582305946326827861270203356980346143245697021484375 mod 3233 = 1236432Plan Gnral du cours Introduction Algorithmes standards de cryptographie Chiffrement symtrique Chiffrement de flux (Stream cipher) ( p ) Chiffrement par blocs (Block cipher) Chiffrement asymtrique Fonctions de hashage Intgrit et Authentification HMAC Signatures Gestion des cls Distribution des cls secrtes Gnration et distribution des certificats Protocoles de scurit et standards divers65Fonctions de hashage Une fonction de hachage est une fonction qui, partir d'une donne fournie en entre, calcule une empreinte servant identifier rapidement, bien qu'incompltement, la donne initiale. Cette empreinte peut tre aussi appele selon le contexte somme de contrle, hash, rsum de message, condens, condensat ou encoreempreinte cryptographique6633Fonctions de hashage Proprits respecter pour une fonction de hashage cryptographique: Collision resistance: Il est trs difficile de trouver deux valeurs x et x telles que h(x) = h(x). W k collision resistance: Et t d Weak lli i i t Etant donn une valeur x, il est trs l st t s difficile de trouver une valeur x' qui vrifie h(x) = h(x). Cette proprit est parfois appele second pre-image resistance. One-way property: Pour n'importe quelle valeur hash y, il est trs difficile de trouver une valeur x telle que h(x) = y. Cette proprit est parfois appele pre-image resistance.Hash function (hash, (hash hash value, hash code)Data Arbitrary lengthDigest Fixed length Trs difficile = techniquement impossible en pratique par toutes techniques algorithmiques et matrielles, en un temps raisonnable67Principe de baseCV f k n b= = = = =chaining variable algorithme de compression Nombre de blocs longueur du code hash longueur du bloc6834Exemple: MD5 MD5: Message Digest 5, est une fonction de hachage cryptographique qui permet d'obtenir l'empreinte numrique d'un fichier / message I Invent par Ronald Rivest (le R d RSA) t R ld Ri t (l de En 1996, une faille qualifie de grave (possibilit de crer des collisions la demande) est dcouverte et indique que MD5 devrait tre mis de ct au profit de fonctions plus robustes comme SHA-1. MD5 est encore largement utilis comme outil de vrification lors des tlchargements pour valider l'intgrit de la version tlcharge grce l'empreinte. MD5 peut aussi tre utilis pour calculer l'empreinte d'un mot de ' ' passe ; c'est le systme employ dans GNU/Linux plutt que de stocker les mots de passe dans un fichier, ce sont leurs empreintes MD5 qui sont enregistres; quelqu'un qui lirait ce fichier ne pourra pas dcouvrir les mots de passe.69MD5: Principe7035MD5: Principe Les quatre fonctions nonlinaires disponibles sont : Notation: clss est une rotation de s bits vers la gauche, s varie pour chaque opration. [+] symbolise l'addition modulo 232. symbolisent respectivement les oprations boolennes XOR, AND, OR et NOT.71MD5: Principe7236MD5: Pseudocode//Note: All variables are unsigned 32 bits and wrap modulo 2^32 when calculating var int[64] r, k //r specifies the per-round shift amounts r[ 0..15] := {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, r[16..31] := {5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, r[32..47] := {4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, r[48..63] := {6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21,7, 9, 4, 6,12, 14, 11, 10,17, 22} 20} 16, 23} 15, 21}//Use binary integer part of the sines of integers (Radians) as constants: for i from 0 to 63 k[i] := floor(abs(sin(i + 1)) (2 pow 32)) //Initialize variables: var int h0 := 0x67452301 var i int h1 := 0xEFCDAB89 var int h2 := 0x98BADCFE var int h3 := 0x10325476 //Pre-processing: append "1" bit to message append "0" bits until message length in bits 448 (mod 512) append bit /* not byte */ length of unpadded message as 64-bit little-endian integer to message73MD5: Pseudocode//Process the message in successive 512-bit chunks: for each 512-bit chunk of message break chunk into sixteen 32-bit little-endian words w[i], 0 i 15 //Initialize var int a := var int b := var int c := var int d := hash value for this chunk: h0 h1 h2 h3//Main loop: for i from 0 to 63 if 0 i 15 then f := (b and c) or ((not b) and d) g := i else if 16 i 31 l f := (d and b) or ((not d) and c) g := (5i + 1) mod 16 else if 32 i 47 f := b xor c xor d g := (3i + 5) mod 16 else if 48 i 63 f := c xor (b or (not d)) g := (7i) mod 167437MD5: Pseudocode//Main loop: for i from 0 to 63 temp := d d := c c := b b := b + leftrotate((a + f + k[i] + w[g]) , r[i]) a := temp //Add h0 := h1 := h2 := h3 := this h0 + h1 + h2 + h3 + chunk's hash to result so far: a b c dvar i int digest := h0 append h1 append h2 append h3 //( i d d d //(expressed as li l d little-endian) di )75Plan Gnral du cours Introduction Algorithmes standards de cryptographie Chiffrement symtrique Chiffrement de flux (Stream cipher) ( p ) Chiffrement par blocs (Block cipher) Chiffrement asymtrique Fonctions de hashage Intgrit et Authentification HMAC Signatures Gestion des cls Distribution des cls secrtes Gnration et distribution des certificats Protocoles de scurit et standards divers7638MACs Message Authentication Code: Code accompagnant des donnes dans le but d'assurer l'intgrit de ces dernires Concept relativement semblable aux fonctions de hachage: Algorithmes qui crent un petit bloc authentificateur de taille fixe fixe. Diffrence: Ce bloc authentificateur ne se base plus uniquement sur le message, mais galement sur une cl secrte. Tout comme les fonctions de hachage, les MAC nont pas besoin dtre rversibles; le rcepteur excutera le mme calcul sur le message et le comparera avec le MAC reu. Le MAC assure: une fonction de vrification de l'intgrit du message Authentification de lexpditeur, dtenteur de la cl secrte Peut (rarement) tre employ comme un chiffrement supplmentaire Calcul avant ou aprs le chiffrement principal (conseill de le faire avant) Examples CBC-MAC HMAC77CBC-MAC Cipher Block Chaining MAC Ek(Mi) : Chiffrement sur un bloc de donnes avec la cl on dcoupe les donnes en blocs de taille fixe m1 mx p on dfinit un vecteur d'initialisation C1=0 on traite les blocs au fur et mesure : Ci+1= Ek(CiMi)7839HMAC Keyed-Hash MAC: MAC calcul en utilisant une fonction de hachage cryptographique en combinaison avec une cl secrte. N'importe quelle fonction itrative de hachage, comme MD5 ou SHA-1, peut tre utilise (HMAC-MD5 ou HMAC-SHA-1) (HMAC MD5 HMAC SHA 1) Qualit cryptographique du HMAC dpend (Qualit cryptographique de la fonction de hachage, taille cl, qualit cl) La fonction HMAC est dfinie comme suit : Avec : h : une fonction de hachage itrative, K : la cl secrte de la taille du bloc de la fonction h m : le message authentifier,"||" dsigne une concatnation et "" un ou exclusif, ipad et opad, chacune de la taille d'un bloc, sont dfinies par : ipad = 0x363636...3636 et opad = 0x5c5c5c...5c5c. Donc, si la taille de bloc de la fonction de hachage est 512, ipad et opad sont 64 rptitions des octets, respectivement, 0x36 et 0x5c.79Signatures digitales Chiffrement cl publique Signature cl publique8040Signatures digitales Chiffrement cl publique (dtails)81Signatures digitales Signature cl publique (dtails)8241Plan Gnral du cours Introduction Algorithmes standards de cryptographie Chiffrement symtrique Chiffrement de flux (Stream cipher) ( p ) Chiffrement par blocs (Block cipher) Chiffrement asymtrique Fonctions de hashage Intgrit et Authentification HMAC Signatures Gestion des cls Distribution des cls secrtes Gnration et distribution des certificats Protocoles de scurit et standards divers83Diffie-Hellman: Principe8442Diffie-Hellman: Exemple Alice et Bob choisissent un nombre premier p=23 et une base g=3 Alice choisit un nombre secret a=6 Elle envoie Bob la valeur ga [mod p] = 36 [23] = 16 Bob choisit son tour un nombre secret b=15 Bob envoie Alice la valeur gb [mod p] = 315 [23] = 12 Alice calcule la cl secrte : (gb [mod p])a [mod p] = 126 [23] = 9 Bob obtient la mme cl qu'Alice : (ga [mod p])b [mod p] = 1615 [23] = 985Certificats Un certificat lectronique est une carte d'identit numrique dont l'objet est d'identifier une entit physique ou non-physique. Le certificat numrique ou lectronique est un lien entre l'entit physique et l'entit numrique (Virtuel). L'autorit de certification fait foi de tiers de confiance et atteste du lien entre l'identit physique et l'entit numrique. Le standard le plus utilis pour la cration des certificats numriques est le X.509.8643Certificats Un certificat lectronique contient : un numro de srie; l'identification de l'algorithme de signature; la dsignation de l'autorit de certification mettrice; la priode de validit au-del de laquelle il sera suspendu ou rvoqu; le nom du titulaire de la cl publique; l'identification de l'algorithme de chiffrement et la valeur de la cl publique constitus d'une paire de cls asymtriques des informations complmentaires optionnelles; l'identification de l'algorithme de signature et la valeur de la g g signature numrique. Un certificat lectronique est gr tout au long de son cycle de vie (Certificate revocation list (CRL), Protocole de vrification en ligne de certificat) avec une infrastructure cls publiques (PKI pour Public Key Infrastructure).87Plan Gnral du cours Introduction Algorithmes standards de cryptographie Chiffrement symtrique Chiffrement de flux (Stream cipher) ( p ) Chiffrement par blocs (Block cipher) Chiffrement asymtrique Fonctions de hashage Intgrit et Authentification HMAC Signatures Gestion des cls Distribution des cls secrtes Gnration et distribution des certificats Protocoles de scurit et standards divers8844Intruder-in-the-middle contre D-HLe protocole Diffie-Hellman ressemble ca:Ua aUVVKU ,V aU aV mod pUn attaquant peut effectuer les substitutions suivantes:Ua a'UVW a' aUVVKU ,W aU a 'V mod pRaison : Pas d'authentificationKV ,W a 'U aV mod pStation-to-Station (STS) Protocol : (1) Alice Bob : gx (2) Alice Bob : gy, CertB, EK(SB(gy, gx)) (3) Alice Bob : CertA, EK(SA(gx, gy))89Authentification de labonn GSM9045Encryptage des donnesEncryptage des donnes46Rfrences Handbook of Applied Cryptography, Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, CRC Press, October 1996. http://www.cacr.math.uwaterloo.ca/hac/index.html http://www.wikipedia.org/ Cours de Systmes de conduite des ordinateurs http://www.montefiore.ulg.ac.be/~herbiet/sco.html Tutorial sur la cryptographie http://www.uqtr.ca/~delisle/Crypto/ Exemple RSA http://www.apprendre-en-ligne.net/crypto/rsa/ htt // d li t/ t / s /9347

Recommended

View more >