Cryptography-Digest Digest #464, Volume #9 Mon, 26 Apr 99 02:13:04 EDT
Contents:
Re: Prime Numbers Generator (David Kuestler)
Re: Prime Numbers Generator (Paul Rubin)
Re: How good is /dev/random... (Sandy Harris)
Re: RSA-Myth (Jim Gillogly)
Re: Prime Numbers Generator (Jim Gillogly)
Re: Prime Numbers Generator (Jim Gillogly)
Re: UBE98 Vendor Admission (JPeschel)
Re: Solitaire -- help, please (Boris Kazak)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(wtshaw)
Re: UBE98 Vendor Admission (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: David Kuestler <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Generator
Date: Mon, 26 Apr 1999 03:09:13 +0000
Jim Gillogly wrote:
> David Kuestler wrote:
> > I should also clarify that my program is actually two programs :
> > 1) generate two files 'bytes3.dat' and 'lsb.dat' as a compression technique to
> > be able to fit onto a CD, where the first 3 bytes of the 4 byte prime number is
> > stored once in 'bytes3.dat' with a pointer into 'lsb.dat' which stores the 4th
> > byte. ( 47 hours )
> > 2) convert the 'bytes3/lsb' files into a single file ( 1 hour )
> > The programs also use network byte order to store the data so the files are
> > portable.
>
> You might be able to get better compression by saving only the
> differences between sucessive primes, with an occasional complete
> number to allow for "random enough" access to the file, depending
> on the needs of the program expected to consume this. If you
> always use them in order, of course, you don't need that. I would
> expect a Huffman code on the differences to be very effective, since
> they will usually be fairly small. The maximum difference between
> primes in this range is 336. Since they're always even, you can
> divide by two and save the differences in one byte, for a file size
> of 203M. A Huffman code on that alphabet of 168 characters would
> undoubtedly give dramatic savings; I wouldn't be surprised if it
hmm.. I tried this technique on an electricity load profile neural network forecasting
system and found the differential to be virtually uncompressable where as the
compressed original profiles were slightly smaller than the raw differentials. What I
found was that there is more unpredictability in the differentials than the original
and so a compression algorithm has less redundancy to go by. By the same token
compressing a compressed file rarely results in a significant extra compression, often
worse.
I also tried a fourier transform on the load profile and compress various differences,
with similar poor results.
I would be very interested to hear if you do get better results.
>
> would all fit in under 30M. Plus, of course, the pointers that let
> you get as much random access as you need.
>
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.
>
> > Your program sounds like it efficiently uses on chip cache or something special
> > as I would not have expected a 400Mhz Pentium II to be over 300 times faster than
> > a 233Mhz K6.
>
> I imagine the main difference is in the algorithm rather than the
> processor. For most crypto applications I find a 400 Mhz P2 to be
> about three times faster than a 200 MHz P1... I'd been hoping for
I find for pure number crunching, the 350Mhz pentium II at my employer is somewhere
between 2 and 3 times faster than the 233Mhz K6 at home, but slightly slower than the
200Mhz PowerMac.
>
> more when I bought it. However, I haven't yet tried anything fancy
> for optimizing caches on any of my programs.
>
I wonder how an 800Mhz Alpha will go ? ( dreaming - if I could afford one ) ;^)
>
> > I would be very interested in your blocking technique if you are willing to share
> > your C source code.
>
> I guess at 83 lines it's not too big to post... lots of messages in
> the "True Randomness" thread are running longer! I'm not writing them
> in network order, by the way. Shall we all agree to stone the person
> who invented little-endian?
> --
> Jim Gillogly
> Mersday, 4 Thrimidge S.R. 1999, 14:12
> 12.19.6.2.9, 5 Muluc 17 Pop, Fourth Lord of Night
>
> ------------------------------------------------------------------------
> /*
> * 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);
> 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;
> }
I'll have to study the code a bit... looks interesting.
Thanks.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Prime Numbers Generator
Date: Mon, 26 Apr 1999 03:42:09 GMT
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.
------------------------------
From: [EMAIL PROTECTED] (Sandy Harris)
Subject: Re: How good is /dev/random...
Date: Mon, 26 Apr 1999 03:49:08 GMT
[EMAIL PROTECTED] (Stephen Robert Norris) writes:
>Has anyone done any analysis on how "good" the randomness from /dev/random
>is in Linux?
There's been quite a bit of discussion of this on a couple of mailing
lists recently, One result is that there is now a /dev/random
support web site:
http://www.openpgp.net/random/index.html
It has archives of the mailing list discussions and source for the
latest version of the device driver.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: RSA-Myth
Date: Sun, 25 Apr 1999 21:44:29 -0700
Matthias Bruestle wrote:
>
> Anonymous ([EMAIL PROTECTED]) wrote:
>
> > 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!
>
> > ...
>
> Are non-English/US people supposed to understand this?
It's equally incomprehensible to at least one native US person.
I suspect steganography.
--
Jim Gillogly
Highday, 5 Thrimidge S.R. 1999, 04:43
12.19.6.2.10, 6 Oc 18 Pop, Fifth Lord of Night
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Generator
Date: Sun, 25 Apr 1999 21:56:25 -0700
David Kuestler wrote:
>
> Jim Gillogly wrote:
>
> > You might be able to get better compression by saving only the
> > differences between successive primes... The max difference between
> > primes in this range is 336. Since they're always even, you can
> > divide by two and save the differences in one byte, for a file size
> > of 203M. A Huffman code on that alphabet of 168 characters would
> > undoubtedly give dramatic savings...
>
> hmm.. I tried this technique on an electricity load profile neural network
>forecasting
> system and found the differential to be virtually uncompressable...
> I would be very interested to hear if you do get better results.
OK -- the raw file of 32-bit numbers is 813MB, as you noted. The
difference file I suggested above is 203MB. With gzip it compresses
to 126MB -- a substantial savings, though not as nice as I was hoping
for. In an off-line message you suggested I try tzip, an implementation
of Burrows-Wheeler compression; this gives 119MB, a little better.
(All MB figures here are 10^6, not 2^20.)
> The ideas of my compression technique was to be able to fit on a CD and still be
> directly searchable.
As long as you don't need anything else on the CD, good enough
compression is good enough. If five times as many primes would
be useful, you could use this kind of compression and include
pointers to "distinguished points" where it's convenient; e.g. every
few thousand, at a point where the bit boundaries line up with the
byte boundaries. You'd be able to get to the prime you need in a
single block read and scan.
> Once DVD writers become afordable I'll be able to save the whole 800Mb prime number
> file directly.
Or more... depending on what you need 'em for.
--
Jim Gillogly
Highday, 5 Thrimidge S.R. 1999, 04:32
12.19.6.2.10, 6 Oc 18 Pop, Fifth Lord of Night
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Generator
Date: Sun, 25 Apr 1999 22:00:37 -0700
Paul Rubin wrote:
> 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.
With plenty of room left over for occasional pointers,
in case you want to access the n'th prime in the file.
Pretty straightforward. Leave out the even bits if you
want twice as much room for pointers.
--
Jim Gillogly
Highday, 5 Thrimidge S.R. 1999, 04:58
12.19.6.2.10, 6 Oc 18 Pop, Fifth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: UBE98 Vendor Admission
Date: 26 Apr 1999 05:04:31 GMT
<[EMAIL PROTECTED]> writes:
>Don't they understand that if the code were right, there would be no need to
>*protect* it all? Even open source would be secure.
No, I guess not, although it was explained here to Lee some months
ago.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Solitaire -- help, please
Date: Sun, 25 Apr 1999 22:07:44 -0400
Reply-To: [EMAIL PROTECTED]
Preston Wilson wrote:
>
> Hey all...
>
> I've been racking my brains, trying to figure out Schneier's Solitaire
> algorithm (http://www.counterpane.com/solitaire.html). Has anybody
> out there figured out how to do it, and if so could you help me to get
> it? I'm trying to work through Sample 1 in the Sample Output section.
> I've correctly gotten 4 (4-Clubs) as the first output character, but I
> always seem to get 12 (Q-Clubs) as the second (whereas the accepted
> second character is 49, 10-Spades).
>
> How I'm doing it:
>
> The deck is un-keyed. With the deck face-down, so I can't see the
> numbers on the cards, the top card is the Ace of Clubs. The bottom
> three cards, top to bottom, are the King of Spades, Joker A (A*), and
> Joker B (B*).
>
> Top -> AC 2C 3C ... KS A* B* <- bottom when face-down
>
> I move the A joker down one, then immediately to the top of the deck
> as instructed.
>
> Top -> A* AC 2C ... QS KS B*
=====================
You should not do this. Let the cards be:
Top -> AC 2C ... KS B* A*
>
> Then I move the B joker down 2
>
> Top -> A* AC B* 2C ... QS KS
===================
Now you get:
Top -> AC B* 2C ... QS KS A*
====================
>
> I do the triple-cut, and end up with this:
>
> Top -> 2C 3C ... KS A* AC B*
====================
And after the triple-cut:
Top -> B* 2C 3C ... KS A* AC
Now the count-cut will make sense, because the bottom card is AC:
Top -> 2C 3C ... KS A* B* AC
And remember to leave the bottom card in place!!
>
> The count-cut doesn't change anything because it wants me to cut the
> deck at the 53rd card from the top, leaving the bottom card where it
> is. Therefore I still have
>
> Top -> 2C 3C ... KS A* AC B*
>
> In the final step, I see the 2C on the top, then I count down two
> cards and look at the third.
>
> Top -> 2C 3C _4C_ ... A* AC B*
>
> 4C is my output card, which translates to the number 4.
>
> The previous step doesn't change the order of the deck, per
> instructions.
>
> Now on to the next character.
>
> I move the A joker down one again.
>
> Top -> 2C 3C ... KS AC A* B*
====================
Your order should be:
Top -> 2C 3C ... KS A* B* AC
All the rest is consequential...
I hope this helps. BNK
>
> Then the B joker moves down two, wrapping around to the top of the
> deck.
>
> Top -> 2C 3C B* 4C ... KS AC A*
>
> The triple cut leaves me with
>
> Top -> B* 4C 5C 6C 7C ... KS AC A* 2C 3C
>
> The count cut gives me
>
> Top -> 6C 7C 8C ... KS AC A* 2C B* 4C 5C 3C
>
> Then I see the 6C on the top of the deck, count down 6 and look at the
> 7th, and I get
>
> Top -> 6C 7C 8C 9C 10C JC _QC_ KC AD ...
>
> My second output is the Queend of Clubs, translating to 12. Does
> anybody have any idea what I'm doing wrong???
>
> Thanks in advance for any help anyone can offer.
>
> Preston Wilson
>
> --
>
> To reply, do *not* remove the word in capitals from my return address.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Sun, 25 Apr 1999 23:49:11 -0600
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.
With some effort, but it could be completely automated, using several
algorithms, it is reasonable to maximize security available not by living
in fear of the weakest algorithm but working to make sure the strongest
was included.
Consider the following key handling scheme: A OTP quality stream key is
converted to a number of complementary keys that must all be assimilated
to reestablish the real key. Those several keys are encrypted using
different algorithms. If any of the several algorithms is broken, it does
not matter because all must be broken to get at the real key.
The disadvantages are the combined length of all the keys, and needing
them all. A scheme might be devised somewhat similiar where only a
certain number of the keys would be needed. The result would be the same,
shared maximized strength of different algorithms.
--
Life's battles do not always go to the stronger of faster man...
But, sooner or later always go to the fellow who thinks he can.
------------------------------
From: SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>
Subject: Re: UBE98 Vendor Admission
Date: Mon, 26 Apr 1999 05:28:59 GMT
In article <7fv19k$[EMAIL PROTECTED]>,
"Jay" <[EMAIL PROTECTED]> wrote:
>
> JPeschel wrote in message <[EMAIL PROTECTED]>...
> >Despite the vendor knowing UBE's weakness,
> >it's still being sold.
>
> > "We ourselves know how to break it with ICE.
> > That is being resolved now (you would need
> > to have access to the user's computer to
> > break it)."
> >
> >The last "fix" was to use Shrinker to
> >protect the executables from disassembly.
> >I suppose some SoftICE-hostile code
> >will be the next "fix."
> >
>
> Don't they understand that if the code were right, there would be no need to
> *protect* it all? Even open source would be secure.
>
> jay
>
>
Why do you ask such silly questions. Since when does reality
get un the way of business people making a fast buck.
David Scott
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
to email me use address on WEB PAGE
============= 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
******************************
