Title: [Solved] Fail at coding my own Secp256k1 function (Pyhon) Post by: SamYezi on August 09, 2022, 07:36:06 AM Fail at coding my private to public key converter script for Bitcoin (Secp256k1)
Currently going through the book "Programming Bitcoin by Jimmy Song", got stuck on page 61 (Chapter 3), but completed the exercise 5 from chapter 3. You can view the source code: here (https://www.oreilly.com/library/view/programming-bitcoin/9781492031482/preface01.html#setting_up) or in Github (https://github.com/jimmysong/programmingbitcoin) . Even though the book is great for understanding cryptographic different concepts, highly abstracted OOP code from the book makes it somewhat harder to gaining the intuition of the fundamental low-level concepts behind key principles. That's why apart from completing exercises, I like to also code my own procedural functions that solve the same problems. I've tried to code an ECC Secp256k1 priv-to-pub key conversion function, but my implementation... just doesn't work. It converts numbers incorrectly. The code for the script is down below, I've highlighted the part where the function stops Code: #Secp256k1 Bitcoin private to public key converter script Link for the script (https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256k1Procedural.py) The main function uses "Binary expansion" technique, but it seems like the problem lies in the "Addition" function that doesn't have it. To see some results I copied OOP code from the book, refactored it a bit uploaded to github and it works: https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256K1OOP.py Tried to debug the 1st code by myself, but failed. If you could help, I'd appreciate it! Edit 1: Updated the code, here on GitHub. Works for big numbers but works correctly for small numbers. In test case 2 coordinates for public key are right, but the public key itself is wrong Edit 2: I've refactored the script once again and everything works now. The test case 1 values in the comments were incorrect and now it outputs the right values. Also the public key outputs are also working properly. Thanks for your help! Title: Re: Fail at coding my own Secp256k1 function (Pyhon) Post by: NotATether on August 09, 2022, 08:24:14 AM Code: while coef: Let's unroll this loop: - Current (x,y) is set to G - Start at the least-significant bit - If the bit is odd: -- Then set Result = Current(x,y) + G [for the first iteration this means G+G] - Set CurrentX += G [again, for the first iteration, it is G+G]. Do you see the problem here? As you go through all of the bits, you are *adding* G to itself, this will make G, 2G, 3G, and so forth. You have to multiply the CurrentX by 2 each time, to get G, 2G, 4G, 8G, 16G,... (2^256-1)*G. And each time the bit is odd, you are adding another G to the result which is already full of G's you're adding in succession, when you should set result = 0 in the initialization, and then you add it to Current (x,y). That is to say, Result += Current(x,y). Binary expansion on private keys doesn't work without multiplication. Title: Re: Fail at coding my own Secp256k1 function (Pyhon) Post by: PowerGlove on August 09, 2022, 09:00:17 AM You're almost there, change this (in secp256k1BinaryExpansion):
Code: if coef & 1: To this: Code: if coef & 1: And your second test case will pass (i.e. 0x45300f2b990d332c0ee0efd69f2c21c323d0e2d20e7bfa7b1970bbf169174c82 => (40766947848522619068424335498612406856128862642075168802372109289834906557916, 70486353993054234343658342414815626812704078223802622900411169732153437188990)) I haven't checked your code carefully though, so I wouldn't consider this "working" just yet. :) Title: Re: Fail at coding my own Secp256k1 function (Pyhon) Post by: SamYezi on August 11, 2022, 12:09:21 PM Code: while coef: Let's unroll this loop: - Current (x,y) is set to G - Start at the least-significant bit - If the bit is odd: -- Then set Result = Current(x,y) + G [for the first iteration this means G+G] - Set CurrentX += G [again, for the first iteration, it is G+G]. Do you see the problem here? As you go through all of the bits, you are *adding* G to itself, this will make G, 2G, 3G, and so forth. You have to multiply the CurrentX by 2 each time, to get G, 2G, 4G, 8G, 16G,... (2^256-1)*G. And each time the bit is odd, you are adding another G to the result which is already full of G's you're adding in succession, when you should set result = 0 in the initialization, and then you add it to Current (x,y). That is to say, Result += Current(x,y). Binary expansion on private keys doesn't work without multiplication. Ok, It is helpful. I've made a few changes. But it still doesn't work for small numbers (Don't know why), https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256k1Procedural.py Sorry, for a delayed response Title: Re: Fail at coding my own Secp256k1 function (Pyhon) Post by: SamYezi on August 11, 2022, 12:25:17 PM You're almost there, change this (in secp256k1BinaryExpansion): Code: if coef & 1: To this: Code: if coef & 1: And your second test case will pass (i.e. 0x45300f2b990d332c0ee0efd69f2c21c323d0e2d20e7bfa7b1970bbf169174c82 => (40766947848522619068424335498612406856128862642075168802372109289834906557916, 70486353993054234343658342414815626812704078223802622900411169732153437188990)) I haven't checked your code carefully though, so I wouldn't consider this "working" just yet. :) I got it, and your suggestions are useful. I changed the code here and on Github. However It still doesn't work for small numbers (See the test case 1) https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256k1Procedural.py Sorry, for a delayed response Title: Re: Fail at coding my own Secp256k1 function (Pyhon) Post by: j2002ba2 on August 11, 2022, 05:18:23 PM ... I got it, and your suggestions are useful. I changed the code here and on Github. However It still doesn't work for small numbers (See the test case 1) https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256k1Procedural.py Sorry, for a delayed response You got mistaken somewhere (or, as usual, in many places). Test case 1 asks us to multiply (47,71) by 8 modulo 223 (with a=0, b=7). However with this prime the curve has structure 42x6, it is noncyclic. Point (47,71) is from the group of (7,166); while (49,71) is from the group of (8,127). So, you could never reach either point from the other one. You might want to change the test. If you insist on modulo 223, then b=5 is a good choice. Otherwise (b=7) use modulo 67 or 79, they are a bit like p and n in secp256k1, modulo one of them the group size is the other. Title: Re: Fail at coding my own Secp256k1 function (Pyhon) Post by: SamYezi on August 12, 2022, 12:42:37 PM ... I got it, and your suggestions are useful. I changed the code here and on Github. However It still doesn't work for small numbers (See the test case 1) https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256k1Procedural.py Sorry, for a delayed response You got mistaken somewhere (or, as usual, in many places). Test case 1 asks us to multiply (47,71) by 8 modulo 223 (with a=0, b=7). However with this prime the curve has structure 42x6, it is noncyclic. Point (47,71) is from the group of (7,166); while (49,71) is from the group of (8,127). So, you could never reach either point from the other one. You might want to change the test. If you insist on modulo 223, then b=5 is a good choice. Otherwise (b=7) use modulo 67 or 79, they are a bit like p and n in secp256k1, modulo one of them the group size is the other. Yeah that's a good idea. However these test case 1 values I took from the book, and I checked the values once again and the problem was that the right values in the comments were incorrect. Now that I've refactored the script, it works fine. Also, Public keys outputs are being correct as well. Thanks for your tips! |