秘密鍵を10億個作れば、高確率で自分の名前を含む公開鍵が作れる件

エンジニアなら誰もがgithubで晒される公開鍵。
https://github.com/ユーザー名.keys
で全世界に公開されます。

それでは、稚拙ながら私[@umihicoの公開鍵](https://github.com/umihico.keys)をご覧ください。

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIF<font color="Red" style="font-weight: bold;">**UMIHICo**</font>Cb3Sy2n1qPXOxc2mFBqW9Hg0dRigxl2F3nW

そうです。自身のユーザー名を挿入することに成功しました。正規表現で指定の文字列が見つかるまで、とにかく鍵を生成し続けるワンライナーを作り、それを1週間くらい回しました。ワンライナーはこちらです。

@Ress さんより`cd $(mktemp -d)`を使用しディスクIOの時間を減らすアドバイスを頂きました。ありがとうございます！

```bash
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
```

鍵生成から正規表現判定と削除までの処理を、`xargs`でマルチプロセスを使って1000個の並列処理をしています。見つかり次第、`while`から抜けています。RSAよりed25519を使うことで短時間で大量に作成できます。しかも鍵の安全性が高まり、文字長も短いです。

@AKKYM さんより、`xargs`より`filter`を使ってマルチプロセスを高速化させる提案を頂きました。1.2倍ほどパフォーマンスが改善します。ありがとうございます。Macbookの`split`は引数がLinuxと異なるので、`brew install coreutils`でインストールできる`gsplit`を使う必要があります。

```bash
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`が分割数＝プロセス数になりますが、増やしたり少なくしたりしてベスト値から外れると、パフォーマンスが低下し`xargs`と同程度になります。それに対し`xargs`はプロセス数は32〜1000で変化させてみても、明らかな差はあまりないです。

サーバーでtmuxなどを使ってバックグラウンドで処理させる場合は通知がほしいので、`echo found`を例えばSlackのWebhook Incoming APIなどに置換しましょう。以下のようになります。（xargsバージョン）

```bash
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
```

ちなみに遊休サーバーなら使ってもいいかというと、EC2はCPUバーストの設定によっては+αの課金をされるので注意しましょう。
[CPUバーストUnlimitedのEC2さんに乱暴したら課金された](https://qiita.com/umihico/items/c8725298d0fb118a41b1)


それでは希望の文字列が発生する確率と待ち時間について考察します。
7文字のbase64からなるランダムな文字列が、偶然`umihico`（case-insensitive）になる可能性は、`2^7/64^7`です。そしてed25519は変化する文字列長が43文字なので、7文字の場合はこの試行を37回同時に行えると解釈できます。つまり１回でヒットする確率は `0.0000001076841726899147%`です。

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

10億回試行するまでに見つかる確率は10億回連続で見つからない確率を1から引けばよいです。65.9%です。

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

X文字をYの確率で出現させるにはZ回試行すればよい、というのは以下の式で得られます。（python3.6以降のターミナル）

```python
>>> import math
>>> X=8
>>> Y=0.6
>>> Z=int(math.log(1-Y,1-2**X/64**X*(43-X+1)))
>>> f"{X}文字の場合{ '{:,}'.format(Z)}回で{Y*100}%"
'8文字の場合27,985,342,058回で60.0%'
```

ワンライナーは1000件生成が完了する毎に`date`が実行されるので、少し眺めていれば１日に何件試行できるか見当がつきます。１秒に1000件できても、8文字で60%を叩き出す270億回のためには324日かかるので、8文字以上の名前の方々は現実的ではないと言えそうです。ごめんなさい。

そして注意点があります、公開鍵は当然、ランダムな文字列ではありません。しかし名前という`任意な文字列を含む確率`という命題に対しては、ランダムとして扱えると仮定しています。色々試し、体感的には正しそうですが、**無根拠です。**つまり、永遠に試行しても発生しない文字列や、ランダムより歪んだ確率を持つ文字列の存在が十分ありえます。この辺をもっと調べたいですが、~~これ以上業務時間を使うべきではありません。~~

@angel_p_57 さんよりコメントで補足を頂きました。
ランダムとして扱ってよいが、最初のIの次は大文字A～Pに限られるとのことです。ありがとうございます。

ご一読ありがとうございました。

[Gist](https://gist.github.com/umihico/4b957f6cbce20f7496cea75ef7e091a6)

参考
- https://qiita.com/suthio/items/2760e4cff0e185fe2db9
- https://qiita.com/wnoguchi/items/a72a042bb8159c35d056
- https://qiita.com/ir-yk/items/af8550fea92b5c5f7fca
- https://jnst.hateblo.jp/entry/2014/12/15/200542
- https://www.slideshare.net/hnw/edomaesec-20150124
- https://hnw.hatenablog.com/entry/20140705
- https://qiita.com/YuukiMiyoshi/items/e428c7d89d713f642638
- http://ichii386.hatenablog.com/entry/20150627/1435357368
- https://stackoverflow.com/questions/46035099/mac-bash-split-cannot-split-by-line-bytes