Cryptage RSA
Répondre à la discussion
Affichage des résultats 1 à 3 sur 3

Cryptage RSA



  1. #1
    rikooneh

    Cryptage RSA


    ------

    J'ai un exercice a résoudre. Je voulais savoir si ce que j'ai écrit était juste.

    N'ayant pas le signe de la congruence je vais poser*:
    a#b[n] veut dire a est congru à b modulo n

    Énoncé

    p et q sont deux nombres premiers distincts et n=pq
    on pose m=(p-1)(q-1) et on choisit a premier avec m
    on a montre qu'il existe a et b tels que ab=1+mc
    on a aussi montre que pour tout entier x, x^(ab)#x[p] et x^(ab)#x[q]

    1. Il faut montrer que x^(ab)#x[n]
    on sait que x^(ab)#x[p] , soit x^(ab)-x=k1*p (1)
    on sait que x^(ab)#x[q] , soit x^(ab)-x=k2*q (2)
    donc k1*p=k2*q
    donc p divise k2*q. Comme p et q sont des nombres premier, ils sont premiers entre eux. D’après le théorème de gauss, p divise k2. Soit k2=k3*p.
    En remplaçant dans l’équation (2) , x^(ab)-x=k3*p*q=k3*n. Ce qui veut dire que x^(ab)x^(ab)#x[q]#x[n].

    le but est de crypter un message. Avec m, n, p, q, a et b ayant les mêmes propriétés qu'au début de l'énoncé
    Cryptage
    on choisit a et n. Ce qui donne la clé publique (n*; a). Le message crypte sera*:
    C(x)#x^a[n]

    Décryptage
    avec la clé publique on décrypte avec la formule:
    D(y)#y^b[n]
    la personne qui décrypte connaît la valeur de b (clé privée)
    Le but est de crypter une numéro de téléphone. Les numéros sont crypte deux par deux.

    a. Justifier que n supérieur ou égal a 100.

    On sait que D(y) est un chiffre compris entre 0 et 99 puisque les numéros sont cryptes deux par deux.
    Comme D(y)#y^b[n], ça veut dire que le reste r de la division euclidienne de y^b par n est compris entre 0 et 99. Donc r vaut au maximum 99. Comme r<n (définition de la division euclidienne) l'entier qui vient après 99 est 100.
    Donc n>=100

    b. montrer que la plus petite clé publique possible est (106,3)

    on sait que n>=100

    *Supposons que n=100 (n est un produit de deux nombres premiers)
    n=2*50=100. Or 50 n'est pas premier donc n est différent de 100

    *supposons que n=101. 101 ne peut pas se décomposer en produit de nombre premiers car il est premier. Donc n différent de 101

    *Supposons que n=102. 102=51*2 . Or 51 n'est pas premier donc n différent de 102

    *Supposons que n=103. 103 ne peut pas se décomposer en produit de nombre premiers car il est premier. Donc n différent de 103

    *Supposons que n=104. 104=52*2. 52 n'est pas premier donc n différent de 104

    *Supposons que n=105. 105=3*35. 35 n'est pas premier donc impossible
    * Supposons que n=106. 106=2*53. 2 et 53 sont premier donc n=106 est une cle possible.
    Donc m=(2-1)*(53-1)=52
    On choisit a premier avec 52. Le plus petit entier premier avec 52 est 3. donc a=3

    c. il faut crypter 06 13 87 11 45 (si mes calculs sont bons)

    c(06)#6^3[106]=04
    c(13)#13^3[106]=77
    c(87)#87^3[106]=31
    c(11)#11^3[106]=59
    c(45)#45^3[106]=71

    -----
    Dernière modification par rikooneh ; 21/03/2013 à 19h42.

  2. #2
    Cherchell


  3. #3
    rikooneh

    Re : Cryptage RSA

    Merci beaucoup. j'ai a peu pres tout compris. Je pense avoir utilise le meme raisonnement que ce qui est ecrit dans le pdf.
    Je voudrais juste savoir (car ma demo de resemble pas a la tienne) si ce que j'ai ecrit pour montrer que la cle de cryptage la plus petite est (106,3) est juste (voir question b de mon post)

Discussions similaires

  1. Cryptage RSA + nombre premier
    Par invitec4b3954c dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 26/10/2008, 14h36
  2. Question sur le cryptage RSA
    Par lezebulon dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 02/06/2008, 22h47
  3. cryptage par chiffrement RSA
    Par invite86f7e163 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 07/08/2006, 17h24
  4. Cryptage RSA
    Par invite6644da5a dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 13/11/2005, 21h43
  5. Problème du cryptage RSA
    Par invite4b26dc46 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 11/06/2004, 14h49