Number-Theoretic Algorithms (RSA and related algorithms)
Each RSA number is a semiprime (A nu mber is semiprime if it is the product of tw o primes ) There are two labeling schemes by the number of decimal digits: RSA-100, RSA Numbers x x , RSA-500, RSA-617 by the number of bits: RSA-576, 640, 704, 768, 896, , 151024 36, 2048
1) A very simple example of RSA encryption
1) A very simple example of RSA encryption This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 45 can probably even do it by hand) 1 Select primes p=11, q=3 2 n = pq = 11 3 = 33 phi = (p-1)(q-1) = 10 2 = 20 3 Choose e=3
The RSA Encryption Scheme General Example
The RSA Encryption Scheme Suppose Alice wants her friends to encrypt email messages before sending them to her Computers represent text as long numbers (01 for \A", 02 for \B" and so on), so an email message is just a very big number The RSA Encryption Scheme is often used to encrypt and then decrypt electronic communications General Alice
RSA { the Key Generation { Example
RSA { Encryption/Decryption { Example The encryption algorithm E: Everybody can encrypt messages m(0 m
Sur l’algorithme RSA
Sur l’algorithme RSA Le RSA a´et´e invent´e par Rivest, Shamir et Adleman en 1978 C’est l’exemple le plus courant de cryptographie asym´etrique, toujours consid´er´e comme surˆ , avec la technologie actuelle, pour des cl´es suffisament grosses (1024, 2048 voire 4096 bits)
Lecture 12: Public-Key Cryptography and the RSA Algorithm
12 2 The Rivest-Shamir-Adleman (RSA) Algorithm for 8 Public-Key Cryptography — The Basic Idea 12 2 1 The RSA Algorithm — Putting to Use the Basic Idea 12 12 2 2 How to Choose the Modulus for the RSA Algorithm 14 12 2 3 Proof of the RSA Algorithm 17 12 3 Computational Steps for Key Generation in RSA 21
Public Key CryptoSystems RSA Algorithm
THE RSA CRYPTOSYSTEM 2 1 RSA Algorithm 13 2 1 1 Key Generation 13 2 1 2 RSA Encryption 14 2 1 3 RSA Decryption 14 2 1 4 Example of RSA 14 2 2 The Security of RSA 15 2 2 1 Brute force 15 2 2 2 Mathematical attacks 16
Introduction à la cryptographie TD6 – RSA : exemples simples
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
[PDF] algorithme rsa pdf
[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
[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
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 T