Probabilités IF Corrigé du devoir du mai
5
pages
Français
Documents
2010
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
5
pages
Français
Documents
2010
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- redaction
Probabilités – 3 IF Corrigé du devoir du 20 mai 2010 Tous les documents et les calculatrices sont autorisés. Le barême n'est donné qu'à titre indicatif et pourra être légérement modifié. Il est conseillé de soigner particulièrement la rédaction. Exercice 1: CRYPTOGRAPHIE, RSA modifié (5 points) On pose p et q deux nombres premiers et distincts, on pose n = pq, on dfinit: ?(n) = (p? 1)(q ? 1) gcd(p? 1, q ? 1) Supposons que l'on modifie RSA pour que ed ? 1 mod ?(n) au lieu d'avoir dans l'algorithme RSA classique ed ? 1 mod ?(n) o ?(n) est la fonction indicatrice d'Euler. 1. Montrer que le chiffrement et le déchiffrement sont toujours des oprations inverses l'une de l'autre avec le nouveau cryptosystème modifié. 1pt Il faut comme condition que e soit premier avec ?(n) pour pouvoir inverser e dans Z/?(n)Z. Si cette condition est vérifiée, on applique RSA modifié : • Alice fabrique sa clé n = pq avec p et q deux grands nombres premiers, e premier avec ?(n) et d tel que ed ? 1 mod ?(n). Alice publie (n, e).
- mod ?
- ?1 ?
- processus de markov homogène
- probabilité
- algorithme rsa classique
- loi de nt
- particules de cendres
- atmosphère des particules de cendre
- dimension temporelle de la dispersion
Probabilites – 3 IF CorrigÉ du devoir du 20 mai 2010
Tous les documents et les calculatrices sont autorisÉs. Le barme n’est donnÉ qu’À titre indicatif et pourra tre lÉgÉrement modifiÉ. Il est conseillÉ de soigner particuliÈrement la rÉdaction.
Exercice 1:CRYPTOGRAPHIE, RSA modifiÉ(5 points) On posepetqdeux nombres premiers et distincts, on posen=pq, on dfinit: (p−1)(q−1) λ(n) = gcd(p−1, q−1) Supposons que l’on modifie RSA pour queed≡1 modλ(n)au lieu d’avoir dans l’algorithme RSA classiqueed≡1 modφ(n)oφ(n)est la fonction indicatrice d’Euler. 1. Montrerque le chiffrement et le dÉchiffrement sont toujours des oprations inverses l’une de l’autre avec le nouveau cryptosystÈme modifiÉ. 1ptIl faut comme condition queesoit premier avecλ(n)pour pouvoir inverseredans Z/λ(n)Zcette condition est vÉrifiÉe, on applique RSA modifiÉ :. Si •Alice fabrique sa clÉn=pqavecpetqdeux grands nombres premiers,e premier avecλ(n)etdtel queed≡1 modλ(n)publie. Alice(n, e). e •Bob veut envoyer un messagemBob calculeÀ Alice :c=mmodn. Bob transmetcÀ Alice. d ed1 •Alice dÉchiffrecen calculant :c≡m≡mmodn=m. 2. Onposep= 37,q= 79ete= 7, calculer la valeurdChiffrerpour le RSA classique. le messagem= 2726. ˙ 2ptp= 37,q= 79ete= 7cherche. ond.φ(n) = (p−1)(q−1) = 3678 = 2808. Par Bezout, on a :ed≡1 modφ(n), i.e.ed+kφ(n) = 1applique donc du. On Euclide Étendu Étendu, ce qui donne :2808 = 7∗401+1et donc7∗(−401)+2808 = −1−1 1soit7≡ −2808401 modet ainsi7≡2407 mod2808. Ona Bob qui chiffre e7 mmodnmod= 2726n= 287. 3. Calculerla valeurdavec les mmes paramÈtres pour la version de RSA modifiÉ.Chiffrer le messagem= 2726. Queconstatez-vous ? 2ptp= 37,q= 79ete= 7cherche. Ond.λ(n) = (p−1)(q−1)/gcd(p−1, q−1) = ˙ 3678/6 = 468mme, en trois Étapes :. De468−7∗68 = 6puis7−6 = 1 −1e donc−468 + 67∗7 = 1. D’oÙ7≡67 modλ(n)a Bob qui chiffre. Onm 7 modn= 2726modn= 287. Leschiffrs sont les mmes.
Le barme qui suit est donnÉ sur 20 points, mais la proportion de points de chaque exercice a ÉtÉ conservÉe par rapport au barme annoncÉ À l’examen.
1
