Probabilités IF Corrigé du devoir du mai

Description

• 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

Sujets

• Redaction
• Probabilité

Informations

• Publié par: profil-urra-2012
• Publié le: 01 mai 2010
• Nombre de lectures: 112
• Langue: Français

Extrait

Probabilites – 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 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 mmes 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 = 468mme, 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 mmes.

Le barme qui suit est donnÉ sur 20 points, mais la proportion de points de chaque exercice a ÉtÉ conservÉe par rapport au barme annoncÉ À l’examen.

1