基于格的密钥封装机制在主成分分析下的比特安全性分析去年年中我们项目组在评估一套格基密钥封装机制KEM的参数方案时遇到了一个挺现实的问题理论上比特安全性可以用经典格攻击估计器去估算但实例数量一多、维度一高估算耗时和结果解读都变得很笨重。后来我试着把主成分分析PCA引入到安全特征分析流程中发现这条路虽然不能替代严格的安全性证明却能在参数筛选和异常样本排查上帮上大忙。这篇文章就把我们这套“PCA辅助比特安全性分析”的思路、流程、踩过的坑完整记录下来。适合正在做后量子密码算法评估、KEM参数选型或者对格密码安全性分析方法感兴趣的同学参考。1. 为什么要把PCA和格基KEM的安全性分析放在一起1.1 比特安全性到底在衡量什么先理清概念。比特安全性bit security描述的是破解一个密码系统所需的最小计算工作量通常用“大约需要执行 2 的多少次方次基础操作”来表达。比如128比特安全就是说攻击者最乐观的情况下也要付出接近2^128量级的代价才能破解。格基KEM的安全性建立在某些格问题难解性假设上最常见的是带错误学习问题LWE及其变体。攻击者手里有公钥、密文要从这些公开数据中恢复出私钥或会话密钥本质上等价于求解一个带噪声的线性方程组。这个问题的难度取决于若干参数格的维度 n、模数 q、噪声分布的标准差 σ还有实例的数量 m。比特安全性并不是一个可以直接从参数公式里精确算出来的数值它高度依赖于攻击算法的演进。目前通用的做法是套用已知的最优攻击模型比如基于格基约化算法BKZ系列的“核心SVP”模型然后在给定参数下输出一个保守估计值。这一步在参数不多时很快但如果你想在一大批候选参数里做安全强度筛选每一条都要跑完整估计就会非常耗时。1.2 格基KEM的安全性本质上是一个高维数据问题这是我觉得最关键的一个切入点。无论是私钥、公钥、密文还是中间计算产生的临时噪声向量在计算机里都以高维数组的形式存在。就拿我们研究的模拟项目X来说它的公钥本质上是一个包含若干多项式的矩阵每个多项式有 n 个系数密文包含两个向量每个向量同样有 n 个系数。如果 n 取512那单个样本就对应上千个数值特征。更重要的是这些特征之间并不独立。LWE问题的噪声向量存在统计规律公钥与密文之间又存在代数约束私钥的分布和参数选取也存在明显相关性。换句话说高维数据内部存在结构性的冗余。这时候PCA就有用武之地了它通过线性变换把高维相关特征压缩为少数几个互不相关的主成分并且按照方差贡献率从大到小排序。前几个主成分往往就能概括数据中的绝大部分结构性信息。打个不严谨但容易理解的比方你面前有一堆KEM参数配置每个配置包含几十上百个内部统计量。肉眼根本看不出这些统计量和最终安全强度之间的关系。PCA就像把这一堆混杂的信息“拧干水分”浓缩成几个综合指标让规律自己显形。1.3 用PCA辅助安全性分析的场景边界这里必须先把边界说清楚避免误导。PCA能做的是“探索”和“筛选”给出一批参数样本PCA可以帮你快速区分哪些参数组合在统计特征上离得更近哪些明显异常以及不同安全级别的样本在高维空间里是否形成可分离的簇。PCA不能做的是“证明”和“保证”它不产生任何安全性下界也不能替代基于最坏情况规约的密码分析。就算某个参数簇在PCA投影图上和其他簇分得再开也不代表这个参数就一定安全。所以在我们实际项目中PCA被定位为“第一层粗筛器”后面还跟着完整的经典安全估计算法验证。这样既省时间也不至于丢失严谨性。2. 分析流程的前半段数据采集与特征工程2.1 样本从哪来模拟KEM实例不能随便抓整个流程的第一步是生成用于分析的数据集。这部分最容易被忽视但后来我意识到它直接决定后面分析的有效性。我们的做法是这样用模拟项目X的开源代码在固定的安全参数集下批量生成密钥对并执行封装和解封装流程。每次运行除了记录是否成功封装/解封装之外还把过程中的关键中间数据导出公钥矩阵和密文向量的全部系数临时噪声向量的系数统计拒绝采样次数如果方案里有拒绝采样多项式乘法后中间结果的系数分布情况这里有一个容易犯的错误直接拿“原始系数”当特征喂给PCA。系数是高度离散的而且不同特征的重纲不一样有些是多项式系数有些是采样次数PCA是基于方差最大化做投影的如果你不归一化那些数值大的特征就会主导主成分把真正有价值的统计信息淹没掉。我们当时吃了这个亏第一次跑PCA第一主成分几乎完全被“拒绝采样次数”这一个特征霸占散点图看起来很有规律但那条规律其实是样本生成流程本身的噪声和安全性能毫无关系。2.2 我们最终选定的特征集经过几轮试错我们把特征集稳定在以下维度上特征类别具体特征提取意义系数分布公钥矩阵系数的均值、标准差、峰度、偏度反映格基数据的随机性与统计规律密文相关性密文向量与公钥对应位置的皮尔逊相关系数捕捉封装过程中引入的代数关联误差信息噪声向量的估计标准差与实际标准差之比衡量噪声是否符合假设分布拒绝采样统计单次封装拒绝采样次数、二次拒绝率反映方案实现的离散性特征代数结构参数向量间的Gram-Schmidt正交化长度平方和近似反映格基约化难度要注意这里选的特征不追求“全”而是追求“有区分度”。特征维度太多会导致维数灾难PCA虽然能降维但如果你原始特征里混入大量纯噪声维度前几个主成分的方差贡献率会被稀释反而看不出结构。实践下来的建议是特征数量控制在20到50之间比较合适太少则信息不足太多则噪声过多。我们最终固定使用了32个特征。2.3 数据标准化是硬前提PCA对特征的尺度非常敏感。如果不做标准化量纲大的特征比如系数值范围在几千的量级会直接主导协方差矩阵PCA投影结果完全变形。我们使用的是 z-score 标准化也就是每个特征减去均值、除以标准差。这一步做完之后所有特征都处于近似同一量级。再跑PCA主成分的语义就干净多了——它反映的是样本间结构性差异而不是数值尺度差异。另外还有一个细节标准化参数应该只在训练样本上计算然后用同一个均值和标准差去处理测试样本绝不能用全体数据的统计量来标准化。这一点和机器学习里防止数据泄露的思路完全一致。我们早期图省事对整个数据集统一做了标准化结果后续在做交叉验证的时候发现精度虚高后来改成按折分别计算才正常。3. PCA分析的主干步骤从协方差矩阵到比特安全区间估计3.1 PCA的标准实现步骤PCA的数学核心不复杂但每一步都有值得注意的实操细节。构建数据矩阵。行是样本KEM参数实例列是特征。对数据矩阵做标准化得到零均值、单位方差的数据。计算协方差矩阵或者用奇异值分解直接对数据矩阵操作。特征维度为32时协方差矩阵是32×32计算开销很小。对协方差矩阵做特征分解得到特征值和对应的特征向量。将特征值从大到小排列对应的特征向量就是第1、第2、……主成分方向。选取主成分个数。常用标准是累积方差贡献率达到某个阈值一般选80%到95%。在我们实验中32个特征经过分解后发现前4个主成分累积方差贡献率接近90%。也就是说这4个综合变量足以代表原始32维特征中的绝大部分信息。下面是我们在项目中使用的核心分析代码骨架数据经过脱敏处理import numpy as np from sklearn.preprocessing import StandardScaler from sklearn.decomposition import PCA # X: shape (n_samples, n_features) # y: shape (n_samples,) 记录每个样本对应的Core-SVP估算结果(比特数) scaler StandardScaler() X_scaled scaler.fit_transform(X) pca PCA(n_components6) X_pca pca.fit_transform(X_scaled) # 查看各主成分方差贡献率 print(Explained variance ratio:, pca.explained_variance_ratio_) # 结合Core-SVP估算结果做区间对应关系分析 for comp_idx in range(3): comp_vals X_pca[:, comp_idx] for level in [80, 96, 112, 128, 160, 192]: mask (y level) (y level 16) subset comp_vals[mask] if len(subset) 0: print( fPC{comp_idx1} | level≈{level}-{level16} | fmean{subset.mean():.4f} | std{subset.std():.4f} )这段代码输出的内容很有用它可以告诉你在不同比特安全级别区间某个主成分的均值、标准差是否有明显移动。如果某个主成分在不同安全级别下的均值呈现单调变化那就可以把它当做一个“安全性指示变量”。3.2 主成分与比特安全级别的对应关系分析拿到主成分投影值后接下来的关键一步是把主成分和已知的经典评估结果做对照。我们为每一个样本都跑了一遍 lattice-estimator 风格的 Core-SVP 估算得到它对应的比特安全数值。然后把这些数值按区间分组观察每个区间内各个主成分的分布。结果很清晰第一主成分 PC1 主要反映参数的“规模维度”比如模数 q 的位数、维度 n 的大小。它和比特安全级别的相关性最高但并不是单调函数。第二主成分 PC2 反映的是“噪声分布形态”比如噪声标准差与模数比值的统计特征。在部分参数区间PC2 对安全级别的影响呈现先升后降的非线性关系。第三主成分 PC3 更多捕捉的是参数之间的互相关特征比如公钥不同部分之间的相关性强度。这个成分在传统安全性分析里几乎不会被单独考虑但它确实携带了一些结构性信息。这里我要特别提醒一个容易踩的坑PCA 主成分方向是数据驱动的不是密码学驱动的。你不能把“PC1 和比特安全相关性高”直接解读成“PC1 是安全性的直接度量”。PCA 只负责把方差最大的方向找出来至于这个方向是否对应安全性必须靠外部标签比如 Core-SVP 估算结果来验证。我们在初期就差点被误导当时 PC1 和样本的维度参数 n 高度相关而 n 又与比特安全粗略正相关于是看上去 PC1 似乎能预测安全性。但换了另一组参数分布的数据后这个关系就变得极不稳定。后来才意识到PC1 反映的只是数据生成过程中方差最大的那个主轴而这个主轴在不同参数采样策略下可能变化。3.3 如何用 PCA 结果辅助比特安全区间估计既然 PCA 不能直接给精确比特数那么它怎么“辅助”估计算法我们把 PCA 当做一个“快速预分类器”来用。流程是这样的对一批新参数样本先提取同样的 32 个特征。用已经训练好的 PCA 模型做变换得到各样本在主成分空间中的坐标。计算该坐标与训练集中各已知安全级别簇中心的欧氏距离。根据最近邻簇给出该样本的“初步安全级别区间”。只有落在目标安全级别区间附近比如 128 到 160 比特之间的样本才送去做完整 Core-SVP 估算验证。这样做的好处非常实际对于明显落在低安全区的参数你根本不需要跑昂贵的格基约化估算直接淘汰即可对于安全级别符合要求的候选项再花资源做精确验证。整个筛选用时从原来的“每样本十几秒级”下降到了“每样本毫秒级”而且不会漏掉高安全性样本。有位同事问过我为什么不直接用 PCA 降维后的变量去做一个回归模型直接预测比特数也可以但我们不建议这么做。原因在于回归模型给出的数值预测会给使用者一种虚假的精确感而实际上 PCA 投影丢失的信息可能导致预测误差远大于预期。用区间估计的方式至少保留了“这个数只是个粗范围”的心理预期。4. 常见问题与排查技巧实录4.1 一个典型的“假结构”案例第一次拿到看起来非常漂亮的 PCA 散点图时我们都很兴奋——不同安全级别的样本在投影空间里分成了清晰的三簇。后来一查发现训练数据是人为按不同参数组分开存放的样本顺序里带了隐含的分组信息数据处理时又没有打乱PCA 投影图里的“聚类”实际上是数据采集顺序的伪影。从那以后我们规定任何 PCA 实验之前必须先随机打乱样本顺序并保证训练集和验证集独立划分。散点图再漂亮也要用外部标签交叉验证不能光看图说话。4.2 常见问题速查问题现象可能原因排查方向第一主成分方差贡献率超过95%标准化没做好某个特征量纲过大或过小检查特征标准化方式确认是否对每个特征分别标准化前5个主成分累积贡献率不足70%特征集包含太多与结构无关的噪声维度精简特征优先保留基于密码学统计量的特征散点图呈现“螺旋”或“抛物线”状PCA的线性假设不满足数据结构呈非线性考虑引入核PCA或UMAP等非线性方法对照分析同一安全级别样本投影过于分散特征提取环节存在随机性过强的测量量换用更稳定的统计特征比如分位数替代原始均值PCA分簇与Core-SVP结果完全一致可能是过拟合假象在独立验证集上重新测试确认是否复现某主成分与安全级别相关性极高但另一数据集上失效主成分方向依赖训练数据的采样分布用多种参数采样策略构建训练集避免单一采样偏差4.3 结合格基约化理论解释 PCA 结果的合理性在分析过程中我们发现把 PCA 结果放回格基约化理论里做交叉解释非常有用。举一个例子我们观察到 PC2 在高安全级样本中的分布呈现出“方差收窄”的现象。回到格理论高安全级参数通常对应更“紧”的格即格基向量之间的正交性更好Gram-Schmidt 规范化后的长度分布更集中。这正好解释了为什么在特征集里加入 Gram-Schmidt 正交化长度平方和后PC2 的安全级别区分能力显著提升。这个发现告诉我们特征工程不只是机械地堆统计量最好能够结合密码学的理论认知来设计特征。基于格基约化理论选特征PCA 的结果更有解释力也更容易赢得同行的信任。我也尝试过把 PCA 分析和侧信道信息的特征集放在一起对比发现 PCA 在两类数据集上都能提取出有效主成分但两者对应的主成分方向几乎完全不同。这说明 PCA 提取到的是数据集内部的结构而不是某种密码学上的“通用安全性指标”。这本身就是很重要的认知。5. 实操中的几条额外心得除了流程本身再说几个我真正用起来之后才明白的细节。第一训练集规模不需要特别大。我们最终使用了大约 2400 个 KEM 实例32 个特征PCA 的效果已经非常稳定。再多加到上万条区分度提升有限但计算开销增加不少。关键在于样本的多样性而不是单纯的数量。如果你的样本都集中在同一个参数区间哪怕一万条PCA 也学不到不同安全级别之间的分界面。第二尽量使用多种参数生成策略。我们早期的训练数据全部来自同一种随机种子生成方式结果 PCA 对同分布数据表现优秀对另一组采样策略的样本几乎失效。后来我们引入了三种不同的参数采样策略包括随机均匀采样、基于目标安全等级的逆向采样、以及网格搜索型采样PCA 模型的泛化能力才真正稳定下来。第三可以把 PCA 和层次聚类结合。PCA 降维到三维后我们在投影空间里跑了一遍层次聚类再对比聚类结果与 Core-SVP 的安全级别区间。两者的一致率在验证集上大约有 87%。虽然做不到工业级的精确预测但在参数初筛场景下已经足够有参考价值。第四工程实现上一些小细节如果特征矩阵过大协方差矩阵求解的内存占用会非常可观建议直接使用随机化 SVD 或者在线的 PCA 更新方式如果是在嵌入式环境或大规模调度流水线里部署可以先把 PCA 投影矩阵和均值、标准差参数固化这样每次预分类只需要一次向量点乘性能开销极低。最后再分享一个我自己印象很深的小实验把 PC1-PC2 投影图上的每一个点按安全级别从低到高染成渐变色然后用鼠标在图上扫过时你会直观地看到颜色在投影空间里并非连续渐变而是存在几个“跳变区”。这些跳变区对应的参数点再拿 Core-SVP 去核验往往就是安全性模型出现切换的位置比如从组合攻击模型切换到纯格攻击模型。这种高维结构里的“相变区域”靠传统一维参数扫描是很难一眼找到的PCA 投影却让它变得一目了然。这就是我最终认为 PCA 在比特安全性分析里真正有价值的地方——它不给出终极答案但能帮助你更高效地找到值得深挖的问题。
