Cryptography-Digest Digest #465, Volume #9 Mon, 26 Apr 99 02:13:04 EDT
Contents:
Re: Prime Numbers Generator (David Kuestler)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
([EMAIL PROTECTED])
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: Prime Numbers Generator (David Kuestler)
Re: RSA-Myth (wtshaw)
----------------------------------------------------------------------------
From: David Kuestler <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Generator
Date: Mon, 26 Apr 1999 05:41:42 +0000
==============F01802D5FC816E0D10E2513A
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Jim Gillogly wrote:
>
snip ...
> ------------------------------------------------------------------------
> /*
> * erato: sieve of eratosthenes for up to 2**32.
> * Two steps: first find all primes less than 2**16, then use them to sift
> * the remaining numbers in blocks.
> *
> * Jim Gillogly, 24 Apr 1999
> */
>
> #include <stdio.h>
>
> #define MAXSMALL 6542 /* 6542 for primes up to 1<<16. */
> #define TOP (1 << 16) /* Top of each block to be sifted. */
> #define PRFILE "primes" /* Save 'em in a file. */
> #define BLOCKS (1 << 16) /* How many blocks to do total? */
>
> char sieve[TOP]; /* Turned off if composite. */
> char * stop = &sieve[TOP];
>
> unsigned long smalls[MAXSMALL]; /* All primes under 2**16. */
> long smallnum = 0;
>
> main()
> {
> unsigned long i, j, k, nprimes, start, step, *s;
> char *p, *q;
> FILE *out;
>
> memset(sieve, 1, TOP);
> sieve[0] = sieve[1] = 0; /* definition */
> p = sieve;
> do
> {
> while (++p < stop && *p == 0); /* Scan to next prime. */
> q = p;
> step = q - sieve;
> while ((q += step) < stop)
> *q = 0;
> } while (p < stop);
You could save a few milliseconds by hard coding the small primes table as I did (
though hardly worth it ).
>
> if ((out = fopen(PRFILE, "w")) == NULL)
> {
> fprintf(stderr, "Phui.\n");
> return 1;
> }
> for (i = 0, s = smalls, p = sieve; i < TOP; i++)
> if (*p++)
> {
> *s++ = i;
> fwrite(&i, 4, 1, out);
> #ifdef VERBOSE
> printf("%d\n", i);
> #endif
> }
> smallnum = nprimes = (s - smalls);
> printf("%d small primes.\n", smallnum);
> /* Now sift each 2**16-number block with these small primes. */
> start = 0;
> for (k = 1; k < BLOCKS; k++)
> {
> start += TOP;
> memset(sieve, 1, TOP); /* Clear it out. */
> sieve[0] = 0;
> for (i = 0, s = smalls; i < smallnum; i++) /* small primes */
> {
> step = *s++;
> for (q = &sieve[step - (start % step)];
> q < stop; q += step)
> *q = 0;
> }
> for (i = 0, p = sieve; i < TOP; i++)
> if (*p++)
> {
> j = i + start;
> #ifdef VERBOSE
> printf("%d\n", j);
> #endif
> fwrite(&j, 4, 1, out);
> nprimes++;
> }
> }
> fclose(out);
> printf("%d primes under %lld\n", nprimes, (long long) TOP * BLOCKS);
> return 0;
> }
Excellent ! This ran just shy of an hour on a 233Mhz K6 and gave the same file size,
though the byte order is different ( as expected ). You're certainly a better C
programmer than I as you only use integers and pointers where as I used array
references with the occasional floating point operation.
If you are interested you should submit it to The Prime Pages . Your code is faster,
smaller, more understandable and therefore would be easier to impliment than others.
==============F01802D5FC816E0D10E2513A
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Jim Gillogly wrote:
<blockquote TYPE=CITE> </blockquote>
snip ...
<blockquote
TYPE=CITE>------------------------------------------------------------------------
<br>/*
<br> * erato: sieve of eratosthenes for up to 2**32.
<br> * Two steps: first find all primes less than 2**16, then use
them to sift
<br> * the remaining numbers in blocks.
<br> *
<br> * Jim Gillogly, 24 Apr 1999
<br> */
<p>#include <stdio.h>
<p>#define MAXSMALL
6542
/* 6542 for primes up to 1<<16. */
<br>#define TOP
(1 << 16) /* Top of each block
to be sifted. */
<br>#define PRFILE
"primes" /* Save 'em in a file.
*/
<br>#define BLOCKS
(1 << 16) /* How many blocks
to do total? */
<p>char
sieve[TOP];
/* Turned off if composite. */
<br>char * stop = &sieve[TOP];
<p>unsigned long smalls[MAXSMALL];
/* All primes under 2**16. */
<br>long
smallnum = 0;
<p>main()
<br>{
<br> unsigned long
i, j, k, nprimes, start, step, *s;
<br>
char
*p, *q;
<br>
FILE
*out;
<p> memset(sieve, 1, TOP);
<br> sieve[0] = sieve[1] =
0;
/* definition */
<br> p = sieve;
<br> do
<br> {
<br>
while (++p < stop && *p == 0); /* Scan to next prime.
*/
<br>
q = p;
<br>
step = q - sieve;
<br>
while ((q += step) < stop)
<br>
*q = 0;
<br> } while (p < stop);</blockquote>
You could save a few milliseconds by hard coding the small primes table
as I did ( though hardly worth it ).
<blockquote TYPE=CITE>
<br> if ((out = fopen(PRFILE,
"w")) == NULL)
<br> {
<br>
fprintf(stderr, "Phui.\n");
<br>
return 1;
<br> }
<br> for (i = 0, s = smalls,
p = sieve; i < TOP; i++)
<br>
if (*p++)
<br>
{
<br>
*s++ = i;
<br>
fwrite(&i, 4, 1, out);
<br>#ifdef VERBOSE
<br>
printf("%d\n", i);
<br>#endif
<br>
}
<br> smallnum = nprimes = (s
- smalls);
<br> printf("%d small primes.\n",
smallnum);
<br> /* Now sift each 2**16-number
block with these small primes. */
<br> start = 0;
<br> for (k = 1; k < BLOCKS;
k++)
<br> {
<br>
start += TOP;
<br>
memset(sieve, 1, TOP); /* Clear it out. */
<br>
sieve[0] = 0;
<br>
for (i = 0, s = smalls; i < smallnum; i++) /* small primes */
<br>
{
<br>
step = *s++;
<br>
for (q = &sieve[step - (start % step)];
<br>
q < stop; q += step)
<br>
*q = 0;
<br>
}
<br>
for (i = 0, p = sieve; i < TOP; i++)
<br>
if (*p++)
<br>
{
<br>
j = i + start;
<br>#ifdef VERBOSE
<br>
printf("%d\n", j);
<br>#endif
<br>
fwrite(&j, 4, 1, out);
<br>
nprimes++;
<br>
}
<br> }
<br> fclose(out);
<br> printf("%d primes under
%lld\n", nprimes, (long long) TOP * BLOCKS);
<br> return 0;
<br>}</blockquote>
Excellent ! This ran just shy of an hour on a 233Mhz K6 and gave the same
file size, though the byte order is different ( as expected ). You're certainly
a better C programmer than I as you only use integers and pointers where
as I used array references with the occasional floating point operation.
<p>If you are interested you should submit it to <a
href="http://www.utm.edu/research/primes/">The
Prime Pages</a> . Your code is faster, smaller, more understandable and
therefore would be easier to impliment than others.</html>
==============F01802D5FC816E0D10E2513A==
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Mon, 26 Apr 1999 05:38:03 GMT
In article <7fusfv$as8$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bryan G. Olson; CMSC (G)) wrote:
> ...
> There is a situation worse than having all one's eggs in one basket.
> The problem with one basket is that there exists a potential failure
> that would be catastrophic. What's worse is a system in which any
> one of many possible failures would be catastrophic. If one accepts
> that in realistic applications of cryptography the same intelligence
> is available from many messages, then choosing from a thousand
> ciphers for each message moves us from one potential catastrophic
> failure to many potential catastrophic failures.
I think you assume that the attacker will know which cipher has
been used. In fact, a good variable cipher protocol would hide the
information about which cipher or cipher combination has been
used.
Let us design two possible future worlds and then pick the one
that is more secure:
In the first the AES is used for almost all encryption.
In the second world we define a set of several interesting
ciphers, preferably ciphers that are different in some fundamental
ways. We put in there the AES, some more ciphers that have been
extensively analyzed, some ciphers that follow different design
methodologies (for example variable ciphers such as Frog, ciphers
designed specifically for making analysis very difficult, ciphers
using novel primitives or structures, etc.). Now add to all
encrypted data or make implicit in all security applications the
following information: the subset of the ciphers that must be used
and at which "depth", i.e. how many ciphers out of this subset are
cascaded in series. Finally extend the secret key with a
sufficient number of bits that define the sequence of the ciphers.
(I don't want to discuss here how the individual ciphers' keys are
defined - I know it is not optimal but as a first approximation
let us suppose all individual keys are identical.) Now observe
that if you want to use the AES, you just define a subset that
includes only the AES and a depth of one. But you can also include
the entire set and a depth of one hundred.
In fact, the original set of ciphers need not be fixed. Allow
anybody to add his or her code to the lot in a public Internet
server in an environment where everybody can "Amazon-like" comment
on all present ciphers, where the experts' opinion is expressively
stated and where statistics are held about which products include
which ciphers in their "standard" set of ciphers. If my email
program receives a message that uses a subset with a cipher not
present in my computer, then it will download the authenticated
Java code from the public server before decrypting.
So which world do you think is more secure: the AES-centric one,
or the "organized chaos" one? It seems to me the latter, because
the attacker will have a more complex task and less information to
work with.
Now, even if we agree that the organized chaos world is more
secure we still have to discuss costs. Now observe that people can
always use only optimized AES code in their applications (in fact,
the public server could also include optimized code for several
cipher/platform combinations). In all cases, royalty free Java
code for the cascaded ciphers would not really increase the cost
of an application. Many secure applications could even be
cipher-neutral. For example, a paranoid organization could use a
standard email program and define a large subset of ciphers at a
great depth without really paying anything more. So I think the
increase of costs would really be marginal and would correspond
largely to the definition of a standard protocol for cascading
ciphers as well as the operation of the "cipher server". In fact
in some cases there may be some cost advantages. For example,
suppose RC6 is chosen as the AES but this cipher can not be as
easily ported to smartcards as RC6a. In the organized chaos world
a smartcard manufacturer could use the cheaper RC6a even in
applications where this smartcard will communicate with PCs all
over the world.
One can ask if all this is really necessary. After all most
experts think that it is extremely unlikely that the AES will
suffer a catastrophic failure in the next 50 years or so. Even so,
it is deeply troubling to think that we are moving towards an
information society and that much of its security will not be
based on theoretical proof or, at least, experimental test but on
personal opinion of a few dozen people, even if they are excellent
and well meaning professionals.
It is still possible that somebody will publish a provable secure
cipher that is practical to implement. Meanwhile a variable cipher
protocol similar to the one described above would fulfil almost
everybody's requirements for symmetric encryption. This would leave
many other problems to worry about such as key management and
public key systems, Trojan horses, the appropriate use of encryption
technology, etc.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Mon, 26 Apr 1999 05:52:11 GMT
"R. Knauer" wrote:
> That is a correct statement. Now let's apply it to the FIPS-140
> Monobit Test. According to that document, you are to generate one
> contiguous sequence of 20,000 bits, count the number of 1 bits and
> from that infer whether the TRNG is broken. If the number of 1 bits is
> excessive or deficient by a stated amount, then you are to conclude
> without further investigation that the TRNG is indeed broken.
No, what the document says (thanks for posting the URL) is that
for Level 3 or 4 security, this is one of a handful of tests that
will put the system into the "error state" (preventing its use
until reset) whenever one of the tests detects a pattern whose
a priori probability is below some tiny threshold (something
like 1 in 1,000,000). Notice the tests are not totally
independent, so in case of a catastrophic malfunction several of
them might trigger the error state at the same time.
The intent is clearly the same as when a nuclear reactor coolant
level, core temperature, etc. sensor causes a shutdown because
it detects violation of a predetermined safety limit.
The threshold of 10^-6 per test (3 or 4 tests) triggers the error
state occasionally when the system is functioning correctly, and
one could argue that "the boy who cried Wolf!" syndrome would set
in, as it did in the horrible Therac-IV incidents, and operators
would eventually just routinely reset the system without checking
whether it might actually need repair first. The reason there is
not a lower threshold is presumably that 20,000 bits is as many
as the specifiers were willing to tolerate being broken before
detection.
It all seems fairly sensible if one wants to halt the system
shortly after it starts generating "busts", rather than letting
inadequately secure key streams compromise a lot of traffic.
(As a matter of historical record, such "busts" have been
instrumental in cryptanalyzing a variety of machine systems.)
> My claim is that you must conduct a large number of tests using very
> large samples in order to get the weight of evidence on your side. A
> single application of a simplistic test like the FIPS-140 Monobit Test
> using a mere 20,000 bits is NOT enough evidence to come to the
> conclusion that the TRNG is malfunctioning.
It is, however, reason to raise the suggestion that it needs to
be checked, which is what FIPS-140 intended the test to do.
> Define "consistently" in analytic terms.
> Define "suitable" in analytic terms.
These are English words; look them up in a dictionary.
> 2) The TRNG subsystems are shown experimentally to operate within
> specifications.
You have never said *how* you could do this, without in effect
applying one or more statistical tests.
> But all this is not necessary, since once a quantum computer is built
> it can be programmed with the algorithm for true randomness (which is
> already known) and the numbers that are calculated must be truly
> random - or otherwise the quantum computer is broken, in which case it
> won't computing anything.
What if it is computing the wrong thing? That's the kind of
brokenness we're concerned about (and that the FIPS-140 tests
are intended to detect).
------------------------------
From: David Kuestler <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Generator
Date: Mon, 26 Apr 1999 05:51:23 +0000
Paul Rubin wrote:
> In article <[EMAIL PROTECTED]>,
> David Kuestler <[EMAIL PROTECTED]> wrote:
> >The ideas of my compression technique was to be able to fit on a CD
> >and still be directly searchable. Once DVD writers become afordable
> >I'll be able to save the whole 800Mb prime number file directly.
>
> Why not just store a bit map of where the primes are?
> 2^32 possible primes = 2^32 bits = 2^29 bytes = 512 MB.
> That will fit on a cd-rom rather nicely.
Good idea ( 2^31 if you only work with the odds = 269MB ). I wonder if
the extra processing overhead would weigh against it in a search.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: RSA-Myth
Date: Sun, 25 Apr 1999 23:57:57 -0600
> >> PGP are such that generator with source code and send that the public
> >> will never with out code and an RSA PGP. Think.
> >
> >> But this is RSA approach? How many times send that the public primes
> >> it is RSA approach? At baud, even the weaknesses that generator with
> >> a probability, that the Spooks may have to think just because the same
> >> algorithms is RSA PGP cannot!
With apologies to the poster if acting under language handicap, we surely
see here an instance where text contains more than the usual expected
harvestable randomness per character.
--
If you think you are beaten, you are.
If you thing you dare not, you don't.
------------------------------
** 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
******************************
