I found myself having to write cryptography code on C++ and I needed to invert a key. Well, libsecp256k1 does not support that natively, so I was forced to find a different way. In the process, I have tried and successfully implemented two different methods you can use to invert your private keys and perform division on them if necessary.
Definition of mod-inverseModular Multiplicative Inverse in cryptography is when you find a number inside a group of numbers, that multiplies with another number to give 1. Then those two numbers are modular inverses of each other.
I will give you an example with small numbers. Lets suppose that our number line only supports:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10
(edit: The first number was supposed to be zero not nine).
And then we "bend" the line into a circle, that is, if you add 10+1 you you would go back to 0, and vice versa for 0 - 1.
Now suppose we want to multiply 5*9. What would that give us in this group? Well normally, we would get 45, but that number is not defined here. So what can we do?
Well, let's see what happens if we subtract "1" to it. Then we will have 44, which happens to be evenly divisible by 11 (representing the total number of elements in the group), and 44 mod 11 is zero - you can open any calculator to verify this.
So we have just proven that 5 and 9 are multiplicative inverses (modulo 11 elements). We have found a very powerful way of finding mod-inverses by expressing them as:
a*x + m*y = gcd(a, m) = 1
Where we are trying to find the inverse of a mod m, and x and y are unknown - in an elliptic curve, A and M are not supposed to have any common factors, hence why it's 1.
Y is not very important here - it just tells us how many times you need to add or subtract m from a*x to get 1. It is X we are really interested in, for this is the modular inverse of A.
Hence it gives rise to the first solution to find modular inverse:
1. Using EGCDEGCD stands for "extended greatest common divisor" but most people just call it the "extended Euclidean algorithm" because it is just an extension of Euler's ancient "sieves" algorithm for finding greatest common factors of two numbers. As I have just demonstrated above, EGCD also finds the multiplicative inverse of the number and also the "shift" that needs to be applied to the group size number to get the GCD, which, in crypto's case, is just 1.
Below I provide an EGCD algorithm you can use with any integral type with high enough resolution (here I use my own fixed-point library available on github at:
https://github.com/ZenulAbidin/xFD). This code is BSD 3-clause licensed and is easily modified to support generalized EGCD by returning all the variables in an array or as reference parameters.
// Returns x such that xa + by = gcd(a, b) (= 1 for prime b)
Decimal MMI(const Decimal& a, const Decimal& b) {
auto old_r = a, r = b;
auto old_s = 1_D, s = 0_D;
auto old_t = 0_D, t = 1_D;
Decimal tmp;
while (r != 0_D) {
auto quotient = xFD::Floor(old_r / r);
tmp = r;
r = old_r - quotient * r;
old_r = tmp;
tmp = s;
s = old_s - quotient * s;
old_s = tmp;
tmp = t;
t = old_t - quotient * t;
old_t = tmp;
}
// s, t = a/gcd(a,b) and b/gcd(a,b) respectively
// old_r is gcd
// r is zero obviously
// old_s, old_t are the Bézout coefficients x and y for a and b respectively.
// The multiplicative inverse should not be negative.
return (old_s < 0_D) ? old_s + b : old_s;
}
(here, m is just swapped for a different name "b").
2. Using Fermat's little theoremThis was described to me by a fellow Bitcoiner on this forum, and arises from the fact that at the curve order P:
a^P === a(^1)
This identity does not look very interesting by itself, until you see what happens when we take some arithmetic on both sides:
a^(P-1) ===a^(1-1) === a^0 === 1
This is called Euler's theorem (and it only works when a and m have a GCD of 1). It's not very useful for us either, but if we apply this again:
a^(P-2) ===a^(1-2) === a^-1
Then we get the multiplicative inverse of a without EGCD.
Now naturally, this only works if you already have an elliptic curve library with support for exponentiation, which is really just repeated self-multiplication. It is also slower than the first method, but one big advantage of this algo is that there are no branches with different timings, making this algo
very secure against side-channel attacks.
So pick your poison. Writing a wallet? Use exponentiation. EGCD is much faster, but is unsuitable for use in wallets.
Additional reading:
https://en.wikipedia.org/wiki/Modular_multiplicative_inversehttps://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
