Comment le facteur de RSA module donné au public et privé exposant?

J'ai une clé privée RSA avec le module m, public exposant e et privé exposant d, mais le programme que je suis en utilisant des besoins, le module de facteurs premiers p et q.

Est-il possible d'utiliser e et d pour obtenir p et q?

OriginalL'auteur user621745 | 2011-04-21

  1. 13

    Oui, une fois que vous savez le module N, et public/privé exposants d et e, il n'est pas trop difficile à obtenir p et q tels que N=pq.

    Ce document par Dan Boneh décrit un algorithme pour le faire. Il s'appuie
    sur le fait que, par définition,

    de = 1 mod phi(N).

    Pour toute choisies au hasard "témoin"
    en (2,N), il y a environ 50% de chances d'être en mesure de l'utiliser pour trouver un non trivial
    racine carrée de 1 mod N (appelons-la x). Alors pgcd(x-1,N) donne un de ces facteurs.

    Juste en coupant les cheveux en quatre: RSA tous les besoins, c'est que de = 1 mod p-1 et mod q-1, ainsi que de = 1 mod lcm(p-1,q-1), qui est un diviseur strict de phi(N) (avec phi(N) c'est juste la façon RSA a été décrite pour la première). Toutefois, la méthode décrite par Boneh œuvres dans le cas général.

    OriginalL'auteur

  2. 9

    Vous pouvez utiliser l'outil open source, j'ai développé, en 2009, qui convertit les clés RSA entre l'AFD de format (n,e,d) et CRT format (p,q,dp,dq,u), et de l'autre manière autour. C'est sur SourceForge : http://rsaconverter.sourceforge.net/

    L'algorithme j'ai mis en place est basé sur les idées présentées par Dan Boneh, tel que décrit par la réponse précédente.

    J'espère que ce sera utile.

    Mounir IDRASSI - IDRIX

    OriginalL'auteur

  3. 3

    J'ai posté une réponse sur le crypto pile d'échange de répondre à la même question ici. Il utilise la même approche que celle décrite dans Boneh du papier, mais fait beaucoup plus d'explications sur la façon dont il fonctionne réellement. J'ai aussi essayer d'assumer un minimum de connaissances antérieures.

    Espérons que cette aide!

    OriginalL'auteur