BTCW (OP)
Copper Member
Full Member
Offline
Activity: 193
Merit: 239
Click "+Merit" top-right corner
|
|
March 20, 2021, 01:30:51 AM Last edit: March 20, 2021, 01:44:00 AM by BTCW |
|
HOWFirst, consider this Bitcoin key pair: 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): Private key (hex): b136fef8391b4956312a6df2f6dc99b7cf238982dbcfbcb629f4ed6d35671a77
Public Address hash160 (hex): b175364aaea8ecb515c1779cd00b0c3ba157bb25 Still not impressed? Alright, let's convert them to decimal (ordinary) numbers, so that: 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 codeIt 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: 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 outputWhen executed, the script outputs the following ==== 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. WHYThey 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
Legendary
Offline
Activity: 3514
Merit: 10712
|
|
March 20, 2021, 04:02:13 AM |
|
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.
|
. .BLACKJACK ♠ FUN. | | | ███▄██████ ██████████████▀ ████████████ █████████████████ ████████████████▄▄ ░█████████████▀░▀▀ ██████████████████ ░██████████████ █████████████████▄ ░██████████████▀ ████████████ ███████████████░██ ██████████ | | CRYPTO CASINO & SPORTS BETTING | | │ | | │ | ▄▄███████▄▄ ▄███████████████▄ ███████████████████ █████████████████████ ███████████████████████ █████████████████████████ █████████████████████████ █████████████████████████ ███████████████████████ █████████████████████ ███████████████████ ▀███████████████▀ ███████████████████ | | .
|
|
|
|
NotATether
Legendary
Offline
Activity: 1666
Merit: 7034
In memory of o_e_l_e_o
|
|
March 20, 2021, 06:02:47 AM |
|
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.
|
. .BLACKJACK ♠ FUN. | | | ███▄██████ ██████████████▀ ████████████ █████████████████ ████████████████▄▄ ░█████████████▀░▀▀ ██████████████████ ░██████████████ █████████████████▄ ░██████████████▀ ████████████ ███████████████░██ ██████████ | | CRYPTO CASINO & SPORTS BETTING | | │ | | │ | ▄▄███████▄▄ ▄███████████████▄ ███████████████████ █████████████████████ ███████████████████████ █████████████████████████ █████████████████████████ █████████████████████████ ███████████████████████ █████████████████████ ███████████████████ ▀███████████████▀ ███████████████████ | | .
|
|
|
|
PrimeNumber7
Copper Member
Legendary
Offline
Activity: 1638
Merit: 1899
Amazon Prime Member #7
|
|
March 20, 2021, 07:03:45 AM |
|
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 (OP)
Copper Member
Full Member
Offline
Activity: 193
Merit: 239
Click "+Merit" top-right corner
|
|
March 21, 2021, 12:40:49 AM |
|
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 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
Legendary
Offline
Activity: 1666
Merit: 7034
In memory of o_e_l_e_o
|
|
March 21, 2021, 04:26:57 AM |
|
How about a field test? I just sent 1 tBTC to 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.
|
. .BLACKJACK ♠ FUN. | | | ███▄██████ ██████████████▀ ████████████ █████████████████ ████████████████▄▄ ░█████████████▀░▀▀ ██████████████████ ░██████████████ █████████████████▄ ░██████████████▀ ████████████ ███████████████░██ ██████████ | | CRYPTO CASINO & SPORTS BETTING | | │ | | │ | ▄▄███████▄▄ ▄███████████████▄ ███████████████████ █████████████████████ ███████████████████████ █████████████████████████ █████████████████████████ █████████████████████████ ███████████████████████ █████████████████████ ███████████████████ ▀███████████████▀ ███████████████████ | | .
|
|
|
|
KingZee
Sr. Member
Offline
Activity: 924
Merit: 452
Check your coin privilege
|
|
March 21, 2021, 05:54:46 PM |
|
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
|
Beep boop beep boop
|
|
|
BTCW (OP)
Copper Member
Full Member
Offline
Activity: 193
Merit: 239
Click "+Merit" top-right corner
|
|
March 21, 2021, 09:39:30 PM |
|
How about a field test? I just sent 1 tBTC to 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" 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 (OP)
Copper Member
Full Member
Offline
Activity: 193
Merit: 239
Click "+Merit" top-right corner
|
|
March 21, 2021, 10:30:13 PM |
|
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
Legendary
Offline
Activity: 1666
Merit: 7034
In memory of o_e_l_e_o
|
|
March 22, 2021, 04:54:30 AM |
|
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. 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.
|
. .BLACKJACK ♠ FUN. | | | ███▄██████ ██████████████▀ ████████████ █████████████████ ████████████████▄▄ ░█████████████▀░▀▀ ██████████████████ ░██████████████ █████████████████▄ ░██████████████▀ ████████████ ███████████████░██ ██████████ | | CRYPTO CASINO & SPORTS BETTING | | │ | | │ | ▄▄███████▄▄ ▄███████████████▄ ███████████████████ █████████████████████ ███████████████████████ █████████████████████████ █████████████████████████ █████████████████████████ ███████████████████████ █████████████████████ ███████████████████ ▀███████████████▀ ███████████████████ | | .
|
|
|
|
pooya87
Legendary
Offline
Activity: 3514
Merit: 10712
|
|
March 22, 2021, 07:53:34 AM |
|
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_primesThere 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 256 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.
|
. .BLACKJACK ♠ FUN. | | | ███▄██████ ██████████████▀ ████████████ █████████████████ ████████████████▄▄ ░█████████████▀░▀▀ ██████████████████ ░██████████████ █████████████████▄ ░██████████████▀ ████████████ ███████████████░██ ██████████ | | CRYPTO CASINO & SPORTS BETTING | | │ | | │ | ▄▄███████▄▄ ▄███████████████▄ ███████████████████ █████████████████████ ███████████████████████ █████████████████████████ █████████████████████████ █████████████████████████ ███████████████████████ █████████████████████ ███████████████████ ▀███████████████▀ ███████████████████ | | .
|
|
|
|
BTCW (OP)
Copper Member
Full Member
Offline
Activity: 193
Merit: 239
Click "+Merit" top-right corner
|
|
March 22, 2021, 10:50:32 PM Last edit: March 22, 2021, 11:25:20 PM by 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_primesThere 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 256 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 n-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
Legendary
Offline
Activity: 1666
Merit: 7034
In memory of o_e_l_e_o
|
|
March 23, 2021, 05:34:53 AM |
|
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.
|
. .BLACKJACK ♠ FUN. | | | ███▄██████ ██████████████▀ ████████████ █████████████████ ████████████████▄▄ ░█████████████▀░▀▀ ██████████████████ ░██████████████ █████████████████▄ ░██████████████▀ ████████████ ███████████████░██ ██████████ | | CRYPTO CASINO & SPORTS BETTING | | │ | | │ | ▄▄███████▄▄ ▄███████████████▄ ███████████████████ █████████████████████ ███████████████████████ █████████████████████████ █████████████████████████ █████████████████████████ ███████████████████████ █████████████████████ ███████████████████ ▀███████████████▀ ███████████████████ | | .
|
|
|
|
archyone
Newbie
Offline
Activity: 25
Merit: 1
|
|
March 23, 2021, 06:28:21 AM |
|
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
|
|
March 25, 2021, 07:34:25 PM |
|
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
|
|
March 26, 2021, 05:21:59 AM |
|
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
Copper Member
Legendary
Offline
Activity: 1638
Merit: 1899
Amazon Prime Member #7
|
|
March 26, 2021, 05:41:14 AM |
|
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.
|
|
|
|
|