If you make 1 billion private keys, you can make a public key including your name with high probability.

A public key that any engineer is exposed to on github. https://github.com/ユーザー名.keys Will be published worldwide.

Then, please take a look at me @ umihico's public key.

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIFUMIHICoCb3Sy2n1qPXOxc2mFBqW9Hg0dRigxl2F3nW

That's right. You have successfully inserted your own username. I made a one-liner that keeps generating keys until I find the specified string in the regular expression, and I ran it for about a week. Click here for one liner.

@Ress advised me to use cd $ (mktemp -d) to reduce disk IO time. Thank you!

cd $(mktemp -d); while true; do seq 1000 | xargs -P 1000 -I NUM sh -c 'ssh-keygen -t ed25519 -f NUM.pem -N "" -C "" > /dev/null && if grep -vi umihico NUM.pem.pub > /dev/null; then rm NUM.pem NUM.pem.pub;fi' ; if find . -mindepth 1 | read; then  for f in *.pem.pub; do echo $f >> files.txt; done; test -f files.txt && head -n1 files.txt | xargs -I F echo found;  break; fi ; date ; done

The processing from key generation to regular expression judgment and deletion is performed in parallel with xargs using multiple processes. As soon as it is found, it is missing from while. By using ed25519 from RSA, you can create a large number in a short time. Moreover, the security of the key is improved and the character length is short.

@AKKYM gave us a suggestion from xargs to use filter to speed up multi-process. Performance is improved by 1.2 times. Thank you very much. Macbook split has different arguments than Linux, so you need to use gsplit which can be installed with brew install coreutils.

cd $(mktemp -d); while true; do seq 1000 | gsplit -u -n r/32 --filter 'while read i; do ssh-keygen -t ed25519 -f $i.pem -N "" -C "" > /dev/null && if grep -vi umihico $i.pem.pub > /dev/null; then rm $i.pem $i.pem.pub;fi; done' ; if find . -mindepth 1 | read; then  for f in *.pem.pub; do echo $f >> files.txt; done; test -f files.txt && head -n1 files.txt | xargs -I F echo found;  break; fi ; date ; done

r / 32 is the number of divisions = the number of processes, but if you increase or decrease it and deviate from the best value, the performance will decrease and it will be about the same as xargs. On the other hand, for xargs, even if the number of processes is changed from 32 to 1000, there is not much difference.

If you want the server to process in the background using tmux etc., you want to be notified, so replace ʻecho found` with, for example, Slack's Webhook Incoming API. It will be as follows. (Xargs version)

cd $(mktemp -d); while true; do seq 1000 | xargs -P 1000 -I NUM sh -c 'ssh-keygen -t ed25519 -f NUM.pem -N "" -C "" > /dev/null && if grep -vi umihico NUM.pem.pub > /dev/null; then rm NUM.pem NUM.pem.pub;fi' ; if find . -mindepth 1 | read; then  for f in *.pem.pub; do echo $f >> files.txt; done; test -f files.txt && head -n1 files.txt | xargs -I F curl -s -X POST -d '{"text":"F"}' https://hooks.slack.com/services/XXXXXXXXX/YYYYYYYYYYY/zzzZZZzZzzZzzZZzz;  break; fi ; date ; done

By the way, if you can use an idle server, please note that EC2 will be charged + α depending on the CPU burst setting. I was charged if I violently attacked EC2 of CPU burst Unlimited

Now let's consider the probability and waiting time for the desired string to occur. The chance that a random string of 7 characters base64 will accidentally become ʻumihico(case-insensitive) is2 ^ 7/64 ^ 7. And since ed25519 has a changing string length of 43 characters, it can be interpreted that this trial can be performed 37 times at the same time with 7 characters. In other words, the probability of hitting once is 0.0000001076841726899147%`.

>>> 2**7/64**7*37
1.076841726899147e-09

The probability of being found by trying 1 billion times is the probability of not being found 1 billion times in a row by subtracting from 1. It is 65.9%.

>>> 1-(1-2**7/64**7*37)**(10**9)
0.6593302436744479

The following formula gives that you only have to try Z times to make the X character appear with a probability of Y. (Terminal of python3.6 or later)

>>> import math
>>> X=8
>>> Y=0.6
>>> Z=int(math.log(1-Y,1-2**X/64**X*(43-X+1)))
>>> f"{X}For letters{ '{:,}'.format(Z)}At times{Y*100}%"
'For 8 characters 27,985,342,058 times 60.0%'

Oneliner executes date every time 1000 cases are generated, so if you look at it for a while, you can guess how many cases you can try in a day. Even if you can do 1000 cases per second, it will take 324 days for 27 billion times to hit 60% with 8 characters, so it seems that people with names of 8 characters or more are not realistic. sorry.

And note that the public key is, of course, not a random string. However, it is assumed that the proposition "probability of including an arbitrary character string" called a name can be treated as random. I tried various things and it seems to be correct, but ** it is unfounded. ** In other words, it is quite possible that there are strings that will not occur even if you try forever, or strings that have a more distorted probability than random. I would like to find out more about this area, but ~~ I shouldn't spend any more business hours. ~~

I received a supplement from @ angel_p_57 in the comments. It can be treated as random, but after the first I, it is limited to uppercase letters A to P. Thank you very much.

Thank you for reading.

Gist

reference

Recommended Posts

If you make 1 billion private keys, you can make a public key including your name with high probability.
If you know Python, you can make a web application with Django
Make your own VPC with a Single Public Subnet Only with boto
Until you can borrow VPS with Conoha and authenticate public key with SSH
If you guys in the scope kitchen can do it with a margin ~ ♪
If you want to make a discord bot with python, let's use a framework