[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
- [Cfrg] Question about edwards448 mapping in draft… Andrew Bennett
- Re: [Cfrg] Question about edwards448 mapping in d… Ilari Liusvaara
- Re: [Cfrg] Question about edwards448 mapping in d… Andrew Bennett