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$
  • $\begingroup$ Is the $q$ you gave the order of the curve or the prime defining the underlying field? $\endgroup$ – SEJPM Oct 2 '16 at 13:37
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$.

| improve this answer | |
$\endgroup$
  • $\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 Oct 2 '16 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$ – Meysam Ghahramani Oct 3 '16 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 Oct 3 '16 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$ – Meysam Ghahramani Oct 3 '16 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}$.

| improve this answer | |
$\endgroup$

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.