提出更高效的密碼評估工具，將統計語言建模技術引入密碼建模，系統評估各類概率密碼模型性能，打破PCFGw的 “最優模型” 認知。

一、研究背景

????????當前研究存在兩大關鍵問題：一是主流的 “猜測數圖” 計算成本極高，且難以覆蓋強密碼信息；二是被廣泛視為 “最先進模型” 的概率上下文無關文法模型PCFG，未與全字符串馬爾可夫模型等其他模型進行系統對比，且密碼建模未充分借鑒統計語言建模領域的成熟技術（如平滑、歸一化）。

二、概率密碼模型

2.1?定義

????????概率密碼模型是一個函數p: Γ→[0,1]。Γ為所有合法密碼集合。需滿足兩個條件：一是所有密碼的概率非負；二是所有密碼的概率和為 1。若模型對每個合法密碼均分配非零概率，則稱為 “完整模型”。

2.2 分類

? ? ? ? 全字符串模型：不分割密碼，密碼有連貫性，直接對完整字符串建模，典型代表為馬爾可夫鏈模型。

? ? ? ? 基于模板的模型：將密碼按字符類別（分割為多個片段，獨立計算每個片段的概率，再相乘得到密碼總概率。典型代表為PCFG模型，需依賴外部字典實例化字母片段。

三、統計語言建模技術

引入統計語言建模技術解決傳統模型的稀疏性，過擬合以及概率歸一化問題

3.1? 全字符串馬爾可夫模型優化

????????全字符串模型不分割密碼，直接對完整字符串建模，核心為馬爾可夫鏈模型

① 歸一化方法：解決傳統馬爾可夫模型 “不同長度密碼概率和為 1” 的不合理假設（實際密碼長度集中在 6-10 位，占比 87%）。

• 直接歸一化：將每個密碼概率除以合法長度范圍，假設長度分布均勻
• 分布 - based 歸一化：按訓練集中各長度密碼的占比調整概率（如訓練集中 8 位密碼占 25%，則所有 8 位密碼概率均乘以 25%），但可能因訓練 / 測試集長度差異導致過擬合；
• 結束符號歸一化：在每個密碼后追加 “結束符號”，通過學習 “字符→結束符號” 的轉移概率，確保所有密碼概率和為 1，同時修正 “前綴概率高于完整密碼” 的問題（如 “passwor” 概率低于 “password”），與回溯結合時性能最優。

② 平滑技術：解決稀疏性與過擬合
高階馬爾可夫模型（如 5 階）易因 “低頻次字符序列計數為 0” 導致密碼概率為 0（稀疏性），或因過度依賴訓練集序列導致泛化差（過擬合）。論文引入兩種核心平滑技術：

• 加 δ 平滑（Add-δ）：對所有字符序列的計數加 δ（取 δ=0.01），避免概率為 0，在高階模型中性能優于 Good-Turing 平滑；
• Good-Turing 平滑：基于 “出現 i 次的序列總概率≈出現 i+1 次的序列總概率”，調整低頻次序列計數（如出現 1 次的序列計數降為 0.22），但對高階模型易加劇過擬合。

③階數自適應：回溯模型（Backoff）平衡擬合與泛化

????????傳統固定階數馬爾可夫模型存在 “高階擬合好但泛化差，低階泛化好但擬合差” 的矛盾。研究引入 Katz 回溯模型，實現階數的動態自適應。

????????高頻序列用高階：若某字符序列在訓練集中出現頻次高于設定閾值（如 10），用高階模型（如 5 階）計算下一個字符的概率，確保對常見組合的擬合精度。

????????低頻序列退低階：若序列頻次低于閾值，自動退化為低階模型（如 2 階），避免因稀疏性導致概率失真。

????????概率歸一化：對退階后計算的概率進行歸一化，確保同一序列的所有可能后續字符概率和為1.

3.2 對基于模板的模型進行優化

????????針對傳統PCFG模型（基于模板的代表）依賴外部字典、泛化差的缺陷，論文提出兩類優化方向：

① 模板概率分配優化：傳統PCFGw通過訓練集計數獲取模板概率（該模板出現次數 / 總密碼數），論文提出 “用馬爾可夫模型預測模板”，基于字符類型序列的轉移概率計算模板概率，提升泛化能力；

????????首先將模板轉化為“字符類型序列”或“類型切換序列”（緊急爐類型變化點）；

????????基于訓練集中所有密碼的類型序列，訓練一個 “類型級馬爾可夫鏈”，，學習類型間的轉移概率。eg：1 階模型中，計算 “α后接β” 的概率P(β|α)?= 訓練集中 “α后接β” 的次數 / 訓練集中 “α后接任意類型” 的總次數。

????????對于任意模板（無論是否在訓練集中出現），通過類型級馬爾可夫模型計算其類型序列的概率，作為模板概率。eg：模板α^2\β^1)的類型序列為ααβ，其概率為P(α|start) ×P(α|α) ×P(β|α)（start為起始符號）

優勢：即使測試集中出現訓練集未見過的新模板，模型也能基于類型轉移規律分配合理概率，避免 “零概率” 問題，泛化性顯著優于傳統計數方法。

② 片段實例化優化：傳統PCFGw依賴外部字典實例化字母片段（未在字典中的序列概率為 0），論文提出 “從訓練集生成字典” 或 “用馬爾可夫模型計算片段概率”。核心是 “從訓練數據中學習片段概率” 并引入平滑技術，覆蓋更多序列，如訓練集字典使PCFGw破解率從 50% 提升至 75%。

????????從訓練集生成字典：

• 遍歷訓練集中所有密碼，按模板片段的 “類型 + 長度” 拆分出所有片段，構建分類型、分長度的片段庫。
• 對于某一 “類型 + 長度” 的片段（eg：α^6），其下某具體片段（如 “passwd”）的概率 = 該片段在訓練集中的出現次數 / 訓練集中該 “類型 + 長度” 的所有片段總次數。
• 優勢是完全基于用戶真實密碼片段，覆蓋個性化組合；局限是對訓練集中未出現的稀疏片段，仍分配概率 0，存在稀疏性問題。

????????用馬爾可夫模型計算片段概率：

• tb-co-mc 模型：模板概率用傳統計數（co），片段實例化用馬爾可夫（mc）。模板概率仍通過訓練集計數計算。片段實例化時，對字母片段、數字片段分別訓練對應長度的馬爾可夫鏈，計算具體字符序列的概率。
• tb-mc-mc 模型：模板概率與片段實例化都用馬爾可夫（mc）。模板概率通過類型級馬爾可夫模型計算，片段實例化用字符級馬爾可夫模型，并引入 “加 δ 平滑”，對未出現的片段分配極低但非零的概率，解決稀疏性問題。

四、新型密碼評估工具：概率閾值圖

????????針對傳統 “猜測數圖（Guess-Number Graphs）” 計算成本高、覆蓋范圍有限的缺陷，論文提出概率閾值圖，作為 Type-1 研究（對比不同密碼集相對強度）的核心評估工具。

4.1 介紹

????????以 “對數尺度的概率閾值” 為橫軸（單位：2^{-x}，x為橫軸坐標），“概率高于該閾值的密碼百分比” 為縱軸。圖中某點(x,y)表示測試集中y%的密碼，其概率不低于2^{-x}。

4.2 步驟

? ? ? ? 基于目標密碼模型，計算測試集中每一條密碼的概率。設定一系列概率閾值。對每個閾值統計測試集中概率高于該閾值的密碼數量，計算占比。以閾值的對數為軸，占比為縱軸，畫線。

五、總結

????????本研究通過提出新型評估工具、優化密碼模型、開展大規模實驗，為密碼研究提供了更高效的方法論與技術框架，優化后的全字符串馬爾可夫模型可替代PCFG成為新的主流模型，為后續密碼強度評估、破解工具開發提供重要支撐。