[비밀 키 200억개] 자기 이름을 담은 비밀 키를 만들었어요.

얼마 전에 Qita에서 이런 기사가 나왔어요.
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

대신 RAM 디스크 사용

한 번에 10^5 키 생성하기

문자열 검색은greptkengo/highway 대신 hw를 사용해야 한다

성공 시 첨부된 키를 복제하고 나머지 부분의 뒷처리를 제거합니다(실행 가능한지)

네.이렇게 되면 손 옆에 있는 기계(Ryzen Thereadripper 3960X)에서 순환(10^5키)/10s의 속도가 나타난다.
원래 보도에서 mktemp-d는 디스크 I/O를 줄일 수 있다고 했지만 수중에 있는 Debian 10은 실감이 나지 않았다.tmpfs 설치를 통해 램 디스크를 사용할 수 있어 아래의 간이 테스트에서도 속도가 현저히 빨라졌다.

$ 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하지 못해서 파이프나 한꺼번에 서류로 정리했다.
검색 대상 문자열에 숫자가 포함되어 있기 때문에case-insitive에서 희망 문자열의 발생 확률이 낮아집니다.앞에서 말한 바와 같이 모든 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억키 생성)가 끝날 때만 발견됐다.한 벌에 열흘 정도 걸려서 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"