Pour le RSA, comment dois-je calculer l'exposant secret?

RSA, comment dois-je calculer l'exposant secret?

Donné p et q deux nombres premiers, et phi=(p-1)(q-1), et le public exposant (0x10001), comment puis-je obtenir le secret de l'exposant 'd' ?

J'ai lu que j'ai à faire: d = e-1 mod phi à l'aide de l'inversion modulaire et la euclidienne équation mais je ne comprends pas comment la formule ci-dessus des cartes pour le un-1 ≡ x mod m formule sur la modularité de l'inversion de la page wiki, ou comment il est associé à la euclidienne, PGCD équation.

Quelqu'un peut-il aider s'il vous plaît, merci

Il ressemble à java, au moins, j'ai besoin de quelque chose comme d=(java.les mathématiques.BigInteger)e.modInverse(phi);
oui, cela devrait le faire...bonne chance!
Je vais voter pour fermer cette question hors-sujet parce que c'est des maths, pas de programmation.

OriginalL'auteur Chris | 2010-07-09

  1. 17

    Vous pouvez utiliser le algorithme d'Euclide étendu à résoudre pour d dans la congruence

    de = 1 mod phi(m)

    Pour le chiffrement RSA, e est la clé de cryptage, d est la clé de déchiffrement, et le chiffrement
    et le déchiffrement sont effectuées par exponentiation mod m. Si vous chiffrer un message a
    avec les principaux e, puis de les décrypter à l'aide de la clé d, le calcul de (ae)e = ade mod m. Mais
    depuis de = 1 mod phi(m), Euler indicateur théorème nous dit que ade est congruent
    un1 mod m -- en d'autres termes, vous obtenez de retour à l'original a.

    Il n'existe pas de moyens efficaces pour obtenir la clé de déchiffrement d ne connaissant que l'
    la clé de chiffrement e et le module m, sans la connaissance de la factorisation m = pq, de sorte
    Le chiffrement RSA est censé être sécurisé.

    J'ai eu de la chance avec le code ici: en.wikipedia.org/wiki/... tout Simplement de la saisie d'une=e, b=phi à cette fonction me donne x,y - y est jeté, et x est le secret de l'exposant d !
    C'est dommage d'Euler et d'Euclide n'a pas survécu à la perception de leur part des revenus de brevets. Si longtemps, et merci à tous pour les maths!
    Juste pour être complet, une autre façon de faire le calcul avec les mêmes performances de base est d = e**(phi(phi(m))-1) mod phi(m).
    L'identité se tient, mais je suis en désaccord que la performance est comparable. Trouver un inverse mod n avec d'Euclide l'algorithme peut être fait en O(log n) fois. Mais trouver phi(n) est aussi difficile que l'affacturage n, pour lesquels il n'existe pas de O( (log n)^k ) pour tout k. Et si l'origine p et q sont bien choisies, (p-1) et (q-1), seront eux-mêmes ont de grands facteurs premiers, de décision phi(phi(m)) difficile à calculer.
    D'accord, vous devez savoir phi(phi(m)) ou c'est inutile. Si p-1=2*p' et q-1=2*q', p' et q' sont des nombres premiers, puis phi(phi(m)) est de 2*p'*q'. Une telle p et q sont appelés nombres premiers sûrs et sont communs (bien qu'inutile) dans le RSA les implémentations.

    OriginalL'auteur Jim Lewis