in my previous response, I referenced RFC 7836, but did not copy the
correct snippet. This is corrected below. (It is only an illustration,
so not that important. However, it should be correct, of course.). My
apologies.
On 5/13/2019 9:42 AM, Rene Struik wrote:
Hi Mohit:
Thanks for your comments. Please see my feedback below.
Best regards, Rene
On 5/13/2019 7:46 AM, Mohit Sethi M wrote:
Hi Rene,
In Section 1, the draft says:
Montgomery curve, and of points of Edwards25519, a so-called twisted
Edwards curve, which are both specified in [RFC7748
<https://tools.ietf.org/html/rfc7748>]
What about referencing RFC 8032: https://tools.ietf.org/html/rfc8032
<https://tools.ietf.org/html/rfc8032>?
RS>> The draft does reference RFC 8032. However, the curve
Edwards25519 is specified in RFC 7748 (see Section 4.1, p. 4).
Admittedly, the naming is somewhat confusing, since Edwards25519
refers to the curve and Ed25519 to the signature scheme (but the
confusing naming already existed). <<RS
A lot of normative parts are currently in the appendix. Wouldn't it
make sense to move them into the actual document body. I looked at
RFC 7748 for example and it defines Curve25519 in the main body:
https://tools.ietf.org/html/rfc7748#section-6.1
<https://tools.ietf.org/html/rfc7748#section-6.1>. It is good to keep
the example computations in Appendix E.3 and Appendix G.3, see
Appendix K as the document currently does.
RS>> This may indeed be possible, although I do not see right away how
much this buys. The main message of the draft is in Section 3 (which
explains how switching between different representations works), and
in Section 4 (which explains how this could be used to either reuse
code or reuse already existing specifications); the remainder being
just "knobs and bolts".
Virtually all the appendices is background material on curves, finite
fields, mappings, representations, etc. (with the exception of
Appendix E, G, H, and K -- which does the switching for Curve25519
"cousins").
Let me rethink the organizational suggestion. Main objective I would
have is that is one were to produce another curve, say, "mohit2519"
and use this to specify another key agreement scheme "m2519" or
signature scheme "sethi2519", one could simply specify the domain
parameters in Weierstrass form and the corresponding versions in
Montgomery and Edwards form, and representations, all reusing
definitions in the current draft, and be done with this as a 2-page
document. (Reason why the draft has so many appendices is that I am
not aware of any technical/academic paper that concisely describes
this material [the draft arose from my desire to set the record
straight here.)
As an example, the Russian schemes defined in [1], could be defined as
instantiations of the current draft and existing generic signature and
Diffie-Hellman schemes, in the following form:
#Russia: [Cfrg] Curve Parameters for Russian standardization
(Stanislav V. Smyshlyaev, January 30, 2015), RFC 7836 [1]
#classification: id-tc26-gost-3410-2012-256-paramSetA;
OID=1.2.643.7.1.2.1.1.1
namedcurve="RussiatEd256"
type="tEd"
p=2^256-617; Fp=GF(p)
#Wei: aa=(3-A^2)/(3*B^2); bb=(2*A^3-9*A)/(27*B^3);
aa=87789765485885808793369751294406841171614589925193456909855962166505018127157
bb=18713751737015403763890503457318596560459867796169830279162511461744901002515
GGx=Fp(65987350182584560790308640619586834712105545126269759365406768962453298326056)
GGy=Fp(22855189202984962870421402504110399293152235382908105741749987405721320435292)
aa=Fp(aa); bb=Fp(bb); E=EllipticCurve(Fp,[aa,bb]);
#tEd:
a=1
d=2724414110474605931834268501164757645998726878473076809432604223414351675387
a=Fp(a); d=Fp(d);
Gx=Fp(13);
Gy=Fp(43779144989398987843428779166090436406934195821915183574454224403186176950503);
#Mont: AA=2*(a+d)/(a-d); BB=4/(a-d);
A=Fp(77708437198656856547901205427399062199001375716101406879613034791099442163334)
B=Fp(77708437198656856547901205427399062199001375716101406879613034791099442163336)
u=Fp(92146305408514047021764629781018839776217875356491594589642772615438293166627)
v=Fp(24902344914088187528377430753722665806365988052905594051427533894712657880405)
#common parms:
h=4;
n=28948022309329048855892746252171976963338560298092253442512153408785530358887
h1=4;
n1=28948022309329048855892746252171976963296432034728028577216638595171034460773
tr=-84256526728449730591029627228991796228
GG=E(GGx,GGy);
Zn=GF(n)
Ref: [1] RFC 7836 - Guidelines on the Cryptographic Algorithms to
Accompany the Usage of Standards GOST R 34.10-2012 and GOST R
34.11-2012 (March 2016)
<<RS
In Section 5, wouldn't it make sense to mention that while re-using
the same code base has advantages, it can also negatively affect the
performance in terms of the computation time?
RS>> The main benefits of the curve model "switches" are (a) code
reuse and (b) reuse of existing specification. As to code reuse, the
computational effect depends on how one does accounting and whether or
not one takes implementation attacks into account (see also Section 6,
first para of p. 9).
FYI - Weierstrass curves and twisted Edwards curves have roughly the
same "point doubling" cost, while the "point addition" costs are not
that far off (in so-called mixed Jacobian coordinates, the ratio is
~1.25) -- all in terms of finite field multiplications and finite
field squarings (and counting naively). Since "point doubling"
generally happens more frequently than "point addition", the overall
cost differential is somewhere in the interval [1.00 - 1.25]. While
the prime number shape may affect modular reduction cost and tilt the
overall cost somewhat, I do not know of any public info on how
real-world implementations really compare.
If you have any suggestion on how to do a fair computational cost
comparison, please let me know. (Right now, I do not know how to do
so, without only providing the naive finite field comparison above --
which could be misleading for real-world implementations, esp. with
constrained devices without trusted hardware.)
<<RS
--Mohit
On 4/19/19 5:50 PM, Rene Struik wrote:
Dear colleagues:
I slightly updated the draft. Main changes: (technical) I added COSE
parm requests (Section8.4-8.6); (editorial) some tiny word-smything
and addition of two more references.
Of course, more references are possible, but - apart from that - I
think the document is technically ready.
FYI - Stanislav Smyshlyaev and Vasily Nikolaev did kindly review the
previous version of this draft and verified all numbers, formulas,
etc. Their main editorial comment was that the document could use
more references. {I will see whether I can find more references, or
perhaps I should see if I can post a full technical paper on all
kinds of curve formulas,, tricks, etc. This will take some time,
though. This should not stop proceeding with this, imho.}
Best regards, Rene
-------- Forwarded Message --------
Subject: [Lwip] I-D Action:
draft-ietf-lwig-curve-representations-04.txt
Date: Fri, 19 Apr 2019 07:33:44 -0700
From: [email protected]
Reply-To: [email protected]
To: [email protected]
CC: [email protected]
A New Internet-Draft is available from the on-line Internet-Drafts
directories.
This draft is a work item of the Light-Weight Implementation
Guidance WG of the IETF.
Title : Alternative Elliptic Curve Representations
Author : Rene Struik
Filename : draft-ietf-lwig-curve-representations-04.txt
Pages : 61
Date : 2019-04-19
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.
The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/
There are also htmlized versions available at:
https://tools.ietf.org/html/draft-ietf-lwig-curve-representations-04
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-04
A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-ietf-lwig-curve-representations-04
Please note that it may take a couple of minutes from the time of
submission
until the htmlized version and diff are available at tools.ietf.org.
Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/
_______________________________________________
Lwip mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/lwip
_______________________________________________
Lwip mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/lwip
--
email:[email protected] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
--
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
