Algorithmique Cours 5 : Cryptographie et cryptosystème RSA ROB3
Algorithmes de chiffrement. Deux classes d'algorithmes de chiffrement : ?. Cryptographie symétrique (ou à clé privé). Les clés de cryptage et de décryptage
Cryptosystème RSA
Cryptosystème RSA. Anca Nitulescu anca.nitulescu@ens.fr Algorithme d'Euclide étendu ... L'algorithme d'Euclid étendu calcule des coeficients (uv).
La cryptographie asymétrique avec RSA
Aug 12 2019 Ce que l'on appelle RSA est un algorithme de chiffrement et déchiffrement. ... l'Union Européenne
Sur lalgorithme RSA
Enfin on va calculer la valeur de ? en un produit de deux nombres premiers distincts. Ceci nous servira en effet dans l'algorithme RSA. Lemme 1.1 Soient p et q
La sécurité informatique
Cryptologie - Clé publique - A08. 12. Premier algorithme à clé publique – RSA. ? Cet algorithme a été proposé en 1977 par Rivest Shamir et.
La cryptographie RSA
Le cryptage RSA du nom de ses concepteurs
Grands nombres premiers Cryptographie RSA
L'algorithme procède par élimination : il s'agit de supprimer de la table complète de tous les entiers allant de 2 jusqu'à n tous les entiers qui sont
CRYPTANALYSE DE RSA
Jan 2 2015 Algorithme 2 : Fabrication des clés. Entrée : Deux nombres premiers p et q. Sortie : Une clé privée d et une clé publique e. 1: Calculer ?(N)=(p ...
Analyse cryptographique des altérations dalgorithmes
Aug 12 2011 Algorithme de signature numérique standardisé par le NIST aux États-. Unis
TP : RSA 1 Algorithmes de RSA avec bc
Comprendre les algorithmes mis en jeu dans le système RSA. 2. Utiliser OpenSSL pour chiffrer/déchiffrer des clés avec RSA. Outils : bc calulateur de précision
[PDF] Cryptosystème RSA - DI ENS
Il existe u et v tels que xu + nv = pgcd(xn) = 1 Trouver l'inverse d'un élément revient à calculer u L'algorithme d'Euclid étendu calcule des coeficients
[PDF] Algorithmique Cours 5 : Cryptographie et cryptosystème RSA ROB3
Algorithmes de chiffrement Deux classes d'algorithmes de chiffrement : ? Cryptographie symétrique (ou à clé privé) Les clés de cryptage et de décryptage
[PDF] Sur lalgorithme RSA
Le RSA a été inventé par Rivest Shamir et Adleman en 1978 C'est l'exemple le plus courant de cryptographie asymétrique toujours considéré comme sûr
[PDF] La cryptographie RSA
Le cryptage RSA du nom de ses concepteurs Ron Rivest Adi Shamir et Leonard Adleman est le premier algorithme de chiffrement asymétrique Il a été découvert
[PDF] Grands nombres premiers Cryptographie RSA
Grands nombres premiers Cryptographie RSA François DE MARÇAY Département de Mathématiques d'Orsay Université Paris-Sud France 1 Limitations physiques
[PDF] La cryptographie asymétrique avec RSA - Zeste de Savoir
12 août 2019 · 1 Un peu d'histoire et beaucoup de mathématiques Ce que l'on appelle RSA est un algorithme de chiffrement et déchiffrement
[PDF] [RSA : Rivest Shamir Adleman] - Zenk - Security
Présentation du RSA Comment génère t'on les clés publique privé ? Algorithme de Bézout Pseudo-code RSA Présentation pratique en JAVA Etude de la sécurité
[PDF] CRYPTANALYSE DE RSA - Abderrahmane Nitaj
Algorithme 1 : Fabrication du module Entrée : Une taille t pour le module du cryptosyt`eme RSA Sortie : Un module RSA N de taille t
[PDF] Cryptographie RSA - Laure Gonnord
Rivest Shamir Adleman ou RSA est un algorithme asymétrique de cryptographie à clé publique très utilisé dans le commerce électronique et plus généralement
[PDF] La cryptographie RSA vingt ans après - Apprendre-en-lignenet
L'algorithme RSA est moins rapide que les algorithmes classiques à une seule clef ce qui est un handicap lorsque l'on doit coder des messages volumineux Aussi
Comment fonctionne l'algorithme RSA ?
Le cryptage RSA fonctionne en utilisant une paire de clés - clés publiques et privées - pour crypter et décrypter les données. La clé publique est utilisée pour chiffrer les données, tandis que la clé privée est utilisée pour déchiffrer les données.Comment coder en RSA ?
Protocole RSA pour le codage
e × d + m × (p – 1)(q – 1) = 1 Pour ce faire, elle peut utiliser un algorithme de calcul très connu depuis l'Antiquité (vers 300 ans avant Jésus-Christ) appelé algorithme d'Euclide. Elle calcule également n = p × q.Quels sont les deux outils mathématiques indispensables du chiffrement RSA ?
RSA a besoin d'une clé publique (constituée de 2 nombres (n,e) ) et d'une clé privée (1 seul nombre d ). Avec ces nombres, le couple (n,e) est appelée la clé publique et le nombre d est la clé privée.Algorithmes de cryptographie symétrique (à clé secrète)
Chiffre de Vernam (le seul offrant une sécurité théorique absolue, à condition que la clé ait au moins la même longueur que le message à chiffrer, qu'elle ne soit utilisée qu'une seule fois et qu'elle soit totalement aléatoire)DES.3DES.AES.RC4.RC5.MISTY1.
![[PDF] Cryptosystème RSA - DI ENS](https://pdfprof.com/Listes/17/30153-17crypto3.pdf.pdf.jpg "[PDF] Cryptosystème RSA - DI ENS")
Rappels
Chiffrement à clé publiqueCryptosystème RSAAnca Nitulescu
anca.nitulescu@ens.frEcole Normale Supérieure, Paris
Cours 3
1/25 Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographieRappels
Chiffrement à clé publiqueArithmétique modulaireExponentiation modulaire
Factorisation des entiersRappels mathématiques
Outils mathématiques
Algorithme d"Euclide étendu
Nombres premiers grands
Exponentiation modulaire
Inversion modulaire
Calcul des restes chinois
2/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueArithmétique modulaireExponentiation modulaire
Factorisation des entiersArithmétique modulaire(Zn;+)forme ungroupe additif commutatif d"ordren.(Zn;+;)forme unanneau commutatif.Inverse modulairedeadansZn: entierb=a1tel que
ab=1 modnZ?n=l"ensemble des éléments inversibles modulon.(Z?n;)forme ungroupe multiplicatif.(Zp;+;)forme uncorps commutatif.Attention!
Z ?n6=Znn f0gpourncomposé Z ?p=Zpn f0gpourpprime3/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographieRappels
Chiffrement à clé publiqueArithmétique modulaireExponentiation modulaire
Factorisation des entiersCritère d"inversibilité Les entiers inversibles modulonx2Z?nest inversibles modulonsi et seulement si pgcd(x;n) =1. Preuve: T. Bézout.Calcul de l"inverse modulaireTrouverx1modnIl existeuetvtels quexu+nv=pgcd(x;n) =1Trouver l"inverse d"un élément revient à calculeru.L"algorithme d"Euclid étendu calcule des coeficients(u;v)4/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueArithmétique modulaireExponentiation modulaire
Factorisation des entiersFonction d"Euler
Définition
'(n)est le nombre d"entiers de[1;n]qui sont premiers avecn.'(n)désigne l"ordre du groupe multiplicatifZ?nPropriétés
sipest premier etqpremier :'(p) =p1'(pq) ='(p)'(q)5/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueArithmétique modulaireExponentiation modulaire
Factorisation des entiersExponentiation modulaire
Théorème de Lagrange
SiGest un groupe multiplicatif d"ordren, alors :
8g2Ggn=eThéorème d"Euler
Pour tout entiernet touta2Z?n, on a
a '(n)=1 modnPetit théorème de FermatPourppremier et tout entieraon a
a p=amodp6/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographieRappels
Chiffrement à clé publiqueArithmétique modulaireExponentiation modulaire
Factorisation des entiersExponentiation modulaire
Ordre du groupeZ?nordrejZ?nj='(n))a'(n)=1(mod n)ordrejZ?pj='(p) =p1)ap1=1(mod n)Règles Dans une exponentiation modulaire (modulo un entierM), lesexposants doivent être pris modulo'(M).Effectuer les réduction modulaires au fur et à mesure.
7/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueArithmétique modulaireExponentiation modulaire
Factorisation des entiersFonctions à sens unique8/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueArithmétique modulaireExponentiation modulaire
Factorisation des entiersFonctions à sens uniquePrincipe
Pour une relationy=f(x), calculeryest facile, et retrouverxà partir deyest difficile sans une "trappe".QuestionComment construire telles fonctions?
9/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueArithmétique modulaireExponentiation modulaire
Factorisation des entiersFactorisation des entiersFactorisation
(p;q)!pqfacilen=pq!(p;q)difficile10/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueArithmétique modulaireExponentiation modulaire
Factorisation des entiersMéthodes connues = exponentiellesAlgorithmes de factorisation
Divisions successives! O(pn)Algorithme de Fermat: trouvern=a2b2! O(n1=3) cas facil:pqpetitMéthode de Gauss: trouver des résidus quadratiques modn cas facil:'(n)connuAlgorithmep1de Pollard! O(plog(p)) cas facil:p1 etq1 ont des petits facteurs premiersAlgorithme Williams cas facil:p+1 etq+1 ont des petits facteurs premiersAlgorithmes sous-exponentiels crible quadratique, courbes elliptiques, crible algébrique11/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéChiffrement à clé publique
12/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéChiffrement à clé publique
Protocole
Algorithme de génération des clésKG(`) = (pk;sk) à partir d"un paramètre de sécurité, il produit une paire de clésAlgorithme de chiffrementE(pk;m) =c
produit le chiffré d"un messagem, par la clé publiqueAlgorithme de déchiffrementD(sk;c) =m
utilise la clé sécrete/privée sk pour retrouvermà partir dec13/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéProtocole RSA
RSA - Génération des clés
KG(`) = (pk;sk)Soit n=pq (p et q premiers)L"ordre du groupe multiplicatifZ?n='(n) = (p1)(q1)Soit e un entier premier avec'(n) = (p1)(q1)Soit d un entier qui satisfait de=1(mod'(n))
de+u'(n) =1 (Bézout)clé publique n=pq : module publice : exposant publicclé secrète d=e1(mod'(n))les premiers p et q14/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéProtocole RSA
RSA - Chiffrement
E(pk= (e;n);M) =Me(mod n)RSA - Déchiffrement
D(sk=d;C) =Cd(mod n)Vérification
(Me)d=Med=M1u'(n)=M1=M(mod n) (Théorème d"Euler)15/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéRSA - Exemple simplifié
Deux petits premiers :p=5 etq=7
n=57=35,'(n) = (51)(71) =24 eetd:ed=1 mod 24 ed=1 : Non, trop petit ed=25 : Ok, maise=d=5 et alors clé privé = clé publique ed=49 : Pareil,e=d ed=73 : 73 est premier, raté ed=97 : 97 est premier, raté ed=121 : 11 au caré, encore raté ed=165 : 165 = 5 * 33, et 5 est premier : OkClé publique =(RSA;35;5)Clé privée =(RSA;33):16/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéConseils d"utilisation du RSA
RSA - Précautions
Il y a de nombreuses manières demal utiliserRSA et d"ouvrir desfailles de sécurité!Ne jamais utiliser de valeurntrop petiteNe jamais utiliser d"exposantetrop petitN"utiliser que des clés fortes
(p1 etq1 ont un grand facteur premier)Ne pas chiffrer de blocs trop courtsNe pas utiliser dencommuns à plusieurs clés17/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéAttaques RSA
RSA - Attaques mathématiques
factorisern=pqet par conséquent trouver'(n) et puisddéterminer'(n)directement et trouverdtrouverddirectement (si petit)attaques "broadcast" attaques sur moduloncommunattaques de synchronisation (sur le fonctionnement du déchiffrement)18/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéEfficacité de RSA
RSA - coût
Le coût est celui d"une exponentiation modulaire : Chiffrement :E(pk= (e;n);M) =Me(mod n)3jej=2 multiplicationssijnj=jejcoût total 1:5log3nDéchiffrement :D(sk=d;C) =Cd(mod n)3jpj=2 multiplications modp+3jqj=2 multiplications modq3jpjmultiplications modp3jnj=8 multiplications modp19/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéPropriétés du chiffrement
RSA = Homomorphisme
Le chiffré d"un produitM1M2est égal au produit des chiffrés C1=Me1(mod n)
C2=Me2(mod n)C
1C2=Me1Me2= (M1M2)e
Intéressant pour certains scénarios
Mais aussi nuisible à la sécurité ...Attaque à chiffré choisi1SoitC=Meun message chiffré2On fabriqueC0=AeMele chiffré du messageAM3Le déchiffrement deC0fournit celui deC20/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéPropriétés du chiffrement
RSA = Déterministe
Chiffrement déterministe= si l"on chiffre plusieurs fois le même message, on obtient le même chiffré Méthodes pour éviter le chiffrement par substitution :couper le message en grands blocs modifier la taille de blocs à chaque fois randomiser le chiffrement RSA21/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéSécurité de RSA
RSA - Sécurité
RSA est considéré sécure :
impossible à déchiffrer sans connaitre l"exposantdde la clésecrètetrouver la clé secrètedest equivalent à factorisern=pqpas d"algorithme polynomial en temps en fonction de la taille
des données (la taille des nombresnete) pour factorisernmeilleur algorithme connu est sous-exponentiel (crible
algébrique) :O e1:92(lnn)1=3(lnlnn)2=322/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographieRappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéSécurité de RSA
RSA - Sécurité
Pour évaluer et tester la sécurité du RSA : évaluer la rapidité des algorithmes de factorisations de grands nombres entiersdémontrer que la clef secrète de déchiffrementdne peut pasêtre obtenue sans factorisern=pqmontrer que on ne peut pas déchiffrer un message sans la clé
secrèted23/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographieRappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéProblèmes difficiles
Factorisation
(p;q)!pqfacilen=pq!(p;q)difficileMeilleur algorithme (crible algébrique) :O
e1:92(lnn)1=3(lnlnn)2=3Fonction RSA
Extraction de racinee-ièmex!xemodnfaciley=xe!x mod ndifficile avec la trapped =e1(mod'(n)):x=yd=xed=xmodn24/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéProblèmes difficiles
Factorisation
(p;q)!pqfacilen=pq!(p;q)difficileMeilleur algorithme (crible algébrique) :O
e1:92(lnn)1=3(lnlnn)2=3Fonction RSA
Extraction de racinee-ièmex!xemodnfaciley=xe!x mod ndifficile avec la trapped =e1(mod'(n)):x=yd=xed=xmodn24/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
Rappels
Chiffrement à clé publiqueProtocole RSA
Attaques sur RSA
SécuritéDifficulté de RSA
Réduction
Si on connaît la factorisation, on casse RSA :
RSA se réduit à la factorisation!
Le contraire est peut-être faux!calculer des racinese-ièmes sans factoriser???En pratiqueLa factorisation est la seule méthodeconnuepour casser RSA.25/25Anca Nitulescu anca.nitulescu@ens.frIntroduction à la cryptographie
quotesdbs_dbs29.pdfusesText_35[PDF] cryptage rsa exemple
[PDF] cryptographie asymétrique algorithme
[PDF] chiffrement asymétrique et symétrique
[PDF] chiffrement asymétrique exemple
[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
