### Re: [Cfrg] uniform random distribution in ECDH public key

"Dan Harkins" <dharkins@lounge.org> Tue, 14 August 2012 18:58 UTC

Return-Path: <dharkins@lounge.org>

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 BC38821F867D for <cfrg@ietfa.amsl.com>; Tue, 14 Aug 2012 11:58:26 -0700 (PDT)

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

X-Spam-Flag: NO

X-Spam-Score: -6.216

X-Spam-Level:

X-Spam-Status: No, score=-6.216 tagged_above=-999 required=5 tests=[AWL=0.049, BAYES_00=-2.599, IP_NOT_FRIENDLY=0.334, RCVD_IN_DNSWL_MED=-4]

Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id lu4XTZljRwvz for <cfrg@ietfa.amsl.com>; Tue, 14 Aug 2012 11:58:26 -0700 (PDT)

Received: from colo.trepanning.net (colo.trepanning.net [69.55.226.174]) by ietfa.amsl.com (Postfix) with ESMTP id 59E0221F8569 for <cfrg@irtf.org>; Tue, 14 Aug 2012 11:58:26 -0700 (PDT)

Received: from www.trepanning.net (localhost [127.0.0.1]) by colo.trepanning.net (Postfix) with ESMTP id DC4541022404C; Tue, 14 Aug 2012 11:23:02 -0700 (PDT)

Received: from 69.12.173.8 (SquirrelMail authenticated user dharkins@lounge.org) by www.trepanning.net with HTTP; Tue, 14 Aug 2012 11:23:03 -0700 (PDT)

Message-ID: <def0111a5e81f715d26eb4a6c426295e.squirrel@www.trepanning.net>

In-Reply-To: <502A928A.7090003@htt-consult.com>

References: <502A928A.7090003@htt-consult.com>

Date: Tue, 14 Aug 2012 11:23:03 -0700

From: Dan Harkins <dharkins@lounge.org>

To: Robert Moskowitz <rgm-sec@htt-consult.com>

User-Agent: SquirrelMail/1.4.14 [SVN]

MIME-Version: 1.0

Content-Type: text/plain; charset="iso-8859-1"

Content-Transfer-Encoding: 8bit

X-Priority: 3 (Normal)

Importance: Normal

Cc: cfrg@irtf.org

Subject: Re: [Cfrg] uniform random distribution in ECDH public key

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.12

Precedence: list

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

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

List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>

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

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

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

X-List-Received-Date: Tue, 14 Aug 2012 18:58:26 -0000

Hi Bob, On Tue, August 14, 2012 11:01 am, Robert Moskowitz wrote: > I understand from RFC 6090 and 5869 that the secret key produced from an > ECDH exchange is not uniformly randomly distributed and that is why we > have the 'Extract' phase in HKDF. Got that. > > This question is about the public key, g^j: > > I understand that like j, it must be a point on the curve, thus if the > curve is p-256, both j and g^j are 256 bits long. But is g^j uniformly > randomly distributed like j is suppose to be? No, it's not. It's it's a special pair (x,y) that satisfy the equation of the curve: y^2 = x^3 + ax + b. Not all pairs will satisfy that equation. I believe about half of them will and about half won't. For x to be random, each number between 0 and p would have equal probability. But that's not the case since about half won't. > Side question: I am still unclear on the length of the exchanged secret > (g^j)^k, is it 256 bits (for p-256) or larger (perhaps 512 bits)? The result of an ECDH is an element in the group so it's also an (x,y) pair but the secret that you use in your KDF is the x coordinate of that result. The y coordinate is discarded. regards, Dan.

- [Cfrg] uniform random distribution in ECDH public… Robert Moskowitz
- Re: [Cfrg] uniform random distribution in ECDH pu… Scott Fluhrer (sfluhrer)
- Re: [Cfrg] uniform random distribution in ECDH pu… Robert Moskowitz
- Re: [Cfrg] uniform random distribution in ECDH pu… David McGrew (mcgrew)
- Re: [Cfrg] uniform random distribution in ECDH pu… Robert Moskowitz
- Re: [Cfrg] uniform random distribution in ECDH pu… Robert Moskowitz
- Re: [Cfrg] uniform random distribution in ECDH pu… Vadym Fedyukovych
- Re: [Cfrg] uniform random distribution in ECDH pu… Dan Harkins
- Re: [Cfrg] uniform random distribution in ECDH pu… David Jacobson
- Re: [Cfrg] uniform random distribution in ECDH pu… Dan Brown
- Re: [Cfrg] uniform random distribution in ECDH pu… Blumenthal, Uri - 0668 - MITLL
- Re: [Cfrg] uniform random distribution in ECDH pu… Dan Brown
- Re: [Cfrg] uniform random distribution in ECDH pu… Blumenthal, Uri - 0668 - MITLL
- Re: [Cfrg] uniform random distribution in ECDH pu… Dan Brown
- Re: [Cfrg] uniform random distribution in ECDH pu… David Jacobson