PF1 encoding for PGP fingerprints.

PF1Coder.java

// PF1-encoding for PGP fingerprints; optimized to fit
// within a Version 2 QR code using M-level error-correction
//
// Format is simple.
// PF1:<32 characters -- Base32 (rfc4648) encoded 160 bit fingerprint>
//
// To test:
//
// $ java PF1Coder encode <40-character hex fingerprint>
// PF1:<....>
//
// $ java PF1Coder decode PF1:<.....>
// <hex fingerprint>

import java.util.Random; // only needed for testing.

public class PF1Coder
{
    // rfc4648
    private final static char[] ENCODE =
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567".toCharArray();

    public static byte[] decode(char[] in)
    {
        if (in.length != 32) {
            throw new IllegalArgumentException("bad length: "+in.length);
        }

        byte[] ret = new byte[20];
        // go through base32 40 bits (8 characters) at a time.
        for (int i=0; i<in.length; i+= 8) {
            long tmp =
                (decodeBase32(in[i+0]) << 35) |
                (decodeBase32(in[i+1]) << 30) |
                (decodeBase32(in[i+2]) << 25) |
                (decodeBase32(in[i+3]) << 20) |
                (decodeBase32(in[i+4]) << 15) |
                (decodeBase32(in[i+5]) << 10) |
                (decodeBase32(in[i+6]) << 5) |
                (decodeBase32(in[i+7]) << 0);
            int idx = i/8*5;
            ret[idx+0] = (byte) ((tmp >> 32) & 0xff);
            ret[idx+1] = (byte) ((tmp >> 24) & 0xff);
            ret[idx+2] = (byte) ((tmp >> 16) & 0xff);
            ret[idx+3] = (byte) ((tmp >> 8) & 0xff);
            ret[idx+4] = (byte) ((tmp >> 0) & 0xff);
        }
        return ret;
    }

    private final static long decodeBase32(char c)
    {
        if ((c >= 'A') && (c <= 'Z')) {
            return (long) (c - 'A');
        }
        if ((c >= '2') && (c <= '7')) {
            return (long) (26 + c - '2');
        }
        throw new IllegalArgumentException("bad base32: '"+c+"'");
    }

    public static char[] encode(byte[] in)
    {
        if (in.length != 20) {
            throw new IllegalArgumentException("bad length: "+in.length);
        }
        char[] ret = new char[32];

        long tmp;

        // Go through fingerprint 40 bits (5 bytes) at a time.
        for (int i=0; i<in.length; i+= 5) {
            tmp =
                (long) (in[i + 0] & 0xff) << 32 |
                (long) (in[i + 1] & 0xff) << 24 |
                (long) (in[i + 2] & 0xff) << 16 |
                (long) (in[i + 3] & 0xff) << 8  |
                (long) (in[i + 4] & 0xff);

            // output 8 base32 characters for these
            // 5 bytes
            int idx = i/5*8;
            ret[idx + 0] = ENCODE[(int) (tmp >> 35) & 0x1f];
            ret[idx + 1] = ENCODE[(int) (tmp >> 30) & 0x1f];
            ret[idx + 2] = ENCODE[(int) (tmp >> 25) & 0x1f];
            ret[idx + 3] = ENCODE[(int) (tmp >> 20) & 0x1f];
            ret[idx + 4] = ENCODE[(int) (tmp >> 15) & 0x1f];
            ret[idx + 5] = ENCODE[(int) (tmp >> 10) & 0x1f];
            ret[idx + 6] = ENCODE[(int) (tmp >> 5) & 0x1f];
            ret[idx + 7] = ENCODE[(int) (tmp >> 0) & 0x1f];
        }
        return ret;
    }

    private final static void usage()
    {
        System.err.println("Usage:");
        System.err.println("  PF1Coder encode <hex fingerprint>");
        System.err.println("      or");
        System.err.println("  PF1Coder decode <PF1 fingerprint>");
        System.exit(1);
    }

    public static void main(String args[])
    {
        if (args.length != 2) {
            usage();
        }
        else if ("encode".equals(args[0])) {
            System.out.println(doEncode(args[1]));
        }
        else if ("decode".equals(args[0])) {
            System.out.println(doDecode(args[1]));
        }
        else if ("test".equals(args[0])) {
            runTest(Integer.parseInt(args[1]));
        }
        else {
            usage();
        }
    }

    public final static String doEncode(String hex)
    {
        if (hex.length() != 40) {
            throw new RuntimeException("bad length: "+hex.length());
        }

        byte[] in = new byte[20];

        for (int i=0; i<40; i+=2) {
            in[i/2] = (byte) Integer.parseInt(hex.substring(i, i+2), 16);
        }
        return "PF1:"+new String(encode(in));
    }

    public static String doDecode(String pf1)
    {
        if (pf1.length() != 36) {
            throw new RuntimeException("bad length: "+pf1.length());
        }

        char[] in = pf1.substring(4).toCharArray();
        byte[] decoded = decode(in);

        StringBuilder sb = new StringBuilder();
        for (int i=0; i<20; i++) {
            int v = ((int) decoded[i] & 0xff);
            if (v < 0x10) {
                sb.append("0");
            }
            sb.append(Integer.toHexString(v));
        }
        return sb.toString();
    }

    public static void runTest(int count)
    {
        Random r = new Random();

        // Test by ensuring that decode and encode
        // are symmetric.
        byte[] test_fp = new byte[20];
        for (int i=0; i<count; i++) {
            r.nextBytes(test_fp);
            char[] pf1 = encode(test_fp);
            byte[] decode_fp = decode(pf1);
            for (int j=0; j<20; j++) {
                if (decode_fp[j] != test_fp[j]) {
                    throw new RuntimeException(new String(pf1));
                }
            }
            System.out.println(pf1);
        }            
    }    
}

this is really great! should be quite easy to incorporate into our apps. I think we might also want to do a OF1: for OTR fingerprint scanning. One question: why not use the base44 since the QR reduced set has 44 chars?

.hc

The real answer is that I found it too fiddly to deal with base44 :-) but you're quite right of course. It should gain another 2-3 characters (log_44(2^160) ~ 29.3, down from 32)

However, that didn't seem enough to get it past the next interesting breakpoint (29 characters, for Q-level error-correction) so I stuck with base32.

By the same token, I should say that straight upper-case hex-coding with a smaller prefix -- say, PF1:<40 char hex> will also get it into a version 2 qrcode, though at the L-level (7%) error correction. The base32 encoding is interesting only because this just squeaks it into the M-level (15%) error correction area. I haven't done enough tests to see whether this increased error-correction is actually useful; but since base32 is itself a bit more fiddly than hex encoding, figured I'd also point out this tradeoff.