HCP
Legendary
Offline
Activity: 2086
Merit: 4318
<insert witty quote here>
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 16, 2018, 05:36:13 AM |
|
Unfortunately in my case I have no idea of the positions of the lost characters, but I keep trying, because it has been very useful for me to learn new skills and resources.
In which case, I think the search space is something like (58chars*47positions)*(58chars*47pos)*(58chars*47pos)*(58chars*47pos)... (58*47) 4 = 5.5220891*10 13 possible combinations ![Undecided](https://bitcointalk.org/Smileys/default/undecided.gif) It should be possible to modify the code (or write new code) to test all the possible combinations... but it is going to take a LONG time to search all of that. Testing 1,000,000 combinations/second will take nearly 2 years to search all of them. (for reference, my Core i5-3570K, running Ubuntu on the Windows 10 Linux Subsystem seems to average around 200,000 combinations/second.) Not exactly "impossible" (and for 5 BTC, probably worth it ![Tongue](https://bitcointalk.org/Smileys/default/tongue.gif) )... but technically it will be difficult to run a task non-stop for that period of time.
|
|
|
|
Thirdspace
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 16, 2018, 01:12:51 PM |
|
The private key starts with 5, so the total would be 51 characters right?
Correct. Unfortunately in my case I have no idea of the positions of the lost characters, but I keep trying, because it has been very useful for me to learn new skills and resources.
In which case, I think the search space is something like (58chars*47positions)*(58chars*47pos)*(58chars*47pos)*(58chars*47pos)... (58*47) 4 = 5.5220891*10 13 possible combinations ---snip---I think your calculation is a bit off. Also we can save computation power by narrowing down search space, the first 2 chars always start with '5H', '5J', '5K', 51-2 = 49 positions and 49-4 = 45 characters known if exact position of 4 lost characters are known = 58^4 = 11,316,496 iterations if exact position is unknown = 58^4 * 4-combination = (58^4) * ( 49! / 4! (49-4)! ) = (58^4) * (46*47*2*49) = (58^4) * 211876 = 2,397,693,906,496 iterations = 2.39 * 10 12do I get this right? Testing 1,000,000 combinations/second will take nearly 2 years to search all of them. (for reference, my Core i5-3570K, running Ubuntu on the Windows 10 Linux Subsystem seems to average around 200,000 combinations/second.) are you sure we can have that computation power for combinations/second? if compute power 200,000 combinations/second ~ 137.5 days (4.5 months) if compute power 1,000,000 combinations/second ~ 27.75 days (1 month) if by any chance the search space can be narrowed down even more (for e.g. assume the first 15 chars are correct) it can cut down the number combinations and the needed time drastically
|
|
|
|
LoyceV
Legendary
Offline
Activity: 3430
Merit: 17355
Thick-Skinned Gang Leader and Golden Feather 2021
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 16, 2018, 03:50:44 PM |
|
if by any chance the search space can be narrowed down even more (for e.g. assume the first 15 chars are correct) it can cut down the number combinations and the needed time drastically
If someone skips 4 characters while writing down a private key, chances are he also wrote down one or more characters incorrectly. If you're sure the rest is correct, it could be worth spending some money on Cloud computing, start up enough nodes, and crunch it quickly. Someone specialized in wallet recoveries may be able to help you with this. I'm thinking about Dave from https://walletrecoveryservices.com/ for instance.
|
|
|
|
bob123
Legendary
Offline
Activity: 1624
Merit: 2481
|
Unfortunately in my case I have no idea of the positions of the lost characters, but I keep trying, because it has been very useful for me to learn new skills and resources.
In which case, I think the search space is something like (58chars*47positions)*(58chars*47pos)*(58chars*47pos)*(58chars*47pos)... (58*47) 4 = 5.5220891*10 13 possible combinations ---snip---I think your calculation is a bit off. Also we can save computation power by narrowing down search space, the first 2 chars always start with '5H', '5J', '5K', 51-2 = 49 positions and 49-4 = 45 characters known if exact position of 4 lost characters are known = 58^4 = 11,316,496 iterations if exact position is unknown = 58^4 * 4-combination = (58^4) * ( 49! / 4! (49-4)! ) = (58^4) * (46*47*2*49) = (58^4) * 211876 = 2,397,693,906,496 iterations = 2.39 * 10 12do I get this right? I am pretty sure you made a small mistake there. You do ignore the order of the 4 missing words with your statement: ( 49! / 4! (49-4)! )You do iterate through each position with your words, but you have to iterate within the words too. This should be the correct calculation: There are 58 choose 4 possible combinations to pick the 4 correct chars from the charspace (without considering the order). Now consider the first two characters as already known. Only looking at the private key without the first two chars here: To put the first unknown char into the correct place, you can choose between 1) before of each already existing char (45 possibilities) and 2) behind the last one (45+1). For the second one you choose either before each char in your privkey (46 possibilities) or behind the last one (46+1)... Overall there are 46 * 47 * 48 * 49 possible combinations to place the 4 chars into a private key with 45 known characters (ignoring the first two) into the right order. This assumes the already known characters are in a correct order already. The total search space (for the private key without the first 2 chars) therefore is 46 * 47 * 48 * 49 * (58 choose 4) = 2.1574231*10 12. Multiplied with 4 (combinations the priv key can start with) = total amount of combinations = 8.6296925 * 1012Considering the birthay paradox, there is a 50% chance to find the correct private key after 1/2 of this space. Feel free to correct me if i have made a mistake!
|
|
|
|
HCP
Legendary
Offline
Activity: 2086
Merit: 4318
<insert witty quote here>
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 17, 2018, 09:45:20 AM Last edit: May 17, 2018, 09:57:38 AM by HCP |
|
Considering the birthay paradox, there is a 50% chance to find the correct private key after 1/2 of this space.
Surely it is just common sense that searching half the space obviously has a 50% chance of finding the right key The maths of the birthday attack suggests that by randomly generating keys (as opposed to sequentially searching the space), the smallest number of keys we'd need to test to have a 50% chance of finding the right one would be: ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fwikimedia.org%2Fapi%2Frest_v1%2Fmedia%2Fmath%2Frender%2Fsvg%2Fa31a9674c3d9f5249ad6d124f5c51d5f1d04294f&t=665&c=7rDF0gloV7wgEQ) Which for your calculated search space is only something like: ~3,458,770 guesses... which isn't a great deal to be honest. I'm pretty sure that the Birthday Attack is the reason why VanityGen generates keys randomly rather than sequentially
|
|
|
|
korandek
Newbie
Offline
Activity: 31
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 17, 2018, 10:01:10 AM |
|
Hello people! I've been looking at the forum and seen that there are some ways to recover a private key that is missing some characters, it fed me hope and I'm trying to figure out a way for me to recover my private key.
Currently my private key has only 47 characters, but of the remaining characters, I'm not sure if the missing ones are the end, beginning or middle of the private key (I think it's the end), you know some algorithm you can try to generate a valid private key in my situation?
Just say, that when i read this information, i starting to go in shock - it is your own security! What is your opinion in it? Why you didn't put this information on a safe place???
|
|
|
|
LoyceV
Legendary
Offline
Activity: 3430
Merit: 17355
Thick-Skinned Gang Leader and Golden Feather 2021
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 17, 2018, 10:03:24 AM |
|
the smallest number of keys we'd need to test to have a 50% chance of finding the right one would be: This can't be right. The birthday paradox is about finding a collision, in other words testing the same private key twice. Which for your calculated search space is only something like: ~3,458,770 guesses... which isn't a great deal to be honest. I can believe it takes about 3 million guesses for a 50% chance (out of 8 trillion possibilities) to guess the same key twice. But that's not going to help you, as you'll still need to search 4 trillion keys for 50% chance of finding the right one. Using a random search only means you test the same key several times, while you may never test some of the other keys.
|
|
|
|
bob123
Legendary
Offline
Activity: 1624
Merit: 2481
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 17, 2018, 11:17:01 AM |
|
Considering the birthay paradox, there is a 50% chance to find the correct private key after 1/2 of this space.
Surely it is just common sense that searching half the space obviously has a 50% chance of finding the right key Unfortunately not as common sense as it should be ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) But you are right. The expression itself is a bit odd. I just wanted to say that you don't actually have to seach the whole space (because thats what most people believe when they hear they are that much combination). On average, it is enough to seach 50% of the space. The maths of the birthday attack suggests that by randomly generating keys (as opposed to sequentially searching the space), the smallest number of keys we'd need to test to have a 50% chance of finding the right one would be: ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fwikimedia.org%2Fapi%2Frest_v1%2Fmedia%2Fmath%2Frender%2Fsvg%2Fa31a9674c3d9f5249ad6d124f5c51d5f1d04294f&t=665&c=7rDF0gloV7wgEQ) Which for your calculated search space is only something like: ~3,458,770 guesses... which isn't a great deal to be honest. It is not about a 50% chance to find one correct key, but to find '2 same keys'. ~3,458,770 would be the amount of guesses it would take to have a 50% chance for having generated the same key twice. I'm pretty sure that the Birthday Attack is the reason why VanityGen generates keys randomly rather than sequentially
Actually this should be a reason for vanitygen to not use randomly. My guess would be that it is just way faster to randomly generate them than to create them sequentially + memory storage and I/O. And since vanitygen is used to create addresses with a relatively small prefix (compared to the overall length), it probably doesn't make a huge difference.
|
|
|
|
LoyceV
Legendary
Offline
Activity: 3430
Merit: 17355
Thick-Skinned Gang Leader and Golden Feather 2021
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 19, 2018, 07:35:36 AM |
|
Am having some missin numbers right at the middle(after the first ten digits), would this algorithm work in such case?
Yes.
|
|
|
|
Thirdspace
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 19, 2018, 11:11:35 AM |
|
The total search space (for the private key without the first 2 chars) therefore is 46 * 47 * 48 * 49 * (58 choose 4) = 2.1574231*1012. Multiplied with 4 (combinations the priv key can start with) = total amount of combinations = 8.6296925 * 1012
I don't understand where you come up with 46 * 47 * 48 * 49 and (58 choose 4) we're not choosing 4 out of 58, but we pick 1 of 58, do 4 times (positions) = 58*58*58*58 = 58^4 I am pretty sure you made a small mistake there. You do ignore the order of the 4 missing words with your statement: ( 49! / 4! (49-4)! ) You do iterate through each position with your words, but you have to iterate within the words too.
There are 58 choose 4 possible combinations to pick the 4 correct chars from the charspace (without considering the order).
why 58 choose 4? the 4 chars are not guaranteed distinct what I do is C(n,k) = n choose k = 49 choose 4 , but not for chars I'm doing this ( 49! / 4! (49-4)! ) for possible position combinations of the missing 4 chars then for each possible position combination, there are 58^4 possible char combinations 49 positions, 45 known chars (order sequence assumed) and trying to fill 4 chars in any 4 positions so total = (49 choose 4) * 58^4 = 211,876 * 58^4 = 2,397,693,906,496 = 2.39 * 10 12
small example: 4 positions, 2 known chars (order sequence assumed) and trying to fill 2 chars in any 2 positions 4 choose 2 = ( 4! / 2! (4-2)! ) = ( 1*2*3*4 / 1*2*1*2 ) = 6 possible position combinations so total = 6*58*58 = (4 choose 2) * 58^2 5 K x x x x 1. 5 K _ _ x x 58*58 2. 5 K _ x _ x 58*58 3. 5 K _ x x _ 58*58 4. 5 K x _ _ x 58*58 5. 5 K x _ x _ 58*58 6. 5 K x x _ _ 58*58
|
|
|
|
ikatamoonshots
Jr. Member
Offline
Activity: 44
Merit: 2
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 01, 2018, 11:34:08 PM |
|
here a very simple bash to guess last 5 chars allnum of a string and add the string as prefix, then import prefixed string to bitcoin-core wallet. #!/bin/bash
BRUTELIST=/home/$USER/brutelist.tst ADDEDPREFIXLIST=/home/$USER/addedprefixlist.tst
crunch 5 5 -f /usr/share/crunch/charset.lst mixalpha-numeric > $BRUTELIST
cat $BRUTELIST | while read LINE do sed -e 's/^/incompletekeyprefix/' $BRUTELIST > $ADDEDPREFIXLIST done
cat $ADDEDPREFIXLIST | while read LOSTKEY do bitcoin-cli -rpcuser=rpcuser -rpcpassword=rpcpass importprivkey $LOSTKEY "mylostkey" false done
echo "check console output for errors" echo "if all went fine you can rescan the wallet now and then export the relevant key(s)"
|
|
|
|
LoyceV
Legendary
Offline
Activity: 3430
Merit: 17355
Thick-Skinned Gang Leader and Golden Feather 2021
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 02, 2018, 06:31:11 AM |
|
here a very simple bash to guess last 5 chars allnum of a string and add the string as prefix, then import prefixed string to bitcoin-core wallet. It's less efficient but easier to understand than the Private Key Restorer in the second post. I'd still be interested in a way to just restore the checksum, that should be quite easy and very fast, but I haven't been able to find anything for it.
|
|
|
|
ikatamoonshots
Jr. Member
Offline
Activity: 44
Merit: 2
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 02, 2018, 07:12:33 AM |
|
here a very simple bash to guess last 5 chars allnum of a string and add the string as prefix, then import prefixed string to bitcoin-core wallet. It's less efficient but easier to understand than the Private Key Restorer in the second post. I'd still be interested in a way to just restore the checksum, that should be quite easy and very fast, but I haven't been able to find anything for it. Checksum for what? Same as restoring the key, no? Dont exactly get what you mean, bit tired ![Tongue](https://bitcointalk.org/Smileys/default/tongue.gif)
|
|
|
|
LoyceV
Legendary
Offline
Activity: 3430
Merit: 17355
Thick-Skinned Gang Leader and Golden Feather 2021
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 02, 2018, 07:25:02 AM |
|
Checksum for what? Same as restoring the key, no? Dont exactly get what you mean, bit tired ![Tongue](https://bitcointalk.org/Smileys/default/tongue.gif) The last 7 characters of the WIF private key are a checksum. I have successfully used this method to import a private key without the last 7 characters into blockchain.info, and when I export it again, it's complete. If blockchain.info can do that, it would be very nice to have a local program that does the same.
|
|
|
|
ikatamoonshots
Jr. Member
Offline
Activity: 44
Merit: 2
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 02, 2018, 07:38:30 AM |
|
7 chars allnum 25terabyte of data, they probably have big IO throughput at hand and did the same as the script, import the entire batch to a wallet or scan it with a block explorer or match the list against one checksum - now idea what else would do, where else could that be derived?
|
|
|
|
LoyceV
Legendary
Offline
Activity: 3430
Merit: 17355
Thick-Skinned Gang Leader and Golden Feather 2021
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 02, 2018, 07:50:20 AM |
|
7 chars allnum 25terabyte of data, they probably have big IO throughput at hand Nothing like that, see https://en.bitcoin.it/wiki/Wallet_import_format for the theory.
|
|
|
|
larry_vw_1955
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 30, 2021, 01:46:32 AM |
|
Hello people! I've been looking at the forum and seen that there are some ways to recover a private key that is missing some characters, it fed me hope and I'm trying to figure out a way for me to recover my private key.
Currently my private key has only 47 characters, but of the remaining characters, I'm not sure if the missing ones are the end, beginning or middle of the private key (I think it's the end), you know some algorithm you can try to generate a valid private key in my situation?
I have the software that recovers up to 6 characters from the private key what i dont understand is how the private key ended up 4 characters short. that's really confusing. did they print it out and the printer messed up or ...i guess they wrote it down wrong on paper but that's kind of hard to believe. one mistake is undestandable but 4?
|
|
|
|
pooya87
Legendary
Offline
Activity: 3570
Merit: 10845
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 30, 2021, 04:59:49 AM |
|
I have the software that recovers up to 6 characters from the private key
Any software that is not 100% open source and available to public to be reviewed is not trustworthy. what i dont understand is how the private key ended up 4 characters short. that's really confusing. did they print it out and the printer messed up or ...i guess they wrote it down wrong on paper but that's kind of hard to believe. one mistake is undestandable but 4?
It can be a lot of different things, you already though of the printer issue and typos. There can also be damages to the storage medium (eg. paper) where some characters have become unreadable now. 4 characters is nothing, the paper could have been torn and half of it could be missing.
|
|
|
|
HCP
Legendary
Offline
Activity: 2086
Merit: 4318
<insert witty quote here>
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 02, 2021, 03:47:23 AM |
|
Indeed... anecdotally, I have seen so many stories on this forum over the last 4-5 years of "small children" that destroy backups (ripping paper, scribbling in notebooks etc)... and, from memory, one or two involving animals. Also, a few with "bad handwriting" where they can't decipher certain characters... and spilling of liquid onto papers is another.
|
|
|
|
|