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

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" <dbrown@certicom.com> написал:
> 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
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg