Cryptography-Digest Digest #314, Volume #9 Wed, 31 Mar 99 15:13:03 EST
Contents:
Re: Random Walk (R. Knauer)
Re: "Biprime Cryptography" to replace RSA? (Jim Gillogly)
Re: Random Walk (Herman Rubin)
Re: RC4 Questions (Kent Briggs)
Re: "Biprime Cryptography" to replace RSA? (Jim Gillogly)
Re: What is fast enough? ([EMAIL PROTECTED])
Re: RC4 Questions ("Ryan Phillips")
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 (Mok-Kong Shen)
Re: New and recent crypto books (Medical Electronics Lab)
Re: "Biprime Cryptography" to replace RSA? (John Savard)
Re: True Randomness & The Law Of Large Numbers ("Tony T. Warnock")
Re: North Korean A3 code (John Savard)
DPA (Re: Live from the Second AES Conference) (Hironobu Suzuki)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Wed, 31 Mar 1999 15:25:41 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 31 Mar 1999 08:52:09 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Given a POPULATION (P) distribution and a SAMPLE (S) distribution,
>one compares S and P to determine the representativeness of S with
>respect to P.
>Given a DESIRED (D) distribution and a SAMPLE (S) distribution, one
>compares the S and D to determine the confidence in the proposition that
>P is similar to D.
Yes, that has always been my understanding of what statistical
analysis is all about.
Now, given what you just said, what does it have to do with true
randomness, or more correctly, non-true-randomness of a TRNG?
If you respond by saying that true randomness for a TRNG must include
the property of no bias in the ensemble average, I fully agree - since
equidistribution is a necesary (but not sufficient condition) for a
TRNG (which is defined that way for purposes of crypto).
But here is where I believe statistics fails: In order to determine
bias in a UBP one must perform an ensemble average, and for any decent
sized keystream that is impossible. Sampling a very small fraction of
very lond sequences is not going to work. For example, sampling as
many as 1 million sequences for 1 thousand bit sequences is only
sampling the infinitesmially small fraction of 10^6/2^1000, which is
so small I cannot calculate it on my TI scientific calculator.
The best you can do with such an infinitesmially small sample is infer
some property that is present in infinite sequences, namely
pseudorandomness. That makes statistical tests useful for diagnostic
warnings, but useless for a reasonable determination of
non-true-randomness.
(By "reasonable" I mean suitable for the crypto application at hand.
Obviously, if you only intend to use a TRNG for one short message -
like the Washington-Moscow Hotline - the conditions for "reasonable"
are relaxed compared to crypto traffic that passes several million
bits per hour).
But since you brought it up, kindly tell us the assumptions that you
must make to be able to infer properties of D from calculations on S.
That is, we model D in such a way that it has no bias - it is a
uniform distribution like that for the UBP. I have a suspicion that
somewhere there is an assumption about D which comes from an analysis
of infinite sequences - which as we know (from expositions like those
of Feller) has little to do with finite sequences, even very large
finite sequences generated from discrete sample spaces.
IOW, the desired property of normality (lack of bias) present in
almost all infinite sequences (Borel normality), is simply not present
in almost all finite sequences generated by a uniform process such as
the UBP, even for a very large number of steps. In fact, contrary to
what one might expect based on naive intuition, the random walk
distribution - a critical measure of bias - actually broadens as n
grow larger. Instead of more sequences having less bias, it turns out
that more sequences have more bias as the paths migrate away from the
origin. IOW, the Gaussian distribution broadens with time.
Bob Knauer
"The laws in this city are clearly racist. All laws are racist.
The law of gravity is racist."
- Marion Barry, Mayor of Washington DC
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: "Biprime Cryptography" to replace RSA?
Date: Wed, 31 Mar 1999 07:41:18 -0800
John Gilmore reported that RSADSI wants people to pick a new name
for the RSA Algorithm.
Arnold Reinhold suggested:
> > I would propose "Biprime Cryptography" or "BPC" as the generic term for
> > RSA.
...
> > If RSADSI no longer wishes the public to honor their founders, we might as
> > well choose a descriptive name.
[EMAIL PROTECTED] wrote:
> Where can I get a whitepaper on this?
On the RSA algorithm? At www.rsa.com, or check the Sci Am article.
On RSADSI's anti-RSA campaign? Their letter to the IEEE P1363
standards group is at
http://grouper.ieee.org/groups/1363/letters/SecurityDynamics.jpg
Neil Koblitz, noted crypto author, suggests putting the authors
in alphabetical order: Adleman Rivest Shamir Encryption.
Perhaps tenable is simply copping a snook at RSADSI, pointing out that
since it's been called the RSA system consistently in the literature
without anybody (including them) writing (tm) after it, it's a bit
late in the millennium for them to be claiming trademark infringement.
Since printed books aren't going to change easily, changing the
ubiquitous common name of the algorithm would only lead to confusion.
IANAL, of course.
--
Jim Gillogly
9 Astron S.R. 1999, 15:32
12.19.6.1.4, 6 Kan 17 Cumku, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Random Walk
Date: 30 Mar 1999 10:05:47 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On Mon, 29 Mar 1999 10:57:46 -0600, Jim Felling
><[EMAIL PROTECTED]> wrote:
>>I would allow them to determine when my TRNG is malfunctioning -- however, they
>would not be
>>the sole piece of evidence considered, and would also not be regarded as being 100%
>>authoritative.
>I think you are saying that you would use statistical tests for
>diagnostic purposes, not to make a determination of the proper
>functioning of the TRNG.
>OK, if that is the case, let's get down to specifics. I sell you a
>TRNG that you plan to use to generate keystreams of length n bits. For
>the sake of discussion lets say that n = 10^6. That is, you will
>generate one million bits, and submit that sequence to statistical
>tests before proceeding to build your one time pad.
>Exactly what statistical tests do you plan to conduct on that
>keystream that you believe will tell you that the TRNG is
>malfunctioning?
If you define functioning as meaning that the sequence of bits
is independent, with each bit being equally likely to be zero or
one, my answer is that the TRNG is malfunctioning, and I do not
need to perform a test. Physical equipment is not going to
preform in an ideal manner.
Far too many believe, and have believed, that the point null
hypothesis is tenable. Even when it is, it is something about
a law of nature, not a realizable experiment.
--
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: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: RC4 Questions
Date: Wed, 31 Mar 1999 16:46:24 GMT
David wrote:
> Do I need to use a new salt for each outgoing message? (a different salt
> for every key?) The keys will be pseudo-random, not chosen by the user.
Yes.
> If I call it ARCFOUR and release it at 40bits international and large key
> USA will I be sued? :)
I've been using RC4 under the name PC1 for several years. You can now export
with key sizes up to 56 bits although you still need the one-time review from
the BXA.
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: "Biprime Cryptography" to replace RSA?
Date: Wed, 31 Mar 1999 08:22:29 -0800
Reply-To: [EMAIL PROTECTED]
DJohn37050 wrote:
> Another idea to to honor the actual inventor, Cliff Cocks of GCHQ. Something
> like Cocks' Two Prime (CTB) algorithm or some such.
This suggestion, CTP for Cocks' Two Prime algorithm, sounds like an excellent
choice, and is my new favorite if a new name must be selected.
However, given RSA Labs' continuing use of RSA as a name for the algorithm
without a (tm) or any other modifier, I think the matter must not be urgent
or important to them. See, for example, section 3.1 of their FAQ at
http://www.rsa.com/rsalabs/faq/html/3-1-1.html which begins:
RSA is a public-key cryptosystem that offers both encryption and
digital signatures (authentication). Ron Rivest, Adi Shamir, an
Leonard Adleman developed RSA in 1977 [RSA78]; RSA stands for the
first letter in each of its inventors' last names.
RSA works as follows: take two large primes, p and q, ...
The CESG report by Clifford C. Cocks was dated 20 Nov 1973, according to
Ellis' paper at http://jya.com/ellisdoc.htm .
--
Jim Gillogly
9 Astron S.R. 1999, 16:11
12.19.6.1.4, 6 Kan 17 Cumku, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: What is fast enough?
Date: Wed, 31 Mar 1999 14:42:30 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bruce Schneier) wrote:
> On Tue, 30 Mar 1999 01:13:49 GMT, [EMAIL PROTECTED] wrote:
>
> >Jack Lloyd and I are currently working on a cipher together. I was just
> >wondering (from the communities point of view) what is acceptable speeds?
> >
> >Right now, in the unoptimized C code, on a 233mhz Cyrix MII, I get between
> >1.4MB/sec and 2.9MB/sec (32 rounds and 16 rounds respectively).
> >
> >Isn't anything above 1MB/sec considered fast enough? I mean my hd controller
> >only works at 4.5MB/sec anyways!
>
> First off, don't calculate speed in MB/sec, count it in clock cycles
> per byte encrypted. (It's a more general measure.)
Allow me to STRONGLY disagree. It is far LESS general.
If measured in clock cycles per byte it becomes highly dependent on machine
architecture: how many superscalar ops/cycle that can be performed, how well
pipelined the architecture is, whether the instruction stream generates
pipeline stalls, etc.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Ryan Phillips" <[EMAIL PROTECTED]>
Subject: Re: RC4 Questions
Date: Wed, 31 Mar 1999 08:56:24 -0800
I've been working on this problem for awhile. You could try to use public
key crypto(El Gamal or RSA) to send the session key of the block cipher to
each user. The slowest part of the program should be the public key
generation and encryption.
Kent Briggs <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> David wrote:
>
> > Do I need to use a new salt for each outgoing message? (a different
salt
> > for every key?) The keys will be pseudo-random, not chosen by the user.
>
> Yes.
>
> > If I call it ARCFOUR and release it at 40bits international and large
key
> > USA will I be sued? :)
>
> I've been using RC4 under the name PC1 for several years. You can now
export
> with key sizes up to 56 bits although you still need the one-time review
from
> the BXA.
>
> --
> Kent Briggs, [EMAIL PROTECTED]
> Briggs Softworks, http://www.briggsoft.com
>
>
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Wed, 31 Mar 1999 17:52:32 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 31 Mar 1999 08:08:03 -0700, "Tony T. Warnock"
<[EMAIL PROTECTED]> wrote:
>Because 1/Sqrt(N) gets smaller, the distribution becomes more peaked. The
>fraction within 5% of the mean is .10*Sqrt(N) as can be shown by
>computation. Physical intuition and statistical intuition also give this
>result. The distribution becomes sharper.
Now is as good a time as any to introduce something I alluded to
earlier about the diffusion example.
In the case of diffusion, which obeys a Gaussian spatial distribution,
the number of ink particles is fixed at the outset - that means that
the area under the Gaussian distribution is constant from the
beginning of the diffusion process.
Therefore because the distribution broadens as time increases, that
means that the probability of the mean decreases with time. Fewer
particles are near the mean (the origin) as time increases.
This is equivalent to an ensemble with a fixed number of steps or
bits. Start out with a fixed number of 2^n particles. As time evolves,
each bit in each particle gets a specific value, one after the other,
until at the end of n steps all n bits are set in 2^n different ways.
The time evolution of any sequence is not the same as the ensemble
average at a fixed point represented by n steps. Any particular
sequence traces out its own unique walk that has no direct bearing on
the ensemble average other than it makes a contribution of size 1/2^n
to the ensemble average.
Therefore, sampling an infinitesimally small number of sequences for
use in statistical tests will lead to incorrect conclusions. Making
certain (false) assumptions about the relationship of pseudorandomness
to true randomness will not make statistical tests correct,either.
As several authors have pointed out (this quote is from Williams &
Clearwater, op. cit.):
"...even when random number generators pass such statistical tests,
the sequence of numbers it generates may still not be random enough to
serve as an approximation to a true random process."
Bob Knauer
"The laws in this city are clearly racist. All laws are racist.
The law of gravity is racist."
- Marion Barry, Mayor of Washington DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Wed, 31 Mar 1999 17:54:51 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 31 Mar 1999 17:42:21 GMT, [EMAIL PROTECTED] (Peter Pearson)
wrote:
>Bryan Olson is correct in saying that as the number of steps, n,
>increases, a larger fraction of random walks of length n will be
>within 0.05*n of the origin. If you bear in mind that the mean
>distance from the origin increases as sqrt(n), which for large
>n increases more slowly than 0.05*n -- or *any* positive constant
>times n -- this is not surprising.
>R. Knauer is correct in saying that perfume molecules will eventually
>diffuse throughout the whole room. There is no contradiction with
>what Bryan said, since the physical analogue of the situation Bryan
>was discussing is a room whose walls recede at a constant rate. The
>experiment R. Knauer describes reflects the proportion of random
>walks whose distances from the origin exceed some *fixed* value,
>and this proportion does indeed tend to 100%.
This reply is identical to the one I posted on another thread:
+++++
Now is as good a time as any to introduce something I alluded to
earlier about the diffusion example.
In the case of diffusion, which obeys a Gaussian spatial distribution,
the number of ink particles is fixed at the outset - that means that
the area under the Gaussian distribution is constant from the
beginning of the diffusion process.
Therefore because the distribution broadens as time increases, that
means that the probability of the mean decreases with time. Fewer
particles are near the mean (the origin) as time increases.
This is equivalent to an ensemble with a fixed number of steps or
bits. Start out with a fixed number of 2^n particles. As time evolves,
each bit in each particle gets a specific value, one after the other,
until at the end of n steps all n bits are set in 2^n different ways.
The time evolution of any sequence is not the same as the ensemble
average at a fixed point represented by n steps. Any particular
sequence traces out its own unique walk that has no direct bearing on
the ensemble average other than it makes a contribution of size 1/2^n
to the ensemble average.
Therefore, sampling an infinitesimally small number of sequences for
use in statistical tests will lead to incorrect conclusions. Making
certain (false) assumptions about the relationship of pseudorandomness
to true randomness will not make statistical tests correct,either.
As several authors have pointed out (this quote is from Williams &
Clearwater, op. cit.):
"...even when random number generators pass such statistical tests,
the sequence of numbers it generates may still not be random enough to
serve as an approximation to a true random process."
+++++
Bob Knauer
"The laws in this city are clearly racist. All laws are racist.
The law of gravity is racist."
- Marion Barry, Mayor of Washington DC
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Wed, 31 Mar 1999 20:27:21 +0100
R. Knauer wrote:
>
> We are discussing the UBP. Tell us where there is a problem with using
> that as a model for an *idealized* TRNG. I use the term "idealized" in
> the exact same manner that a mathematician uses it to discuss the
> properties of a perfect circle. The fact that perfectly circular
> objects do not exist in the physical world does not prevent us from
> discussing the concept of the perfect circle as an idealized model of
> real wheels. Likewise, nothing reasonable prevents us from discussing
> the properties of an idealized TRNG, modeled after the UBP, as the
> model for real TRNGs.
I believe THE problem is the impossiblity of obtaining an algorithm
(method) to determine a measure (quantity) of deviation of a given
'real TRNG' from the 'idealized TRNG', if you do not accept
the applicability of statistical tests (which as far as I understand
is one of your positions concerning random number generations).
M. K. Shen
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: New and recent crypto books
Date: Wed, 31 Mar 1999 12:27:07 -0600
[EMAIL PROTECTED] wrote:
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (CryptoBook) wrote:
> >
> > Classical Crypto Books is pleased to announce that the following new and
> recent
> > crypto books are in stock and ready for immediate shipment.
>
> Commercial advertising is a no-no. Please don't do it again.
It's a useful announcement to those of us who
are interested. These posts come out once every
few months, it isn't spam at all. Please keep
posting new books.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: "Biprime Cryptography" to replace RSA?
Date: Wed, 31 Mar 1999 18:51:39 GMT
[EMAIL PROTECTED] wrote, in part:
>At 5:27 PM -0800 3/29/99, John Gilmore wrote:
>>Now that their patent is getting ready to expire (next fall), RSA is
>>trying to crack down on anyone who refers to the use of the
>>algorithm by calling it "RSA".
>>Perhaps we should have a little contest for what to call the RSA
>>algorithm, given RSA's objection to calling a shovel a spade.
>I would propose "Biprime Cryptography" or "BPC" as the generic term for
>RSA. Biprime is a natural and appropriate English name for the product of
>two primes.
Before hastily coming to a conclusion, one might consider other candidates,
although I'll have to agree that this is a good one.
"Exponential Non-Secret Encryption" - good historical reference there...
"Clifford Cocks Algorithm" - it might sound impolite if shortened...
"Secret Inverse Exponent Method"; "Concealed Factorization Modulus Method";
"Composite Modular Exponentiation Method" ... all technically accurate, but
not likely to catch on as something immediately identified with the one
particular algorithm.
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Wed, 31 Mar 1999 08:08:03 -0700
Reply-To: [EMAIL PROTECTED]
>
>
> "R. Knauer" wrote:
>
>>
>> Feller (op. cit.) does these very calculations, but not using any
>> PRNG. The probability for large n is a Gaussian, and it spreads out in
>>
>> time - like SQRT(n) / n = 1/SQRT(n). As n increases, 1/SQRT(n) gets
>> smaller.
>>
>
Because 1/Sqrt(N) gets smaller, the distribution becomes more peaked. The
fraction within 5% of the mean is .10*Sqrt(N) as can be shown by
computation. Physical intuition and statistical intuition also give this
result. The distribution becomes sharper.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: North Korean A3 code
Date: Wed, 31 Mar 1999 19:24:28 GMT
Eric Hildum <[EMAIL PROTECTED]> wrote, in part:
>In today's Japan Times, there was a discussion of a 1978 kidnapping of a
>Japanese woman from Japan by North Korea [this is one of about a dozen suspected
>cases over the last twentyfive years].
I remember reading about this, or a similar case, in the Reader's Digest: a
beauty contest winner from Japan was kidnapped to serve as a concubine to
Kim Jong Il, son of Kim Il Sung and North Korea's current ruler.
>The article discussed a North Korean code
>called "A3," described as a five digit number for each hangul (?) character.
Hangul is correct. Although it is like an alphabet, the possible Korean
syllables are often treated as single entities. However, there are only a
few hundred Hangul syllables.
>Given the recent discussion on this newsgroup, it would seem to me that such a
>code system would be relatively easy to break -- are there any references on the
>internet to this system? I assume that as so much is known about this code that
>it has in fact been broken....
I'm not aware of any, but I'll see what I can turn up...
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (Hironobu Suzuki)
Subject: DPA (Re: Live from the Second AES Conference)
Date: 31 Mar 1999 18:47:22 GMT
>>>>> "B" == Bruce Schneier <[EMAIL PROTECTED]> writes:
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Bruce Schneier)
writes:
B> He said in his talk that every cipher is vulnerable. We've done
B> this sort of work, too, and we have found that you can't defend
B> against these types of attack with the algorithm. You can do some
B> things with the implementation and some things with the hardware,
B> but basically you need to defend in the protocol layer.
Smart-Card should be inexpensive, physical robustness and easy to use
for ordinary people.
I'm thinking that Smart-Card is too week hardware to use strong
cipher. To analyze or to bypass a cheap hardware, Smart-Card is easy
(ie. Hitachi's Mondex card).
And I'm afraid of that the EC market not accept Smart-Card which
become expensive, fragile and not easy use to protect against
analyzing or something.
Smart-Card with AES sounds like Japanese conpact car with American V8
engine; CR-X's body with Vetty's engine. It's geek and dangerous.
--hironobu
------------------------------
** 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
******************************
