Subject: [Cfrg] Question about A=6 Montgomery over 2^89-1

From: Dan Brown <[email-masked]>
Date: Thu, 10 Dec 2015 21:22:16 +0000

Hi,

I stumbled upon something surprising (to me), using Sage (while searching
for something else).

The Montgomery curve y^2 = x^3 + 6x^2 + x over the field of size 2^89-1, has
order 2^89, so it is maximally vulnerable to Pohlig-Hellman.  (Other
details: it has order p+1, so is also vulnerable to MOV.  I haven't checked
yet, but I'd _bet_ it's supersingular.  It has j-invariant 66^3.)  

As is well-known, the supersingular curve y^2 = x^3 + x also has order 2^89
(it has j-invariant 1728=12^3).  But I recall a result of Koblitz saying
that curves over F_p with order p+1 are very rare (among isomorphism
classes).  Naively, I would think that finding two such curves so close
together (A=0 and A= 6) has negligible chance, unless these weak curves are
distributed towards small |A|.

Nonetheless, I still hope that this does _not_ indicate some general _weak_
correlation between Montgomery curves with a small coefficient and known
attacks.

To that end, I'd be curious if somebody here could explain the theory behind
this example curve.  For example, it would be re-assuring to explain this as
a mere one-time coincidence, rather than a higher chance of a known attack
(e.g. MOV or PH) on smaller-coefficient curves.  (Purely speculating: maybe
there's a good theory of supersingular j-invariants for each prime p, then a
way to deduce A from j, such that p=2^89-1 and j=66^3 formed a superstorm to
arrive at a small A=6.)

Absent such an explanation, the worry is that if known attacks more
generally exhibit this kind of correlation with coefficient size, then how
wise is it to suggest small-coefficient curve as a remedy against secret
attacks?  

I am aware that there are other worries of a different nature
("manipulation") involved with methods that generate larger coefficients,
but maybe there's a good way to balance both concerns.

Best regards,

Daniel Brown

---

From: "Grigory Marshalko" <[email-masked]>
Date: Fri, 11 Dec 2015 20:20:01 +0000

Hi,

May be this is the case:
from wiki:
If an elliptic curve over the rationals has complex multiplication then the set of primes for which
it is supersingular has density 1/2. If it does not have complex multiplication then Serre showed
that the set of primes for which it is supersingular has density zero. Elkies (1987) showed that
any elliptic curve defined over the rationals is supersingular for an infinite number of primes.

and this is also may be useful http://pages.cs.wisc.edu/~cdx/ComplexMult.pdf

Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (ТC 26)
www.tc26.ru
11 декабря 2015 г., 00:22, "Dan Brown" <[email-masked]> написал:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Grigory Marshalko" <[email-masked]>
Date: Fri, 11 Dec 2015 21:09:36 +0000

This seems to be a better answer

http://alexricemath.com/wp-content/uploads/2013/07/EC2.pdf

Regards,
Grigory Marshalko,
expert,

---

From: Dan Brown <[email-masked]>
Date: Sat, 12 Dec 2015 15:23:25 +0000

So 66^3 is one of the few (13???) integral j-invariants with CM over the rationals (the Baker-Stark-Heegner theorem?). And yes Elkies shows that half the primes will give a supersingular. I'll look at how j=66^3 corresponds to A=6 in 2016, and eventually try to sort out whether there's much to say about small |A|.

  Original Message
From: Grigory Marshalko
Sent: Friday, December 11, 2015 4:09 PM
To: Dan Brown; [email-masked]
Subject: Re: [MASSMAIL][Cfrg] Question about A=6 Montgomery over 2^89-1

Regards,
Grigory Marshalko,
expert,

---

From: "Grigory Marshalko" <[email-masked]>
Date: Sat, 12 Dec 2015 18:21:22 +0000

Yes, exactly 13, see for example http://www2.warwick.ac.uk/fac/cross_fac/complexity/people/students/dtc/students2013/klaise/janis_klaise_ug_report.pdf

Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (ТC 26)
www.tc26.ru
12 декабря 2015 г., 18:23, "Dan Brown" <[email-masked]> написал:
> So 66^3 is one of the few (13???) integral j-invariants with CM over the rationals (the
> Baker-Stark-Heegner theorem?). And yes Elkies shows that half the primes will give a supersingular.
> I'll look at how j=66^3 corresponds to A=6 in 2016, and eventually try to sort out whether there's
> much to say about small |A|.
> 
> Original Message
> From: Grigory Marshalko

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sat, 12 Dec 2015 18:29:04 +0000

Hi Dan,

I asked Steven Galbraith about this. Here's what he said:

"Some thoughts on the elliptic curve:  E : y^2 = x^3 + 6x^2 + x
It is a global CM curve with j(E) = 66^3, so it has complex
multiplication of discriminant -16.
Due to congruence conditions it is therefore supersingular.
To flip the question around:  For a given prime p, there is usually a CM
elliptic curve over Q which is supersingular modulo p.  And since that
curve is from a finite list it usually has small coefficients. So it is
not at all surprising that one can find a curve with small coefficients
that is supersingular. And if the prime p is such that p+1 is smooth
then this is weak for Pohlig-Hellman.
There is no reason to think there would be another other such example,
so I guess there is nothing to worry about."

Steven no longer subscribes to this list, so include him in cc if you want
him to see any responses.

Cheers

Kenny

On 12/12/2015 15:23, "Cfrg on behalf of Dan Brown" <[email-masked]
on behalf of [email-masked]> wrote:

>So 66^3 is one of the few (13???) integral j-invariants with CM over the
>rationals (the Baker-Stark-Heegner theorem?). And yes Elkies shows that
>half the primes will give a supersingular. I'll look at how j=66^3
>corresponds to A=6 in 2016, and eventually try to sort out whether
>there's much to say about small |A|.
>
>  Original Message
>From: Grigory Marshalko
>> and this is also may be useful
>>http://pages.cs.wisc.edu/~cdx/ComplexMult.pdf
>>
>> Regards,
>> Grigory Marshalko,
>> expert,

---

From: Ben Laurie <[email-masked]>
Date: Sun, 13 Dec 2015 22:13:13 +0000

OK, now I want the shortest possible reading course that lets me figure out
what you just said.

Actually a serious request.

---

From: Dan Brown <[email-masked]>
Date: Mon, 14 Dec 2015 03:34:20 +0000

there's already been some answers on the list, but they haven’t resolved the issue fully to me, so I worked out that j = 256(a^2-3)^3/(a^2-4). For both j and a to be a (rational) integer, we must have a-2 and a+2 divide powers of two, which means a is 0,2,-2,6,-6.  I expect this is all worked out in some old publication.

so, for other j‎, I'd expect a mod p not too small. Not sure what happens for irrational j with CM over the rationals.

hence, so far, I only expect this one small a example‎. not yet sure how to infer something from this about unpublished weaknesses in ECDLP (assuming they exist, which is unlikely)

  Original Message
From: Steven Galbraith
Sent: Sunday, December 13, 2015 6:26 PM
To: Ben Laurie; Paterson, Kenny; Dan Brown; Grigory Marshalko; [email-masked]
Subject: Re: [Cfrg] Question about A=6 Montgomery over 2^89-1

Read Chapters 2 and 4 of Washington's book on Elliptic Curves. Section
4.6 comes close to discussing this sort of thing.

For a deeper knowledge you can look at Washington's chapter on Complex
Multiplication, or the book by Cox "Primes of the form x^2 + n*y^2", or
this great course by Drew Sutherland:
   http://math.mit.edu/classes/18.783/lectures.html

Steven

On 14/12/15 11:13, Ben Laurie wrote:
> OK, now I want the shortest possible reading course that lets me figure
> out what you just said.
>
> On Sat, 12 Dec 2015 at 18:29 Paterson, Kenny <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>     Hi Dan,
>
>     On 12/12/2015 15:23, "Cfrg on behalf of Dan Brown"
>     <[email-masked] <mailto:[email-masked]>
>     on behalf of [email-masked] <mailto:[email-masked]>> wrote:
>
>     >To: Dan Brown; [email-masked] <mailto:[email-masked]>
>     >www.tc26.ru <http://www.tc26.ru>
>     >11 декабря 2015 г., 23:20, "Grigory Marshalko"
>     <[email-masked] <mailto:[email-masked]>>
>     >написал:
>     >
>     >> Hi,
>     >>
>     >> May be this is the case:
>     >> from wiki:
>     >> If an elliptic curve over the rationals has complex
>     multiplication then
>     >>the set of primes for which
>     >> that the set of primes for which it is supersingular has density
>     zero.
>     >>Elkies (1987) showed that
>     >> www.tc26.ru <http://www.tc26.ru>
>     >> 11 декабря 2015 г., 00:22, "Dan Brown" <[email-masked]
>     <mailto:[email-masked]>> написал:
>     >>
>     >>> Hi,
>     >>>
>     >>> As is well-known, the supersingular curve y^2 = x^3 + x also has
>     order
>     >>>2^89
>     >>> To that end, I'd be curious if somebody here could explain the
>     theory
>     >>>behind
>     >>> there's a good theory of supersingular j-invariants for each
>     prime p,
>     >>>then a
>     >>> generally exhibit this kind of correlation with coefficient
>     size, then
>     >>>how
>     >>> [email-masked] <mailto:[email-masked]>
>     >[email-masked] <mailto:[email-masked]>
>     [email-masked] <mailto:[email-masked]>