Cryptography-Digest Digest #167, Volume #9 Mon, 1 Mar 99 13:13:03 EST
Contents:
Re: Testing Algorithms (Patrick Juola)
Re: Testing Algorithms [moving off-topic] (Patrick Juola)
Re: Can the quantum computer determine the truth from a lie? (R. Knauer)
Re: compression?security (Somniac)
Re: Testing Algorithms [moving off-topic] (R. Knauer)
Re: My Book "The Unknowable" (Neil Nelson)
Re: True Randomness - DOES NOT EXIST!!! (John Briggs)
Common meaning misconception in IT, was Re: Unicity of English, was Re: New
high-security 56-bit DES: Less-DES ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Testing Algorithms
Date: 1 Mar 1999 09:12:48 -0500
In article <[EMAIL PROTECTED]>, Somniac <[EMAIL PROTECTED]> wrote:
>Herman Rubin wrote:
>>
>> The problem is NOT to produce state changes with extremely low
>> energy; this is not difficult. It is to produce state changes
>> which will not reverse spontaneously or from transient noise.
>> A "permanent" magnet illustrates the situation; it has a large
>> hysteresis loop, which means that most of the energy in changing
>> its state goes off in heat, but this keeps it stable. Computer
>> memory, and also the state of more accessible units, is like this;
>> changeable, but not too easily so. The latter is what is needed
>> to keep it from being lost.
>> --
>Yes, true. And expand upon this wishful thinking about computing 2^256
>answers without heating up the Earth by 99 degrees, consider the Carnot
>Cycle using reversible adiabatic processes. No container has ever been
>built which provides reversible adiabatic processes. Insulators are not
>perfect, so some heat leaks out. Therefore, no one has ever built an
>ideal Carnot engine. In addition, the intake temperature of a heat engine
>must be lower than the exhast temperature.
Yes, but at this point, the question is no longer a physical problem,
but a technological one.
The point, as originally made, was that counting up to 2^256 was impossible
because there did not exist enough energy in the sun/galaxy/universe/whatever
to toggle that many bits DUE TO PHYSICAL LIMITS. This is, demonstrably,
not the case. "Insulators are not perfect,... therefore no one has ever
built an ideal Carnot engine." However, and let me stress this, I have
no reason to believe -- and every reason to disbelieve -- that current
insulator technology represents the acme above which science and
civilization will never rise.
>To make 2^256 calculations, there is not present device which can
>succeed. Future developments cannot relied upon to create perpetual
>motion computers that have reversible adders, nand gates, and memory. The
>past shows that most inventions failed to become practical.
... and I submit that this is exactly the sort of short-sighted thinking
(exactly along the lines of "we've hit the ultimate limit of the photo-
lithographic process") that results in failed predictions. You
claim that technology "cannot be relied upon" to produce these kinds of
devices -- but the conclusion that you wish to draw from that statement
is that it can be relied upon NOT to produce these devices.
Which I firmly believe is an untenable position.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Testing Algorithms [moving off-topic]
Date: 1 Mar 1999 09:15:50 -0500
In article <[EMAIL PROTECTED]>,
Darren New <[EMAIL PROTECTED]> wrote:
>> > > > Think of it this way -- what's the minimum amount of energy necessary
>> > > > to move a brick five feet (horizontally)?
>> >
>> > One photon?
>>
>> A photon of what energy? Are we talking gamma rays or radio waves?
>
>My point is that if your key is 2^300 long, there are fewer than 2^300
>photons in the universe, regardless of the energy involved.
Yes, but if you get your photon back at the end of the process, you
can use it over and over again.
-kitten
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Crossposted-To: alt.privacy,talk.politics.crypto
Subject: Re: Can the quantum computer determine the truth from a lie?
Date: Mon, 01 Mar 1999 13:49:36 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 1 Mar 1999 10:32:44 +0000 (GMT), [EMAIL PROTECTED]
(Paul Kinsler) wrote:
>There is nothing "spooky" or questionable about the theoretical basis
>of quantum computing.
There is when you start talking about a QC that uses quantum
entanglement, like in teleporation, quantum compression and superdense
codes.
Those "ebits" (entanglement bits) are very spooky indeed.
Bob Knauer
"If you want to build a robust universe, one that will never go wrong, then
you don't want to build it like a clock, for the smallest bit of grit will
cause it to go awry. However, if things at the base are utterly random, nothing
can make them more disordered. Complete randomness at the heart of things is the
most stable situation imaginable - a divinely clever way to build a universe."
-- Heinz Pagels
------------------------------
From: Somniac <[EMAIL PROTECTED]>
Subject: Re: compression?security
Date: Mon, 01 Mar 1999 08:12:02 -1000
alex wrote:
>
> Hi,
> Can any experts tell me that what is the relationship between dat
> compression and data security? I am new in security and so where can I
> pick up some basic materia?
> Thanks
Compression does not provide enough security to be safe from educated
cryptanalysts. But it can provide a small amount of security if you know
that your adversary is only one uneducated person. For example, maybe you
do not want your father to read you messages on a home computer that both
of you share. Then if you compress the messages, store the decompression
program on a floppy disk that you hide in your school locker, then it may
be safe. You may know that your father does not know about compression
software, and so, you can feel secure that your known adversary does not
have the technical knowledge to crack the code.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Testing Algorithms [moving off-topic]
Date: Mon, 01 Mar 1999 16:21:04 GMT
Reply-To: [EMAIL PROTECTED]
On 1 Mar 1999 08:55:09 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>Good answer. Now, the *next* question -- what's the minimum energy
>of a photon?
The zero point energy, namely 1/2 h_bar omega.
Bob Knauer
"There is much to be said in favour of modern journalism. By giving us the opinions
of the uneducated, it keeps us in touch with the ignorance of the community."
--Oscar Wilde
------------------------------
From: Neil Nelson <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.physics,sci.logic
Subject: Re: My Book "The Unknowable"
Date: Mon, 01 Mar 1999 16:26:44 GMT
In article <[EMAIL PROTECTED]>,
Neil Nelson wrote:
> On _true_ randomness, mathematically, randomness is only with
> respect to some non-random viewpoint; it says something _appears_
> random as against saying something _is_ random. _True_ or pure
> randomness does not have an identifying procedure because there
> would be no non-random vantage point from which to make sense of
> anything at all including any randomness. _True_ randomness is an
> incoherent, self contradictory notion by definition. Those two
> words can be combined but no definite sense can be made of them.
Bob Knauer wrote:
[ If you try to describe randomness as that which cannot be described,
[ you run afoul of the Berry Paradox. Take your statement above:
[ " _True_ randomness is an incoherent, self contradictory notion by
[ definition."
[ Notice that you have described True Randomness in a paradoxical
[ manner, by the very fact that you described it.
That's right. _True Randomness_ is a self contradictory (paradoxical)
notion.
[[ For example the sequence 101010...10 is not prefix complexity
[[ random, although it is a true random number by virtue of its
[[ generation by a TRNG.
> it needs to be asked in what manner this sequence is used with
> respect to cryptography. It would clearly not be wise to use such a
> string of sufficient length as a bit overlay since the prefix
> complexity is small and that sequence could be easily attacked.
[ Not if it were used in a properly implemented OTP cryptosystem, one
[ that is provably secure.
[ It is one of the strings of the same length as the message, so the
[ attacker cannot decide if the message he detects is the intended
[ message, under the hypothesis that that is the correct key. He
[ needs more information to go on than just the regularity of that
[ keystring.
[ For example, what if there are two intelligible messages:
[ A = "ATTACK AT DAWN"
[ B = "ATTACK AT DUSK"
[ and I XOR them together to get a key K:
[ K = A XOR B.
[ Now I send "cipher" A openly and send the key K by a secure channel.
[ You intercept the cipher A, but not the key.
[ Which message is the intended message? My correspondent will know
[ unambiguously because he has the key.
I am having trouble with this sequence. There is: (1) the message to
be secured, (2) the key sent by a secure channel, and (3) the
encrypted message sent openly. If I needed to run an XOR each time to
get my key that would be the length of my intended message and could
send the key securely, I should just send my message securely and
forget encryption.
Traditionally the sequence would be: A is the message to be encrypted,
B is the key, XOR A and B and send K in the open and B secure. The
correspondent reverses the XOR with B to get A. But as I mentioned
previously if the key (a part of the cryptosystem) is at least as
complex as the message then the message cannot likely not be
decrypted.
[ To make this point even clearer let's say my two messages are
[ identical:
[ A = "ATTACK AT DAWN"
[ B = "ATTACK AT DAWN"
[ Now the key K is:
[ K = A XOR B = 000...0
[ But you don't know that, so you still do not know what my intended
[ message is, not with the scant amount of information I have allowed
[ you to have.
[ Since K can be any sequence, even 000...0, and they are
[ equiprobable, you have nothing to cause you to decide that either A
[ or B is my intended message.
Clearly, if you can send a key the length of the encrypted message
after the message has been encrypted, then the encrypted message is
technically redundant as you have shown. But traditionally, the key
is relatively small with respect to the entire message set used for
that key and the key is sent before any particular messages to be
encrypted are known, making the previous sequence incompatible with
common circumstances.
> Apparently non-random sequences appear randomly in relatively
> complex (relatively random) sequences,
[ How do you know that those sequences are non-random? By your own
[ "definition", you cannot tell if something is random, so you can't
[ tell if it is non-random either.
Non-random is defined as a string that can be completely defined via a
smaller string (prefix code) within a given string generating system
(language). E.g., I could write a sequence of 1000 0's here, which I
will not do as it would interrupt the reader's comprehension, or I
could just say, ``consider a sequence of 1000 0's", which is a much
shorter expression meaning the same thing. One expression is very
long with respect to the other yet they both mean the same thing. The
long expression (the actual 1000 0's) is non-random relative to the
English expression. The English expression is non-random relative to
the language (English) I am using, though it is essentially random
with respect to any other string that will give the same meaning as it
is not expected any shorter expression in English will give the same
meaning.
So initially, there are strings, then a language on strings, and then
a compression of strings using language. The language is defined to
be non-random, incompressible strings are random with respect to the
language, and compressible strings non-random with respect to the
language. Note this is not _true_ randomness but _apparent_
randomness with respect to a language.
[ If you could state that something is non-random because of some
[ necessary and sufficient property, then you could state that
[ something is random because it lacks that necessary and sufficient
[ property. Yet you have stated that randomness is not
[ characterizeable, at least not formally. That Ol' Berry Paradox
[ sure is a bummer, eh.
Randomness (apparent randomness) with respect to a non-random
perspective (a language) is definable, but randomness without a
perspective (true randomness) is not definable except in the self
contradictory manner noted above.
[ Those "non-random" sequences must appear out of necessity. Random
[ numbers must be normal in the Borel sense. Therefore every bit
[ group must be present, even ones that flunk simplistic statistical
[ tests for bias.
[ That means every finite sequence of numbers, even those with highest
[ regularity, like 000...0, must be present in a true random number,
[ even those sequences where the run length of one particular bit is
[ nearly infinite.
First we must define what it is to have a random number, which was
just indicated to be according to a non-random perspective (a
language). If, according to the previous discussion, random means a
string sequence not compressible in the language then a sufficiently
long run of 0's would be compressible and hence that string not random
wherever it might appear.
I welcome the result of Berry's Paradox from the notion of `True
Randomness' and am interested in your definition of `True Randomness'
that avoids a paradox.
Neil Nelson
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: True Randomness - DOES NOT EXIST!!!
Date: 1 Mar 99 11:39:09 -0400
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (R. Knauer)
writes:
> On 26 Feb 99 09:47:25 -0400, [EMAIL PROTECTED] (John Briggs)
> wrote:
>
>>> Oh really? Nothing existed before the Universe, eh.
>
>>Really. Even the phrase "before the Universe" is devoid of meaning.
>
> "Before" in terms of cause and effect, not time per se.
>
> IOW, "before" as "antecedent".
Still devoid of meaning. If it's outside the Universe, it can't affect
something inside the Universe. That's basic to pretty much any definition
of "the Universe".
>>It sounds like you are going for the Francis of Assisi line of bogus
>>logic:
>
>> "For every effect there must be a prior cause"
>
> I did not know that he was the person who enunciated that. I always
> thought it was the Greek philosophers, most notably Aristotle.
>
> And what gives you this pontifical authority to declare that the law
> of cause and effect is "bogus"?
I didn't call the law bogus. I called the line of logic bogus. And it is.
I need no authority to state that opinion. Much less any "pontifical"
authority.
>>Which can then be used to fallaciously derive the existence of a
>>single root causeless cause of everything else -- the prime mover.
>>The Deity. The One.
>
> What gives you this pontifical authority to declare that that
> derivation is "fallacious"?
Fallacy one: Why just one first cause? Why not two? Or three?
Fallacy two: Why not a causal loop?
Fallacy three: Why not infinite regress?
Fallacy four: What causes the first cause?
Looks like a fallacious argument to me.
>>The universe can proceed perfectly well without this "law".
>
> Oh really - the very Universe we observe, eh?
Yes, the very Universe we observe. We see plenty of effects without
any visible cause.
> Well tell us, just how does the Universe contain order if there is no
> cause-effect law in operation? What effective principle is responsible
> for the order that we do observe, if it is not the law of cause and
> effect?
I didn't say that there is no such thing as cause and effect. I said
that the law of cause and effect _WHICH I EXPLICITLY STATED AND WHICH
YOU HAD LEFT COMPLETELY UNSPECIFIED_ was not needed by the Universe.
To re-iterate, that statement was:
>> "For every effect there must be a prior cause"
Now, if you want to loosen up the definition of "cause and effect" to
the point where radioactive decay and quantum fluctuations in the vacuum
have causes then you can make a credible argument in favor of this law.
But then you are left with the question: What causes a TRNG based on
radioactive decay to emit the sequence it does?
John Briggs [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Common meaning misconception in IT, was Re: Unicity of English, was Re: New
high-security 56-bit DES: Less-DES
Date: Mon, 01 Mar 1999 17:54:17 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> > Please see my previous reply a few minutes ago, where I analyze the two
> > messages and show that the first message is much more probable. The fact
that
> > both appear to be in English was puzzling but it is actually neutral since
> > the first is much more English-like. In fact, standard formalism applied to
> > those two messages leads to only one answer, by what seems to be a large
> > safety margin.
>
> You missed the whole point of that exercise.
This is a common misconception in Information Theory analysis: information
versus meaning. Information in Shannon's sense has nothing to do with
meaning. Information is simply that which is transferred from source to
destination. If, before transmission, the information is already present at
the destination, then the transfer is zero. Information is thus that which I
do not expect. It has nothing to do with knowledge or even if it is
meaningful or not.
My point is thus technically correct for Information Theory analysis: given
two messages, choose the one that has the best-possible approximation to
English statistics. This is done by syntax analysis at the lowest level
possible: letter frequency with unigram, digram, trigram, etc,
You are confusing meaning with syntax. Letter-frequency analysis has nothing
to do with meaning. Shannon's theory specifically excludes meaning.
If anyone wants to "read" something else in that example, then that is not
granted by the theory that was invoked behind the example: Shannon's. The
example calls upon unicity in order to define it and uncity is defined by
language statistics not by a savvy human reader.
> Neither message stands a chance of arising in normal English
> conversation;
Reading some mail lists, I beg to disagree ;-)
But, that is besides the point. Again, the example invokes unicity and
Shannon's analysis -- which specifically excludes meaning, and just focuses
on language statistics.
>.they were specifically engineered as the solution
> to a puzzle (find two very long near-English texts that are
> isomorphic under simple substitution).
> In fact, the "right" answer was determined arbitrarily by the
> author of that little essay; it cannot be determined by any
> logical analysis (since the messages are illogical to start with).
>
If a message is "logical" or not this is of no concern to a decryption based
on letter frequency analysis -- since what is not "logical" to you may be to
the intended recipient. The ONLY point that mattters in a letter frequency
attack is letter frequency, of course.
Yes, you can also then later on try to interpret the message -- but that is
outside the scope of a letter-frequency attack based on knwon language
statistical structure and may even revise it, but only afterwards -- not
before ;-)
Cheers,
Ed Gerck
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
