11

I am interested in generating a Bitcoin address by hand for security's sake. After I choose/generate a private key, how do I generate the public key?

From there, how would I double check my work?

Essentially, I am interested in not exposing my private key to any hardware, including my own.

Please feel free to give technical answers, if necessary. Thank you for reading thus far!

3
  • 1
    I guess this might take a dauntingly large amount of time. Double checking might involve using the private key to create an ECDSA signature then using the public key to check the signature. Commented Jul 16, 2023 at 15:19
  • 4
    Just to give you an idea, I believe I've heard estimates that computing a public key from a private key by hand would take something like a month of full time work, if done by hand, with the help of books with precomputed tables. Commented Jul 16, 2023 at 16:15
  • Interesting question, but also consider doing the calculation on a small device like a Raspberry Pi or even smaller that doesn't have bluetooth or WiFi. Once the calculation is done, the device could be destroyed or stored with your paperwork for future use. Input can be done locally with a keyboard, and output could be to a LCD screen or a monitor. Mentioning because using only paper seems to be impossible.
    – JPhi1618
    Commented Jul 17, 2023 at 14:40

3 Answers 3

25

I've spent a fair bit of time thinking about this and can provide a fairly comprehensive answer about the state of the art. But unfortunately the TL;DR is that we don't know how to do this (yet) in fewer than many months of full-time tedious computation, where checking your work is a similar amount of time. Near the bottom of this post there is a bold paragraph with specific numbers, which have a lot of hand-waving in them but I think represent the right order of magnitude.

"Not exposing your private key to any hardware" is a fairly common and understandable goal. And there are some operations that (it turns out) are totally reasonable to do by hand. In particular, you can do Shamir Secret Sharing and compute certain checksums by hand. (See codex32 and BIP 93 for more information on these. See seedxor for a simpler approach that does not include checksumming. For random number generation there are a variety of "diceware" schemes for extracting data from dice rolls.)

Working with an 128-bit seed, in my experience it takes 5-10 minutes to do very simple operations (adding seeds together character-by-character, or multiplying them by fixed Lagrange multipliers during secret sharing) and 30-60 minutes to do more complex ones (computing or verifying BCH checksums).

However, what the above schemes all have in common is that they are able to break seed data down into a sequence of characters, and then do computations on them character-by-character. This means that the operations involve tediously repeating steps which are easy to describe and master, and easy to assist via lookup tables and paper computers.

codex32/bip93, by having a checksum, allows you to check all your by-hand work by filling in a "checksum worksheet" on your results. You can even zero in on the exact location of your mistakes doing this. (To check your work on the checksum worksheets themselves, you have to redo them.)

Okay. So if you are merely trying to store your seed and verify its integrity, this is "easy" and you can follow the links I provided to see how to do it. But there are two harder things that you want to do:

  1. Hash secret data, or otherwise "stretch" your base entropy to get multiple secret keys, a la BIP32.
  2. Given a secret key, derive a public key from it. (This is your specific question, so I apologize for giving such a general answer, but I think this extra context is helpful.) The jargon for this operation is an "EC mult", a term that I'll unpack a bit below.

For step 1, in 2014 Ken Shirrif famously started to compute a sha256 by hand and estimated that it would take him 1.5 days of continuous work to do the full double-sha256 needed for mining. It would be a comparable amount of work to do a BIP32 derivation. Fortunately, if all you want are HD keys, I think a chacha20-based approach could be devised which is would probably take around 4 hours. Though if you follow that link, you'll see there are lots of missing details here; this is just an extrapolation from some simpler computations, and since even 4 hours per key is pretty brutal, people want to find a better scheme before they put too much time into playing with this.

Unlike with secret sharing and related schemes, there isn't any checksum that will be preserved when doing sha2 or chacha20. So to check your work on this, you'll have to redo the entire computation.

For step 2, secret to public key derivation things get interesting. As you may or may not know, this single operation is sufficient to derive addresses (prior to Taproot, you would also need to compute at least one hash, but with Taproot you can pretty-much just use a key as an address) (plus a checksum, but it's a BCH code so you can use the bip93 process to compute that by hand). It's also sufficient to compute signatures (the hard part of producing a Taproot/Schnorr signature is an EC multiplication; there is also a field multiplication and field addition, but as we'll see, if you can do an EC mult, you've necessarily figured out how to do this).

So to answer your "how do I check my work when doing an EC mult" question, the answer is: you compute a signature with your derived public key. Signatures are public so you can use a computer to check it. You will also want to use a computer to compute the message hash[*]. In fact, Bitcoin Core does this when it derives addresses: it signs a dummy message with every key and verifies it, to make sure that nothing glitched in its key derivation logic.

Okay, so, what's involved in a secret key to public key derivation? Essentially, what you do is interpret your secret key as an integer $n$, take a special elliptic curve (EC) point called G, and compute n × G which is defined as G added to itself n times. And "added to" means the elliptic curve group operation which is a ratio of polynomials. These polynomials are in a field of order 2^256 - 2^32 - 977, so every addition and multiplication involves manipulating 256-bit numbers modulo a large prime.

Maaaaybe you could express an EC multiplication in a way that didn't look like a series of polynomials over this field. But if you discovered such a thing I suspect you'd have solved the discrete log problem, in which case this entire discussion is moot. So I'll assume for the rest of this answer that we're stuck in the "polynomials in a finite field" paradigm. I'll further assume that division in a finite field will be very slow, at least ten times as slow as multiplication, in which case you want to represent your points in "Jacobian coordinates", which is a special coordinate system in which your points are represented by 3 numbers rather than 2, and where you can always replace divisions by (a couple of) multiplications. I don't have a good citation for Jacobian coordinates; they are not the same as "Jacobi coordinates" that Google will find for you. As far as I'm aware, they're used heavily in the field of computing elliptic curve math, and pretty-much unused everywhere else.

This is the same paradigm as electronic computers have to work in, so we actually know how to do the minimum number of field operations for each EC group operation. The answer is 6-16 field multiplications, depending on how "compatible" the points you're combining are (whether their third coordinates match (good), or are one (better)).

Putting this all together, there are three main strategies for efficiently doing EC mults:

  1. Reducing the number of group operations (EC additions) you have to do.
  2. Reducing the number of field operations (addition/multiplication modulo a prime) you have to do, per group operation.
  3. Doing the field operations faster.

For step 1, again assuming no discrete-log-breaking levels of novel math, the only way to reduce the number of group operations is to introduce lookup tables. When computing $G$ plus itself $n$ times, obviously we're not going to actually do $n$-many additions. That would be ~2^255 additions. Instead, we would represent $n$ is base-16, say, so that we have a simpler equation that looks like

n_0 + n_1×(2^4)G + n_2×(2^8)G + n_3×(2^12)G + ... + n_63×(2^252)G

For each term there are only 16 possibilties; these don't overlap so you'll be adding from a set of size 16×64 = 1024. So if you had a lookup table with 1024 entries, you could do this in 64 multiplications. Rather than using base 16, you might use base 1024; then you'd have to do 26 additions from a lookup table of size 26×1024 = 26624.

I was able to fit 18 per page in my "table of discrete logarithms", which I put together in 2018 or so, then thinking it was a joke; I wasted a lot of space, but you can tell that it'd be hard to readably get more than 64 on a page, as a simple estimate. So let's say 64 per page. Then 26624 entries is a 416-page tome. There are diminishing returns to trying to go further and I think this line of analysis is pretty much complete.

For step 2, reducing the number of field operations, we observe from the EFD page I linked above that we can reduce the number of operations we have to do by choosing the points that we're adding carefully. Since even addition will have one point from the lookup table, we can make sure that all the points in the lookup table have z=1; if we need to work in Fourier space or in Montgomery form, we can also do those conversions in the lookup table rather than making the user do them by hand[**]. Just with z=1 we can reduce every EC operation to 11 multiplications.

Peter Dettman has a scheme called "effective affine" which could be used to treat other points as having z=1 even if they don't, but it's not obviously applicable to this.

Step 3 has the most room for exploration in my view, because here is where the hand-computation story really diverges from the electronic-computation story, and we can no longer depend on existing research to get turnkey best-in-class algorithms.

Let's start working things out in detail. We'll assume that we're working in base-32 and that our field elements consist of 52 bech32 "digits" in this base. The benefit of working in this base is that we can do digit multiplication and addition using 1024-element volvelles which are a particularly error-resistant form of lookup table. If we used a lower base, we'd be doing extra work, and with a higher base, the volvelles would be too big. Though maybe there is room to fudge this.

Addition modulo a 256-bit prime will involve 52 digit additions, then another 52 to reduce. Because additions for computers are basically free, I don't have easy-at-hand estimates for the number of additions we have to do per point, but let's say 10 as a swag. So 1040 operations.

We then have to do 11 field multiplications. Naively multiplying two 52-digit numbers involves 2704 digit operations. But with Karatsuba multiplication we can reduce this to around 1500 (if I'm remembering right). With Fourier transform techniques we could reduce this to more-like 52 operations, but every few multiplications we'd need to move out of Fourier space, an operation which costs 10000s of digit operations. I don't have a good estimate of how often you have to do this; it could be anywhere from "you have to do it so frequently this is useless" to "so infrequently that this is a massive win".

Unfortunately these algorithms are for integer multiplication, and we want to do modular multiplication. Naively this would be horrible and involve Euclid's algorithm and dozens of digit divisions and stuff. But non-naively we can use Montgomery multiplication to do this, which roughly adds the overhead of multiplying each digit by a fixed precomputed factor. The digits in the precomp table we could pre-multiply so this is free. For the other digits, we'll also assume this is free, because multiplication by a fixed constant can be done very cheaply using lookup tables, and I haven't yet thought through the details.

A few people have explored combining Montgomery multiplication with Karatsuba-like techniques or even Fourier techniques. Unfortunately the Karatsuba stuff turns out not to be worth the overhead until you get to numbers a fair bit bigger than 256 bits, and the Fourier stuff not til you're way bigger. So the literature on this is few and far between and is written in weird jargon for weird specific applications like digital signal processing chips, or 1950s-era computers, or whatever. I can feel in my bones that there's some really big result ("big" for people trying to do bitcoin wallets by hand) in here but the limiting agent here is deep study time. I would encourage anyone reading this to get their hands dirty and to open a discussion on the codex32 github repo if they're making progress. There are other more speculative ideas (e.g. using residue number systems and then representing entries in the lookup table as their residue modulo various small primes .... if we could then do multiplication/division modulo small primes, then suddenly digit division becomes just as cheap as digit multiplication, which opens up new avenues) that I haven't seen in the literature but may lead somewhere useful.

Putting this all together, here is where we stand: with a 400-page lookup table, assuming no overhead (keeping track of carries, copying data from line to line, etc) and assuming volvelles for every operation, we can do 26 group operations, totalling 286 field multiplications and 260 field additions, which break down into ~786k digit operations (naively) or ~440k (assuming some Karatsuba-like stuff works). Let's say we can do 5 digit operations per minute. Then even after all this hand-waving we are still looking at 2622 hours of work naively or 1475 hours. At a 40 hour/week this is 65 weeks naively or 36 weeks with the tricks that we're fairly confident about.

In my view, if we could reduce this to one month (160 hours of work) (plus another 160 to verify a signature, if you're doing this to derive addresses), I think this would be a reasonable thing to do for a certain kind of super-paranoid Bitcoin user who only transacted every several years. Perhaps you could operate a cold wallet this way, and teach your children and grandchildren to do it, and over the centuries it wouldn't add up to too much trouble. I'm also skeptical that we could do better than this, given that it's already ~16x faster than what we currently know how to do. Though given the magnitude of the unknowns here, I wouldn't be shocked if we could.

However, in my view, no matter how crazy paranoid you are, this is not realistic with current techniques, even for a very-long-term cold wallet.

[*] If you're super serious about avoiding trust in electronic computers, you may be upset about signing hashes that a computer makes for you. After all, the computer could lie about what the hash is, thereby tricking you into signing a transaction you don't intend to. To deal with this, I would advise asking multiple computers to make the same hash, and maybe even do it on a TI-84 or a Gameboy or something which long predates Bitcoin. You could compute the hashes by hand but this is many tens of hours of work.

[**] Maybe you are worried that the computations done in the lookup table may be wrong or compromised. Well, unless you are willing to make your own lookup table tome, which will take you many decades doing monk-like work in a secret location, you will need to live with this. There's more I could say about this but I am trying to keep this answer focused.

6
  • 1
    Would it be possible to use trust-minimized hardware (like calculators I suppose) to speed up the process? Commented Jul 17, 2023 at 17:00
  • 5
    Clearly the only practical solution is to build a hand-cranked mechanical computer out of Lego and then turn the crank for a few hours until it it's done computing the public key :) Commented Jul 17, 2023 at 18:08
  • 1
    @SonKaos999 yes, certainly. One "obvious" approach is to use a TI-83 or a Gameboy or even an old Thinkpad, where you can do arbitrary computations and the supply chain story makes you comfortable that the device isn't backdoored in a bitcoin-relevant way. But the more interesting thing would be to somehow build a transparently-operating machine, like one with few gears that are all visible....but this would require a more mechanical brain than mine to figure out! Using Lego Technic, or Knex, or something, is not a bad thought ;) Commented Jul 17, 2023 at 18:54
  • The "compute a signature with your derived public key" part is impossible. The private key is required for that. And if the goal is to never expose it, computing the signature must be done by hand, and will require comparably as much work as computing the public key in the first place.
    – fgrieu
    Commented Jul 17, 2023 at 19:38
  • 1
    @SonKaos999 you would need to do the encryption by hand though, and I'm not aware of any FHE schemes where that's easier than just doing the ecmult. Commented Jul 18, 2023 at 13:49
0

I’m one of the folks that’s interested in the Residue Number System angle of attack here. RNS already has a long history of helping making cryptographic functions more efficient for computers, just search “RNS CRYPTOGRAPHY” on google scholar. The reason why they are so attractive both for computers and for humans to handle large arithmetic operations is that they completely dispense with carrying operations.

What this means in practice is that each “digit column” of your operation may be done entirely in parallel. RNS works based of something called the Chinese Remainder Theorem, which proves that if you take any set of coprime integers (integers that share no common factors other than the 1), which we’ll call our “Moduli Set”, then every integer between 1 and the product of our Moduli Set has a unique representation by its set of remainders after being divided by each of our Moduli Set.

Example:

Moduli Set = 2,3,5 product = 30

1 = 1,1,1

2 = 0,2,2

3 = 1,0,3

4 = 0,1,4

5 = 1,2,0

30 = 0,0,0

31 = 1,1,1

You can see here in that example that we can only get up to 30 (2x3x5) before we start to “overflow” our RNS, however for a lot of cryptographic operations we don’t care about these overflows, as they actually serve as a natural method of obfuscating information. If you’re familiar with modular / finite field arithmetic, which is essentially universal in modern cryptographic systems, this is just an example of that.

The difference is that by representing our numbers in an RNS we don’t actually need to bother with doing arithmetic mod 30, we only need to bother with doing it mod 2,3 and 5. (Generally with RNS you want to use “Primorial Numbers”, ie the product of the first n primes, just because that will end up giving you the smallest coprime integers).

As previously stated what makes RNS so cool is that there is no carrying, you only need to do your arithmetic per digit column:

17 = 1,2,2

x 9 = 1,0,4

———————————

153 = 1,0,3

2s column: 1x1=1

3s column: 2x0=0

5s column: 2x4=8=3

For a computer this means they can do these operations in a highly parallel fashion which makes computers happy and for humans it means that we have to deal with MUCH smaller finite fields within which we need to do maths which makes us happy. Going from having to work mod 30 vs mod 5 might not seem like that big a difference. But how about 193 vs 2^256? If we were to build a 2^256 sized RNS then 193 would be the biggest number we’d have to work with.

This is just a high level overview of RNS and why I’m stoked on it potentially leading to hand crypto, but as Andrew mentioned it’s highly speculative whether or not a bridge can be built into the specific applications we are looking for here. If you’re interested there’s a couple papers in particular that initially got me to think that this might be feasible:

http://journals.theired.org/journals/paper/details/5008.html

https://arxiv.org/abs/1801.07561

In the end with this stuff I think you’d still want some kind of slide rule-y type gadget to help you, and if we really want to do this stuff right it probably means we need to invent entirely new cryptography under these human constraints, which is also something I spend a fair amount of time thinking about.

6
  • Good observation that the ability to dispense with carrying is the most useful thing here. Carrying takes extra worksheet space and nearly doubles the amount of operations you need to do, and disproportionately increases the likelihood of errors. I believe you could make a usable 192-position slide wheel, which is what you'd need for multiplication mod 193. I have a 365-position wheel for other purposes and that is too dense to assemble precisely, but 192 looks fine. Commented Jul 17, 2023 at 13:01
  • 1
    @fgrieu-onstrike I haven't parsed out the analysis in the second citation, but the first suggests that with single-layer RNS the cost is roughly 2k^2 (end of sections 4.1 and 4.2). If we use 40 primes (say, 17 through 199) this is 3200 digit operations. Same order of magnitude as the estimates in my answer (1504, plus carries, plus Montgomery operations which I think actually 2x the number of digit ops). I would expect recursive RNS to make this a bit worse but reduce errors by using smaller moduli. So, yes, a "high price", but I think it's actually worth it. Commented Jul 17, 2023 at 22:19
  • 1
    The first paper does not look encouraging to me. Issues: the experimental results are for multiplication without modular reduction, when modular reduction dominates the cost of secp256k1 operations. Table 3 shows recursive RSN (being studied) more than doubles the area compared to RSN or textbook method. Also, the first paragraph of the "Experimental results" section and other editorial blunders show that there was no working review process. Combined with sketchy description of the design and a complete lack of a description of how it was validated, my confidence index stands low.
    – fgrieu
    Commented Jul 18, 2023 at 5:36
  • 1
    @fgrieu-onstrike oops, we are talking about different papers. I am reading "A Full RNS Implementation of RSA" which Sam did not directly cite, but which more-or-less spawned all the other RNS papers, so is widely cited. In particular it is citation [7] of Sam's second paper. That is where I got the 2k^2 estimate (and my optimism). I agree that Sam's first paper looks sloppy, though it looks like it may provide useful intuition for other recursive-RNS results. Commented Jul 18, 2023 at 13:57
  • 1
    @Andrew Poelstra: ah, I don't have similar reservation on first skimming about that other paper. And now I understand your comment. It looks like we need the product of the primes to exceed (k+2)^2 N where N is the 256-bit p in secp256k1, and we need two disjoints sets of such primes, thus we'll need primes slightly larger than what you quote, but that's still the right ballpark (at most 3 decimal digits) for k=40. RNS indeed seems worth studying in the context. Duno for recursive RNS.
    – fgrieu
    Commented Jul 18, 2023 at 14:38
0

I love the answer by Andrew

It isn’t by hand on a piece of paper, but a spreadsheet with all the calculations visible (no macros or array formulas) that can perform the ECDSA secp256k1 formula for bitcoin’s public key and another set of spreadsheets for other steps (e.g. RIPEMD160 and SHA256, again no array or macros) can deliver a functional public address, and cuts the time down to under an hour to manually convert from a private key to a public key. I built some in excel and you can find the spreadsheets at modulo.network

I suppose could follow the spreadsheet(s) tabs by hand and arrive at the public address but there are over 180 tabs with long division (and I mean long!) that would become tedious. Hence why I like Andrew’s answer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.