Re: [Cfrg] Curve25519 lacks private/public homomorphism?

"Scott Fluhrer (sfluhrer)" <> Tue, 05 February 2019 03:27 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id BD069130FA9 for <>; Mon, 4 Feb 2019 19:27:07 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -14.641
X-Spam-Status: No, score=-14.641 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.142, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id KCRxT9PP9FvN for <>; Mon, 4 Feb 2019 19:27:05 -0800 (PST)
Received: from ( []) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 704281294FA for <>; Mon, 4 Feb 2019 19:27:05 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple;;; l=9322; q=dns/txt; s=iport; t=1549337225; x=1550546825; h=from:to:cc:subject:date:message-id:references: in-reply-to:mime-version; bh=rlTWnhbUYN1gJRfobjZ5CrJ9Zc5RteeuEY8myh3CpEk=; b=Whj3Lu9+MLcYYl9VQVt7zVPLRO+0agKXZ3ZUBjQETYUbrCQz5wyRXUHe z43zo5QFIafmotS5dxoEOHoShF6Z7Q3AjGvKOfFArqGJ+1s1WJYfB6bBq f/gXwfrIEQVS9FFMWdilUv3VqueaFDzHJf6AMq+uY7oTXoGb+lyFzzYxZ c=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-AV: E=Sophos;i="5.56,560,1539648000"; d="scan'208,217";a="294802698"
Received: from ([]) by with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 05 Feb 2019 03:27:03 +0000
Received: from ( []) by (8.15.2/8.15.2) with ESMTPS id x153R3EX026195 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL); Tue, 5 Feb 2019 03:27:03 GMT
Received: from ( by ( with Microsoft SMTP Server (TLS) id 15.0.1395.4; Mon, 4 Feb 2019 22:27:03 -0500
Received: from ([]) by ([]) with mapi id 15.00.1395.000; Mon, 4 Feb 2019 22:27:02 -0500
From: "Scott Fluhrer (sfluhrer)" <>
To: Adam Langley <>, Richard Barnes <>
Thread-Topic: [Cfrg] Curve25519 lacks private/public homomorphism?
Thread-Index: AQHUvNgNtZc7Pq3KVEGarVna6KzeeKXQrMCA///d/2A=
Date: Tue, 05 Feb 2019 03:27:02 +0000
Message-ID: <>
References: <> <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: []
Content-Type: multipart/alternative; boundary="_000_a6a12fd3d3204d4cb4fbaca65a484c94XCHRTP006ciscocom_"
MIME-Version: 1.0
Archived-At: <>
Subject: Re: [Cfrg] Curve25519 lacks private/public homomorphism?
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 05 Feb 2019 03:27:08 -0000

From: Cfrg <> On Behalf Of Adam Langley
Sent: Monday, February 04, 2019 7:26 PM
To: Richard Barnes <>
Cc: CFRG <>
Subject: Re: [Cfrg] Curve25519 lacks private/public homomorphism?

On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <<>> wrote:
When you try to do this with Curve25519 (or Curve448), however, you run into a problem: `k_list[31] |= 64`.  The X25519 function in RFC 7748 [2] ensures that the second-most-significant bit of a scalar private key is always set, but this bit is not necessarily set in the product of two such scalars.  In other words, there are scalars `ab` such that you can arrive at `abG` as the result of a DH computation, but never abG will never be a public key (since `X25519(ab, 9) != abG`).  The mapping from private keys to public keys is not a homomorphism with regard to addition or multiplication.

This means we're out of luck with regard to our delta scheme.  If the delta happens to result in a new private key with its penultimate bit unset, then it can't actually be used as a private key -- and there's no way for the delta-generating party to know this.

Setting the 255th bit is just done to avoid having to worry about infinity in the Montgomery ladder, I believe. But if you handle infinity explicitly, doesn't that solve the problem?

Actually, the ladder code handles infinity just fine.  DJB put the ‘set the high-order bit’ logic there so that too-clever implementors wouldn’t be tempted to optimize the code by skipping initial 0’s (which would of course add a potential time-based side channel)