论文部分内容阅读
单向函数的存在性是密码学的最基本假设,也是绝大多数对称密码学算法的充分必要条件.作为一个计算复杂性问题,单向函数可以用来构造伪随机产生器进而构成流密码算法,或是在伪随机产生器的基础上进一步构造伪随机函数和伪随机置换从而用作分组加密算法.规则单向函数是一类具有特殊结构的单向函数,该函数的每个像都有相同个数的原像.基于单向函数的密码学组件(如伪随机产生器)构造研究主要有两种思路:一是从任意单向函数出发来设计组件,其优点是具有通用性,不需要使用单向函数的特有结构;另一种是从具有特定结构的单向函数(比如单向置换、规则单向函数等)出发来设计组件,其优点是构造出来的密码学组件效率较高(比如种子长度更短、单向函数调用次数更少等).学界一直感兴趣于怎样在两者之间取得折中:即寻找既能够适用于范围更广的单向函数、又具有高效性的构造方法.本文提出了弱规则单向函数的概念,规则单向函数仅是弱规则单向函数的一种特殊情况.如果一个函数不是弱规则函数的话,那么这种反例的构造需要人工刻意设计.本文进一步通过具体构造说明,基于规则单向函数的密码学组件构造(伪随机产生器)可以推广至基于弱规则单向函数的情况.与HILL型产生器相比,基于弱规则单向函数的伪随机产生器构造兼具种子长度更短和保持安全性的优点.基于弱规则单向函数的通用单向哈希函数构造则推广了学界基于未知规则单向函数构造的研究工作,具有密钥长度为O(nlogn)、输出长度为Θ(n)的特点.
The existence of a one-way function is the most basic assumption of cryptography and also a necessary and sufficient condition for most symmetric cryptography algorithms. As a computational complexity problem, a one-way function can be used to construct a pseudo-random generator and then constitute a stream cipher algorithm , Or use pseudo-random permutation and pseudo-random permutation based on the pseudo-random generator as a packet encryption algorithm.Regular one-way function is a kind of one-way function with special structure, each image of the function has The same number of the original image.According to the one-way function of cryptography components (such as pseudo-random generator) structure of the study there are two main ideas: First, from any one-way function to design components, the advantage is universal, not Need to use the unique structure of the one-way function; the other is to design the component from the one-way function with a specific structure (such as one-way permutation, regular one-way function, etc.), which has the advantage of high efficiency of the constructed cryptographic component (Such as shorter seed length and fewer one-way function calls), the academic community has always been interested in how to achieve a compromise between the two: finding a solution that can be applied to a wider range of To the function, but also has the high efficiency construction method.This article proposed the concept of weak rule one-way function, the rule one-way function is only a special case of the weak rule one-way function.If a function is not the weak rule function, then this The construction of counterexamples needs to be artificially designed.This paper further through the specific structure shows that the construction of cryptography components based on the rule one-way function (pseudo-random generator) can be extended to the situation based on the weak rule one-way function.Compared with the HILL type generator phase Compared with the weak one-way function, the construction of pseudo-random generator has the advantages of shorter seed length and keeping the security.Universal one-way hash function construction based on the one-way function with weak rules promotes the application of the uni-directional The research work of the function construction has the feature that the key length is O (nlogn) and the output length is Θ (n).