Annonce

Réduire
Aucune annonce.

Comment fonctionne le RSA ?

Réduire
Cette discussion est fermée.
X
X
 
  • Filtre
  • Heure
  • Afficher
Tout nettoyer
nouveaux messages

  • Comment fonctionne le RSA ?

    Bonjour à tous.
    J'ai beau lire et relire des tutoriels sur le RSA, je n'arrive à rien.
    Comme ici.

    Par exemple :
    Je choisi p et q deux nombres premiers.
    p=3
    q=47

    Le calcul de n est n=p*q.
    n=141

    Le calcul de f est f=(p-1)(q-1)
    f=92

    Je choisi un nombre premier e.
    e=7

    Petit calcul inverse 7 mod 92.
    7*d=1 % 92 ==> résultat : 79

    La clef publique = x^7 % 141
    La clef privée = y^79 % 141

    Je choisi une valeur x inférieur à n.
    x=10

    Chiffrement avec la clef publique x^7 % 141
    y=139

    Déchiffrement avec la clef privée y^79 % 141
    z=16
    Edit: z=10

    X est censé être égale à Z . Ce n'est pas le cas.
    A mon avis je n'ai pas bien compris la valeur e ("e premier avec f" ?).

    Quelqu'un peut m'expliquer ?
    Merci d'avance
    Dernière modification par Yarflam, 04 février 2013, 19h54.
    ~ Yarflam ~

    ❉ L'Univers se dirige vers son ultime perfection ❉

  • #2
    Ta valeur de e est bonne. "e premier avec f" signifie qu'il faut trouver une valeur de e de manière à ce que e et f soient copremiers, c'est à dire que e et f n'aient aucun autre dénominateur commun que 1 ou -1.

    Tu te trompes dans tes calculs finaux.

    Reprenons à partir du calcul de d. On utilise :
    Code:
    ed mod (p-1)(q-1) = 1 <=> ed mod f = 1
    Avec tes valeurs on obtient bien d = 79.

    On a donc :
    Clé privée = (d,n) = (79,141).
    Clé publique = (e,n) = (7,141).

    On chiffre 'HACK' :
    HACK = 72656775 en (ASCII).

    Ensuite, on passe à l'étape de slicing. Il faut segmenter la séquence en blocs comportant moins de chiffres que n. Ici on a n = 141, du coup on segmentera par des blocs de deux chiffres en complétant par des zéros si nécessaire :
    72 65 67 75

    On passe au chiffrement avec la clé publique :
    On utilise la formule bloc^e mod n .
    • 72^7 mod 141 = 27
    • 65^7 mod 141 = 53
    • 67^7 mod 141 = 73
    • 75^7 mod 141 = 111


    Notre message 'HACK' chiffré est donc 275373111.

    On le déchiffre avec la clé privée :
    On utilise la formule bloc^d mod n.
    • 27^79 mod 141 = 72
    • 53^79 mod 141 = 65
    • 73^79 mod 141 = 67
    • 111^79 mod 141 = 75


    On obtient donc la séquence 72 65 67 75. Ce qui en ASCII nous donne bien 'HACK'.
    Dernière modification par MadHatter, 04 février 2013, 18h44.
    Ex-membre Hackademiciens.

    Commentaire


    • #3
      Merci beaucoup !
      J'ai tout compris.
      Le calcul "139^79 mod 141" vaut bien 10.
      Python m'a mal interprété la sortie "math.pow(139,79) % 141".

      Par contre, Comment puis-je faire pour calculer une grande puissance ?
      ~ Yarflam ~

      ❉ L'Univers se dirige vers son ultime perfection ❉

      Commentaire


      • #4
        Chouette j'ai réussi à faire fonctionner mon script python.
        Et pour répondre à ma question : pour calculer une grande puissance, il faut utiliser pow() et pas math.pow().

        #!/usr/bin/python
        #RSA cryptographic system by Yarflam vBeta
        import math, random

        def yrs_p(yrsv_a,yrsv_b):
        yrsv_r=[]
        while yrsv_a < yrsv_b:
        yrsv_s=2
        yrsv_t=1
        while yrsv_s < yrsv_a:
        yrsv_tmp=float(yrsv_a)/float(yrsv_s)
        yrsv_tmp=yrsv_tmp-int(yrsv_tmp)
        if yrsv_tmp == 0:
        yrsv_t=0
        yrsv_s=yrsv_s+1
        if yrsv_t == 1:
        yrsv_r.append(yrsv_a)
        yrsv_a=yrsv_a+1
        return yrsv_r

        def yrs_mi(yrsv_a,yrsv_n):
        yrsv_r=-1
        yrsv_i=1
        yrsv_t=0
        while yrsv_t == 0 and yrsv_i < yrsv_a:
        yrsv_i=yrsv_i+1
        yrsv_temp=float(1+yrsv_n*yrsv_i)/float(yrsv_a)
        yrsv_temp=yrsv_temp-int(yrsv_temp)
        if yrsv_temp == 0:
        yrsv_t=1
        yrsv_r=(1+yrsv_n*yrsv_i)/yrsv_a
        return yrsv_r

        d=-1
        while d == -1:
        ga=yrs_p(2,20)
        gb=yrs_p(20,50)
        p=ga[int(random.random()*len(ga))]
        q=gb[int(random.random()*len(gb))]
        n=p*q
        f=(p-1)*(q-1)
        e=ga[int(random.random()*len(ga))]
        d=yrs_mi(e,f)

        print "p=",p
        print "q=",q
        print "n=",n
        print "f=",f
        print "e=",e
        print "Modulation inverse = "+str(e)+"*d=1 % "+str(f)+"; R="+str(d)
        print "Public key = x^"+str(e)+" % "+str(n)
        print "Private key = y^"+str(d)+" % "+str(n)

        x=int(raw_input('x < '+str(n)+'; x = '))
        y=int(pow(x,e) % n)
        z=int(pow(y,d) % n)
        print "X="+str(x)
        print "Y="+str(int(y))
        print "Z="+str(int(z))

        http://pastebin.com/J4BdnhsB

        Je me demande quand même si dans ma fonction yrs_mi (fonction de modulation inverse), j'ai bien fait d'ajouter une limite (i < a). Si quelqu'un sait reconnaître une modulation inverse sans résultat, comme 3 mod 12, ce serai vraiment sympas

        C'est passionnant le RSA !
        Dernière modification par Yarflam, 05 février 2013, 11h13.
        ~ Yarflam ~

        ❉ L'Univers se dirige vers son ultime perfection ❉

        Commentaire


        • #5
          Bonjour.
          Je suis en train de programmer une application de cryptage RSA.
          Pas publiable pour le moment, je compte l'affiner.

          Par contre je partage une application de reverse qui devrait vous intéresser pour des petites clefs publiques.
          http://pastebin.com/mdX1b3Qy

          Vous indiquez 'n' et il vous trouve p & q. E vous le connaissez déjà avec la clef publique. Y a plus qu'à calculer
          NB : Ce script est provisoire et je compte bien augmenter la vitesse de déchiffrage d'une clef publique RSA.
          Dernière modification par Yarflam, 09 février 2013, 13h23.
          ~ Yarflam ~

          ❉ L'Univers se dirige vers son ultime perfection ❉

          Commentaire


          • #6
            Il est cool ton explication MadHatter, simple et rapide, comme je les aimes

            Commentaire


            • #7
              Envoyé par Yarflam Voir le message
              Par contre, Comment puis-je faire pour calculer une grande puissance ?
              Ceci peut aider pour calculer des puissances avec de grand nombre A et B, modulo N ((A^B)%N).


              En esperant t'aider !

              Commentaire


              • #8
                Ceci peut aider pour calculer des puissances avec de grand nombre A et B, modulo N ((A^B)%N).


                En esperant t'aider !
                Je ne pense pas, déjà c'est un grand déterrage, ensuite il a trouvé la solution, et elle devait être en python (langage de programmation)

                Je ferme le topic !

                Commentaire

                Chargement...
                X