For example, let's use secp256k1, the curve used by bitcoin, y^2 = x^3 + 7, and x=12. Over the real numbers, that calculation is trivial - I can simply use a calculator. But in a finite field, how does it work? If I say "X is 12", how do I calculate Y? The equation (when using real numbers) almost always results in fractions. And modulo P only works with integers.
6
-
1$\begingroup$ This is essentially a duplicate of crypto.stackexchange.com/questions/10024/… Please note that you don't divide but take inverses in the finite field (modulo the prime $p$). $\endgroup$– kodluFeb 12, 2020 at 6:16
-
4$\begingroup$ Does this answer your question? Finite fields and ECC $\endgroup$– kodluFeb 12, 2020 at 6:17
-
1$\begingroup$ I don't think the linked duplicate answers the question which seems fundamentally on how to find square roots over finite fields. $\endgroup$– SEJPMFeb 12, 2020 at 8:47
-
1$\begingroup$ This one is probably closer to what're your looking for though it only covers the case of the field prime $p$ being $p\equiv 3\pmod 4$ $\endgroup$– SEJPMFeb 12, 2020 at 8:57
-
1$\begingroup$ Alternatively the Handbook of Applied Crypto has the algorithm as Algorithm 3.34 (Chapter PDF) $\endgroup$– SEJPMFeb 12, 2020 at 9:01
|
Show 1 more comment