 Show Posts
|
|
Pages: [1] 2 »
|
maybe you should use a library. For that particular function? For modinv only? I use this one for modular multiplicative inverse. 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;
} 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 |
|
|
|
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" 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:])
et voila ! edit: it is for random génération, don't know if you want a linear génération ? in this case ETFbitcoin example is the good one ^^ |
|
|
|
HOW
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. |
|
|
|
it seems that bitaddress version (1.6) dates from 11 Jan 2014..don't exist in 2012 |
|
|
|
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 --> original parameter #N = 57896044618658097711785492504343953926418782139537452191302581570759080747169 --> 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) |
|
|
|
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 |
|
|
|
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 ^^ |
|
|
|
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 = 98003708678762621233683240503080860129026887322874138805529884920309963580118How 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't 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
|
|
|
|
|
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.
|
|
|
|
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 |
|
|
|
That's what I wanted! Could you make private key 3?
We must not forget that there are two formulas The 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--> 1 + 1 =2 ( but that could be another point) 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°1Qy = 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 |
|
|
|
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 |
|
|
|
|
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
|
|
|
|
Here's some working python code that generates the point of the public key for private key = 2 # 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: ('0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5',
'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 --> Y coordinate of (8+2) = 62070622898698443831883535403436258712770888294397026493185421712108624767191
If we check these coordinates, we find that it corresponds to the private key: 000000000000000000000000000000000000000000000000000000000000000a (10)
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 substraction. Is this also possible?
Thanks in advance (again^^)
|
|
|
|
|
