# Breaking Insecure Elliptic Curve Cryptography

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).

• sorry for inadvertently removing 70 in my edit. thanks @MORNING_WOOD for fixing it. – kodlu Apr 13 '17 at 8:39
• Do you know the two orders ? A general solution doesn't seem to apply, so maybe looking at the numbers.. – Ruggero Apr 13 '17 at 9:21
• 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. – CurveEnthusiast Apr 13 '17 at 9:59
• The order of P is 93556643250795678718734474880013829509196181230338248789325711173791286325820 and the ratio of orders from P to nP is 1:60. – LieutenantCurly Apr 13 '17 at 17:54

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.

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

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$?

• If the ratio of orders is 1:60 that would mean 60 is a factor of t, correct? – LieutenantCurly Apr 13 '17 at 17:54
• Maybe; try to prove it and you will see. :) – fkraiem Apr 13 '17 at 18:03
• I think it stands but even knowing it is a multiple of 60, finding n this way would still take too long, no? – LieutenantCurly Apr 13 '17 at 18:26
• 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.) – fkraiem Apr 13 '17 at 18:54
• 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? – LieutenantCurly Apr 13 '17 at 19:41