Cryptography-Digest Digest #937, Volume #8 Wed, 20 Jan 99 17:13:03 EST
Contents:
Re: Metaphysics Of Randomness (Darren New)
Re: Metaphysics Of Randomness (R. Knauer)
Re: Visual Basic Cipher (Jim Dunnett)
Help. Protocol feasibility advice needed ([EMAIL PROTECTED])
Re: Metaphysics Of Randomness ("John Feth")
Re: Metaphysics Of Randomness ("Trevor Jackson, III")
Re: Metaphysics Of Randomness ("Trevor Jackson, III")
Re: Metaphysics Of Randomness (R. Knauer)
Scramdisk-Question ("David Rex")
Amateur/Newbie question... ("Mike DeTuri")
----------------------------------------------------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Wed, 20 Jan 1999 19:29:08 GMT
> >Well, turing machines are mathematical abstractions, and they are by
> >definition deterministic.
>
> So what if they are deterministic? Does that mean that the halting
> problem is not real?
No, it means they likely don't have anything to do with radioactive
decay and quantum mechanics.
> >Once you start talking about radioactivity,
> >there's no "definition" that assures they're deterministic.
>
> Again, I ask "so what"?
Well, *you* brought it up! :-) I think my point was that QM can be
nondeterministic, and hence doesn't need any infinities to make it
possible to be random.
> >I wouldn't
> >want to try to deduce properties of the real world from properties of
> >turing machines.
>
> Why not? Chaitin does. He claims that his halting probability is
> intimately related to randomness in arithmetic, which something in the
> real world - 1,2,3, and all that.
Ummmm, no.... 1,2,3 isn't real-world at all. It's just very very
convenient. If I have three apples on my desk, the only reason there's
three of them is that I think of them as apples. If one's rotten, I have
only two edible apples, but I still have three apples. If I mush them
into sause, it's still three apples but there's no longer any 1,2,3
about them. So arithmetic isn't any more real-world than turing
machines are.
> Shades of Godel's Epimenides Paradox - the statement that says that it
> cannot be proven true. Here you have the program that proves it cannot
> halt but returns a statement that it can.
Exactly. I think most diagonalization arguments are reducto ad absurdem
too FWIW.
> >every time it fills up and then ask what the expected time of an
> >insertion is.
>
> Again, infinite recursion shows up.
Not infinite. Just unbounded. These are different.
> I suppose that is an undocumented feature of Windows. :-)
(giggle)
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Wed, 20 Jan 1999 19:19:03 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 20 Jan 1999 18:39:14 GMT, Darren New <[EMAIL PROTECTED]>
wrote:
>Well, turing machines are mathematical abstractions, and they are by
>definition deterministic.
So what if they are deterministic? Does that mean that the halting
problem is not real? I don't get the connection between determinism
and the halting problem.
>Once you start talking about radioactivity,
>there's no "definition" that assures they're deterministic.
Again, I ask "so what"?
>I wouldn't
>want to try to deduce properties of the real world from properties of
>turing machines.
Why not? Chaitin does. He claims that his halting probability is
intimately related to randomness in arithmetic, which something in the
real world - 1,2,3, and all that.
>Altho it is an interesting metaphysical question...
That is the purpose of this thread - a place to speculate about such
things.
>There's an easier way to show that the halting problem cannot be solved,
>via reducto ad absurdum.
>Assume you have a function
> boolean PROGRAM_WILL_HALT(program) /* accepts a program, returns true
>if it'll halt,
> and this function always halts */
>
>Write prog2 like this:
> boolean prog2() {
> if (PROGRAM_WILL_HALT(prog2)) {
> while (true) /* infinite loop */ ;
> }
> else {
> return false;
> }
> }
>
>That is, write a program that halts only if its argument doesn't halt,
>and that does not halt if its argument does halt.
>
>What is PROGRAM_WILL_HALT(prog2)? prog2 first checks to see if
>PROGRAM_WILL_HALT thinks prog2 will halt. If so, prog2 loops forever. If
>not, prog2 stops. We've constructed a program that causes
>PROGRAM_WILL_HALT to return the wrong value, based on the fact that we
>assumed PROGRAM_WILL_HALT always returns the right value.
>
>(I might have minor details wrong, but you see how this can work.)
Shades of Godel's Epimenides Paradox - the statement that says that it
cannot be proven true. Here you have the program that proves it cannot
halt but returns a statement that it can.
Deeply involved in all of this is infinite self-reference - recursion
which takes an infinite amount of memory or "space" to work thru.
>No. It's a function whose value cannot be computed without arbitrary
>levels of recursion, and hence cannot be computed with bounded loops and
>no recursion. (I.e., it's a function whose value cannot be computed by
>only using FOR loops, no matter how much you nest them.) Hence, it's a
>function that is impossible to program in a computer language restricted
>to statements that can be proven to always halt. It shows up in a number
>of computational order statistics as G (or inverse of G or something
>like that), when you do things like double the size of a hash table
>every time it fills up and then ask what the expected time of an
>insertion is.
Again, infinite recursion shows up.
>A quick metacrawler search reveals
>http://source.syr.edu/~jdimpson/proj/ack44.html which reveals the
>formula for it without any further explaination of why it's interesting.
I just looked it up. It's a good thing his machine did not know how to
handle segmentation errors gracefully or he might not have figured it
out.
I suppose that is an undocumented feature of Windows. :-)
Bob Knauer
"A man with his heart in his profession imagines and finds
resources where the worthless and lazy despair."
--Frederic the Great, in instructions to his Generals
------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Subject: Re: Visual Basic Cipher
Date: Wed, 20 Jan 1999 19:50:58 GMT
Reply-To: Jim Dunnett
On Tue, 19 Jan 1999 22:10:55 GMT, "Oliver Keeling" <[EMAIL PROTECTED]> wrote:
>do while not eof(1)
>
>leads to problems!!
That seems suspect. Surely it should be:
while not eof(1):<body of loop>:wend
The 'do' isn't necessary. Try taking it out.
--
Regards, Jim. | We mustn't downgrade the Royal Opera House.
olympus%jimdee.prestel.co.uk | I don't want to sit next to someone in a
dynastic%cwcom.net | singlet, shorts and a smelly pair of
nordland%aol.com | trainers.
marula%zdnetmail.com | - Colin Southgate, incoming chairman.
Pgp key: wwwkeys.uk.pgp.net:11371
------------------------------
From: [EMAIL PROTECTED]
Subject: Help. Protocol feasibility advice needed
Date: Wed, 20 Jan 1999 20:46:21 GMT
Here's my problem. In a client/server implementation, I need to send x and
f(x) to the client. Assume that the server does not have the computational
power of the clients involved. Assuming I can successfully fend off all
other attacks, I need to keep f(x) secure somehow against an attack involving
decompiling of the client program and passive listening of data sent and
received on the client's port(s). I figure it boils down to me trying to
share a secret with someone who's going to give it away and thus is
impossible, but I've done an RSA secure chat program and now am reading
Schneier's [exemplary] book and am getting kinda wary of doubting the
possibilities of encryption protocols and algorithms. So, maybe it can come
down to some sort of dynamic encryption which is infeasible to attack.
Trying to develop a protocol... looking for insights. Thanks in advance.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "John Feth" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: 20 Jan 1999 20:58:57 GMT
R. Knauer <[EMAIL PROTECTED]> wrote in article
<[EMAIL PROTECTED]>...
<Snip>
Bob,
Numbers do not change state between random and "special"--a random string
is a random string and will always be a random string. If you dragged your
random string out of obscurity to use it, it remains random, but not
obscure.
By the way, while there are infinitely many different random strings, every
electron, such as those you describe in the slit experiment is identical,
and because all electrons are identical, there is no such thing as a
"random electron".
Regards,
John Feth
> What I am trying to get across is that is appears (and this is only a
> speculation on my part) that once a random number K is used in an
> encryption operation, it loses its randomness because then it becomes
> unique in the context of that operation.
>
> There is only one key possible that will reproduce the message, and
> that makes K unique, not random since it is no longer just one of the
> possible outputs from a TRNG. Only the key K can do that, and that
> makes it special, not random.
>
> The fact that you may not know what K is, is not a measure of
> randomness but a measure of obscurity. And we all know that obsurity
> has nothing to do with true randomness per se - although obscurity is
> confused with randomness all the time.
>
> Before K is used to encrypt the message, it is totally random - it can
> be any sequence out of a pool of equiprobable sequences of given
> length. But once you use it to form the ciphertext, it loses that
> characteristic of randomness by virtue of its uniqueness in the new
> context in which it has become entangled. And when the inverse
> operation of decryption takes place, it is returned to the pool of
> random numbers, because it is no longer entangled in any context.
>
> As an analogy consider a beam of free electrons which passes thru one
> of the slits of a double slit experiment. Once it passes thru a slit,
> it is no longer just "any random electron", but is a very unique
> electron by virtue of the fact that it will impinge on an exact place
> on the screen behind the slits.
>
> Because it has interacted with the double slit system, it has lost its
> original randomness and has become unique in terms of its
> wavefunction. Physicists call that the collapse of the wavevector due
> to the particular electron's entanglement with the apparatus. If the
> electron had not become entangled in such manner, it would not form
> the characteristic interference pattern.
>
> Call that "silly" if you must for personal reasons, but I maintain for
> purposes of discussion that there is an element of truth contained in
> my speculation. How much truth and whether that truth is of any
> signifcance is up for comments - preferably ones that are more
> intelligent than just "silly" name calling.
>
> Bob Knauer
>
> "Whatever you can do, or dream you can, begin it. Boldness has
> genius, power and magic in it."
> --Goethe
>
>
------------------------------
Date: Wed, 20 Jan 1999 16:11:26 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Patrick Juola wrote:
> Randomness is what's left after you throw
> out everything non-random.
There's a strong definitional similarity between random numbers and irrational
numbers. Both are defined in the negative sense; what's left after you throw
away the regular stuff. Further, the succinct description of an irrational as a
"non-repeating fraction" has an analogue wherein a random number contains no
pattern (correlation).
The statistical definition of the *generation process* for random numbers,
selection from a pool of equal probabilities, has no analogue for irrationals
that I can spot. Is this just empty sophistry or is there something I'm not
seeing?
------------------------------
Date: Wed, 20 Jan 1999 16:22:05 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
This is getting off topic, but in searching for the "root of randomness" you may want
to
follow up some concepts from the late '70s in which (then) modern cosmology was recast
by
a theorist (whose name I am searching for) into a theory of interaction events in which
the only exchange was that of information. The reformulation had a number of
interesting
insights and provided simplification of (then) modern particle theory.
One of the most interesting aspects of "cosmological information theory", for want of
the
original name, was that, like all predictive theories, it contained a number of
critical
constants. The entrancing aspect was that all the constants could be taken as one (1).
I don't think the theory went very far. It may be one of those things we cannot
appreciate for another 100 years.
R. Knauer wrote:
> On Wed, 20 Jan 1999 12:32:32 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >OK then. On those grounds, let it be known that in my insufficiently humble opinion
> >there is a negative amount of truth in your conclusion.
>
> Oh, but that is a certainty, because I am not an Expert. Only Experts
> have the enormous burden of having to be correct all the time.
> Non-experts like me can be wrong and it won't ruin our day.
>
> BTW, I happened to be reading a particular part of that book I have
> cited several times ("Fire In The Mind"), and it just so happens that
> the passage is focused on how randomness in Quantum Mechanics is
> "dissipated" by the environment - which is one physicist's theory of
> how one goes from the quantum realm to the classical realm.
>
> It starts on page 161 and goes like this:
>
> +++++
> "If we follow the approach of some of the people at Santa Fe and Los
> Alamos and admit information as another fundamental, along with mass
> and energy, then quantum theory can be viewed in a subtly different
> light. All that is required to break the symmetry of the wave function
> is information processing. Not only are conscious observers
> superfluous - the theory does not even require artifical observers
> like photographic emulsions or photoelectric cells. The universe
> itself might process information just as it processes matter and
> energy.
>
> [...]
>
> "At Los Alamos, [Wojciech] Zurek and some of his colleagues have been
> examining the difference between quantum and classical measurements in
> an attempt to better understand how we come to know the world. The
> trick, they say, is to follow the information. Where does it go when
> we make a quantum measurement? In addition to its static attributes -
> mass, spin, that which makes it an electron, a photon, or whatever - a
> quantum particle carries this huge complex of dynamic information: the
> wave function describing every possible state, and every possible
> combination of states, that it might assume. When it is measured and
> takes on one of these states, to the exclusion of all others, what
> happens to the extra information? Does it dissipate into the
> environment in an irreversible act of erasure?"
> +++++
>
> The writer goes on to discuss that part of this theory in which
> collapse of the wavefunction is directly related to the loss of all
> that information carried around by quantum particles. That information
> is lost to the environment, and it is this continual loss of
> information which causes the Classical Universe to be what it is.
>
> So - speculating on the disappearance of randomness in a key when it
> is used to encrypt a message is not quite as "silly" as it may seem at
> first glance, at least if you want to speculate on the the ultimate
> roots of randomness in the physical world. After all, it is that very
> random character of such physical processes that are required to make
> a TRNG work properly - so there is some king of tie-in somewhere.
>
> Maybe.
>
> Bob Knauer
>
> "A man with his heart in his profession imagines and finds
> resources where the worthless and lazy despair."
> --Frederic the Great, in instructions to his Generals
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Wed, 20 Jan 1999 20:34:33 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 20 Jan 1999 19:21:23 GMT, Darren New <[EMAIL PROTECTED]>
wrote:
>(Of course, I'm of the opinion that the mathematics of finite stuff is
>"computer science",
You obviously don't work with Windows.
>which is anything but boring... :-)
On the other hand, maybe you do work with Windows.
>Godel says that given a sufficiently powerful formal system X, there are
>two strings S and ~S, and no matter how many rules from X you apply,
>you'll reach neither S nor ~S. That doesn't mean that the rules of X are
>hazy, random, or indeterminent. It just means that there's no
>combination of the rules that will generate S or ~S. Note also that the
>proof, as I understand it, relies on an interpretation of the meaning of
>S outside of the formal system; however, formal systems don't ascribe
>meaning to their theorems.
Yeah, it depends on our appreciation of the fact that a proposition,
like the Godel statement, cannot be expected to be proved. I mean, how
can you prove a statement that reads: "This proposition is
unproveable"? Or "This proposition is not part of this formal system"?
Chaitin shows that one cannot prove the randomness of a number of
complexity N with a formal system that is less complex than N.
>You can't. I didn't say you could. The machine behaves completely
>deterministically.
Then it would seem that determinism is not a significant property of
this kind of randomness.
>Well, *I* understand what *my* confusion was, and that was the
>uninutitive and/or sloppy use of the term "random" in some of the posts.
>(Unintuitive when "random" was used as Chaitin defines it, and sloppy
>when applied to the behavior of a turing machine.)
Chaitin defines what he means by random in clear unequivocal terms. He
even gives a calculation to show whether a number is random in his
theory, and how many of them you can expect for a given complexity
cutoff.
I believe you joined us after that preliminary definition had been
laid down in another thread, before this thread was begun.
Bob Knauer
"A man with his heart in his profession imagines and finds
resources where the worthless and lazy despair."
--Frederic the Great, in instructions to his Generals
------------------------------
From: "David Rex" <[EMAIL PROTECTED]>
Subject: Scramdisk-Question
Date: Wed, 20 Jan 1999 14:59:49 -0700
There was mention of a dos version of the executable for this program, I'm
experimenting with the Windows version now.
1. Is there a DOS version, and where should I look for it (tried a search,
could only find windows version)
2. Will the two versions work together?
FYI I'm usion version 202g (sdisk202g.exe)
Thanks
------------------------------
From: "Mike DeTuri" <[EMAIL PROTECTED]>
Subject: Amateur/Newbie question...
Date: Wed, 20 Jan 1999 21:36:54 GMT
I used the random C sources that George Marsaglia posted a few weeks back to
create a stream cipher. (See "Random numbers in C: Some suggestions.")
First, I set up a CipherSaber type initialization vector (10 bytes of
nonsecret data that changes with each encryption) and appended it to the
user's passphrase to create the key. Then I filled the array t[256] with
repeating values of the key, just like I would if I was using RC4 or
CipherSaber.
The array t[256] seeds the LFIB4 and SWB generators. I used the output from
the LFIB4 and/or SWB PRNGs to initilize/reset the variables z, w, jsr, and
jcong, which are required by the generators that make up the KISS generator
(MWC, CONG, and SHR3). Then I take the output from KISS mod 256 and XOR
with a byte of plaintext to produce ciphertext.
Is it really this easy? Am I doing something wrong? Is there an easy way
to analyze my results?
Thanks in advance,
Mike
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
