超伪随机置换的构造及安全性证明

论文摘要

随机性理论是现代密码学的主要理论基础之一,而置换理论在分组密码的研究与设计中有着重要的地位。实际上,序列密码本质上就是一个伪随机生成器G,其输出的乱数序列和随机序列是计算不可分辨的;而分组密码的设计目标实质上就是设计一个伪随机置换,它与随机置换是计算不可分辨的。 本文综合运用概率论、代数学、密码学、信息论等相关学科的知识及“混合技巧”和“归约论证”思想,以计算不可分辨性为基础,研究了DES型置换的性质和构造,得到较为实用的结果。首先综述了DES型置换的研究动态,接着讨论了DES型置换的伪随机性和超伪随机性,重点给出了4-轮DES型超伪随机置换的新构造和基于移位循环置换的改进的DES型超伪随机置换的构造及安全性证明。上述工作为密码学中置换理论的研究提供了新的方法、新思路。本文的主要工作和取得的研究成果如下: 1) 讨论了DES型置换的伪随机性和超伪随机性。研究了伪随机性与不可预测性、单向函数（置换）的关系及伪随机函数与伪随机生成器的关系。 2) 给出了4-轮DES型置换的新构造Ψ(h,f,f,h-1,提高了DES型超伪随机置换在运算和密钥使用方面的效率。 3) 给出了基于移位循环置换的超伪随机置换的构造,新构造改变了原有4-轮DES型置换的构造模式,简化了构造的复杂性和基于随机预言模型的安全性证明,并指出:首末两轮循环移位置换和中间两轮DES-型的随机置换的组合是超伪随机置换。该构造降低了区分优势的上界和敌手攻击成功的概率并降低了对首末轮函数的要求,其中区分优势的上界降低m2/22n。 4) 从理论上对超伪随机置换的构造进行了一般化处理。依据一般化构造模式,安全性更易于证明。

论文目录

• 目录
• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 伪随机序列发生器在密码系统中的作用
• 1.3 置换与伪随机置换的研究现状
• 1.3.1 置换研究的意义和现状
• 1.3.2 伪随机置换的研究现状
• 1.4 伪随机置换研究的理论基础和基本方法
• 1.5 论文安排与研究结果
• 第二章 OES型置换和伪随机性
• 2.1 基本概念和符号
• 2.1.1 DES型置换及记号
• 2.1.2 基本定义
• 2.2 计算不可分辨性
• 2.2.1 基本概念
• 2.2.2 计算不可分辨性质研究
• 2.3 伪随机序列发生器定义
• 2.3.1 定义
• 2.3.2 构造及证明
• 2.3.3 伪随机发生器的应用
• 2.4 伪随机性与不可预测性
• 2.4.1 不可预测性
• 2.4.2 伪随机性与不可预测性关系定理
• 2.5 伪随机发生器与单向函数
• 2.5.1 伪随机发生器存在隐含着单向函数存在
• 2.5.2 基于单向置换构造伪随机发生器
• 2.5.2.1 基于单一置换的构造
• 2.5.2.2 构造的扩展
• 2.5.3 基于置换族的构造伪随机序列生成器
• 2.5.3.1 单向函数和单向函数族
• 2.5.3.2 硬核断言
• 2.5.3.3 基于单向置换族的构造
• 2.6 伪随机函数与伪随机发生器
• 2.6.1 定义
• 2.6.2 构造与证明
• 2.6.3 结论
• 2.7 随机预言模型
• 第三章 DES型超伪随机置换的新构造及其安全性证明
• 3.1 引言
• 3.2 预备知识
• 3.3 构造方法
• 3.4 主要结果
• 3.4.1 预备命题及其证明
• 3.4.2 结论及安全性证明
• 3.5 本章小结
• 3.5.1 创新点
• 3.5.2 有待进一步研究的问题
• 第四章 基于循环移位置换的超伪随机置换的构造
• 4.1 引言
• 4.2 预备知识
• 4.2.1 相关研究概述
• 4.2.2 记号与基本概念
• 4.2.3 构造的新模式
• 4.3 主要结果
• 4.3.1 预备命题及其证明
• 4.3.2 结论及安全性证明
• 4.4 构造的一般化
• 4.4.1 一般化模式
• 4.4.2 总结
• 4.5 本章小结
• 4.5.1 创新点
• 4.5.2 有待进一步研究的问题
• 第五章 结束语
• 参考文献
• 致谢
• 附录:论文和参加科研情况