Now to mailing address "[email protected]". (I do not understand why "LWIG"
has an "lwip" mailing address.)
-------- Forwarded Message --------
Subject: (initial triage - final disposition with rev-02) Re: Fwd:
Review of draft-ietf-lwig-curve-representations-00 by crypto review panel
Date: Tue, 11 Dec 2018 09:36:53 -0500
From: Rene Struik <[email protected]>
To: Mohit Sethi M <[email protected]>, [email protected]
<[email protected]>, [email protected]
Hi Stanislav:
Thanks for your review.
Some brief initial feedback now; final disposition will be with rev02.
(One my "to dos prior to 2018-end" is to add test vectors to a draft-02
version that I have had on my machine since Nov 15th. That version also
includes some minor editorial massaging.)
BTW - all calculations (including isogenies) were done in Sage and
write-up is based on an extensive LaTeX document with curve
constructions for personal use. I will double-check everything prior to
releasing rev-02.
On 12/11/2018 7:46 AM, Mohit Sethi M wrote:
Hi all,
We have received the following detailed review of
draft-ietf-lwig-curve-representations from Stanislav Smyshlyaev on
behalf of the Crypto Review Panel.
Thank you Stanislav for the excellent review. It would be great if the
authors can address his feedback and submit a new version.
Please feel free to chime in if you have any additional feedback on
this document at this stage.
Zhen and Mohit
-------- Forwarded Message --------
Subject: Review of draft-ietf-lwig-curve-representations-00 by crypto
review panel
Date: Tue, 11 Dec 2018 07:50:11 +0200
From: Stanislav V. Smyshlyaev <[email protected]>
To: Mohit Sethi M <[email protected]>, [email protected]
<[email protected]>, [email protected] <[email protected]>,
Alexey Melnikov <[email protected]>
Good afternoon,
Please find below the review of the document made on behalf of Crypto
Review Panel.
I'll be happy to discuss all questions raised in the review directly
via e-mail: [email protected] <mailto:[email protected]>
Document: draft-ietf-lwig-curve-representations-00
Reviewer: Stanislav Smyshlyaev
Review Date: 2018-11-26
Summary: Revision needed
The document “Alternative Elliptic Curve Representations” contains
procedures and formulae of representing Montgomery curves and
(twisted) Edwards curves in short Weierstrass form.
The reviewer believes that the document is very helpful and can be
used by developers implementing ECC operations in real-world
applications.
The reviewer has verified all decimal numbers (and hexadecimal
numbers, where they are provided in the draft) and does not have any
concerns besides the following ones.
Since some of the concerns seem to be important enough for the overall
document, the reviewer recommends to send an updated version of the
draft to Crypto Review Panel for a new review.
The review was made for draft-ietf-lwig-curve-representations-00.
During the review process an updated version
draft-ietf-lwig-curve-representations-01 was published – some comments
about the -01 version can be found in the end of the current review.
Comments:
1) Section C.2: The mapping from Weierstrass curves to Montgomery
curves is not defined in the current version. The mapping from
Weierstrass to Montgomery cannot usually be described as shortly as
others, but maybe it could still be useful here. For example, the root
of x^3+ax+b in Fp could be provided explicitly.
RS>> True: although I am not sure how useful this is, this could be
done. One of the issues is that a Weierstrass curves with a point of
order two does not automatically lead to a Montgomery curve. Having to
spell out those conditions may make life really hard for non-specialists
and obscure the main message. My main point was to try and exemplify how
the different curve models are sometimes the "same animal, in disguise",
which could be helpful, e.g., when implementing Ed25519 and Curve225519
on a small device or when one wishes to reuse an existing HW
implementation of short Weierstrass curves. <<RS
2) It would be better to stress in Appendix C.1 that formulae provided
there do not allow to get parameter a of the twisted Edwards
curve equal to 1 or -1. In Appendix D.2 additional constant c is used
that helps to obtain the curve with a equal to -1 (this fact by the
way implies that the phrase “Here, we used the mapping of Appendix
C.1” is inaccurate).
RS>> I did indeed use the isomorphism from E{a,d} to E_{1,d/a}, for a a
square in GF(q), as well.<<RS
2a) Section D.2: The formulae (u,v) -> (c*u/v, (u-1)/(u+1)) lead to an
error. It is not clear why it is needed to multiply by the constant c.
RS>> Hmm. I copied this from LaTeX source based on checked Sage
calculations. I will double check all of this once more (also
elsewhere). <<RS
2b) Section D.3: The Montgomery curve Curve25519 doesn’t correspond to
Twisted Edwards curve Edwards25519 because of (A+2)/B = (486662+2)/1
!= -1.
RS>> It does correspond to this, since I added the "c" multiplication in
the x-coordinate, since c^2=-(A+2)/B. See your point under your point 2)
above. <<RS
2c) If one uses the formula from C.1 for Montgomery to Edwards mapping
(a:=(A+2)/B and d:=(A-2)/B), she obtains that d for Edwards25519 is
equal to 486660 but not the value of d which is provided in D.3.
RS>> It does correspond to this, for the same reason as above under your
point 2b) above. <<RS
3) Section E.1: The isomorphic mapping between W_{a,b} and W_{a',b'}
should be defined as a’:=a*s^4 and b’:=b*s^6, instead of a:=a'*s^4 and
b:=b'*s^6. Otherwise the mapping is defined incorrectly and the test
vectors from F.3 are incorrect.
RS>> This is often confusing (initially also to me). However, I do think
this is correct, but will of course double check my Sage code.<<RS
4) It seems that the formula for lambda in case Q:=2P for Montgomery
curve is wrong. According to
http://hyperelliptic.org/EFD/g1p/auto-montgom.html and to
https://eprint.iacr.org/2017/212.pdf (page 4) it should be: lambda =
(3*x1^2 + 2*A*x1 + 1)/(2*B*y1). So you need to add “B” as a factor in
the denominator.
RS>> This small editorial glitch was corrected in version 01. <<RS
5) in Appendix D.2 it would be better to stress explicitly that we
work with projective coordinates, otherwise the formulae do not have
to be correct.
RS>>I did separate out the points of order one and two to make the
rational mappings always work. Did I miss something here? <<RS
Editorial comments:
a) It seems that the text will be easier to read if the formulae for
group law are provided in the following form (for example, for
Weierstrass):
x = lambda^2 – x1 – x2
y = lambda * ... (at a new line, but with “and”)
lambda = ... (again at a new line)
b) In reviewer’s opinion, the text will be easier to read if different
symbols for coordinates of different forms of a curve are used. For
example, (x,y) for Weierstrass, (X,Y) for Montgomery and (u,v) for
Edwards. And it would be better to use the same symbols in different
parts of the document (now (u,v) is used for Montgomery in A.2 and
(x,y) for Montgomery in B.2).
RS>> Agreed. I will do this for version 02. <<RS
c) The term “short Weierstrass form” is widely used in publications as
is. The draft, however, has two variants of it – “short” Weierstrass
form and short-Weierstrass form. It seems that one (commonly used)
variant would be better to use.
d) The reviewer recommends to use only “GF(p)” everywhere in document
instead of “GF(q)” together with “GF(p)”. For example, now in C.1 –
GF(q) and GF(p) in D.1.
RS>> I would like to keep this as is, just in case at some point in the
future, someone wishes to specify a curve over GF(q), where q=p^2, for
example (whether this is FourQ or a curve used for isogeny-based key
agreement. <<RS
Additional clarifications might be useful:
Also the reviewer believes that it will be useful to write additional
clarifications in D.2 on “can be implemented via integer-only
arithmetic as a shift of (p+A)/3 for the isomorphic mapping and a
shift of -(p+A)/3 for its inverse” regarding the need of using the mod
operation for transformation.
RS>> If I parse this comment correctly: indeed one may need to add or
subtract the modulus p (but does not need to implement GF(p) arithmetic
otherwise for this conversion). <<RS
###### draft-ietf-lwig-curve-representations-01:
The concerns 1, 2, 2a, 2b, 2c, 4 and 5 for 00 version are still valid
for version -01. The concern 3 has been addressed.
Additional question for draft-ietf-lwig-curve-representations-01:
appendices C.1 and C.2 contain information about properties that help
to recover y-coordinates of a multiple point if one uses Montgomery
ladder. This information may not be needed in the draft, since the
ladder itself is not described there.
RS>> I do think the recovery of the y-coordinate is useful, e.g., if one
wishes to implement Ed25519 using an extension of the Montgomery ladder
for Curve25519 (Example 4.2 in rev-01 document). This could be
especially useful for constrained devices (and, in my opinion, should
have been part of RFC 7748). <<RS
Best regards,
Stanislav Smyshlyaev
--
email:[email protected] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
_______________________________________________
Lwip mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/lwip
