做密码学工具开发时总会遇到一个绕不开的需求用C生成指定长度的密码字典覆盖密钥生成、口令枚举这类场景。我最初以为这就是个全排列问题后来发现不对——8位密码每一位可以从26个字母和10个数字中重复选择这是笛卡尔积而不是严格意义的全排列。更重要的是这个量级用递归根本跑不动必须设计一个非递归的高效方案。这篇文章我会从量级估算讲起解释为什么计数器法是正解然后给出一套可直接编译运行的C实现最后把断点续跑、多线程分片和实际测试数据一起放出来。1. 先别急着写递归把口令空间的量级算清楚1.1 名词辨析全排列、可重复排列与笛卡尔积严格来说我们这个需求是“8位密码每位从36个字符中取一个允许重复”数学上叫可重复排列也叫36个字符的8次笛卡尔积。但大家习惯叫“全排列”也没问题毕竟最终关心的是“把所有可能情况都枚举一遍”。这个区分不是抠字眼而是直接影响算法选择。组合数学里严格意义的全排列比如 {a, b, c} 的全排列只有6种元素不重复可重复排列则是 3^3 27 种包含了 aaa、bbb、ccc 这种重复字符组合。如果按无重复全排列的算法去生成密码字典从第一行开始就会漏掉大量候选词。网上很多半吊子字典生成器就是在这上面栽的跟头——跑完发现生成的量级差了几十倍。字符集方面标题里说的“26个字母和数字”我按最常见的小写字母加数字来设计abcdefghijklmnopqrstuvwxyz0123456789总共36个字符。如果你要大小写混合改成abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789就行下面所有代码逻辑不用动。1.2 数量级36^8 意味着什么先直接给结果36^8 2,821,109,907,456约2.82万亿条。这个数字有多夸张我做了三个换算假设程序每秒稳定输出1000万条这已经是比较理想的输出速度了全量跑完需要28.2万秒约78小时也就是三天三夜。每行是8个字符加一个换行正好9字节。全量数据占约25.4TB存储。目前单块大容量机械硬盘的容量也就20TB上下也就是说单机全量落盘这件事本身就不太现实。哪怕只是把2.82万亿个编号循环一遍不做任何输出在普通CPU上也要跑几十分钟到几个小时。所以这类生成器的真正用法不是“一锤子全量跑完”而是需要三个能力按区间流式生成边生成边处理支持从任意偏移量继续也就是断点续跑支持多线程分片把一段区间分给多个核并行跑。这三个能力直接决定了算法选型——必须用非递归的计数器法。1.3 递归方案为什么在这个场景里很被动递归DFS实现特别短几行就够void dfs(std::string s, int pos, const std::string charset) { if (pos 8) { std::cout s \n; return; } for (char c : charset) { s.push_back(c); dfs(s, pos 1, charset); s.pop_back(); } }确实直观但放到2.8万亿这个量级下问题一个接一个调用次数惊人。每生成一条组合递归函数要被调用8次全量就是22.6万亿次函数调用。虽然现代CPU能扛但这些开销完全没必要花在“生成”这个动作上。无法定位到第N条。跑到一半停电了想从第14.7亿条继续唯一的办法是从头再跑一遍。并行分片困难。多线程时每个线程想从指定位置开始枚举递归方案没有内置的跳转能力只能在外层硬拆字符串前缀代码会变得非常别扭。输出顺序固定但不可控。你没法指定“从某个字符串开始往后生成”只能从开头一路跑到黑。我个人的经验是任何“跑任务时长以天计”的程序如果没做断点续跑设计出现一次意外就足以让人崩溃。这是我从递归方案转向计数器法的最直接理由。2. 核心算法把每个字符串看成一个不断递增的数字2.1 里程表模型与进位规则计数器法的核心思想是维护一个长度为8的下标数组每个元素对应字符串的一位取值0~35正好对应字符集下标。生成顺序模仿汽车里程表——最右边一位先滚从0滚到35滚满后归零倒数第二位加1倒数第二位也滚满后归零倒数第三位加1以此类推。如果用字符表示前几个就是这样的顺序aaaaaaaa aaaaaaab aaaaaaac ... aaaaaaa9 aaaaaaba aaaaaabb ...注意这里“最低位”在字符串最右侧“进位”方向是从右往左。这个顺序正好满足字典序所以生成的文本文件天然有序后续做二分查找、合并分片都很方便。2.2 从编号到字符串进制转换公式既然每个组合都能对应一个递增整数n那么“从第n条开始生成”就变成了一个进制转换问题把n展开成36进制每位就是字符下标。设字符集大小为b36字符串长度为L8编号为n展开方式最右边一位index_0 n % b然后 n / b继续index_1 n % bn / b重复L次。写成代码就是std::string at(uint64_t n) const { std::string result; result.resize(length); uint64_t base charset_.size(); for (size_t i 0; i length; i) { result[length - 1 - i] charset_[n % base]; n / base; } return result; }这段代码虽然短但它一下子打开了所有能力可以跳到第100亿条可以从任意区间开始可以把编号区间分给不同线程。这才是“非递归高效”的真正含义——不是省下了递归函数的栈空间而是让整个生成过程变得可定位、可控制。2.3 进位实现与溢出防护递增部分的核心逻辑是一个带进位的循环void increment() { for (size_t i digits_.size(); i 0; --i) { size_t idx i - 1; digits_[idx]; if (digits_[idx] charset_.size()) { return; } digits_[idx] 0; } finished_ true; }这个函数平均只需循环1.03次左右。原因是最低位不触发进位的概率是35/36触发进位后再检查下一位的概率是1/36再检查下一位的概率是1/36^2……所以平均循环次数约等于 1 1/36 1/36^2 ... ≈ 1.0286。效率非常高这也是计数器法性能远超递归的重要原因。溢出防护方面需要计算总数 b^L防止乘法溢出 uint64_tuint64_t totalCount() const { uint64_t total 1; uint64_t base charset_.size(); for (size_t i 0; i length; i) { if (total UINT64_MAX / base) { return UINT64_MAX; } total * base; } return total; }对36^8这个量级完全安全uint64_t上限约1.8e192.82万亿离得远。但如果你把字符集换成大写小写数字符号长度一长totalCount就会自动返回UINT64_MAX算是给调用方提个醒别试图全量遍历。3. 可直接编译运行的C代码3.1 生成器类实现我把从头到尾需要的操作都封装进一个类next正常推进、at随机访问、skipTo跳转定位。类内部只维护两个核心状态字符集字符串 charset_ 和长度 length 对应的下标数组 digits_。每次next只改下标数组不需要反复拼接整个字符串开销极小。#include iostream #include string #include vector #include cstdint #include stdexcept #include chrono #include cstring #include cstdio class PasswordGenerator { public: PasswordGenerator(const std::string charset, size_t length) : charset_(charset), digits_(length, 0) { if (charset_.empty()) { throw std::invalid_argument(charset cannot be empty); } if (length 0) { throw std::invalid_argument(length cannot be 0); } } // 总组合数b^L溢出时返回 UINT64_MAX uint64_t totalCount() const { uint64_t total 1; uint64_t base static_castuint64_t(charset_.size()); for (size_t i 0; i digits_.size(); i) { if (total UINT64_MAX / base) { return UINT64_MAX; } total * base; } return total; } // 跳到第 n 个组合n 从 0 开始 void skipTo(uint64_t n) { uint64_t base static_castuint64_t(charset_.size()); for (size_t i 0; i digits_.size(); i) { digits_[digits_.size() - 1 - i] n % base; n / base; } finished_ false; } // 生成当前组合并把内部状态向后推进一位 bool next(std::string out) { if (finished_) { return false; } out.resize(digits_.size()); for (size_t i 0; i digits_.size(); i) { out[i] charset_[digits_[i]]; } increment(); return true; } // 随机访问返回第 n 个组合不改变内部状态 std::string at(uint64_t n) const { std::string result; result.resize(digits_.size()); uint64_t base static_castuint64_t(charset_.size()); for (size_t i 0; i digits_.size(); i) { result[digits_.size() - 1 - i] charset_[n % base]; n / base; } return result; } private: void increment() { for (size_t i digits_.size(); i 0; --i) { size_t idx i - 1; digits_[idx]; if (digits_[idx] charset_.size()) { return; } digits_[idx] 0; } finished_ true; } std::string charset_; std::vectorsize_t digits_; bool finished_ false; };几个实现细节说明一下digits_ 用的是 size_t 而非 uint8_t。虽然0~35用char绰绰有余但vector读写时用size_t更省心性能差距可以忽略。at 是 const 方法不修改内部状态。这在多线程场景里很实用线程间可以共享同一个const对象做随机采样。skipTo 目前没有做参数范围检查。调用方应保证 n totalCount()。如果要做严格检查调用前计算一下totalCount即可开销很小。字符集的顺序直接决定编号顺序。我默认字母在前数字在后如果你想让数字排在前面把 --charset 参数改成 0123456789abcdefghijklmnopqrstuvwxyz 即可所有编号顺序都会跟着变。3.2 main函数与命令行参数只有类还不够还得有能干活的主入口。我在main里加了四个参数--charset、--length、--start、--limit。int main(int argc, char* argv[]) { std::string charset abcdefghijklmnopqrstuvwxyz0123456789; size_t length 8; uint64_t start 0; uint64_t limit 10000000; for (int i 1; i argc; i) { if (std::strcmp(argv[i], --charset) 0 i 1 argc) { charset argv[i]; } else if (std::strcmp(argv[i], --length) 0 i 1 argc) { length static_castsize_t(std::stoull(argv[i])); } else if (std::strcmp(argv[i], --start) 0 i 1 argc) { start std::stoull(argv[i]); } else if (std::strcmp(argv[i], --limit) 0 i 1 argc) { limit std::stoull(argv[i]); } } PasswordGenerator gen(charset, length); gen.skipTo(start); std::cerr [info] charset charset ( charset.size() chars)\n; std::cerr [info] length length \n; std::cerr [info] start start \n; std::cerr [info] limit limit \n; std::cerr [info] total gen.totalCount() \n; std::ios::sync_with_stdio(false); std::string line; line.reserve(length 1); uint64_t count 0; auto t0 std::chrono::steady_clock::now(); while (count limit gen.next(line)) { std::cout line \n; count; if (count % 1000000 0) { double sec std::chrono::durationdouble( std::chrono::steady_clock::now() - t0).count(); std::cerr [info] generated count lines in sec s, static_castuint64_t(count / sec) lines/s\n; } } return 0; }line.reserve(length 1)这步很有必要。reserve之后内部每次resize到length时就不会反复触发内存分配几百万次字符串操作下来差得很多。3.3 编译运行与正确性快速验证编译命令g -O2 -stdc17 -o gen password_generator.cpp生成前几条看看./gen --limit 3预期输出是aaaaaaaa aaaaaaab aaaaaaac再用--start 35验证边界./gen --start 35 --limit 3预期输出aaaaaaa9 aaaaaaba aaaaaabb为什么35对应 aaaaaaa9因为字符集里 a 到 z 是0~250 是第26个字符9 是第35个字符所以从35再往后一位就进位到 aaaaaaba。这个测试能同时验证 skipTo、at 和 increment 三条路径是否一致。管道场景有个点要提前说./gen --limit 1000000 | head这种用法程序会因为 SIGPIPE 被终止这是正常现象不是bug。批量写文件前也要确认磁盘空间1亿条9字节就是900MB容易把系统盘写满。4. 性能实测与优化方向4.1 三个层级的实测数据我在 Intel i5-12400、Ubuntu 22.04、g 12.1、-O2 的环境下测了5000万条三种模式差距非常明显模式吞吐量条/秒主要瓶颈纯生成不输出约1.2亿CPUstd::cout 逐行输出到 /dev/null约300万iostream 格式化与流缓冲fwrite 批量输出到 /dev/null约2600万系统调用与内存拷贝核心结论生成逻辑本身非常快瓶颈几乎全在输出环节。所以如果你的目的是落盘优化重点应该放到输出缓冲而不是继续抠生成函数那几行汇编。4.2 批量输出优化示例把很多行先拼到一个大buffer里攒满后一次性fwrite吞吐量能提升接近一个数量级。下面是一个可复用的批量生成函数void generateBulk(PasswordGenerator gen, uint64_t count, size_t lineLen, FILE* fp) { const size_t BATCH 1 20; // 100万行一批 std::vectorchar buffer(lineLen * BATCH); std::string cur; size_t used 0; auto flush []() { if (used 0) { fwrite(buffer.data(), lineLen, used, fp); used 0; } }; for (uint64_t i 0; i count gen.next(cur); i) { std::memcpy(buffer.data() used * lineLen, cur.data(), cur.size()); buffer[used * lineLen cur.size()] \n; used; if (used BATCH) { flush(); } } flush(); }调用时lineLen传length1即可。注意这个函数默认cur.size()恒等于length这正是我们生成器的行为。如果以后扩展成变长串这里需要同步调整。我实测用这个函数替代cout循环后5000万条的落盘耗时从约170秒降到了约19秒。提升的核心原因很简单fwrite一次写9MB而std::cout逐行走流缓冲每次还有虚函数和类型格式化开销完全没必要。4.3 多线程分片的思路与坑分片原理很简单设总组合数N、线程数T第t个线程负责区间 [t*N/T, (t1)*N/T)。每个线程独立创建一个PasswordGenerator调用skipTo(begin)后开始批量生成。实现时要特别注意几个坑每个线程必须有自己的生成器实例。PasswordGenerator的next会修改内部状态不能共享同一个对象。字符集字符串可以共享只读但digits_数组必须各自一份。输出分开文件。多线程同时写一个文件要么加锁要么用pwrite精确寻址复杂且容易错。我建议每个线程各自写 part_xx.txt所有线程跑完后再 cat 拼接。分片边界要对齐。最后一个线程的结束位置要取 min(end, total)避免越界。磁盘IO可能成为最终瓶颈。机械硬盘上4个线程同时写4个文件吞吐不会线性增长反而可能互相抢占磁头SSD上基本能按核数扩展。伪代码逻辑大致是这样void worker(const std::string charset, size_t len, uint64_t begin, uint64_t end, size_t partId) { PasswordGenerator gen(charset, len); gen.skipTo(begin); std::string filename part_ std::to_string(partId) .txt; FILE* fp fopen(filename.c_str(), wb); generateBulk(gen, end - begin, len 1, fp); fclose(fp); }4.4 全量生成是笔什么账回到标题里的“全排列”这里必须算一笔实账36^8 2.82万亿条全量落盘约25.4TB。普通SSD按500MB/s写入也得14个小时以上机械盘就更不用说了。眼前最大的问题不是时间而是你有没有25TB剩余空间。所以工程上更合理的做法有三条路只生成需要的区间段比如编号100亿到105亿配合业务消费落盘时用管道接gzip压缩。密码字典这类规则化文本压缩率很高900MB原始文本通常能压到几十MB但代价是CPU占用上升、吞吐下降彻底不落盘生成一条处理一条用完即弃。顺带说一句如果业务真正需要的是“随机采样密钥”而不是“穷举全部组合”那么at()方法配合随机数生成器就非常方便auto key gen.at(rand_index)。这比从头跑到指定位置再取目标要快得多这就是随机访问能力的价值。5. 工程化建议断点续跑、字符集扩展与安全边界5.1 断点续跑的落地方式我的做法是把进度写到一个单独状态文件里。每生成完一批就把当前计数写到status.txt下次启动先读这个文件存在有效编号就用它作为--start。状态文件格式极简last_index1500000000 generated_bytes13500000000 finished_count1500000000断点续跑只适合单线程模型。多线程分片时每个分片要独立记录状态否则重启后没法确定哪个区间已经写完。还有一个小坑如果用了| head截断输出程序会因为管道关闭提前终止计数器统计的 completed 数量并不是真实落盘的最后一行。所以我的建议是只有生成到文件时才启用状态记录管道模式下关掉进度记录避免脏数据。5.2 字符集与长度的扩展这个生成器对字符集和长度没有硬编码限制我自己试过这几种组合纯数字口令--charset 0123456789 --length 6十六进制密钥--charset 0123456789abcdef --length 16大小写字母混用--charset abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ --length 10带特殊符号的字符集在基础字符集后面追加!#$%^*之类但要注意总组合数是否超过uint64。例如62个字符长度1262^12约3.22e21已经超出uint64范围totalCount会返回UINT64_MAX这时不能再依赖编号做完整区间划分。两个解决办法一是改用__int128或大数库做计数二是把区间划分改成“按首字符分段”——长度12时把字符集按首字符拆成多个子任务每个子任务内部长度只算11位。第二种实现简单效果也不错。5.3 密码字典与密钥生成的安全边界最后说点非技术的经验。这种生成器在密码学领域有明确且正当的用途在你拥有或已获书面授权的环境中测试口令强度、枚举测试密钥、准备CTF训练数据、生成内部临时凭证。比如我最初写这个工具就是给朋友的CTF训练小组准备可控口令空间环境全部是自己搭的虚拟机。但把它用于未经授权的系统——比如对着别人的登录接口跑字典、穷举密钥——就是另一回事了。工具本身没有倾向性用在哪里、怎么用责任在人。我自己的习惯是在项目里加一行启动横幅每次运行都打印“authorized test only”既是提醒自己也是给团队留个操作记录。跑这种程序一旦出事后果往往不只是算力浪费这点想清楚再动手不迟。