Bitcoin Forum
May 21, 2019, 06:09:59 AM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1] 2 »  All
  Print  
Author Topic: For the super paranoid: How do I get the public key from a private key by hand?  (Read 4529 times)
TheKing01
Newbie
*
Offline Offline

Activity: 12
Merit: 0


View Profile
July 01, 2016, 11:46:51 PM
 #1

Okay, so let's say I have flipped a fair coin (on which I've done extensive statistical analysis on (doing the statistics by hand)) 256 times and now have a private key. How would one go about calculating the public key by hand? This way the private key has only gone through one brain, an organic one.

I'm okay with using things like paper and pencil, and even an abacus, but nothing that uses electricity. (Mechanical computers of sufficient complexity should also be avoided. The human mind should be doing the brunt of the work.)

(P.S. If you are actually interested in creating private keys by hand, I would recommend shuffling a deck. A randomly shuffled deck has about 225 bits of entropy. (See en.wikipedia.org/wiki/Shuffling#Research and other sources for random shuffling.) If you want all 256 bits, shuffle the deck again and draw 6 cards. Although you could convert this to a number using a mixed radix method (en.wikipedia.org/wiki/Mixed_radix), its easier to type in the deck and hash it. The advantage of the deck method as opposed to computer based methods is you don't have to worry as much about your entropy source being compromised (its only likely that the NSA has tampered with the thickness or amount of friction between the cards.))
1558418999
Hero Member
*
Offline Offline

Posts: 1558418999

View Profile Personal Message (Offline)

Ignore
1558418999
Reply with quote  #2

1558418999
Report to moderator
1558418999
Hero Member
*
Offline Offline

Posts: 1558418999

View Profile Personal Message (Offline)

Ignore
1558418999
Reply with quote  #2

1558418999
Report to moderator
1558418999
Hero Member
*
Offline Offline

Posts: 1558418999

View Profile Personal Message (Offline)

Ignore
1558418999
Reply with quote  #2

1558418999
Report to moderator
NEW GAME FORMAT
JACKPOT UP TO $8000+
Guess The Symbols Of a Real Ethereum Hash
PLAY NOW
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1558418999
Hero Member
*
Offline Offline

Posts: 1558418999

View Profile Personal Message (Offline)

Ignore
1558418999
Reply with quote  #2

1558418999
Report to moderator
1558418999
Hero Member
*
Offline Offline

Posts: 1558418999

View Profile Personal Message (Offline)

Ignore
1558418999
Reply with quote  #2

1558418999
Report to moderator
1558418999
Hero Member
*
Offline Offline

Posts: 1558418999

View Profile Personal Message (Offline)

Ignore
1558418999
Reply with quote  #2

1558418999
Report to moderator
unamis76
Legendary
*
Offline Offline

Activity: 1414
Merit: 1000


View Profile
July 01, 2016, 11:51:10 PM
 #2

Not sure if I can really help you, but you can start here
theymos
Administrator
Legendary
*
Offline Offline

Activity: 3388
Merit: 5531


View Profile
July 02, 2016, 03:06:15 AM
Last edit: July 02, 2016, 03:38:54 AM by theymos
 #3

If the private key is d, then the public key is d * G, where G is a specific point on the elliptic curve (everyone uses the same G), and * is not normal multiplication, but elliptic curve multiplication.

There's a good guide on elliptic curve math here:
http://www.johannes-bauer.com/compsci/ecc/
Your main goal will be to do "scalar point multiplication", which is what d*G is. To do that you'll need to do elliptic curve addition & doubling. And all math must be done using modular arithmetic, also explained on that page. It's actually fairly simple, but when dealing with Bitcoin's huge 256-bit numbers, it'll take a very long time.

Bitcoin's values for the constants G (the generator point needed for getting a public key point from a private key number), a, b (used to define the curve itself), and p (the modulus used for modular arithmetic) are listed here:
https://en.bitcoin.it/wiki/Secp256k1
There G is encoded in a standard way; what it means is that G is the point (79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798, 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8).

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
TheKing01
Newbie
*
Offline Offline

Activity: 12
Merit: 0


View Profile
July 02, 2016, 02:31:26 PM
 #4

I wonder if it would be possible to draw a giant elliptic curve and do it that way. Elliptic curves probably aren't geometrical for finite fields though.
vetpet
Member
**
Offline Offline

Activity: 84
Merit: 10


View Profile
July 02, 2016, 04:08:42 PM
 #5

It is enough to "generate" private key on the paper. Obtain bitcoin address is too difficult without computer.
johoe
Full Member
***
Offline Offline

Activity: 217
Merit: 141


View Profile
July 02, 2016, 08:42:08 PM
 #6

Computing the public key d*G from the private key d needs a lot of computations.  It takes about 1000 multiplications of 77 digit numbers.  Not something you can easily do with pen and paper.

Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3
Monnt
Legendary
*
Offline Offline

Activity: 938
Merit: 1000


View Profile
July 03, 2016, 05:03:04 AM
 #7

Technically it is possible. Logical? No way! Maybe you can, using a calculator, but not with pen and paper unless you want to run through 3 pens and a hundred bucks if paper. As the guy above me said, it'll take more than a thousand multiplications.
VTC
Member
**
Offline Offline

Activity: 77
Merit: 14



View Profile
July 03, 2016, 06:22:46 PM
 #8

If it takes too much time to compute the public key at least you can do some mining:

Mining Bitcoin with pencil and paper: 0.67 hashes per day
http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html
https://www.youtube.com/watch?v=y3dqhixzGVo
TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1002


View Profile
July 04, 2016, 09:47:29 AM
 #9

What is the actual objective here?  You want to make sure that your private key is never written to any computer?

If the funds being stored at the address are that important, they are probably not worth risking to a public key like that.

At minimum, you should have some kind of CRC-like check.

To get the money out, you need to sign the transaction resulting manually too.  Armory (or similar) could be used to generate the transaction.  I assume it can import a "watching-only" public key.

For the CRC-like check, you could take two 256-bit random numbers, a and b (chosen by dice roll or coin toss).

Compute your public key, P = a*G.   Then compute the check value, C = P + (b * G).

If you have done everything correctly, then

C = P + (b * G)
C = a * G + b * G
C = (a + b) * G

You can manually compute (a + b) and then use a computer to compute (a + b) * G and make sure it matches your C value.  If it does, then P is probably correct.  As long as b is random, I don't think this leaks any info about your private key.

This means that a is your private key and P is your public key and you should destroy b.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
Dabs
Staff
Legendary
*
Offline Offline

Activity: 2324
Merit: 1140



View Profile
July 04, 2016, 03:26:45 PM
 #10

If you are super paranoid, will the following work for you?

1. Set up large faraday cage, only electricity goes in. No electricity if running on battery. No sounds. No wifi. No radio. Alternatively, a really noisy place.
2. Use an old laptop or tablet to do the calculation offline. Tails / Live-CD
3. Write the results by hand / print.
4. Destroy devices.

I would just skip the last one since I know how to effectively wipe computers.

Finally, I would use casino grade dice, not shuffled playing cards or flipped coins.

You could also use any camera and take pictures, then SHA256 the jpegs / raw.

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
cpfreeplz
Legendary
*
Offline Offline

Activity: 966
Merit: 1036


View Profile
July 06, 2016, 01:13:10 AM
 #11

I must say, this is the coolest thread I've seen in a long time. It's obviously not practical/logical but this is really cool even to just say that you've done it (or know how haha)
Ned Kelly
Full Member
***
Offline Offline

Activity: 167
Merit: 100


View Profile
July 07, 2016, 11:18:33 AM
 #12

Finally, I would use casino grade dice, not shuffled playing cards or flipped coins.

Is it a source of randomness? If yes, is it good enough? Maybe, use a scintillator or Geiger tube.
Dabs
Staff
Legendary
*
Offline Offline

Activity: 2324
Merit: 1140



View Profile
July 07, 2016, 03:31:47 PM
 #13

Finally, I would use casino grade dice, not shuffled playing cards or flipped coins.

Is it a source of randomness? If yes, is it good enough? Maybe, use a scintillator or Geiger tube.





I think these are the type you want, but really, even cheap game board dice will do. Roll it a hundred times for 256 bits.

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
Decoded
Legendary
*
Offline Offline

Activity: 1218
Merit: 1024


give me your cryptos


View Profile
July 08, 2016, 11:21:46 AM
 #14

Finally, I would use casino grade dice, not shuffled playing cards or flipped coins.

Is it a source of randomness? If yes, is it good enough? Maybe, use a scintillator or Geiger tube.





I think these are the type you want, but really, even cheap game board dice will do. Roll it a hundred times for 256 bits.

The dots and the plastic would be made of different materials meaning they have a different mass. This would mean the dots would make an effect on the weight (however small). But the engravings on the dice could cause it to be lighter on that face. Even throwing the die with a certain face up gives a higher chance of landing on the same face twice, especially if thrown by the same person.

Nothing is completely random.

WTS 27/100 funded bitpiece, dm me offers

Also looking for a signature campaign, dm me for that too
Ned Kelly
Full Member
***
Offline Offline

Activity: 167
Merit: 100


View Profile
July 08, 2016, 04:28:25 PM
 #15

The dots and the plastic would be made of different materials meaning they have a different mass. This would mean the dots would make an effect on the weight (however small). But the engravings on the dice could cause it to be lighter on that face. Even throwing the die with a certain face up gives a higher chance of landing on the same face twice, especially if thrown by the same person.

Nothing is completely random.

This is the good point.

Also Dabs idea about taking images with camera can be useful, if take it a step further.
We can take optical microscope, drop of water, pollen and conduct a Brown's experiment, film it, take hash from a file.
Should be better than a die:)
Syke
Legendary
*
Offline Offline

Activity: 2968
Merit: 1030


View Profile
July 08, 2016, 05:30:23 PM
 #16

Nothing is completely random.

Radioactive decay is.

Buy & Hold
Dabs
Staff
Legendary
*
Offline Offline

Activity: 2324
Merit: 1140



View Profile
July 09, 2016, 03:33:37 AM
 #17

If you use the dice the way it was designed, using a craps table and making it bounce across the other side, you can not reliably predict the result. It will be random for all intents and purposes. The house wins because of the house edge; not due to crooked dice.

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
Blinken
Sr. Member
****
Offline Offline

Activity: 337
Merit: 250



View Profile
July 13, 2016, 07:35:43 PM
 #18

It would take many days of work to do this by hand and if you made a single error then the public key would be wrong.

Bitcoin ♦♦♦ Trust in Mathematics, Not Bankers ♦♦♦
andytoshi
Full Member
***
Offline Offline

Activity: 174
Merit: 131

-


View Profile
July 15, 2016, 01:19:43 PM
Last edit: July 15, 2016, 03:33:51 PM by andytoshi
Merited by theymos (20), ETFbitcoin (1)
 #19

How much precomputation are you willing to do? Is it OK to use a computer for this? Note that you can verify this multiple ways (by patching some quick-and-dirty code into libsecp, and using sage are my go-tos) and that the precomputation will have nothing to do with your secret key at all, so you can also ask outside parties to verify.

Depending on your answer, this might not be too crazy, and you could do it in less than a day per pubkey. Here's one scheme:

0. As others have mentioned, the public key is derived from the secret key by means of x → x*G, where x, your secret key, is a 256-bit number, G is a standard generator of the secp256k1 elliptic curve, and * means repeated addition of G to itself by the elliptic curve group addition formula.

0a. The formula can be found on Wikipedia and here. I recommend you understand the wikipedia formula algebraically, then go to that link to find more computationally efficient schemes. In particular you'll want to use a coordinate system that lets you avoid doing any modular inversion, because that's a bear to do by hand. (You will eventually need to do this, because the final form needs to be in affine coordinates, but you can put it off to the end instead of doing it at every step.)

0b. The formulae that libsecp256k1 uses are in this Sage script, which if you run, will also check that they are actually algebraically equivalent to the cleaner formula found on wiki and elsewhere. libsecp's computational goals (avoid inversions, strongly prefer addition to multiplication) are similar enough to a human's goals that it's probably faster to just use these than to go researching better ones.

0c. The formulae for doubling and adding distinct points are different. You'll need to double to do the precomputation, but never afterward. So that will simplify your life a bit.

Ok, the actual scheme:

1. Take your secp256k1 generator G, and compute G, 2G, 3G, ..., 15G. Then compute each of these times 16, times 16^2, times ..., times 16^63. (This isn't as bad as it looks since each generation can be gotten from the last by multiplying by 16 again.) To multiply by 16, double 4 times. This is a total of 15×64 = 960 points you need to precompute. Now, I'm not in your head, but I really think your ghosts will allow you to do this using computers, since it's independent of your secret and you can do it multiple ways.

1a. I think it would be funny for the libsecp project to sell books with these precomputed tables, like the books of logarithms that sailors used to use. It's a quick job in sage and LaTeX, if I still think it's funny by the end of this post I'll make a PDF.

2. Now, take your secret key in hex-encoding. This is a base 16 encoding, something like x = a + b*16 + c*16^2 + ... and so on, where all of a, b, c, are between 0 and 15 inclusive. There will be 64 digits, some of which (four of them, on average) are zero. So you can write x*G = (a + b*16 + c*16^2 + ...)*G = a*G + b*16*G + c*16^2*G.

2a. Here's the cool part: the 0*G's you can ignore. Everything else that's multiplied by G in the above formula is in your precomputed table. So you'll have (at most) 64 points that you simply look up, and you have to add them together. 63 additions. To do this in 24 hours, you'd have to do each one in a bit under 23 minutes. This is plausible, but I couldn't do it.


By increasing the size of your precomputed table you can reduce the work from 64 points, but the table gets much bigger. (To halve your work, you roughly have to square the size of the table.) To add 32 points, you'd need 8160 precomputed points; for 16 points you'd need a bit over a million; for 8 it's 35 billion ... for 1 you'd need to write out literally every single point.)


Edit: Here, I have done the precomputation for you. You want page 38, base 16 digits. https://download.wpsoftware.net/bitcoin/todl.pdf



DannyHamilton
Legendary
*
Offline Offline

Activity: 2198
Merit: 1401



View Profile
July 16, 2016, 01:49:42 PM
 #20

Edit: Here, I have done the precomputation for you. You want page 38, base 16 digits. https://download.wpsoftware.net/bitcoin/todl.pdf

Thanks.

Saving a copy of this.

Don't know that I'll ever use it, but I like the idea.

Pages: [1] 2 »  All
  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!