Anomalous elliptic curves over finite rings

Question

I was wondering if it is possible to solve the discrete logarithm on an Elliptic Curve E(Z/nZ) (defined over the ring of integers modulo a composite n) with #E(Z/nZ)=n by applying a method analogous to the Semaev, Satoh-Araki, and Smart attack for anomalous elliptic curves over prime fields.

Answer 1

The condition $\#E(\mathbb{Z}/n\mathbb{Z}) = n$ is not enough, I believe. You would need that $E(\mathbb{Z}/p\mathbb{Z})$ is cyclic of order $p$ for all prime divisors $p$ of $n$.

By the Chinese Remainder Theorem, we have $E(\mathbb{Z}/n\mathbb{Z}) = \prod_{p\mid n} E(\mathbb{Z}/p^{k_p}\mathbb{Z})$ where $k_p=\operatorname{ord}_p(n)$. That reduces the problem to prime powers. If $E(\mathbb{Z}/p\mathbb{Z})$ is cyclic of order $p$, then you can use the $p$-adic logarithm to solve $E(\mathbb{Z}/p^{k_p}\mathbb{Z})$, too.

Now if $n=pq$ for two distinct primes and $E(\mathbb{Z}/p\mathbb{Z})$ has $q$ elements then the $p$-adic logarithm won't help to solve the discrete logarithm there.

This means that the naivest version of using the same idea only works in special cases. But maybe I am missing something.

Answer 2

I believe you can factor $n$ if you know such curve.

Assume $n$ is odd. Reason mod $p$. since $n=pq$, you know a multiple of the order (no matter if the order is $p$ or $q$).

Compute the division polynomial $\psi_n(u) \pmod n$ for random $u$.

$\psi_n(u) \equiv 0 \pmod{p}$ iff $u$ is $x$ coordinate in $\mathbb{F_p}$ which happens half the time.

If $u$ is $x$ coordinate mod $p$ but not mod $q$ you find $p$ by computing $\gcd(\psi_n(u) \mod n,n)$.

Here is sage code:

def molog():
    p=113
    q=131
    K=GF(p)
    Kq=GF(q)
    E=EllipticCurve(K,[40,54])
    Eq=EllipticCurve(Kq,[7,62])
    print 'order=',E.order(),Eq.order()
    n=p*q
    for u in [ 1 .. 20]:
            dp=E.division_polynomial(n,u)
            dq=Eq.division_polynomial(n,u)
            print u,'mod p',dp,'mod q',dq

pari/gp example:

? p=113;q=19;a=chinese(Mod(40,p),Mod(16,q));b=chinese(Mod(54,p),Mod(12,q));n=p*q;E=ellinit([0,0,0,a,b]);N=p*q;u=1;dp=SLPDivisionPolynomial(a,b,u,N);g=gcd(lift(dp),N);g
%62 = 113