From: Derek Atkins <warlord@ATHENA.MIT.EDU>
Date: Sat, 23 Apr 94 12:10:24 PDT
To: "Jim Sewell - KD4CKQ" <jims@Central.KeyWest.MPGN.COM>
Subject: Re: How to explain...
In-Reply-To: <9404231425.AA12751@Central.KeyWest.MPGN.COM>
Message-ID: <199404231910.PAA03059@charon.MIT.EDU>
MIME-Version: 1.0
Content-Type: text/plain


The difficulty really is not reversing the mathematics, thats easy
(and, in fact, it is already done for you in part of the algorithm).


What makes it hard to reverse is the fact that these algorithms are
actually sets of algorithms, and it is the key which sets the actualy
unique algorithm that is being used, and since the key is secret, you
need to find a weekness in the set of algorithms as a whole, or
brute-force search all the keys to find the exact algorithm being
used.  So, to follow your friends example, if you have X to go from
plain->crypt, then you can reverse it, but part of 'X' is the key, and
if you have the key, you can already decrypt it!

As for RSA (or other such algorithms), it is not poroven, but it is
believed that braking the system (for a single key) is as hard as
factoring that key's modulus.  But factoring is a known-to-be-hard
problem (It is an NP problem, I don't believe it is NP-Complete, but
please someone correct me if I am wrong).  Again, it is a known
algorithm to take the crypted message and decrypting it.  The problem
is that, again, it is a specific algorithm in a set of algorithms, and
you have to find the specific key that is being used (actually, in the
case of RSA, there are at least two keys that you can use, but when
you are talking about 512-bit keys, this means that there are 2 in
10^130 keys to try to guess.

Again, it is the case that there are a set of formula, but truely
reversing it requires knowledge of the key, which you do not have, and
if you had said knowledge, you wouldn't NEED to reverse the formula,
since the forumal reverses itself for you with the proper key.

I hope this explains it some.  If you have more questions, or someone
else feels like clarifying, please go ahead.

Enjoy!

-derek