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

Vadym Fedyukovych <vf@unity.net> Tue, 14 August 2012 18:51 UTC

Return-Path: <vf@unity.net>
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 9966821E8048 for <cfrg@ietfa.amsl.com>; Tue, 14 Aug 2012 11:51:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.599
X-Spam-Level:
X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599]
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 ZXeZ3LlGOFpN for <cfrg@ietfa.amsl.com>; Tue, 14 Aug 2012 11:51:38 -0700 (PDT)
Received: from vc.unity.net (140-242.trifle.net [195.24.140.242]) by ietfa.amsl.com (Postfix) with ESMTP id CAB9521E8042 for <cfrg@irtf.org>; Tue, 14 Aug 2012 11:51:37 -0700 (PDT)
Received: from vf by vc.unity.net with local (Exim 4.72) (envelope-from <vf@unity.net>) id 1T1MDH-00024W-Cm for cfrg@irtf.org; Tue, 14 Aug 2012 21:51:35 +0300
Date: Tue, 14 Aug 2012 21:51:35 +0300
From: Vadym Fedyukovych <vf@unity.net>
To: cfrg@irtf.org
Message-ID: <20120814185135.GJ20940@unity.net>
References: <502A928A.7090003@htt-consult.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=koi8-r
Content-Disposition: inline
In-Reply-To: <502A928A.7090003@htt-consult.com>
User-Agent: Mutt/1.5.20 (2009-06-14)
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:51:38 -0000

On Tue, Aug 14, 2012 at 02:01:46PM -0400, 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.

I'd say, shared secret produced by ECDH is "fixed" for two parties,
represented by their public keys.
HKDF (5869) would produce "per-application" keys then

> 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?

g^j (or, in additive notation, jG) is distributed uniformly over non-trivial elements of the group,
on condition at least one of j or k (at section 4 of 6090) was chosen uniformly at random from integers 1 up to (group order -1).

"j" is not a point on the curve, but an index (logarithm) in the finite group

> 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)?

Depends on representation of the point on the curve.
Basically, two numbers (x- and y- coordinates) of 256 bits long.

> Thank you for helping me get all this straight.