Bitcoin Forum
May 23, 2019, 02:26:11 AM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: How is a public key calculated from a private key using ecc?  (Read 125 times)
Anonymous Kid
Member
**
Offline Offline

Activity: 182
Merit: 22


View Profile
October 02, 2018, 07:39:21 AM
Merited by theymos (4), bones261 (2)
 #1

As I understand it a pub key is calculated by;

u = random number (private key)
(x, y) = G = Base point

uG = P = public key

my question is, if its possible to calculate the pub key with uG then since you are doing u computations already, can't you just calculate the private key from P?
Just brute force G as many times as needed until you arrive at P.

Obviously I am misunderstanding something. Is P calculated in a more efficient way than just u*G?
1558578371
Hero Member
*
Offline Offline

Posts: 1558578371

View Profile Personal Message (Offline)

Ignore
1558578371
Reply with quote  #2

1558578371
Report to moderator
1558578371
Hero Member
*
Offline Offline

Posts: 1558578371

View Profile Personal Message (Offline)

Ignore
1558578371
Reply with quote  #2

1558578371
Report to moderator
1558578371
Hero Member
*
Offline Offline

Posts: 1558578371

View Profile Personal Message (Offline)

Ignore
1558578371
Reply with quote  #2

1558578371
Report to moderator
GET 25 FREE SPINS AT REGISTRATION
GET 100% BONUS ON FIRST DEPOSIT
PLAY NOW
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
tromp
Hero Member
*****
Offline Offline

Activity: 590
Merit: 528


View Profile
October 02, 2018, 08:03:58 AM
Merited by theymos (4), bones261 (2), ETFbitcoin (1), Anonymous Kid (1)
 #2

> Obviously I am misunderstanding something. Is P calculated in a more efficient way than just u*G?

Yes; u*G is computed in time logarithmic in u, not linear in u as you seem to think.
For instance 13*G is computed as 2 * (2 * (2 * G + G)) + G.
Anonymous Kid
Member
**
Offline Offline

Activity: 182
Merit: 22


View Profile
October 02, 2018, 08:27:33 AM
 #3

Yes; u*G is computed in time logarithmic in u, not linear in u as you seem to think.
For instance 13*G is computed as 2 * (2 * (2 * G + G)) + G.

Ah yes. This makes a lot more sense. Thanks.
aplistir
Full Member
***
Offline Offline

Activity: 315
Merit: 144



View Profile
October 02, 2018, 12:57:23 PM
Last edit: October 02, 2018, 01:51:49 PM by aplistir
 #4

my question is, if its possible to calculate the pub key with uG then since you are doing u computations already, can't you just calculate the private key from P?
Just brute force G as many times as needed until you arrive at P.

The numbers are so big that brute forcing is not possible with the technology that we currently have. Even if all the existing computers would be used simultaneously for only that purpose, it would still take more than 10000 years to brute force ONE bitcoin key. (Much, much more than 10000 years.)

Yes; u*G is computed in time logarithmic in u, not linear in u as you seem to think.
For instance 13*G is computed as 2 * (2 * (2 * G + G)) + G.

Correct, but I think the same can be more clearly explained in the way  it is actually done:
First pre-calculate the values:
G, 2*G, 4*G, 8*G, 16*G, 32*G ....... 2²⁵⁶*G

Then these pre-calculated values are used for getting any desired value by using only addition.
eg:
13*G= 8*G+4*G+G
This is faster, because you do not have to do the same multiplications every time. You can just use addition. And to do this you only need to keep the 256 precalculated values in memory.

My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
andytoshi
Full Member
***
Offline Offline

Activity: 174
Merit: 131

-


View Profile
October 02, 2018, 02:03:25 PM
Merited by achow101 (3), TheArchaeologist (3)
 #5

Not to detract from the main point, but if you were implementing this multiplication yourself, using the "powers of two" ladder is a bad idea for security reasons. Specifically, for each 1 bit in your secret key you're adding 2^i*G, while for each 0 bit you're not doing anything. Somebody timing your algorithm could easily determine how many powers of 2 you added, i.e. how many bits in your secret key are 1.

In general, you want to use a multiplication algorithm that never puts secret data into if-conditionals [1] or into array indices [2][3]. It is possible to efficiently do this, which I think is actually even more surprising than the fact that you can do the multiplication in sublinear time.

One such algorithm, though by no means the most efficient one, is as follows (a special case of [4], unless I screwed it up):

1. Compute x' = (x + 2^256 - 1)/2 mod the secp256k1 curve order. The bits of this number have a special property: if you interpret all the 0's as -1's, they also represent the original secret key x. See [5], top of page 9.
2. Compute G, -G, 2G, -2G, 4G, -4G, ..., 2^256G, -2^256G and put them in an array P.
3. Compute the sum of { x_i'*P[2*i + 1] + (1 - x_i')*P[2*i] } over each bit x'_i of x'.

[1] "Don't branch on secret data" is folklore, I don't have a citation for it.
[2] https://cryptojedi.org/peter/data/chesrump-20130822.pdf
[3] http://www.tau.ac.il/~tromer/papers/cache.pdf
[4] https://github.com/bitcoin-core/secp256k1/pull/546
[5] https://eprint.iacr.org/2012/309.pdf
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!