Cryptography-Digest Digest #379, Volume #9 Mon, 12 Apr 99 15:13:03 EDT
Contents:
Re: LFSR polynomial testing ("Douglas A. Gwyn")
Re: Enhanced ECB mode any thoughts ? ("Douglas A. Gwyn")
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: True Randomness & The Law Of Large Numbers (Herman Rubin)
Re: Is public key crypto just Snake Oil?? (Medical Electronics Lab)
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: True Randomness & The Law Of Large Numbers (Herman Rubin)
Identification ([EMAIL PROTECTED])
Re: True Randomness & The Law Of Large Numbers (Herman Rubin)
Re: True Randomness & The Law Of Large Numbers (Herman Rubin)
Re: help in decrypting a message using the playfair cipher (Gallicus)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: LFSR polynomial testing
Date: Mon, 12 Apr 1999 17:07:25 GMT
[EMAIL PROTECTED] wrote:
> ... I was wondering if anyone had a program to test for valid
> LFSR polynomials (LFSRs of any bit length)?
What do you mean by "valid"? Irreducible?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Enhanced ECB mode any thoughts ?
Date: Mon, 12 Apr 1999 16:39:59 GMT
Assuming you're the same David Scott,
I want to thank you for the much improved tone of your postings
to sci.crypt recently.
Best wishes..
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Mon, 12 Apr 1999 17:26:07 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 12 Apr 1999 16:19:08 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>> I'm saying that the test result (pass/fail) is a random variable.
>> As such it has a distribution.
>Excellent point.
Yeah, but what does it have to do with the main issue of this thread?
Nobody has satisfactorily demonstrated that the FIPS-140 Monobit Test
is valid. I remind you of Feller's very words:
"Thus, contrary to widespread belief, the time average for any
individual game has nothing to do with the ensemble average at any
given moment."
Here the term "game" means a true random process like the flip of a
fair coin.
The FIPS-140 Monobit Test is an instance of calculating the time
average, which as you can see clearly from Feller's comment above is
not valid in terms of inferring any characteristic of the ensemble,
such as whether it is a flat distribution.
NB: For those who came in late, the term "time average" used by Feller
means calculating some average property for a particular sequence
generated by a TRNG. IOW, "time" means the number of steps the TRNG
has generated, i.e., the number of bits in the sequence.
Now you two need to stop the silly kissy-poo and get back down to
business. My challenge is clearly stated above - can you meet it head
on?
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: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: 12 Apr 1999 12:23:00 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 10 Apr 1999 10:22:22 -0500, [EMAIL PROTECTED] (Herman
>Rubin) wrote:
>>>a) Random sampling is a necessary condition for the validity of
>>>statistical tests. If the population distribution is not randomly
>>>sampled, then the statistical test is invalid - which means nothing
>>>can be determined from it whether it is passed or it is failed.
>>This is if one is sampling from a finite population.
>That seems to say that you agree with my statement above.
>>One can do statistical testing under any probability model whatever.
>That is an example of the circularity that Kolmogorov pointed out in
>those quotes I have given here from Li & Votanyi:
>+++++
>"In everyday language we call random those phenomena where we cannot
>find a regularity allowing us to predict precisely their results.
>Generally speaking, there is no ground to believe that random
>phenomena should possess any definite probability. Therefore we should
>distinguish between randomness proper (as absence of any regularity)
>and stochastic randomness (which is the subject of probability
>theory). There emerges the problem of finding reasons for the
>applicability of the mathematical theory of probability to the real
>world".
>--A. N. Kolmogorov (as quoted in Li & Vitanyi, p. 52, op. cit.)
>"The frequency concept based on the limiting frequency as the number
>of trials increases to infinity does not contribute anything to
>substantiate the application of the results of probability theory to
>real practical problems where we always have to deal with a finite
>number of trials."
>--A. N. Kolmogorov (as quoted in Li & Vitanyi, p. 55, op. cit.)
>+++++
At that time, quite a few people believed, and quite a few still
do, that one can start with the state of the universe at a particular
time, and using the precise laws of nature, exactly predict what
all of the future, and all of the past, must be.
If one does not believe in physical probability, one does not believe
in physical probability. Einstein claimed, "God does not play dice
with the universe."
>>That government testing standards are what SHOULD be done is not
>>the issue.
>I do not understand what you are driving at.
>All I intended with that statement was to repeat the FIPS-140
>procedure for sampling, not pass judgement on it. We chose FIPS-140 as
>an example of approved statistical testing since no one would come up
>with a test of their own.
I would not accept the stated standards as adequate for statistical
purposes. I want much better randomness that they promise, and
I would test much harder, and I still would not accept the output
of a single device stream, as it is impossible to test it adequately.
Even if a decay source is "perfect", the transcribing device has its
problems, and these are not the problems of dead time.
>Someone mentioned Chi Square once, but never followed up on it after
>repeated requests to do so. What a test for variance has to do with
>true random numbers is a bit obscure, anyway. Best stick with 1-bit
>bias for starters.
The chi squared test was originally a test for the statistical fit of
cell frequencies to theoretical probabilities. This test does not
have exactly the chi squared distribution under the hypothesis, but
does have this distribution asymptotically.
>>>c) The claim of the Monobit Test is that if it is not passed, then the
>>>distribution of bits produced by the TRNG process is determined not to
>>>be random within reasonable certainty. It is that claim which I
>>>challenge.
>>I do not need the test,
>Neither do I, but that is irrelevant. The experts on here swear by
>those tests, so I introduced them to have something to critique.
>Novody else would volunteer a test, so I had to pick one from the
>expert's repertoire.
>>and it is the wrong problem.
>Please clarify what you mean by that, since I think it is the wrong
>testing methodology too.
>>The question is whether it is CLOSE to being a TRNG.
>It is tempting to equate statistical significance with closeness to
>being a TRNG, as if there is some kind of measurement being conducted.
This is the typical misuse of statistics by those who have not had
decent statistical theory. I suspect the statistics book you have
cited conveys the same impression. The term "statistical significance"
should be eliminated from the vocabulary; its meaning is limited
and not relevant to what one is doing.
>We know that there can be no statistical tests that pass judgement on
>how good a TRNG is. The candidate TRNG could pass the tests with a
>99.999% significance and still be a very poor TRNG.
This is correct. What should be done instead is to construct tests
which poor RNGs would fail with high probability. This is not that
hard to do, but forces large sample sizes. A good approximation to
a TRNG (notice that I did not say a TRNG) should pass it with large
probability, and a poor approximation should fail it with large
probability. I do not think this possible for a direct use of a
single generated sequence; the sample size needed would be well
beyond feasibility.
>Testing of a TRNG is not a measurement in the traditional sense.
>Randomness and non-randomness are nominal entities, not real measures
>along an interval.
It is, if one has a long enough sequence, or considers that one
has a poor measurement. But we are not going to get sequences of
length 10^30, or even 10^20. Sequences of 20,000 are too short for
any kind of consideration.
>>>d) The result obtained, namely that the population distribution is not
>>>random within reasonable certainty,
>>What population?
>The population of all sequences in the ensemble.
The "ensemble" is a construct in the absence of a belief in
probability.
>>Populations are only relevant when one is sampling
>>from a finite population.
>The TRNG specification calls for a finite population. That was done
>deliberatelyt to avoid nondiscrete distributions, the kind that lend
>themselves to probability measures.
It does not. It involves a finite sequence. The "population of
sequences" is a purely mathematical construct.
>>Consider probability models instead, and
>>these do not involve such objects, although the term lingers on.
>That requires that you choose a model for the TRNG. What is the model
>you choose? A finite uniform Bernoulli process?
The full model is that there is a joint distribution of the
observations. This model is huge. What one can test for is that
the behavior of the physical process is close to what is wanted,
ASSUMING that it changes slowly, and that long-term dependencies can
be ignored. It is possible to come up with tests which will be very
likely to accept a sequence which is random within an error of .001,
and very likely to fail for a sequence which has an error of .01.
If we then test something like eight sequences produced by different
devices, or the same device at different times, and accept if at
least 5 of them pass, and XOR the sequences to get one sequence, I
would feel rather confident in using that sequence as having the
desired probabilities of a TRNG within about one part in 10^10.
Notice that the tests would consider the probabilities of both
kinds of errors, and use a defined measure of "good" and "bad".
>I have not seen any prevailing consensus for that as the model TRNG
>process. I think most people realize that a fair coin is impossible to
>construct, much less flip in a fair manner.
>>One of the areas of concern in statistics is that of inference from
>>a single realization of a stochastics process.
>I have said that all along: You cannot infer the properties of a TRNG
>from a single instance of the TRNG output. Nor can you for an
>infinitesimally small sample of outputs compared to the size of the
>ensemble of all possible sequences.
The ensemble does not exist, except as a mathematical model. You
will only get one sequence under given conditions.
>Are you agreeing with me?
No. The law of large numbers is meaningful, but frequency
interpretations of probability are inadequate.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Is public key crypto just Snake Oil??
Date: Mon, 12 Apr 1999 12:34:25 -0500
Peter Gunn wrote:
> Anyways, the problem is simple... you can only verify a signature
> from someone who you're not familiar with by checking with some
> trusted authority to make sure the public key is owned by whoever
> claims to be the author, and not a person-in-the-middle.
>
> If this is the case, wouldnt it be simpler to have a traditional
> username/password account with the trusted authority, and
> send them the hash for a document you want to sign, and
> have them return a signature of the hash encrypted using
> some 'private key' unknown even to you. Similarly, people
> could verify the signatures by simply sending off the signature
> and your username, and receive the hash for the document
> which they could then check.
But that opens up a whole 'nother can of worms (better drink some
more beer :-) A much simpler solution is to check the public
key "out of band". If you really want to be sure you have the
right connection with nothing in the middle you only have to be
sure the public key they send you is correct. You can use phone
lines, snail-mail, radio links, and any other "channel" you can
think of.
This is the point of the PGP "finger print". It can be published
in many places, not all on the net. As long as the public key
you get creates the same finger print published by the person you
get the key from, you know it's legit.
So, to avoid the person in the middle attack, you need to verify
the key you got was from the person who claims to have sent it.
If it's really important to all sides, it makes sense to publish
"finger prints" in newspaper ads or call them on the phone or have
them send you the key via floppy in the mail, or all of that!
The more you dig into this, the more you realize that doing things
over the net isn't that much different from doing things face to
face. How do you know the next person you meet isn't a con artist?
Who do you trust and why?
In the real world, the person in the middle attack is an expensive
proposition. There are good reasons to worry about it if you
are doing something "interesting". If you are paranoid, you need
to do some extra work to make sure you connect with who you want
to. If it isn't that important, chances are your normal instincts
will tell you there's something wrong.
Public key crypto is really useful. Just use it with care.
Like everything else (don't drink too much beer!) :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Mon, 12 Apr 1999 16:38:28 GMT
"R. Knauer" wrote:
> On Sun, 11 Apr 1999 20:42:42 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
> wrote:
> >Perhaps because it had nothing to do with "normality".
> Oh, really.
Yes. Your dismissal of the use of Pearson's chi-square statistic
on the basis of it depending on an assumption of normality is not
founded in reality.
> >Pearson's chi-square statistic measures the difference between
> >observations and theoretical predictions, with no assumption
> >about the underlying distribution.
> According to Triola many statistical tests presumably have nothing to
> do with the underlying distribution. You have said nothing that we did
> not already know.
But you were incorrectly tying Pearson's chi-square statistic to
the assumption of normality, which is a distributional constraint.
> > It is closed related to
> >Friedman's "index of coincidence". Pearson's chi-square doesn't
> >work too well when there are fewer than about five observations
> >in a category, but Kullback's information statistic does, and
> >twice that statistic has asymptotically a chi-square distribution
> >(not the same as Pearson's statistic) with the same number of d.f.,
> >which means that it can be related to confidence or significance.
> >I mentioned Pearson's chi-square statistic instead of Kullback's
> >merely because it is much better known, being taught in nearly
> >every course that discusses data fitting.
> You said that Triola was the definitve reference work. Have you
> changed your mind?
I never said any such thing. I suggested that you study Triola
in order to learn basic statistics before making pronouncements
about the field. That's because the edition I am familiar with
is an acceptably good textbook for introductory statistics.
There is a big difference between a good textbook and a
"definitive reference work". (I doubt that any "definitive
reference work" exists for statistics, a field which still
has much research activity.)
It's about the same difference as between learning a subject
and learning what (you think) experts think about the subject.
If you don't know the subject yourself, you cannot (in most
cases) correctly interpret what experts have to say about it.
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: 12 Apr 1999 13:16:41 -0500
In article <7eqmn2$794$[EMAIL PROTECTED]>, Franzen <[EMAIL PROTECTED]> wrote:
>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.
>Bob Knauer <[EMAIL PROTECTED]> replied Sunday, April 11, 1999
>at 5:11 AM:
>>Most expected head count is 500,000.
>Well, you said it out loud. Let us see if you can live with your
>assertion.
The most likely number of heads is 500,000, assuming that the
number has a binomial distribution with p = .5 and n = 1,000,000.
By itself, this tells us little, but the proof only involves
high school algebra.
>1. I refer you to a chi-square table in any standard math reference.
>Go to the 0.5 probability column in the middle of that table. Do you
>see a zero chi-square sum anywhere in that column. My table starts
>with .45 at one degree of freedom, and the listed sums increase with
>each added degree of freedom.
I do not know if the table has cumulative probabilities or tail
probabilities. If it has tail probabilities (probability headers
going to 0), then the column which would have all 0's would have
1.0 as the header.
>You do know how to calculate chi-square sums? The sum of
>((Achieved heads - EV heads)^2)/EV heads. You are saying (and
>someone else seems to agree with you at the moment) 2*
>(((500,000 - 500,000)^2)/500,000) = (0.225 + 0.225).
I see the value as zero. However, the chi squared test does
not have exactly the chi squared distribution; it is an
approximation.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: [EMAIL PROTECTED]
Subject: Identification
Date: Mon, 12 Apr 1999 18:11:35 GMT
I was wondering two things a) is this a good idea, and b) has this (will
define this in a bit), been done before?
(it's for knowledge based identification on insecure mediums)
...
My idea (well maybe someone has done this before?) for a knowledge-based
identification system is,
Bob and Alice both pick a LFSR register state (say 127 bits...), and both pick
a large prime 'B' (512 to 1024 bits...), Then to verfify they perform this
interactive protocol...
1. They both generate 64 bits using the LFSR, then another 8 bits. The
larger number is called 'A' and the smaller 'B'. Then they calculate:
((A ^ B) mod N) mod P
Where N 2^(twice the number of bits in P) (i.e 1024 or 2048 in this case).
This is done such that the intermitent result (while calculating A^B is not
truncated too prematurely).
2. Then one person (Bob in the first round, Alice in the second, etc...)
actually communicates this number.
3. If it matches they peform another round and go back to 1.
I really don't think anything of the LFSR's or P will be leaked in this
process..
I want to write a school (I am in grade 11) paper on the subject, and I would
like any feedback.
Thanks,
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: 12 Apr 1999 12:46:33 -0500
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>Herman Rubin wrote:
>> I wonder how many of you understand that the current use of statistical
>> significance is a major error which should never have happened? The
>> significance level is NOT directly related to anything about the degree
>> of certainty; that "accepted" null hypothesis is rarely, if ever, true.
>Use of significance or confidence level is a legacy from R. Fisher.
This is not correct. It goes back to the 18th century, and was used
quite a bit by people in the physical sciences in the 19th. I have
seen those uses.
>It is meaningful if properly understood: Suppose we find that an
>observation disagrees with the model at the 95% level; the meaning
>of that is: "*if* the model were correct, *then* there would be a
>probability of 0.95 that a similar observation would have better
>agreement with the model". Intuitively, such an observation gives
>one reason to doubt the model, when no contrary information is
>available. Thus, it *is* related to certainty -- about the
>correctness of the model (or "null hypothesis"). But it's an
>asymmetric relationship: while doubt can be cast on the model by
>contradictory evidence, lack of contradictory evidence does not
>necessarily *support* the model.
>The null hypothesis doesn't have to be true to be useful.
This is quite true. However, it was not considered by most
scientists until well into this century the models they were
producing were only approximations; when they tested the model,
they were looking to reject it if there was any error.
Fisher very strongly pushed this use of point null hypotheses.
Even now, there are very few papers considering the real
problem, which is to decide if the erroneous null is useful.
>There are other approaches, including "weight of evidence",
>likelihood ratios, etc. that can deal appropriately with such
>things as a priori expectations and combining (possibly
>conflicting) evidence from multiple sources.
These are not quite as simple as the one who does not know
might believe from your paragraph. The likelihood function,
when FULLY stated, contains all the information from the
data, but one has to be careful when using it. Weight of
evidence, crudely used, is almost useless, and in coming up
with an approach which carefully considers the problem,
the prior should be used as a weight function.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: 12 Apr 1999 13:26:00 -0500
In article <7er15d$ib4$[EMAIL PROTECTED]>, Franzen <[EMAIL PROTECTED]> wrote:
>Date: Bob Knauer <[EMAIL PROTECTED]> wrote Sunday, April 11,
>1999 at 1:21 PM:
>>Chi Square is a statistic that tests variances. Variances are not the
>>same as biases.
The chi squared distribution is the distribution of the sum of squares
of independent normal random variables with mean 0, divided by their
common variance. As such, it can be used to test for variances.
The chi squared test was introduced by Karl Pearson about a century
ago to test that the numbers of points in cells are obtained by
random sampling with fixed proportions. He argued that it has
approximately the chi squared distribution for large samples by
computing its first four moments; this is not adequate, and the
result was correctly proved later. But it is asymptotic.
>> Bias is a deviation from the mean which is related to
>>the first moment of a distribution, whereas variance is related to the
>>second moment of a distribution.
This is not relevant.
>I prefer Beethoven's fifth myself.
>>They are fundamentally different quantities, just as the center of
>>mass and the moment of inertia are fundamentally different quantites.
>>Perhaps you would benefit from a reading of the elementary book on
>>statistics by Mario Triola. He discusses Chi Square in detail. I never
>>could figure out why the poster who recommended Triola ever suggested
>>Chi Square with regard to non-randomness tests when there are more
>>direct estimates of deviation from normality.
I suggest you refer to a more advanced text. But in any case, the
chi squared test of goodness of fit refers to a finite classification,
such as heads and tails.
>Perhaps we could both benefit from sticking to the point we are at. You
>assert if I flip a fair coin one million times, my single most probable
>result will be 500,000 heads. By your prior arguments, you also appear
>to believe it is the most desirable result also.
What is "desirable"?
>I assert to you that the chi-square table (derived from the incomplete
>Gamma fuction) is the most accurate and reliable predictor of the number
>of heads expected each and every one million tosses.
This is utter nonsense. If one has independent trials with a
constant probability of success, the most likely time for the
first occurrence is the first trial. If the probability of
success is 10^-6, the expected number of trials is 10^6.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: [EMAIL PROTECTED] (Gallicus)
Subject: Re: help in decrypting a message using the playfair cipher
Date: Mon, 12 Apr 1999 18:50:47 GMT
On Mon, 12 Apr 1999 12:17:32 GMT, [EMAIL PROTECTED] wrote:
>Hi,
>
>I was wondering if anyone would be able to help me in decrypting a message
>which was encrypted using the Playfair Cipher. I have tried decrypting it for
>the past 2 weeks but have not even come close to doing so.
Try the Lanaki lessons :
Index of /org/crypto/crypto/lanaki.crypt.class/lessons/
and a US Army field manual (N� 34-40-2) for basic cryptanalysis :
They are on the Web.
Good luck.
Gallicus.
------------------------------
** 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
******************************
