Re: could it be a trapdoor



laicko <yichun.zhang@xxxxxxxxx> wrote:
if E(K) is a elliptic curve over a finite field K, then we could
construct a subgroup with order N.
Let N=p*q, p and q are both big prime.

Then here comes my question:
if we make N in public , let p and q in secret,
let the points in this subgroup is the plaintext space,

then could we can conclude that: if we let e<N, then to compute eM from
M is easy and compute M from eM is hard?

As Tom said, you only need 1/e mod N, not mod phi(N). It does not
matter if you publish N, point counting is easy in this context.

Second: I believe it is possible to extract e'th roots on an elliptic
curve even if you do not know N, at least if e is small. Simply
compute symbolic equations for multiplication by e, then solve them.
You can try yourself with e=2 and e=3.

--
Kristian Gjøsteen
.



Relevant Pages

  • Re: could it be a trapdoor
    ... laicko wrote: ... construct a subgroup with order N. ... because counting the order of a composite order curve is no harder ... find it themselves they can find 1/e and decrypt. ...
    (sci.crypt)
  • Re: computing k-th roots mod q for a prime q such that GCD(k, q-1) > 1
    ... iteratively over each prime power factor of k. ... for k^n-th roots are no harder than k-th roots. ... this algorithm is nice and I had not noticed it. ... subgroup generated by x and thus cannot be a k-th root of x. ...
    (sci.crypt)
  • Re: subgroup of unit group
    ... evey finite subgroup of the multiplicative group ... Let G be a finite subgroup of the multiplicative group of a field. ... Suppose the exponent of G is p^r. ... of p^r-th roots of 1. ...
    (sci.math)