5
$\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$
4
  • 1
    $\begingroup$ sorry for inadvertently removing 70 in my edit. thanks @MORNING_WOOD for fixing it. $\endgroup$
    – kodlu
    Commented Apr 13, 2017 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
    Commented Apr 13, 2017 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$ Commented Apr 13, 2017 at 9:59
  • $\begingroup$ The order of P is 93556643250795678718734474880013829509196181230338248789325711173791286325820 and the ratio of orders from P to nP is 1:60. $\endgroup$ Commented Apr 13, 2017 at 17:54

2 Answers 2

6
$\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$
10
  • $\begingroup$ Could I reduce the computation by knowing t < 400000000000000000000000000000? $\endgroup$ Commented Apr 13, 2017 at 20:50
  • $\begingroup$ Yes, then you immediately get $t$, by the above. $\endgroup$ Commented Apr 13, 2017 at 20:56
  • $\begingroup$ Would I simply compute up to mod 3637793? $\endgroup$ Commented Apr 13, 2017 at 21:06
  • $\begingroup$ Well 5733569 is also doable. But you'll want to apply the Pohlig-Hellman algorithm. $\endgroup$ Commented Apr 13, 2017 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$ Commented Apr 14, 2017 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$
5
  • $\begingroup$ If the ratio of orders is 1:60 that would mean 60 is a factor of t, correct? $\endgroup$ Commented Apr 13, 2017 at 17:54
  • $\begingroup$ Maybe; try to prove it and you will see. :) $\endgroup$
    – fkraiem
    Commented Apr 13, 2017 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$ Commented Apr 13, 2017 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
    Commented Apr 13, 2017 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$ Commented Apr 13, 2017 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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