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

Robert Moskowitz <rgm-sec@htt-consult.com> Tue, 14 August 2012 18:51 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 0467321E8041 for <cfrg@ietfa.amsl.com>; Tue, 14 Aug 2012 11:51:37 -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=[AWL=0.000, 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 t0VBdNdwSpec for <cfrg@ietfa.amsl.com>; Tue, 14 Aug 2012 11:51:36 -0700 (PDT)
Received: from klovia.htt-consult.com (klovia.htt-consult.com [208.83.67.149]) by ietfa.amsl.com (Postfix) with ESMTP id 6F1A021E803C for <cfrg@irtf.org>; Tue, 14 Aug 2012 11:51:36 -0700 (PDT)
Received: from localhost (unknown [127.0.0.1]) by klovia.htt-consult.com (Postfix) with ESMTP id BD48062A80; Tue, 14 Aug 2012 18:51:12 +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 Ft6q7evt9F0X; Tue, 14 Aug 2012 14:50:55 -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 83CE762A5D; Tue, 14 Aug 2012 14:50:55 -0400 (EDT)
Message-ID: <502A9E0E.6060209@htt-consult.com>
Date: Tue, 14 Aug 2012 14:50:54 -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: "David McGrew (mcgrew)" <mcgrew@cisco.com>
References: <CC500FDA.A36D4%mcgrew@cisco.com>
In-Reply-To: <CC500FDA.A36D4%mcgrew@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:51:37 -0000

On 08/14/2012 02:26 PM, David McGrew (mcgrew) wrote:
> Hi Bob,
>
> On 8/14/12 2:01 PM, "Robert Moskowitz" <rgm-sec@htt-consult.com>; 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?
> Something quick to add to what Scott said.   Note that j is uniformly
> random when considered as an integer between 1 and the group order; it is
> not uniformly random when considered as a bit string.

AH! Important clearification.

But this means that on the curve, the possible points are uniform. I 
thought that they need to be prime values? I am getting more confused, I 
think, as I think about this!

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