Re: [Cfrg] Fwd: [TLS] Curve25519 in TLS and Additional Curves in TLS

Andrey Jivsov <> Tue, 28 January 2014 17:20 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 4D65F1A0158 for <>; Tue, 28 Jan 2014 09:20:35 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, LOTS_OF_MONEY=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id hSnYTAVL7c6c for <>; Tue, 28 Jan 2014 09:20:32 -0800 (PST)
Received: from ( [IPv6:2001:558:fe2d:43:76:96:30:96]) by (Postfix) with ESMTP id D9AA01A0187 for <>; Tue, 28 Jan 2014 09:20:32 -0800 (PST)
Received: from ([]) by with comcast id KSHh1n0050mlR8UA9VLW15; Tue, 28 Jan 2014 17:20:30 +0000
Received: from [] ([]) by with comcast id KVLV1n0044uhcbK8XVLVgG; Tue, 28 Jan 2014 17:20:30 +0000
Message-ID: <>
Date: Tue, 28 Jan 2014 09:20:29 -0800
From: Andrey Jivsov <>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: Robert Ransom <>
References: <> <> <> <> <> <> <> <> <> <> <> <>
In-Reply-To: <>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=q20121106; t=1390929630; bh=r6REO+dPn6ArijMqywrRTOyssQkUzfjJ5xsdEN4LlBI=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=E+sljGH2ikLNUv5rhNZ73SOvAFoLQsaJqGv8WIBds9biZQFMsZcplhqg9XT0DiHAs aqWqYYYoNfLnGA5PhrHT6KEo7WVQS0NYca/Yw5sR7oge/WUZS0HMKN69/7LfYcaFYj ZIhUnHyTNd0I9o9RXlFhSWohTrfePgD7oAbEmm8MC3onsM9j8+i63DHi7MGXRNrD8x 47QvYlL+3AUcEwb7/94wvSK0/ENatFhM8trEzXkKGwnFk8om5uGGK7UTOxoy7if8LX LM+DEY/53dT8kHha9n3sxHYjrLszhJ2beNt4yI07w7LKqqb/cFcHdIgZeHyBjpar8i jO2MYuWTzNoGw==
Subject: Re: [Cfrg] Fwd: [TLS] Curve25519 in TLS and Additional Curves in TLS
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 28 Jan 2014 17:20:35 -0000

On 01/28/2014 06:47 AM, Robert Ransom wrote:
> On 1/28/14, Andrey Jivsov <> wrote:
>> On 01/23/2014 06:58 PM, Robert Ransom wrote:
>>> On 1/23/14, Andrey Jivsov <> wrote:
>>>> Wouldn't be another
>>>> method?
>>>> ( BTW, the proposal in the draft is in public domain since it was
>>>> published on December 10, 2012. )
>>> Are you claiming that the point format that I suggested is patented?
>> I was making a statement about my contribution, in case this issue comes
>> up.
>> The IP for the use of 1 bit to compress a point is a common knowledge,
>> but I've heard that some of them are expiring.
> If you are referring to the patent addressed in
> <>, claim 29 of the same patent
> covers point decompression with your proposal.

I am basing the method on the the CRYPTO '85 paper, which tells:

> Finally, it should be remarked, that even though we have phrased
> everything in terms of points on an elliptic curve, that, for the key
> exchange protocol (and other uses as one-way functions), that only the
> x-coordinate needs to be transmitted. The formulas for multiples of a
> point cited in the first section make it clear that the x-coordinate of
> a multiple depends only on the x-coordinate of the original point.

>> However, I am concerned about the cofactor issue. These curves have the
>> cofactor greater than 1. Unlike "unsafe" NIST curves, this needs to be
>> handled. The draft suggest methods that, as I understand them, may run
>> into IP issues. Besides, there may be protocols that want to do classic
>> DH. One solution to these issues is to enumerate the points in the small
>> subgroup, explicitly in the document, or by providing the method to
>> identify them.
> U.S. patent 6,226,383 (Jablon) claims 31 and 32 cover the use of your
> suggestion in ECDH.

I try not to read patents, one never knows what can be found there...

Because any modp group will have a cofactor of at least 2, all modp 
operations are effected by these claims. These claims would cover, for 
example, sec 2.2 that excludes 0 and p-1.

I was assuming that such a general method of comparing one element to 
another, or a concept of a subgroup, were known before 1990s.

> Dr. Bernstein's paper which specifies Curve25519 for use in ECDH
> addresses its groups' cofactors by (a) generating Diffie-Hellman
> keypairs such that the secret exponent is divisible by the cofactor
> (as is common in multiplicative-group Diffie-Hellman, where the
> cofactor is at least 2), and (b) requiring that the shared-secret
> group element be used only as input to a hash function or hash-based
> KDF (as is required for all Diffie-Hellman systems).
> Are you aware of any specific patent claims which cover these
> techniques, or are you merely trying to spread patent FUD?

The quick search reveals this one: US6563928. Yes, I did notice that the 
paper specifies that the key generation must clear the lower bits, which 
is equivalent to multiplying by a (power of 2) cofactor. Such a method 
hardwires the cofactor multiplication into the field operation. This was 
not necessarily needed, but I understand that this was important to be 
"safe". I personally would prefer the cofactor not to be a part of the 
raw ECC operations.