🚀 go-pugleaf

In article <1992Sep25.191759.25545@nevada.edu>, oliverm@nevada.edu (Moises Oliveira ) writes:
>I keep hearing that RSA uses the product of two big primes to produce a really
>big number that is hard to factor.  Appearently the diffuculty in factoring
>the product of two primes is what makes RSA so hard to crack.

Yes.

>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 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?

You have two large primes, P and Q.
Let N = P * Q.  That's your "really big number".
Find a pair of numbers, E and D, such that mod(E * D, (P-1)*(Q-1)) = 1
You publish N and E as your public key.  To encrypt messages, calculate
    Y = mod(X ** E, N), where X is the input data

You keep N and D as your private key.  To decrypt messages, calculate
    X = mod(Y ** D, N), where Y is the encrypted data

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.

>Finally, is the product of two primes method used in all public keys, or
>just in RSA? what about PGP?  What about the one the NSA and NIST produced.?

PGP is essentially RSA performed on a bitmask which is used repeatedly on
a single message.  I don't know about the others.

>If anyone has any books or other materials that they would reccommend for
>reading on the security of this type, I would appreciate it.

Check out the "Mathematical Games" column of _Scientific American_, August
1977, for a cursory examination of RSA.  Then August 1978 for a full-blown
article.

Keith Lewis             klewis@mitre.org          "Mr. Cheap"
I don't dance to music; music dances to me.  Email me for my PGP key.
The above may not (yet) represent the opinions of my employer.