Cryptography-Digest Digest #75, Volume #14 Wed, 4 Apr 01 11:13:01 EDT
Contents:
Re: PRNG analysis, runs of zeroes (Vincent Quesnoit)
Re: PRNG analysis, runs of zeroes (Vincent Quesnoit)
Re: quick LFSR question (really simple question) (Phil Carmody)
(Slightly Off) BSD file wiping code (Joe H Acker)
Re: Factoring.... (Mark Wooding)
Re: patent this and patent that (Phil Carmody)
Re: quick LFSR question (really simple question) ("Tom St Denis")
Re: patent this and patent that (Phil Carmody)
Re: keys and random (Phil Carmody)
Re: His cat would love to sodomize sick toilet paper ("Frog2000")
Re: Winter loves potatoes ("Frog2000")
Re: patent this and patent that ("Tom St Denis")
Re: keys and random ("Tom St Denis")
Re: keys and random (Phil Carmody)
Re: Problematic Patent (Yechuri)
Re: quick LFSR question (really simple question) (Phil Carmody)
Re: quick LFSR question (really simple question) ("Tom St Denis")
Re: keys and random ("Tom St Denis")
Re: Royalty free use of Mars (Kent Briggs)
Re: keys and random (Mark Wooding)
----------------------------------------------------------------------------
From: Vincent Quesnoit
Subject: Re: PRNG analysis, runs of zeroes
Date: Wed, 04 Apr 2001 13:52:36 +0200
Reply-To: [EMAIL PROTECTED]
Tom St Denis a �crit :
> "Steve Portly" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > I finally got around to doing some large volume analysis of my PRNG.
> > Since it takes the better part of a day to generate a trillion bit file
> > I had been putting this off. It seems to me that any quantity of random
> > bits should exhibit a predictable number of runs of either zero or 1.
> > For very large volume tests finding long runs in your data should rule
> > out many deterministic patterns.
> >
> > In this context, (for gaming quality randomness) what would you expect
> > the longest runs to be in a trillion bit sample?
>
> Simple the probability of any n-length run is simply (1/2)^n if the bits are
> decorrelated. Which means in your trillion (2^40 for simplicity sake) you
> should expect about 2^39 runs of 1, 2^38 runs of 2, etc...
I would not say it was that simple.
The probability you state corresponds to the case when you create independant
series of n bits. In the case he's talking about, a sequence can start from any
point in the billion bits, thus it can overlap several diffferent series of n
bits.
To find the probability of any n run, you need to do a little more math than
that.
For instance, there is a 1/2^1billion probability of NOT having a 1-long run of
ones (2^1 billion possible sequences, one of them has no ones).
For not having a 2-long run it would be :
(1+1billion+(1billion/2)*(1billion-1))/2^1billion
And so on and so forth.
You need to compute how any numbers in the 1 ... 2^1billion range have a certain
run length of bits to get an answer to the question.
Vincent Quesnoit
------------------------------
From: Vincent Quesnoit
Subject: Re: PRNG analysis, runs of zeroes
Date: Wed, 04 Apr 2001 14:01:10 +0200
Reply-To: [EMAIL PROTECTED]
Vincent Quesnoit a �crit :
> Tom St Denis a �crit :
>
> > "Steve Portly" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > I finally got around to doing some large volume analysis of my PRNG.
> > > Since it takes the better part of a day to generate a trillion bit file
> > > I had been putting this off. It seems to me that any quantity of random
> > > bits should exhibit a predictable number of runs of either zero or 1.
> > > For very large volume tests finding long runs in your data should rule
> > > out many deterministic patterns.
> > >
> > > In this context, (for gaming quality randomness) what would you expect
> > > the longest runs to be in a trillion bit sample?
> >
> > Simple the probability of any n-length run is simply (1/2)^n if the bits are
> > decorrelated. Which means in your trillion (2^40 for simplicity sake) you
> > should expect about 2^39 runs of 1, 2^38 runs of 2, etc...
>
> I would not say it was that simple.
> The probability you state corresponds to the case when you create independant
> series of n bits. In the case he's talking about, a sequence can start from any
> point in the billion bits, thus it can overlap several diffferent series of n
> bits.
> To find the probability of any n run, you need to do a little more math than
> that.
> For instance, there is a 1/2^1billion probability of NOT having a 1-long run of
> ones (2^1 billion possible sequences, one of them has no ones).
> For not having a 2-long run it would be :
> (1+1billion+(1billion/2)*(1billion-1))/2^1billion
> And so on and so forth.
> You need to compute how any numbers in the 1 ... 2^1billion range have a certain
> run length of bits to get an answer to the question.
>
> Vincent Quesnoit
(1+1billion+(1billion/2)*(1billion-1))/2^1billion
is wrong of course, there are a littel more combinations than that which do not
exhibit a sequence of two ones.
I only took into account results with 1 bit set to one and two bits set to one, you
have to compute arrangements up to 1/2 billion bits set to ones. But i'm sure you
can come up with a nice formula.
Vincent Quesnoit
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: quick LFSR question (really simple question)
Date: Wed, 04 Apr 2001 12:53:04 GMT
Tom St Denis wrote:
>
> I am using an LFSR on my i8032 for a test... I need to know if this is good
> C code (i.e does the right LFSR)
>
> /* expand using LFSR (0,3,9,10,12) */
> for (x = 12; x < 76; ++x)
> tmp[x] = tmp[x-12] ^ tmp[x-10] ^ tmp[x-9] ^ tmp[x-3];
>
> The #'s represent the taps given by the LFSR maker I have found on the web.
> I want to know if I interpreted the taps correctly.
Congratulations, Tom, on creating an amazing thread! Who'd have guessed
a simple question could yield what it did.
The 'S' in LFSR is "shift". I think you're not 'shifting' properly. I
know you're using a sliding window, but you're not pushing the feedback
into the new position.
The register is 13 wide [0..12].
Therefore you want to take the 5 tapping points, and combine them into
the next position
for(x=12; x<76-1; ++x)
tmp[x+1] = tmp[x-12] ^ tmp[x-10] ^ tmp[x-9] ^ tmp[x-3] ^ tmp[x-0]
What you have implemented I'd view as LFSR(2,8,9,11) which has length 12
bits [0..11].
However, this _could_ be simply a notational thing.
HTH,
Phil
------------------------------
From: [EMAIL PROTECTED] (Joe H Acker)
Subject: (Slightly Off) BSD file wiping code
Date: Wed, 4 Apr 2001 15:00:54 +0200
I'm looking for file wiping code for Mac OS X, which essentially should
work like file wiping on any BSD systems. (Please correct me if that's
wrong, OS X uses HFS+ and there might be other differences to standard
BSD file systems I am not aware of.)
Preferably, the "Gutman" overwrite with some cache flushing at OS
level... Does anyone got a reference to such code?
Thanks,
Erich
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Factoring....
Date: 4 Apr 2001 13:06:43 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> No you have that backwards. Finding square roots is as hard as factoring.
> Factoring can be very easy if for example your number is B-Smooth :-)
Actually, factoring is just as hard as finding square roots.
If you can factor, you can find square roots, by doing it mod each prime
factor and recombining the results using CRT.
If you can find square roots, you can factor. Let n be some composite.
Choose some x in Z^*_n. Use your square-root finding algorithm to find
x' where x'^2 = x^2 = y (mod n). Because n is composite, y will have at
least four square roots, so you have at least a 1/2 probability that x'
is `interesting' -- i.e., x' != x and x' != -x (mod n). If this is the
case, then gcd(x - x', n) is a nontrivial factor of n.
Square roots of unity are particularly interesting. It's by finding a
nontrivial square root of unity that you can factor an RSA modulus by
knowing both public and secret exponents.
-- [mdw]
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: patent this and patent that
Date: Wed, 04 Apr 2001 13:09:33 GMT
Vernon Schryver wrote:
>
> In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>
> > ...
> >Please. Adding? XOR? Patented? I don't think so....
>
> How can someone who is neither uniformed nor short of intellectual
> honesty make such a statement?
>
> Recall the infamous XOR cursor patent. (What was its number? Asking
There is one at
http://www.delphion.com/details?pn=US05471570__
<<<
US5471570:Hardware XOR sprite for computer display systems
Rackley; Darwin P. , Boca Raton, FL
West; R. Michael P. , Colchester, VT
International Business Machines Corporation, Armonk, NY
Nov. 28, 1995 / Dec. 30, 1993
Method and apparatus for adjusting the color of the sprite in display
systems, so that the sprite is always distinctively visible irrespective
of the underlying displayed data.
...
>>>
This is a color version of the old B/W idea. Maybe there are links back
from this one to the original monochrome one.
> http://www.delphion.com/ for "cursor, xor" produces wonderful items
> including some that would have been old news to me if I'd heard of
> them 10 years before they were filed. but I don't or recognize see
> the infamous XOR cursor among them.)
I searched for 'pixel xor', but it appears that the key word is possibly
'sprite'
Phil
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: quick LFSR question (really simple question)
Date: Wed, 04 Apr 2001 13:18:47 GMT
"Phil Carmody" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Congratulations, Tom, on creating an amazing thread! Who'd have guessed
> a simple question could yield what it did.
>
> The 'S' in LFSR is "shift". I think you're not 'shifting' properly. I
> know you're using a sliding window, but you're not pushing the feedback
> into the new position.
> The register is 13 wide [0..12].
> Therefore you want to take the 5 tapping points, and combine them into
> the next position
>
> for(x=12; x<76-1; ++x)
> tmp[x+1] = tmp[x-12] ^ tmp[x-10] ^ tmp[x-9] ^ tmp[x-3] ^ tmp[x-0]
>
> What you have implemented I'd view as LFSR(2,8,9,11) which has length 12
> bits [0..11].
Ok, well it's ot now since I changed the design to avoid the LFSR but if I
wanted to have a 12-stage LFSR given by (0,3,9,10,12) I would use the code
you gave?
Tom
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: patent this and patent that
Date: Wed, 04 Apr 2001 13:21:28 GMT
> In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>
> > ...
> >Please. Adding? XOR? Patented? I don't think so....
Oooh - I've just found an 'adding and subtracting' patent!
http://www.delphion.com/details?&pn10=US04719590
Best thing about this is that at least one claim is factually _wrong_.
Any coder should spot the error as soon as s/he reads it (think
'arrays')
Happy hunting!
Hmmm, anyone seen the "lookup table for sin and cosine" patent?
Phil
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: keys and random
Date: Wed, 04 Apr 2001 13:49:41 GMT
Mark Wooding wrote:
>
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> > > Generating Lim-Lee primes is only a little harder than generating random
> > > primes, and the result is as good as a Sophie-Germain prime against any
> > > attack I know of. Performance in use is also better, since your
> > > exponents are shorter.
> >
> > What are LL primes? AFAIK SG primes are the strongest against any index
> > calculus based method because of the large subgroup.
>
> I didn't think that index-calculus methods cared much about the subgroup
> structure of field.
>
> A Lim-Lee prime p = 2 q_0 q_1 ... q_n + 1 where the q_i are all `large'
> -- large enough to dissuade collision-finding attacks such as Pollard's
> rho. Thus, except for the trivial subgroup, all subgroups are large
> enough not to be a problem. And you don't have to worry about evil
> people forcing you into smooth-ordered subgroups, because there aren't
> any.
>
> You generate Lim-Lee primes by making a collection of q_i candidates and
> multiplying them together in various combinations until you get a prime
> out the far end. GnuPG generates Lim-Lee primes for DSA and ElGamal, if
> I remember correctly. Catacomb also generates Lim-Lee primes if you so
> wish.
Nice idea, I'd never heard of them (LL) before. Am I right in thinking
that the 'security' is increased with larger min(q_i)? So if you can
find 'about half length' q_0 and q_1 with 2.q_0.q_1+1 prime then you're
happiest.
Basically are you looking for p-1 to be non-factorable apart from the
trivial factor 2? So you want a defence against not just Rho but SQUFOF,
QS, ECM too?
Phil
------------------------------
From: "Frog2000" <[EMAIL PROTECTED]>
Crossposted-To: soc.men,alt.security.pgp
Subject: Re: His cat would love to sodomize sick toilet paper
Date: Wed, 4 Apr 2001 09:49:37 -0400
Isn't there a talk.crypt.politics, or something like that? :)
--
http://welcome.to/speechsystemsfortheblind
"Anonymous" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Frog loves to burn most of politically correct jews
> [STATS] Austria wants TLA
> [STATS] Cracow needs carrots
> Green wants republicans
> 0,4727682 0,2866326 0,3427811 -2001/03/25 23:59:31-
> Script-Kiddie MASTER of APAS/ADRU/SM/AUK
> For a 21st Century completely REMAILER-FREE
> That CRAP brought to you by request from Thomas J. BOSCHLOO
> [EMAIL PROTECTED]
> TLA requires to write more of pommies
------------------------------
From: "Frog2000" <[EMAIL PROTECTED]>
Crossposted-To: soc.men,alt.security.pgp
Subject: Re: Winter loves potatoes
Date: Wed, 4 Apr 2001 09:50:47 -0400
--
http://welcome.to/speechsystemsfortheblind
"Anonymous" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Gates probably wants CIA
Nah, they pay well, but he makes better money.
> 0,5851809 0,5951465 0,7299836 -2001/03/25 23:37:34-
> Script-Kiddie MASTER of APAS/ADRU/SM/AUK
> For a 21st Century completely REMAILER-FREE
> That CRAP brought to you by request from Thomas J. BOSCHLOO
> [EMAIL PROTECTED]
> [INFO] Shinn sure used some republicans
> Re: My sister absolutely asks to fist-fuck most of Pangborn
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: patent this and patent that
Date: Wed, 04 Apr 2001 13:54:35 GMT
"Phil Carmody" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> > In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]>
wrote:
> >
> > > ...
> > >Please. Adding? XOR? Patented? I don't think so....
>
> Oooh - I've just found an 'adding and subtracting' patent!
>
> http://www.delphion.com/details?&pn10=US04719590
>
> Best thing about this is that at least one claim is factually _wrong_.
> Any coder should spot the error as soon as s/he reads it (think
> 'arrays')
> Happy hunting!
>
> Hmmm, anyone seen the "lookup table for sin and cosine" patent?
Thank you guys for making my point and giving me a good laugh..."how to
exercise a cat...".
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: keys and random
Date: Wed, 04 Apr 2001 13:56:38 GMT
"Phil Carmody" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Mark Wooding wrote:
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> >
> > > > Generating Lim-Lee primes is only a little harder than generating
random
> > > > primes, and the result is as good as a Sophie-Germain prime against
any
> > > > attack I know of. Performance in use is also better, since your
> > > > exponents are shorter.
> > >
> > > What are LL primes? AFAIK SG primes are the strongest against any
index
> > > calculus based method because of the large subgroup.
> >
> > I didn't think that index-calculus methods cared much about the subgroup
> > structure of field.
> >
> > A Lim-Lee prime p = 2 q_0 q_1 ... q_n + 1 where the q_i are all `large'
> > -- large enough to dissuade collision-finding attacks such as Pollard's
> > rho. Thus, except for the trivial subgroup, all subgroups are large
> > enough not to be a problem. And you don't have to worry about evil
> > people forcing you into smooth-ordered subgroups, because there aren't
> > any.
> >
> > You generate Lim-Lee primes by making a collection of q_i candidates and
> > multiplying them together in various combinations until you get a prime
> > out the far end. GnuPG generates Lim-Lee primes for DSA and ElGamal, if
> > I remember correctly. Catacomb also generates Lim-Lee primes if you so
> > wish.
>
> Nice idea, I'd never heard of them (LL) before. Am I right in thinking
> that the 'security' is increased with larger min(q_i)? So if you can
> find 'about half length' q_0 and q_1 with 2.q_0.q_1+1 prime then you're
> happiest.
> Basically are you looking for p-1 to be non-factorable apart from the
> trivial factor 2? So you want a defence against not just Rho but SQUFOF,
> QS, ECM too?
No it's not to avoid factoring the # (it's prime anyways) It's to avoid
discrete logs in small subgroups. And yes as min(q_i) gets larger you get a
larger minium subgroup and more security using currently known methods.
Tom
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: keys and random
Date: Wed, 04 Apr 2001 14:17:04 GMT
Tom St Denis wrote:
> > Basically are you looking for p-1 to be non-factorable apart from the
> > trivial factor 2? So you want a defence against not just Rho but SQUFOF,
> > QS, ECM too?
>
> No it's not to avoid factoring the # (it's prime anyways) It's to avoid
Blimey, quick reply!
I did have "p-1 to be non-factorable" though. p prime is a given.
> discrete logs in small subgroups. And yes as min(q_i) gets larger you get a
> larger minium subgroup and more security using currently known methods.
Ah, discrete logs aren't anything I've mucked around with in the past,
dunno what's good, and what's bad.
Phil
------------------------------
From: [EMAIL PROTECTED] (Yechuri)
Date: 04 Apr 2001 14:17:05 GMT
Subject: Re: Problematic Patent
Actually, in the field of hardware engineering as well there are these
"obvious" patents that are a headache for smaller companies.
Somebody should organize a non-profit organization to fight absurd patents on
behalf of the public. Right ?
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: quick LFSR question (really simple question)
Date: Wed, 04 Apr 2001 14:49:09 GMT
Tom St Denis wrote:
> "Phil Carmody" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Congratulations, Tom, on creating an amazing thread! Who'd have guessed
> > a simple question could yield what it did.
> >
> > The 'S' in LFSR is "shift". I think you're not 'shifting' properly. I
> > know you're using a sliding window, but you're not pushing the feedback
> > into the new position.
> > The register is 13 wide [0..12].
> > Therefore you want to take the 5 tapping points, and combine them into
> > the next position
> >
> > for(x=12; x<76-1; ++x)
> > tmp[x+1] = tmp[x-12] ^ tmp[x-10] ^ tmp[x-9] ^ tmp[x-3] ^ tmp[x-0]
> >
> > What you have implemented I'd view as LFSR(2,8,9,11) which has length 12
> > bits [0..11].
>
> Ok, well it's ot now since I changed the design to avoid the LFSR but if I
> wanted to have a 12-stage LFSR given by (0,3,9,10,12) I would use the code
> you gave?
12-stage?
0-12 is _13_ bits remember.
The feedback in mine is putting into [13] what would go on [0], and the
window thence becomes [1..13]
So I think we must have a terminological discrepancy here. I wouldn't
call LFSR(0,3,9,10,12) "12-stage", for a start.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: quick LFSR question (really simple question)
Date: Wed, 04 Apr 2001 14:52:09 GMT
"Phil Carmody" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> > "Phil Carmody" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > Congratulations, Tom, on creating an amazing thread! Who'd have
guessed
> > > a simple question could yield what it did.
> > >
> > > The 'S' in LFSR is "shift". I think you're not 'shifting' properly. I
> > > know you're using a sliding window, but you're not pushing the
feedback
> > > into the new position.
> > > The register is 13 wide [0..12].
> > > Therefore you want to take the 5 tapping points, and combine them into
> > > the next position
> > >
> > > for(x=12; x<76-1; ++x)
> > > tmp[x+1] = tmp[x-12] ^ tmp[x-10] ^ tmp[x-9] ^ tmp[x-3] ^ tmp[x-0]
> > >
> > > What you have implemented I'd view as LFSR(2,8,9,11) which has length
12
> > > bits [0..11].
> >
> > Ok, well it's ot now since I changed the design to avoid the LFSR but if
I
> > wanted to have a 12-stage LFSR given by (0,3,9,10,12) I would use the
code
> > you gave?
>
> 12-stage?
> 0-12 is _13_ bits remember.
>
> The feedback in mine is putting into [13] what would go on [0], and the
> window thence becomes [1..13]
>
> So I think we must have a terminological discrepancy here. I wouldn't
> call LFSR(0,3,9,10,12) "12-stage", for a start.
Well the program I found asks the size in bits, I entered 12....
I think you ignore the 0 and move everything down one so it becomes
tmp[x - 11] ^ tmp[x - 9] ... etc
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: keys and random
Date: Wed, 04 Apr 2001 14:54:01 GMT
"Phil Carmody" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> > > Basically are you looking for p-1 to be non-factorable apart from the
> > > trivial factor 2? So you want a defence against not just Rho but
SQUFOF,
> > > QS, ECM too?
> >
> > No it's not to avoid factoring the # (it's prime anyways) It's to avoid
>
> Blimey, quick reply!
>
> I did have "p-1 to be non-factorable" though. p prime is a given.
>
> > discrete logs in small subgroups. And yes as min(q_i) gets larger you
get a
> > larger minium subgroup and more security using currently known methods.
>
> Ah, discrete logs aren't anything I've mucked around with in the past,
> dunno what's good, and what's bad.
Generally small sub-groups is a bad thing since it facilates simpler
discrete logs and some c.r.t math. Justl ike small factors is bad for
factoring.
Often people claim factoring is as hard as discrete log but I disagree. The
sieve step may take the same amount of time, but afaik (and I am most likely
wrong so please no cross burning!) the discrete log involves GF(p) math in
the matrix step to find the solution.
Tom
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: Royalty free use of Mars
Date: Wed, 04 Apr 2001 09:54:16 -0500
"M.S. Bob" wrote:
> Let's see, let's go to the MARS home page at IBM
> <http://www.research.ibm.com/security/mars.html>.
> Oh, what's the link at the top of the page...
>
> "MARS is now available worldwide under a royalty-free license from
> Tivoli.
Keep in mind that "royalty-free" does not necessarily mean totally free.
There could be an up-front license fee required and still be royalty-free.
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: keys and random
Date: 4 Apr 2001 14:59:41 GMT
Phil Carmody <[EMAIL PROTECTED]> wrote:
> Nice idea, I'd never heard of them (LL) before. Am I right in thinking
> that the 'security' is increased with larger min(q_i)? So if you can
> find 'about half length' q_0 and q_1 with 2.q_0.q_1+1 prime then you're
> happiest.
There are a number of different attacks, and you need to consider what
kind of numbers best resist each. Then you ensure that your final
number has the right balance of security.
Index-calculus attacks are best resisted by choosing large fields (big p).
Their precise structure doesn't matter much, as long as they're big.
You can resist collision-finding attacks (such as Pollard's rho) by
using a large-ish subgroup. Since collision-finding attacks are
square-root in the subgroup order, rather than subexponential in the
field characteristic, the subgroup order q_0 doesn't need to be anywhere
near as large as p. (We have q_0 as a factor of p, obviously. We
choose the q_0-order subgroup by picking our generator so that g^{q_0} =
1 (mod p). This should remind you of choosing DSA parameters.)
There are some sly active attacks against Diffie-Hellman exchanges and
similar which force values into different subgroups. You resist these
attacks by (a) noticing when something is in the trivial subgroup (1,
-1) and (b) making sure that it doesn't matter when this happens because
all the other subgroups are at least as difficult as your main one
anyway. Lim-Lee primes fit this bill perfectly -- you make sure that
q_i >= q_0 for all i.
> Basically are you looking for p-1 to be non-factorable apart from the
> trivial factor 2? So you want a defence against not just Rho but SQUFOF,
> QS, ECM too?
No. It's fine to publish the factors of p - 1, and indeed this is a
good way of giving other people confidence in your field. (Choosing p
large is the best way of preventing factoring of p - 1, and indeed of
(p - 1)/(2 q_0), since the best way of factoring numbers that large is
the GNFS, and its running time is determined solely by the size of the
thing being factored, not the size of the factors.)
The trick now is to balance your choices of the various parameters.
The reason that picking S-G primes is pointless is that the subgroup is
*way* too large compared to the field size -- difficulty of collision-
finding attacks is out of proportion compared to the ease of index-
calculus attacks.
The DSA recommendations are well-balanced. The subgroup order is 160
bits and the field is 1024 bits. Breaking this seems to be about 2^{80}
effort no matter what you do. (The original choice of 512 bits for
the field was too small.) SHA1, KEA and Skipjack are also well-balanced
components of the same system.
-- [mdw]
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
