未知参数多重递归发生器的截低位还原.pdf

收稿日期:修回日期:基金项目:国家自然科学基金资助项目()作者简介:于寒冰()女硕士生主要研究方向为格理论与格密码分析:.:/未知参数多重递归发生器的截低位还原于寒冰 郑群雄(信息工程大学河南 郑州)摘要:多重递归发生器的可预测性问题即能否由一段截位序列还原多重递归发生器未知的参数与初态进而预测后面的序列是评估发生器的重要指标也是设计发生器的主要考量 目前截高位情形下的可预测性问题已被解决但截低位情形有待补充且截高位情形的方法不能平凡推广到截低位情形 研究表明截低位情形下多重递归发生器的可预测性问题可通过 步解决 首先通过格基约化找到序列的零化多项式其次计算零化多项式的结式与最大公因式还原模数与系数最后构造格还原初态并估计所需的截位数据量 对于模数是偶数的情形还原初态还可以采用带模高位的格方法 实验结果表明模数为偶数时同时使用两种初态还原方法可提高成功率关键词:多重递归发生器环上序列格基约化算法截位还原中图分类号:.文献标识码:文章编号:().第 卷第 期 年 月信 息 工 程 大 学 学 报 .随机数在密码学、统计采样、蒙特卡洛模拟、数值分析等领域中均有广泛应用 由于真正的随机数是使用物理现象产生的效率较低不能很好地满足实际需求因此实际中通常采用伪随机数代替真正的随机数 生成伪随机数常用的方法是使用确定算法生成伪随机序列即伪随机数发生器()线性同余发生器()是一类重要的 生成的序列 ()对于任意的整数 满足递归关系:其中:是模数 /()分别是种子、乘子和增量 需要说明的是本文中对于整数 用 /()表示模 的整数剩余类环并取 作为代表元 用 表示以 为底的对数 对于一个模数为 的 其生成序列的最大可能周期不超过 由于 具有简洁、高效、理论性质清楚等特点曾广泛应用于各类编译器内置的 函数中但是随着研究的不断深入 逐渐暴露出其生成序列周期短序列格结构明显等弊端 为规避以上不足寻找生成序列周期更长、性质更好的 密码学家开始研究 的高阶扩展 多重递归发生器()阶 生成的序列 ()对于任意的整数 满足递归关系:其中:是模数 /()是系数且不全为零 从 /()中任选 个不全为零的数 作为初态 按其递归关系生成序列 ()当 是素数时 阶 输出序列的最大周期是()当 是一般合数时设其标准分解为 阶 输出序列的最大周期是()()()如果 的特征多项式()是 /()上的本原多项式(本原多项式定义见定义)那么输出序列可达到最大周期通过 生成的一段序列片段预测后面的序列称为 的可预测性 可预测性不仅是评估 安全性的重要指标也是设计 的重要考量 对于 的可预测性的研究成果包括当输出序列的所有比特时文献证明了即使模数、乘子和增量都未知 也可以由不超过()长的生成序列片段预测 因此输出序列的全部比特是不安全的 文献发现如果模数 是 的方幂 生成的序列的高位部分比特比低位部分比特更随机所以为了提高 的抗预测能力建议使用截位的 即只输出 生成序列的高位部分比特 对于仅模数已知乘子和增量未知的情况 如果模数 给定 拍序列片段的高()比特文献可在()/)步内还原未知的参数 文献对于一般的模数也证明了类似结果 对于模数和乘子已知增量未知的情况给定一段截位序列(截取高位部分比特或者低位部分比特)文献给出了一个基于格的多项式时间算法但对于某些特殊的乘子该方法无效 对于模数、乘子和增量都未知的情况给定一段高位部分比特截位序列文献利用格可以在多项式时间内完成对 的预测但该方法依赖于两个格上的启发性假设 文献改进了文献的算法从而减少了算法运行时间和所需数据量对于 的可预测性研究可分为两大类:输出全比特序列片段和输出截位序列片段 当输出序列的所有比特时如果模数 是一个素数且输出序列长度为 ()算法可在()步内还原 如果模数是一般合数 可通过扩展 算法进行预测 当仅输出最高比特序列文献和文献各自独立证明了环 /()上的本原序列与其最高比特序列一一对应 当输出截位序列的比特数大于 如果 的模数和系数都已知文献给出了一个基于 方法的序列还原算法 如果 的模数和系数都未知文献 扩展了文献的算法利用格方法还原了 的模数、系数和初态 文献进一步改进了文献的方法引入结式、最大公因式等技术减少了算法的运行时间和所需数据量目前对于 的截位还原问题现有成果只考虑了截高位部分比特的情形 对于截低位部分比特的情形没有相关的研究成果且 截高位还原的方法不能平凡地推广到截低位情形难点在于:)在寻找序列的零化多项式这一步中当已知 的截高位序列时截位序列片段的待求整系数线性组合是一个短向量进而自然地构成了格上的一个短向量可以通过格基约化进行求解 而当已知 的截低位序列时截位序列片段的待求整系数线性组合不是一个短向量之前构造格虽然包含这个格向量但无法通过格基约化算 信 息 工 程 大 学 学 报 年法将其求解出来)在还原初态这一步中当已知 的截高位序列时可以通过 嵌入构造包含初态低位部分比特的格向量进而通过约化格基进行还原 而当已知 的截低位序列时同样的格构造虽然包含初态高位部分比特但由于向量较长无法求解本文主要研究未知参数的 的截低位还原问题 具体来说当 的模数和系数未知本文通过 生成序列的低位部分比特来还原模数 、系数 以及初态 还原过程分为 步:)寻找序列 的零化多项式正如第 个难点 截高位还原的方法不能平凡地推广到截低位情形 因此本文提出了新的格:在原非满秩的格上添加 个行向量(参数 的含义见.节)通过格基约化对原目标向量中的大数分量做模运算使其化为 从而构造包含待求整数的短向量 为保证该短向量可通过格基约化还原出来本文通过高斯启发式假设计算出大数 并乘到格的前 列从而确保格的约化基中最短向量的前 个分量为零)还原 的模数和系数 按文献中的方法分别计算零化多项式的结式和最大公因式)还原初态 对于一般模数本文通过模逆运算将其转化为截高位情形 对于模数为偶数的特殊情形本文提出了一种新的基于格的求解方法 与步骤 类似本文通过添加格向量和乘大数的方法构造了包含初态高位部分比特的格向量 虽然该法构造的格规模更大约化花费时间更长 但实验结果表明部分未能用一般还原方法求解的实例可以用新方法求解从而提高还原初态的成功率本文第 节为预备知识介绍后文需要用到的概念和引理第 节介绍了还原截低位 的方法第 节给出整体还原的实验结果第 节总结了本文的工作并提出值得进一步研究的问题 预备知识.整数剩余类环上序列定义 设整数 多项式()是 /()上的 次首一多项式 如果 /()上的序列 ()对于任意的整数 满足线性递归关系:则称 为 /()上由()生成的 级线性递归序列称()为 的特征多项式称次数最小的特征多项式为极小多项式 若/()上的多项式()对于任意的整数 均满足 则称()为 的零化多项式对于任意整数 记 模 的非负最小剩余为 对 于 /()上 的 序 列 ()记 ()同样的对于/()上的多项式()记()设()是 /()上的 次多项式若()是 /()上的可逆元则存在正整数 使得在/()上()整除()其中最小的正整数 称为()的周期记为()定义 设 是 素 数 方 幂()是/()上的 次首一多项式且()若()()则称()为/()上的 次 本 原 多 项 式 若 序 列 由/()上的 次本原多项式生成且 ()则称 为 /()上的 级本原序列若()是 /()上的 次本原多项式则对于任意的 ()是/()上的 次本原多项式定义 设 是 的标准分解()是 /()上 的 次 首 一 多 项 式 且()若对于任意 ()是 /()上的 次本原多项式则称()为 /()上的 次本原多项式 若序列 由 /()上的 次本原多项式生成且对任意 则称 为 /()上的 级本原序列.格与格基约化算法定义 设 是上 个线性无关向量则这 个向量的整系数线性组合构成一个 维格 即:其中:向量组 称为格 的一组基 称为格 的维数 称为格 的秩 当 时称格是满秩的设 是由行向量 构成的()维矩阵 是 的转置格 的行列式定义为()()格 的第 个逐次最小长度()定义为以原点为球心包含 个线性无关格向量的最小球的半径 特别地()就是 中非零最短向量 第 期于寒冰等:未知参数多重递归发生器的截低位还原长度引理 高斯启发式假设 设 是一个 维随机格()以极大概率满足:()()对任意向量 令 表示 的欧几里得范数 下面介绍格上的两类困难问题:最短向量问题()和最近向量问题()定义 给定格 找非零格向量 使得对格 上任意非零向量 定义 给定格 和目标向量 找格向量 使得对格 上任意向量 目前求解 的算法分为两类:一是近似算法如 算法、算法等二是精确算法如枚举算法、随机筛法等.结式在代数领域结式是用于判断两个多项式是否含有公因子的重要工具其定义如下定义 结式 设 是一个交换环 是 上的多项式环 令()和()分别是 上次数为 和 的多项式 多项式()和()的结式()定义为如下行列式值:的截低位还原算法首先介绍本文研究的问题设整数 多项式()/()序列 ()是 /()上由()生成的 级线性递归序列即对于任意的整数 满足如下线性递归关系 令 表示()的比特数 设 表示 的高 比特 表示 的低 比特即 ()式中 令()则根据序列 的线性递归关系可知()()进而有 ()式中:()表示 的第 个列向量未知参数下截低位 的可预测性问题定义如下:给定 长截低位序列片段 还原未知的模数 系数 和初态.寻找 的零化多项式正如文献中给出的针对未知参数下截高位 的可预测性问题的求解方法如果可以找到多个 的零化多项式那么就可以通过求解结式和最大公因式的方法还原模数 和系数 本文仿照文献中寻找零化多项式的思路 给出通过截低位序列片段得到序列 的零化多项式的方法引理 设 是 维空间中的一组整数向量且 且 构造向量组()根据引理 存在整数 使得 ()式中 且 信 息 工 程 大 学 学 报 年接下来通过格基约化寻找使得式()成立的整数 由式()和式()易知 其中()()令 ()构造如下格()显然目标向量 ()因为格 的维数是()行列式为()()根据引理 格 的非零最短向量长度约为()()由于 ()故可以通过对格 调用格基约化算法得到目标向量 使得式()成立需要说明的是目前对于参数、的取值的估计比较粗糙与实验取值相差较大 在实验中通常用大量实验正向验证的方法选择合适的、当选择合适的、的值时对 的一次格基约化可以得到多组整数 使得式()成立根据式()每得到一组整数 就等同于得到一个序列()()的零化多项式:()如文献所示当得到足够多的零化多项式就可以用来还原 的模数和系数.还原模数和系数在得到足够多的零化多项式后按文献所示计算零化多项式的结式来还原 的模数 计算零化多项式的最大公因式来还原 的系数 设在.节中共得到 个不同的零化多项式()()()()()()首先定理 给出了环上序列零化多项式与模数之间的关系定理 设整数 ()是 /()上的 次本原多项式 是/()上由()生成的本原序列 设()()、()()是序列 的两个不同的零化 多 项 式 那 么 在 上 有()()()()根据定理 计算多个零化多项式的结式的最大公因数可以还原模数 在还原出模数 后按文献中的方法还原 的系数 这等价于还原特征多项式()首先计算 的标准分解 对于每一个 计算()()()()的最大公因式得到 ()然后逐层调用扩展欧几里得算法依次计算出 ()()最后通过中国剩余定理恢复().还原初态当成功还原 的模数和系数后需要在参数已知的情况下根据给定的截低位序列片段 还原初态 根据式()由于 已知还原初态 等价于还原 假设还原初态需要的截位序列长度为 根据式()和式()可知 ()()式中 对于 令 则有:下面给出还原初态的具体方法 其中.节的方法适用于一般模数.节的方法适用于模数为偶数的情形.一般还原方法设()则 且由式()知 当 .实验证明至少需要 拍截位数据才能成功还原初态 这也证实了式()的数据量估计是有效的上述整个还原过程花费时间不足 分钟此外为比较模数为偶数情形下两种还原初态的方法选择模数 特征多项式仍为()随机选择 组初态生成序列按式()估计给定 拍低 比特序列 用于还原初态 实验表明.节方法成功率达.节方法成功率达.同时调用两种方法的成功率可提高至.结束语本文研究了未知参数下截低位 的可预测性问题 即对于 给定 长截低位序列片段 还原未知的模数 系数 和初态 本文首先通过格基约化找到序列 ()的零化多项式然后计算零化多项式的结式与最大公因式还原 的模数与系数最后构造格还原初态并估计所需的截位数据量 对于模 第 期于寒冰等:未知参数多重递归发生器的截低位还原数是偶数的情形 本文还提出了带模高位的格方法来还原初态 实验结果表明模数为偶数时同时使用两种初态还原方法可提高成功率 目前未知参数下截中间位 的可预测性问题还没有相关成果有待进一步研究参考文献:.:.:.:.():./().():.:.():.:.():.:.():.:.():.黄民强.环上本原序列的分析及其密码学评价.合肥:中国科学技术大学.():.杨建斌.整数剩余类环上截位序列还原研究.郑州:信息工程大学.():./.().:./.:.:.:.:“”.:.(编辑:刘彦茹)信 息 工 程 大 学 学 报 年