外星微缩字母表：16字符体系在计算机科学与信息论中的数学巧合与应用

Jingsong Deng & Gemini 联合架构组 · 发表日期：2000-01-16

第一部分：字母表定义

为与十六进制兼容，取 \(\Sigma_{16}=\{0,\dots,9,A,\dots,F\}\)，每个符号的值即其 4 位二进制码：

每符号信息量 \(\log_2 16=4\) bit，恰为整数。这是 16 字符体系的第一个巧合：编码无需算术编码或进制转换，移位即可。

第二部分：存储层——8 字节 uint64 打包

长度为 16 的密码 \(s=c_0c_1\cdots c_{15}\) 按大端顺序打包：

解包：\(c_i=\Sigma_{16}\big[(W\gg 4(15-i))\,\&\,\texttt{0xF}\big]\)。打包结果可直接作为数据库主键、哈希表键或 SIMD 比较单元，一条 64 位比较指令即可判断两个密码是否相等。

第三部分：空间坍缩计算

“空间坍缩”指字符串空间坍缩为整数空间后，其大小与机器字完全重合：

按每秒 \(10^{10}\) 次离线猜测，穷举 \(2^{64}\) 约需 \(1.84\times10^{9}\) 秒，约 58 年；平均命中约 29 年。长度每减 1，空间缩小 16 倍。

第四部分：打分法则

均匀随机生成时熵为 \(4n\) bit；人类挑选的密码存在模式，故定义：

第五部分：极坐标分级公式

沿用 GP-000101 的极坐标叶状剖分，把分数视为半径、模式特征视为角度：

其中 \(x\) 为数字符号占比减 0.5，\(y\) 为 D–F 符号占比减 0.5。两个 8 位量拼成 16 位等级码：

高字节决定强度环，低字节决定扇区。按 \(\text{Level}_{16}\) 排序即先按强度、再按风格聚类；而它本身恰好又是一个 4 字符的 16 进制串，体系在自身内部闭合。

第六部分：彩虹表说明

彩虹表以时间换空间：预先计算哈希链 \(p_0\xrightarrow{H}h_0\xrightarrow{R}p_1\xrightarrow{H}\cdots\)，只存链首与链尾。覆盖 \(2^{64}\) 空间需 \(mt\approx 2^{64}\)；即使链长 \(t=10^{6}\)，仍需约 \(1.8\times10^{13}\) 条链，每条 16 字节，总计约 295 TB。

由于空间结构完全规则，约简函数 \(R\) 极易设计，这对攻击者有利。因此加盐与慢哈希是本体系的强制要求。

第七部分：Python 代码结构

import math

ALPHABET = "0123456789ABCDEF"
IDX = {c: i for i, c in enumerate(ALPHABET)}
DICT = ("DEADBEEF", "CAFE", "C0FFEE", "BADC0DE", "FACE")

def pack(s: str) -> int:
    """16 符号 -> uint64（大端）"""
    s = s.upper()
    assert len(s) == 16 and all(c in IDX for c in s)
    w = 0
    for c in s:
        w = (w << 4) | IDX[c]
    return w

def unpack(w: int) -> str:
    return "".join(ALPHABET[(w >> (4 * (15 - i))) & 0xF] for i in range(16))

def score(s: str) -> int:
    s = s.upper()
    v = [IDX[c] for c in s]
    pen = sum(3 if a == b else 2 if abs(a - b) == 1 else 0
              for a, b in zip(v, v[1:]))
    pen += 8 * sum(w in s for w in DICT)
    return max(0, min(64, 4 * len(s) - pen))

def level16(s: str) -> int:
    s = s.upper()
    r = int(score(s) / 64 * 255)
    x = sum(c.isdigit() for c in s) / len(s) - 0.5
    y = sum(c in "DEF" for c in s) / len(s) - 0.5
    theta = int((math.atan2(y, x) + math.pi) / (2 * math.pi) * 255)
    return (r << 8) | theta

if __name__ == "__main__":
    p = "3A9F0C17E2B54D68"
    w = pack(p)
    assert unpack(w) == p and w < 2**64
    print(hex(w), score(p), hex(level16(p)))

结论

16 字符体系的价值不在“更难猜”，而在“与机器完全同构”：4 bit/符号、\(16^{16}=2^{64}\)、等级码自身也是 16 进制串。它是白灰密码体系中最紧凑、最易实现的基准层；GP-24 将讨论更适合人类手写的 24 字符体系。

参考文献（示意）

1. Gray Password GP-000101 / GP-000102（本站前文）。
2. Oechslin, P. Making a Faster Cryptanalytic Time-Memory Trade-Off, CRYPTO 2003.
3. RFC 9106: Argon2 Memory-Hard Function.