| 学科主题: | 计算机科学技术基础学科::数据安全与计算机安全
|
| 题名: | 多项式理想上的特征理论及其在代数密码分析中的应用 |
| 作者: | 徐琳
|
| 答辩日期: | 2010-05-23
|
| 导师: | 林东岱
|
| 专业: | 信息安全
|
| 授予单位: | 中国科学院研究生院
|
| 授予地点: | 北京
|
| 学位: | 博士
|
| 关键词: | 计算机代数
|
| 摘要: | 多项式理想成员相关的计算，尤其是多项式系统（即非线性代数方程组）的求解技术，在现代科学技术领域中有广泛的应用。在密码学领域，多项式系统的求解技术更是直接带来了一种近年来受到广泛关注的密码分析手段——代数密码分析。自上世纪末以来，代数密码分析一直是密码学的研究热点，且至今已取得一系列重要成果。同时，代数密码分析相关研究也显著推动了多项式系统求解技术本身的发展，使得新的优秀算法如XL算法、F4算法、F5算法等在这一时期不断涌现。
针对多项式理想成员的计算问题，本论文提出了一种新的计算理论：多项式理想上的特征理论。该理论的核心思想源于F5算法中的多项式签名技术，而本论文将这一技术从特定条件下的计算技巧，完善和推广为针对完全一般情况的理论体系，并将其移植到了对于代数密码分析尤其重要的布尔多项式环境下。多项式理想上的特征理论，为每个理想成员分配了一个关于理想生成集唯一的标识（即特征）。由于多项式理想成员的特征与首项之间存在一一对应的关系，使得特征能够为遍历多项式理想所有（线性无关的）成员提供方向性的指引。进而，根据其在多项式理想组织结构中的作用，所有特征被划分为若干类别。通过分别确定各个类别的核心部分，多项式理想成员相关计算中的重复部分能够被自然合并，无效部分能够被预先发现，最终只有核心部分被实际执行，从而显著降低计算的时间和空间开销。通过将该理论应用于不同环境，本论文取得了一系列现实成果。具体包括：
一、对于生成集为单个布尔多项式的情况，得到了一些特有的良好结论。这些结论可被用于帮助高效地计算布尔多项式的零化子和代数免疫阶。实验表明，新的零化子和代数免疫阶算法的性能表现显著优于现有算法，并尤其适合处理现有算法无能为力的变元数较高的情况。这一算法的提出也间接地回答了如何将Groebner基方法应用于零化子计算的问题。
二、关于Groebner基的计算问题，本论文基于特征理论分析了F5算法对输入的齐次性要求，在不影响F5算法本身优点的前提下，得到了无需齐次化的F5算法变体。此外，本论文还给出了F5准则在布尔多项式环境下的更强版本。
三、关于多项式系统的求解问题，本论文以基于特征的计算模式为基础，成功地整合了F4算法和F5算法的核心技术，在保证于最低的代数次数上界内完成求解的同时，实现了无效计算（0约化）的极小化。此外，该算法还融入了XL系列算法中对于布尔多项式特有的有益技术，从而最大限度地整合了同类求解算法的优点。在代数密码分析模拟实验中，该算法的布尔多项式版本取得了良好的结果。 |
| 语种: | 中文
|
| 内容类型: | 学位论文
|
| URI标识: | http://ir.iscas.ac.cn/handle/311060/2370
|
| Appears in Collections: | 信息安全国家重点实验室_学位论文
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| 博士学位论文(最终版).pdf（1387KB） | -- | -- | 限制开放 | | 联系获取全文 |
|
| Recommended Citation: | |
徐琳. 多项式理想上的特征理论及其在代数密码分析中的应用[D]. 北京. 中国科学院研究生院. 2010-05-23.
|
|
|
