### [CFRG] Re: RFC7748

Michael Scott <mike.scott@miracl.com> Sun, 09 June 2024 18:57 UTC

Return-Path: <mike.scott@miracl.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 33C2AC14CE44 for <cfrg@ietfa.amsl.com>; Sun, 9 Jun 2024 11:57:21 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -2.105

X-Spam-Level:

X-Spam-Status: No, score=-2.105 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham autolearn_force=no

Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=miracl.com

Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Ch0BAf-7y0cM for <cfrg@ietfa.amsl.com>; Sun, 9 Jun 2024 11:57:16 -0700 (PDT)

Received: from mail-ed1-x531.google.com (mail-ed1-x531.google.com [IPv6:2a00:1450:4864:20::531]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 95D65C14F6FC for <cfrg@irtf.org>; Sun, 9 Jun 2024 11:57:16 -0700 (PDT)

Received: by mail-ed1-x531.google.com with SMTP id 4fb4d7f45d1cf-57a4d7ba501so4720956a12.2 for <cfrg@irtf.org>; Sun, 09 Jun 2024 11:57:16 -0700 (PDT)

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=miracl.com; s=google; t=1717959434; x=1718564234; darn=irtf.org; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=GvAOXvSXc+4jWMpa6/WxPPziym1gBchBpx8nQrfx+ks=; b=jBU/oNjzQ1s2iWChWisHFiKbLNRZzgl6DR4eOlIEYaiJX3sKqoTgGBg26zADkrzBcn 7x8xpqusKE1jdNeBhAX2mmRttR9XWDcuBoF45PIbwniSH4J6LgIuXNPYqsjY2kv5i0ng AMoiF5p1IvWkyXreGfyc2xqnXh6nqwWcwxS/YMPfPb0CQar7rmbxS5z3q9whhaJjuixp oosCNAIKGhA2CYiFU/BTL+KhSNj/ks53Gh7Q2fWvH6W82P2QWzj9z6ZtEZwyqhrwRN0u em9eDOcb908oFSX6kOUROTLdcKZrjN9ML2RRMjDG25TiD/wOaKL13/9UWE3X/qj24huH SdCg==

X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717959434; x=1718564234; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=GvAOXvSXc+4jWMpa6/WxPPziym1gBchBpx8nQrfx+ks=; b=lFOI3puAgM63w6xjwBNzr45Bx5TAlC9uCeeEeJlZSD/NgMKAChKmz/NiQYHmN8stAD CCvScrcpBq+p1a+ysrkhMCbYuba7Qegj50wevce3qf7qN0d00e9RX7J6/XfMuvOiaNF2 y7rlqJ1rBXt571oUPqfIeXhcu9c8mWkYft/jQrW/AUYZCyfpgpi3/Wtk+RBnm12cyNTb KCTzBZIrPUwC6ijqzTLH+QGT66x1vPSMQrEC5rDWtxle484yPs3pcRj0QRJxFoXPVVOd K+vVd5EDmoSfBTJRS9v1WiR4GL+VVofMG5zuiZOoUnS7S55emy96oSGPRkNVXgDA+C23 TJig==

X-Gm-Message-State: AOJu0YwSOpBFW5qztN3arDuB2plvgNUVlwMK01DN0uBFXZdguS/wp0Og gOwEfrqcAHXKKH/xdwbLpMznAhvcBeN6QJZysaYd7G2Y98VqV0uuBvyjGsd4XF4dVGdrtalftYp 4YeDCnQb3lif64m7VImVZwkOJ8jVC2TT/Q1HHTzTDaxAH/m+8

X-Google-Smtp-Source: AGHT+IGR95zRaJPZMGo/X5yz+0keYhUzsiVEcYpu3Sbc9goBw3VQxqtWepD3W9zVqPiz1uipP2LUreGHYL/DFjQZhSo=

X-Received: by 2002:a50:aa85:0:b0:572:7bda:1709 with SMTP id 4fb4d7f45d1cf-57c5087fcfamr4319059a12.9.1717959433402; Sun, 09 Jun 2024 11:57:13 -0700 (PDT)

MIME-Version: 1.0

References: <CAEseHRoXMBExK0wXruv+MuHj-YdPYhB7ke+RCbyxDvLuBG7kkg@mail.gmail.com> <20240609165557.869866.qmail@cr.yp.to>

In-Reply-To: <20240609165557.869866.qmail@cr.yp.to>

From: Michael Scott <mike.scott@miracl.com>

Date: Sun, 09 Jun 2024 19:57:00 +0100

Message-ID: <CAEseHRpMsGMPwrozknDy2b-tK29qg2QtaiJWFTGMjCLcQuuung@mail.gmail.com>

To: cfrg@irtf.org

Content-Type: multipart/alternative; boundary="000000000000c45ad7061a7999c0"

Message-ID-Hash: OHVL5TG4ZFUD4TE2XC3XNF3JZHKTPGT3

X-Message-ID-Hash: OHVL5TG4ZFUD4TE2XC3XNF3JZHKTPGT3

X-MailFrom: mike.scott@miracl.com

X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; header-match-cfrg.irtf.org-0; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header

X-Mailman-Version: 3.3.9rc4

Precedence: list

Subject: [CFRG] Re: RFC7748

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/m-Yi6_KG0SBqfgTa1xOUelm5B7A>

List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Owner: <mailto:cfrg-owner@irtf.org>

List-Post: <mailto:cfrg@irtf.org>

List-Subscribe: <mailto:cfrg-join@irtf.org>

List-Unsubscribe: <mailto:cfrg-leave@irtf.org>

Hello Dan, Thanks for the very complete answer and the clarification. Mike On Sun, Jun 9, 2024 at 5:56 PM D. J. Bernstein <djb@cr.yp.to> wrote: > Michael Scott writes: > [ regarding Montgomery A^2-4 being a non-square ] > > In Appendix A of RFC7748 a script is provided for generating suitable > > Montgomery curves, but the above condition is not specified. > > Meanwhile the RFC specifies other conditions; so, before asking about > the safety of a hypothetical curve meeting the RFC's conditions and not > having A^2-4 being square, one might try to actually construct such a > curve, to show that the discussion isn't vacuous. > > A natural way to investigate would be to start with small fields, as in > the following Sage script, which runs through all odd primes p < 1000, > printing out all elliptic curves y^2 = x^3+Ax^2+x meeting the cofactor > conditions in the RFC (group order 8*prime for base field 1 mod 4, group > order 4*prime for base field 3 mod 4, twist order 4*prime in any case), > and noting for each curve whether A^2-4 is a non-square: > > #!/usr/bin/env sage > for p in primes(3,1000): > F = GF(p) > cofactor = 8 if p%4 == 1 else 4 > twistcofactor = 4 > for A in F: > if A == 2 or A == -2: continue > E = EllipticCurve(F,[0,A,0,1,0]) > n = E.cardinality() > twistn = 2*(p+1)-n > if n%cofactor != 0: continue > if not ZZ(n/cofactor).is_prime(): continue > if twistn%twistcofactor != 0: continue > if not ZZ(twistn/twistcofactor).is_prime(): continue > print(not (A^2-4).is_square(),'p',p,'A',A,'n',n,'twistn',twistn) > > The output shows 2007 elliptic curves. The only squares A^2-4 appear for > base fields of size <=17. At that point one might reasonably formulate > a hypothesis that, actually, the curves in question don't exist over > larger fields. > > Looking more closely at the square cases, one might notice that in each > case the "n" output is 8 or 16; i.e., the prime in "group order 8*prime" > or "group order 4*prime" is specifically the prime 2. So one might > formulate a more specific hypothesis that a Montgomery curve with > > * group order 8*(odd prime) for base field 1 mod 4, > * group order 4*(odd prime) for base field 3 mod 4, and > * twist order 4*(odd prime) > > must have A^2-4 being non-square. (The RFC doesn't say "odd" here; but, > by Hasse's theorem, large fields won't give group orders 16 or 8. We ask > for much larger fields and much larger group orders in ECC.) > > One might then check what the literature says about the structure of > Montgomery curves, and, based on that, formulate a proof of the > hypothesis, perhaps along the following lines: > > * Consider any A where A^2-4 is a nonzero square. > > * Consider the Montgomery curves E_{M,A,B}: By^2 = x^3+Ax^2+x for > nonzero B. If B is square then E_{M,A,B} is isomorphic to E_{M,A,1} > so #E_{M,A,B} is the "group order" above. If B is non-square then > #E_{M,A,B} is the "twist order" above. > > * E_{M,A,B} has three points of order 2, namely (0,0) and > ((-A+-sqrt(A^2-4))/2,0). > > * On E_{M,A,A+2}, the point (1,1) has order 4, so #E_{M,A,A+2} has to > be a multiple of 8. > > * For base field 3 mod 4, we're done at this point: the group order > or twist order is a multiple of 8, contradicting the assumption > that both orders are 4*(odd prime). So assume base field 1 mod 4 > from now on. Fix a square root i of -1 in the field. > > * By assumption the twist order is 4*(odd prime), so E_{M,A,A+2} is > isomorphic to E_{M,A,1}, so A+2 is a square, and (1,sqrt(A+2)) has > order 4 on E_{M,A,1}. > > * By assumption, the group order is 8*(odd prime). Since there are > exactly three points of order 2, the order-8 subgroup is isomorphic > to \Z/4 times \Z/2. In particular, there are exactly 3 points of > order 4, and 0 points of order 8. > > * Note that E_{M,A,1} is birationally equivalent to the Edwards curve > with coefficient d = (A+2)/(A-2). > > * By Theorem 3.1 of https://eecm.cr.yp.to/eecm-20111008.pdf, there > are exactly four points of order 4 on the Edwards curve doubling to > (0,-1), since d is a square. > > * By the same theorem, if either square root of 1/d were a square, > then there would be further points of order 4, contradiction. So > +-sqrt(1/d) aren't squares. > > * By Theorem 3.2 of https://eecm.cr.yp.to/eecm-20111008.pdf, there > are points of order 8 on this Edwards curve if there exists x in > the field with dx^4-2x^2+1 = 0 or with dx^4-2dx^2+1 = 0. > > * Pick a square root s of A+2. Then s^2-4 = A-2 is a square (since > A^2-4 is a square), so 4-s^2 is a square (since -1 is a square); > i.e., 4-s^2 = r^2 for some r. > > * Note that s is nonzero (since A=-2 wouldn't be elliptic). > > * Write m = (2-r)/s. Then m^2 = (2-r)^2/s^2 = (2-r)^2/(4-r^2) = > (2-r)/(2+r), so m^2+1 = 4/(2+r), so r = 4/(m^2+1)-2. > > * Note that m is nonzero (since r=2 would give s=0), so > s = (2-r)/m = 4m/(m^2+1). > > * Now d = -4m^2/(m^2-1)^2, and the square roots of 1/d are > +-i(m^2-1)/2m, so i(m^2-1)/2m isn't a square. > > * If (1-m^2)/2 were square, say x^2, then dx^4-2x^2+1 would be 0, > giving a point of order 8, contradiction. So (1-m^2)/2 isn't > square. > > * If (m+1)^2/2m were square, say x^2, then dx^4-2dx^2+1 would be 0, > giving a point of order 8, contradiction. So (m+1)^2/2m isn't > square; i.e., 2m isn't square. > > * The product of three non-squares is a non-square, so 2i is a > non-square. But that's contradicted by quadratic reciprocity: > fields 1 mod 8 have 2 and i both being squares; fields 5 mod 8 > have 2 and i both being non-squares; either way 2i is a square. > > Q.E.D. > > One might then say, wait, that's a rather long proof, and there are a > bunch of steps that could have gone wrong. One might then address this > by double-checking the steps, or writing a Sage script with numerical > sanity checks of each step, or writing a computer-checked proof. People > vary in how far they need to go before they're willing to confidently > say that these curves don't exist. > > > In the safecurves site it is made a condition for a safe Montgomery > > curve that A^2-4 should be a non-square. > > No. The SafeCurves ladder requirement is as follows: > > SafeCurves requires curves to support simple, fast, constant-time > single-coordinate single-scalar multiplication, avoiding conflicts > between simplicity, efficiency, and security. This is not a > requirement specifically to use Montgomery curves: there are other > types of curves that support simple, fast, constant-time ladders. > "Fast" means that implementations of scalar multiplication for the > same curve cannot be much faster, and "simple" means that reasonably > fast implementations of scalar multiplication for the same curve > cannot be much more concise. At this time there are no examples close > enough to the edge to warrant quantification of "much". > > The SafeCurves completeness requirement is as follows: > > SafeCurves requires curves to support simple, fast, _complete_, > constant-time single-coordinate single-scalar multiplication. This > includes the SafeCurves ladder requirement but goes further by > requiring completeness. SafeCurves also requires curves to support > simple, fast, _complete_, constant-time multi-scalar multiplication. > > The mention of A^2-4 being non-square is in the SafeCurves review of > relevant history: > > 2006 Bernstein had shown a more limited form of completeness for the > Montgomery ladder on Montgomery curves y^2=x^3+Ax^2+x with a unique > point of order 2, i.e., with A^2-4 not a square. > > ---D. J. Bernstein > > _______________________________________________ > CFRG mailing list -- cfrg@irtf.org > To unsubscribe send an email to cfrg-leave@irtf.org >

- [CFRG] RFC7748 Michael Scott
- [CFRG] Re: RFC7748 D. J. Bernstein
- [CFRG] Re: RFC7748 D. J. Bernstein
- [CFRG] Re: RFC7748 Michael Scott