|
Title: Presentation of my ECC Calculator Post by: MixMAx123 on November 16, 2019, 07:52:32 PM Here I would like to introduce my little ECC calculator
https://github.com/MrMaxweII/Secp256k1-Calculator/blob/master/README.md https://user-images.githubusercontent.com/34688939/68996640-257c1d00-089d-11ea-960b-4a55e3ef7781.png Secp256k1-Calculator A small calculator of operations calculated on the elliptic curve Secp256k1. All entered in hexa decimal numbers. All calculations are done mod (p). Same numbers are marked in color. following arithmetic operations are implemented: - mod(n) addition, subtraction, multiplication and division of 256bit hexadecimal numbers. - addition and subtraction of points on the curve. - Multiplication with a point on the curve - Divide a point on the curve with a number - ECDSA Signature - ECDSA verification Title: Re: Presentation of my ECC Calculator Post by: charlie137 on November 19, 2019, 04:28:07 PM very smooth solution!! sry no merit https://www.blockchain.com/btc/tx/3eda977b908fcdd8962794be6b48f8f07fa988a56b275b39919d6efd6e3342c3
Title: Re: Presentation of my ECC Calculator Post by: MixMAx123 on November 19, 2019, 06:10:19 PM Thank you very much Charlie137 :-*
Have you (or anyone else) tested / compared everything? In particular, the signature is difficult to compare with a reverence program, since always the "k" (random number) is different. Title: Re: Presentation of my ECC Calculator Post by: bytcoin on February 15, 2020, 10:37:12 PM Here I would like to introduce my little ECC calculator I used and liked it ... very good toolhttps://github.com/MrMaxweII/Secp256k1-Calculator/blob/master/README.md https://user-images.githubusercontent.com/34688939/68996640-257c1d00-089d-11ea-960b-4a55e3ef7781.png Secp256k1-Calculator A small calculator of operations calculated on the elliptic curve Secp256k1. All entered in hexa decimal numbers. All calculations are done mod (p). Same numbers are marked in color. following arithmetic operations are implemented: - mod(n) addition, subtraction, multiplication and division of 256bit hexadecimal numbers. - addition and subtraction of points on the curve. - Multiplication with a point on the curve - Divide a point on the curve with a number - ECDSA Signature - ECDSA verification Title: Re: Presentation of my ECC Calculator Post by: MixMAx123 on February 16, 2020, 09:32:57 AM Thank you very much.
If you have any requests, improvements or comments. Just ask! I would be happy to extend it. Title: Re: Presentation of my ECC Calculator Post by: MrFreeDragon on April 11, 2020, 01:28:31 AM Nice idea and realization!
What libriary do you use to perform scalar multiplication and division (multiplication by inverse scalar). The multiplication and division is calculated very slow.... like 10-20 seconds for one operation. However one operation should be performed immediately i beleive. Points addition/division is also made no immediately but with some 1-2 seconds freeze. My python code performs 120-140 scalar multiplications per second on the same machine (faster by 1.5k times). So, no need to calculate just one operation for 10-20 seconds. For python I use gmpy2 C based library. Not sure which one should you use for Java. If you improve the productivity it would be great Title: Re: Presentation of my ECC Calculator Post by: arulbero on April 12, 2020, 04:23:49 PM My python code performs 120-140 scalar multiplications per second on the same machine (faster by 1.5k times). So, no need to calculate just one operation for 10-20 seconds. For python I use gmpy2 C based library. Not sure which one should you use for Java. I have a python code that performs over 4300 scalar multiplications per second (about 2800 if I don't use the invert function from gmpy2). this is a file "privatekeys.txt" with 10k private key randomly generated: Code: 1AD2C071915A20CE95C8D837E46F40D2A9BB40E15211762CD870A9EC24FD5DCF and with my script "private_to_publickeys.py " I get: Code: $ time python3 private_to_publickeys.py privatekeys.txt > publickeys.txt if I don't use gmpy2 at all I get instead: Code: $ time python3 private_to_publickeys.py privatekeys.txt > publickeys.txt Title: Re: Presentation of my ECC Calculator Post by: MixMAx123 on April 12, 2020, 05:19:27 PM Nice idea and realization! What libriary do you use to perform scalar multiplication and division (multiplication by inverse scalar). The multiplication and division is calculated very slow.... like 10-20 seconds for one operation. However one operation should be performed immediately i beleive. Points addition/division is also made no immediately but with some 1-2 seconds freeze. My python code performs 120-140 scalar multiplications per second on the same machine (faster by 1.5k times). So, no need to calculate just one operation for 10-20 seconds. For python I use gmpy2 C based library. Not sure which one should you use for Java. If you improve the productivity it would be great Thank you for the information and the feedback. I think that's very good! I use my self-written library Secp256k1: https://github.com/MrMaxweII/Secp256k1 (https://github.com/MrMaxweII/Secp256k1) When it comes to calculating time, it makes a big difference whether you multiply by a known generator point or an unknown point on the curve. If there is an unknown point on the elliptic curve, the algorithm is different and much slower. I don't know anything about other python codes because I only program in Java. Surely there will be algorithms that are better or faster than mine. My code is not particularly performance, but the result is correct in the end. On a powerful PC, the calculation takes an average of 2 seconds. This is not particularly fast, but I find it sufficient for this purpose in this calculator. It is not the case that they use this calculator to carry out mass calculations one after the other. It is not made for such purposes. When it comes to speed, you shouldn't use my library. I am sorry, for this reason, I do not think that I will invest a lot of time here to make the calculation faster. If there was a great demand and no alternatives, it would be different. Title: Re: Presentation of my ECC Calculator Post by: arulbero on April 12, 2020, 05:29:26 PM 1) on my pc (Ubuntu 17.04) I get a windows too small; how to resize it?
2) Scalar 653646536547337543 Vector x 65366546543536537574373456456 If I click on the first 'y' I get '0', If I click on the second one I get 'fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f', it is a bug? Title: Re: Presentation of my ECC Calculator Post by: MixMAx123 on April 12, 2020, 05:44:17 PM An X coordinate "65366546543536537574373456456" is not on the SECP256k1 curve. So this is an input error.
If you enter coordinates explicitly, the points must lie on the curve. I'm just starting my Ubuntu to test it there ... So under Linux (Ubuntu) the font size is a bit larger, so that the input fields are a bit too short to display the whole number. But the cursor can be moved in the input field with the arrow keys and the numbers then scroll to the right or left. This at least enables input and output. Even if it's not nice, admittedly. The GUI was created under Windows. There all fields are the right size. I'm sorry if it is different on Linux. With my next update, I will improve that. Title: Re: Presentation of my ECC Calculator Post by: arulbero on April 12, 2020, 05:51:03 PM I'm just starting my Ubuntu to test it there ... My PC Lenovo has a very high resolution: Code: xdpyinfo | grep dimensions Title: Re: Presentation of my ECC Calculator Post by: MixMAx123 on April 12, 2020, 06:05:11 PM I'm just starting my Ubuntu to test it there ... My PC Lenovo has a very high resolution: Code: xdpyinfo | grep dimensions Could you print out a screen? Title: Re: Presentation of my ECC Calculator Post by: arulbero on April 12, 2020, 06:28:13 PM I'm just starting my Ubuntu to test it there ... My PC Lenovo has a very high resolution: Code: xdpyinfo | grep dimensions Could you print out a screen? https://i.imgur.com/A9frh8p.png Title: Re: Presentation of my ECC Calculator Post by: MrFreeDragon on April 13, 2020, 01:02:03 AM -snip- I have a python code that performs over 4300 scalar multiplications per second (about 2800 if I don't use the invert function from gmpy2). -snip- What kind of CPU do you use? I tested the code under Ubuntu, and it needs 16 seconds to perform 10k scalar multiplications for 10k random private keys, so it is 620-630 per second. However for the subsequent multiplications for numbers from 1 up to 10,000 (not random) it needed 0.6 seconds for all 10k multiplications. Title: Re: Presentation of my ECC Calculator Post by: arulbero on April 13, 2020, 06:17:43 AM What kind of CPU do you use? Intel Xeon CPU E3-1505M v6 3.00 GHz, a mobile cpu and my laptop is 3 years old.I tested the code under Ubuntu, and it needs 16 seconds to perform 10k scalar multiplications for 10k random private keys, so it is 620-630 per second. However for the subsequent multiplications for numbers from 1 up to 10,000 (not random) it needed 0.6 seconds for all 10k multiplications. I use a precomputed table of multiples of G. Title: Re: Presentation of my ECC Calculator Post by: Coding Enthusiast on April 13, 2020, 06:59:22 AM I use my self-written library Secp256k1: https://github.com/MrMaxweII/Secp256k1 (https://github.com/MrMaxweII/Secp256k1) One of the main reasons for your code being slow is that you are using BigInteger, or more precisely an arbitrary length integer. The implementation of BigInteger is also known to be not-optimized which contributed to it being slow. Optimization of BigInteger itself could help increase speed by a factor of 5 to 10. Replacing it with a fixed length integer increases the speed by a factor of 20. Replacing methods such as Add, Subtract, Multiply,... with their modular alternatives (AddMod, MultMod,...) increases the speed by a factor of 10. There are some more ideas I'm currently exploring that would optimize ECC further. I've actually started a topic about optimization here 4 month ago but didn't receive any reply so the ideas are kinda on pause right now. Title: Re: Presentation of my ECC Calculator Post by: arulbero on April 13, 2020, 07:18:43 AM There are some more ideas I'm currently exploring that would optimize ECC further. I've actually started a topic about optimization here 4 month ago but didn't receive any reply so the ideas are kinda on pause right now. If you want to share your ideas … Optimizing field operations is the first thing, in particular way a) "mod p" after multiplication b) inversion operation Optimizing scalar multiplication (group operation) is another step. Title: Re: Presentation of my ECC Calculator Post by: Coding Enthusiast on April 13, 2020, 07:40:54 AM If you want to share your ideas … The other ideas were mostly language related (C#) which is why I didn't mention them. For instance I've been experimenting with the new feature added in recent C# versions called ref structs. A ref readonly struct has been a successful optimization too. Another idea was playing around with underlying integer type (UInt32 versus UInt64) and to use 32-bit or half of a UInt64 which later I found an article explaining an optimization for Curve25519 which uses radix 251 representation instead. Basically I've started the optimization from the lowest part which is the integer type and all the basic arithmetic. If there is interest, I could start a topic and share my findings when I'm done optimizing ECC in near future. Title: Re: Presentation of my ECC Calculator Post by: MixMAx123 on April 13, 2020, 09:35:39 AM Quote https://i.imgur.com/A9frh8p.png It looks exactly like me in Ubuntu. The input fields are then a little too short for the length of the number. But it can be scrolled. I use my self-written library Secp256k1: https://github.com/MrMaxweII/Secp256k1 (https://github.com/MrMaxweII/Secp256k1) One of the main reasons for your code being slow is that you are using BigInteger, or more precisely an arbitrary length integer. The implementation of BigInteger is also known to be not-optimized which contributed to it being slow. Optimization of BigInteger itself could help increase speed by a factor of 5 to 10. Replacing it with a fixed length integer increases the speed by a factor of 20. Replacing methods such as Add, Subtract, Multiply,... with their modular alternatives (AddMod, MultMod,...) increases the speed by a factor of 10. There are some more ideas I'm currently exploring that would optimize ECC further. I've actually started a topic about optimization here 4 month ago but didn't receive any reply so the ideas are kinda on pause right now. That's exactly the case! Thanks for the feedback. I know that too, but I didn't mean to change that. Programming my own data type is a lot of work for me and I have other projects I'm working on. I am currently programming a block explorer that uses the LevelDB database from the Bitcoin Core. Using BigInteger is the easiest way to start. If someone knows, provides or programs a suitable data type in Java for this 32 byte data, it would be great and I would then incorporate this into my libraries and into this program. Of course, the required modular operations for this data type must then be provided. I still can't assess how difficult that would be. Title: Re: Presentation of my ECC Calculator Post by: arulbero on April 13, 2020, 12:49:30 PM However for the subsequent multiplications for numbers from 1 up to 10,000 (not random) it needed 0.6 seconds for all 10k multiplications. Consecutive keys: 210k keys per sec; with some optimizations: 800k per sec. Title: Re: Presentation of my ECC Calculator Post by: MrFreeDragon on April 13, 2020, 02:32:28 PM -snip- I use a precomputed table of multiples of G. I did not use any precomputed multiples of G. Do you use just 256 precomupted points for powers of two (2^0, 2^1, 2^2, 2^3, 2^4, ... 2^255) and later represent every private key number in binary and make scalar additions of precomputed points? If no, how much is your precomupted table and what kind of points include? Title: Re: Presentation of my ECC Calculator Post by: MixMAx123 on April 13, 2020, 02:41:45 PM -snip- I use a precomputed table of multiples of G. I did not use any precomputed multiples of G. Do you use just 256 precomupted points for powers of two (2^0, 2^1, 2^2, 2^3, 2^4, ... 2^255) and later represent every private key number in binary and make scalar additions of precomputed points? If no, how much is your precomupted table and what kind of points include? https://github.com/MrMaxweII/Secp256k1-Calculator/blob/master/EXPList.java Title: Re: Presentation of my ECC Calculator Post by: arulbero on April 13, 2020, 03:07:54 PM https://github.com/MrMaxweII/Secp256k1-Calculator/blob/master/EXPList.java -snip- I use a precomputed table of multiples of G. I did not use any precomputed multiples of G. Do you use just 256 precomupted points for powers of two (2^0, 2^1, 2^2, 2^3, 2^4, ... 2^255) and later represent every private key number in binary and make scalar additions of precomputed points? If no, how much is your precomupted table and what kind of points include? If you precompute only the powers of two, you avoid only the doublings. It is like you split your binary key in 256 pieces, each piece in this case is a particular point and then you perform 255 additions between these points. But if you split 256 in 128/64/32/16/8 parts and you precompute every key in these "parts" (in these cases each part has more than 1 point) you can lower the number of additions. I use 32 groups of 255 points = 8160 precomputed points. I represent every private key in binary, I split that number in 32 pieces (each piece has 256/32=8 bit -> 255 elements) and I compute only 32-1 = 31 group additions (instead of 256) for each key. No doubling. Just for example, if you have a 32 bit key: key = 10101010101000001111111101000010 split in 4 pieces of 32/4=8 bits: (10101010)*2^24 + (10100000)*2^16 + (11111111)*2^8 + (01000010) Then I need to do only 3 additions, if I have precomputed this table (a line for each piece): Code: 00000001 00000010 00000011 … 11111111 Each line has 255 elements because you don't need the (00000000) element. For a 256 bit key, this is the precomputed table (32 lines * 255 elements = 8160): Code: 2^0 , 2*2^0, 3*2^0, … , 255*2^0 I split a 256 bit key in 32 pieces of 8 bit and I compute 31 additions. Title: Re: Presentation of my ECC Calculator Post by: MrFreeDragon on April 13, 2020, 04:06:59 PM -snip- I represent every private key in binary, I split that number in 32 pieces (each piece has 256/32=8 bit -> 255 elements) and I compute only 32-1 = 31 group additions (instead of 256) for each key. No doubling. -snip- I split a 256 bit key in 32 pieces of 8 bit and I compute 31 additions. Thank you very much! Very good approach! I have tested already with 256 precomputed powers of two (so performed 255 additions) - for 10k random private keys I need 7.13 seconds (1400 per second) compared to 16 seconds (625 per second) without precomputed table. More than 2 times improvement. I beleive that with your approach the speed will be faster. Not sure but seems that if I need only 31 additions instead of 255, the speed should be faster by 255/31 = 8 times, so for 10k I will need less than 1 second (11k per second). I use 32 groups of 255 points = 8160 precomputed points. How do you think, if use 16 groups 65,535 points (1 048 576 points) will it be faster? Only 15 additions will be required. Title: Re: Presentation of my ECC Calculator Post by: arulbero on April 13, 2020, 04:15:15 PM I use 32 groups of 255 points = 8160 precomputed points. How do you think, if use 16 groups 65,535 points (1 048 576 points) will it be faster? Only 15 additions will be required. I think it would be slower, the table would be in RAM and not in some faster cpu's cache. Title: Re: Presentation of my ECC Calculator Post by: brainless on April 22, 2021, 09:15:15 PM can some ecc expert write about Point addition / Point concatenate
https://bitcointalk.org/index.php?topic=5332526.new#new waiting your expert views Title: Re: Presentation of my ECC Calculator Post by: fxsniper on April 23, 2021, 02:26:47 AM How to use this program?
Did developer have video show hot to use? Title: Re: Presentation of my ECC Calculator Post by: MixMAx123 on April 23, 2021, 07:23:18 AM How to use this program? Did developer have video show hot to use? If I find the time, I'll make a video. Unfortunately, my English is very poor and I am not a video professional. I would be very happy from someone else who would like to make a video of the program :-) |
