[Cfrg] Question about edwards448 mapping in draft-irtf-cfrg-curves-11

Andrew Bennett <potatosaladx@gmail.com> Mon, 18 January 2016 03:59 UTC

Return-Path: <potatosaladx@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 98FEC1AD094 for <cfrg@ietfa.amsl.com>; Sun, 17 Jan 2016 19:59:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.599
X-Spam-Level:
X-Spam-Status: No, score=-0.599 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id vjgBj2kYKS3i for <cfrg@ietfa.amsl.com>; Sun, 17 Jan 2016 19:59:29 -0800 (PST)
Received: from mail-yk0-x231.google.com (mail-yk0-x231.google.com [IPv6:2607:f8b0:4002:c07::231]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 40AF71AD087 for <cfrg@irtf.org>; Sun, 17 Jan 2016 19:59:29 -0800 (PST)
Received: by mail-yk0-x231.google.com with SMTP id a85so522813402ykb.1 for <cfrg@irtf.org>; Sun, 17 Jan 2016 19:59:29 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:from:date:message-id:subject:to:content-type; bh=JiRsHbNuCIQaiZSSZmRhk4pr4Z3HzgllamAo1G2cOJ4=; b=o4rHq35lZo+LXxTlo5+ov8Rx8RMMkoZIbbbZD8zNK2Gzjm1n1hKiozBFY9WASggbAj hRMFyp+7DLANWmsJJEshZyrdFePY2WayH3k/NdtJF21rE2G8VL2ObRSuYm2w/fvxpzB4 10a+qcuSdRSMVO+Z4SUTSJZ53aLfsfxnixj+SAFDJHMS2vl4LhXilLn7I4TMQVDbCbx+ kcRinN1PV8pF+cnL6PzCO5IVvcCseCSRrqSsPBbvrpFg98HdzOmulnN6YsXDqRzJNRRj /LefXJudNq81pW7meufcyhuUe4kImg2yW9kMJK8kV7IbXsENZSvUYua/cCrTzaz5WgfJ Byfw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:from:date:message-id:subject:to :content-type; bh=JiRsHbNuCIQaiZSSZmRhk4pr4Z3HzgllamAo1G2cOJ4=; b=b1EsK6PeoL+i2EGz+FrAO7qNE3OM/cPyCEp2xJ5BuvCclbBy9Hluf1a7XcldOfb8Kt HKOkQf2xvhevsMwZfRIi45/lKZrO9fbSTOTkZob68Z6gK96u7HllRt4eOYz73oFGUCi9 fmz7aaYtbmeyEsgGkEUsHTGAkjUdlxjUaEWNkeBjdZUnYbZQ6qHSsUOh7cLzKZDDO1i6 yzU+85SAGYEomppkf5XyN+r3dm5D9XhFZu+URvxivVjtAPGA3ZLKXghn+cyi+qP0cFyZ A0EhitCLJYZc0Z/9dI4runIdVKHmWJFfbiPkXxuqsN3FOUWNopC3yNoeaHSttmoc0fsH UADA==
X-Gm-Message-State: ALoCoQnJ4gsyIgyUyXcTZOnMX9J3sFnq076Rt4hjztFqaekslEN2pmaYDy3Q5hEnoXP1xnAdtfN81YdY2Y25do7mAzlJmxMx1w==
X-Received: by 10.129.137.68 with SMTP id z65mr13702869ywf.311.1453089568368; Sun, 17 Jan 2016 19:59:28 -0800 (PST)
MIME-Version: 1.0
From: Andrew Bennett <potatosaladx@gmail.com>
Date: Mon, 18 Jan 2016 03:59:18 +0000
Message-ID: <CAMRqpb8g1so9=26w3Png3HaBthMeE1p7Q5Q2-Sz7AnNwWZsAWw@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="94eb2c064ac08caf1d052993c76e"
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/87dWyeaByAjt0TqxjHzL2Rzj6ik>
Subject: [Cfrg] Question about edwards448 mapping in draft-irtf-cfrg-curves-11
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 18 Jan 2016 03:59:31 -0000

Hello,

Quick disclaimer: my question detailed below might simply be due to my own
lack of knowledge related to the mathematical concepts of elliptic curves
and their isogenies.

In section 4.2 [1], there are 3 curves described: (1) a Montgomery curve
named "curve448" (2) an unnamed birationally equivalent Edwards curve (3) a
4-isogenous Edwards curve named "edwards448".

For each curve, a set of (u, v) and (x, y) functions are provided which are
easily verifiable using the provided basepoints between curves (1) and (2)
and partially between curves (1) and (3).

My question is about the 4-isogeny mapping listed under (3):

(u, v) = (y^2/x^2, (2 - x^2 - y^2)*y/x^3)
(x, y) = (4*v*(u^2 - 1)/(u^4 - 2*u^2 + 4*v^2 + 1),
          -(u^5 - 2*u^3 - 4*u*v^2 + u)/
          (u^5 - 2*u^2*v^2 - 2*u^3 - 2*v^2 + u))

The (u, v) functions return the expected basepoint from "curve448" when
using the x and y values from "edwards448" (in python/sage):

# variables used in examples below
p = 2^448 - 2^224 - 1
u = 5
v =
355293926785568175264127502063783334808976399387714271831880898435169088786967410002932673765864550910142774147268105838985595290606362
x =
224580040295924300187604334099896036246789641632564134246125461686950415467406032909029192869357953282578032075146446173674602635247710
y =
298819210078481492676017930443930673437544040154080242095928241372331506189835876003536878655418784733982303233503462500531545062832660

# testing (u, v) functions; both return True
u == y^2/x^2 % p
v == (2 - x^2 - y^2)*y/x^3 % p

However, I am unable to produce the expected "edwards448" basepoint from
the (x, y) functions when using the u and v values from "curve448":

# testing (x, y) functions; both return False
x == 4*v*(u^2 - 1)/(u^4 - 2*u^2 + 4*v^2 + 1) % p
y == -(u^5 - 2*u^3 - 4*u*v^2 + u)/(u^5 - 2*u^2*v^2 - 2*u^3 - 2*v^2 + u) % p

# x returned is:
209710714663589237570084264541991420589833663592202160838176801982171960997051286469552065490170659385708816452452440655275673121357616
# y returned is:
603515570432573637134887094808958022419371301976351441963100315034426774344109511210661998660350679225364893651728492312845104034682937

Adding to my confusion, while searching for more understanding of the
Edwards-Montgomery mapping, I found another paper [2] which contains a
"Proposition 2" with similar functions which produce the same x and y
values:

# variables used in examples below
d = -39081
A = -(4*d - 2)

# testing alternative (x, y) functions; both return False returning
identical x and y values mentioned above
x == (-4*(1 - u^2)*v)/(u^4 - 2*u^2 + 4*v^2 + 1) % p
y == ((u^2 + 2*v - 1)*(u^2 - 2*v - 1))/(2*A*u^3 + u^4 + 2*A*u + 6*u^2 + 1)
% p

All of the above code examples are also available in a gist [3].

My question is: Are the functions for the (x, y) mapping correct?  If so,
am I calculating the resulting x and y values correctly?  If so, how are
the x and y values returned related to "edwards448"?

Any help with understanding the (x, y) mapping between "curve448" and
"edwards448" would be greatly appreciated.

Thanks,
Andrew Bennett

[1] https://tools.ietf.org/html/draft-irtf-cfrg-curves-11#section-4.2
[2] http://cryptosith.org/papers/isogenies_tEd2Mont.pdf
[3] https://gist.github.com/potatosalad/fc758365095d5d659cdb