### [Cfrg] Your Secret is Too Short (was: Is Diffie-Hellman Better Than We Think?)

Michael D'Errico <mike-list@pobox.com> Wed, 21 October 2020 15:31 UTC

Return-Path: <mike-list@pobox.com>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (localhost [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id 4736B3A0C45
for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 08:31:02 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -2.098

X-Spam-Level:

X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H3=0.001,
RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001]
autolearn=ham autolearn_force=no

Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key)
header.d=pobox.com header.b=mp2H7mGr;
dkim=pass (2048-bit key)
header.d=messagingengine.com header.b=pqUnDsBb

Received: from mail.ietf.org ([4.31.198.44])
by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id 89TQtzX5Ck-X for <cfrg@ietfa.amsl.com>;
Wed, 21 Oct 2020 08:30:59 -0700 (PDT)

Received: from out2-smtp.messagingengine.com (out2-smtp.messagingengine.com
[66.111.4.26])
(using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id B757C3A0BBE
for <cfrg@irtf.org>; Wed, 21 Oct 2020 08:30:59 -0700 (PDT)

Received: from compute4.internal (compute4.nyi.internal [10.202.2.44])
by mailout.nyi.internal (Postfix) with ESMTP id CD9BA5C0264
for <cfrg@irtf.org>; Wed, 21 Oct 2020 11:30:58 -0400 (EDT)

Received: from imap21 ([10.202.2.71])
by compute4.internal (MEProxy); Wed, 21 Oct 2020 11:30:58 -0400

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pobox.com; h=
mime-version:message-id:in-reply-to:references:date:from:to
:subject:content-type:content-transfer-encoding; s=fm1; bh=tnO1G
SxsRBjabnSqoPafYKu84RwvbekPwGlfwXZKueQ=; b=mp2H7mGrzO/+3eYk1NVae
5hMzJbUGiMZAjgTsjq5c1XBYjLPoXOKSLwpp6ERYYm1sptClQrOLDv0W936C5KR5
v6qEoLbH2/UrulaJwA9sWl7oJkBOpH/gbYxXqME+vhiUPMGFW1DXVchRA6uZrkzl
uUGsU8IXcl5Ung+Tt2N9KpzFjWRfkELRNj2mmKlfkrCfc1nz3WksLkH98MdKsrUy
q3aJ2jb4cG5d1T6WZixRE22Nz5VIBlC7uJ7mtzDYpNYxaJTTSkb9FaGOKsZBoxre
nQr5K4fhbgbVGOeQLnCKAFe/97B3MYz7VeJD+Tl8um1sRlAL2Odmmj6os8oDymgM
A==

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
messagingengine.com; h=content-transfer-encoding:content-type
:date:from:in-reply-to:message-id:mime-version:references
:subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender
:x-sasl-enc; s=fm1; bh=tnO1GSxsRBjabnSqoPafYKu84RwvbekPwGlfwXZKu
eQ=; b=pqUnDsBbVZodjYuVG/RIQjUOKQ0Zu5Hm2OStcoElpv/zGk1YjSx0Rbm2G
bmtwoBxazKswJNnIsKRO6+6D/PmsNYyjpYGy+iLSUs0GrHLOXgvy4LAAvc1HPwKb
9UHdm7ebkienJVvx8PUGno14xpROZ0+YZEZxTXh/ou21boJN2HZCtIpr2Soxjfoq
oSpEJXD+d59U5KjLboT6JRtp8RTFivR8kpwQCDBDzkzXdOa+lps0MpCSlSjbuhSx
fufsRqJBAwYMjBZ4DJUg5J2QNsGnBqwiPOUCb9+oCqqU0OrgPOwp65xSEqj7C4rp
3esafuV1XGMiMLzVLtDrSDesxwWzg==

X-ME-Sender: <xms:MlSQX0rF4YjZSSmV7fmyftgZCBrT4X_728i7fUKpAf1wlDK5OhKirA>
<xme:MlSQX6qYj3Orw1gN6XZaTDs8au5JC9ljgb5u1VQ6svYfD0bYdFaVO9aJ5ONC-8ZbE
0ZlNXfLcBT8EaLkzg>

X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrjeehgdeltdcutefuodetggdotefrodftvf
curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu
uegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgfgsehtqh
ertderreejnecuhfhrohhmpedfofhitghhrggvlhcuffdkgfhrrhhitghofdcuoehmihhk
vgdqlhhishhtsehpohgsohigrdgtohhmqeenucggtffrrghtthgvrhhnpeegleetfeeiie
ejueegvdekgfejieejffevieejkeekkeelhfeiheevjedtueegieenucffohhmrghinhep
rghlphgvrhhtrhhonhdrtghomhdrrghrnecuvehluhhsthgvrhfuihiivgeptdenucfrrg
hrrghmpehmrghilhhfrhhomhepmhhikhgvqdhlihhsthesphhosghogidrtghomh

X-ME-Proxy: <xmx:MlSQX5MUZVeGClVptjHVAEjCCCPZaPPZ47KffUSkKlaalU8h8_f7Fw>
<xmx:MlSQX75A7by8qTsURYL1eoiMbtoouossuBEzWeJUAfeZQ9JThw1zIg>
<xmx:MlSQXz4Jm0hMAV0fkSYU8pj9lhzQx9xkXGEjBPG-sc2xwxkjxKqigw>
<xmx:MlSQX1HPpeTrKTuneV92tOcJ1d54oHiwSv3ctniWW0JRV_bKlQWb-Q>

Received: by mailuser.nyi.internal (Postfix, from userid 501)
id 8E4DF66006F; Wed, 21 Oct 2020 11:30:47 -0400 (EDT)

X-Mailer: MessagingEngine.com Webmail Interface

User-Agent: Cyrus-JMAP/3.3.0-502-gfef6c88-fm-20201019.001-gfef6c888

Mime-Version: 1.0

Message-Id: <81ebf7c4-7529-4693-85c9-edc3ece508a6@www.fastmail.com>

In-Reply-To: <1ed370e4-8a09-4a41-bf15-22d8e61bef6e@www.fastmail.com>

References: <07090aa6-1bd1-4a37-810d-6cd95a6f1e7c@www.fastmail.com>
<ACF3D521-99D7-4A46-A3E6-2865FE53A816@gmail.com>
<19672d78-77de-4744-b9d8-470a18dc3ac0@www.fastmail.com>
<770E332F-B404-45C8-898B-BAD69A9B75A0@shiftleft.org>
<cc5b03ef-01d0-44a3-9030-1faa99107425@www.fastmail.com>
<3c63be30-5c09-42b0-a0a4-18190ef5d548@www.fastmail.com>
<bc77f256-2fc6-48c1-9a7a-60ec6caaa55d@www.fastmail.com>
<1ed370e4-8a09-4a41-bf15-22d8e61bef6e@www.fastmail.com>

Date: Wed, 21 Oct 2020 11:30:36 -0400

From: "Michael D'Errico" <mike-list@pobox.com>

To: cfrg@irtf.org

Content-Type: text/plain;charset=utf-8

Content-Transfer-Encoding: quoted-printable

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/rCLEPDYWstc_AJ1sEC5Bq8FCgs8>

Subject: [Cfrg] =?utf-8?q?Your_Secret_is_Too_Short_=28was=3A_Is_Diffie-He?=
=?utf-8?q?llman_Better_Than_We_Think=3F=29?=

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.29

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>,
<mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Wed, 21 Oct 2020 15:31:02 -0000

Hello, If the length of your Diffie-Hellman secret exponent is on the order of the number of bits of security you are trying to achieve, then it's too short. [Below I propose a way to make a better choice for the prime P used in the Diffie-Hellman exchange, which may make it easier to determine the strength of D-H.] The prime P will end with at least 2 ones in the least significant bits (if it's a safe prime) and all of the published parameters in [MODP] and [FFDHE] have primes with at least 64 trailing bits of 1. If you count the number of trailing one bits and call this M, then brute force finding the secret takes 1/M the time you would expect. A custom device can be built to unwind the modular exponentiation M steps at a time. For details, please refer to the conversation below, starting with the first message all the way at the bottom. This translates to a loss of log2(M) bits of security of the secret. As an example, if you have a requirement that your secret exponent X can not be determined in 2^64 operations and assume you can just generate a random 64-bit number to use as the Diffie-Hellman exponent, and if you are using any of the published MODP or FFDHE parameters, then your secret is actually only giving you about 58 bits of security. (This revised estimate may be optimistic.) All of the trailing 1 bits show up as factors of 2 in the number (P+1), which is why I got interested in factoring these numbers (see below for a list of the factors of all of the MODP and FFDHE primes plus one). I don't know how factors other than 2 affect the security, so it seems best to avoid them. Here's a proposed way to avoid any factors of (P+1) which aren't 2: - Choose a prime W of sufficient length ending with bits 01 (W mod 4 is 1) - Append a whole lot of 1 bits to the end of (W-1) and call this P - Ensure P and (P-1)/2 are both prime Would P be roughly twice as long as W at the minimum? Does P perform better than expected w.r.t. all of the known Diffie-Hellman attacks on primes on the order of the length of W? (P is only effectively as long as W, right?) Do we actually know that P isn't effectively even shorter than W? Mike [MODP]: RFC 2409 and RFC 3526 [FFDHE]: RFC 7919 On Tue, Oct 20, 2020, at 12:50, Michael D'Errico wrote: > Hi again, > > My theory is that vanilla modular-exponentiation > Diffie-Hellman is not as bad as currently thought > and maybe the Number Field Sieve achieves its > impressive results when the prime is "bad", where > bad means that P+1 has lots of (small) factors. > > It was pointed out to me that the largest prime > satisfying [1], [2], and [3] in my previous > message is 11, but that [3] could be replaced by: > > [3'] (P+1)/12 is prime > > Does anybody have access to a Number Field Sieve > program who can do the following experiment? > > - Choose a prime P such that (P-1)/2 and > (P+1)/12 are also prime > > - [Added bonus for long string of 1's in > the top bits? (*)] > > - Determine equivalent security bits for > the prime P > > Maybe a 64-bit prime would have 30 or so bits > of security? > > Mike > > (*) All of the published primes have sixty-four > 1's in the top bits -- is this done for the > reason that Diffie-Hellman fails if the secret > X is greater than P? > > [I also corrected the factorizations below; there > were two missing large factors.] > > > On Sun, Oct 18, 2020, at 10:04, Michael D'Errico wrote: >> Good morning, >> >> Perhaps there is an "ideal" Diffie-Hellman prime >> with the following characteristics: >> >> [1] P is prime >> [2] (P-1)/2 is prime >> [3] (P+1)/4 is prime >> >> Is it possible to generate such a number (in a >> reasonable amount of time)? (You'd be able to >> skip any numbers where P mod 8 isn't 3.) >> >> In addition, I notice that all of the published >> Diffie-Hellman primes in [MODP] and [FFDHE] have >> their 64 most significant bits set to 1. >> >> Is this to make it unlikely for the secret X to >> be randomly chosen greater than P (when >> calculating 2^X mod P)? >> >> Does Diffie-Hellman fail if you choose a secret >> X larger than P? Do clients and servers check? >> >> Mike >> >> [MODP]: RFC 2409 and RFC 3526 >> [FFDHE]: RFC 7919 >> >> >> On Sat, Oct 17, 2020, at 14:34, Michael D'Errico wrote: >>> Hi, >>> >>> I went to the trouble of computing the factors [*] >>> of (P+1)/2^64 for all of the "MODP" primes in RFCs >>> 2409 and 3526, and the "FFDHE" primes in RFC 7919, >>> so I thought it would be good to share the results. >>> >>> The final factor(s) are not shown but are assumed >>> to be prime or very large since the factoring >>> program never finished: >>> >>> >>> modp-0768: 3 * 5 * 58502243 * >>> 500905890761075075179[a] * {183-digits} >>> >>> modp-1024: 2 * 3^3 * 7 * 61 * 755333 * >>> 903210511397 * {267} >>> >>> modp-1536: 2^3 * 3^2 * 5 * 7 * 59 * 773 * >>> 10111 * 713941 * 116114161 * {418} >>> >>> modp-2048: 3 * 5 * {597} >>> ffdhe-2048: 2^3 * 3^3 * 5 * 101 * 46559 * >>> 95651 * {583} >>> >>> modp-3072: 3 * 13 * 2129 * 5572027361377 * {888} >>> ffdhe-3072: 2^3 * 3 * 173 * {902} >>> >>> modp-4096: 2 * 3 * 3067 * {1210} >>> ffdhe-4096: 3^3 * 5^2 * 5683 * 853854997 * {1199} >>> >>> modp-6144: 3 * 19 * 137 * 211 * >>> 233140623089477581[b] * {1807} >>> ffdhe-6144: 2 × 3 × 41 × 9533 × 2417897 * {1818} >>> >>> modp-8192: 2^5 * 3^3 * 5 * 7^2 * 17 * 277 * {2438} >>> ffdhe-8192: 3 * 937 * 140611 * {2439} >>> >>> >>> Are there any conclusions to be drawn from this? >>> >>> Maybe that modp-2048 is "better" than ffdhe-2048, >>> but ffdhe-8192 is better than modp-8192? >>> >>> Is modp-1536 a really bad choice for a prime? >>> >>> Mike >>> >>> >>> [*] I used: https://www.alpertron.com.ar/ECM.HTM >>> (hopefully I didn't make any mistakes....) >>> >>> [a] This factor was accidentally omitted when I >>> composed my original message >>> >>> [b] I didn't wait long enough to find this factor >>> but someone else did (via private email) >>> >>> >>>> Hello, >>>> >>>> I think that the current definition of a "safe prime" >>>> for use in Diffie-Hellman may be inadequate and >>>> could require more than just: >>>> >>>> [1] P is prime >>>> [2] (P-1)/2 is also prime >>>> >>>> Maybe you also want: >>>> >>>> [3] (P+1) is square-free >>>> >>>> This postulate follows from the discussion quoted >>>> below. I've found that all of the Diffie-Helman primes >>>> published in RFC's 2409, 3526, and 7919 allow you >>>> to brute-force compute a secret 32 times faster than >>>> you would expect just looking at the number of bits. >>>> >>>> The prime numbers all have the property that (P+1) >>>> is divisible by 2^64. This follows from the fact that >>>> the lower sixty-four bits are all ones. I don't know >>>> if any additional problem arises by having the top >>>> 64 bits also equal to 1. >>>> >>>> These primes are (assumedly) safe according to the >>>> current definition ([1] and [2] above), but perhaps >>>> effectively 64 or more bits shorter than advertised. >>>> >>>> This could mean that the number field sieve would >>>> also be faster (the 2048-bit primes could act like >>>> 1984-bit primes), but I have not tried to determine >>>> this myself. >>>> >>>> It may be really difficult to find primes satisfying [1], >>>> [2], and [3], so there'd maybe be a trade-off where >>>> you'd allow a few square factors.... >>>> >>>> This is not my field of expertise, so I apologize if >>>> anyone feels I'm wasting their time. >>>> >>>> Mike >>>> >>>> >>>> On Fri, Oct 16, 2020, at 09:07, Mike Hamburg wrote: >>>>> Hello Mike, >>>>> >>>>> The limiting factor for DH security (and also RSA security) is a >>>>> very complex attack algorithm called the Number Field Sieve. So >>>>> attacks on 2048-bit DH safe prime would take time: >>>>> >>>>> * ~ 2^2048 using straightforward brute force >>>>> * ~ 2^1024 using collision-based brute force such as Pollard’s Rho >>>>> * ~ 2^112 using NFS. >>>>> >>>>> For DSA and sometimes for DH, people use primes p with a generator >>>>> g of smaller prime order q, eg q ~ 2^256 here. This speeds up the >>>>> operation at the cost of lower brute-force resistance. This would >>>>> reduce the brute force costs to >>>>> >>>>> * ~ 2^256 using straightforward brute force >>>>> * ~ 2^128 using collision-based brute force >>>>> * but still ~ 2^112 using NFS >>>>> >>>>> This is generally seen as acceptable, because the cost estimates for >>>>> rho attacks are much more certain than for NFS, and are still at an >>>>> acceptable level. Since the security is determined mainly by the >>>>> best attack, this doesn’t lower the security. (Unless NFS at that >>>>> scale is harder than projected, but in that case the security is >>>>> still fine.) >>>>> >>>>> Likewise, your attack slightly speeds up straightforward brute force, >>>>> but not (as far as you’ve shown) collision-based brute force or NFS. >>>>> So it doesn’t affect the overall security of DH / DSA. >>>>> >>>>> However, primes of a special form *can* reduce security against the >>>>> NFS. But these aren’t primes that specifically begin or end with a >>>>> lot of 1s, but rather primes that can be expressed as a low or medium- >>>>> degree polynomial with small coefficients. For example, >>>>> p = 2^2048 - 1557 would be a poor choice, because it can be written >>>>> as a small polynomial, eg >>>>> >>>>> p = x^32 - 1557 with x = 2^64. >>>>> >>>>> I’m not an expert on NFS, so I’m not sure exactly how much security >>>>> this knocks off. Asymptotically you lose about 20% of the bits, >>>>> (eg 2^112 -> 2^89, which is still out of reach of academics but maybe >>>>> not large / govt organizations, especially because most of the work >>>>> can be amortized across many discrete logs) but concretely this might >>>>> be quite different. >>>>> >>>>> Cheers, >>>>> — Another Mike >>>>> >>>>>> On Fri, Oct 16, 2020, at 03:22, Michael D'Errico wrote: >>>>>> >>>>>> Hello, >>>>>> >>>>>> [...] >>>>>> >>>>>> The algorithm I showed should run about 32 times faster >>>>>> than brute force, even though it's doing a brute force >>>>>> search. >>>>>> >>>>>> According to Wikipedia, a 2048-bit Diffie-Hellman prime >>>>>> is equivalent to 112 bits for a symmetric key, so perhaps >>>>>> the special structure of both 2048-bit published primes >>>>>> makes them equivalent to only 107 bits. >>>>>> >>>>>> Mike >>>>>> >>>>>>>> On Thu, Oct 15, 2020, at 09:15, Michael D'Errico wrote: >>>>>>>> >>>>>>>> Hi, >>>>>>>> >>>>>>>> I've figured out just a bit more. I'm actually trying >>>>>>>> not to work on this problem, but my brain keeps >>>>>>>> thinking about it anyway. The special format of >>>>>>>> the prime numbers in RFC's 2409, 3526, and >>>>>>>> 7919 allow you to create an interesting device to >>>>>>>> calculate the private value from a Diffie-Hellman >>>>>>>> public value using on the order of N bits (size of >>>>>>>> prime P). >>>>>>>> >>>>>>>> The lowest 64 bits of the Diffie-Hellman public >>>>>>>> value Y = (2^X mod P) contain a record of when >>>>>>>> the mod operation performed a subtraction of a >>>>>>>> shifted version of P (see my original message >>>>>>>> quoted below). You can reconstruct a larger value >>>>>>>> the modulo operation was working on by adding >>>>>>>> back: >>>>>>>> >>>>>>>> uint64 y = Y; // low 64 bits of public value >>>>>>>> >>>>>>>> Y += y * P; // mod P touched this number >>>>>>>> >>>>>>>> This updated version of Y contains the number >>>>>>>> that the mod P operation was working on 64 steps >>>>>>>> prior to finishing. But since the generator was 2 >>>>>>>> (and 2^X is a solitary 1 followed by a huge string >>>>>>>> of zeros), this new larger value of Y will have 64 >>>>>>>> zeros at the end which can be removed: >>>>>>>> >>>>>>>> Y>>= 64; // remove 64 zero bits >>>>>>>> >>>>>>>> This process can now repeat using the lowest 64 >>>>>>>> bits of Y again: >>>>>>>> >>>>>>>> repeat { >>>>>>>> >>>>>>>> uint64 y = Y; >>>>>>>> >>>>>>>> Y += y * P; >>>>>>>> >>>>>>>> Y>>= 64; >>>>>>>> >>>>>>>> } until (???); >>>>>>>> >>>>>>>> This process unwinds the modulo P operation all >>>>>>>> the way back to 2^X in steps of size 64. The only >>>>>>>> thing missing is the terminating condition, which >>>>>>>> I'm pretty sure would be: Y contains a single bit >>>>>>>> with value 1 (somewhere in the top 64 bits). If >>>>>>>> so, then the value of y would be zero a few times >>>>>>>> in a row and then contain a single one bit. >>>>>>>> >>>>>>>> If you can reliably determine when the algorithm >>>>>>>> has finished, you could build a device which >>>>>>>> computes X from Y using roughly N bits. It would >>>>>>>> be really slow, but it would be guaranteed to find >>>>>>>> the answer (32 times faster than brute force >>>>>>>> reversing the mod P operation one bit at a time >>>>>>>> on average?). >>>>>>>> >>>>>>>> Perhaps there is a way to make this algorithm >>>>>>>> (much) faster? >>>>>>>> >>>>>>>> Even if there isn't, it is very interesting to me that >>>>>>>> these primes exhibit such a strange feature. >>>>>>>> >>>>>>>> Mike >>>>>>>> >>>>>>>> >>>>>>>> On Sat, Oct 10, 2020, at 18:01, Michael D'Errico wrote: >>>>>>>>> Subject: [Cfrg] Weak Diffie-Hellman Primes >>>>>>>>> >>>>>>>>> Hi, >>>>>>>>> >>>>>>>>> I'm not a member of this list, but was encouraged to >>>>>>>>> start a discussion here about a discovery I made >>>>>>>>> w.r.t. the published Diffie-Hellman prime numbers in >>>>>>>>> RFC's 2409, 3526, and 7919. These primes all have >>>>>>>>> a very interesting property where you get 64 or more >>>>>>>>> bits (the least significant bits of 2^X mod P for some >>>>>>>>> secret X and prime P) detailing how the modulo >>>>>>>>> operation was done. These 64 bits probably reduce >>>>>>>>> the security of Diffie-Hellman key exchanges though >>>>>>>>> I have not tried to figure out how. >>>>>>>>> >>>>>>>>> The number 2^X is going to be a single bit with value >>>>>>>>> 1 followed by a lot of zeros. All of the primes in the >>>>>>>>> above mentioned RFC's have 64 bits of 1 in the most >>>>>>>>> and least significant positions. The 2's complement >>>>>>>>> of these primes will have a one in the least significant >>>>>>>>> bit and at least 63 zeros to the left. >>>>>>>>> >>>>>>>>> When you think about how a modulo operation is done >>>>>>>>> manually, you compare a shifted version of P against >>>>>>>>> the current value of the operand (which is initially 2^X) >>>>>>>>> and if it's larger than the (shifted) P, you subtract P at >>>>>>>>> that position and shift P to the right, or if the operand >>>>>>>>> is smaller than (the shifted) P, you just shift P to the >>>>>>>>> right without subtracting. >>>>>>>>> >>>>>>>>> Instead of subtracting, you can add the 2's complement >>>>>>>>> I mentioned above. Because of the fact that there are >>>>>>>>> 63 zeros followed by a 1 in the lowest position, you will >>>>>>>>> see a record of when the modulo operation performed >>>>>>>>> a subtraction (there's a one) and when it didn't (there's >>>>>>>>> a zero). >>>>>>>>> >>>>>>>>> You can use the value of the result you were given by >>>>>>>>> your peer (which is 2^X mod P) and then add back the >>>>>>>>> various 2^j * P's detailed wherever the lowest 64 bits >>>>>>>>> had a value of 1 to find the state of the mod P operation >>>>>>>>> when it wasn't yet finished. This intermediate result is >>>>>>>>> likely going to make it easier to determine X than just a >>>>>>>>> brute force search. >>>>>>>>> >>>>>>>>> I don't plan to join this list, though I am flattered to >>>>>>>>> have been asked to do so. I'm not a cryptographer. >>>>>>>>> >>>>>>>>> Mike

- [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Dan Brown
- Re: [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Anna Johnston
- Re: [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Mike Hamburg
- [Cfrg] Inadequate Definition of "Safe Prime" ? (w… Michael D'Errico
- Re: [Cfrg] Inadequate Definition of "Safe Prime" … Michael D'Errico
- [Cfrg] Ideal Diffie-Hellman Primes (was: Inadequa… Michael D'Errico
- [Cfrg] Is Diffie-Hellman Better Than We Think? (w… Michael D'Errico
- Re: [Cfrg] Is Diffie-Hellman Better Than We Think… Christopher Patton
- [Cfrg] Your Secret is Too Short (was: Is Diffie-H… Michael D'Errico
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Mike Hamburg
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Dan Brown
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Andrey Jivsov
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Ian Goldberg
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Dan Brown
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Andrey Jivsov
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Andrey Jivsov
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Ian Goldberg
- [Cfrg] New Type of Math Object Discovered? (was: … Michael D'Errico