#PaperY0/zxcvbn

Dropbox zxcvbn 密码强度估计器的 MoonBit 移植。 输入密码字符串，输出 0–4 强度分 + 猜测次数及其 log10 + 四场景破解时间 + 命中的模式明细 + 改进建议。

English below

#为什么是它

#与 LUDS 规则打分的实证边界

#能力范围

• 8 个模式匹配器：6 个频率词典（30k 常见密码 / 30k 维基词 / 3712 女名 / 983 男名 / 10k 姓氏 / 19160 影视词，共 93,855 词）、 反向词典、l33t 替换（17 条替换表 + 子集枚举）、键盘空间（qwerty/dvorak/keypad/mac_keypad）、 重复（abcabcabc）、序列（abc/123/97531）、正则（年份）、日期（多格式 + 分隔符）
• 最优匹配序列 DP：动态规划取最小 guesses 的非重叠序列
• 输出：guesses / log10(guesses) / 0–4 分 / 四场景破解秒数（在线限流 100/h、在线 不限流 10/s、离线慢哈希 1e4/s、离线快哈希 1e10/s）/ warning + suggestions

#API 设计

pub fn zxcvbn(
  password : String,
  user_inputs : Array[String],
  reference_year? : Int = 2026,
) -> Entropy

pub struct Entropy {
  password : String
  /// 保守估计的猜测次数（Double：长密码会达到 1e10^n 甚至上溢）
  guesses : Double
  /// log10(guesses)
  guesses_log10 : Double
  /// 0..4，阈值 1e3 / 1e6 / 1e8 / 1e10（与上游一致）
  score : Int
  /// 四场景破解秒数
  crack_times_seconds : CrackTimes
  /// 人类可读破解时间
  crack_times_display : CrackTimesDisplay
  /// 最优匹配序列
  sequence : Array[Match]
  feedback : Feedback
}

/// 一次模式匹配（按模式拆成 enum + 每模式 struct，仿 zxcvbn-rs 的强类型范式）
pub enum Match {
  Bruteforce(BruteforceMatch)
  Dictionary(DictionaryMatch)
  Spatial(SpatialMatch)
  Repeat(RepeatMatch)
  Sequence(SequenceMatch)
  Regex(RegexMatch)
  Date(DateMatch)
}
pub fn Match::start_index(self) -> Int    // 闭区间起点
pub fn Match::end_index(self) -> Int      // 闭区间终点
pub fn Match::token(self) -> String       // 命中的原文字符串
pub fn Match::pattern(self) -> String     // "dictionary" / "spatial" / ...
pub fn Match::guesses(self) -> Double

pub fn dictionary_match(Array[Char], Array[(Dictionary, Map[String, Int32])], Int32) -> Array[Match]
pub fn reverse_dictionary_match(Array[Char], Array[(Dictionary, Map[String, Int32])], Int32) -> Array[Match]
pub fn l33t_match(Array[Char], Array[(Dictionary, Map[String, Int32])], Map[Char, Array[Char]], Int32) -> Array[Match]
pub fn spatial_match(Array[Char], Array[(String, Map[Char, Array[(Char, Char)?]])]) -> Array[Match]
pub fn repeat_match(Array[Char], Array[(Dictionary, Map[String, Int32])], Int32, Map[Char, Array[Char]], Int32) -> Array[Match]
pub fn sequence_match(Array[Char]) -> Array[Match]
pub fn regex_match(Array[Char]) -> Array[Match]
pub fn date_match(Array[Char], Int32) -> Array[Match]

#三个使用场景

1. 注册/改密表单（服务端）：zxcvbn(pw, [username, email]) —— 用户输入参与词典， 防止"用自己名字当密码"。
2. CLI 工具：moon run cmd/main -- "Tr0ub4dor&3" 打印分数/猜测次数/破解时间/模式明细/建议； --json 输出机器可读结果（供差分对拍消费）。
3. 浏览器强度条：demo/ 一个可运行的页面——输入即实时打分，密码不离开浏览器， 评估过程不发送密码（初次加载静态资源仍会产生网络请求）。MoonBit 侧编到 js 后端产出 ES module，zxcvbnReport(password, user_inputs) 返回 JSON 字符串；wasm / wasm-gc 后端 由 CI 的三后端测试矩阵覆盖。详见 demo/README.md。

#与上游的刻意差异（都是修正，逐条说明）

1. 下标按 Unicode 标量值计，而非 UTF-16 码元。 上游在含非 BMP 字符的密码上有过经典的 UTF-16 边界 bug（HIV 密码一例）；本实现用 MoonBit 的 Char（即标量值）遍历， 从根上避免。代价：token 长度与上游 String::length() 在含 emoji 时不同。
2. guesses 用 Double 而非整数。 上游 JS 全程是浮点数；长密码的 bruteforce 猜测数会 达到 10^n 乃至上溢，用 Int 会静欲溢出。zxcvbn-rs 同样用 f64。
3. reference_year 参数化（默认固定为 2026）。 为保持计算与测试可复现，库不读取运行时钟； 集成方应显式传入所需年份，默认值不会随日历自动变化。
4. recent_year 正则升级为 19\d\d|20\d\d。 上游的正则是 2017 年的 19\d\d|200\d|201\d， 识别不出 2020 年之后的年份；这里沿用 zxcvbn-rs 已更新的范围。 （附带：MoonBit core 的 Regex 不支持 \d，须用 POSIX 类 [[:digit:]]， 而正则也没有反向引用 \1——所以本项目的 repeat_match 用手写的周期检测， regex_match 用手写的四位年扫描，两者在语义上与上游等价。）
5. 词典匹配的长度上限裁剪。 只枚举到"所有词典中最长词条"的长度：更长的子串不可能命中， 语义完全等价，但把词典匹配从 O(n²) 次哈希查询降到 O(n × 最长词长)。
6. 用户信息按调用传入。 本实现不使用全局用户词典，返回的默认反馈数组也相互独立。 内置词典、键盘表和兼容导出的集合仍是共享数据，调用方不应修改它们。
7. String::to_lower() 的 Unicode 范围。 MoonBit 标准库的 String::to_lower() 正确处理 ASCII（A-Z → a-z）和 Latin-1 Supplement（Ü → ü），但不处理 Greek 大写（Α → α 不做转换）。 因此希腊字母的大小写变体在用户词匹配中仍会失败，这是 MoonBit 标准库的限制，非本项目的 算法偏差。ASCII/Latin-1 范围的大小写不敏感匹配已通过 lower() 辅助函数对齐。

#测试策略

1. 上游官方向量（test/test-matching.coffee 10 个块 + test/test-scoring.coffee 12 个块） 逐块转写：词典/反向/l33t（含子表与子集枚举）/键盘空间/序列/重复/正则/日期/omnimatch， 以及 nCk、log、DP 搜索、各模式 guesses、uppercase/l33t 变体。官方向量里的 genpws prefix/suffix 变体矩阵也一并转写。
2. 性质与端到端：r0sebudmaelstrom11/20/91aaaa 精确复现上游 omnimatch 的四大匹配； correcthorsebatterystaple → score 4。
3. 边界：空串、单字符、纯空白、1000 长度密码、非 BMP emoji（验证按标量值计长）、 user_inputs 命中自身、reference_year 参数化、完整 JSON 解析与控制字符往返、 非有限数值序列化，以及调用之间的反馈数组隔离。

moon check   # 0 error，0 warning
moon test    # 61/61（默认 wasm 后端）

# 三个后端都全绿（验证”纯计算、无 IO 依赖”的声明）
moon test --target wasm     # 61/61
moon test --target wasm-gc  # 61/61
moon test --target js       # 61/61

moon run cmd/main -- "correct horse battery staple"

#非目标（明确不做）

#开发

curl -fsSL https://cli.moonbitlang.com/install/unix.sh | bash -s -- "$(cat .moonbit-version)"

moon check          # 静态检查
moon info           # 更新 .mbti 接口
moon fmt            # 格式化
moon test           # 测试
moon run cmd/main -- "password"
python tools/gen_dictionaries.py      # 从 data/upstream 重新生成词典数据模块
python tools/gen_adjacency_graphs.py  # 从 data/upstream 重新生成键盘邻接图模块
python tools/diff_test.py             # 对上游 zxcvbn@4.4.2 差分对拍，重写 DIFF-REPORT.md
bash demo/build.sh                   # 构建 JS CLI 并复制演示页引擎
python -m unittest discover -s tools -p 'test_*.py'
node --test tools/test_demo.mjs
# 两个生成器的产物需再跑一次 moon fmt（生成器不保证 fmt-clean，CI 的 fmt 门禁会校验）

上面的生成脚本需要 Python 3（>=3.9，无第三方依赖）。POSIX 系统上命令名通常是 python3；Windows 上若装的是 CPython 而非 Microsoft Store 版，命令名是 python——注意 WindowsApps\python3.exe 是商店占位程序，会以退出码 49 直接失败，这不是脚本的问题。

tools/diff_test.py 额外需要 node 与 tools/ref/node_modules，先执行一次 npm ci --prefix tools/ref。CI 会运行差分校验和上述集成回归； tools/known_deviations.json 固定具体用例、字段及两侧期望值，新增差异不会自动豁免。

#输入边界与序列化

• 库不静默截断密码。尽管 DP 已避免临时子串并加速支配关系查询，其前缀索引仍需 O(n²) 空间， 任意长输入没有固定时间保证；服务端接收不可信输入时应先限制长度与用户信息规模。
• 演示页在 Worker 内计算，密码最多 256 个 Unicode 标量值，用户信息最多 32 项、每项最多 256 个。 超限会显示错误并隐藏旧评分，不会把截断后的密码当成完整输入评分。
• Entropy::to_json() 将 Infinity、-Infinity 和 NaN 写成 null，与 JSON.stringify 一致； 直接调用 MoonBit API 仍能取得原始浮点值。JSON 消费方应处理这些可空数值。
• CLI 使用 -- 结束选项解析，例如 moon run cmd/main -- --json -- --year 会评估字面密码 --year。 --year 只接受 1900–2100 的四位年份；缺少参数、未知选项或多密码未加 --batch 时返回非零退出码。 --help 显示用法。当前固定工具链的 wasm-gc 宿主把 eprintln 写到 stdout； 因此机器调用必须先检查退出码，失败输出不能当作 JSON 结果解析。

#数据与许可

• 词典数据（6 个频率表，93,855 词条）与官方向量来自 dropbox/zxcvbn 的 src/frequency_lists.coffee（上游运行时实际加载的过滤后词典，与 zxcvbn-rs 逐词一致）， MIT License, (c) Dropbox, Inc.，见 data/README.md。
• 结构参考 shssoichiro/zxcvbn-rs（MIT）。
• 本项目以 MIT 发布，LICENSE 保留上游版权声明。

#当前状态（2026-10-31）

#PaperY0/zxcvbn (EN)

let result = @zxcvbn.zxcvbn("Tr0ub4dor&3", ["bob", "bob@example.com"])
result.score          // 0..4
result.guesses        // conservative attack-model lower bound (Double)
result.sequence       // optimal non-overlapping matches
result.feedback       // warning + suggestions