记一次DES算法Java实现的优化

Java DES 性能优化 密码学
发布日期:   2026-09-13
更新日期:   2026-09-13
文章字数:   4.5k
阅读时长:   19 分
阅读次数:  

前情提要

Des 是本仓库里一套纯 Java 手写的 DES 加解密工具，没有用 JCE，也没有引入任何第三方加密库。用途很单一：把一批 密文,用户名长度,密码长度 的记录批量解密成 用户名,密码。

代码自同一份 JavaScript 版 DES 移植而来，因此仓库里躺着两份实现：

根目录 Des.java（957 行） src/Des.java（315 行）
内部表示 int[] + 裸 List，逐行直译风格 byte[] + StringBuilder + ArrayList<byte[]>
方向 strEnc 和 strDec 只有 strDec
置换表 逐项硬编码赋值 indices 数组 + 循环
其它 —— switch fallthrough 选密钥段、@Contract 注解

两份的算法行为完全一致，连那处非标准的 PC-1 都一致，只是写法不同。不过正是这个写法差异，决定了后面 4 倍的性能差距——这是后话。

批量任务的开销结构是这样的：密文以 16 位十六进制为一个分组，一行密文是 2 个分组、3 段密钥，所以每行要调用 6 次单分组解密 dec()。

加线程没什么用

遇到慢，第一反应当然是并发。CasDec 用 8 线程池逐行处理，看起来很像那么回事。实测下来（5 万行输入）：

线程数 总耗时 相对 1 线程
1 3890 ms 1.00×
2 2869 ms 1.36×
4 2759 ms 1.41×
8 2975 ms 1.31×
8（去掉无意义的 .parallel()） 3034 ms 1.28×
16 2774 ms 1.40×

8 线程比 4 线程还慢，16 线程也毫无起色。为了排除”锁竞争”这个头号嫌疑，把去重和写文件的共享状态整个去掉，只保留解密，结果仍然只有 1.45×（1 线程 4085 ms → 8 线程 2823 ms）。

也就是说，那堆 synchronized 和 ConcurrentHashMap 是背锅的。

瓶颈是分配

排除了锁，第二嫌疑是 GC。-Xlog:gc 打出来的是：

1
2
gc1.log: GC 暂停次数=32, 累计暂停=84 ms
gc8.log: GC 暂停次数=22, 累计暂停=160 ms   ← 相对 3~4 秒的总时间可以忽略

暂停占比极小，也不是 GC 的锅。那就上 com.sun.management.ThreadMXBean#getThreadAllocatedBytes 直接量分配：

测量项 结果
generateKeys（密钥编排） 1.948 µs/次，3488 B/次
dec()（单分组解密，含密钥编排） 12.492 µs/块，65,968 B/块
→ dec 的单线程分配速率 5.28 GB/s
strDec（1 块密文，整条路径） 19.147 µs/块，72,981 B/块，52,227 块/s

一个 DES 分组的输入输出各只有 64 位，却产生 66 KB 垃圾，比例约 8000 : 1。原因很直白，每个置换函数都在 new int[...]：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 根 Des.java:492  dec()
public int[] dec(int[] dataByte, int[] keyByte) {
    int[][] keys = generateKeys(keyByte);     // ← 每块重算密钥编排
    int[] ipByte = initPermute(dataByte);     // int[64]
    int[] ipLeft = new int[32]; int[] ipRight = new int[32]; int[] tempLeft = new int[32];
    for (i = 15; i >= 0; i--) {
        int[] key = new int[48];              // ← 每轮
        ...
        int[] tempRight = xor(pPermute(sBoxPermute(xor(expandPermute(ipRight), key))), tempLeft);
        ...
    }
    return finallyPermute(finalData);
}

每轮都要新建 expandPermute(48) / xor(48) / sBoxPermute(32) / pPermute(32) / xor(32) / tempRight(32) / key(48) 一堆数组，16 轮乘下来就是 66 KB。推算到批量任务：

1
2
3
每行分配 ≈ 6 × 65,968 B + 2 块 × 约 7 KB ≈ 410 KB
5 万行  ≈ 20.5 GB
单线程耗时 3.89 s × 5.28 GB/s ≈ 20.5 GB   ← 与上式吻合

也就是说，单线程的墙钟时间几乎全部花在”把这 20.5 GB 内存分配出来”上。而内存带宽是全局共享资源，所以加线程并不会更快——第二个结论也就顺理成章了。

顺带说一个意外发现。IDEA 运行配置里有一串 -Xms10G -XX:+UseZGC -XX:ZAllocationSpikeTolerance=5，但它被填在了 PROGRAM_PARAMETERS（程序参数）而不是 VM options 里，而 CasDec.main 根本不接收参数，所以从未生效；实际一直跑在默认 G1 + 8136 MB 堆上。这串参数本身倒是说明作者已经感觉到分配压力了。

问题清单

把所有可疑点摊开，按实测影响排个序：

# 问题 实测影响 修复难度
P1 每个分组分配约 66 KB（临时数组风暴） 分配速率 5.28 GB/s；吞吐第一瓶颈，并压制线程扩展性 中
P2 每个分组都重算 16 组子密钥 占 dec 耗时 15.59%、3488 B/次 低
P3 每块 hex→比特 走”字符串 + 64 次 substring/parseInt” 2.037 µs/块 → 可降到 0.037 µs（54.95×） 低
P4 用 s += ... 逐块累积字符串 O(n²)：32k 块时 352 ms vs StringBuilder 的 0.21 ms（1652×） 低
P5 keyCache 用 byte[] 作键：永不命中且无界增长 命中率 0.0000%；5 万行 → 15 万条目；8.3 万条目 GC 后仍占 83 MB 低
P6 线程扩展性差却”看起来”并发 1→8 线程仅 1.31×；去掉共享状态也仅 1.45× 见 P1
P7 无界任务队列：每行都 execute 一个任务 5 万行提交后队列里还有 49,990 个待执行任务 低
P8 synchronized 套 synchronized + 无意义的 .parallel() 非主瓶颈，但白白增加争用与复杂度 低
P9 每行 line.split(",") 95.4 ns/行 vs indexOf 32.3 ns/行（2.95×） 低
P10 去重表保存完整 用户,密码 字符串 内存随唯一记录数线性增长 低
P11 IDEA 把 JVM 参数填到了 PROGRAM_PARAMETERS -Xms10G -XX:+UseZGC 从未生效 极低

逐个展开

密钥编排：缓存不如上提

generateKeys 占 dec 的 15.59%，直觉是”缓存起来”。我先按密钥内容做了个 Map<String, int[][]>（键用 Arrays.toString）的 DesCached，结果只快 1.01×（19.147 → 18.950 µs/块）——构造字符串键 + 哈希 + 查表的成本几乎等于重算。

所以正确做法不是缓存，而是把密钥编排上提到分组循环之外。strDec 外层是分组、内层是密钥块，完全可以对每个密钥块只算一次 generateKeys，再把结果传给 decWithKeys(block, keys)。能上提到循环外的，就别缓存。

而 src/Des.java 里那个 keyCache 更有意思：

1
2
3
private final ConcurrentHashMap<byte[], byte[][]> keyCache = new ConcurrentHashMap<>();
...
byte[][] keys = keyCache.computeIfAbsent(keyByte, _ -> generateKeys(keyByte));

byte[] 用的是 Object 的身份比较，内容相同也是不同的键，所以跨调用必然失效。实测 1 块密文连续 5 万次 strDec，命中率 0.0000%，条目从 20,000 涨到 70,000；真实批量场景（5 万行 × 3 密钥）留下 15 万条目，System.gc() 之后仍占 83 MB——这些对象永久可达，等于一个内存泄漏。

hex 解码

根版走的是”字符串 + 64 次 substring + parseInt“，src 版已经改成 16 次 parseInt(..., 16)，还可以更直接：

1
2
3
4
5
6
7
for (int i = 0; i < 16; i++) {
    int v = Character.digit(hex.charAt(i), 16);
    out[4 * i]     = (v >>> 3) & 1;
    out[4 * i + 1] = (v >>> 2) & 1;
    out[4 * i + 2] = (v >>> 1) & 1;
    out[4 * i + 3] =  v        & 1;
}

字符串拼接

javac 会把循环里的每个 s += unit 编译成”新建 StringBuilder → 复制旧串 → 追加 → toString”。隔离实验（每块 8 字符）非常直观：

分组数 字符数 s += unit StringBuilder 倍数
2000 16,000 1.31 ms 0.05 ms 24.5×
8000 64,000 24.80 ms 0.10 ms 236.8×
32000 256,000 352.22 ms 0.21 ms 1652.1×

无界队列

CasDec 对每一行都 executor.execute(...)，而 Executors.newFixedThreadPool 用的是无界 LinkedBlockingQueue。实测 5 万行输入，在”全部行已提交”这一刻队列里还躺着 49,990 个任务——整个文件的行被一次性塞进队列。1.85 MB 的输入，队列持有的对象开销是它的数倍；千万行量级就会变成 GB 级堆占用。修法是有界队列 + CallerRunsPolicy 形成背压：

1
2
3
var executor = new ThreadPoolExecutor(threads, threads, 0, TimeUnit.MILLISECONDS,
        new ArrayBlockingQueue<>(threads * 1024),
        new ThreadPoolExecutor.CallerRunsPolicy());

多余的锁与 .parallel()

credMap 本身就是 ConcurrentHashMap，外面再套 synchronized (credMap) 直接退化成全局串行；containsKey + put 应该改成 putIfAbsent 的返回值判重：

1
2
3
if (credMap.putIfAbsent(usr_passwd_pair, Boolean.TRUE) == null) {
    synchronized (writeLock) { opt.write(usr_passwd_pair + "\n"); }
}

另外 BufferedReader.lines() 的 Spliterator 不可切分，.parallel() 根本不会并行读取，只会套一层 ForkJoin 调度开销——实测 nopar 3034 ms vs parallel 2975 ms，在噪声范围内，删掉即可。

换成 byte[] 实现

排完 P1，最省事的修法其实就在同一个仓库里：换成 src/Des.java 的 byte[] 实现。同样一份 5 万行输入：

实现 线程数 耗时 相对 root/1 线程 1→8 线程扩展性
根 Des.java（原用） 1 3890 ms 1.00× 1.31×
根 Des.java（原用） 8 2975 ms 1.31×
src/Des.java（改一行） 1 1183 ms 3.29× 2.05×
src/Des.java（改一行） 8 577 ms 5.16×

单块指标上，strDec 从 19.147 µs / 72,981 B 降到 4.436 µs / 3,208 B——每块快 4.32×、分配少 22.75×。

两点说明：src/Des.java 只有 strDec，而批处理只需要解密，所以可以直接替换；但它自带 P5 那个 keyCache 泄漏（本次运行留下 150,000 条目），替换时应一并修掉。

更值得注意的是，减少每块分配之后，线程才真正开始起作用——扩展性从 1.31× 恢复到 2.05×。这反过来验证了前面的判断：之前不是线程没用，而是内存带宽这个全局资源已经饱和。

顺带一查：和标准 DES 的差异

优化过程中反复确认过一个前提：这些优化只改实现方式，不改算法。于是很自然想把”这份实现离标准 DES 有多远”也弄清楚。

一言以蔽之：这是一套”把文本按 UTF-16BE 编码后、用改过 PC-1 的 DES、以多段口令做 E-E-E 级联、ECB + 零填充”的私有格式。

# 差异 标准 DES（FIPS 46-3） 本实现 后果
1 PC-1 子密钥编排 FIPS 表 D 段的 4 个位组逆序 子密钥不同 → 密文不同 → 不互通
2 分组/密钥单位 8 个字节 = 64 位 4 个 16 位码元 = 64 位 等价于对 UTF-16BE 字节做 DES
3 多密钥 3DES 为 E-D-E E-E-E 级联，密钥为任意长度口令 与 3DES 不是一回事
4 填充/长度 PKCS#7 等 零填充 + 解密时丢弃 U+0000 长度须外部携带；NUL 会丢数据
— 模式 ECB/CBC/… ECB，无 IV、无 MAC 相同明文块产生相同密文块

先说一致的部分，都逐项核对过：IP / FP / E / P 置换表、8 张 S 盒、PC-2、循环左移表全部与 FIPS 吻合（src 版把硬编码表改成了 indices 数组 + 循环，数值一一对应），轮函数是教科书式 Feistel，解密时子密钥逆序。

PC-1

1
2
3
4
5
6
7
8
// src/Des.java:40-48
// PC-1
// WRONG IMPLEMENTATION, FUCK NEUSOFT
for (int i = 0; i < 7; i++) {
    for (int j = 0, k = 7; j < 8; j++, k--) {
        key[i * 8 + j] = keyByte[8 * k + i];
    }
}

（根目录 Des.java:802-806 是同一个循环，只是没写那句注释——所以两份文件必须同步改。）

它的效果是：key[0..27]（C 半区）与标准完全一致，而 key[28..55]（D 半区）是把标准的 4 个位组 [8][8][8][4] 整体倒序成 [4][8][8][8]。用 FIPS 官方测试向量一测就现形：

版本 K1（第 1 个子密钥） 密文
FIPS 46-3 已发布 00011011 00000010 11101111 11111100 01110000 01110010 85E813540F0AB405
把 PC-1 换成 FIPS 表后 同上 ✅ 85E813540F0AB405 ✅
本实现原样 …11101111 10100110 11100101 11110110 ❌ CC38B78305003643 ❌

前 24 位（来自 C1）三者一致，后 24 位（来自 D1）不一致，与推导完全对应。

需要特别注意的是，不要”顺手修正”。历史密文和输出都是围绕这个私有 PC-1 生成的，改了就让旧数据全部解不开。代码里那句脏话注释，大概就是原作者踩过这个坑留下的。

UTF-16BE

strToBt 把一个 char 的完整 16 位都塞进去，4 个码元 = 64 位。所以 "abcd" 的 64 位是 00 61 00 62 00 63 00 64——即 UTF-16BE 编码的字节，而不是 ASCII 的 61 62 63 64。

这个等价关系实测过：把 PC-1 换成标准表后，strEnc("abcd","1") 与 JCE 用 new SecretKeySpec("1".getBytes(UTF_16BE) 补齐 8 字节, "DES") 的结果完全相同（都是 5D4D01A3BDBCFD91）。

顺带一个坑，落单代理码元无法经字符串编码互转。密钥里若有 U+DFF1 这类未配对代理，Java 字符串本身能保存，但 getBytes(UTF_16BE) 会把它替换成 U+FFFD，而 strToBt 走 charAt 用的是真实位。向外部工具搬运这类密钥时务必用原始字节/位数组。

E-E-E

每一段口令的每一个 4 码元块，都是一把独立的 64 位密钥，按 first → second → third 顺序各做一次完整 DES，解密严格逆序。实测 strEnc("abcd","AB","CD","") = 2C96D4E6C12BDF01，与手算 E-E-E 相同、与 E-D-E 不同。

零填充与 ECB

不足 4 码元用 0 补齐，解密时 byteToString 直接跳过零值码元（if (count != 0)），所以文本可往返，代价是明文里本来就存在的 U+0000 也会被吞掉（实测 a\u0000bc 解出 abc）。ECB 无 IV，相同明文块产生相同密文块。

另外 iterator = length / 16 不校验余数，尾部不完整 hex 会被静默忽略（实测喂 20 个 hex 字符只解出第 1 块）。

互通性矩阵如下：

场景 结果
本实现加密 → JCE/OpenSSL 解密 ❌
JCE/OpenSSL 加密 → 本实现解密 ❌
本实现解 3DES(EDE) 数据 ❌
本实现解含 NUL 的明文 ❌ 丢字符
PC-1 换成标准表后 → JCE 解密 ✅

即：UTF-16BE 编码和零填充都能用标准库复现，唯一的”硬墙”就是 PC-1。

两条改造路线

路线 A：保持兼容（除非明确要迁移，否则推荐）。 不动 PC-1。任何”修正”都会让既有密文无法解密。新增功能时必须同时改 src/Des.java 与根 Des.java。

路线 B：迁移到标准 DES（会改变所有历史密文）。

  1. 把 generateKeys 的 PC-1 换成 FIPS 表（两份文件都要改）：

    1
    2
    3
    int[] pc1 = {56, 48, 40, 32, 24, 16, 8, 0, 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35,
                62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 60, 52, 44, 36, 28, 20, 12, 4, 27, 19, 11, 3};
    for (int i = 0; i < 56; i++) key[i] = keyByte[pc1[i]];

  2. 保持 UTF-16BE 编码（4 码元 = 8 字节）与零填充；

  3. 多段口令按块顺序连续 DES（E-E-E），解密逆序；

  4. 之后就能直接用标准库，多段口令的等价写法是”每段口令按 4 码元切块，逐块做一次完整的 doFinal“；

  5. 迁移校验：拿一批旧数据，用”改好的本实现”与”标准库”各解一遍，结果必须逐字节相同，再用 FIPS 官方向量回归一次。

总结

  • 先测量，再优化。 靠直觉两次都猜错了（先猜锁，再猜 GC），只有把”分配字节数”量出来才定位到真凶。
  • 加线程没用时，先找不可并行化的共享资源。 这里的内存带宽是全局共享的，加线程只是在抢同一条带宽。
  • “分配压力大”经常被误诊为”需要 ZGC / 需要大堆”。 IDEA 里那串 10 GB + ZGC 参数既没生效，也本就不该是首选方案——先减少每块的 new，问题自然消失。
  • 缓存不是免费的。 用字符串键 + 哈希表缓存子密钥编排，实测只快 1.01×。能上提到循环外的，就别缓存。
  • 顺手检查 IDE 运行配置。 JVM 参数填进 PROGRAM_PARAMETERS 里不会报错，只会静默失效。
  • 性能优化和算法兼容性是两件事。 本次所有优化都只改实现方式、未改算法。

按实测影响排序的优化清单：

优先级 动作 预期收益 风险
1 批量任务改用 src/Des.java 的 byte[] 实现 单线程 3.29×、8 线程 5.16×；分配降低 22.75× 低
2 修 keyCache：删除或改为内容键 消除无界增长（5 万行 15 万条目、8.3 万条目占 83 MB） 低
3 密钥编排上提出分组循环 省 dec 的 15.59% 时间与 3488 B/块 低
4 任务队列改为有界 + 背压 内存从”随文件行数”变为有界，大文件不再有 OOM 风险 低
5 s += ... → StringBuilder 隔离实验 1652×，端到端最高约 1.94× 低
6 hex 解码改为按 nibble 取位 每块省 2.04 µs（54.95×） 低
7 缓冲区复用，把每块分配降到接近 0 让线程真正可扩展（当前被内存带宽压制） 中
8 去重改 putIfAbsent、删掉 .parallel()、线程数默认 ≤4 降争用与抖动，可读性提升 低
9 每行解析改 indexOf、去重表存哈希、IDEA VM options 归位 各为个位数百分比 低

复现

性能部分在 D:\Code\Des\.qwen\tmp\perf-verify\（Perf.java 微基准、Gen.java 生成输入、CasPerf.java 支持 线程数 [nopar] [nopost] [src] 四种开关并打印队列长度）：

1
2
3
4
5
6
7
8
9
10
11
12
13
cd /d D:\Code\Des\.qwen\tmp\perf-verify
set JV=C:\Users\sfc9982\.jdks\graalvm-jdk-22\bin\java.exe
set JC=C:\Users\sfc9982\.jdks\graalvm-jdk-22\bin\javac.exe

%JC% --release 22 --enable-preview -encoding UTF-8 -nowarn -cp "D:\Code\Des\lib\annotations-24.0.0.jar" -d classes Des.java Des2.java DesCached.java Perf.java Gen.java CasPerf.java
%JV% --enable-preview -cp classes Perf
%JV% --enable-preview -cp classes Gen 50000 input.txt
%JV% --enable-preview -cp classes CasPerf 1
%JV% --enable-preview -cp classes CasPerf 8
%JV% --enable-preview -cp classes CasPerf 8 nopar        :: 去掉无意义的 parallel()
%JV% --enable-preview -cp classes CasPerf 8 nopost       :: 隔离：只解密，不做去重/写文件
%JV% --enable-preview -cp classes CasPerf 8 post src     :: 换成 src 版实现
%JV% -Xlog:gc:file=gc1.log --enable-preview -cp classes CasPerf 1

标准 DES 对照部分在 D:\Code\Des\.qwen\tmp\des-verify\（DesStd.java 仅把 PC-1 换成 FIPS 表，Verify.java 逐项验证 PC-1、UTF-16BE、E-E-E、零填充与边界行为，并与 JCE 对照）：

1
2
3
4
copy /y D:\Code\Des\Des.java D:\Code\Des\.qwen\tmp\des-verify\Des.java
cd /d D:\Code\Des\.qwen\tmp\des-verify
"C:\Users\sfc9982\.jdks\graalvm-jdk-22\bin\javac.exe" --release 22 --enable-preview -encoding UTF-8 -nowarn -d classes Des.java DesStd.java Verify.java
"C:\Users\sfc9982\.jdks\graalvm-jdk-22\bin\java.exe" --enable-preview -cp classes Verify

注意 Des.java 用了字符串模板 STR."..."（Java 22 预览特性），编译与运行必须带 --enable-preview。另外吞吐类数字存在 ±5%～10% 的运行间波动（8 线程尤其明显），上表取自一次串行执行的完整矩阵；结论（扩展性饱和在 1.3~1.5×、换实现后约 5×）在多次运行中稳定复现。

Reference

文章作者: sfc9982
文章链接: https://googles.plus/2026/09/13/ji-yi-ci-des-suan-fa-java-shi-xian-de-you-hua/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 sfc9982 !
Java DES 性能优化 密码学
  目录