7. Base 32 Encoding with Extended Hex Alphabet

扩展十六进制字母表的Base32编码

以下对Base32的描述源自 [7]。此编码可称为"base32hex"。此编码不应被视为与"base32"编码相同，也不应仅称为"base32"。此编码被例如NextSECure3 (NSEC3) [10] 使用。

此字母表具有base64和base32字母表所缺乏的一个属性，即当按位比较编码数据时，编码数据保持其排序顺序。

此编码与前一个编码相同，除了字母表。新字母表见表4。

---

Base32Hex字母表

表4: "扩展十六进制" Base32字母表

值  编码  值  编码  值  编码  值  编码
0   0     9   9    18   I    27   R
1   1    10   A    19   J    28   S
2   2    11   B    20   K    29   T
3   3    12   C    21   L    30   U
4   4    13   D    22   M    31   V
5   5    14   E    23   N
6   6    15   F    24   O    填充  =
7   7    16   G    25   P
8   8    17   H    26   Q

字符集组成

0-9:  10个数字       (值 0-9)
A-V:  22个大写字母   (值 10-31)
=:    等号          (填充字符)

特点: 按字典序排列

---

与标准Base32的区别

特性	标准Base32	Base32Hex
字母表	A-Z, 2-7	0-9, A-V
首字符	A (值0)	0 (值0)
最大字符	7 (值31)	V (值31)
排序保持	❌ 否	✅ 是
人类友好	✅ 较好	⚠️ 一般

---

排序保持属性

什么是排序保持？

当比较两个编码后的字符串时，其字典序与原始数据的大小顺序相同。

示例演示

原始数据比较:
Data A: [0x00, 0x00] < Data B: [0x00, 0x01]
                     (A小于B)

标准Base32编码:
A: "AAAA====" < B: "AAAQ===="
   ✅ 排序保持

Base32Hex编码:
A: "00000000" < B: "00040000"
   ✅ 排序保持

但Base32Hex的字典序直接对应数值:
0 < 1 < 2 < ... < 9 < A < B < ... < V
(完全按ASCII顺序)

详细对比

值  标准Base32  Base32Hex
0   A           0
1   B           1
2   C           2
3   D           3
4   E           4
5   F           5
6   G           6
7   H           7
8   I           8
9   J           9
10  K           A
11  L           B
...

标准Base32排序: A < B < C < ... < Z < 2 < 3 < ...
   (字母在前，数字在后) ❌

Base32Hex排序:  0 < 1 < 2 < ... < 9 < A < B < ...
   (完全按ASCII值) ✅

---

实际应用场景

DNSSEC - NSEC3记录

NSEC3使用Base32Hex编码哈希值:

原因:
1. 排序保持 - DNS区域需要保持记录顺序
2. 不区分大小写 - DNS不区分大小写
3. 避免特殊字符 - 不使用 =+/ 等

示例NSEC3记录:
0P9MHAVEQVM6T7VVT5QKT7K4J8Q2JGMQ.example.com.
↑ Base32Hex编码的哈希值

数据库索引

使用场景: 需要对编码数据进行范围查询

示例:
CREATE INDEX idx_hash ON table(base32hex_hash);

SELECT * FROM table 
WHERE base32hex_hash BETWEEN '0000' AND '9999';
↑ 直接使用字符串比较，对应原始数据的范围

文件系统排序

文件名使用Base32Hex:
file_00000001.dat
file_00000002.dat
...
file_0000000A.dat
file_0000000B.dat

优点:
- 自然排序 (按字母顺序 = 按数值顺序)
- 避免 "file_10" 排在 "file_2" 之前的问题

---

编码示例

示例1: 短数据

输入: [0x00]
二进制: 00000000

分割: 00000|000[00]
        0      0
        ↓      ↓
        0      0

Base32Hex: "00======"
标准Base32: "AA======"

比较: '0' < 'A' (ASCII值)

示例2: 递增序列

输入序列:
[0x00] → Base32Hex: "00======"
[0x01] → Base32Hex: "08======"
[0x02] → Base32Hex: "10======"
[0x03] → Base32Hex: "18======"

排序: "00" < "08" < "10" < "18"
✅ 与原始数据顺序一致

示例3: 与标准Base32对比

输入: "Hello"

标准Base32:
"JBSWY3DP"

Base32Hex:
"91IMOR3F"

字典序比较:
'J' (0x4A) vs '9' (0x39)
'J' > '9' 在ASCII中
但两者都正确编码了"Hello"

---

实现代码

Python实现

def base32hex_encode(data):
    """Base32Hex编码"""
    alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUV"
    result = []
    
    for i in range(0, len(data), 5):
        group = data[i:i+5]
        
        # 转换为40位整数
        value = 0
        for byte in group:
            value = (value << 8) | byte
        
        # 补齐
        value <<= (5 - len(group)) * 8
        
        # 提取8个5位组
        for j in range(8):
            if j < (len(group) * 8 + 4) // 5:
                idx = (value >> (35 - j * 5)) & 0x1F
                result.append(alphabet[idx])
            else:
                result.append('=')
    
    return ''.join(result)

def base32hex_decode(encoded):
    """Base32Hex解码"""
    alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUV"
    decode_table = {c: i for i, c in enumerate(alphabet)}
    
    encoded = encoded.upper().rstrip('=')
    result = []
    
    value = 0
    bits = 0
    
    for char in encoded:
        if char not in decode_table:
            raise ValueError(f"非法字符: {char}")
        
        value = (value << 5) | decode_table[char]
        bits += 5
        
        if bits >= 8:
            bits -= 8
            result.append((value >> bits) & 0xFF)
    
    return bytes(result)

Go实现

import (
    "encoding/base32"
)

// Go标准库直接支持Base32Hex
var base32HexEncoding = base32.HexEncoding

func Base32HexEncode(data []byte) string {
    return base32HexEncoding.EncodeToString(data)
}

func Base32HexDecode(encoded string) ([]byte, error) {
    return base32HexEncoding.DecodeString(encoded)
}

---

排序性能优化

数据库索引优化

-- 使用Base32Hex编码的列可以直接索引
CREATE INDEX idx_encoded ON records(base32hex_value);

-- 范围查询高效
SELECT * FROM records
WHERE base32hex_value >= '0000'
  AND base32hex_value < 'A000';
  
-- 排序查询无需额外转换
SELECT * FROM records
ORDER BY base32hex_value;

文件系统操作

# 文件自然排序
ls file_*.dat
file_00000000.dat
file_00000001.dat
...
file_0000000A.dat
file_FFFFFFFF.dat

# 排序正确 (不像Base64那样 + 和 / 会打乱顺序)

---

字母表设计分析

为什么用0-9, A-V?

设计考虑:

1. 排序保持
   0 < 1 < ... < 9 < A < ... < V
   (完美对应ASCII顺序和数值大小)

2. 32个字符
   10个数字 + 22个字母 = 32
   (2^5 = 32，完美映射5位)

3. 避免混淆
   不使用W-Z (超出32个字符)
   
4. 标准化
   使用连续的字符集

与十六进制的关系

十六进制 (Base16):
0-9, A-F (16个字符)

Base32Hex:
0-9, A-V (32个字符)

可以看作是"扩展的十六进制"

---

使用建议

✅ 适合使用Base32Hex的场景

1. 需要排序保持
   - 数据库范围查询
   - 分布式系统分片键
   - B树索引
   
2. DNS相关应用
   - NSEC3记录
   - DNS标签
   
3. 文件系统
   - 需要自然排序的文件名
   - 目录结构组织
   
4. 分布式系统
   - 一致性哈希
   - 分区键

❌ 不适合使用Base32Hex的场景

1. 人类输入
   - 0和O容易混淆
   - 标准Base32更友好
   
2. TOTP密钥
   - 应使用标准Base32
   - 避免数字0和1的混淆
   
3. 需要Base32兼容
   - 如果已有标准Base32数据
   - 两者不兼容

---

常见问题

Q1: Base32Hex与Base32可以互换吗？

A: 不可以。字母表不同，编码结果不同。

标准Base32: "JBSWY3DP"
Base32Hex:  "91IMOR3F"
(相同输入"Hello"，完全不同的输出)

Q2: 为什么不直接使用十六进制？

A: Base32Hex的优势:

1. 不区分大小写
   Base32Hex: "91IMOR3F" = "91imor3f"
   十六进制: 通常区分大小写
   
2. 更紧凑
   相同数据，Base32Hex比十六进制短37.5%
   
3. 更适合DNS
   符合DNS标签规范

Q3: 排序保持有多重要？

A: 对某些应用至关重要:

关键应用:
- DNSSEC (NSEC3必须保持排序)
- 分布式数据库 (范围查询)
- 文件系统 (ls排序)

不重要的应用:
- 一般数据编码
- 传输编码
- 简单存储

---

测试向量

输入: "" (空)
Base32Hex: ""

输入: "f" (0x66)
Base32Hex: "CO======"

输入: "fo" (0x66 0x6F)
Base32Hex: "CPNG===="

输入: "foo" (0x66 0x6F 0x6F)
Base32Hex: "CPNMU==="

输入: "foob" (0x66 0x6F 0x6F 0x62)
Base32Hex: "CPNMUOG="

输入: "fooba" (0x66 0x6F 0x6F 0x62 0x61)
Base32Hex: "CPNMUOJ1"

输入: "foobar" (0x66 0x6F 0x6F 0x62 0x61 0x72)
Base32Hex: "CPNMUOJ1E8======"

---

相关规范

• RFC 4648 §6 - 标准Base32
• RFC 5155 - DNSSEC NSEC3
• RFC 7218 - DNS Zone Hash