--- 1/draft-ietf-lwig-curve-representations-06.txt 2019-07-08 16:15:08.748109507 -0700
+++ 2/draft-ietf-lwig-curve-representations-07.txt 2019-07-08 16:15:08.924113946 -0700
@@ -1,18 +1,18 @@
lwig R. Struik
Internet-Draft Struik Security Consultancy
-Intended status: Informational May 16, 2019
-Expires: November 17, 2019
+Intended status: Informational July 8, 2019
+Expires: January 9, 2020
Alternative Elliptic Curve Representations
- draft-ietf-lwig-curve-representations-06
+ draft-ietf-lwig-curve-representations-07
Abstract
This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves.
Requirements Language
@@ -30,21 +30,21 @@
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
- This Internet-Draft will expire on November 17, 2019.
+ This Internet-Draft will expire on January 9, 2020.
Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
@@ -75,42 +75,42 @@
10.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 13
10.4. JOSE Elliptic Curves Registration . . . . . . . . . . . 13
10.5. JOSE Algorithms Registration (1/2) . . . . . . . . . . . 13
10.6. JOSE Algorithms Registration (2/2) . . . . . . . . . . . 14
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 14
12.1. Normative References . . . . . . . . . . . . . . . . . . 14
12.2. Informative References . . . . . . . . . . . . . . . . . 16
Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 17
A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 17
- A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 17
+ A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 18
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 18
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 18
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 18
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 20
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 21
C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 21
- C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 21
+ C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 22
C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 22
Appendix D. Relationship Between Curve Models . . . . . . . . . 23
D.1. Mapping between Twisted Edwards Curves and Montgomery
- Curves . . . . . . . . . . . . . . . . . . . . . . . . . 23
+ Curves . . . . . . . . . . . . . . . . . . . . . . . . . 24
D.2. Mapping between Montgomery Curves and Weierstrass Curves 24
D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 25
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 25
E.1. Curve Definition and Alternative Representations . . . . 25
E.2. Switching between Alternative Representations . . . . . . 26
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 27
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 29
- F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 29
+ F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 30
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 30
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 31
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 32
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 33
G.1. Further Alternative Representations . . . . . . . . . . . 33
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 33
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 34
Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 36
H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 36
H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 36
@@ -118,42 +118,47 @@
H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 41
H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 42
H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 42
H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 44
H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 47
Appendix I. Point Compression . . . . . . . . . . . . . . . . . 48
I.1. Point Compression for Weierstrass Curves . . . . . . . . 49
I.2. Point Compression for Montgomery Curves . . . . . . . . . 49
I.3. Point Compression for Twisted Edwards Curves . . . . . . 50
Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 51
- J.1. Conversion between Bit Strings and Integers . . . . . . . 51
+ J.1. Conversion between Bit Strings and Integers . . . . . . . 52
J.2. Conversion between Octet Strings and Integers (OS2I,
- I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 51
+ I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 52
J.3. Conversion between Octet Strings and Bit Strings (BS2OS,
OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 52
J.4. Conversion between Field Elements and Octet Strings
- (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 52
+ (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 53
J.5. Conversion between Elements of Z mod n and Octet Strings
(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 53
- J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 53
- Appendix K. Representation Examples Curve25519 Family Members . 54
+ J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 54
+ Appendix K. Representation Examples Curve25519 Family Members . 55
K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 55
- K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 56
+ K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 57
K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 58
- K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 59
+ K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 60
K.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 61
Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 62
L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 62
L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 62
- L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 62
- L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 62
- Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 63
+ L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 63
+ L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 63
+ L.3. Mapping to Curve Points . . . . . . . . . . . . . . . . . 63
+ L.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 63
+ L.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 64
+ L.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 65
+ L.4. Randomized Representation of Curve Points . . . . . . . . 65
+ Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 66
1. Fostering Code Reuse with New Elliptic Curves
It is well-known that elliptic curves can be represented using
different curve models. Recently, IETF standardized elliptic curves
that are claimed to have better performance and improved robustness
against "real world" attacks than curves represented in the
traditional "short" Weierstrass model. This document specifies an
alternative representation of points of Curve25519, a so-called
Montgomery curve, and of points of Edwards25519, a so-called twisted
@@ -748,31 +753,43 @@
[Mont-Ladder]
P.L. Montgomery, "Speeding the Pollard and Elliptic Curve
Methods of Factorization", Mathematics of
Computation, Vol. 48, 1987.
[Rosener] N. Rosener, "Evaluating the Performance of Transformations
Between Curve Representations in Elliptic Curve
Cryptography for Constrained Device Security",
M.Sc. Universitat Bremen, August 2018.
+ [SWUmap] E. Brier, J-S. Coron, Th. Icart, D. Madore, H. Randriam,
+ M. Tibouchi, "Efficient Indifferentiable Hashing into
+ Ordinary Elliptic Curves", CRYPTO 2010, Lecture Notes in
+ Computer Science, Vol. 6223, New York: Springer-Verlag,
+ 2010.
+
[tEd] D.J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters,
"Twisted Edwards Curves", Africacrypt 2008, Lecture Notes
in Computer Science, Vol. 5023, New York: Springer-Verlag,
2008.
[tEd-Formulas]
H. Hisil, K.K.H. Wong, G. Carter, E. Dawson, "Twisted
Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes
in Computer Science, Vol. 5350, New York: Springer-Verlag,
2008.
+ [Tibouchi]
+ M. Tibouchi, "Elligator Squared -- Uniform Points on
+ Elliptic Curves of Prime Order as Uniform Random Strings",
+ Financial Cryptography 2014, Lecture Notes in Computer
+ Science, Vol. 8437, New York: Springer-Verlag, 2014.
+
[Wei-Ladder]
T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve
Multiplication Resistant Against Side Channel Attacks",
Centre for Applied Cryptographic Research, Corr 2002-03,
2002.
Appendix A. Some (non-Binary) Elliptic Curves
A.1. Curves in short-Weierstrass Form
@@ -916,21 +933,23 @@
field GF(p) as a subset. If m=1, we always pick f(z):=z, so that the
definions of GF(p) and GF(p^1) above coincide. If m>1, then GF(q) is
called a (nontrivial) extension field over GF(p). The number p is
called the characteristic of GF(q).
A field element y is called a square in GF(q) if it can be expressed
as y:=x^2 for some x in GF(q); it is called a non-square in GF(q)
otherwise. If y is a square in GF(q), we denote by sqrt(y) one of
its square roots (the other one being -sqrt(y)). For methods for
computing square roots and inverses in GF(q) - if these exist - see
- Appendix L.1 and Appendix L.2, respectively.
+ Appendix L.1 and Appendix L.2, respectively. For methods for mapping
+ a nonzero field element that is not a square in GF(q) to a point of a
+ curve, see Appendix L.3.
NOTE: The curves in Appendix E and Appendix G are all defined over a
prime field GF(p), thereby reducing all operations to simple modular
integer arithmetic. Strictly speaking we could, therefore, have
refrained from introducing extension fields. Nevertheless, we
included the more general exposition, so as to accommodate potential
introduction of new curves that are defined over a (nontrivial)
extension field at some point in the future. This includes curves
proposed for post-quantum isogeny-based schemes, which are defined
over a quadratic extension field (i.e., where q:=p^2), and elliptic
@@ -1103,21 +1123,21 @@
One can map points of the Montgomery curve M_{A,B} to points of the
Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and
b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence,
which - in fact - is an isomorphism between M_{A,B} and W_{a,b},
thereby showing that, e.g., the discrete logarithm problem in either
curve model is equally hard.
The mapping from M_{A,B} to W_{a,b} is defined by mapping the point
at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while
mapping each other point (u,v) of M_{A,B} to the point
- (X,Y):=(u/B+A/(3*B),v/B) of W_{a,b}. Note that not all Weierstrass
+ (X,Y):=((u+A/3)/B,v/B) of W_{a,b}. Note that not all Weierstrass
curves can be injectively mapped to Montgomery curves, since the
latter have a point of order two and the former may not. In
particular, if a Weierstrass curve has prime order, such as is the
case with the so-called "NIST curves", this inverse mapping is not
defined.
If the Weierstrass curve W_{a,b} has a point (alpha,0) of order two
and c:=a+3*(alpha)^2 is a square in GF(q), one can map points of this
curve to points of the Montgomery curve M_{A,B}, where A:=3*alpha/
gamma and B:=1/gamma and where gamma is any square root of c. In
@@ -1140,21 +1160,21 @@
form that hard-code the domain parameter a to a= -3 (which value is
known to allow more efficient implementations) cannot always be used
this way, since the curve W_{a,b} resulting from an isomorphic
mapping cannot always be expressed as a Weierstrass curve with a=-3
via a coordinate transformation. For more details, see Appendix F.
D.3. Mapping between Twisted Edwards Curves and Weierstrass Curves
One can map points of the twisted Edwards curve E_{a,d} to points of
the Weierstrass curve W_{a,b}, via function composition, where one
- uses the isomorphic mapping between twisted Edwards curve and
+ uses the isomorphic mapping between twisted Edwards curves and
Montgomery curves of Appendix D.1 and the one between Montgomery and
Weierstrass curves of Appendix D.2. Obviously, one can use function
composition (now using the respective inverses - if these exist) to
realize the inverse of this mapping.
Appendix E. Curve25519 and Cousins
E.1. Curve Definition and Alternative Representations
The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined
@@ -2276,29 +2295,31 @@
where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this
equation does not have a solution in GF(q) and the ordered pair (X,
t) does not correspond to a point of this curve. Otherwise, there
are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero
element of GF(q), one can uniquely recover the Y-coordinate for which
par(Y):=t and, thereby, the point P:=(X, Y). This is also the case
if alpha=0 and t=0, in which case Y=0 and the point P has order two.
However, if alpha=0 and t=1, the ordered pair (X, t) does not
correspond to the outcome of the point compression function.
- If the Weierstrass curve W_{a,b} has a point of order two, we extend
- the definition of the point compression function to all points of the
- curve, by associating the (non-affine) point at infinity O with the
- ordered pair compr(O):=(X,1), where (X,0) is any point of order two,
- and recover this point accordingly. (Note that this corresponds to
- the case alpha=0 and t=1 above.) In this case, the point at infinity
- O can be represented by any ordered pair (X, 1) of elements of GF(q),
- where (X,0) is any point of order two. Note that this ordered pair
- does not satisfy the defining equation of the curve in question.
+ We extend the definition of the point compression function to all
+ points of the curve W_{a,b}, by associating the (non-affine) point at
+ infinity O with any ordered pair compr(O):=(X,0), where X is any
+ element of GF(q) for which alpha:=X^3+a*X+b is a non-square in GF(q),
+ and recover this point accordingly. In this case, the point at
+ infinity O can be represented by any ordered pair (X,0) of elements
+ of GF(q) for which X^3+a*X+b is a non-square in GF(q). Note that
+ this ordered pair does not satisfy the defining equation of the curve
+ in question. An application may fix a specific suitable value of X
+ or choose multiple such values and use this to encode additonal
+ information. Further details are out of scope.
I.2. Point Compression for Montgomery Curves
If P:=(u, v) is an affine point of the Montgomery curve M_{A,B}
defined over the field GF(q), then so is -P:=(u, -v). Since the
defining equation B*v^2=u^3+A*u^2+u has at most two solutions with
fixed u-value, one can represent P by its u-coordinate and one bit of
information that allows one to distinguish P from -P, i.e., one can
represent P as the ordered pair compr(P):=(u, par(v)). If P is a
point of order two, one can uniquely represent P by its u-coordinate
@@ -2347,21 +2368,31 @@
-x. If alpha is a nonzero element of GF(q), one can uniquely recover
the x-coordinate for which par(x):=t and, thereby, the affine point
P:=(x, y). This is also the case if alpha=0 and t=0, in which case
x=0 and the point P has order one or two. However, if alpha=0 and
t=1, the ordered pair (t, y) does not correspond to the outcome of
the point compression function.
Note that the point compression function is defined for all points of
the twisted Edwards curve E_{a,d} (subject to the Note in
Appendix C.3). Here, the identity element O:=(0,1) is associated
- with the compressed point compr(O):=(0,1).
+ with the compressed point compr(O):=(0,1). (Note that this
+ corresponds to the case alpha=0 and t=0 above.)
+
+ We extend the definition of the compression function further, to also
+ include a special marker element 'btm', by associating this marker
+ element with the ordered pair compr(btm):=(1,1) and recover this
+ marker element accordingly. (Note that this corresponds to the case
+ alpha=0 and t=1 above.) The marker element 'btm' can be represented
+ by the ordered pair (1,1) of elements of GF(q). Note that this
+ ordered pair does not satisfy the defining equation of the curve in
+ question.
Appendix J. Data Conversions
The string over some alphabet S consisting of the symbols x_{l-1},
x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by
str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string
(over S) is the number of symbols it contains (here: l). The empty
string is the (unique) string of length l=0.
The right-concatenation of two strings X and Y (defined over the same
@@ -2676,21 +2708,21 @@
f5b5da19 923d6da7,
where the rightmost bit of the rightmost octet indicates the parity
of the x-coordinate of the point of Edwards25519 in question (which,
in this case, are zero and one, respectively, since x is even and x1
is odd). See Appendix I.3 and Appendix J for further detail on
(squeezed) point compression.
The scalar representation and (squeezed) point representation
illustrated above are fully consistent with the representations
- specified in [RFC8032]. Note that, contrary to [RFC8032], [RFC8032]
+ specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032]
requires unique representations of all elements of GF(p).
K.3. Example with Wei25519
Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519:
X 14428294459702615171094958724191825368445920488283965295163094662
783879239338
(=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
@@ -2933,16 +2964,131 @@
1/y:=y^{q-2} (since y^{q-1}=1).
Further details are out of scope. If inverses are easy to compute in
GF(q), then so are these in GF(q^2).
The inverses of two nonzero elements y1 and y2 of GF(q) can be
computed by first computing the inverse z of y1*y2 and by
subsequently computing y2*z=:1/y1 and y1*z=:1/y2.
+L.3. Mapping to Curve Points
+
+ One can map elements of GF(q) that are not a square in GF(q) to
+ points of a Weierstrass curve (see Appendix L.3.1), to points of a
+ Montgomery curve (see Appendix L.3.2), or to points of a twisted
+ Edwards curve (see Appendix L.3.3), under some mild conditions on the
+ domain parameters. Details on mappings that apply if these
+ conditions are not satisfied are out of scope.
+
+L.3.1. Mapping to Points of Weierstrass Curve
+
+ The description below assumes that the domain parameters a and b of
+ the Weierstrass curve W_{a,b} are nonzero. For ease of exposition,
+ we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of
+ W_{a,b} one has Y^2=f(X).)
+ If t is an element of GF(q) that is not a square in GF(q) and that is
+ unequal to -1, then the element X:=(-b/a)*(1+1/(t+t^2)) is the unique
+ solution of the equation f(t*X)=t^3*f(X). Consequently, either X or
+ X':=t*X is the x-coordinate of an affine point of W{a,b}, depending
+ on whether f(X) is a square in GF(q).
+
+ a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)) then t is mapped
+ to the point P(t):=(X, Y);
+
+ b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is
+ mapped to the point P(t):=(X', -Y').
+
+ Formally, this mapping is not properly defined, since a nonzero
+ square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is
+ properly defined, however, if one designates for each element in
+ GF(q) that is a square in GF(q) precisely one square root as "the"
+ square root of this element. Note that always picking the square
+ root with zero parity (see Appendix I) satisfies this condition, as
+ does using one of the square root functions specified in
+ Appendix L.1.
+
+ If -1 is not a square in GF(q), this element is mapped to the point
+ at infinity O of W_{a,b}.
+
+ The set of points of W_{a,b} that arises this way has size roughly
+ 3/8 of the order of the curve and each such point arises as image of
+ one or two t values. Further details are out of scope.
+
+L.3.2. Mapping to Points of Montgomery Curve
+
+ The description below assumes that the domain parameter A of the
+ Montgomery curve M_{A,B} is nonzero. For ease of exposition, we
+ define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of
+ M_{A,B} one has B*v^2=f(u).)
+
+ If t is an element of GF(q) that is not a square in GF(q) and that is
+ unequal to -1, then the element u:=-(1+1/t)/A is the unique solution
+ of the equation f(t*u)=t^3*f(u). Consequently, either u or u':=t*u
+ is the u-coordinate of an affine point of M{A,B}, depending on
+ whether f(u)/B is a square in GF(q).
+
+ a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is
+ mapped to the point P(t):=(u, v);
+
+ b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then
+ t is mapped to the point P(t):=(u', -v').
+
+ As before, formally, this mapping is not properly defined, since a
+ nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it
+ is properly defined, however, if one designates for each element in
+ GF(q) that is a square in GF(q) precisely one square root as "the"
+ square root of this element. Note that always picking the square
+ root with zero parity (see Appendix I) satisfies this condition, as
+ does using one of the square root functions specified in
+ Appendix L.1.
+
+ If -1 is not a square in GF(q), this element is mapped to the point
+ at infinity O of M_{A,B}.
+
+ The set of points of M_{A,B} that arises this way has size roughly
+ 1/2 of the order of the curve and each such point arises as image of
+ precisely one t value. Further details are out of scope.
+
+L.3.3. Mapping to Points of Twisted Edwards Curve
+
+ One can map elements of GF(q) that are not a square in GF(q) to
+ points of the twisted Edwards curve E_{a,d} via function composition,
+ where one uses the mapping of Appendix L.3.1 to arrive at a point of
+ the Weierstrass curve W_{a,b} and where one subsequently uses the
+ isomorphic mapping between twisted Edwards curves and Weierstrass
+ curves of Appendix D.3 to arrive at a point of E_{a,d}. Another
+ mapping is obtained by function composition, where one instead uses
+ the mapping of Appendix L.3.2 to arrive at a point of the Montgomery
+ curve M_{A,B} and where one subsequently uses the isomorphic mapping
+ between twisted Edwards curves and Montgomery curves of Appendix D.1
+ to arrive at a point of E_{a,d}. Obviously, one can use function
+ composition (now using the respective pre-images - if these exist) to
+ realize the pre-images of either mapping.
+
+L.4. Randomized Representation of Curve Points
+
+ The mappings of Appendix L.3.1, Appendix L.3.2, and Appendix L.3.3
+ allow one to represent a curve point Q as a specific element of
+ GF(q), provided this point arises as a point in the range of the
+ mapping at hand. For Montgomery curves and twisted Edwards curves,
+ this covers roughly half of the curve points; for Weierstrass curves,
+ roughly 3/8 of the curve points. One can extend the mappings above,
+ by mapping a pair (t1, t2) of inputs to the point Q:=P2(t1,
+ t2):=P(t1) + P(t2). In this case, each curve point has roughly q/4
+ representations as a pair (t1, t2) on average. In fact, one can show
+ that if the input pairs are generated uniformly at random, then the
+ corresponding curve points follow a distribution that is also
+ (statistically indistinguishable from) a uniform distribution. Here,
+ each pair (t1, t2) deterministically yields a curve point, whereas
+ for each curve point Q, a randomized algorithm yields a pair (t1, t2)
+ of pre-images of Q, where the expected number of randomized pre-
+ images one has to try is small (four if one uses the mapping of
+ Appendix L.3.1; two if one uses the mapping of Appendix L.3.2). For
+ further details, see [Tibouchi].
+
Author's Address
Rene Struik
Struik Security Consultancy
Email: rstruik.ext@gmail.com