How a PGP Message Is Built, and Radix-64

The mapping is exact where it matters. A Literal Data packet holds precisely the textbook's message component: a one-byte format, the file name, a four-byte date, and the data. A version 4 Signature packet holds the signature component's four fields, as the run below shows field by field: a creation time, the issuer's key ID, the left sixteen bits of the hash, and the signature values.

Radix-64

Radix-64 turns arbitrary bytes into printable characters. OpenPGP called it radix-64 for years; RFC 9580 simply calls it base64, which it always was.

The rule. Take the data three bytes at a time. Three bytes are 24 bits. Cut the 24 bits into four groups of six bits. Each six-bit group is a number from 0 to 63, and each number is written as one symbol from a fixed alphabet of 64:

Worked by hand. RFC 9580's sample signature packet begins with the three bytes 88, 5E and 04 in hexadecimal.

Written one after another the 24 bits are 100010000101111000000100. Cut into sixes:

So 88 5E 04 becomes iF4E, and that is exactly how the armored signature in RFC 9580 begins.

When the length is not a multiple of three. The last group is padded with zero bits and the missing symbols are written as =. One leftover byte gives two symbols and ==; two leftover bytes give three symbols and =. Every four symbols therefore still stand for exactly three bytes.

The cost. Four symbols for every three bytes is an increase of one third: the 96-byte signature packet becomes 128 symbols. Line breaks add a little more; RFC 9580 limits a line of base64 data to 76 characters.

Armor. Radix-64 data is wrapped in ASCII armor: a header line such as -----BEGIN PGP MESSAGE-----, optional header lines such as Version:, a blank line, the base64 lines, and a matching -----END PGP MESSAGE----- line. RFC 4880 added a checksum line: a 24-bit CRC of the decoded bytes, itself base64-encoded after an = sign.

The checksum is on its way out. RFC 9580 s.6.1 says the CRC-24 footer "SHOULD NOT be generated" except for compatibility, and must not be rejected when present, missing or wrong. Its reason: computing it "incurs a significant cost, while providing no meaningful integrity protection". A CRC catches transmission errors, not tampering, and the signature and the encryption's own integrity check already detect both.

The run: two published messages, taken apart

The listing works radix-64 by hand and against Python's own base64, then takes apart two messages published in the OpenPGP standards: the armored example of RFC 4880 s.6.6, and the sample version 4 signature of RFC 9580 Appendix A.2, which it verifies with the sample key of A.1.

# Inside two published OpenPGP messages: radix-64 by hand, the packets, and the signature.
import base64, datetime, hashlib, zlib

ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'

def radix64(data):                         # three bytes in, four symbols out
    out = []
    for i in range(0, len(data), 3):
        chunk = data[i:i + 3]
        n = int.from_bytes(chunk + bytes(3 - len(chunk)), 'big')
        symbols = [ALPHABET[(n >> shift) & 63] for shift in (18, 12, 6, 0)]
        out += symbols[:len(chunk) + 1] + ['='] * (3 - len(chunk))
    return ''.join(out)

def crc24(data):                           # RFC 9580 s.6.1.1, translated from its C
    crc = 0xB704CE
    for byte in data:
        crc ^= byte << 16
        for _ in range(8):
            crc <<= 1
            if crc & 0x1000000:
                crc ^= 0x864CFB
    return crc & 0xFFFFFF

def dearmor(text):
    lines = [l for l in text.strip().split('\n') if l and not l.startswith('-----')]
    body = [l for l in lines if ':' not in l and not l.startswith('=')]
    check = [l[1:] for l in lines if l.startswith('=')]
    return base64.b64decode(''.join(body)), check

def packets(data):                         # (tag, body) per packet; one-byte lengths only,
                                           # which is all these two small messages use
    out, i = [], 0
    while i < len(data):
        head = data[i]
        if head & 0x40:                    # OpenPGP format: tag in the low six bits
            tag, n, i = head & 0x3F, data[i + 1], i + 2
        else:                              # legacy format: tag in bits 5 to 2
            tag, n, i = (head >> 2) & 0x0F, data[i + 1], i + 2
        out.append((tag, data[i:i + n]))
        i += n
    return out

# ---- 1. radix-64, the first three bytes by hand -----------------------------------------
sig_armor = """-----BEGIN PGP SIGNATURE-----

iF4EABYIAAYFAlX5X5UACgkQjP3hIZeWWpr2IgD/VvkMypjiECY3vZg/2xbBMd/S
ftgr9N3lYG4NdWrtM2YBANCcT6EVJ/A44PV/IgHYLy6iyQMyZfps60iehUuuYbQE
-----END PGP SIGNATURE-----"""
sig_bytes, _ = dearmor(sig_armor)
first = sig_bytes[:3]
bits = ''.join(format(b, '08b') for b in first)
print('RADIX-64, BY HAND')
print('  three bytes          ', ' '.join('%02X' % b for b in first))
print('  as 24 bits           ', ' '.join(bits[i:i + 8] for i in (0, 8, 16)))
print('  cut into four sixes  ', ' '.join(bits[i:i + 6] for i in (0, 6, 12, 18)))
print('  as numbers           ', ' '.join(str(int(bits[i:i + 6], 2)) for i in (0, 6, 12, 18)))
print('  as symbols           ', ' '.join(ALPHABET[int(bits[i:i + 6], 2)] for i in (0, 6, 12, 18)))
print('  this program and Python\'s base64 agree on all %d bytes:' % len(sig_bytes),
      radix64(sig_bytes) == base64.b64encode(sig_bytes).decode())
print('  %d bytes became %d symbols, %.4f times as many' % (
      len(sig_bytes), len(radix64(sig_bytes)), len(radix64(sig_bytes)) / len(sig_bytes)))
for n in (1, 2, 3, 4, 5):
    print('  %d byte(s) -> %s' % (n, radix64(bytes(range(65, 65 + n)))))

# ---- 2. RFC 4880 s.6.6: an armored message, taken apart ---------------------------------
msg_armor = """-----BEGIN PGP MESSAGE-----
Version: OpenPrivacy 0.99

yDgBO22WxBHv7O8X7O/jygAEzol56iUKiXmV+XmpCtmpqQUKiQrFqclFqUDBovzS
vBSFjNSiVHsuAA==
=njUN
-----END PGP MESSAGE-----"""
data, check = dearmor(msg_armor)
print()
print('RFC 4880\'S EXAMPLE MESSAGE, TAKEN APART')
print('  checksum line =%s, CRC-24 of the %d decoded bytes gives =%s'
      % (check[0], len(data), base64.b64encode(crc24(data).to_bytes(3, 'big')).decode()))
tag, body = packets(data)[0]
print('  outer packet: tag %d, Compressed Data; algorithm %d, which is ZIP' % (tag, body[0]))
inner = zlib.decompress(body[1:], -15)
tag, lit = packets(inner)[0]
name_len = lit[1]
print('  inside it  : tag %d, Literal Data' % tag)
print('    format   ', repr(chr(lit[0])), '(binary)')
print('    file name', repr(lit[2:2 + name_len].decode()))
print('    date     ', int.from_bytes(lit[2 + name_len:6 + name_len], 'big'))
print('    data     ', repr(lit[6 + name_len:].decode()))

# ---- 3. RFC 9580 A.2: a version 4 signature, field by field -----------------------------
tag, s = packets(sig_bytes)[0]
hashed_len = int.from_bytes(s[4:6], 'big')
hashed = s[6:6 + hashed_len]
u = 6 + hashed_len
unhashed_len = int.from_bytes(s[u:u + 2], 'big')
unhashed = s[u + 2:u + 2 + unhashed_len]
left16 = s[u + 2 + unhashed_len:u + 4 + unhashed_len]
mpis = s[u + 4 + unhashed_len:]
created = int.from_bytes(hashed[2:6], 'big')
print()
print('RFC 9580\'S SAMPLE SIGNATURE PACKET, FIELD BY FIELD (%d bytes)' % len(sig_bytes))
print('  packet tag           %d, Signature' % tag)
print('  version              %d' % s[0])
print('  signature type       0x%02X, a signature of a binary document' % s[1])
print('  public-key algorithm %d, EdDSA (legacy form)' % s[2])
print('  hash algorithm       %d, SHA2-256' % s[3])
print('  hashed subpacket     type %d, creation time %s UTC' % (
      hashed[1], datetime.datetime.fromtimestamp(created, datetime.timezone.utc)
      .strftime('%Y-%m-%d %H:%M:%S')))
print('  unhashed subpacket   type %d, issuer key ID %s'
      % (unhashed[1], unhashed[2:].hex().upper()))
print('  left 16 bits of hash %s' % left16.hex())
print('  signature            two numbers, r and s, %d bytes' % len(mpis))

trailer = s[:6 + hashed_len]
m = b'OpenPGP' + trailer + b'\x04\xff' + len(trailer).to_bytes(4, 'big')
d = hashlib.sha256(m).digest()
print('  hashed input rebuilt equals RFC 9580\'s m:',
      m.hex() == '4f70656e504750040016080006050255f95f9504ff0000000c')
print('  its SHA2-256 begins with the packet\'s   :', d[:2].hex(), d[:2] == left16)

# ---- Ed25519 verification, RFC 8032 s.5.1 ---------------------------------------------
P = 2**255 - 19
L = 2**252 + 27742317777372353535851937790883648493
D = -121665 * pow(121666, -1, P) % P
def sha512(b): return hashlib.sha512(b).digest()
def padd(A, B):
    x1, y1, z1, t1 = A; x2, y2, z2, t2 = B
    a = (y1 - x1) * (y2 - x2) % P; b = (y1 + x1) * (y2 + x2) % P
    c = 2 * t1 * t2 * D % P; d = 2 * z1 * z2 % P
    e, f, g, h = b - a, d - c, d + c, b + a
    return (e * f % P, g * h % P, f * g % P, e * h % P)
def pmul(k, A):
    Q = (0, 1, 1, 0)
    while k:
        if k & 1: Q = padd(Q, A)
        A = padd(A, A); k >>= 1
    return Q
def recover_x(y, sign):
    x2 = (y * y - 1) * pow(D * y * y + 1, -1, P) % P
    x = pow(x2, (P + 3) // 8, P)
    if (x * x - x2) % P: x = x * pow(2, (P - 1) // 4, P) % P
    if (x * x - x2) % P: return None
    if x & 1 != sign: x = P - x
    return x
gy = 4 * pow(5, -1, P) % P
gx = recover_x(gy, 0)
G = (gx, gy, 1, gx * gy % P)
def compress(A):
    x, y, z, _ = A; zi = pow(z, -1, P); x, y = x * zi % P, y * zi % P
    return int.to_bytes(y | ((x & 1) << 255), 32, 'little')
def decompress(s):
    y = int.from_bytes(s, 'little'); sign = y >> 255; y &= (1 << 255) - 1
    x = recover_x(y, sign)
    return None if x is None else (x, y, 1, x * y % P)
def expand(secret):
    h = sha512(secret); a = int.from_bytes(h[:32], 'little')
    a &= (1 << 254) - 8; a |= 1 << 254
    return a, h[32:]
def public_key(secret): return compress(pmul(expand(secret)[0], G))
def sign(secret, msg):
    a, prefix = expand(secret); A = compress(pmul(a, G))
    r = int.from_bytes(sha512(prefix + msg), 'little') % L
    R = compress(pmul(r, G))
    h = int.from_bytes(sha512(R + A + msg), 'little') % L
    return R + int.to_bytes((r + h * a) % L, 32, 'little')
def point_eq(A, B):
    return (A[0] * B[2] - B[0] * A[2]) % P == 0 and (A[1] * B[2] - B[1] * A[2]) % P == 0
def verify(public, msg, sig):
    A = decompress(public); R = decompress(sig[:32]); s = int.from_bytes(sig[32:], 'little')
    if A is None or R is None or s >= L: return False
    h = int.from_bytes(sha512(sig[:32] + public + msg), 'little') % L
    return point_eq(pmul(s, G), padd(R, pmul(h, A)))

q = bytes.fromhex('403f098994bdd916ed4053197934e4a87c80733a1280d62f8010992e43ee3b2406')
r = mpis[2:34]
s_ = mpis[36:68]
print('  Ed25519 verifies with the key of RFC 9580 A.1:', verify(q[1:], d, r + s_))
print('  and fails for the text "OpenPGP!"            :',
      verify(q[1:], hashlib.sha256(b'OpenPGP!' + m[7:]).digest(), r + s_))

What the run establishes, in order.

Radix-64 is exactly the rule above. 88 5E 04 becomes the six-bit numbers 34, 5, 56 and 4, and the symbols i, F, 4 and E. The program's own encoder agrees with Python's base64 on all 96 bytes, and 96 bytes become 128 symbols, 1.3333 times as many. The five short examples show the padding: one leftover byte ends in ==, two in =.

RFC 4880's example message comes apart into the textbook's message component. Its checksum line =njUN is exactly the CRC-24 the program computes. The outer packet is tag 8, Compressed Data, algorithm 1, ZIP; decompressed, it holds a tag 11 Literal Data packet whose fields are a format (b, binary), a file name (_CONSOLE), a date (0) and the data, the sentence "Can't anyone keep a secret around here?".

RFC 9580's sample signature carries the signature component's four fields. Version 4, a signature of a binary document, EdDSA, SHA2-256; a hashed subpacket giving the creation time, 16 September 2015 at 12:24:53 UTC; an unhashed subpacket giving the issuer's key ID, 8CFDE12197965A9A; the left sixteen bits of the hash, f622; and the signature values.

The digest is rebuilt and the signature verified. The program rebuilds the exact bytes that were hashed, the data OpenPGP followed by the signature's own hashed fields and a trailer, and they equal the value RFC 9580 prints. Their SHA2-256 begins with f622, the two octets the packet carries in the clear. The Ed25519 signature verifies with the sample key, and fails for the text OpenPGP!.

Why the creation time is hashed and the key ID is not. The creation time is inside the hashed subpackets, so it is covered by the signature and cannot be changed. The issuer key ID is in the unhashed area: it is only a hint about which key to use, and changing it could only make verification fail, never make a forgery pass.

Distinctions that carry marks

What beginners get wrong here

Calling radix-64 encryption. It is an encoding that anyone can reverse, and it hides nothing.

Getting the expansion backwards. Three bytes become four symbols: the encoded form is one third larger, not one quarter.

Thinking the two leading octets are a security feature. They are sent in the clear and prove nothing; they only let the recipient abandon a wrong key or a damaged message cheaply.

Forgetting the file name and timestamp in the message component. They are part of the Literal Data packet, as RFC 4880's example shows.

Treating the CRC-24 line as integrity protection. It detects accidental damage, and RFC 9580 now says it should not be generated at all.

Quick revision

• Message component: file name, timestamp, data (a Literal Data packet, tag 11).
• Signature component: timestamp, key ID of the sender's public key, leading two octets of the digest, the digest signed with the sender's private key (a Signature packet, tag 2).
• Session key component: key ID of the recipient's public key, session key encrypted with it (tag 1).
• Signature and message are compressed (tag 8), encrypted with the session key (tag 18), and the whole is converted to radix-64.
• Radix-64: 3 bytes, 24 bits, 4 groups of 6, 4 symbols from A-Z a-z 0-9 + /; = pads; one third larger; lines at most 76 characters.
• Worked: 88 5E 04 is iF4E. RFC 4880's checksum =njUN is a CRC-24, which RFC 9580 says should not be generated.

Test yourself

1. Draw the general format of a PGP message and state what each field is for. The session key component holds the key ID of the recipient's public key, saying which of the recipient's private keys to use, and the session key encrypted with that public key. The signature component holds a timestamp, the key ID of the sender's public key, the leading two octets of the message digest as a quick check, and the digest encrypted with the sender's private key, which is the signature. The message component holds the file name, a timestamp and the data. The signature and message components are compressed and encrypted with the session key, and the whole message is converted to radix-64.

2. Convert the bytes 88 5E 04 (hexadecimal) to radix-64, showing the working. In binary the three bytes are 10001000, 01011110 and 00000100, which run together as the 24 bits 100010000101111000000100. Cut into four groups of six they are 100010, 000101, 111000 and 000100, which are 34, 5, 56 and 4. In the radix-64 alphabet 34 is i, 5 is F, 56 is 4 and 4 is E, so the result is iF4E.

3. By how much does radix-64 enlarge data, and why does PGP use it anyway? Every three bytes become four symbols, an increase of one third, plus a little for line breaks. PGP uses it because signed and encrypted output is arbitrary binary data and many mail systems carry only printable text; and since the message was compressed first, the result is usually still smaller than the original text.

4. Why does the signature carry the leading two octets of the message digest? So that the recipient can compare them with the first two bytes of the digest it computes and detect a wrong key or a damaged message immediately, before performing the costly public-key verification. They are sent in the clear and provide no security by themselves.

5. What does RFC 9580 say about the CRC-24 checksum, and why? It says the CRC-24 footer should not be generated except for compatibility with implementations that require it, and that a receiver must not reject a message whose footer is present, missing or wrong. The reason it gives is that computing the checksum costs time while providing no meaningful integrity protection, since a CRC detects accidental errors but not deliberate tampering.

6. In RFC 9580's sample signature, which field is protected by the signature and which is not, and why does it matter? The creation time is in the hashed subpackets, so it is covered by the signature and cannot be altered without the signature failing. The issuer key ID is in the unhashed area; it is only a hint about which key to try, and altering it could only cause verification to fail, never make a forged signature verify.