Bitcoin Forum
November 23, 2017, 07:45:27 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Elliptic Curve operations in Bitcoin  (Read 717 times)
bolfio
Newbie
*
Offline Offline

Activity: 11


View Profile
October 20, 2017, 07:06:05 PM
 #1

Hi all.

I have got a question: Bitcoin uses Elliptic Curves maths for several reasons. But my question is: How does it work in reality?

Of course in every book you find the "normal" addition and point doubling formulas in every book, such as:

http://patentimages.storage.googleapis.com/EP1653428A1/imgf0001.png


This is nice to see, but is is "standard theory", these computations are very expensive; there are much more efficient algorithms. Especially, Renes, Costello and Batina showed "complete addition formulas" (see https://eprint.iacr.org/2015/1060.pdf), where one calculates in the projective plane.

So, does anyone know how ECC is used in Bitcoin? Is there a possibility where I can find the code in the Bitcoin protocol?


I also read that Bitcoin chose Secp256k1 because of efficiency reasons, so I cannot believe that they use "standard" formulas for calculating.
1511423127
Hero Member
*
Offline Offline

Posts: 1511423127

View Profile Personal Message (Offline)

Ignore
1511423127
Reply with quote  #2

1511423127
Report to moderator
1511423127
Hero Member
*
Offline Offline

Posts: 1511423127

View Profile Personal Message (Offline)

Ignore
1511423127
Reply with quote  #2

1511423127
Report to moderator
Join ICO Now Coinlancer is Disrupting the Freelance marketplace!
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
hingleMC
Jr. Member
*
Offline Offline

Activity: 37


View Profile WWW
October 22, 2017, 12:52:59 PM
 #2

I would give anything to have the ability to run my fingers through secp256k1 (personally) and verify how free it is of any air bubbles

https://en.m.wikipedia.org/wiki/Dual_EC_DRBG


1FoxgDJ3R8ciG611117BvCwHHBrHuHw8vh
aplistir
Member
**
Offline Offline

Activity: 84


View Profile
October 22, 2017, 01:23:27 PM
 #3

I have got a question: Bitcoin uses Elliptic Curves maths for several reasons. But my question is: How does it work in reality?

This is nice to see, but is is "standard theory", these computations are very expensive; there are much more efficient algorithms. Especially, Renes, Costello and Batina showed "complete addition formulas" (see https://eprint.iacr.org/2015/1060.pdf), where one calculates in the projective plane.

I also read that Bitcoin chose Secp256k1 because of efficiency reasons, so I cannot believe that they use "standard" formulas for calculating.

Bitcoin uses ECC in making the public key from your private key.

Private key is just a big number that is kept secret.
Your private key is multiplied with the base point B using ECC math to get the public key.
Privkey*B=Pubkey

This operation is "one way" meaning that it is easy to do, but almost impossible to reverse.

For some curves like secp256k1 there are some more efficient ways to do the addition and multiplication operations. But basically they do the exact same thing as the "standard formulas" only  ~20-30% faster. For example the field size is  2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 which makes it faster to take the mod operation.

The other thing where bitcoin uses ECC is ECDSA https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
It is a public key signing algorithm, which enables you to verify that you own your address without showing anyone your secret private key. You just use your private key to sign the transfer.

It is really just normal elliptic curve crypto. Nothing that special in it or the curve secp256k1.


My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
aplistir
Member
**
Offline Offline

Activity: 84


View Profile
October 22, 2017, 01:28:52 PM
 #4

I would give anything to have the ability to run my fingers through secp256k1 (personally) and verify how free it is of any air bubbles

What prevents you? It is all public knowledge.

There is even a challenge, where you can win hundreds of thousands of dollars if you can break their crypto  Smiley
https://www.certicom.com/content/dam/certicom/images/pdfs/challenge-2009.pdf

Good luck!

My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
hingleMC
Jr. Member
*
Offline Offline

Activity: 37


View Profile WWW
October 22, 2017, 03:02:25 PM
 #5

I would give anything to have the ability to run my fingers through secp256k1 (personally) and verify how free it is of any air bubbles

What prevents you? It is all public knowledge.

There is even a challenge, where you can win hundreds of thousands of dollars if you can break their crypto  Smiley
https://www.certicom.com/content/dam/certicom/images/pdfs/challenge-2009.pdf

Good luck!



just a few more hours brute forcing this https://blockchain.info/address/1oBgkXsgCDMvoWcnrnm1XvYmRAqiuovFd and drinks are on me


1FoxgDJ3R8ciG611117BvCwHHBrHuHw8vh
btctousd81
Sr. Member
****
Offline Offline

Activity: 252


View Profile WWW
October 22, 2017, 03:25:43 PM
 #6

I would give anything to have the ability to run my fingers through secp256k1 (personally) and verify how free it is of any air bubbles

What prevents you? It is all public knowledge.

There is even a challenge, where you can win hundreds of thousands of dollars if you can break their crypto  Smiley
https://www.certicom.com/content/dam/certicom/images/pdfs/challenge-2009.pdf

Good luck!

what is the bitcoin address ? or is it different type of challenge., i did nt read the pdf yet.

aplistir
Member
**
Offline Offline

Activity: 84


View Profile
October 22, 2017, 03:28:22 PM
 #7

just a few more hours brute forcing this https://blockchain.info/address/1oBgkXsgCDMvoWcnrnm1XvYmRAqiuovFd and drinks are on me

Well at least you are not greedy  Grin

Why not try this address, that has over 1000 000 000$ worth of bitcoins in it:
https://blockchain.info/address/3D2oetdNuZUqQHPJmcMDDHYoqkyNVsFk9r

My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
btctousd81
Sr. Member
****
Offline Offline

Activity: 252


View Profile WWW
October 22, 2017, 04:15:47 PM
 #8

just a few more hours brute forcing this https://blockchain.info/address/1oBgkXsgCDMvoWcnrnm1XvYmRAqiuovFd and drinks are on me

Well at least you are not greedy  Grin

Why not try this address, that has over 1000 000 000$ worth of bitcoins in it:
https://blockchain.info/address/3D2oetdNuZUqQHPJmcMDDHYoqkyNVsFk9r

isnt that multisig address ?, and its diffucult to calculate multiple private keys rather than just one for simple address public key which starts with 1 ?


DannyHamilton
Legendary
*
Offline Offline

Activity: 1988



View Profile
October 22, 2017, 04:51:09 PM
 #9

isnt that multisig address ?,

No.  It's a P2SH address.

P2SH addresses can have multisig as the script that was used to generate the hash, however there is no requirement that the spender use a multisig script when spending it.

and its diffucult to calculate multiple private keys rather than just one for simple address public key which starts with 1 ?

You wouldn't need to calculate multiple private keys.

You would only need to calculate a SINGLE key pair.  Any private/publick key pair at all would work.  You don't even need to find the original key (or keys) that were used when creating the address.

Then, you would build a script that uses the public key that you generated and a nonce value.  After that, all you have to do is brute force the nonce until the hash of the script (public key + nonce) is equal to the hash used for that address.  On average, it should take you approximately 2159 attempts.

bolfio
Newbie
*
Offline Offline

Activity: 11


View Profile
October 22, 2017, 05:24:18 PM
 #10

I have got a question: Bitcoin uses Elliptic Curves maths for several reasons. But my question is: How does it work in reality?

This is nice to see, but is is "standard theory", these computations are very expensive; there are much more efficient algorithms. Especially, Renes, Costello and Batina showed "complete addition formulas" (see https://eprint.iacr.org/2015/1060.pdf), where one calculates in the projective plane.

I also read that Bitcoin chose Secp256k1 because of efficiency reasons, so I cannot believe that they use "standard" formulas for calculating.

Bitcoin uses ECC in making the public key from your private key.

Private key is just a big number that is kept secret.
Your private key is multiplied with the base point B using ECC math to get the public key.
Privkey*B=Pubkey

This operation is "one way" meaning that it is easy to do, but almost impossible to reverse.

Thanks for your answer. Of course, I know the "sense" about kryptography. These is not new for me. My question is why we got these 20-30% faster computations. You wrote:


Quote
For some curves like secp256k1 there are some more efficient ways to do the addition and multiplication operations. But basically they do the exact same thing as the "standard formulas" only  ~20-30% faster. For example the field size is  2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 which makes it faster to take the mod operation.

So my question is: Why is it ~20-30% faster? What are the more efficient ways to do the addition and multiplication operations?

Of course the result is the same as if I would calculate it with the "standard formulas". The specific curve was chosen because you can do more efficient operations on it. But why is this the case?



btctousd81
Sr. Member
****
Offline Offline

Activity: 252


View Profile WWW
October 22, 2017, 05:27:52 PM
 #11

isnt that multisig address ?,

No.  It's a P2SH address.

P2SH addresses can have multisig as the script that was used to generate the hash, however there is no requirement that the spender use a multisig script when spending it.

and its diffucult to calculate multiple private keys rather than just one for simple address public key which starts with 1 ?

You wouldn't need to calculate multiple private keys.

You would only need to calculate a SINGLE key pair.  Any private/publick key pair at all would work.  You don't even need to find the original key (or keys) that were used when creating the address.

Then, you would build a script that uses the public key that you generated and a nonce value.  After that, all you have to do is brute force the nonce until the hash of the script (public key + nonce) is equal to the hash used for that address.  On average, it should take you approximately 2159 attempts.

from 1 sha256 private key i can create WIF private key and public kay pair which is
5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf  1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm

how would i get p2sh address for something like that ?

or am i missing again something .,

does the p2sh address's private key also falls in

int range
1 - 115792089237316195423570985008687907852837564279074904382605163141518161494336

if so then how can i generate a pair ?

lets say , so far i have these

input                        : 1
network                      : Bitcoin mainnet
netcode                      : BTC
secret exponent              : 1
 hex                         : 1
wif                          : KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU73sVHnoWn
 uncompressed                : 5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf
public pair x                : 55066263022277343669578718895168534326250603453777594175500187360389116729240
public pair y                : 32670510020758816978083085130507043184471273380659243275938904335757337482424
 x as hex                    : 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
 y as hex                    : 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
y parity                     : even
key pair as sec              : 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
 uncompressed                : 0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798\
                                 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
hash160                      : 751e76e8199196d454941c45d1b3a323f1433bd6
 uncompressed                : 91b24bf9f5288532960ac687abb035127b1d28a5
Bitcoin address              : 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH
Bitcoin address uncompressed : 1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm
Bitcoin segwit address       : p2y59b9U5YTUAYEDBr5zwSHFoM8pn3ozAhRD



DannyHamilton
Legendary
*
Offline Offline

Activity: 1988



View Profile
October 22, 2017, 05:52:37 PM
 #12

from 1 sha256 private key i can create WIF private key and public kay pair which is
5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf  1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm

That is NOT a public key.

That is a bitcoin address.  Specifically, that is an uncompressed key P2PKH bitcoin address.

From that SAME WIF private key, you could also generate a compressed key P2PKH bitcoin address:
1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH

Furthermore, you could create 2160 different P2SH bitcoin addresses.  Here are a few of them:
38fEX6RbBBMmpu3nbbuULku1xyrrzqqqnE
3Q2iKGxFppUJEZUTUMmahjwUoLNRqDY9o3
3CZj1DTSHD4vhr3zALL3pgs6acyw1deYDt

how would i get p2sh address for something like that ?

Build a bitcoin output script.  Hash it.  Concatenate a byte value of 0x05 in front of the hash value. Encode the result with base64check encoding.

or am i missing again something .

Probably.

does the p2sh address's private key also falls in

int range
1 - 115792089237316195423570985008687907852837564279074904382605163141518161494336

if so then how can i generate a pair ?

P2SH means "pay to script hash".  It doesn't necessarily need a key, but is it is safer to build a script that requires a signature (in which case a signature would be required).

theymos_away
Jr. Member
*
Offline Offline

Activity: 45


View Profile
October 22, 2017, 09:20:32 PM
 #13

Bitcoin Core's ECC code is libsecp256k1, which uses several optimizations to achieve ~5x speedup vs OpenSSL. The code has a lot of comments, eg. this one describing the algorithm exploiting secp256k1's endomorphism: https://github.com/bitcoin-core/secp256k1/blob/0b7024185045a49a1a6a4c5615bf31c94f63d9c4/src/scalar_impl.h#L259

test
bolfio
Newbie
*
Offline Offline

Activity: 11


View Profile
October 24, 2017, 10:51:55 PM
 #14

Bitcoin Core's ECC code is libsecp256k1, which uses several optimizations to achieve ~5x speedup vs OpenSSL. The code has a lot of comments, eg. this one describing the algorithm exploiting secp256k1's endomorphism: https://github.com/bitcoin-core/secp256k1/blob/0b7024185045a49a1a6a4c5615bf31c94f63d9c4/src/scalar_impl.h#L259

Wow, thank you very much!
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!