TD 2 : Le cryptosyst`eme RSA 1 Example de protocole RSA
Il sait maintenant qu'il doit utiliser le syst`eme RSA avec les deux entiers n et e. Il transforme en nombres son message en remplaçant par exemple chaque
GUIDE DE SÉLECTION DALGORITHMES CRYPTOGRAPHIQUES
8 mars 2021 5.1 Primitive RSA et factorisation de grands entiers . ... Par exemple dans un mécanisme symétrique de chiffrement
Algorithmique. Rappels mathématiques. Cryptosystème RSA
25 janv. 2016 Rappels mathématiques. Protocole RSA. • Définition. • Complexité des algorithmes. • Hiérarchie entre fonctions. Exemple de complexité.
Introduction à la cryptographie TD6 – RSA : exemples simples et
14 nov. 2019 l'exemple de l'algorithme de signature asymétrique RSA telle qu'il est par exemple utilisé dans les cartes bancaires.
RSA : clés chiffrement
signatures
Analyse cryptographique des altérations dalgorithmes
12 août 2011 Algorithme de chiffrement `a flot conçu en 1987 par R. Rivest. Il est supporté par différentes normes par exemple dans SSL. RSA.
Chapitre 7 - Le chiffrement par clé publique
de l'algorithme RSA bien que là aussi
Chiffrer avec RSA
en temps réel (penser à une conversation téléphonique par exemple). La génération d'une paire de clés RSA comporte un algorithme probabiliste ...
Authentification et Integrité : Signature numérique et Hachage
Algorithme de génération des clés. KG(l)=(pksk) Signature d'un document de 15 Mo avec RSA 1024 bits ? ... Modèle de sécurité = un but + des moyens.
La cryptographie RSA
Un chiffrement asymétrique est un cryptage où l'algorithme de chiffrement n'est pas Voici un exemple de l'utilisation de RSA avec des petits nombres :.
[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] TD 2 : Le cryptosyst`eme RSA 1 Example de protocole RSA - DI ENS
1 1 Génération des clés Alice choisit : • deux entiers premiers p et q et fait leur produit n = p · q • un entier e premier avec ?(n)=(p ? 1)(q ? 1)
[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] [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] La cryptographie asymétrique avec RSA - Zeste de Savoir
12 août 2019 · Ce que l'on appelle RSA est un algorithme de chiffrement et déchiffrement l'Union Européenne par exemple édite régulièrement un PDF
[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
[PDF] Grands nombres premiers Cryptographie RSA
Supposons par exemple que l'on rêve d'imprimer la liste complète de tous les nombres entiers premiers qui sont inférieurs à un certain entier nombre assez
[PDF] CRYPTANALYSE DE RSA - Abderrahmane Nitaj
Dans le chapitre 3 nous présentons quelques aspects de la réduction des réseaux plus précisément l'algorithme LLL et son utilisation pour attaquer le
[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
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.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.Quels sont les algorithmes de cryptographie ?
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.- Le chiffrement est un procédé de cryptographie qui consiste à protéger des données qui sont alors incompréhensibles pour celui qui ne dispose pas de la clef du chiffrement.
Introduction à la cryptographie
TD6 - RSA : exemples simples et signatures
Cécile Pierrot
14 novembre 2019
L"objectif de ce TD est d"abord de voir quelques exemples simplifiés et concrets d"utilisation de RSA. Ensuite, nous allons voir à quel point la cryptographie est un parcours semé d"em- bûches, y compris lors de l"implémentation d"une simple primitive. Nous utiliserons pour cela l"exemple de l"algorithme de signature asymétrique RSA, telle qu"il est par exemple utilisé dans les cartes bancaires.1 Prérequis et premiers exemples
1.1 Quelques rappels : définitions et propriétés du modulo
Soitnun entier naturel. L"ensembleZ/nZest défini comme l"ensemble des entiers modulo n, c"est-à-diref0,1,2,,n2,n1g. Un entier naturel est dit premier s"il existe exactement deux entiers naturels qui le divisent : 1 et lui-même. Par exemple 3,7,43 sont des nombres premiers mais 0,1,8 et 15 ne le sont pas. Attention à ne pas confondre avec la définition de deux nombres premiersentre-eux:metnsont premiers entre-eux si et seulement si leur seul diviseur commun est 1. Cela signifie que tout nombre premier est premier avec n"importe quel autre entier, mais deux nombres peuvent être premiers entre-eux, sans être premiers. Par exemple 4et21 sont premiers entre-eux. Soientaetbdeux entiers relatifs. Alors on écritab(modn)et on dit queaest congru àb modulonsi et seulement sindivisejabj. Cela est équivalent à dire qu"il existequn entier naturel tel quea=nq+b. En particulier, sirest le reste de la division euclidienne deapar nalorsar(modn). Il existe de nombreuses manières de noterab(modn)et elles sont toutes équivalentes. On peut par exemple aussi écrire : -a=bmodn -abmodn -ab[n] -a=b[n]. Question 1.Vérifiez que 1872 mod 5, que 800 mod 8 et que76 mod 13. Quelquespropriétésàavoirentête,quenous nemontreronspas.Soient,a,b,desentiersrelatifs etketndes entiers naturels. Alors :1.nk0 modn
2. Siaest premier avecnalors il existe un entier que l"on notea1et que l"on appelle
l"inverse modulaire deatel queaa11 modn.3. Siabmodnalorsakbkmodn. Attention la réciproque est fausse.
4. Siakbkmodnet quekdivisenalorsabmodn/k
Question 2.Qui est l"inverse modulaire de 3 modulo 7? 3 a-t-il une inverse modulaire modulo 18?Question 3.Montrez l"item 3 et l"item 4.
1.2 Pourquoi RSA fonctionne-t-il?
Lors du déchiffrement, on calcule le chiffrécmemodNà la puissance l"entier publicd, le tout moduloN. Nous rappelons que : ed1 mod(p1)(q1). Pour garantir que l"on retrouve bien le message, nous avons besoin du théorème suivant, que l"on ne prouvera pas : Théorème 1(Petit théorème de Fermat).Soientpun entier premier etaun entier naturel pre- mier avecp. Alors : a p11 modp. Question 4.Montrez qu"en calculantcdmodNon obtient bien le message initialmmodN. Indice : appliquez deux fois le théorème de Fermat sur un entierabien choisi, une fois modulop, et une fois moduloq.1.3 Comment calculer l"exposant secretd?
Supposons quee,petqsoient connus. Pour le moment nous faisons l"hypothèse qu"il existe et il faut en particulier vérifier certains conditions. Supposons donc quedexiste. Pour calculer cet exposantdtel queed1 mod(p1)(q1) il s"agit de savoir retrouver l"inverse modulaire d"un entier modulo(p1)(q1). On pourrait procéder par recherche exhaustive, en testant tous les entiers modulos(p1)(q1)mais celaserait beaucoup trop long. La bonne idée consiste à appliquer l"algorithme d"Euclide étendu.
L"algorithme d"Euclide étendu est une version de l"algorithme d"Euclide (qui pour rappel, per- met de calculer le pgcd de deux entiers) dans laquelle, à partir de deux entiersaetbpris en entrée, nous calculons non seulement le pgcd deaetb, mais aussi la valeur de deux autres entiers relatifsuetvtels que : au+bv=pgcd(a,b). Question 5.Que vaut le pgcd de deux entiersaetbsiaetbsont premiers entre eux? Dans ce cas, si l"on suppose queeest premier avec(p1)(q1), quelles sont les valeurs qu"il faut prendre en entrée de cet algorithme pour obtenir l"inverse modulaire dee? Question 6.L"algorithme est donné en pseudo-code dans la figure ci-dessous. Appliquez à la main poura=3 etb=7. Qui est alors l"inverse modulaire de 3 modulo 7?1.4 Un exemple simple
Maintenant que vous êtes armés, nous allons (enfin!) calculer le chiffrement d"un message (super simple). Prenonsp=7 etq=13. Choississonse=5. Question 7.Qui est la clef secrète? La clef publique? def bezout(a, b): r, u, v, rr, uu, vv = (a, 1, 0, b, 0, 1) while rr: q = r // rr r, u, v, rr, uu, vv = (rr, uu, vv, r - (q*rr), u - (q*uu), v - (q*vv)) return r, u, v Supposons maintenant que le message clair soitm=18. Question 8.Quel est le message chiffré correspondant? Question 9.Et si l"on dispose d"un message chiffréc6 mod 91. Quel est le message clair?Même question avecc1 mod 91.
2 La signature RSA
2.1 Quelques rappels
et privée pour RSA s"effectue de la manière suivante :1. choisir au hasard deux nombres premiers distinctspetqden/2 bits chacun;
2. calculer lemodule N=pq, ainsi que l"indicatrice d"Eulerj(N) = (p1)(q1);
3. choisir unexposant public e2Z/j(N)Z, non nul et co-premier avecj(N);
4. calculer l"exposant privé d2Z/j(N)Ztel queed1(modj(N))(un teldexiste
toujours et il est unique; on le calcule avec un algorithme d"inversion modulairecomme l"algorithme d"Euclide étendu);5. laclé publiqueest alors le couplePK= (e,N), et laclé privée SK= (d,N).
Telles que les clés publique et privée ont été calculées, on a M edmodN=Mpour tout messageM2Z/NZ. Question 1.Quelle est la taille (en bits) du moduleN? Et celle dej(N)? Actuellement, quelles valeurs sont recommandées pourn? Question 2.Expliquez en quoi ce n"est pas une bonne idée de prendree=1. Pour signer un messageM2Z/NZavec la clé privée(d,N), on calcule la signatureS= SigSK(M) =MdmodN.
Question 3.Grâce à la clé publique, comment peut-on vérifier qu"une signatureScorrespond bien à un messageMdonné?2.2 Un petit exemple
Prenons par exemplep=5,q=11, ete=3.
Question 4.Combien valentN,j(N), etd?
Considérons alors le messageM=13 et les signaturesS1=9 etS2=7. Question 5.Laquelle de ces deux signatures correspond àM? Question 6.Calculez (à la main) une signature valide pour le messageM=7. Fastidieux, n"est-il pas? Essayez de ruser pour ne pas avoir à calculer 26 produits moduloN.3 Calcul d"exponentiation modulaire
3.1 Algorithme naïf
Comme vous avez pu vous en rendre compte à la question précédente, le calcul deMdmodN(on appelle ça uneexponentiation modulaire) coûte cher, surtout s"il est effectué naïvement. Mais
cher comment? Question 1.En admettant que, par construction, l"exposant secretdprend une valeur quel- conque dansZ/j(N)Z, quelle est sa taille (en bits)? Question 2.Quelle est la taille (en bits) de l"entierMd? Pour les valeurs recommandées den, est-ce que cela est envisageable? Comment remédier à ce problème? Question 3.Combien de multiplications modulaires sont-elles nécessaires pour calculer une signatureS=MdmodN? Encore une fois, pour les valeurs recommandées den, est-ce que cela est envisageable?3.2 Algorithme d"exponentiation binaire
Nous allons tenter ici de voir comment faire mieux qu"un algorithme en temps linéaire end (c"est-à-dire exponentiel enn) pour calculerMdmodN. Question 4.Montrez que, sidest pair (c"est-à-dired=2d0), alors vous pouvez ramener le calcul deMdmodNau calcul deMd0modNsuivi d"un carré moduloN. Question 5.Que faire lorsquedest impair (c"est-à-dired=2d0+1)? Question 6.Sidfaitnbits, quelle taille faitd0dans les deux questions précédentes? Question 7.On peut alors répéter l"opération pour le calcul deMd0modN, et ainsi de suite. Déduisez-en un algorithme en tempsO(n)pour calculerMdmodN. Quel est son coût?Astuce: Considérezd= (dn1...d1d0)2=ån1
i=0di2il"écriture en base 2 de l"exposantd. Question 8.Utilisez cet algorithme afin de calculer 917mod 55. De combien de carrés et de multiplications modulo 55 avez-vous eu besoin?4 Attaques par canaux cachés
Nous nous plaçons ici dans le cadre de l"algorithme de signature RSA tel qu"il peut être utilisé
par une carte bancaire, par exemple lors de l"authentification dynamique du protocole EMV. Dans ce contexte, l"alimentation électrique de la puce de la carte bancaire provient du terminal dans lequel elle est insérée. De la même manière qu"il est possible que desskimmersana-lysent et modifient les données qui circulent entre le terminal et la carte, il est aussi possible
de construire unskimmerqui mesure très précisément (voire modifie) le courant électrique alimentant la puce, à la manière d"un oscilloscope. Nous allons voir comment, dans un tel contexte, une implémentation naïve de l"algorithme d"exponentiation binaire peut révéler l"exposant secretdde la carte.4.1 Analyse simple de consommation
Question 1.Dans l"algorithme d"exponentiation binaire obtenu aux questions précédentes, constatez que les calculs effectués à chaque itération dépendent des bits de l"exposant secretd. Il se trouve que les opérations moduloNsont coûteuses : les nombres manipulés font en effet tousnbits. Lors du calcul d"un carré ou d"un produit modulaire, la puce va ainsi consommer plus que durant le reste de l"exécution de son programme. Question 2.Commentez la trace de consommation ci-dessous, mesurée lors du calcul d"une exponentiation binaire pour un exposant den=6 bits. Retrouvez la valeur de l"exposant secretd.Consommation
TempsQuestion 3.Quelle contre-mesure simple peut-on mettre en oeuvre au niveau de l"algorithme d"exponentiation afin d"éviter cette attaque? Quel est son coût?4.2 Attaque par injection de fautes
En contrôlant la tension d"alimentation de la puce, il est possible de baisser celle-ci très ponc-
tuellement afin de lui faire faire des erreurs de calcul à des moments précis de l"exécution de
son programme. (Une forte perturbation électromagnétique peut aussi faire l"affaire.) Question 4.Expliquez comment l"injection de fautes peut vous permettre de détecter des opé- rations inutiles dans l"exécution d"un algorithme. Déduisez-en un moyen de déjouer la contre-mesure précédente. En 1987, Montgomery proposa l"algorithme suivant, appelééchelle de Montgomery(ouMontgo- mery powering ladder) : T 0 1 T 1 M fori n1downto0do T1di T0T1modN
T di T2d imodN returnT0Question 5.Quel est le coût de cet algorithme?
Question 6.Montrez qu"au début de chaque itération de l"algorithme, on a toujoursT1= T0MmodN.
Question 7.Montrez qu"aprèsjitérations de l"algorithme (jn), on a bienT0=Md(j)modN, avecd(j)= (dn1...dnj)2=bd/2njc, l"entier formé par lesjbits de poids forts ded. Question 8.Que calcule l"échelle de Montgomery? Question 9.Montrez que cet algorithme n"est pas vulnérable aux injections de fautes.quotesdbs_dbs15.pdfusesText_21[PDF] algorithme rsa exercice corrigé
[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