基于数论函数的新型伪随机数生成器的设计与分析

Arithmetical functions are one of theoritical foundations of cryptography, including Fermat Little Theorem and Euler Theorem, which are used directly in RSA and ElGamal public cryptosystems. the project mainly aims at the applications of Fermat Little Theorem and Euler Theorem to stream ciphers, whose security heavily depends on the pseudorandomness and predictability of key-streams. Thus the generation of key-streams is a key technique of stream ciphers. We will apply Fermat quotients, Euler quotients and Carmichael quotients, which are related to Fermat Little Theorem and Euler Theorem, to designing new algorithms for generating pseudorandom sequences with security cryptographic properties. On one hand, we will discuss the mathematical properties, study a relationship between Fermat quotients, Euler quotients and Carmichael quotients and discrete logarithm, discribe new quotients. On the other hand, we investigate cryptographic measures of the sequences, such as distribution, correlation, linear complexity, non-linear complexity and k-error linear complexity using the theory of finite fields (rings) and exponential sums. At the same time, we will extend our methods to Fermat quotients over p-adic fields and try to discuss some cryptographic applications. The research will present new aoglrithms of key-stream sequences with good cryptographic properties and improve the theory of stream ciphers furtherly.

数论函数是密码学的理论基础之一，像费马小定理、欧拉定理等就直接应用于RSA、ElGamal等公钥密码体制中。本项目将借助费马小定理、欧拉定理等经典性数论性质，进一步探析它们在序列密码中的应用。序列密码的安全性依赖于密钥序列的伪随机性、不可预测性，因此密钥序列的生成是序列密码的关键技术。我们将以费马小定理、欧拉定理相关的数论函数--费马商、欧拉商和Carmichael商为工具，一方面进一步讨论其数学解析性质、其与离散对数的内在联系，提出新的商式函数；另一方面应用它们设计新型伪随机数（序列）生成算法，以构造适合密码学应用的安全的新型伪随机数（序列），结合有限域（环）理论、指数和理论深入分析序列的分布、相关性、（非）线性复杂度、k-错复杂度等密码学指标；并将相关方法进行延拓，探索p-adic域上费马商的应用。项目的研究将为序列密码提供新的密码算法及性能良好的密钥序列，进一步完善密码理论。

伪随机序列在通信、密码领域应用相当广泛。费马商作为数论函数，一直以来主要在解析数论中得到应用，本项目我们系统讨论了费马商在密码学上的应用，我们还考虑了更一般的概念：欧拉商、Carmichael 商，并首次提出了“多项式商”的概念，研究成果主要有下面几个内容：.一是设计基于费马商、欧拉商、Carmichael 商的伪随机序列生成器。这个内容是研究的重点，采用这些商式来设计新型的伪随机数与伪随机序列，得到周期分别为p^2、p^r(r>2)、2^e和2p等几种不同类型的序列。我们应用割圆理论、离散傅里叶变换理论，讨论了相关序列的分布、相关性等，指出这类序列具有良好的伪随机性；分析了序列的线性复杂度，指出这类序列具有良好的复杂度及稳定性；给出了序列生成的迹形式。这类序列能提供更多性能良好的密钥序列，是一个丰富的序列源。同时，我们也研究了费马商、欧拉商若干数论性质。主要利用特征和理论，推广、确立了分布特性；我们也结合特征和理论考虑费马商的插值问题。成果丰富了费马商、欧拉商基础理论。.二是初步建立“多项式商”的理论。我们在费马商的基础上，首次定义一种新型的商式：多项式商，它是费马商的推广。我们深入探析多项式商的数学特性，研究了多项式商的特征和估计，并针对不同的多项式加以分析，证明了多项式商的特征和估计的理论上界。相关结果初步奠定了多项式商理论，推广了费马商理论，对费马商理论的发展有积极的意义。我们也进一步探索多项式商在密码学上的应用，首次应用多项式商来设计伪随机序列。特别是多项式商，可以选择更多的多项式以生成不同的序列，可形成更加丰富的序列源。.我们还研究了几类特殊序列，包括割圆与广义割圆4元序列的线性复杂度、迹表示等；椭圆曲线序列的伪随机性等；编码理论中的覆盖集问题与特殊性质的电子签名问题等。.本项目的研究，拓展了Legendre序列、Jacobi序列等经典伪随机序列的研究与应用，探索了费马商、欧拉商、Carmichael 商在密码学上的应用，在理论上有重要的意义，也进一步完善了序列的密码学理论。项目成果在许多权威刊物发表，并得到学者的广泛关注与引用。