Prime number Bitcoin keypairs - How and why

[BTCW]

HOW

First, consider this Bitcoin key pair:

Code:

Private key compressed (wif):
L3ACAgUJquKbnuYUywUqJNo6QACyMZvMvtx7Gt7QrbsrMkBhCDwA

P2PKH Public Address (Legacy):
1HBK1zXfLLJw9GUidvnb5bBVt8GReDnXhj

At a first glance, they look random and nothing special at all. Let's however convert these base58 numbers to hexadecimal, and we get (note that I use only the compressed form):

Code:

Private key (hex):
b136fef8391b4956312a6df2f6dc99b7cf238982dbcfbcb629f4ed6d35671a77

Public Address hash160 (hex):
b175364aaea8ecb515c1779cd00b0c3ba157bb25

Still not impressed? Alright, let's convert them to decimal (ordinary) numbers, so that:

Code:

Private key (dec):
80156543676389067380819750297890580630517839339787739613967701593439506733687

Public Address hash160 (dec):
1013105283100545924034097521935085705519926065957

Decimal numbers are easier for us humans. Do you see it now? These numbers are prime! You can easily verify this by trying to factor the two numbers here, or with programs like Matlab or other programs that can handle large numbers.

These two are only divisible with themselves and 1. In other words, they are prime. How cool is that?


The code

It took me some time to figure out how to produce key pairs like this. Large number factorization is computationally heavy. The pseudo-code works like:

Code:

1. Generate a random 32-byte number

2. If it is prime, go to step 3 - if it is not prime, go back to step 1

3. We have a prime private key; from it, compute the compressed public address, and more specifically its hash160

4. If both the private key and hash160 are prime, we are done - if the hash160 is not a prime, go back to step 1

If anybody is interested, I have the complete code in Python3 with several speed optimizations. Do tell!

On a regular laptop and using CPU only, it takes about 2-10 seconds to produce what I call "a true prime Bitcoin key pair".


Example output

When executed, the script outputs the following

Code:

==== RESULTS ===================================================

Private Key (32-byte PRIME NUMBER in HEX):
b136fef8391b4956312a6df2f6dc99b7cf238982dbcfbcb629f4ed6d35671a77

Public Address (HASH160 - 20-byte PRIME NUMBER in HEX)
b175364aaea8ecb515c1779cd00b0c3ba157bb25

==== PRIVATE KEY AND PUBLIC ADDRESSES (COMPRESSED ONLY) ========

Private key (WIF):
L3ACAgUJquKbnuYUywUqJNo6QACyMZvMvtx7Gt7QrbsrMkBhCDwA

P2PKH Public Address (Legacy):
1HBK1zXfLLJw9GUidvnb5bBVt8GReDnXhj

P2WPKH-P2SH Public Address (Wrapped):
39PGSGyV2dokiPxBUnsLR1a8N2bE1Hv9h2

Segwit P2SH Public Address (Bech32):
bc1qk96nvj4w4rkt29wpw7wdqzcv8ws40we9pynp28

==== IMPORT IN ELECTRUM WITH ===================================

p2pkh:L3ACAgUJquKbnuYUywUqJNo6QACyMZvMvtx7Gt7QrbsrMkBhCDwA
p2wpkh-p2sh:L3ACAgUJquKbnuYUywUqJNo6QACyMZvMvtx7Gt7QrbsrMkBhCDwA
p2wpkh:L3ACAgUJquKbnuYUywUqJNo6QACyMZvMvtx7Gt7QrbsrMkBhCDwA

(For other wallets: Read the manual)

==== VERIFICATION ==============================================

Paranoid people should use independent and offline software to
confirm that 80156543676389067380819750297890580630517839339787739613967701593439506733687 and
1013105283100545924034097521935085705519926065957 are prime
numbers, and that they are equal to the hexadecimal numbers in
the first paragraph.

WHY

They say that "prime numbers are the atoms of math, and math is the language of the universe."

It is beautiful. It is satisfactory. It is nerdy.

After coming up with this, I use only perfect Bitcoin primes myself.

But does it have any actual use? I'd love your take on it.

Does it add value? (Primes cannot - by definition - be factorized, so no one could ever arrive at your private key by factorization and multiplication [if that's even a thing].)

Are primes handled "better" (whatever that means) when for example signing transactions, resulting in better byte economy for the blockchain?

Is this unsafe? (I think not, according to the prime number theorem (PNT) there should be about 6.54*10^74 primes - a huge number - in the range as defined by the secp256k1 with the ECDSA algorithm. In other words, of all possible private keys, approximately 0.056% are prime, but only a few of these correspond to public addresses whose hash160 happen to be prime too.)

What do you think?

[pooya87]

But does it have any actual use? I'd love your take on it.

No. In fact I would avoid any method that changes the way you come up with the random private key to something that is based on a modified and possibly biased entropy.

Does it add value? (Primes cannot - by definition - be factorized, so no one could ever arrive at your private key by factorization and multiplication [if that's even a thing].)

I don't think that's a thing. All the methods that solve ECDLP are working with the public key which I haven't seen be affected by whether or not the key is prime.

Are primes handled "better" (whatever that means) when for example signing transactions, resulting in better byte economy for the blockchain?

It won't affect anything in signatures unless you also brute force the ephemeral key for signing and use a custom one which would significantly decrease the security of the signature. It also doesn't change anything regarding size of the signature.

Is this unsafe? (I think not, according to the prime number theorem (PNT) there should be about 6.54*10^74 primes - a huge number - in the range as defined by the secp256k1 with the ECDSA algorithm. In other words, of all possible private keys, approximately 0.056% are prime, but only a few of these correspond to public addresses whose hash160 happen to be prime too.)

It is slightly less safe since the search space is being reduced. I have to study how prime-counting functions work more before I can say anymore.

[NotATether]

Does it add value? (Primes cannot - by definition - be factorized, so no one could ever arrive at your private key by factorization and multiplication [if that's even a thing].)

It doesn't because they primes are not multiplied together in ECC they are added to the generator point that many times which precludes trying to factorizate of a public key in the first place (you'll just get a bunch of meaningless factors that have traces of G and the private key in them).

Are primes handled "better" (whatever that means) when for example signing transactions, resulting in better byte economy for the blockchain?

I think you mean whether they can be computed the fastest, which the answer is no. The points which can be generated the quickest are powers of two by means of repeated point doubling.

Is this unsafe? (I think not, according to the prime number theorem (PNT) there should be about 6.54*10^74 primes - a huge number - in the range as defined by the secp256k1 with the ECDSA algorithm. In other words, of all possible private keys, approximately 0.056% are prime, but only a few of these correspond to public addresses whose hash160 happen to be prime too.)

It is slightly less safe since the search space is being reduced. I have to study how prime-counting functions work more before I can say anymore.

That's around 2^248.53, but it could be larger depending on how OP is generating them. That's because it is computationally impractical to test whether a number is exactly prime so instead people use algorithms that test if they are "probable primes" such as if (a^n-1 mod n) === 1 for some a between 1 and n, however although these tests pass for all prime numbers they also pass for a small proportion of composite numbers with huge factors.

[PrimeNumber7]

Is this unsafe? (I think not, according to the prime number theorem (PNT) there should be about 6.54*10^74 primes - a huge number - in the range as defined by the secp256k1 with the ECDSA algorithm. In other words, of all possible private keys, approximately 0.056% are prime, but only a few of these correspond to public addresses whose hash160 happen to be prime too.)

Yes. You are reducing the number of possible private keys. There is no benefit to doing this, but there is a reduction in security.

[BTCW]

Thanks for the feedback so far, all of you.

I would however still argue that since primality testing takes a lot more time than "test 'em all" (brainflayer stylee), using "perfect prime" Bitcoin key pair does have a real-life negative impact on safety.

As stated in the OP, there are approximately 6.54*10^74 primes within the private key-space. To calculate them all would take godzillions of years, and result in a list so large that it couldn't be stored in this universe.

Compare these two scenarios

1. Output random 32-byte numbers. Test all against known addresses on the blockchain. (Let's for the sake of discussion disregard the fact that such experiments have never yielded any success.)

2. Output random 32-bytes numbers. Test each for primality (time-consuming!). Discard all numbers that are not prime, and test only the remaining ones (the primes) against known addresses on the blockchain.

Scenario 1 is always going to be faster.

In other words, testing 1,000 private keys regardless of primality is always going to be faster than first sorting out the, according to PNT, approximately 145 primes, only to test these in a second step.

How about a field test?

I just sent 1 tBTC to

Code:

Public Address, Legacy, compressed (base58)
n2wPWMxUnmvS2RYtZ4MQpW68SNkRh7Q8iU

hash160 (hex)
eaf9abaeb1c1c4010f05fee3c1fc8acb097ec6ef

hash160 (dec)
1341471681573518193062054609505455185344881149679

Here is the transaction id.

You can verify for yourselves that the hash160 is prime. The private key for it is prime too. Can you break it and snatch the coins? I think not. Would be very surprised.

Please try!

[NotATether]

How about a field test?

I just sent 1 tBTC to

Code:

Public Address, Legacy, compressed (base58)
n2wPWMxUnmvS2RYtZ4MQpW68SNkRh7Q8iU

hash160 (hex)
eaf9abaeb1c1c4010f05fee3c1fc8acb097ec6ef

hash160 (dec)
1341471681573518193062054609505455185344881149679

Here is the transaction id.

You can verify for yourselves that the hash160 is prime. The private key for it is prime too. Can you break it and snatch the coins? I think not. Would be very surprised.

Please try!

Somebody can use the fact that the hash160 was the next random number generated after the private key and try to "rewind" the state of whatever random number generator you used (most likely Python/Windows because you said it's a laptop).

The RNG seed is obviously unknown but someone can potentially work backwards from whatever algorithm it's using to find the private key.

[KingZee]

Thanks for the tip, now I'm gonna run a program that iterates through all prime numbers up to infinity and scoop up all your sats 

[BTCW]

How about a field test?

I just sent 1 tBTC to

Code:

Public Address, Legacy, compressed (base58)
n2wPWMxUnmvS2RYtZ4MQpW68SNkRh7Q8iU

hash160 (hex)
eaf9abaeb1c1c4010f05fee3c1fc8acb097ec6ef

hash160 (dec)
1341471681573518193062054609505455185344881149679

Here is the transaction id.

You can verify for yourselves that the hash160 is prime. The private key for it is prime too. Can you break it and snatch the coins? I think not. Would be very surprised.

Please try!

Somebody can use the fact that the hash160 was the next random number generated after the private key and try to "rewind" the state of whatever random number generator you used (most likely Python/Windows because you said it's a laptop).

The RNG seed is obviously unknown but someone can potentially work backwards from whatever algorithm it's using to find the private key.

Regardless of my OS, good luck "rewinding"

Code:

openssl rand -hex 32

iterated until reaching a prime, to give the private key (not shown). From which the public address, whose hash160 is prime too, is derived.

The blockchain says I still control it. Leaving it there for a while

[BTCW]

So. if private key is prime, so address would be prime too?

Nope, there is no causality for primality between the private key and the public address (expressed as hash160).

Both elliptic curve cryptography and hashing (SHA256 and RIPEMD160) in between, so it's a trial and error process.

[NotATether]

Regardless of my OS, good luck "rewinding"

Code:

openssl rand -hex 32

iterated until reaching a prime, to give the private key (not shown). From which the public address, whose hash160 is prime too, is derived.

So Linux/Python. 

The fact that you used OpenSSL is even better because it just uses the MD5 hash of the entropy as the random number function.

[pooya87]

Regardless of my OS, good luck "rewinding"
iterated until reaching a prime, to give the private key (not shown). From which the public address, whose hash160 is prime too, is derived.

My knowledge in this topic is limited but the method to generate primes is not "iterate through numbers then check primality". Instead there are more efficient methods designed to quickly find prime numbers with a lot less effort. https://en.wikipedia.org/wiki/Generation_of_primes
There is even a challenge to find the next "biggest" prime number to set a new record which is currently at 2^82589933−1 (a number which has 24,862,048 digits in base 10). In comparison 2²⁵⁶ has 78 digits!

P.S. The problem with your "challenge" is that there is no reward involved since testnet coins have no value. So it can't prove anything.

[BTCW]

Regardless of my OS, good luck "rewinding"
iterated until reaching a prime, to give the private key (not shown). From which the public address, whose hash160 is prime too, is derived.

My knowledge in this topic is limited but the method to generate primes is not "iterate through numbers then check primality". Instead there are more efficient methods designed to quickly find prime numbers with a lot less effort. https://en.wikipedia.org/wiki/Generation_of_primes
There is even a challenge to find the next "biggest" prime number to set a new record which is currently at 2^82589933−1 (a number which has 24,862,048 digits in base 10). In comparison 2²⁵⁶ has 78 digits!

P.S. The problem with your "challenge" is that there is no reward involved since testnet coins have no value. So it can't prove anything.

You refer to so-called Mersenne primes, which indeed can be written like 2ⁿ-1, where n is a positive integer (but not any positive integer). Fun fact: in base 2, all Mersenne primes are a (long) series of 1's.

In the strange game of finding very, very large primes, plugging in very large values for n in the Mersenne formula and testing for primality - in that order - is the way forward. Far from all primes are Mersenne, though.

In order to generate primes that are "only" 1-78 digits long (in base 10), you create a pseudorandom number and check it for primality. This is quicker than any other method. There is no known general formula for primes. Rather, a prime is a number that satisfies a certain set of criteria. (Why the number 1 is not prime is an interesting story in itself, if you like math.)

Also, this wasn't meant as a challenge, or a bounty, or the like. And, I am a little confused regarding testcoins - isn't this what they are for? Playing around with.

Further, I don't get why my OS is of interest here. My little script is Python 3, sure, but it runs equally well on Windows, Ubuntu, and macOS. These are the three I have tested it on. I am by no means a professional coder, but I don't like Python code that is "locked" to a certain OS.

RNG is very interesting, no doubt, but beside the point. OpenSSL is a nice library to create pseudorandom numbers, but there are other cryptographically sound methods and libraries too. The RNG in Bitcoin Core isn't fancier than this, and it is clearly good enough.

I thought it would be fun to see if I could come up with a method to create "perfect prime" Bitcoin key pairs, which - according to my own definition - means both the private key and public address (stripped of its script and presented as its hash160) are prime.

Nothing more. Just playing with math and applying it to Bitcoin.

If someone wants to take a look at my script, I can share it. The interest seems limited, and I'm totally cool with that.

All of this is just a result of my private fascination with primes and cryptography. The in my opinion utterly absurd story of illegal primes led me into this.

That's all

Edit/addition: SSL-certificates (based on RSA) for webpages and PGP keys for encrypted email are "only" large primes (this is borderline overly simplified). The magic of asymmetric encryption is a secret component, which is a very large prime, and a public component. Bitcoin uses ECC instead of RSA, so I figured I'd try something with primes and Bitcoin - a recombination of different cryptographic methods experiment.

[NotATether]

Further, I don't get why my OS is of interest here. My little script is Python 3, sure, but it runs equally well on Windows, Ubuntu, and macOS. These are the three I have tested it on. I am by no means a professional coder, but I don't like Python code that is "locked" to a certain OS.

It's no longer important now that we know the primes were generated from OpenSSL.

If someone wants to take a look at my script, I can share it. The interest seems limited, and I'm totally cool with that.

I'm interested.

All of this is just a result of my private fascination with primes and cryptography. The in my opinion utterly absurd story of illegal primes led me into this.

Absurd indeed. Reminds me of the time Sony was trying to use legislation to stop people from posting a short hex sequence that can decrypt the DRM on their music CDs. Then people posted it all over slashdot lmao.

[archyone]

HOW


If anybody is interested, I have the complete code in Python3 with several speed optimizations. Do tell!

I would like to take a quick look at it, I admit, more out of curiosity than anything else. For the moment, apart from reducing the number of possibilities I do not see too much interest, I could be wrong of course.

[dex1]

It is beautiful. It is satisfactory. It is nerdy.

You may well be living a "beautiful", "satisfactory" and "nerdy" life to the full extent thinking
you're the only proud owner of private keys created in a convoluted way that happen to hash
to prime numbers and I've got no issues with that.

However I'd like to point out that according to pigeon hole principle on average there exist
2^96 = 79 228 162 514 264 337 593 543 950 336 private keys (prime or not) for any single hash.

So after all it's possible your private key - hash set turns out not as much unique as you thought.

[nullius]

But does it have any actual use? I'd love your take on it.

Does it add value? (Primes cannot - by definition - be factorized, so no one could ever arrive at your private key by factorization and multiplication [if that's even a thing].)

If you confuse the concepts between the ECDLP and the RSA Problem, then you should not be generating your own private keys.

Are primes handled "better" (whatever that means) when for example signing transactions, resulting in better byte economy for the blockchain?

No.

Is this unsafe? (I think not, according to the prime number theorem (PNT) there should be about 6.54*10^74 primes - a huge number - in the range as defined by the secp256k1 with the ECDSA algorithm. In other words, of all possible private keys, approximately 0.056% are prime, but only a few of these correspond to public addresses whose hash160 happen to be prime too.)

It is slightly less safe since the search space is being reduced.

That's around 2^248.53,

You are reducing the number of possible private keys.

He is also changing the distribution of the keyspace.  Private keys are supposed to be selected from a discrete uniform random distribution within the keyspace (and those who don’t know what that means should NOT be messing with this stuff...).  The subset from which he is selecting keys does not have that distribution—unlike keys that are simply restricted to a contiguous part of the keyspace.

I have no idea if or how this difference of distribution could be exploited—or even whether or not that would require solving one of the biggest, oldest problems in mathematics...  However, I would not bet that a cryptographer could not think of something clever!

What do you think?

The NSA loves you.

You have not even adequately answered the question implied in the topic title:  Why?

[PrimeNumber7]

Compare these two scenarios

1. Output random 32-byte numbers. Test all against known addresses on the blockchain. (Let's for the sake of discussion disregard the fact that such experiments have never yielded any success.)

2. Output random 32-bytes numbers. Test each for primality (time-consuming!). Discard all numbers that are not prime, and test only the remaining ones (the primes) against known addresses on the blockchain.

Scenario 1 is always going to be faster.

This is not necessarily true. Someone could utilize a dataset of 32-byte numbers that are prime. Or someone could develop an ASIC to generate 32-byte numbers. Once an attacker has a list of prime numbers, they can test each one against the calculated address derived from the prime number to see if there are any unspent outputs.