3. 密码算法实现基础

在密码性能优化中，第一步不是急着换指令集或改并行策略，而是先看清三类算法在代码层面“长什么样”。对称加密、哈希、公钥算法虽然都属于密码学，但它们的实现结构、数据依赖方式和计算瓶颈差异极大。只有把典型实现结构拆开，才能准确判断热点函数落在哪里，避免把优化预算花在无关紧要的循环上。

对称加密：分组迭代与轮函数是主战场

以 AES-128 为例，典型实现结构可以概括为“密钥扩展 + 分组迭代 + 模式封装”。密钥扩展把 16 字节主密钥扩展成 11 组轮密钥；分组迭代对每个 16 字节数据块执行 10 轮变换，每轮包含 SubBytes、ShiftRows、MixColumns、AddRoundKey。若采用查表实现，SubBytes 和 MixColumns 常被合并为 T 表查表，每轮 4 次查表、4 次异或；若采用 AES-NI 指令，则整轮由 aesenc 一条指令完成。

热点通常集中在轮函数循环体。以 CBC 模式加密 1 MB 数据为例，数据被切成 65536 个 16 字节块，每个块都要串行依赖前一块密文，因此并行度低，热点就是 aes_encrypt_block 本身。若换成 CTR 模式，块之间无依赖，热点会转移到计数器生成与异或操作，此时优化重点从轮函数转向内存带宽和并行调度。

/* AES-128 轮函数核心（查表实现示意） */
for (round = 1; round < 10; round++) {
    t0 = Te0[s0>>24] ^ Te1[(s1>>16)&0xff] ^
         Te2[(s2>>8)&0xff]  ^ Te3[s3&0xff] ^ rk[4*round];
    /* ... 其余三列同理 ... */
}

哈希算法：压缩函数与消息扩展的链式结构

SHA-256 的典型实现结构是“消息填充 + 分块压缩 + 链值迭代”。消息先填充到 512 位整数倍，每个 512 位块经过 64 轮压缩函数，每轮使用一个 32 位字 W[t] 和一个轮常量 K[t]。W[t] 由消息扩展生成：前 16 个字直接取自消息块，后 48 个字由递推公式计算。压缩函数内部包含 6 个逻辑运算和 2 个加法，链值 H0~H7 在每块结束后更新。

热点函数通常是 sha256_transform，其中消息扩展和 64 轮循环各占相当比例。若用 SHA-NI 指令，压缩函数可大幅加速，但消息扩展仍需软件完成。对于 HMAC-SHA256，热点还包括内外两次哈希的填充块处理，尤其是密钥长度超过 64 字节时先做一次哈希的开销。

公钥算法：大数模幂与椭圆曲线点乘

RSA 的典型实现结构是“密钥生成 + 模幂 + 填充”。加密/验签使用小指数 e（如 65537），模幂只需 17 次模乘；解密/签名使用私钥 d，模幂需要约 2048 次模乘，是真正的热点。模幂内部又分解为模乘和模约减，模乘的优化（如 Montgomery 乘法）直接决定整体性能。

ECC 的典型实现结构是“标量乘 + 点加 + 倍点”。以 P-256 为例，标量乘 kP 需要约 256 次倍点和 128 次点加，每次点加/倍点又包含若干模乘、模平方和模逆。模逆开销远大于模乘，因此常用 Jacobian 坐标避免每步求逆，只在最后转回仿射坐标时做一次模逆。热点函数通常是 point_mul 和 mod_mul。

如何识别热点函数与计算密集型操作

识别热点不能靠猜，要结合 profiling 工具和算法结构判断。常用手段包括 perf record、gprof、VTune 或语言级 profiler。以 OpenSSL 为例，用 perf top 观察 RSA-2048 签名，通常看到 bn_mul_mont 和 BN_mod_mul_montgomery 占据大部分采样；观察 AES-128-CBC 加密，则 AES_encrypt 或 aesni_encrypt 是主要入口。

判断计算密集型操作时，可以看三个特征：第一，是否处于最内层循环且被反复调用；第二，是否包含大量乘法、模运算或查表；第三，是否受数据依赖限制而无法并行。例如 SHA-256 的 64 轮循环每轮都依赖前一轮结果，属于典型串行热点；而 CTR 模式的 AES 块之间无依赖，热点虽在轮函数，但可通过多缓冲和指令级并行掩盖延迟。

三类算法的热点对比与优化切入点

需要强调的是，热点识别必须结合具体模式和参数。同样是 AES，CBC 和 GCM 的热点就不同：CBC 的热点在分组加密本身，GCM 的热点还包括 GHASH 的有限域乘法。同样是 RSA，公钥操作和私钥操作的开销相差两个数量级。只有把实现结构、调用频率和 profiler 数据三者对齐，才能把优化力量集中在真正影响性能的函数上。