Cryptography-Digest Digest #294, Volume #14 Fri, 4 May 01 18:13:01 EDT
Contents:
Re: Message mapping in EC. (Doug Kuhlman)
Re: Best encrypting algoritme (Jim Gillogly)
Re: Random and not random (Mok-Kong Shen)
Re: OAP-L3: The absurd weakness. (Anthony Stephen Szopa)
Re: OAP-L3: The absurd weakness. (Tom St Denis)
WHY I HATE BOSCHLOO (Fight Boschloo)
Re: Encryption Algorythm (EE)
Re: Best encrypting algoritme (Bill Unruh)
Re: Encryption Algorythm (Tom St Denis)
Re: Encryption Algorythm (Scott Fluhrer)
From: Doug Kuhlman [EMAIL PROTECTED]
Subject: Re: Message mapping in EC.
Date: Fri, 04 May 2001 13:58:03 -0500
Mike Rosing wrote:
Doug Kuhlman wrote:
Seems like they were lucky (and/or more is going on than meets the
eye). We expect approximately 1/2 of the x values to be on the curve
(semi-rigorously, due to Hasse-Weil). With 4 play bits, you would get
16 possible x-values. A priori, we would expect to see about 153 (10
million / 2^16) misses.
With five bits, you get 32 possible values for x, which means about 1 in
4 trillion values is expected (with no other thought) to miss being on
the curve.
You lost me. If 4 bits is 1/2^2^4 then 5 bits is 1/2^2^5 is 1 in 4 billion.
Or am I missing something?
My typo. You're supposed to read what I *mean*, not what I say! (yes,
that's tongue-in-cheek). You're right, of course. 2^2^5 is 4 billion,
not 4 trillion.
I am, of course, assuming that the position of the play bits is fixed,
so that there is no ambiguity on the receiver's end. Allowing for more
movement of these bits increases the chances of success but seems to
needlessly complicate the system.
Yeah, they have to be fixed. Using more play bits is better because you can
introduce randomness, but that's a different problem.
Yep.
I am quite sure many mathematicians *have* looked at it. And, yes, it
is quite difficult to prove in practice -- at least as difficult as
results about densities of primes. There are lots of factors that go
into trying to rigorously prove that a point exists in every Hamming
sphere of radius n.
Where would I find references? I've been totally guessing at this, am
not a mathematician, and don't know what keywords to look for. Any mathematicians,
please chime in!
Well, I am a mathematician. I've looked into it. For a while, I
thought it might be my dissertation topic, but it's still too hard a
problem. My advisor looked into it. I know guys like Menezes and
Koblitz have asked that question.
Now, as far as publications, I don't know of any. It's pretty hard to
publish (well, uhh... we looked at this problem. And, well, we got the
obvious heuristic value. But, well, that's about it.) Keywords might
be elliptic curve (too many references), points, Hamming sphere
wouldn't be bad, but my guess is very few (if any) papers include both
Hamming sphere and elliptic curve.
I do accept the empirical *evidence* that it works, though. There is
also some sound mathematical reasoning why it should. Proof is a ways
away, though.
Hey, it worked for the 4 color map :-) In fact, that's kind of how I started
looking at it. I plotted rows of consecutive x values to see which half
plane was covered, and seemed to be randomly distributed. After some shifting,
I saw some patterns, but I couldn't correlate them to anything other than
my brain saw patterns. I doubt I could follow the math, but I'd still be
interested in any published papers.
Yeah, but the 4-color problem has a lot of limiting structure that
discussions of Hamming spheres in elliptic curves don't. For one thing,
the size of the base field is allowed to be arbitrarily large, which
leads to an asymptotic estimate, which is always harder to do. The
rules of mappings are also very well-established, whereas point density
locations in ECs aren't (to my knowledge, anyway).
A more fundamental problem is that a Hamming sphere is not a very nice
abstract algebraic object. It doesn't obey rules like we want it, too.
This makes proof extremely difficult.
Since the proof appears to be very difficult and the heuristic appears
to work pretty well, it's hard to justify why anyone should get into the
problem right now.
If you do succeed in finding anything on this topic, though, please let
me know, as I would be quite interested.
Doug
--
From: Jim Gillogly [EMAIL PROTECTED]
Subject: Re: Best encrypting algoritme
Date: Fri, 04 May 2001 12:13:14 -0700
david wrote:
Im making a backup program, and I don'treally know what is the most secure
algoritme, im using Rijndael rigth now and using 256 bit keys, are rc6
stronger or are there others??
The strength of Rijndael will not be the weakest part of your
backup system. You don't need to shop for a more secure algorithm.
--
Jim Gillogly
Sterday, 13