Subject: Re: [Cfrg] Suggestions for draft-irtf-cfrg-curves-01.txt

From: Evgeny Alekseev <[email-masked]>
Date: Mon, 2 Feb 2015 18:07:27 +0300

Stanislav V. Smyshlyaev wrote:

> Dear colleagues,
>
> We would like you to consider several proposals on the latest variant of
draft (draft-irtf-cfrg-curves-01).
>
> 1)      In our opinion, some important clarifications have to be done
explicitly in the document, though needed references are given.
>  a) In Section 3.3 declare explicitly what "r” denotes.
>  b) In Section 5 mention explicitly Schoof–Elkies–Atkin algorithm as an
algorithm used to calculate number of curve points or even fully cite it
there.
>  c) Add explicit description of algorithms used to examine curve on MOV-,
CM- and twist-security as well as Frobenius trace calculation formula. Add
“perform checks” step in algorithms proposed in sections 5.1 and 5.2.
> 2)      Select and add a higher security curve (512- or 521-bit).
> 3)      Add some explanations on parameter d of the selected 255-bit
curve (the current draft leaves the question whether it is the first d to
be returned by 5.2 algorithm and the reason of choice if it is not).
> 4)      Introduce a rigid base point generation algorithm (either the one
that was proposed in the previous version of the draft or one using
cryptographic hash function). We consider that important to ensure the
generated points > could be safely used in applied protocols like
password-based key establishment protocols (PAKE, EKE, PACE etc.) and RNGs
like Dual EC DRBG.
>
>
> Best regards,
> Stanislav V. Smyshlyaev, Ph.D.,
> Head of Information Security Department,
> CryptoPro LLC

I agree with Stanislav Smyshlyaev’s questions and suggestions about current
draft version. I would like to draw attention to the 3d remark. If the
answer to this question ("... whether it is the first d to be returned by
5.2 algorithm ...") is “no” then it turns out that extra requirements that
are not mentioned in the draft are implicitly applied to the curve. Also it
seems strange that the recommended curve is not the one with the smallest
d, but the isogeny of this curve. Also I would like to add that it would be
convenient if the recommended Edwards curve is included in the document in
the same way as twisted Edwards curve.

Kind regards, Evgeny Alekseev, Doctor of Philosophy,
Moscow State University, Faculty of Computational Mathematics and
Cybernetics

---

From: Watson Ladd <[email-masked]>
Date: Mon, 2 Feb 2015 08:35:21 -0800

On Mon, Feb 2, 2015 at 7:07 AM, Evgeny Alekseev <[email-masked]> wrote:
>> 3)      Add some explanations on parameter d of the selected 255-bit curve
>> (the current draft leaves the question whether it is the first d to be
>> returned by 5.2 algorithm and the reason of choice if it is not).
> seems strange that the recommended curve is not the one with the smallest d,
> but the isogeny of this curve. Also I would like to add that it would be

The recommended curve is y^2=x^3+486662x^2+x. Were we to use an
isomorphic curve, as opposed to a 4-isogenous one, that 486662 would
be replaced by a larger number, and thus slow down implementations
significantly. Note that 486662 is the smallest value of a that
ensures that
y^2=x^3+ax^2+x has order 8*prime, twist order 4*prime, and the usual
CM restrictions. This is the same as 121665 being the smallest d that
ensure that y^2+x^2=1+dx^2y^2 has the same order and CM restrictions.

Sincerely,
Watson Ladd

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Paul Lambert <[email-masked]>
Date: Mon, 2 Feb 2015 12:04:47 -0800

On 2/2/15, 8:35 AM, "Watson Ladd" <[email-masked]> wrote:

>>>  a) In Section 3.3 declare explicitly what "r² denotes.
>>>  b) In Section 5 mention explicitly SchoofElkiesAtkin algorithm as an
>>> ³perform checks² step in algorithms proposed in sections 5.1 and 5.2.
>>>curve
>> I agree with Stanislav Smyshlyaev¹s questions and suggestions about
>>current
>> 5.2 algorithm ...") is ³no² then it turns out that extra requirements
>>that

+1

>ensure that y^2+x^2=1+dx^2y^2 has the same order and CM restrictions.

So Š the designated editing team will process the above answer
and create suitable text for possible inclusion into the
draft specification.  Yes?

Paul

---

From: Evgeny Alekseev <[email-masked]>
Date: Thu, 12 Feb 2015 10:39:24 +0300

>> Q1: Should CFRG recommend a curve at the 192-bit security level?
Possibly

>> Q2: Should CFRG recommend a curve at the 256-bit security level?
Yes

I don't really think that specification of a new 512-bit curve will
take too many time. Method and requirements
can be similar to ones used for 256-bit (maybe cofactors’ pair will be
(16,16) and (16,8) or something like
these). At the same time 521-bit curve seems kind of strange for me
because speed advantage is not too crucial
but implementation of such arithmetic may be much harder on some
architectures – and it can really delay
incorporation of such curves in some hardware solutions.

Kind regards, Evgeny Alekseev, PhD
Moscow State University, Faculty of Computational Mathematics and Cybernetics