Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: TheKing01 on July 01, 2016, 11:46:51 PM



Title: For the super paranoid: How do I get the public key from a private key by hand?
Post by: TheKing01 on July 01, 2016, 11:46:51 PM
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 (http://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 (http://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.))


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: unamis76 on July 01, 2016, 11:51:10 PM
Not sure if I can really help you, but you can start here (https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses)


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: theymos on July 02, 2016, 03:06:15 AM
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).


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: TheKing01 on July 02, 2016, 02:31:26 PM
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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: vetpet on July 02, 2016, 04:08:42 PM
It is enough to "generate" private key on the paper. Obtain bitcoin address is too difficult without computer.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: johoe on July 02, 2016, 08:42:08 PM
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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: Monnt on July 03, 2016, 05:03:04 AM
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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: VTC on July 03, 2016, 06:22:46 PM
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


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: TierNolan on July 04, 2016, 09:47:29 AM
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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: Dabs on July 04, 2016, 03:26:45 PM
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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: cpfreeplz on July 06, 2016, 01:13:10 AM
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)


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: Ned Kelly on July 07, 2016, 11:18:33 AM
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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: Dabs on July 07, 2016, 03:31:47 PM
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.

https://images-na.ssl-images-amazon.com/images/I/51a2x3OvEaL.jpg

https://images-na.ssl-images-amazon.com/images/I/61wx6Tm6cxL._SL1000_.jpg

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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: Decoded on July 08, 2016, 11:21:46 AM
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.

https://images-na.ssl-images-amazon.com/images/I/51a2x3OvEaL.jpg

https://images-na.ssl-images-amazon.com/images/I/61wx6Tm6cxL._SL1000_.jpg

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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: Ned Kelly on July 08, 2016, 04:28:25 PM
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:)


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: Syke on July 08, 2016, 05:30:23 PM
Nothing is completely random.

Radioactive decay is.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: Dabs on July 09, 2016, 03:33:37 AM
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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: Blinken on July 13, 2016, 07:35:43 PM
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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: andytoshi on July 15, 2016, 01:19:43 PM
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 (https://hyperelliptic.org/EFD/g1p/auto-shortw.html). 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 (https://github.com/bitcoin-core/secp256k1/blob/master/sage/secp256k1.sage), 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 1564 = 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





Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: DannyHamilton on July 16, 2016, 01:49:42 PM
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.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: jasonv75 on July 17, 2016, 05:21:31 AM
Isn't this the reason why there are bitcoin hardware wallets?


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: Cubic Earth on July 18, 2016, 07:31:22 AM
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.

If the day comes that you will ever need it, you are going to wish you had printed it out ahead of time.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: hhanh00 on July 18, 2016, 10:31:53 AM
It's faster in wNAF and using Jacobian coordinates rather than Cartesian. Still nuts though...


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: andytoshi on July 18, 2016, 02:55:04 PM
It's faster in wNAF and using Jacobian coordinates rather than Cartesian. Still nuts though...

Good idea, I might add some tables usable for wNAF.

And you can extend my coordinates to Jacobian by simply adding a third `1` coordinate to everything :).


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: zimmah on August 19, 2016, 12:16:48 AM

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.

the dots (pips) of die of that grade are usually the same material but just with a different color.

they have the exact same density.

the engraving though might be the only weak spot, and the way you throw them.


Title: Re: For the super paranoid: How do I get the public key from a private key by hand?
Post by: MyBTT on August 19, 2016, 03:23:24 AM

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.

the dots (pips) of die of that grade are usually the same material but just with a different color.

they have the exact same density.

the engraving though might be the only weak spot, and the way you throw them.

I've never gambled at a casino myself, but casino grade dice would probably have flat faces and not have engraved faces, due to this reason.