The better algorithm for Modular Exponentiation on secp256k1/r1

Question

I know Modular Exponentiation ($r = b^e \bmod m$) is important for RSA, and I can find some algorithm that if e is expressed in binary form (for exp: )--in such way for a n-bit long e, one can expect ~1.5n rounds multiply modular operation.

I am working on making a public key recovery methodology for ECC like secp256k1/r1. There is a very efficient implementation in the secp256k1 lib, but that was coded in ASM code--hard to understand. But at least I know the 1st step--you need to recover the $ry$ from the $rx$ (i.e. r of the signature). It is very easy to get $ry^2$ from $rx$, but the next I will need to do square root modular--which can be converted to the exponentiation modular on the field, that is $e= (p+1)/4.$

OK, so now questions are:

1. Is there a better algorithm other than the usual Modular Exponentiation to calculate the ($r = b^e \bmod m$)?
2. Or alternatively, is there any short-cut algorithm specifically for secp256k1 that I don’t need run Modular Exponentiation at all and still be able to recover the $ry$ from $rx$?

Answer 1

There is no substitute for modular multiplication in the question's cryptosystems. Some languages like Python make that easy for educational purposes, only.

In RSA and DSA, and to a lesser degree ECC crypto on secp256k1 or secp256r1, one needs to compute $b^e\bmod m$ for large $e$. The fastest algorithms (e.g. sliding window exponentiation) perform about $\log_2 e$ modular squaring and like $\approx0.2\,\log_2 e$ modular multiplications. However there are other algorithms only marginally more costly (e.g. Montgomery's ladder) that may be better from the standpoint of security against side channels.

Each modular multiplication or squaring modulo $m$, for the above or (in ECC) point addition or multiplication by a scalar, has computational cost growing at most like $(\log m)^2$ when using the algorithms learned in primary school adapted to computer words instead of digits. That can be lowered to $(\log m)^{\approx1.6}$ with Karatsuba or $(\log m)^{\approx1.5}$ with Toom-3, but in ECC the modulus $m$ is not large enough that it pays much ($m$ is a 'only' some hundreds bit in ECC, rather than some thousands in RSA/DSA).

When developing signature or encryption using secp256k1 or secp256r1 from scratch for educational purposes, there typically are phases:

• Getting something that works, by building point addition and doubling in Cartesian coordinates on top of modular multiplication, then point multiplication, then signature or/and encryption.
• Getting it to work much faster by using a better representation of point, e.g. projective coordinates (which allows to deffer the costly modular inversion until the end of point multiplication)
• Getting it to work securely, which is very hard and typically requires rewriting a lot of things from the grounds up.
• Performance optimizations. These can be attempted at any stage, but ponder the saying "premature optimization is the root of all evil".

---

Some online references on modular multiplication and exponentiation (not ECC):

• Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography (CRC press, 1996), especially sections 14.3 and 14.6.
• Richard Brent and Paul Zimmermann's Modern Computer Arithmetic (Cambridge University press, 2010), especially sections 2.4 and 2.6.