6
$\begingroup$

I am looking for a fast way to find the modular multiplicate inverse of an integer $a$ in mod $p$. I am mainly interested in $p=115792089210356248762697446949407573530086143415290314195533631308867097853951$, which is the prime used for the finite field over which the elliptic curve P-256 is defined by the NIST (https://www.nsa.gov/ia/_files/nist-routines.pdf).

Take for example $a=23212057121572626849771762094316348576132063248523924165380765792316089469237$. What is the fastest way to calculate $a^{-1}$ mod $p$? I am currently using the extended Euclidean algorithm, but it is quite slow. I need the speed, since it's an operation that I will need to use a lot for encryption.

A file of 1664 bytes for example, requires about 20000 uses of the extended Euclidean, which takes about 10 seconds on my computer, which is quite long to encrypt 1664 bytes.

The algorithm I'm using is the following (taken from "Guide to Elliptic Curve Cryptography":

$\endgroup$
5
  • 1
    $\begingroup$ I don't know about relative speed, but finding the value of $a^{p-2}\pmod p$ provides this information. "Modular exponentiation" is the term for this approach. $\endgroup$
    – abiessu
    Commented Jan 3, 2015 at 23:51
  • 3
    $\begingroup$ @abiessu Calculating $a^{p-2}$ is slower than the extended Euclidean algorithm, since $p$ is so large. $\endgroup$
    – Dasherman
    Commented Jan 4, 2015 at 0:05
  • 4
    $\begingroup$ The extended Euclidean algorithm should be blindingly fast (try Wolfram Alpha for example). Perhaps your implementation is faulty? $\endgroup$
    – Greg Martin
    Commented Jan 4, 2015 at 0:37
  • $\begingroup$ I am quite certain that my implementation works, since I copied it pretty much straight from a book on elliptic curve cryptography ("Guide to Elliptic Curve Cryptography") $\endgroup$
    – Dasherman
    Commented Jan 4, 2015 at 0:40
  • $\begingroup$ I'm guessing you know you can keep remainders less than p/2 ? $\endgroup$
    – user645636
    Commented Feb 26, 2019 at 19:31

1 Answer 1

Reset to default
5
$\begingroup$

After typing the answer, I see that the question is five years old...

Euclidean division is usually fast enough for applications in cryptography. It is at most a $\log$ factor slower than multiplication, and there is probably no better way of calculating modular inverse.

However, if you do want to save the $\log$ factor, then in your specific case I would suggest using an "inversion-free" version of your algorithm.

The method is simply to express all points on your elliptic curve in projective coordinates. This is equivalent to keeping a "common denominator" of all the numbers.

This way, you don't have to calculate the inverse in every step of elliptic curve arithmetic, but only have to do it once at the very end, when you want to translate it back to affine coordinates.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .