🚀 go-pugleaf

In article <BvExML.Juq@usenet.ucs.indiana.edu> shulick@yankton.ucs.indiana.edu writes:
>Let's say someone retreives the DES source code, which is easy enough.  Why
>WOULDN'T they be able to take every single mathematical operation, reverse each
>one, and then have a "decrypt()"?

It's been done.  In fact, it will probably come with the DES
source.  It may even be called "decrypt()"!  Problem is, it requires
a key...

DES is entirely reversible if you have the key, but not very
reversible otherwise; it would be a rather useless system otherwise.

>Sam Hulick

   Eli   ebrandt@jarthur.claremont.edu

shulick@yankton.ucs.indiana.edu writes:

>NOTE: Yes, you may have noticed I'm posting a lot about breaking DES/UNIX
>encryption.  I am not a hacker, I'm merely trying to understand the way it
>works and learn exactly how secure this algorithm really is.  I gave up hacking
>a long time ago. (:

I don't feel like going into the hacker/cracker distinction right now... :-)

>Let's say someone retreives the DES source code, which is easy enough.  Why
>WOULDN'T they be able to take every single mathematical operation, reverse each
>one, and then have a "decrypt()"?  I know it's not that simple, but how has DES
>made it so even a good mathematician can't just reverse all the operations?

Well, how do you plan on reversing the step that looks like "free(key)"?  If
you're referring to UNIX crypt(3) encryption, it's the password that is used
as the key...Even if you had the key/password, reversing every operation
pretty much leaves you with just 0's... :-)  If you mean DES encryption, well
of course there's a decrypt()...How else is someone supposed to be able to
read the data after they've encrypted it? :-)

My point: The only thing decrypt has to go on is the output of crypt, so you
can't simply reverse each operation...And sometimes (public-key, one-way hash
functions) it's still hard to reverse things even if you know exactly what
the encryption algorithm is doing to the plaintext...

-- 
 -- Erick, the perfect square  :-)

     Here's something that's been troubling me for a while: Bearing in
mind that 1) commercially available software (Mathematica, Maple,
etc.) are capable of computing & displaying hundreds of digits of,
say, pi in next to no time (thousands of digits if you let the program
run overnight), and that 2) the digits of pi (well, the first billion
or so anyway) so far appear to be "normal"; that is, they appear with
roughly equal frequency... 

     Is it possible to use some irrational number as the basis for a
strong random number generator?  For example, suppose that I was to
use the decimal part of 17 * (pi * e ^ 5), specifying in advance or
perhaps as part of a public key sequence which decimal digit would be
used as the starting point.  If I were to use the aforementioned idea
with the proviso that the "key" would begin at the 175th digit, this
would appear to be usable as a random-number generation scheme
considerably more "random" than any deterministic function that could
be implemented in software.

     Of course, I could further muddle things by factoring in more
obscure yet easy-to-remember numbers, such as, oh, the inverse
fine-structure constant, Feigenbaum's number, the wavelengths of the
Fraunhofer lines....

     If this is a really stupid idea, please tell me so that I can
quit wasting brain and silicon power on it.  If not, feel free to use
it if you haven't thought of it already.

     Some of you probably have.  You know who you are...

=============================================================================
Dave Schulman                                   capsalad@uful07.phys.ufl.edu
                                                Late of the
                                                University of Florida's
                                                Department of Physics
                                                I'm still one
=============================================================================

shulick@indiana.edu (Sam Hulick) writes:
>
>NOTE: Yes, you may have noticed I'm posting a lot about breaking DES/UNIX
>encryption.  I am not a hacker, I'm merely trying to understand the way it
>works and learn exactly how secure this algorithm really is.  I gave up hacking
>a long time ago. (:
>
>Let's say someone retreives the DES source code, which is easy enough.  Why
>WOULDN'T they be able to take every single mathematical operation, reverse each
>one, and then have a "decrypt()"?  I know it's not that simple, but how has DES
>made it so even a good mathematician can't just reverse all the operations?
>

Obviously, if you know the key used, then DES is reversible - how else, can
the plaintext be retrieved.  However, if you mean is it possible to reverse 
the process to produce the plaintext & key from the ciphertext, then the answer
is NO.

Why not?  Each of the subkeys is used in an XOR operation, you can't reverse
this one to one.  A XOR B = C, if you know C you can't be sure what A and B are.

OK?

-- 
"Therefore was the name of it called Babel;  because Jehovah
 did there confound the language of all the earth." -Genesis 11:9
.
  John L.S.Davies          dc91jld@brunel.ac.uk
.
.

In article <1992Oct1.082352.16506@eng.ufl.edu> capsalad@uful07.phys.ufl.edu (Dave Schulman) writes:

	Here's something that's been troubling me for a while: Bearing in
   mind that 1) commercially available software (Mathematica, Maple,
   etc.) are capable of computing & displaying hundreds of digits of,
   say, pi in next to no time (thousands of digits if you let the program
   run overnight), and that 2) the digits of pi (well, the first billion
   or so anyway) so far appear to be "normal"; that is, they appear with
   roughly equal frequency... 

Fair enough.  They appear random.

	Is it possible to use some irrational number as the basis for a
   strong random number generator?  For example, suppose that I was to

Yes.  There exist some irrational numbers, the sequence of digits
(bits etc) of which are unpredictable in a useful sense.  In fact,
almost all of them have this property.  (Irrationals are uncountable;
programs to calculate the digits are countable.)

   use the decimal part of 17 * (pi * e ^ 5), specifying in advance or
   perhaps as part of a public key sequence which decimal digit would be
   used as the starting point.  If I were to use the aforementioned idea
   with the proviso that the "key" would begin at the 175th digit, this
   would appear to be usable as a random-number generation scheme

So the secret information would be *which* irrational you would be using?

   considerably more "random" than any deterministic function that could
   be implemented in software.

Eh?  You've just described a number which can be generated by a deterministic
function implemented in software.  What is Mathematica, if it isn't software?
How do you propose to use your digits of an irrational number, if you
can't calculate them more than once (i.e. non-deterministic)?

	Of course, I could further muddle things by factoring in more
   obscure yet easy-to-remember numbers, such as, oh, the inverse
   fine-structure constant, Feigenbaum's number, the wavelengths of the
   Fraunhofer lines....

Translation: you can expand your keyspace by adding in other quantities.

	If this is a really stupid idea, please tell me so that I can
   quit wasting brain and silicon power on it.  If not, feel free to use
   it if you haven't thought of it already.

It doesn't sound "really stupid".  You just have to ensure that the
bit or digit pattern of your irrational isn't predictable.  If I knew
you were using the digits of 3\pi, I could predict the bit stream and
crack your communications.  Another problem might be that actually
calculating the digits might be computationally expensive.

Paul
--
Paul Leyland <pcl@oxford.ac.uk>          | Hanging on in quiet desperation is
Oxford University Computing Service      |     the English way.
13 Banbury Road, Oxford, OX2 6NN, UK     | The time is come, the song is over.
Tel: +44-865-273200  Fax: +44-865-273275 | Thought I'd something more to say.

In article <1992Oct1.082352.16506@eng.ufl.edu> capsalad@uful07.phys.ufl.edu (Dave Schulman) writes:
>     Here's something that's been troubling me for a while: Bearing in
>mind that 1) commercially available software (Mathematica, Maple,
>etc.) are capable of computing & displaying hundreds of digits of,
>say, pi in next to no time (thousands of digits if you let the program
>run overnight), and that 2) the digits of pi (well, the first billion
>or so anyway) so far appear to be "normal"; that is, they appear with
>roughly equal frequency... 

Well, looking at the Maple situation; it's got 10000 digits of Pi as a
"built-in" thing.  People tend to check out what Pi looks like as one
of their first bits of "playing" with it, so the SCG put 10K digits
in.

I would be totally unsurprised to hear that Wolfram did the same with
Mathematica.

What this means is that there's a table of 10000 digits (which can
probably get BCD packed into about 5K as a "no-brainer" optimization).
I once get Maple going to compute digit 10001.  I didn't wait for it
to find it; it probably would take a LONG time.  Hours?  Days?  Weeks?
I don't know which.

>     Is it possible to use some irrational number as the basis for a
>strong random number generator?  For example, suppose that I was to
>use the decimal part of 17 * (pi * e ^ 5), specifying in advance or
>perhaps as part of a public key sequence which decimal digit would be
>used as the starting point.  If I were to use the aforementioned idea
>with the proviso that the "key" would begin at the 175th digit, this
>would appear to be usable as a random-number generation scheme
>considerably more "random" than any deterministic function that could
>be implemented in software.

It's PROBABLY going to be pretty random; I think there have been a
number of theses in statistics/number theory on the arrangement of
digits in Pi.

Unfortunately, any irrational number whose properties are "ugly"
enough for encryption purposes is probably gonna be a pain to compute
to any significant number of decimal places.

Remember as well that the term "irrational" applies to numbers whose
digits DO have lots of patterns; the only requirement is that the
period be non-constant.

>     Of course, I could further muddle things by factoring in more
>obscure yet easy-to-remember numbers, such as, oh, the inverse
>fine-structure constant, Feigenbaum's number, the wavelengths of the
>Fraunhofer lines....
>
>     If this is a really stupid idea, please tell me so that I can
>quit wasting brain and silicon power on it.  If not, feel free to use
>it if you haven't thought of it already.

I don't think it's stupid, it's just not likely to be {\bf practical}.
This is true of MANY things in math...  

Of late, I've been doing stuff on solving minimum cost network
problems.  There's some recent "cute" algorithms that are
theoretically wonderful.  Unfortunately, the "classic" Simplex method
will beat 'em into the ground for any problems that are not absolutely
ENORMOUS (and that current hardware probably couldn't solve EITHER
way).

Enough work, and perhaps one of the algorithms may be made practical.
And in working on improvements, some other idea may come out.  Working
with irrational number patterns probably works this way too.

-- 
Christopher Browne
cbbrowne@csi.uottawa.ca
University of Ottawa
Master of System Science Program

dc91jld@brunel.ac.uk (John L Davies) writes:
>Obviously, if you know the key used, then DES is reversible - how else, can
>the plaintext be retrieved.  However, if you mean is it possible to reverse 
>the process to produce the plaintext & key from the ciphertext, then the answer
>is NO.

There have been a number of replies to Sam Hulick's article, and they all
say about the same thing.  However, I think Mr. Hulick has confused DES
with a public key system like RSA.  The question is, why can't you decrypt
a message with the public key?

I don't have a very good understanding of public key encryption, but I
think that the basic idea has two elements:
1) an extremely difficult problem
2) a trick for solving it quickly that only works when you have some
   special information (the secret key)
RSA is based on the difficulty of reversing exponentiation by large numbers
in modular arithmetic unless factors of the exponent are known (with a trick
discovered by Euler, of course) and the fact that multiplying two large prime
numbers together is much easier than factoring an even larger composite.
(At least, nobody knows of easy ways to do these things.  Yet.)  Conceptually,
it can be reversed, but the ammount of computation required is prohibitive.

swehtam bob

>Let's say someone retreives the DES source code, which is easy enough.  Why
>WOULDN'T they be able to take every single mathematical operation, reverse each
>one, and then have a "decrypt()"?  I know it's not that simple, but how has DES
>made it so even a good mathematician can't just reverse all the operations?

Suppose		A = B XOR C
now reverse it, given A = 1, find B and C.  Not so easy, huh?  It
gets worse with AND and OR.

Suppose the function you wish to reverse takes a 56-bit DES key, encrypts
the constant plaintext 0x0000000000000000, and generates 64 bits of
ciphertext.  It *IS* possible to reverse this.  You end up with
56 boolean equations, one for each bit of the key, and maybe you want
one for indicating whether it's a possible output or not.  

Unfortunately, each of the 56 equations involves 64 input variables
(the ciphertext bits), and there are about 2**55 terms in each equation 
(corresponding to each possible ciphertext output where the key bit in 
question is a 1 and the other key bits vary).  I say "about" because
"collisions" where two different keys map the same plaintext to
the same ciphertext would cause redundant terms in the equation,
which could be removed.  Due to the way DES "mixes up the bits", 
these equations won't reduce much.  

This analysis is almost as messy as just pre-computing a "dictionary"
of what all 2**56 keys generate, and looking up the result you want
to crack to find the corresponding key.

					Gordon L. Burditt
					sneaky.lonestar.org!gordon