1. 项目概述当密码安全遇上余弦相似度最近在做一个安全审计相关的项目遇到了一个挺有意思的需求如何量化地评估用户设置的密码之间的相似度。这可不是简单的字符串比对比如“Password123”和“password123”这种大小写差异或者“MyDog2024”和“MyCat2024”这种部分替换。传统的编辑距离Levenshtein距离在这里有点力不从心它更关心“变成另一个字符串需要多少步操作”但对于密码这种短文本且可能包含字符类别大写、小写、数字、符号和模式如“首字母大写常见名词年份”的结构我们需要一个能捕捉“模式相似性”而非“字符差异性”的指标。这时我想到了在自然语言处理和信息检索领域老生常谈的余弦相似度。这个算法通常用于比较两段文本的语义相似性其核心思想是把文本转换成高维空间中的向量然后计算这两个向量夹角的余弦值。夹角越小余弦值越接近1表示越相似夹角越大余弦值越接近0表示越不相关。听起来很抽象我们可以把每个密码想象成一部电影向量就是这部电影在不同类型动作、爱情、科幻等上的评分。两部电影即使片名完全不同但如果它们在“科幻”和“冒险”类型上都得了高分那它们对特定观众来说就是“相似”的。密码同理我们可以定义一些“特征维度”比如“大写字母占比”、“数字序列长度”、“是否包含常见键盘路径如‘qwerty’”等将密码向量化再用余弦相似度计算它们的“模式相似度”。这个思路对于批量检查用户密码策略合规性、识别弱密码变体、甚至在风控中检测疑似共用或泄露的密码模式都有不小的实用价值。今天我就来详细拆解一下如何将余弦相似度算法“嫁接”到密码相似度计算这个场景中包括核心思路、向量化策略、算法实现细节以及在实际操作中踩过的那些坑。2. 核心思路从字符序列到特征向量直接比较两个密码字符串“abc123”和“123abc”编辑距离是6全部字符位置互换但直观上它们都包含相同的字符集只是顺序不同具有一定的模式相似性。余弦相似度要做的就是先忽略字符的具体顺序从更高维的“特征”视角来刻画一个密码。2.1 密码特征工程这是整个方案中最关键、最需要经验的一步。特征选得好算法效果就好。我们需要提取那些能有效区分密码强弱、并能表征用户设置习惯的特征。以下是我在实践中总结出的一套基础特征维度你可以根据具体场景扩充长度特征密码长度本身是一个重要特征。可以单独作为一个维度也可以分段处理如是否小于8、8-12、大于12。字符类别分布这是核心中的核心。计算密码中四类字符的占比小写字母占比大写字母占比数字占比特殊符号如 !#$%^*占比 一个强密码通常要求这四类都有一定分布而“Password123”可能大写字母和数字占比较低。序列特征数字序列长度连续数字的最大长度如“123”长度为3。过长的数字序列是弱密码的典型标志。字母序列长度连续字母的最大长度。键盘路径序列是否包含常见的键盘相邻键序列如“qwerty”、“asdfgh”、“123456”。这需要预先定义一个常见路径字典进行匹配。熵相关特征近似虽然不能直接计算香农熵但可以用一些代理特征。字符集大小密码中不重复字符的数量。字符类别数密码中包含上述小写、大写、数字、符号几类字符。结构模式特征二值特征判断密码是否符合某些常见模式。是否以大写字母开头常见于“首字母大写名词”模式。是否以数字结尾常见于“单词年份”模式。是否整体为纯数字或纯字母。注意特征维度的选择需要平衡。维度太少区分度不够维度太多可能引入噪声且计算量增加。建议从上述基础特征开始根据实际业务数据的效果进行迭代筛选。2.2 向量化与标准化每个密码根据上述特征列表可以生成一个数值向量。例如对于密码“Pssw0rd2024”长度12小写字母占比5/12 ≈ 0.417大写字母占比1/12 ≈ 0.083数字占比4/12 ≈ 0.333特殊符号占比1/12 ≈ 0.083最长数字序列长度4 (“2024”)字符集大小10 (P, , s, w, 0, r, d, 2, 4) 注意’s’重复了只算一个。字符类别数4 (包含所有四类)是否以大写开头是 (1)是否以数字结尾是 (1)这样我们就得到了一个向量[12, 0.417, 0.083, 0.333, 0.083, 4, 10, 4, 1, 1]。接下来是标准化。由于特征量纲不同长度是计数占比是0-1的小数序列长度是计数直接计算余弦相似度会有问题因为量级大的特征会主导结果。我们必须进行标准化通常使用Min-Max标准化或Z-score标准化将每个特征维度缩放到一个可比的范围。这里我推荐Min-Max因为它能将所有特征映射到[0,1]区间更直观。我们需要在整个密码数据集上计算每个特征的最大最小值然后对每个密码向量进行缩放。3. 算法实现与实操步骤理论讲完了我们来看看具体怎么实现。我会用Python来演示因为它有丰富的科学计算库。3.1 环境准备与依赖安装首先确保你的环境有必要的库。我们主要用到numpy进行向量运算。pip install numpy如果需要更复杂的特征提取比如更精准的键盘路径检测可能还需要一些基础库但核心计算numpy就够了。3.2 密码特征提取器实现我们来编写一个密码特征提取的类。为了清晰我们分步骤实现。import numpy as np import re class PasswordFeatureExtractor: 密码特征提取器 # 定义一些常见的键盘相邻序列可扩展 KEYBOARD_SEQUENCES [ qwerty, asdfgh, zxcvbn, 123456, !#$%^, qaz, wsx, edc, rfv, tgb, yhn, ujm, ik, ol, 1qaz, 2wsx, 3edc, 4rfv, 5tgb, 6yhn, 7ujm, 8ik, 9ol, 0p ] def __init__(self): # 用于存储全局最大最小值以便标准化 self.feature_mins None self.feature_maxs None def extract_features(self, password): 提取单个密码的特征向量 返回: numpy array if not password: return np.zeros(10) # 根据特征数量返回零向量 features [] pw_len len(password) # 1. 长度特征 features.append(pw_len) # 2. 字符类别占比 lower_cnt sum(1 for c in password if c.islower()) upper_cnt sum(1 for c in password if c.isupper()) digit_cnt sum(1 for c in password if c.isdigit()) special_cnt pw_len - lower_cnt - upper_cnt - digit_cnt features.append(lower_cnt / pw_len) features.append(upper_cnt / pw_len) features.append(digit_cnt / pw_len) features.append(special_cnt / pw_len) # 3. 序列特征 - 最长数字序列 digit_sequences re.findall(r\d, password) max_digit_seq_len max((len(seq) for seq in digit_sequences), default0) features.append(max_digit_seq_len) # 4. 熵相关特征 - 字符集大小 unique_chars len(set(password)) features.append(unique_chars) # 5. 字符类别数 char_categories 0 if lower_cnt 0: char_categories 1 if upper_cnt 0: char_categories 1 if digit_cnt 0: char_categories 1 if special_cnt 0: char_categories 1 features.append(char_categories) # 6. 结构模式特征 # 是否以大写字母开头 starts_with_upper 1 if password and password[0].isupper() else 0 features.append(starts_with_upper) # 是否以数字结尾 ends_with_digit 1 if password and password[-1].isdigit() else 0 features.append(ends_with_digit) # 7. (可选) 键盘路径检测 - 作为一个二值特征示例 # 这里简化处理检查是否包含任何预定义的键盘序列 has_keyboard_seq 0 lower_pw password.lower() for seq in self.KEYBOARD_SEQUENCES: if seq in lower_pw: has_keyboard_seq 1 break features.append(has_keyboard_seq) return np.array(features) def fit(self, password_list): 在密码数据集上拟合计算每个特征维度的最小值和最大值 用于后续的Min-Max标准化 if not password_list: return self # 提取所有密码的特征 all_features [] for pw in password_list: features self.extract_features(pw) all_features.append(features) all_features_matrix np.vstack(all_features) # 计算每个特征列的最小值和最大值 # 注意避免除零对于最大值等于最小值的特征我们将其缩放范围设为[0,1]即所有值变为0.5 self.feature_mins np.min(all_features_matrix, axis0) self.feature_maxs np.max(all_features_matrix, axis0) return self def transform(self, password): 提取特征并应用Min-Max标准化 features self.extract_features(password) if self.feature_mins is None or self.feature_maxs is None: raise ValueError(必须先调用 fit() 方法在数据集上拟合。) # Min-Max 标准化: (x - min) / (max - min) # 处理 max min 的情况避免除零 ranges self.feature_maxs - self.feature_mins ranges[ranges 0] 1.0 # 如果范围为0设为1这样分子为0结果为0 normalized (features - self.feature_mins) / ranges return normalized3.3 余弦相似度计算特征向量标准化后计算余弦相似度就很简单了。余弦相似度公式为cosine_sim(A, B) (A · B) / (||A|| * ||B||)其中A·B是点积||A||是向量A的欧几里得范数模长。def cosine_similarity(vec_a, vec_b): 计算两个向量的余弦相似度 输入应为numpy array dot_product np.dot(vec_a, vec_b) norm_a np.linalg.norm(vec_a) norm_b np.linalg.norm(vec_b) # 避免除零错误 if norm_a 0 or norm_b 0: return 0.0 return dot_product / (norm_a * norm_b)3.4 完整流程封装我们将上述步骤封装成一个完整的密码相似度计算器。class PasswordSimilarityCalculator: 密码相似度计算器基于余弦相似度 def __init__(self): self.extractor PasswordFeatureExtractor() self.is_fitted False def fit(self, password_list): 使用一个密码列表来拟合特征提取器计算标准化参数 这个列表应该是你业务中典型的密码样本集 self.extractor.fit(password_list) self.is_fitted True return self def calculate_similarity(self, pw1, pw2): 计算两个密码的相似度得分范围[0, 1] 1表示特征模式完全相同0表示完全不同 if not self.is_fitted: # 如果没有拟合数据可以临时用这两个密码来拟合但不推荐 # 更好的做法是要求用户先提供数据集进行fit raise ValueError(请先使用 fit() 方法提供数据集进行拟合。) vec1 self.extractor.transform(pw1) vec2 self.extractor.transform(pw2) return cosine_similarity(vec1, vec2) def find_similar_passwords(self, target_pw, password_candidate_list, threshold0.85): 在一个候选密码列表中找出与目标密码相似度高于阈值的密码 返回: 列表元素为(密码, 相似度得分) if not self.is_fitted: raise ValueError(请先使用 fit() 方法提供数据集进行拟合。) target_vec self.extractor.transform(target_pw) results [] for candidate in password_candidate_list: cand_vec self.extractor.transform(candidate) sim_score cosine_similarity(target_vec, cand_vec) if sim_score threshold: results.append((candidate, sim_score)) # 按相似度降序排序 results.sort(keylambda x: x[1], reverseTrue) return results3.5 实战演示让我们用一个例子来跑通整个流程。# 1. 准备一个模拟的密码数据集用于拟合标准化参数 training_passwords [ Password123, admin2024, qwertyuiop, MySecurePwd!, 1234567890, JohnDoe#88, iloveyou, Summer2024!, Qwerty123, Pssw0rd ] # 2. 初始化计算器并拟合数据 calculator PasswordSimilarityCalculator() calculator.fit(training_passwords) # 3. 定义我们要检查的目标密码和候选密码 target_password Pssword2024 # 注意这里故意拼写错误测试相似性 candidate_list [ Password2024, Pssw0rd2024, password2024, Admin1234, pssword2024, Winter2023! ] # 4. 计算单个相似度 similarity_score calculator.calculate_similarity(target_password, Pssw0rd2024) print(f{target_password} 与 Pssw0rd2024 的相似度: {similarity_score:.4f}) # 5. 在列表中查找相似密码 similar_ones calculator.find_similar_passwords(target_password, candidate_list, threshold0.7) print(f\n在候选列表中与 {target_password} 相似度高于0.7的密码有) for pw, score in similar_ones: print(f - {pw}: {score:.4f})运行这段代码你会看到输出结果。像“Pssword2024”和“Pssw0rd2024”数字0替换了字母o这样的密码尽管字符不完全相同但由于长度、字符类别分布、结构大写开头、数字结尾等特征高度一致它们的余弦相似度会非常高。而它与“Admin1234”的相似度就会低很多。4. 参数调优与效果评估算法搭起来了但效果到底怎么样我们需要一套方法来评估和调优。4.1 相似度阈值的选取阈值如上面代码中的threshold0.85的选择至关重要它直接决定了算法的灵敏度和误报率。阈值过高可能漏掉真正相似的密码变体漏报。阈值过低可能将不相关的密码判为相似误报。如何确定阈值没有银弹需要结合业务场景。业务定义首先明确业务上认为“多相似才算相似”。是要求密码几乎一样如只差一个字符还是允许一定的模式变化样本测试准备一个标注好的测试集包含“确实相似”的密码对和“确实不相似”的密码对。例如相似对(Password123, Pssword123)、(Summer2024, Summer2023)不相似对(Password123, Admin456)、(qwerty, 5tgb^YHN)绘制ROC曲线在不同阈值下计算真阳性率TPR找出了多少真正的相似对和假阳性率FPR误判了多少不相似对。选择曲线上靠近左上角的点或根据业务对误报的容忍度来定。例如在风控场景可能宁愿漏报也不能误报阈值就设高一些在用户提示“您的密码与旧密码太相似”的场景可以适当调低阈值提高提醒的覆盖率。4.2 特征权重的调整我们目前将所有特征视为同等重要。但在现实中某些特征可能更具区分度。例如“是否包含键盘路径”这个特征一旦出现值为1几乎就能断定密码较弱那么这个特征在相似度计算中的权重就应该提高。如何调整有两种方法经验加权在计算点积前给特征向量乘以一个权重向量W。W的每个元素对应一个特征的权重。你可以根据特征的重要性手动设定如长度权重1.2键盘路径权重1.5其他为1.0。基于模型学习如果有大量的标注数据密码对及其是否相似的标签可以使用逻辑回归等模型来学习每个特征的权重。这更科学但成本也更高。在我们的cosine_similarity函数中加权计算可以这样融入def weighted_cosine_similarity(vec_a, vec_b, weights): 带权重的余弦相似度计算 weights: 与特征向量同维度的权重数组 weighted_a vec_a * weights weighted_b vec_b * weights return cosine_similarity(weighted_a, weighted_b)4.3 与其它算法的对比为什么要用余弦相似度而不是其他算法这里做一个简单对比算法原理在密码相似度计算中的优缺点适用场景余弦相似度比较特征向量在空间中的方向一致性。优点对绝对数值不敏感关注模式分布适合高维特征结果规整到[0,1]。缺点严重依赖特征工程的质量无法直接捕捉字符顺序的局部变化。密码模式相似性、批量弱密码检测、风控聚类。编辑距离计算将一个字符串变为另一个所需的最少单字符编辑插入、删除、替换次数。优点直观直接作用于字符串能捕捉顺序变化。缺点对“Pss”和“Pass”距离为2对“123abc”和“abc123”距离为6可能过高结果受长度影响大需归一化。轻微修改检测如旧密码后加数字、完全相同的子串检测。Jaccard相似度计算字符集合的交集与并集之比。优点计算简单完全忽略顺序和重复。缺点信息损失大“aabb”和“ab”的相似度为1.0因为字符集都是{a,b}。快速粗筛对字符集重合度要求高的场景。最长公共子序列寻找两个字符串共有的、相对顺序一致的最长子序列。优点能捕捉非连续但顺序一致的公共部分。缺点计算复杂度稍高对“Dog2024”和“2024Dog”的LCS是“2024”或“Dog”可能低估整体相似性。检测密码中包含的常见单词或日期序列。实操心得没有最好的算法只有最合适的算法。在实际项目中我常常采用混合策略。例如先用余弦相似度进行快速初筛因为它计算快适合批量处理对高于某个阈值的候选对再用编辑距离进行精细复核综合判断。这样既能保证效率又能提高准确性。5. 常见问题、陷阱与优化策略在实际部署和应用中我遇到了不少坑。这里总结一下希望能帮你避开。5.1 特征提取的边界情况处理空密码或超短密码代码中虽然做了简单判断但在生产环境中密码长度小于4的情况可能需要特殊处理。例如直接返回一个与其他任何密码相似度都为0的特定向量或者直接判定为无效输入。非ASCII字符如果密码允许包含中文或emoji我们的特征提取需要扩展。str.isdigit()和str.islower()等方法对中文无效。需要更通用的Unicode类别判断或者将这类字符统一归入“特殊符号”类别。键盘路径检测的误判我们定义的KEYBOARD_SEQUENCES可能不全也可能误判。比如“asdf”确实是键盘路径但“news”这个单词就不是。更稳健的方法是使用更全面的键盘布局字典并考虑斜向路径如“qse”。也可以引入模糊匹配允许路径中有1-2个字符的间隔。5.2 标准化带来的“信息扭曲”Min-Max标准化依赖于拟合数据集的最大最小值。这里有个关键问题如果新来的密码其某个特征值超出了拟合时的范围怎么办例如拟合数据中密码最长20位但来了一个30位的密码。标准化公式(x - min) / (max - min)会产生大于1的值破坏了[0,1]的区间假设。解决方案稳健的数据集用于fit的数据集应尽可能覆盖所有可能出现的密码特征范围可以加入一些极长、极复杂的虚拟密码。截断处理在transform时对超出[min, max]范围的值进行截断强制设为0或1。或者使用np.clip函数。normalized (features - self.feature_mins) / ranges normalized np.clip(normalized, 0.0, 1.0) # 将值限制在[0,1]区间考虑使用RobustScaler如果特征中存在异常值使用基于中位数和四分位数的标准化方法可能更稳定但对密码特征来说Min-Max更直观。5.3 性能考量与大规模计算当需要比较一个密码对上百万个现有密码时逐对计算余弦相似度是O(n)的复杂度可能成为瓶颈。优化策略向量化计算利用numpy的广播机制一次性计算一个目标向量与一个矩阵所有密码向量堆叠而成的余弦相似度。这比循环快几个数量级。# target_vec 形状 (m,) # all_vectors 形状 (n, m) # 一次性计算所有相似度 dot_products np.dot(all_vectors, target_vec) norms_all np.linalg.norm(all_vectors, axis1) norm_target np.linalg.norm(target_vec) similarities dot_products / (norms_all * norm_target)近似最近邻搜索如果密码库极大如十亿级精确计算所有对的相似度不可行。可以考虑使用局部敏感哈希或球树等索引结构进行近似搜索快速找到可能相似的候选集再进行精确计算。预计算与缓存对于不变的密码库可以预计算所有密码的标准化特征向量和它们的L2范数模长。这样在计算相似度时只需要计算点积然后除以缓存的范数乘积大大减少计算量。5.4 安全与隐私注意事项这一点至关重要。处理密码即使是哈希值也需极度谨慎。绝不存储明文密码上述所有操作理想情况下应在密码的哈希值上进行不这行不通。因为哈希函数如SHA-256是雪崩效应的明文微小的变化会导致哈希值天差地别我们需要的“相似性”会完全丢失。因此必须在可信的、高度安全的隔离环境中进行密码相似度计算服务必须部署在严格管控的后端与数据库、应用服务器隔离。计算过程内存中的明文密码必须在计算完成后立即清除。结果日志脱敏输出的日志中只能包含密码的匿名ID或哈希绝不能记录明文密码或高相似度分数对应的具体密码对。合规性确保该技术的使用符合相关的数据安全法规和公司内部的安全策略。通常这类操作需要严格的安全评审和授权。6. 扩展应用场景与进阶思路基于特征向量的余弦相似度计算其潜力不止于简单的两两比较。6.1 密码策略合规性增强检查很多系统要求新密码不能与旧密码“过于相似”。传统的检查可能就是简单的字符串包含或编辑距离小于N。利用余弦相似度我们可以定义一个更科学的“相似度阈值”。当用户修改密码时系统可以计算新密码与最近用过的N个旧密码的相似度如果任何一对超过阈值则提示用户新密码与旧密码模式太像要求重新设置。6.2 弱密码聚类与模式发现在海量的密码数据库中当然是脱敏或哈希后的元数据我们可以使用聚类算法如K-Means、DBSCAN对密码特征向量进行聚类。同一个簇内的密码具有相似的特征模式。安全工程师可以分析这些簇发现流行的、潜在的弱密码模式例如“大写字母常见英文名两位年份”从而更新密码策略黑名单或加强针对性的安全提醒。6.3 结合词库与语义分析对于包含字典单词的密码我们可以进一步引入自然语言处理技术。例如使用词干提取器提取密码中的单词词干如“running”提取为“run”将“是否包含常见字典单词”、“包含的单词数”作为新的特征维度。甚至可以训练一个词向量模型将单词映射到向量空间从而计算密码中单词的语义相似度。这能捕捉到“Sunshine2024”和“Summer2024”之间的语义关联都与季节/天气相关这是纯字符特征难以做到的。6.4 实时风控中的应用在登录或注册风控中如果系统检测到某个IP或设备在短时间内尝试了多个高度相似的密码例如“Test001”、“Test002”、“Test003”即使这些密码本身复杂度尚可这种“序列化尝试”的行为模式也极有可能是自动化攻击脚本在试探。通过实时计算尝试密码之间的余弦相似度可以快速识别这种模式并触发风控规则如要求二次验证、临时封禁。实现这个功能需要在特征工程中加入“与上一次尝试密码的相似度”作为一个动态特征并维护一个短时间窗口内的尝试历史。密码安全是一个永恒的攻防战场。余弦相似度算法为我们提供了一个从“模式”和“特征”角度量化密码相似性的有力工具。它不再是简单地看字符是否相同而是去理解用户设置密码的习惯和结构。通过精心设计特征、合理设置阈值、并注意性能与安全这个工具可以有效地融入密码策略管理、安全审计和风控体系中提升整体的安全水位。当然它也不是万能的需要与其他技术如哈希加盐、速率限制、多因素认证等结合使用才能构建起纵深防御体系。