Cryptography-Digest Digest #373, Volume #9 Sun, 11 Apr 99 10:13:06 EDT
Contents:
Re: True Randomness & The Law Of Large Numbers ("Franzen")
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: tops9720.zip source code for "Topsecret" (Peter Gunn)
----------------------------------------------------------------------------
From: "Franzen" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 11 Apr 1999 02:31:10 -0500
On Sat, 10 Apr 1999 04:43:53 -0500, "Franzen" <[EMAIL PROTECTED]>
wrote:
>>I do a fair coin toss one million times in a row and record the results. I
>>end up with 500,367 heads. Repeating the same process once more, I end up
>>with exactly 500,000 heads.
>>
>>According to your definition, is either of these two results biased?
1-bit,
>>2-bits, etc?
Bob Knauer <[EMAIL PROTECTED]> replied Saturday, April 10, 1999
at 9:55 AM:
>Bias is the condition in which one bit groups are not evenly
>distributed. Thus, if there is not an equal number of 1s as 0s, then
>there is 1-bit bias. If there is not an equal number of 2-bit groups,
>then there is 2-bit bias.
>
>In the case cited above the first string exhibits 1-bit bias, and the
>second does not. Those 2 strings may or may not be representative of
>the uniform Bernoulli process which generated them, therefore your
>assumption of a "fair" (uniform) coin toss is not confirmed.
Thank you. I wanted to be sure I understood your concept of bias before
continuing. I think if we can resolve the issue of bias, we can affirm or
deny the chi-square concept. If chi-square is a valid concept, I think we
can then come to a reasonable conclusion about infinite uniform random
distribution.
First of all let me correct a small error in the first sequence I gave you.
It is 500,335 heads. I transposed a chi-square .45 sum to .54 in my head.
Good old expected value (EV) is misnamed. I think it shoud be named
something
like "reference value" or "theoretical value." When I begin tossing the coin
I expect my actual head count at one million tosses to be almost anything
but
exactly 500,000.
My most expected head count is 500,335, or its complement 499,665. These two
counts are the minimum bias results possible. Every actual result from one
million tosses which is less than, or more than, these two counts is
increasingly biased as the actual results move away from these two most
expected head counts.
Exactly 500,000 heads is a very unexpected and improbable result. It would
probably cause you and I to be suspicious about the coin tossing environment
and/or the recording of the individual toss results.
More to our discussion here, I would describe exactly 500,000 heads as a
very 1-bit biased result. This is opposite how you currently describe 1-bit
bias.
I will await your comments before continuing.
---
Douglas McLean
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 11 Apr 1999 10:00:16 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 11 Apr 1999 02:46:34 GMT, Dave Knapp <[EMAIL PROTECTED]> wrote:
>It is indeed your description, and NOT a consensus here.
That specification for a crypto-grade TRNG is not mine - it was and
still remains the prevailing consensus from numerous (over 1,000
posts) from 1 1/2 years ago plus input from recent discussions.
You and others have had ample opportunity to give you comments as that
specification has been states and restated many times here recently.
I notice that you cannot offer any improvements, only broad
allegations which you do not substantiate. If you have a better
specification, then see if you can get a consensus.
For example, to date no one has seriously defended the uniform
Bernoulli process although it has been suggested as a model for a
TRNG, and is implicitly references in the form of the "fair coin
toss". I suspect that is because people know that it is impossible to
build a classical device which has p = q = 1/2. Anything other than
that and you do not have a UBP, which means you cannot meet the TRNG
specification.
A quantum computer, on the other hand, promises to calculate true
random numbers when programmed to do so. I have given that as the
model, and I await its development into an actual operating device. In
the meantime, a radioactive TRNG with no deadtime effects is the
closest device I can conceieve of which meets the TRNG specification
without making any assumptions. Others have suggested reverse diode
noise, and that may also be a source of quantum randomness.
>As I recall, a few months ago you were trying to ram this definition
>down the throat of whoever would listen, and there were _many_
>objections to your "definition" of true randomness.
You are completely full of it. If anything, there was a recent
modification that Patrick Juola (an original contributor to the
prevailing consensus) recommended.
>By the way, quantum-mechanical randomness is not "true randomness" by
>your defintion, since most quantum-mechanical distributions are not
>flat.
I never said that ALL quantum mechanical processes were truly random.
I have always referred to the book on quantum computing by Williams &
Clearwater, in particular the chapter entitled "True Randomness".
They discuss the quantum algorithm for calculating true randomness.
Our meaning of the term here on sci.crypt is that a TRNG is suitable
for proveably secure crypto, which does require a flat distribution.
>You don't do your case much good by lying about what other people say.
You are the liar, not me. I have the archives to prove my case. All
you have is delusions from which to fabricate your comments.
It is interesting to note that you have made absolutely no
contributions here. You don't even understand the concept of classical
correlation. All you do is bitch and whine like some twit. Why not go
for something more suitable to you, like cipherpunks.
Bob Knauer
"I am making this trip to Africa because Washington is an international
city, just like Tokyo, Nigeria or Israel. As mayor, I am an international
symbol. Can you deny that to Africa?"
- Marion Barry, Mayor of Washington DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 11 Apr 1999 10:11:30 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 11 Apr 1999 02:31:10 -0500, "Franzen" <[EMAIL PROTECTED]>
wrote:
>My most expected head count is 500,335, or its complement 499,665.
Most expected head count is 500,000.
>These two
>counts are the minimum bias results possible.
The minimum 1-bit bias is present in exactly 500,000 heads - in fact
the is exactly zero since the number of heads and the number of tails
is exactly the same.
>Every actual result from one
>million tosses which is less than, or more than, these two counts is
>increasingly biased as the actual results move away from these two most
>expected head counts.
Bit bias is a property of the sequence. It is the difference between
the number of heads versus tails.
>Exactly 500,000 heads is a very unexpected and improbable result.
But it is more expected than any other combination of heads and tails.
That comes from the binomial distribution for p = q = 1/2.
>It would
>probably cause you and I to be suspicious about the coin tossing environment
>and/or the recording of the individual toss results.
The assumption is that p = q = 1/2, that is, the coin toss is a "fair"
one - a uniform Bernoulli process. Of course, if p != 1/2, then there
will definitely be bias present. In fact, for n tosses, the expected
result is np heads if the probability for heads is p.
>More to our discussion here, I would describe exactly 500,000 heads as a
>very 1-bit biased result. This is opposite how you currently describe 1-bit
>bias.
I describe 1-bit bias the way most people describe it. You must be
working with a different meaning from the conventional one.
Bob Knauer
"The contagious people of Washington have stood firm against
diversity during this long period of increment weather."
- Marion Barry, Mayor of Washington DC
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 11 Apr 1999 12:36:54 GMT
Franzen wrote:
> Exactly 500,000 heads is a very unexpected and improbable result.
So is exactly 500,335; in fact, slightly more improbable.
The only especially suspicious thing about 500,000 is that it can
also be explained by fakery (since a person would "know" that
that was the "expected" result), or by systematic bias, e.g.
010101010101..., or by some other decidedly "nonrandom" process.
There have in fact been published results of supposedly
scientific experiments that agreed "too well" with the results
expected by some theory, e.g. in genetics, and that have later
been demonstrated to have been faked, consciously or unconsciously.
The main reason behind "double blind" experimental design is to
eliminate such effects.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 11 Apr 1999 12:29:08 GMT
"R. Knauer" wrote:
> On Sun, 11 Apr 1999 02:46:34 GMT, Dave Knapp <[EMAIL PROTECTED]> wrote:
> >It is indeed your description, and NOT a consensus here.
> That specification for a crypto-grade TRNG is not mine - it was and
> still remains the prevailing consensus from numerous (over 1,000
> posts) from 1 1/2 years ago plus input from recent discussions.
If it is a "consensus", then it's an uninformed one, since the
definition you gave was of an unrealizable system.
But it's *not* a consensus, according to the primary dictionary
definition: "consensus: agreement in opinion, testimony, or belief".
If you think that there is agreement on your "specification",
you haven't been paying attention, *especially* to recent discussions.
> I notice that you cannot offer any improvements, only broad
> allegations which you do not substantiate. If you have a better
> specification, then see if you can get a consensus.
How can a meaningless notion receive a better specification?
There have been several attempts to patch up the definition
of "TRNG" to give it meaning, but you haven't agreed with them.
The one constant in your notion seems to be that a "TRNG" is
whatever results from some implementation suggested by Williams
& Clearwater. You keep claiming that it would have some
property different from other kinds of RNG (which you mislabel
"PRNG"), but have resisted every attempt to pin down what such a
property might actually *be*. That smacks of mysticism.
> For example, to date no one has seriously defended the uniform
> Bernoulli process although it has been suggested as a model for a
> TRNG, and is implicitly references in the form of the "fair coin
> toss". I suspect that is because people know that it is impossible to
> build a classical device which has p = q = 1/2. Anything other than
> that and you do not have a UBP, which means you cannot meet the TRNG
> specification.
To the contrary, the UBP was one of the suggested meaningful
formulations (models) for what "TRNG" might denote. Whether
one can actually construct a TRNG is a separate question from
what is *meant* by "TRNG". Certainly, if one can show that
the "meaning" is such as to imply nonexistence, that would be
a fatal flaw, as with the definition you gave in terms of
uniform distribution over all integers. However, it is
actually not terribly hard to approximate ideal coin flips so
closely that no tests are able to tell the difference. The
thermal-noise based random bit generators on some commercial
crypto chips do this already.
> ... Others have suggested reverse diode
> noise, and that may also be a source of quantum randomness.
Reverse diode noise is a classical thermal, not quantum, effect.
exp(-kT) and all that.
> Why not go for something more suitable to you, like cipherpunks.
You certainly have no business suggesting that to people who
are more capable of making a positive contribution than you.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 11 Apr 1999 13:53:34 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 11 Apr 1999 12:29:08 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>If it is a "consensus", then it's an uninformed one, since the
>definition you gave was of an unrealizable system.
It was synthesized from the prevailing consensus of experts here on
sci.crypt. And it was never intended to be anything other than a
specification. It was not intended to be either a model or an actual
implementation. It is the specification for a flat distribution of
finite integers, which is necessary and sufficient for the purposes of
providing a keystream for the proveably secure OTP cryptosystem.
You have completely mis-characterized me in order to fluff your own
feathers in front of everyone. I am like a writer who tries to gather
material for a book by interviewing the experts and coming to some
kind of consensus understanding which I then put in my book.
Imagine that I was writing a book about Round Objects. I would ask the
experts on Roundness what were the characteristics of Roundness. I
would then propose a synthesis that Roundness has to do an
idealization known as the True Roundness Generator which meets the
following specification:
+++++
A True Roundness Generator (TRG) is a process which generates an
object whose surface is equidistant from a single point called the
Center.
+++++
I would also try to find examples of a TRG in the real world, and
would undoubtedly propose a lathe as such a device, and possibly a
Numerically Controlled Machine Tool as another example.
And for this you would fault me. Shame on you. You are a fake.
>But it's *not* a consensus, according to the primary dictionary
>definition: "consensus: agreement in opinion, testimony, or belief".
And that is exactly what happened in our lengthy discussions of 1 1/2
years ago. We came to a consensus, which was the prevailing opinion of
the experts. I fine tuned the specification recently at the suggestion
of one of the posters, which resulted in even a more general
specification.
>If you think that there is agreement on your "specification",
>you haven't been paying attention, *especially* to recent discussions.
I have been paying close attention, so much so that I have been
challenging every assertion which runs counter to the notion of a TRNG
as we have formulated it for the purposes of proveably secure crypto
in the OTP system.
It is you who has not paid attention, and that is why you always get
it wrong - like you are getting it wrong right here and now.
>How can a meaningless notion receive a better specification?
The specification for the TRNG is a specification for a flat
distribution, which has its roots in the proveable security of the OTP
cryptosystem. It is precisely because the distribution of keys is
completely flat that the cryptanalyst cannot know which key is being
used in a particular cipher. He can never know (unless he acquires the
key or it is used more than once) because it is formally unknowable.
>There have been several attempts to patch up the definition
>of "TRNG" to give it meaning, but you haven't agreed with them.
There have not been "several" anything proposed here. And the TRNG
specification does not need "patching up". It is a specification for a
flat distribution which is the necessary and sufficient specification
for proveably secure classical crypto.
>The one constant in your notion seems to be that a "TRNG" is
>whatever results from some implementation suggested by Williams
>& Clearwater.
I stated that a quantum computer programmed to calculate true random
numbers is an exact implementation of a TRNG. All other realizations,
even the radioactive TRNG, are not proveably truly random.
>You keep claiming that it would have some
>property different from other kinds of RNG (which you mislabel
>"PRNG"),
I did no such thing. If I use the term "PRNG", then I use it correctly
to signify a deterministic process. Not all deterministic processes
are computer algorithms. Classical physical processes are also
deterministic.
>but have resisted every attempt to pin down what such a
>property might actually *be*. That smacks of mysticism.
That is utter toss.
If anything, it is you who speaks like a mystic instead of like a
person who practices Western Science.
I have stated in completely unequivocal terms that the property which
guarantees true randomness is Quantum Indeterminism. I have stated
that on so many occasions that if you were to query the archives for
sci.crypt using my email address and the word "quantum" as the
keywords you would find:
+++++
Search Results ...about 3200 matches for search
[EMAIL PROTECTED] quantum
+++++
Of course, not all of those are of my origination, since replies to my
posts are also counted if they contain those keywords. But that is how
much activity on sci.crypt has been generated by me in which the
keyword "quantum" has been involved.
The point is that I have stated innumerable times that quantum
indeterminism is the cause of true randomness, or is it the other way
around? We have a chicken-egg issue there which is outside the bounds
for discussion here. Suffice it to say for purposes of crypto that
true randomness is a consequence of quantum indeterminism.
>To the contrary, the UBP was one of the suggested meaningful
>formulations (models) for what "TRNG" might denote.
I just said that. Read my exact words, which are verbatim with my
original post:
+++++
For example, to date no one has seriously defended the uniform
Bernoulli process although it has been suggested as a model for a
TRNG, and is implicitly references in the form of the "fair coin
toss". I suspect that is because people know that it is impossible to
build a classical device which has p = q = 1/2. Anything other than
that and you do not have a UBP, which means you cannot meet the TRNG
specification.
+++++
You are not paying attention to what I say. You are reading in what
you want so you can then claim that what I say is incorrect.
That is an extremely dishonest practice on your part intellectually -
to deliberately misread simple English sentences in order to play the
role of some big shot "expert".
>Reverse diode noise is a classical thermal, not quantum, effect.
>exp(-kT) and all that.
Reverse diode Shot Noise is quantum in nature. Ever hear of the Fermi
Surface?
>You certainly have no business suggesting that to people who
>are more capable of making a positive contribution than you.
We have seen no positive contributions from either you or that poster.
Claiming that you are "capable" of doing so, but never demonstrating
it in the real world, is a characteristic of mystical thinking - which
is what you and that other poster are doing here.
Bob Knauer
"The contagious people of Washington have stood firm against
diversity during this long period of increment weather."
- Marion Barry, Mayor of Washington DC
------------------------------
From: Peter Gunn <[EMAIL PROTECTED]>
Subject: Re: tops9720.zip source code for "Topsecret"
Date: Sun, 11 Apr 1999 14:11:28 +0100
Ryan Phillips wrote:
> Snakeoil?
Since the sender never stated any claims about what the
prog was supposed to do, other than simply being an
"encryption program", it would be hard to label it as
Snake Oil, well, not high quality Snake Oil anyway.
I think the "encryption" takes place in as follows....
C[i]=I[i]^n^l^K1[n]^K2[n]^O[i]
where C is ciphertext, I is input text,
O is a 'pad' file, l is key length,
n=i%l, K1 is the key, K2[i]==K1[i+1],
K2[l-1]==0.
So, K[n]=K1[n]^K2[n]^n, O[i] can be
dropped since its intended to be used
for every encryption (its not a
One Time Pad)... so, after XORing with
O...
C[i]=I[i]^K[i%l]^l
Now, this could be a One Time Pad, as
long as l is less than the size of I
(the key is bigger than the input file),
and from the prog l is 0..63 so, I
doubt this is the intention.
So, I think this can be broken by a
single plaintext attack, so you can
remove I by XORing, then...
C[i]=K[i%l]^l
So, no, I dont think this is Snake Oil,
I think its something cheaper thats been
bottled as snake oil :-)
heehee
PG.
------------------------------
** 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
******************************
