0
$\begingroup$

There is an elliptic curve with parameters:

a = 0xb3b04200486514cb8fdcf3037397558a8717c85acf19bac71ce72698a23f635
b = 0x12f55f6e7419e26d728c429a2b206a2645a7a56a31dbd5bfb66864425c8a2320

Also the prime number is:

q = 0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c297

How can I solve the equation 65537 * P = H and obtain the value of P?

P and H are points and H equals to (72782057986002698850567456295979356220866771008308693184283729159903205979695, 7766776325114464021923523189912759786515131109431296018171065280757067869793).

Note that in the equation we have https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

$\endgroup$
1
  • $\begingroup$ Is the $q$ you gave the order of the curve or the prime defining the underlying field? $\endgroup$
    – SEJPM
    Commented Oct 2, 2016 at 13:37

2 Answers 2

2
$\begingroup$

Find an integer $k$ such that $65537k \equiv 1 \pmod q$; such a $k$ exists because $q$ is prime.

If $65537\cdot P = H$, then clearly $P = k\cdot H$ (keeping in mind that $q\cdot P = \mathcal{O}$ for all points $P$), and conversely $(k\cdot H)\cdot 65537 = H$.

$\endgroup$
4
  • $\begingroup$ For the interested reader: If you have looked for an excuse to get into SAGE, here it is, as elliptic curves are fully supported :) $\endgroup$
    – SEJPM
    Commented Oct 2, 2016 at 13:38
  • $\begingroup$ Dear @fkraiem, based on your answer, $k$ must be equal to $2544954363427735394864394040193014025260293190481810685052829923353728826615$. Now, let $P=k*H$. Using simple computation it is easy to see that $65537*P \ne H$. $\endgroup$ Commented Oct 3, 2016 at 10:24
  • $\begingroup$ @MeysamGhahramani Is $q$ not the order of the group we are operating in, as is usual? I am too old to do the actual computations. :D $\endgroup$
    – fkraiem
    Commented Oct 3, 2016 at 11:25
  • $\begingroup$ @fkraiem, Yes, $q$ is the order of group $Z_q$. But in this problem we have two groups. First group is $Z_q$ and second is elliptic curve defined over $Z_q$ with order $\#E$. $\endgroup$ Commented Oct 3, 2016 at 12:55
1
$\begingroup$

The order of your elliptic curve is:

$$\#E=16503925798136106726026894143294039201930\\439456987742756395524593191976084900.$$

$65537\cdot P=H$ so $P=(65537^{-1} \quad mod \#E)\cdot H$. Therefore $P$ is:

$$(93813596734667685691144143661248488893272149637339517155513405730225\\00973149,126326936796887255657293386261991198154426075402912518061871706759386\\37384365)$$

Note that $q\cdot P=\mathcal{O}$ is not true for all points $P$.

Example: $q=17$, $a=1$, $b=4$ and $P=(0,2)$ then $17\cdot P=(14,5)\ne \mathcal{O}$.

$\endgroup$

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.