It was the Bitcointalk forum that inspired us to create Bitcointalksearch.org - Bitcointalk is an excellent site that should be the default page for anybody dealing in cryptocurrency,
since it is a virtual gold-mine of data. However, our experience and user feedback led us create our site;
Bitcointalk's search is slow, and difficult to get the results you need, because you need to log in first to find anything useful - furthermore, there are rate limiters for their search functionality.
The aim of our project is to create a faster website that yields more results and faster without having to create an account and eliminate the need to log in -
your personal data, therefore, will never be in jeopardy since we are not asking for any of your data and you don't need to provide them to use our site with all of its capabilities.
We created this website with the sole purpose of users being able to search quickly and efficiently in the field of cryptocurrency
so they will have access to the latest and most accurate information and thereby assisting the crypto-community at large.
FYI: https://gcd.cr.yp.to/papers.html The fastest modular inversion with constant time that I know. About 4000 CPU clock cycles per inversion. Also check "software" tab for avx-optimized example sources. It can be optimized further but at the cost of constant time implementation.
That's great, I'll check it out when I get some time.
I tried to implement this fast modular exponentation into C++, but it works only for small numbers. Obviously, it won't work for long numbers, because of overflow problems. This makes a dilemma. How can we even represent these numbers properly in C++?
I was thinking using libsecp256k1 for that kind of thing, but I'm at an utter loss of how to do a modinverse with a byte array as the private key, because that particular function exists but it's not exported.
FYI: https://gcd.cr.yp.to/papers.html The fastest modular inversion with constant time that I know. About 4000 CPU clock cycles per inversion. Also check "software" tab for avx-optimized example sources. It can be optimized further but at the cost of constant time implementation.
no way to use inv for downgrade priv simple mult point to mod inv(a) will give redult point * inv(a) bits !!!!
FYI: https://gcd.cr.yp.to/papers.html The fastest modular inversion with constant time that I know. About 4000 CPU clock cycles per inversion. Also check "software" tab for avx-optimized example sources. It can be optimized further but at the cost of constant time implementation.
then div 99 / 50 result = 50 + 49/50.so fo find 99 need, if dont known divisision (49), so calc from (1/50 to 50/50 ),+ 50 and privkey 99 will bi finded in 49 operations... mach then 99.
With Fermat's little theorem, you have no guarantees about the immunity to side channel attacks, because it all relies on the underlying library's exponentiation function being safe against side channel attacks. Most math libraries are not safe against this.
That is correct.
I am now wondering whether it is possible to eliminate side-channels in EGCD at all, considering that the loop uses expensive division and multiplication ops followed by cheap subtraction ops that could leak some info about keys via power frequency.
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-inverse
Modular 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:
9, 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10
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 EGCD
EGCD 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.
Code:
// 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;
// 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 theorem
This 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.
while i < 2**61: d= (divnum(input,delta)) s = divnum(i,gamma) %N result = divnum(d,s)
if result =0: print("result",hex(result),"i",hex(i),"input",hex(input))
i = i +1
result:
Code:
result 0x0 i 0x0 input 0x5f88 result 0xfec i 0x1 input 0x5f88 result 0x7f6 i 0x2 input 0x5f88 result 0x3fb i 0x4 input 0x5f88 result 0x4 i 0x3fb input 0x5f88 result 0x2 i 0x7f6 input 0x5f88 result 0x1 i 0xfec input 0x5f88
as you see result = 1 geted in 0xfec operation instaed input 0x5f88 operation.
basepoint for bsgs or kangaroo vill = inversion(gamma)
how to use this with pubkeys ? 1 is pubkey from priv 1, this is no problem . a and m is pubkeys too(a is unknown for ex and m i known. x and y are need to find, but they are not unknown....
With Fermat's little theorem, you have no guarantees about the immunity to side channel attacks, because it all relies on the underlying library's exponentiation function being safe against side channel attacks. Most math libraries are not safe against this.
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-inverse
Modular 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 EGCD
EGCD 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.
Code:
// 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;
// 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 theorem
This 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.
?