How to get a PGP RSA key pair with a "rare" fingerprint, e.g. one that begins "ABBA"? (Windows 10)

Question

On Windows 10, how can I automate the generation of PGP RSA key pairs, dumping each one if the 40 hex-character fingerprint doesn't begin ABBA (for example), stopping when a generated pair meets that criterion, then exporting the public and private key in standard ASCII-armoured form? Assuming all fingerprints are equiprobable, in this example the expected number of pairs to be generated is about 45,000 and is too many to cope with by hand.

Answer 1

I'm not sure there's a good way to do this in Windows.

EDIT

I ended up tinkering with this some more just for fun and came up with a new python script that will work in both Linux and Windows. It does away with the need for gpgsplit by reading the exported keys directly. The script also runs all the commands including generating, exporting, and importing the key - everything except the --edit-key part at the end of the process which the user has to do manually. All you have to do is run the script then edit the key.

Python 3 isn't installed in Windows, so you'll need to install it. You can get it from the Microsoft Store or you can download it from the Python website.

Just save save the script below as keychanger.py in any directory you want, then open a terminal or powershell in that same directory and enter python keychanger.py. It prompts for user input to tell it what hex string you want the fingerprint to start with and the key algorithm to use (prompts include some helpful info). There will be prompts from gpg when the created key is being deleted (you will have to confirm deletion 3 times; no way around this).

Note that Windows seems to interpret the --passphrase '' option literally and instead of the key having no password, it will have two single quotes as the password. If you see a pinentry pop up while the script is running, enter '' for the password. You can change this password when you edit the key after the script has run. I included the instructions for editing the key in the script output so it will be viewable on screen when you need it.

Also, neither Powershell nor Command Prompt allow copy/pasting commands unless you enable it by right-clicking on its title bar, selecting "Preferences" and checking the box that says "Use Ctrl+Shift+V/C as Copy/Paste".

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# keychanger.py - a script to create PGP keys with fingerprints begining
# with a custom hex string.
# Requires GnuPG 2.2.x or later and Python 3.4 or later
#
#
# Max number of iterations to try before giving up:
limit = 1209600

# If the script fails to find a match for your target, try increasing
# this number. Note that this is equivalent to the maximum number of
# seconds to subtract from the timestamp. The default of 1209600 is 2
# weeks and should be sufficient to find any 4 character or less hex
# string. One year is 31557600 seconds. Longer string lengths require a
# greater number of iterations.

########################################################################
#  ! ! !      DON'T CHANGE ANYTHING FROM THIS POINT ON        !  !  !  #
#  ! ! !      UNLESS YOU REALLY KNOW WHAT YOU'RE DOING.       !  !  !  #
########################################################################

algos = {'rsa', 'rsa1024', 'rsa2048', 'rsa3072', 'rsa4096', 'dsa', 'dsa1024', 'dsa2048', 'ed25519', 'nistp256', 'nistp384', 'nistp521', 'brainpoolP256r1', 'brainpoolP384r1', 'brainpoolP512r1', 'secp256k1'}

# Message prompts for user input
P = ["\nEnter the target hex string you want the key fingerprint to start with.\nIf you want to match a string longer than 4 characters, you'll need to increase to iteration 'limit' value in the script.\n\nEnter hex string target> ","\nChoose the algorithm for the signing key. Valid signing key algorithms are:\n  rsa  rsa1024  rsa2048  rsa3072  rsa4096\n  dsa  dsa1024  dsa2048  dsa3072\nGnuPG also allows elliptic curve key algorithms:\n  ed25519\n  nistp256  nistp384  nistp521\n  brainpoolP256r1  brainpoolP384r1  brainpoolP512r1\n  secp256k1\n(note: some elliptic curve algorithms might not be available in your version of GnuPG)\n\nEnter key algorithm> "]

def hexcheck(target):
    digits = '0123456789abcdef'
    target = target.lower()
    return set(list(target)).issubset(list(digits))

target = input(P[0])
while hexcheck(target) == False:
    print("String contains non-hex digits. Try again.")
    target = input(P[0])
target = target.lower()
algo = input(P[1])
while algo not in algos:
    print("Algorithm not in list. Try again.\n")
    algo = input(P[1])

import hashlib, time, subprocess, uuid, pathlib

# Set user ID and generated file names to random strings.
# This is to ensure none of them already exist
user_id = str(uuid.uuid4())
public_key = str(uuid.uuid4())
secret_key = str(uuid.uuid4())

# Commands to generate, export, then delete the generated keys
cmd1 = ["gpg --quiet --batch --pinentry-mode loopback --passphrase '' --quick-gen-key "+user_id+" "+algo, "gpg --quiet -o "+public_key+" --export "+user_id,"gpg --quiet -o "+secret_key+" --export-secret-keys "+user_id, "gpg --quiet --yes --delete-secret-and-public-keys "+user_id]
for c in cmd1:
    subprocess.call(c, shell=True)


# Functions to read gpg exported key data and list individual packets
def header_info(x):
    if x[0]&64 == 64:
        tag = x[0]&63
        if x[1] < 192: [hlen,plen] = [2,x[1]]
        elif x[1] <= 223: [hlen,plen] = [3,((x[1] - 192) << 8) + x[2] + 192]
        elif x[1] == 255: [hlen,plen] = [5,int.from_bytes(x[2:6],byteorder='big',signed=False)]
    else:
        tag = (x[0]&60)>>2
        if x[0]&3 == 0: [hlen,plen] = [2,x[1]]
        elif x[0]&3 == 1: [hlen,plen] = [3,int.from_bytes(x[1:3],byteorder='big',signed=False)]
        elif x[0]&3 == 2: [hlen,plen] = [5,int.from_bytes(x[1:5],byteorder='big',signed=False)]
    return [tag, hlen, plen]

def splitpackets(x):
    packets = []
    i = 0
    while i < (len(x)-1):
        h = header_info(x[i:i+5])
        tag = h[0]
        packet = x[i:i+h[1]+h[2]]
        i += (h[1]+h[2])
        packets.append([tag,packet])
    return packets


# Rewrite secret_key file without signature packet
with open(secret_key, 'rb') as f:
    key = bytes(f.read())
key = splitpackets(key)
key = b''.join([x[1] for x in key if x[0] in {5,13}])
with open(secret_key, 'wb') as f:
    f.write(key)

# Get public_key packet
with open(public_key,'rb') as f:
    key = bytes(f.read())

# Define header and packet length (subject to adjustment in next step).
hlen = 3
plen = int.from_bytes(key[1:3],byteorder='big',signed=False)

# Make sure public key header is properly formed for calculating the
# fingerprint by verifying the first byte is 0x99. In practice the only
# times this wouldn't be the case is for rsa1024 and elliptic curve
# algorithms whose smaller key size means the packet length can be
# encoded in a single byte.
if key[0] != 0x99:
    # Check that header is "old" format (should be, but just in case...)
    if key[0]&64 == 0:
        hlen = 2
        plen = key[1]
    else:
        # "New" format header. Irregular but not invalid format for a
        # key packet header.
        if key[1] < 192:
            hlen = 2
            plen=key[2]
        elif key[1] <= 223:
            plen = ((key[1] - 192) << 8) + key[2] + 192

# Canonicalize header for fingerprinting. Fingerprint is calculated
# over the packet data with a 3 byte header consisting of 0x99 and a 2-
# byte big endian number that is a count of bytes in the packet data.
h = b'\x99'+plen.to_bytes(2,byteorder='big',signed=False)
key = bytearray(h+key[hlen:hlen+plen])

# Extract current timestamp
timestamp = int.from_bytes(key[4:8],byteorder='big',signed=True)

# Set length of string to match
L = len(target)

# Set the initial hash value and iteration counter.
fingerprint = hashlib.sha1()
fingerprint.update(key)
current = fingerprint.hexdigest()[0:L]
i = 0

# Timer to measure duration of search.
start = time.time()

# Begin search for fingerprint string match
while current != target and i < limit:
    fingerprint = hashlib.sha1()
    timestamp -= 1
    i += 1
    key[4:8] = timestamp.to_bytes(4,byteorder='big',signed=True)
    fingerprint.update(key)
    current = fingerprint.hexdigest()[0:L]

# Stop time for timer.
end = time.time()

if current == target:
    # Success :)
    with open(secret_key,'r+b') as f:
        # Go to start of timestamp in exported secret_key file
        f.seek(hlen+1)
        # Overwrite timestamp with the one found in the while loop
        f.write(bytes(key[4:8]))
    print("\nDone "+str(i)+" iterations. Total time: "+str(end-start)+" seconds\n")
    # List of commands to import key and display fingerprint
    cmd2 = ["gpg --quiet --allow-non-selfsigned-uid --import "+secret_key, "gpg -K "+user_id]
    for c in cmd2:
        subprocess.call(c, shell=True)
    print("\nYOU NEED TO EDIT THIS KEY.\nEnter 'gpg --edit-key "+user_id+"' then use the following commands after the 'gpg>' prompt in the order shown:\n  gpg> adduid       ...add a new user ID by following the prompts.\n  gpg> 1            ...selects the '"+user_id+"' user id\n  gpg> deluid       ...delete the selected user ID then confirm.\n  gpg> change-usage ...toggle usage options until it shows 'Current allowed actions: Sign Certify' then enter Q.\n  gpg> passwd       ...set a password\n  gpg> addkey       ...follow prompts to add encryption subkey\n  gpg> save         ...save the changes made in editing mode")
else:
    # Failure :(
    print("Failed to match "+str(target)+" in "+str(i)+" iterations. Total time: "+str(end-start)+" seconds")

# Remove generated key files
pathlib.Path(public_key).unlink()
pathlib.Path(secret_key).unlink()

The fingerprint is just a SHA1 hash of the public key packet - and this packet contains a timestamp. This means you can generate new fingerprints from the same key by incrementally changing only the timestamp.

The details might sound a little complicated, but it's very fast and easy to do.

The script works by incrementing the key packet timestamp backwards by 1 then feeding the resulting packet into sha1 to check if the fingerprint will begin with start with the chosen hex string for each iteration.

When it finds a fingerprint that starts with hex characters matching the target string, it stops iterating and overwrites the timestamp in the key with the timestamp that will produce the desired fingerprint.

It then imports the new key to gpg and deletes the files created by the script.

Almost done

Now you need to use gpg to edit the key to get it ready for actual use. A new user ID needs to be added, the old (unsigned) user ID needs to be deleted, key usage needs to be set to only "SC" (sign, certify), a password needs to be set, and an encryption subkey needs to be created. These changes then need to be saved.

$ gpg --edit-key <some long uuid>

Look at the script output for the uuid. It will show the full edit-key command which you can copy/paste.

All of the commands that follow are entered in the context of the edit-key menu.

• Add your user ID by entering the following at the gpg> prompt:

adduid

It will prompt you to enter a "Real name", "Email address" and "Comment" (ie, the same stuff gpg does when you normally generate a key). Follow the prompts and enter o when prompted to accept the data you've entered for a user ID.

• Delete the old unsigned userid. Enter 1 to select the first user ID. Then enter:

deluid

It will ask you to confirm deleting the user id. Enter y.

• Change key usage (note that you have to do the adduid step before doing this) by entering the following at the gpg> prompt:

change-usage

It will show Current allowed actions: Sign Certify Encrypt Authenticate and because this is a primary key it should only be Sign and Certify. Enter e to toggle the encrypt ability off, then enter a to toggle the Authenticate ability off. Now it should display Current allowed actions: Sign Certify which is what we want so enter q.

• Set a password.

passwd

A pinentry window will pop up - enter the password you want to use.

• Add an encryption subkey by entering this:

addkey

Then select the type of key, then enter your password when prompted.

• Now, most importantly save the changes you made while editing the key by entering

save

This returns you to the command prompt. You can do this at any time during the key edit process. You now have a fully functional custom fingerprint key.