3
$\begingroup$

If you knew the entire equation of an elliptic curve $$y^2 = x^3 + ax + b~( mod ~~m)$$ given $a, b$ and $m$ which are all more than 70 digits in length, as well as a point $P$ and the point $t P$, with different orders, would it be possible to calculate $t$? What would be the fastest way to do this?

(I'm aware that $tP$ and $P$ not sharing the same order makes this less secure but I'm wondering how exactly to exploit it).

$\endgroup$
  • 1
    $\begingroup$ sorry for inadvertently removing 70 in my edit. thanks @MORNING_WOOD for fixing it. $\endgroup$ – kodlu Apr 13 '17 at 8:39
  • $\begingroup$ Do you know the two orders ? A general solution doesn't seem to apply, so maybe looking at the numbers.. $\endgroup$ – Ruggero Apr 13 '17 at 9:21
  • 3
    $\begingroup$ It depends on many things.. If P has order 2 and $t=2$ then it is trivial. If $P$ has order $2p$ for a large prime $p$, and $t=2n$ for some random $1\leq n\leq p-1$, then it will be hard. You'll have to give some more information. $\endgroup$ – CurveEnthusiast Apr 13 '17 at 9:59
  • $\begingroup$ The order of P is 93556643250795678718734474880013829509196181230338248789325711173791286325820 and the ratio of orders from P to nP is 1:60. $\endgroup$ – LieutenantCurly Apr 13 '17 at 17:54
5
$\begingroup$

You mention your point has order $$93556643250795678718734474880013829509\\196181230338248789325711173791286325820$$ which factorizes as

$$2^2\cdot 3\cdot 5\cdot 7\cdot137\cdot593\cdot 24337\cdot 25589\cdot3637793\cdot5733569\cdot106831998530025000830453\cdot1975901744727669147699767.$$

Without much computing power, we can apply the Pohlig-Hellman algorithm to obtain $$t\bmod4, t\bmod3,t\bmod5,\ldots,t\bmod5733569.$$

Using the Chinese Remainder Theorem, we can combine all these results to get

$$t\bmod\left(4\cdot3\cdot5\cdots5733569\right),$$ i.e. $$t\bmod443208349730265573969192476820.$$

As @Ruggero remarks, the other primes are only about 80 bits. So with $\approx 40$ bits of computing power we could also break that discrete logarithm. It takes a little more effort than the others though, so if $t < 400\cdots 0$, then you may as well only do the easy ones.

$\endgroup$
  • $\begingroup$ Could I reduce the computation by knowing t < 400000000000000000000000000000? $\endgroup$ – LieutenantCurly Apr 13 '17 at 20:50
  • $\begingroup$ Yes, then you immediately get $t$, by the above. $\endgroup$ – CurveEnthusiast Apr 13 '17 at 20:56
  • $\begingroup$ Would I simply compute up to mod 3637793? $\endgroup$ – LieutenantCurly Apr 13 '17 at 21:06
  • $\begingroup$ Well 5733569 is also doable. But you'll want to apply the Pohlig-Hellman algorithm. $\endgroup$ – CurveEnthusiast Apr 13 '17 at 21:09
  • 1
    $\begingroup$ Perhaps, but there could be a bug anywhere. Why dont you add all parameters to your question, so we can have a go? $\endgroup$ – CurveEnthusiast Apr 14 '17 at 6:32
2
$\begingroup$

Hint: this allows one to find a factor of $t$; find out how.

As an example, consider the multiplicative group modulo a prime, with a generator $g$. If $g^t$ is a quadratic residue, what does that say about $t$?

$\endgroup$
  • $\begingroup$ If the ratio of orders is 1:60 that would mean 60 is a factor of t, correct? $\endgroup$ – LieutenantCurly Apr 13 '17 at 17:54
  • $\begingroup$ Maybe; try to prove it and you will see. :) $\endgroup$ – fkraiem Apr 13 '17 at 18:03
  • $\begingroup$ I think it stands but even knowing it is a multiple of 60, finding n this way would still take too long, no? $\endgroup$ – LieutenantCurly Apr 13 '17 at 18:26
  • $\begingroup$ Nobody said you can completely find $t$. ;) (You can't, or at least not just from the order of $g^t$, since different values of $t$ may yield the same order.) $\endgroup$ – fkraiem Apr 13 '17 at 18:54
  • $\begingroup$ I was able to discover that, factoring and finding the cofactor for the prime divisor 7, and multiplying that cofactor h by P and tP produces the same point hP. Applying multiplicative properties, would I be correct in assuming that, given the cofactor h composed of factors {a,b,c..}, some combination of abc*... will yield t? $\endgroup$ – LieutenantCurly Apr 13 '17 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.