Search content
Sort by
Showing 20 of 26 results by archyone
maybe you should use a library.
For that particular function? For modinv only?
I use this one for modular multiplicative inverse.
Code:
int modInverse(int a, int n)
{
int i = n, v = 0, d = 1;
while (a>0) {
int t = i/a, x = a;
a = i % x;
i = x;
x = d;
d = v - t*x;
v = x;
}
v %= n;
if (v<0) v = (v+n)%n;
return v;
}
{
int i = n, v = 0, d = 1;
while (a>0) {
int t = i/a, x = a;
a = i % x;
i = x;
x = d;
d = v - t*x;
v = x;
}
v %= n;
if (v<0) v = (v+n)%n;
return v;
}
On the other hand you would save your time using a library like Bouncy Castle for all your work on ecc calculation
You can find good source code to learn like Casascius one - https://github.com/casascius/Bitcoin-Address-Utility
What is this program? It generates random addresses at a speed of 240m / s on gtx1066 and checks against the base of addresses, while for bitcrack only 25-30 in the -u -c mode and only with the specified range. I found a video on YouTube and took screenshots, perhaps the seller renamed the original version, which can be downloaded for free.
Video link - https://youtu.be/5ITn7_kGb8c
screen link
https://ibb.co/qpz15HG
https://ibb.co/9wzzVDZ
https://ibb.co/Dpc0HxR
https://ibb.co/YWQcqtM
https://ibb.co/rZ1XPT8
Video link - https://youtu.be/5ITn7_kGb8c
screen link
https://ibb.co/qpz15HG
https://ibb.co/9wzzVDZ
https://ibb.co/Dpc0HxR
https://ibb.co/YWQcqtM
https://ibb.co/rZ1XPT8
Yeah ! faster .. see your screenshot - https://ibb.co/Dpc0HxR - 50% in 1.26609e+32years ^^ good luck
so DON'T BUY IT !! Hi, you can use secrets library.. "pip install secrets"
et voila !
Code:
import secrets
for n in range(100): # replace 100 by your number of time
bits = secrets.randbits(256) # replace 256 by your choosen range (here this is the number of bits)
with open('result.txt', 'a') as file:
file.write("\n" + hex(bits)[2:])
for n in range(100): # replace 100 by your number of time
bits = secrets.randbits(256) # replace 256 by your choosen range (here this is the number of bits)
with open('result.txt', 'a') as file:
file.write("\n" + hex(bits)[2:])
et voila !
HOW
If anybody is interested, I have the complete code in Python3 with several speed optimizations. Do tell!
If anybody is interested, I have the complete code in Python3 with several speed optimizations. Do tell!
I would like to take a quick look at it, I admit, more out of curiosity than anything else. For the moment, apart from reducing the number of possibilities I do not see too much interest, I could be wrong of course.
Re: Half of any bitcoin (crypto) public key - (public key half)
Is there a code or script to do the math?
It's easier than you might think. In fact, you can use any library that allows you to calculate the public key from a private key and replace the parameters:
# Elliptic curve parameters (secp256k1)
P = 2**256 - 2**32 - 977
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337
#N = 57896044618658097711785492504343953926418782139537452191302581570759080747168 --> here to divide by 2 for example
A = 0
B = 7
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240 --> here put the key you want to divide
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424 --> same for y coordinate
G = (Gx, Gy)
Re: Half of any bitcoin (crypto) public key - (public key half)
this topic is already filled with many examples!
i think you should start at the basics and read what Elliptic Curve Cryptography and Modular Arithmetic are before trying to come up with the code that computes half of a public key!
start here: https://en.wikipedia.org/wiki/Modular_arithmetic
then:
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
https://en.wikipedia.org/wiki/Elliptic-curve_cryptography
and finally
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
Thanks for the links, I have a bit of a headache but now I have the basics to understand.
Well, I now know how to divide a point by 2 as in my example (private key 10). On the other hand, I realize after several tests that if the point to be divided corresponds to an odd private key, the result no longer corresponds to what I expected. As long as the private key is divisible by 2, the calculations seem to respect a certain logic but since the division does not give a whole number (without comma), this "rule" is shattered ^^.
Can someone explain to me this part:
3. If d is odd let P = P + Q
4. Double Q: Q = 2 * Q, halve d rounding towards zero: d = floor (d / 2)
I don't quite understand the logic yet.
The floor () method returns the floor of x i.e. the largest integer not greater than x. With bitcoin is this the rule to apply, why not the other way around? (the smallest integer)?
Thanks in advance
Re: Half of any bitcoin (crypto) public key - (public key half)
Multiply by 57896044618658097711785492504343953926418782139537452191302581570759080747169
Let the point you want to multiply is G, and the multiplication constant is c. The result will be P=c*G
One way to do it is:
1. Start with the point at infinity P = (0,0) = 0*G, Q = G = 1*G, d = c
2. if d is zero return P
3. If d is odd let P = P + Q
4. Double Q: Q = 2*Q, halve d rounding towards zero: d = floor(d/2)
5. Go to step 2
I'm sorry but i don't understand, can you give me an example
I do not have the necessary bases in mathematics and you lost me with "constant is c" & d
ideally a small python script would be welcome but I'm certainly asking too much
Signed: the noob ^^
Re: Half of any bitcoin (crypto) public key - (public key half)
In secp256k1 there are two important primes - the prime p which is used for coordinates x and y (2^256 - 2^32 - 977), and the prime n, which is the group order (2^256 - 432420386565659656852420866394968145599).
The group is defined by two operations - addition of two points, and doubling a point.
From this we easily could multiply a point by scalar, this is series of additions and doublings.
Multiplying a point by scalar gives another point. Multiplying a point by n gives the point at infinity (0,0).
Dividing by 2 in a group with order n is equivalent to multiplying by the scalar 1/2 (mod n).
One can find the inverse of 2 modulo n by the Extended Euclidean Algorithm.
1/2 (mod n) = 57896044618658097711785492504343953926418782139537452191302581570759080747169
You'd have to multiply (x,y) by 1/2 (mod n), this gives
x = 21505829891763648114329055987619236494102133314575206970830385799158076338148
y = 98003708678762621233683240503080860129026887322874138805529884920309963580118
The group is defined by two operations - addition of two points, and doubling a point.
From this we easily could multiply a point by scalar, this is series of additions and doublings.
Multiplying a point by scalar gives another point. Multiplying a point by n gives the point at infinity (0,0).
Dividing by 2 in a group with order n is equivalent to multiplying by the scalar 1/2 (mod n).
One can find the inverse of 2 modulo n by the Extended Euclidean Algorithm.
1/2 (mod n) = 57896044618658097711785492504343953926418782139537452191302581570759080747169
You'd have to multiply (x,y) by 1/2 (mod n), this gives
x = 21505829891763648114329055987619236494102133314575206970830385799158076338148
y = 98003708678762621233683240503080860129026887322874138805529884920309963580118
How
I just reread your post and I understand that you manage to do it ?So my question is simple, how multiply a point (x,y) by 1/2 (mod n) ? I can get a working méthod with python
Assume i have this public key (x = 72488970228380509287422715226575535698893157273063074627791787432852706183111 , y = 2898698443831883535403436258712770888294397026493185421712108624767191)
what is the math méthod to multiply (x,y) by 1/2 (mod n) --> it is also assumed that I do not know the private key
How get (x = 21505829891763648114329055987619236494102133314575206970830385799158076338148 , y = 98003708678762621233683240503080860129026887322874138805529884920309963580118)
c = (qy py) / (qx px)
rx = c^2 px qx
Wrong formula
Use this one -->
dx = (Qx - Px) % modulo
dy = (Qy - Py) % modulo
c = dy * invert(dx) % modulo
Rx = (c*c - Px - Qx) % modulo
Ry = (c*(Px - Rx) - Py) % modulo
rx = c^2 px qx
Wrong formula
Use this one -->
dx = (Qx - Px) % modulo
dy = (Qy - Py) % modulo
c = dy * invert(dx) % modulo
Rx = (c*c - Px - Qx) % modulo
Ry = (c*(Px - Rx) - Py) % modulo
Re: Half of any bitcoin (crypto) public key - (public key half)
Ok, this confirms what i thought. Even if it is possible to halve a point, it is useless ^^
On the other hand I still do not know how to do ^^ lol
Thanks for the explanations all.
On the other hand I still do not know how to do ^^ lol
Thanks for the explanations all.
Re: Half of any bitcoin (crypto) public key - (public key half)
this is all because of how 2-1 is defined and its value is 57896044618658097711785492504343953926418782139537452191302581570759080747169 because 2 * 57896044618658097711785492504343953926418782139537452191302581570759080747169 ≡ 1 (mod N)
it can be computed using Euclidean algorithm or the simplified 2(prime-2) mode prime.
now multiplying that with the point we had returns the half point
x = 21505829891763648114329055987619236494102133314575206970830385799158076338148
Y = 98003708678762621233683240503080860129026887322874138805529884920309963580118
why not. private key will tell you how many times to add G to itself. but after you are done and have the value for k*G as point P then you can do whatever you want with that point. for example you can add another G to that point and compute Q=P+G or R=P-G and similarly you can multiply that point with any number like computing S=3*P (the same way you would compute 3*G).
2-1 is just another number that your point (P or G or Q,...) is multiplied by. you just have to first calculate what integer 2-1 is in congruence with. to do that you compute its modular multiplicative inverse as i explained above. there is also an example in my second comment with small numbers.
Hum! I'm clearly a noob and i can't get it working..
I'm ok with the concept of multiplicative inverse of 2 --> 57896044618658097711785492504343953926418782139537452191302581570759080747169
But how use this number to half a public key with x and y coordinates ?
I have a lot of difficulty doing research with my broken English, someone can clarify this for me, perhaps with a python code ---> how half public key (private key 10) to get public key (private key 5)
It's now that I realize that mathematics is a profession ^^ lol
Thanks in advance
it can be computed using Euclidean algorithm or the simplified 2(prime-2) mode prime.
now multiplying that with the point we had returns the half point
x = 21505829891763648114329055987619236494102133314575206970830385799158076338148
Y = 98003708678762621233683240503080860129026887322874138805529884920309963580118
why not. private key will tell you how many times to add G to itself. but after you are done and have the value for k*G as point P then you can do whatever you want with that point. for example you can add another G to that point and compute Q=P+G or R=P-G and similarly you can multiply that point with any number like computing S=3*P (the same way you would compute 3*G).
2-1 is just another number that your point (P or G or Q,...) is multiplied by. you just have to first calculate what integer 2-1 is in congruence with. to do that you compute its modular multiplicative inverse as i explained above. there is also an example in my second comment with small numbers.
Hum! I'm clearly a noob and i can't get it working..
I'm ok with the concept of multiplicative inverse of 2 --> 57896044618658097711785492504343953926418782139537452191302581570759080747169
But how use this number to half a public key with x and y coordinates ?
I have a lot of difficulty doing research with my broken English, someone can clarify this for me, perhaps with a python code ---> how half public key (private key 10) to get public key (private key 5)
It's now that I realize that mathematics is a profession ^^ lol
Thanks in advance
That's what I wanted! Could you make private key 3?
We must not forget that there are two formulasThe one you used to find the point corresponding to the private key: 2 (or rather 0000000000000000000000000000000000000000000000000000000000000002 to be more precise) it is Duplication of points.
You did it in your example with the base point(but it can be another point)--> 1 + 1 =2
To go now with 3 we need to do --> 2 + 1 = 3 (we have now 2 différents points and we can't doubling them)
For that you need to use the second formula:
modulo = 115792089237316195423570985008687907853269984665640564039457584007908834671663
Px = 89565891926547004231252920425935692360644145829622209833684329913297188986597 (x coordinate point 2)
Py = 12158399299693830322967808612713398636155367887041628176798871954788371653930 (y coordinate point 2)
Qx = 55066263022277343669578718895168534326250603453777594175500187360389116729240 (x coordinate point 1) not because it is the base point, just because it is the point n°1
Qy = 32670510020758816978083085130507043184471273380659243275938904335757337482424 (y coordinate point 1)
dx = (Qx - Px) % modulo --> 34499628904269660561674201530767158034393542375844615658184142552908072257357
dy = (Qy - Py) % modulo --> 95279978516251208768455708490894263304954079172022948940317551626939868843169
c = dy * invert(dx) % modulo --> 23578750110654438173404407907450265080473019639451825850605815020978465167024
Rx = (c*c - Px - Qx) % modulo --> 112711660439710606056748659173929673102114977341539408544630613555209775888121 (x coordinate of point (2+1 =3)
Ry = (c*(Px - Rx) - Py) % modulo --> 25583027980570883691656905877401976406448868254816295069919888960541586679410 (y coordinate of point (2+1 =3)
Can't explain better
Re: Half of any bitcoin (crypto) public key - (public key half)
Is it possible without the private key to divide a point by 2 ?
why not. private key will tell you how many times to add G to itself. but after you are done and have the value for k*G as point P then you can do whatever you want with that point. for example you can add another G to that point and compute Q=P+G or R=P-G and similarly you can multiply that point with any number like computing S=3*P (the same way you would compute 3*G).
2-1 is just another number that your point (P or G or Q,...) is multiplied by. you just have to first calculate what integer 2-1 is in congruence with. to do that you compute its modular multiplicative inverse as i explained above. there is also an example in my second comment with small numbers.
First thanks for the response.
Ok i begin to understand the concept but not ready to go yet ^^.
I know add or substract a point to another (different or equal) but i can't divide a point by any number if i only have the x and y coordinates.
If it's possible can you show me how divide this point by 2 for example ?
x = 72488970228380509287422715226575535698893157273063074627791787432852706183111
y = 62070622898698443831883535403436258712770888294397026493185421712108624767191
It is public key for private key: 10 , and we say here i haven't got this private key.
I expect to obtain the public key:
x = 21505829891763648114329055987619236494102133314575206970830385799158076338148
Y = 98003708678762621233683240503080860129026887322874138805529884920309963580118
(private key 5 )
Thanks in advance
Re: Half of any bitcoin (crypto) public key - (public key half)
hello,
I read this post several, several, several times and i can't understand how it is possible to half a point like the first example.
Is it possible without the private key to divide a point by 2 ?
assume i have like the first example a point without the private key for it and divide it by 2
x = 545d2c25b98ec8827f2d9bee22b7a9fb98091b2008bc45b3b806d44624dc038c
y = f1e18224b09ed00841c5407e571829e41876d44522f97e05e405a91ef38d4f00
How get ?
x = 8f870b1693cb408f96a3da9e3623b6d0315a403395d79f412f26044210bcddd2
y = 8a0a3e2399787a1f084d53500bc577ba1cc4e19ab7b2d9a2bd327e5e56e8afa0
I clearly don't understand the concept of multiply by 2^-1 (mod n)
is it possible for someone to clarify this with an real example (not n, N P Q ETC... LOL ..I was the one sleeping in math classroom ^)
Thanks
I read this post several, several, several times and i can't understand how it is possible to half a point like the first example.
Is it possible without the private key to divide a point by 2 ?
assume i have like the first example a point without the private key for it and divide it by 2
x = 545d2c25b98ec8827f2d9bee22b7a9fb98091b2008bc45b3b806d44624dc038c
y = f1e18224b09ed00841c5407e571829e41876d44522f97e05e405a91ef38d4f00
How get ?
x = 8f870b1693cb408f96a3da9e3623b6d0315a403395d79f412f26044210bcddd2
y = 8a0a3e2399787a1f084d53500bc577ba1cc4e19ab7b2d9a2bd327e5e56e8afa0
I clearly don't understand the concept of multiply by 2^-1 (mod n)
is it possible for someone to clarify this with an real example (not n, N P Q ETC... LOL ..I was the one sleeping in math classroom ^)
Thanks
Here's some working python code that generates the point of the public key for private key = 2
Code:
# Inversion using Extended Euclidean algorithm.
def EEA_invert(a, b):
r = {}; s = {}; r[0] = a; r[1] = b; s[0] = 1; s[1] = 0
i = 1;
while True:
if r[i]==0: break
q = r[i-1]//r[i]; r[i+1] = r[i-1] - q*r[i]; s[i+1] = s[i-1] - q*s[i]
i += 1
return s[i-1] % b
# Bitcoin's EC parameters: see https://en.bitcoin.it/wiki/Secp256k1
G = '79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'.replace(' ', '')
gx, gy = int(G[:64], 16), int(G[64:], 16)
p = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
# Calculate differential at the generator point.
slope = (3*gx**2)*EEA_invert(2*gy, p) % p
# Calculate x, y.
x = (slope**2 - 2*gx) % p
y = (slope*(gx - x) - gy) % p
print(hex(x), hex(y))
which yields:def EEA_invert(a, b):
r = {}; s = {}; r[0] = a; r[1] = b; s[0] = 1; s[1] = 0
i = 1;
while True:
if r[i]==0: break
q = r[i-1]//r[i]; r[i+1] = r[i-1] - q*r[i]; s[i+1] = s[i-1] - q*s[i]
i += 1
return s[i-1] % b
# Bitcoin's EC parameters: see https://en.bitcoin.it/wiki/Secp256k1
G = '79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'.replace(' ', '')
gx, gy = int(G[:64], 16), int(G[64:], 16)
p = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
# Calculate differential at the generator point.
slope = (3*gx**2)*EEA_invert(2*gy, p) % p
# Calculate x, y.
x = (slope**2 - 2*gx) % p
y = (slope*(gx - x) - gy) % p
print(hex(x), hex(y))
Code:
('0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5',
'0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a')
'0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a')
Hello everyone !
I know it is a very old thread but is it possible for someone to explain what is the differential at the generator point (slope ?) and why it is use in calculation ?
I see this function give the result for the private key 2 (doubling Gx) but is it possible with this formula to obtain the result for 200 (for example) or is it and another formula.
Thanks in advance
If the formula is always the same, All public keys will also always be the same! "Where am I wrong?
(dx, dy, c, R.x, R.y, Q.x Q.y, P.x, P.y)Can someone explain to me what are this?
I think Rx and Ry are the coordinates of the public key, right?
[/quote]
ok, I will try to explain as simply as possible because it is true that I myself struggled to understand the system.
So it is a question here of adding 2 points (not the same). In this example we use :
first point: (all values are in décimal for a better comprehension)
X coordinate: 21262057306151627953595685090280431278183829487175876377991189246716355947009 (it is Qx)
Y coordinate: 41749993296225487051377864631615517161996906063147759678534462689479575333124 (it is Qy)
The Private key for this point is 0000000000000000000000000000000000000000000000000000000000000008
second point to add:
X coordinate: 89565891926547004231252920425935692360644145829622209833684329913297188986597 (it is Px)
Y coordinate: 12158399299693830322967808612713398636155367887041628176798871954788371653930 (it is Py)
The Private key for this point is 0000000000000000000000000000000000000000000000000000000000000002
So to add the 1st point to the second we use the formula : (here modulo is 115792089237316195423570985008687907853269984665640564039457584007908834671663 )
dx = (Q.x - P.x) % modulo
dy = (Q.y - P.y) % modulo
c = dy * invert(dx) % modulo
R.x = (c*c - P.x - Q.x) % modulo
R.y = (c*(P.x - R.x) - P.y) % modulo
in our example we have
dx = (21262057306151627953595685090280431278183829487175876377991189246716355947009 - 89565891926547004231252920425935692360644145829622209833684329913297188986597) % modulo
dx = 47488254616920819145913749673032646770809668323194230583764443341328001632075
dy = (41749993296225487051377864631615517161996906063147759678534462689479575333124 - 12158399299693830322967808612713398636155367887041628176798871954788371653930) % modulo
dy = 29591593996531656728410056018902118525841538176106131501735590734691203679194
invert of dx = 70279122268919195963430815486314537773961171454828771794853116552210630553734
c = dy * invert(dx) % modulo
c = 16132032934385503768504319366562120314980927452732756733183380715276156205226
So the new point (8 + 2)
R.x = (c*c - P.x - Q.x) % modulo
R.x --> X coordinate of (8+2) = 72488970228380509287422715226575535698893157273063074627791787432852706183111
R.y = (c*(P.x - R.x) - P.y) % modulo
R.y = 62070622898698443831883535403436258712770888294397026493185421712108624767191
If we check these coordinates, we find that it corresponds to the private key: 0000000000000000000000000000000000000000000000000000000000000010
There you go, I hope I was as clear as possible and apologies for my broken English ^^
there is no special formula for point subtraction as far as i know. instead the P-Q is simply defined as P+(-Q) (same as addition) and -Q or negative of a point is defined as negating its y coordinate. or in other words -Q(x,y) = Q(x,-y) and since we don't use negative numbers in modular arithmetic -y becomes P-y where P is curve's prime.
oOO !! wonderfully explained, first test -> total success .. I understood the first time when research for several weeks had not led to much.
Many thanks to you BrewMaster (again ^^)
It is this notation (-y becomes P-y where P is curve's prime) that I have not seen anywhere that I am lacking.
Hello everyone, good! thanks to the help of MrFreeDragon and BrewMaster I now have a good basis for adding 2 points on an elliptical curve.
As a reminder :
If you want to double point P in order to receive R = P + P, you should make the following:
c = 3 * P.x * Px * invert (2 * P.y)% modulo
R.x = (c * c - 2 * P.x)% modulo
R.y = (c * (P.x - R.x) - P.y)% modulo
modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
and
If you want to add 2 points P and Q (2 different non-zero Points) there is another formula for R = P + Q:
dx = (Q.x - P.x)% modulo
dy = (Q.y - P.y)% modulo
c = dy * invert (dx)% modulo
R.x = (c * c - P.x - Q.x)% modulo
R.y = (c * (P.x - R.x) - P.y)% modulo
I have now no problem with this but as you can imagine, I still have 1 problem ^^, certainly due to my approximate understanding of English I am unable to find a formula for point to point subtraction. Is this also possible?
Thanks in advance (again^^)
As a reminder :
If you want to double point P in order to receive R = P + P, you should make the following:
c = 3 * P.x * Px * invert (2 * P.y)% modulo
R.x = (c * c - 2 * P.x)% modulo
R.y = (c * (P.x - R.x) - P.y)% modulo
modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
and
If you want to add 2 points P and Q (2 different non-zero Points) there is another formula for R = P + Q:
dx = (Q.x - P.x)% modulo
dy = (Q.y - P.y)% modulo
c = dy * invert (dx)% modulo
R.x = (c * c - P.x - Q.x)% modulo
R.y = (c * (P.x - R.x) - P.y)% modulo
I have now no problem with this but as you can imagine, I still have 1 problem ^^, certainly due to my approximate understanding of English I am unable to find a formula for point to point subtraction. Is this also possible?
Thanks in advance (again^^)