[PDF] Cryptographie asymétrique - Lexemple de RSA

View - Download Cryptographie asymétrique - Lexemple de RSA

Previous PDF

Next PDF

Cryptographie asymétriqueL'exemple de RSATrancetrancefusion@hotmail.frwww.ghostsinthestack.org

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org2/33SommaireIntroduction à la cryptographieCryptographie symétriquePrincipe, exemples, avantage / inconvénientCryptographie asymétriquePrincipe, illustration, utilisation couranteL'exemple de RSAPréliminaires, PrincipeAttaquesAlgorithmes et nombres premiers

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org3/33Cryptographie - IntroductionBut : échanger un secret entre 2 pers.Utilisation d'algorithmes simplesAlgo révélé = perte du secret➔ insuffisantUtilisation d'algo + d'une cléClé = sorte de " variante » pour l'algoAlgo révélé = nécessite toujours la clé...➔ déjà mieux...

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org4/33Cryptographie - IntroductionDeux types de cryptographiesCrypto symétrique (à clé privée)Crypto asymétrique (à clé publique)Chacune a ses avantages / inconvénientsDe nos jours, on utilise les 2

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org5/33Cryptographie symétriqueNécessite :Un algorithme F de chiffrement symétriqueOu 2 algos (F1 pour chiffrer, F2 pour déchiffrer)Une clé K partagée entre Bob et AlicePrincipe :Bob chiffre le message M en C = F1(K,M)Bob envoie le message C à AliceAlice le décrypte et retrouve M = F2(K,C)

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org6/33Cryptographie symétriqueExemples simplesCode César et variantes (ROT13, ...)F1(3," COUCOU ») = " FRXFRX »Algos de substitutionsCarré de Polybe...AvantageTrès rapide en généralInconvénientSi la clé est interceptée, le secret est perdu

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org7/33Cryptographie asymétriquePrincipe : On utilise 2 clésUne clé " publique » qui sert à crypterUne clé " privée » servant à décrypterClé publique : peut transiterS'assurer toutefois de son authenticitéClé privée : reste chez son propriétaireIl doit être impossible de déduire la clé privée de la clé publique

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org8/33Principe en imagesAlice génère deux clés. La clé publique (verte) qu'elle envoie à Bob et la clé privée (rouge) qu'elle conserveprécieusement sans la divulguer à quiconque.Bob chiffre le message avec la clé publique d'Alice et envoie le texte chiffré.Alice déchiffre le message grâce à sa clé privée.

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org9/33Cryptographie asymétriqueAvantageMême en interceptant le message, impossible de le décrypter sans la clé privéeInconvénientAlgos lents en généralAttaques par substitution de clé possibles...Organismes de confiance, PKI, ...

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org10/33Utilisation couranteOn utilise en fait les 2 types de cryptoCrypto symétriqueOn chiffre un message M avec une clé KCrypto asymétriqueOn génère 2 clés privée (Pr) et publique (Pu)La clé K est cryptée avec la clé Pu On envoie M et la clé K cryptée sur le réseauLe dest. décrypte la clé K avec Pr, et s'en sert pour finalement décrypter MGain de temps !

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org11/33L'exemple de RSARivest, Shamir et Adleman en 1977Algo le plus utiliséSSL

PGPCarte BleueReste non cassé à ce jourAttention à la signification de " casser »...

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org12/33RSA - PréliminairesDiviseura est diviseur de b si b est un multiple de aex: 2 = diviseur de tous les nombres pairsdécomposition d'un nombre en ses diviseursNombre premiern'a que 2 diviseurs : 1 et lui-mêmeex: 2, 3, 5, 7, 11, 13, 17, 23, ...PGCD(a,b)le plus grand diviseur commun de 2 a et b

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org13/33RSA - PréliminairesNombres premiers entre euxa et b sont premiers entre eux ssi PGCD(a,b)=1 ex: 4 et 5, 3 et 10, ...Identité de Bézoutsi a et b sont premiers entre eux, il existe x et y tel que a.x + b.y = 1

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org14/33RSA - PréliminairesCongruencesOn dit que " a est congru à b modulo n » , et l'on note si a peut s'écrire :a≡b[n]a = n.q + b avec 0 < b < nr est le reste de la division de a par nq est le quotientex: 15 = 7*2 + 1 donc Si alors a est un multiple de n

15≡1[7]

a≡0[n]

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org15/33RSA - PréliminairesFonction indicatrice d'Euler : PhiA valeur de dans (entiers naturels)Phi(n) = nombre d'entiers premiers à n et inférieurs à nex: Phi(8) = 3 car 3,5,7 premiers avec 8Calcul de Phi(n) : Si n = p.q avec p et q premiers, alors Phi(n) = (p-1).(q-1)Très dur à calculer si n est grand...Calculer Phi(n) est aussi dur que de factoriser nℕℕ

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org16/33RSA - PréliminairesThéorème d'EulerSi a est premier avec n, alors :Petit théorème de FermatSi p est un nombre premier,aPhin≡1[n]

ap≡a[p]

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org17/33RSA - Génération des clésChoisir 2 entiers premiers n et pPoser N = p.qCalculer Phi(N) = (p-1).(q-1)Choisir E tq E

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org18/33RSA - (Dé)cryptagePour crypter un message M :

Pour décrypter un message crypté C :

Comment ça marche ?Posons et . On a alors :C≡ME[N]

M≡CD[N]

C≡ME[N]M≡CD[N]

CD≡MED[N]≡ME.D[N]Or, donc E.D = k.Phi(N) + 1Donc

E.D≡1[PhiN]

≡1[N](Voir http://fr.wikipedia.org/wiki/Rivest_Shamir_Adleman pour la preuve détaillée)( Euler + Fermat )

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org19/33Attaques de RSAFactorisation du module (N = p.q)Si on parvient à retrouver p et q, on peut tout retrouver...... mais la factorisation d'un nombre est un problème complexe (complexité NP)Le temps croît exponentiellement avec la taille de NPlusieurs méthodes existent pour accélérer...Crible algébrique (NFS)... mais restent encore trop lentes

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org20/33Attaques de RSAAttaques temporelles (timing attacks)Attaque uniquement liée à l'implémentation !Tiennent compte du temps mis pour décrypterInefficace si l'implémentation de RSA utilise de l'aveuglement cryptographique (blinding)Faire en sorte que le temps de calcul soit constantInsérer des calculs " inutiles » dans l'algo...

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org21/33Attaques de RSAOrdinateur quantique... ?Nouvelle génération de calculateursRégis par la mécanique quantiqueUtilisent des q-bits à états superposablesAccélération phénoménale de la vitesse de factorisation (temps linéaire)Le record actuel : 15 = 5 * 3 :)... c'est pas encore gagné !

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org22/33RSA, en résuméUn système basé sur une conjectureOn " suppose » qu'il est fiable, et que le casser revient à factoriser le moduleEn pratique, a fait ses preuvesmême si certaines implémentations contiennent des failles...Utiliser des clés de 1024 bits min.Lent, comme tout système asymétriqueSert en pratique à crypter des clés symétriques pour les échanger

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org23/33Algos et nombres premiersButsGénérer des nombres premiersEn général de plus de 500 chiffresTester si un nombre et premierFactoriser un nombre composé(Mal)heureusement...Aucun algo 100% efficaceLes algos exacts sont trops lentsLes algos rapides ne sont pas toujours exacts

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org24/33Générer des nombres premiersIl existe un tas de formulestoutes plus complexes les unes que les autresEx : polynôme de degré 25 à 26 variablesTrouver la bonne combinaison des 26 variables qui donne un nombre positifEn réalité, inutile...... on n'a trouvé que le nombre 2 avec !

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org25/33La bête...

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org26/33Tests de primalitéEn général, on génère un nombre N aléatoire, et on teste s'il est premierComment tester si un nombre est premier ?Méthode naïvetester si N est divisible par tous les entiers inférieurs à pas efficace pour les grands nombresAutres méthodes exactesTest AKS, temps polynomialN

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org27/33Tests de primalitéAlgos probabilistesRépondent " oui » ou " non » avec une certaine probabilité pPlus p est proche de 1, plus on est sûrEx : Fermat, Miller-Rabin, Solovay-Strassen

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org28/33Test de FermatSi

Alors x est " certainement » premierDe façon générale, si avec a premier, x est certainement premiera est appelé " témoin »Augmenter le nombre de témoins augmente la chance de ne pas se tromper1≡2x-1≡3x-1≡5x-1≡7x-1[x]

ax-1≡1[x]

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org29/33Exponentiation modulaireBut : calculer de façon efficacePlusieurs techniquesEx: méthode rapideBasée sur les équations suivantes :ac[b]

a2[b]≡a[b]2[b]m∗n[b]≡m[b]∗n[b][b]A vous de faire l'algo !Indice : regarder la parité de l'exposant... cad pour a^n, regarder si n est pair ou impair et appliquer l'une des 2 formules en fonction.Défense de regarder sur internet ! La solution (certes pas optimisée) tient en 4 lignes...

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org30/33FactorisationDivisions successives, le plus simpleGNFS, un des plus efficace (et complexe)Courbes elliptiques, efficace, probabilisteFactorisation de Fermat, simplePrincipe : tout N impair se décompose ainsi :N=a2-b2=ab.a-b

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org31/33Factorisation de FermatFactorFermat(N): // N doit être impair A := partie_entiere(sqrt(N)) Bsq := A*A - N tant que Bsq n'est pas un carré: A := A + 1 Bsq := A*A - N retourner (A - sqrt(Bsq) , A + sqrt(Bsq))

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org32/33ConclusionCryptographie basée sur les mathsCertaines propriétés restent non prouvéesex : difficulté de casser RSAImportance des nombres premiersSans oublier...Les méthodes présentées ici sont simples, la réalité est bien plus complexe...Les démos des propriétés ont été (volontairement) zappées

Trance - trancefusion@hotmail.fr - www.ghostsinthestack.org33/33RéférencesWikipédia FRComprendre, implémenter et casser RSA,

dedji, Hackademy Manuel n°8quotesdbs_dbs29.pdfusesText_35

[PDF] cryptographie exercices corrigés pdf

[PDF] les nombres en lettres pdf

[PDF] les nombres en lettres de 0 ? 1000

[PDF] ap seconde chiffres significatifs

[PDF] chiffres significatifs excel

[PDF] les chiffres significatifs cours

[PDF] chiffres significatifs sinus

[PDF] precision d une mesure et chiffres significatifs

[PDF] chiffres significatifs exacts

[PDF] chiffres significatifs exos

[PDF] exercices chiffres significatifs 2nde

[PDF] les nombres cardinaux en anglais pdf

[PDF] les nombres en anglais pdf

[PDF] les nombres et les chiffres en anglais pdf

[PDF] l'heure en anglais pdf