文档介绍：摘要
Trivium 是 E-STREAM 工程最终的流密码胜选算法之一，该算法是由 De
Canniere 和 Bart Preneel 设计的。由于算法设计简单且易于硬件实现，Trivium 受到
了密码学届的广泛关注。优秀的流密码算法要求所产生的密钥流具有高度的伪随
机性，即需要满足 Golomb 伪随机三公设：均衡性、自相关性、游程分布。其中自
相关性是衡量流密码的一个很重要的指标，因为它是进行区分攻击的一个基础。
基于 Trivium 的现有研究成果，本文主要对如下方面进行了讨论：
(1)流密码算法 Trivium可以看作是一个初始状态为288 比特的二进制有限状态
机，则必然存在一个关于 289 个密钥流 zt 的线性函数 L(zz1,L,)289 ，且此线性函数
关于 288 比特的初始内部状态是非平衡的。这样的非平衡 L 函数，Trivium 目前只
有 1 个，本文通过高斯消元获得了 9 个类似的函数。
(2)对于密钥长为 k 比特的流密码算法，当上述线性函数 L 的相关偏差大于
2-k /2 时，进行区分攻击是有效的。所以分析相关偏差是进行区分攻击的基础。本
文具体分析了 Trivium 的这 9 个相关多项式，且获得了相关偏差的具体值。
关键词： 流密码 Trivium 自相关性 多项相关偏差
ABSTRACT
Trivium is one of the final winner algorithms in the project of E-STREAM which
was designed by De Canniere and Bart Preneel. As the algorithm is designed to be
simple and easy hardware implementation, Trivium has been widely concerned in
cryptography. Excellent stream ciphers need a high pseudo-randomness, that is to say
the key stream bits need to meet the Golomb pseudo-random theorem: balance,
correlation and run-length distribution. In which correlation is a very important
indicator because it is a basis to distinguish attack. The correlation of Trivium is mainly
studied in this paper. Many results are as follows:
(1)Trivium can be seen as a binary keystream generator with 288 bits of memory
whose initial state is chosen uniformly at random, there exits a linear function L of at
most 289 consecutive output bits which is an unbalanced function of the initial state
variables. Such L function is only one currently, and nine new such functions have been
obtained by Gauss elimination.
(2)If the key length is k, distinguish attack is effective if and only if the correlation
k
-
is greater than 2 2 . Therefore, the relevant bias is the