🚀 go-pugleaf

In article <1992Sep25.191759.25545@nevada.edu>, oliverm@nevada.edu
(Moises Oliveira) writes:
|> Now, assume that the actual factoring is trivial by use of some mathematical
|> method.  What good does it do you?  Exactly how does having the two prime 
|> factors of some really big number do to help you crack RSA?
|> 
|> In other words, if I see someones public key, how can I find what really
|> big number they used? And then after I factor it, what whould I do to the
|> encrypted communications to return it to plain text?

Here is a Mathematica function to crack an RSA public key consisting of
the public modulus n ("the big number", as you call it) and the public
exponent e:

crackRSA[publicKey[e_,n_]] :=
  Block[ { factors = FactorInteger[n], p, q },
    p = factors[[1,1]]; q = factors[[2,1]];
    PowerMod[e, -1, (p - 1) (q - 1)]
  ]

p and q are the two prime factors of n.  The function returns the secret
(private) exponent d which is the multiplicative inverse of e in the
finite field of numbers in the range [0,(p-1)(q-1)-1].  (I have never
tried it for moduli n which have more than about 20 digits ... )

Check out any good book on modern cryptography or chapter 33 of
"Introduction to Algorithms" by Cormen, Leiserson and Rivest
for the number theoretical background.

-- 
Robert Marti                    |  Phone:    +41 1 254 72 60
Informationssysteme             |  FAX:      +41 1 262 39 73
ETH-Zentrum                     |  E-Mail:   marti@inf.ethz.ch
CH-8092 Zurich, Switzerland     |