Pages:
Author

Topic: For the super paranoid: How do I get the public key from a private key by hand? (Read 4695 times)

sr. member
Activity: 378
Merit: 250

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.
legendary
Activity: 1106
Merit: 1005

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.
full member
Activity: 179
Merit: 151
-
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 Smiley.
sr. member
Activity: 467
Merit: 267
It's faster in wNAF and using Jacobian coordinates rather than Cartesian. Still nuts though...
legendary
Activity: 1176
Merit: 1020
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.
full member
Activity: 156
Merit: 100
I'm an artist, my paint is code
Isn't this the reason why there are bitcoin hardware wallets?
legendary
Activity: 3472
Merit: 4801
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.
full member
Activity: 179
Merit: 151
-
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



sr. member
Activity: 338
Merit: 253
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.
legendary
Activity: 3416
Merit: 1912
The Concierge of Crypto
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.
legendary
Activity: 3878
Merit: 1193
full member
Activity: 170
Merit: 101
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:)
legendary
Activity: 1232
Merit: 1030
give me your cryptos
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.
legendary
Activity: 3416
Merit: 1912
The Concierge of Crypto
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.
full member
Activity: 170
Merit: 101
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.
legendary
Activity: 966
Merit: 1042
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)
legendary
Activity: 3416
Merit: 1912
The Concierge of Crypto
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.
legendary
Activity: 1232
Merit: 1094
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.
VTC
member
Activity: 84
Merit: 14
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
legendary
Activity: 938
Merit: 1002
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.
Pages:
Jump to: