Topic: Prime number Bitcoin keypairs - How and why (Read 363 times)

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.

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


No.


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!


The NSA loves you.

---

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

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.

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.

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



I'm interested.


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.

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.

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.

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.

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.

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.

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

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 

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.

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


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!

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

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).


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.



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.

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.

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.

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.

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.

HOW

First, consider this Bitcoin key pair:


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):


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


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:


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



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?