【秘密鍵200億個】自分の名前を含む秘密鍵を作った

少し前にQiitaでこんな記事を見つけました
秘密鍵を10億個作れば、高確率で自分の名前を含む公開鍵が作れる件

そして記事のものを少し改変したこのようなワンライナーを使い

tgt=gack951; mkdir /tmp/ram; sudo mount -t tmpfs -o size=1G /dev/shm /tmp/ram; cd /tmp/ram; date -Is; for i in `seq 1e5`; do ls | xargs rm; seq 1e5 | SHELL=/bin/sh split -u -n r/48 --filter 'while read n; do ssh-keygen -t ed25519 -f id_ed_$n -N "" -C "" > /dev/null; done'; find . -name \*.pub | xargs cat > tmp.pub; if [ -n "$(hw -ilN $tgt tmp.pub)" ]; then break; fi; echo -n -e "\r"`date -Is`" "$i; done; echo -e "\n"`date -Is`; rm tmp.pub; hw -eiN "(?<=ssh-ed25519 ).+$tgt"

次のような公開鍵を得ました
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIN3LJ5kpJIc/bL+vGack9517bjl7Zn9rgdKYtrNQDtlH

オリジナルからの変更点は

• xargsではなくsplitを使用 (論理コア数に合わせて分割数を48に)
• mktemp -dではなくtmpfsでRAMディスクを使用
• 一度に$10^5$個の鍵を生成
• 文字列検索にgrepではなくhwを使用 (tkengo/highwayのインストールが必要)
• 成功時にアタリの鍵をコピーし残りを消す後処理が未実装 (なんとかならんのか)

です。これで手元のマシン(Ryzen Threadripper 3960X)にて$1$ループ($10^5$鍵)$/10s$強の速度が出ました。

元記事にはmktemp -dでディスクI/Oが削減できるとありましたが、手元のDebian 10では実感できませんでした。tmpfsをマウントすることでRAMディスクが使用でき、以下のような簡易的なテストでも明らかに速くなっていました。

$ cd $(mktemp -d)
$ dd if=/dev/zero of=./zero bs=1M count=8k conv=fdatasync
8192+0 records in
8192+0 records out
8589934592 bytes (8.6 GB, 8.0 GiB) copied, 10.1727 s, 844 MB/s

$ mkdir /tmp/ram; sudo mount -t tmpfs -o size=8G /dev/shm /tmp/ram; cd /tmp/ram;
$ dd if=/dev/zero of=./zero bs=1M count=8k conv=fdatasync
8192+0 records in
8192+0 records out
8589934592 bytes (8.6 GB, 8.0 GiB) copied, 2.43279 s, 3.5 GB/s

SSDはSamsung 970 EVO Plus 500GB PCIe NVMe M.2です。

xargsやsplitでgrepを並列して動かすよりも、マルチスレッドで実装されたhwを使ったほうが速いです。ただしファイル数が多すぎてrm *やhw $tgt *.pubができないのでパイプを使ったり一度1ファイルにまとめたりと工夫しています。

検索対象文字列に数字が含まれているため、case-insensitiveでの希望文字列の発生確率が下がります。元記事にあるように7文字すべてアルファベットの場合、10億個生成時の発生確率は

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

ですが、7文字中3文字が数字の場合

>>> 1-(1-2**4/64**7*37)**1e9
0.12593909104192935

とかなり望み薄…。100億個生成時でようやく

>>> 1-(1-2**4/64**7*37)**1e10
0.7397342771010214

となります。

ガチャ運が足りなかったため実際には2セット目(200億鍵生成)の終わり際にようやく発見されました。1セットおよそ10日だったので、20日かかりました。そんな場合に備えてワンライナーではなく、マウントと検索ループは分けておいたほうが良い気がします。

mkdir /tmp/ram; sudo mount -t tmpfs -o size=1G /dev/shm /tmp/ram; cd /tmp/ram;
tgt=gack951; date -Is; for i in `seq 1e5`; do ls | xargs rm; seq 1e5 | SHELL=/bin/sh split -u -n r/48 --filter 'while read n; do ssh-keygen -t ed25519 -f id_ed_$n -N "" -C "" > /dev/null; done'; find . -name \*.pub | xargs cat > tmp.pub; if [ -n "$(hw -ilN $tgt tmp.pub)" ]; then break; fi; echo -n -e "\r"`date -Is`" "$i; done; echo -e "\n"`date -Is`; rm tmp.pub; hw -eiN "(?<=ssh-ed25519 ).+$tgt"