Cryptography-Digest Digest #515, Volume #9 Fri, 7 May 99 16:13:03 EDT
Contents:
Re: Roulettes ([EMAIL PROTECTED])
Re: Random permutation (John Savard)
Re: Shamir's Discover: to those in the know (Medical Electronics Lab)
Re: Random permutation ([EMAIL PROTECTED])
Re: Little Irish girl's algorithm? (Emmanuel BRESSON)
Re: Shamir's Discover: to those in the know (Bob Silverman)
Re: Shamir's Discover: to those in the know (DJohn37050)
Re: Shamir's Discover: to those in the know (DJohn37050)
Re: Shamir's TWINKLE Factoring Machine (DJohn37050)
Re: Random permutation (Herman Rubin)
East German encyption code? (Lars Hohmuth)
Re: Crypto export limits ruled unconstitutional (John Savard)
Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO (SCOTT19U.ZIP_GUY)
Re: The simplest to understand and as secure as it gets. (SCOTT19U.ZIP_GUY)
Netscape Encryption Algorithm ("Majestic")
Re: Shamir's Discover: to those in the know (David A Molnar)
THE DIRECTION OF CRYPTO IN THE U.S. (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
Date: Fri, 07 May 1999 10:53:01 -0400
From: [EMAIL PROTECTED]
Subject: Re: Roulettes
Right, you probably need a some kind of weighted sum of the convex hull
of the perimiter of each face. Still it would be nice to be able to
roll a 60-sided die. The eldest numbering system (Sumerian I think)
survives only in our time metrics.
Patrick Juola wrote:
>
> In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> >Patrick Juola wrote:
> >>
> >> In article <[EMAIL PROTECTED]>,
> >> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >> >Paul Rubin wrote:
> >> >>
> >> >> In article <[EMAIL PROTECTED]>,
> >> >> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >> >> >Boris Kazak wrote:
> >> >> >>
> >> >> >
> >> >> >> Just use octahedric dice (8faces) and get your random numbers in octal.
> >> >> >
> >> >> >Are such dices on sale? BTW, maybe Rubik's cube (there is also a
> >> >> >4*4*4 variant) and similar toys could be of use.
> >> >>
> >> >> Yes, go to a game store and you can get N-sided dice for
> >> >> various N including N=4, 6, 8, 10, 12, 20, etc.
> >> >> Of course N=6 is the easiest to find. N != 6 is mostly
> >> >> used for role playing games like Dungeons and Dragons.
> >> >
> >> >But according to mathematics there exist exactly 5 regular polyhedra:
> >> >tetrahedron, hexahedron, octahedron, dodecahedron and icosahedron.
> >>
> >> But there are lots of other dice out there that are symmetrical,
> >> but not regular, polyhedra. For example, to construct a fair
> >> 10-sided die, simply construct a regular pentagon and place two
> >> vertices a fixed distance "above" and "below" the center of the
> >> pentagon. Connect all vertices and you have a solid with the
> >> necessary 10-fold symmetry, even though the faces are not themselves
> >> symmetric.
> >>
>
> >This works for any even N, but in the limit you actually have a coin to
> >flip and then a large roulette wheel to spin.
> >
> >For decimal dice the best answer is an appropriately marked icosahedron
> >(each number appears twice). Percentile dice are composed ot two
> >differently colored decimal dice.
> >
> >The largest solid that can be constructed from unit edges, ignoring
> >stellation is a rhombicosaduodecahedron. This figure has 60 faces
> >composed of triangles, squares, and pentagons. By truncating a
> >stellation of each face one can construct a version where the areas of
> >the faces are equal.
> >
> >Does this form a "fair" die?
>
> Certainly not by virtue of differently-shaped areas having equal
> area. Consider a pencil (a hexagonal prism) as an eight sided
> "die"; six long rectangular faces and two hexagonal faces at the
> end. By adjusting the length of the pencil, we can make all
> eight faces have equal area, but the hex faces are still very
> unlikely to be thrown for simple reasons of stability.
>
> -kitten
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Random permutation
Date: Fri, 07 May 1999 17:03:36 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>[EMAIL PROTECTED] wrote:
>> This returns a uniform choice from [0, 16!-1], which
>> we cam map one-to-one to the possible permuations. It's
>> optimal in the expected number of calls to rand16().
>Suppose you have computed x as a uniform choice. How do you get from
>x to the permutation desired? Do you maintain a table of all
>permutations and use x as index to it?
You simply multiply by 16, then by 15, then by 14, and so on, each
time dividing by 16! and using the result in the classical shuffling
algorithm and keeping the remainder for the next multiplication.
Besides requiring multiplication and division, it requires
multi-precision arithmetic (say to hold a number the size of 256! in a
variable).
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Shamir's Discover: to those in the know
Date: Fri, 07 May 1999 12:23:46 -0500
Robert Harley wrote:
> I think the lesson here is that ECDLs are an ideal problem as long as
> you stick to randomly chosen ones with a large prime dividing the
> number of points. If you go and pick some ultra-special curves you
> are likely to get bitten sooner or later. Doesn't matter if it makes
> your arithmetic faster or counting points easier or falls under some
> patent you hold. Just don't do it, 'cause if you do all bets about
> security are off.
Exactly. So far the Koblitz curves are only reduced by sqrt(m) in
a field of GF(2^m) from the large prime. That's not too many more
bits to get good security, but I agree that random curves with
large primes are the ideal.
> Anybody interested in solving the next Certicom problem?
YES! But I thought 102 was already done?
> It is in the field GF(2^97) and the curve is not defined over any
> small subfield so it ought to take about 4 x 10^14 elliptic curve
> operations.
>
> I've got code to solve it ready to run that does about 110 K
> operations per second on a 450 Mhz Pentium II.
>
> It does 85 K on a 333 MHz UltraSparc with Sun's 32-bit compiler but
> 200 K with their new 64-bit compiler (64 bit registers really help!)
>
> It does about 350 K on a 500 MHz Alpha 21164 and 450 K on the new 21264.
>
> If people out there with fast machines are interested, let me know!
Well, I don't have a fast machine yet. But when Kryotech comes
out with their 1GHz K7 ("real soon now") I will be real happy to
join the chase.
> Assuming there's enough interest i.e., hundreds of machines, we can go
> ahead. There's prize money of $5000 to be won which would go to a
> good cause (before we gave $4000 to the Free Software Foundation and
> the rest to the people who found the two halves of the solution).
Seems appropriate. Keep posting, so far I've not been able to
help in many of these things because my toys are way too slow to
be useful. by the end of the year I hope to change that!
Patience, persistence, truth,
Dr. mike
------------------------------
Date: Thu, 06 May 1999 09:57:11 -0400
From: [EMAIL PROTECTED]
Subject: Re: Random permutation
Mok-Kong Shen wrote:
>
> A problem raised in another thread is whether it is possible e.g.
> to generate a random permutation of [0, 15], given only a random
> generator for [0, 15] and no generator for [0, 14], etc. One way I
> can think of is quite trivial: One obtains successive outputs from
> the generator and discards duplicates until one gets 16 numbers.
>
> Question: Are there more efficient ways of achieving the same goal?
Yes, but only slightly. As described above getting 16 samples is
expected to require roughly (N^2)/2 samples from the original generator.
To create a subset generator the best approach is to constrain the
outputs while preserving fairnesss.
One way to do this is to discard samples over the largest multiple of
the subset size, and use modulus on the samples less than that
multiple. Thus you'll discard only a few samples. This requires a
division, a multiplication, and a modulus but it is useful if samples
are expensive.
If samples are not expensive the most efficient algorithm is to mask
each sample and discard after masking. For example:
int subsample( int subN /* we want 0..subN-1 */ )
{
int mask = bit_mask( -bit_width( subN ) ); // takes O(log N)
int result;
do { // expect two iterations on average
result = sample() & mask;
} while ( result >= subN );
return( result );
}
For 4-bit numbers it hardly matters. For 32-bit numbers it matters a
lot.
------------------------------
Date: Fri, 07 May 1999 13:44:53 -0400
From: Emmanuel BRESSON <[EMAIL PROTECTED]>
Subject: Re: Little Irish girl's algorithm?
Hi Dan,
I said :
NO paper has been released. (as far as I know). Maybe you can forget this story.
Emmanuel
> >Well, We can think this was a good (?) joke, since no paper has been released
> >until now....
> >Emmanuel
> So there is a paper published after all? Is there an online version or
> available for download?
> -Dan
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Shamir's Discover: to those in the know
Date: Fri, 07 May 1999 18:23:25 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (DJohn37050) wrote:
> Schoof's algorithm to count points on an elliptic curve is an eighth order
> algorithm and is one of the most complicated I have ever come across in
> practice.
It's been improved to 6th order.
Try coding the Cyclotomy primality test, if you think Schoof's algorithm is
complicated! Or the entire suite of code needed for the Number Field Sieve.
> Don Johnson
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Shamir's Discover: to those in the know
Date: 7 May 1999 18:45:51 GMT
When I talked about the ECDLP, I meant it as it is used in cryptography, with
the known weak cases tossed out. For example, X9.62 ECDSA requires a large
prime subgroup and excludes the MOV-attackable (including supersingular) and
anomalous curves.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Shamir's Discover: to those in the know
Date: 7 May 1999 18:47:39 GMT
For a viewpoint on Twinkle from another crypto company see
http://www.certicom.com/press/shamir.htm.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Shamir's TWINKLE Factoring Machine
Date: 7 May 1999 18:53:00 GMT
Well, let's see now, a while back the annual NSA retreat was entirely devoted
to discussing ECC. I was not one, but the reason I know this is all the
attendees got a t-shirt that had an elliptic curve on it. Draw your own
conclusions.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Random permutation
Date: 7 May 1999 10:15:59 -0500
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>Volker Hetzer wrote:
>> > Question: Are there more efficient ways of achieving the same goal?
>> Like modulo?
>The problem is that there is a non-zero chance that one has to
>wait very long till one gets the result. (It should be mentioned
>that one needs to get only 15 distint numbers, the 16th being
>then unique.)
This is unavoidable. Suppose one wants to generate uniform
random numbers among 0,1,2. Then the procedure which minimizes
the probability of using more than k bits simultaneously for
all k is to look at pairs of bits until the base-2 number is
one of the above. This type of tail behavior is the best that
can be done.
--
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: Lars Hohmuth <[EMAIL PROTECTED]>
Subject: East German encyption code?
Date: Fri, 07 May 1999 14:03:49 -0500
According to a newspaper article in Germany's Welt (
http://www.welt.de/990508/0508s301.htm ), someone at the BStU, the
office working through the archive of the former east German secret
police managed to crack their encryption codes.
Does anyone have an idea what they were using?
Thanks,
Lars
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: comp.dcom.vpn
Subject: Re: Crypto export limits ruled unconstitutional
Date: Fri, 07 May 1999 19:46:49 GMT
William Hugh Murray <[EMAIL PROTECTED]> wrote, in part:
>Where is David Sternlight when we really need him? How are we to
>understand the significance of this without his wise council?
His wise counsel is provided in a posting to talk.politics.crypto, in
which he notes that the particular court in question had had a low
batting average as far as being upheld on appeal, and he also notes
that he won't be sticking around to read or answer the many personal
attacks he expects to encounter as a result of showing his face...
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>
Subject: Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO
Date: Fri, 07 May 1999 19:45:28 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> SCOTT19U.ZIP_GUY wrote:
> >
>
> > > You never know what kind of files are going to be compressed by
> > > your program. Someone might try to compress ANY binary file with
> > > that. So you can't ignore some cases because they are rare in your
> > > opinion. Consider an extremely unbalanced tree with 8 nodes such
> > > that each right branch (taking 1) leads to a terminating node. Then
> > > 8 0's is a valid symbol. Well, in this case you could mirror the
> >
> > It handles the case of 8 0's. The tree is such that there is
> > never a symbol made up of all zeros less than eight.
>
> (I suppose you wanted to say 'never a symbol containing 8 or more
> zeros as prefix.)
No I meant table is such that will be always one token (symbol) that
has eight of more zeros. But the table will never have a symbol with
less than 8 zeros.
>
> >
> > > tree and avoid the situation. But you are handling 256 symbols and
> > > the tree is constantly being updated. Of course, you could build
> > > in a barrier while building the tree in order to avoid 8 0's being
> > > the code of a valid symbol. But is then the tree optimal? Perhaps
Yes I actually did think of this but rejected it for 2 reasons.
One I have code to handle the 8 zero case. And secondly to avoid
8 zero's (the starting human tree which is for 256 characters all
have exactly 8 bits total) case some of the symbols would have
more than 8 bits and this is not what I wanted to do.
However I feel that one could do what you state. I just
went down a different path and I hope you and others try various
paths. I am sure mine is not the only way.
> >
> > Yes the tree is optimal since there is always more than tree that
> > preserves same symbol lengths.
>
> >
> > > you could find some way in arbitrairy situations to achieve
> > > that similar to what I illustrated above. But that would make your
> > > program logic unnecessarily complicated. And I am not sure that you
> > > can easily show that the optimality is always preserved.
> >
> > Yes I am sure the logic is somewhat complicated but that is
> > what computers are made for.
>
> This effort to check for avoiding the occurence of 8 0's as prefix
> can be saved if you have an EOF in my sense.
>
Yes but I think it makes files longer.
see comment after next paragraph.
>
> This 'hanging around' is meant for my EOF. One assumes from the
> very beginning that the input file contains such an EOF (outside of
> 0 -255) with the lowerst frequency than any actual symbols. In
> all the updates of the Huffman table one takes that into consideration.
> As the tree gets dynamically modified, it may or may not have
> the code assigned to it changed. But that doesn't matter. At end
> of the input file one then output the code of EOF and fill with
> anything after that to byte/word boundary. This would be my scheme.
> What do you mean by 'any file could be treated as decompressed file
> of another'? Do you mean that the code of my EOF has no correspondence
> to any actual symbol in the range [0, 255]? But neither does the
> ensemble of filling bits of 0's that you introduce at the end.
>
We seem to get to this point over and over and over. I don't
think you know what I am driving at. You can use your EOF scheme
if you want but I don't think it would be secure for 2 reasons.
YOur compressed files we be longer ( write code and we can test this).
Second it lacks the property that I keep trying to explain. You
don't have to agree but I had at least hoped you would understand
what I state but I think you still don't see it. So here it is
again
THE SENDER
the user compress file A to get file B ( buy what ever compression
method). The user then takes file B and encrypts it to file C using
a secret key known only to him and the reciver.
THE RECIEVER
gets file C uses shared secret key to decrypt to file B and
then decompresses using matching routine of compression to
get file A. (A may be ascii or may be binary just a file).
THE SPOOKS
They have all the programs used. They have file C but not the
secret key. They try to guess a key they then decrpt using
that wrong key. They get a file D. They notice that when they
decompress file D to an E and then compress file E to F they
notice that F and D are not the same. There fore they know
that D is not your C which they can't see. It is my view
(it need not be yours) that I would prefer and compress/decompression
routines that always force F and D to be the same. Even when
any possible wrong key is used for the decryption.
> At your place I would try to use, as said, a file of extreme
> (the opposite of uniform) frequency distribution to 'exercise'
> the program to its limit.
>
I have tested with large constant files. And large zipped files
so far so good.
David A. 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
------------------------------
From: SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.privacy
Subject: Re: The simplest to understand and as secure as it gets.
Date: Fri, 07 May 1999 19:50:46 GMT
In article <7guql6$6ie$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
>
> > No it is not a OTP but there is a write up by a guy at my site.
> > There are links to the code at my webpage. I hope your in the
> > US so you can get scott19u it is better. But the main difference
> > is I use 19 bit fields in it while the 16u uses 16 bit fields.
>
> 19 bit fields? You mean GF(2**19)? Isn't that slower? Just a wondering..
>
Yes 19 bit fields it was a challage. Since it uses a 19x19 S table
and the key can be over one million bytes. A scott20u would not allow
the key to be written on a floppy. Take a look at my contests.
And yes it is dirt slow on my 486. But runs fast on some friends machines.
> I am in Canada (eh?) so I will take a peek at your code this weekend when I
> have the time (I am at school right now, hehe, what else if grade 13 comp sci
> for?)
>
> I will get back to you.... :)
>
> Tom
> --
> PGP public keys. SPARE key is for daily work, WORK key is for
> published work. The spare is at
> 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
> 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
>
David A. 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
------------------------------
From: "Majestic" <[EMAIL PROTECTED]>
Subject: Netscape Encryption Algorithm
Date: Fri, 7 May 1999 20:51:15 +0200
Hi
The recent flaw in Netscape Navigator allows a user to decrypt the password
stored in the preferences file. I would like to know which encryption
algorithm is used in Netscape, since that DES is not used.
Please put your ideas in my mailbox...
Regards,
Majestic
[EMAIL PROTECTED]
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Shamir's Discover: to those in the know
Date: 7 May 1999 19:59:14 GMT
Medical Electronics Lab <[EMAIL PROTECTED]> wrote:
>> It does 85 K on a 333 MHz UltraSparc with Sun's 32-bit compiler but
>> 200 K with their new 64-bit compiler (64 bit registers really help!)
>>
>> It does about 350 K on a 500 MHz Alpha 21164 and 450 K on the new 21264.
>>
>> If people out there with fast machines are interested, let me know!
> Well, I don't have a fast machine yet. But when Kryotech comes
> out with their 1GHz K7 ("real soon now") I will be real happy to
> join the chase.
I just purchased a P3/500. Yes, I know, not such a great idea.
Except it was the same price as the P2. :-)
Tell me where to find the code and I'll download it, skim it,
then try it out. If there's a distributed.net style crack going
on, please let me know.
-David Molnar
------------------------------
From: SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>
Subject: THE DIRECTION OF CRYPTO IN THE U.S.
Date: Fri, 07 May 1999 19:59:54 GMT
I notice most freedom loving people are happy that the
court tried to make a blow for freedom. But I fear it will
be short lived. Just like when the Clipper chip died the
NSA (in my view) got the AES thing rolling so they could
effectively do the some thing. Don't get me wrong maybe
there are good small key crypto systems but does anyone
over the age of 40 really think the NSA would allow it to
win the contest.
Even if the Supreme Court upholds our freedoms bills like
the so called SAFE encryption act will be passed as if they
are helping but it will end up business as usually and more
freedoms down the toilet in this country. But at least most
dolts we be dumb enough to believe we are getting more freedom
as what little freedoms we have get pissed away.
David A. 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
******************************
