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

Robert Moskowitz <rgm-sec@htt-consult.com> Tue, 14 August 2012 18:26 UTC

Return-Path: <rgm-sec@htt-consult.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 1A91821F863B for <cfrg@ietfa.amsl.com>; Tue, 14 Aug 2012 11:26:05 -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 ZoiTaXmAbu1v for <cfrg@ietfa.amsl.com>; Tue, 14 Aug 2012 11:26:04 -0700 (PDT)
Received: from klovia.htt-consult.com (klovia.htt-consult.com [208.83.67.149]) by ietfa.amsl.com (Postfix) with ESMTP id 4F9CC21F8611 for <cfrg@irtf.org>; Tue, 14 Aug 2012 11:26:04 -0700 (PDT)
Received: from localhost (unknown [127.0.0.1]) by klovia.htt-consult.com (Postfix) with ESMTP id 5393D62A5D; Tue, 14 Aug 2012 18:25:40 +0000 (UTC)
X-Virus-Scanned: amavisd-new at localhost
Received: from klovia.htt-consult.com ([127.0.0.1]) by localhost (klovia.htt-consult.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id U1aKYPZ2Vnjr; Tue, 14 Aug 2012 14:25:30 -0400 (EDT)
Received: from lx120e.htt-consult.com (nc4010.htt-consult.com [208.83.67.156]) (Authenticated sender: rgm-sec@htt-consult.com) by klovia.htt-consult.com (Postfix) with ESMTPSA id EBF7062820; Tue, 14 Aug 2012 14:25:29 -0400 (EDT)
Message-ID: <502A9819.7080708@htt-consult.com>
Date: Tue, 14 Aug 2012 14:25:29 -0400
From: Robert Moskowitz <rgm-sec@htt-consult.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120717 Thunderbird/14.0
MIME-Version: 1.0
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
References: <502A928A.7090003@htt-consult.com> <A113ACFD9DF8B04F96395BDEACB34042111D9F@xmb-rcd-x04.cisco.com>
In-Reply-To: <A113ACFD9DF8B04F96395BDEACB34042111D9F@xmb-rcd-x04.cisco.com>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
Cc: "cfrg@irtf.org" <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:26:05 -0000

thank you. I was using the compact notation (x-coordinate only) for the 
256bit size with p-256. I should have said that.

On 08/14/2012 02:14 PM, Scott Fluhrer (sfluhrer) wrote:
> No, the value g^j (or jG,

And I am going by 6090. Sometimes I suspect the notation used there is 
to distance it from more 'modern' usages as appear in certain documents 
filed with a department of the US gov. But that is pure speculation.

>   if we prefer the more traditional additive notation for elliptic curves) is not uniform; it is a 512 bit value (for P256), and corresponds to a point on the curve (that is, it is a pair of 256 bit values that together are a solution to a specific cubic equation).  There are approximately 2^256 possible values for this 512 bit value, and so there are a large number of 512 bit public values which are not possible.

Is there any information of the distribution of jG?

>
> -----Original Message-----
> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of Robert Moskowitz
> Sent: Tuesday, August 14, 2012 2:02 PM
> To: cfrg@irtf.org
> Subject: [Cfrg] uniform random distribution in ECDH public key
>
> 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?
>
> 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)?
>
> Thank you for helping me get all this straight.
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>