🚀 go-pugleaf

In article <1992Sep28.202620.25342@linus.mitre.org> 
lewis@aera8700.mitre.org (Keith Lewis) writes:

|> >If you have somebody's N and E, and you somehow factor N into P and Q, you
|> >must then find a D that works in the above equality (a non-trivial task, I
|> >think).  Then you can decrypt his/her messages.


In article <1992Sep28.215845.10593@Princeton.EDU>, 
mgflax@ernie.Princeton.EDU (Marshall G. Flax) writes:

|> Suppose you know P, Q, and E.  Then D is the multiplicative inverse of E
|> modulo (P-1)(Q-1).  Finding multiplicative inverses is in fact a trivial
|> operation if one keeps track of the quotients and remainders generated
|> while applying the Euclidean algorithm in GCD(E,(P-1)(Q-1)), but I'll
|> leave that as an exercise to the reader!
 
Finding D, given N, P, Q and E, is computationally feasible, although not
quite trivial.

However, finding P and Q, given N and E, is not presently computationally
feasible.  This fact is the *entire* basis for security of RSA.


-- 
	   _   _
    /_    / ) / ) Jeff Hull          jhull@den.mmc.com
   //_) -/- -/-   1544 S. Vaughn Cir
/_/ \_/ /   /	  Aurora, CO 80012   303-977-1061