1995-11-07 - Re: Photuris Primality verification needed

Header Data

From: “William Allen Simpson” <bsimpson@morningstar.com>
To: bal@martigny.ai.mit.edu
Message Hash: 66d7521e466a13b08d0a18813b98382709bf9e82889245c55f512598a913b315
Message ID: <1999.bsimpson@morningstar.com>
Reply To: N/A
UTC Datetime: 1995-11-07 15:31:52 UTC
Raw Date: Tue, 7 Nov 1995 23:31:52 +0800

Raw message

From: "William Allen Simpson" <bsimpson@morningstar.com>
Date: Tue, 7 Nov 1995 23:31:52 +0800
To: bal@martigny.ai.mit.edu
Subject: Re: Photuris Primality verification needed
Message-ID: <1999.bsimpson@morningstar.com>
MIME-Version: 1.0
Content-Type: text/plain


> From: "Brian A. LaMacchia" <bal@martigny.ai.mit.edu>
>    > Recently, someone asked for a smaller prime of only 512-bits for speed.
>    > This is more than enough for the strength of keys needed for DES, 3DES,
>    > MD5 and SHA.  Perhaps this would be easier to have more complete and
>    > robust verification as well.
>
> Our practical experiences with discrete logs suggests that the effort
> required to perform the discrete log precomputations in (a) is slightly
> more difficult than factoring a composite of the same size in bits.  In
> 1990-91 we estimated that performing (a) for a k-bit prime modulus was
> about as hard as factoring a k+32-bit composite.  [Recent factoring work
> has probably changed this a bit, but it's still a good estimate.]
>
Thanks.  I have added the [from Schneier] estimate

   e ** ((ln p)**1/2 * (ln (ln p))**1/2)

and number field sieve estimate

   e ** ((ln p)**1/3 * (ln (ln p))**2/3)

to the Photuris draft, with a small amount of explanation.

Hilarie Orman posted that 512-bits only gives an order of 56-bits
strength, 1024-bits yeilds 80-bits strength, and 2048 yields 112-bits
strength.  I do not have the facilities to verify her numbers.

As most of us agree that 56-bits is not enough (DES), the 512-bit prime
seems a waste of time and a tempting target.  I'd like to drop it, but
Phil is inclined to keep it with a disclaimer.

Bill.Simpson@um.cc.umich.edu
          Key fingerprint =  2E 07 23 03 C5 62 70 D3  59 B1 4F 5E 1D C2 C1 A2





Thread