eSTREAM决赛流密码设计：计算机科学讲座笔记4986

需积分: 9 89 浏览量更新于2024-07-30 1 收藏 4.75MB PDF 举报

"Lecture Notes in Computer Science 4986" 是一本专注于计算机科学领域，特别是密码学中流密码（Stream Cipher）设计的学术著作。由Matthew Robshaw和Olivier Billet编辑，该书汇集了eSTREAM项目中的最终入选算法，该项目是流密码设计的国际竞赛，旨在为加密技术提供高效且安全的标准。本书于2008年由Springer-Verlag Berlin Heidelberg出版，并受到德国版权法的保护。流密码是一种序列密码，它通过对明文数据逐位加密来工作，通常用于实时通信和大量数据的加密。eSTREAM项目在2000年代初启动，目的是选择出适合各种应用场合的高效流密码算法，包括软件和硬件实现。本书中包含的"eSTREAM Finalists"是经过严格评估和测试的流密码算法，它们代表了当时该领域的前沿技术和研究成果。书中可能涵盖了以下核心知识点： 1. **流密码基础**：解释了流密码的基本原理，包括如何生成伪随机比特流，以及如何将这个流与明文数据结合以实现加密。 2. **eSTREAM算法详解**：对每个决赛算法进行详细介绍，包括其设计结构、安全性分析、性能评估以及可能的优化策略。 3. **密码学安全性和分析**：讨论了流密码的安全性标准，如抵抗线性和差分攻击的能力，以及密码分析的方法和技术。 4. **实现与效率**：探讨了这些算法在不同平台上的实现，包括软件和硬件，以及它们的计算和内存效率。 5. **应用背景**：分析了流密码在无线通信、网络安全、数据存储等领域的实际应用，以及它们相对于块密码的优势。 6. **未来研究方向**：可能提出了流密码设计的未来挑战和研究方向，包括适应新兴技术的需求和应对新的安全威胁。 7. **编委会与作者**：由全球知名的计算机科学家和密码学专家组成的编委会和作者团队，确保了内容的专业性和权威性。 "Lecture Notes in Computer Science 4986" 是了解和研究流密码设计的宝贵资源，对于密码学学者、信息安全专业人员以及对加密技术感兴趣的读者来说具有很高的参考价值。通过深入学习本书，读者可以掌握流密码的核心概念，理解eSTREAM项目的意义，以及如何评估和应用这些先进的加密算法。

CryptMT3 Stream Cipher 9

that is, the ﬁrst 32-bit part is the addition of x[3] and y[3] modulo 2

, the second

32-bit is that of x[2] and y[2] (without the carry from the second 32-bit part to

the ﬁrst 32-bit part, diﬀerently from the addition of 128-bit integers). The outer

most [ ] in the right hand side is to emphasize that they are concatenated to

give a 128-bit integer.

Similarly, for an integer S,

x >>

S := [(x[3] >> S), (x[2] >> S), (x[1] >> S), (x[0] >> S)]

means the shift right by S bits applied to each of the four 32-bit integers, and

x >>

S := [(x[3][2] >> S), (x[1][0] >> S)]

means the shifts applied to each of the two 64-bit integers.

In the following, we often use functions such as

x → x ⊕ (x[2][1][0][3] >>

S),

which we call perm-shift.Here⊕ means the bit-wise exclusive-or. The permu-

tation [2][1][0][3] may be an arbitrary permutation, and the shift may be to the

left. A function of the form

x → x[i

][i

] ⊕ (x >>

is also called a perm-shift, where i

is a permutation of 3, 2, 1, 0. A perm-

shift is an F

-linear transformation, and if S ≥ 1 then it is a bijection. (Since

its representation matrix is an invertible triangular matrix times a permutation

matrix, under a suitable choice of the basis.)

Let n be a positive integer, and x be a 32-bit integer. The n most signiﬁcant

bits of x are denoted by MSB

(x). Similar notation LSB

(x)isalsoused.Fora

128-bit integer x, we deﬁne

MSB

(x):=[MSB

(x[3]), MSB

(x[2]), MSB

(x[1]), MSB

(x[0])],

which is a (n × 4)-bit integer.

A function f : Y × X → Z is bi-bijective if for any ﬁxed x ∈ X, the mapping

Y → Z, y → f(y,x) is bijective, and for any ﬁxed y ∈ Y , the mapping X →

Z, x → f(y,x) is bijective. It is necessary that the cardinalities coincide: #(X)=

#(Y )=#(Z).

2.2 SIMD Fast MT

CryptMT3 adopts the following mother generator, named SIMD-oriented Fast

Mersenne Twister (SFMT) [10].

Let N be an integer, and x

, x

,...,x

N−1

be N 128-bit integers given as the

initial state. A version of SFMT used here is to generate a sequence of 128-bit

integers by the following F

-linear recursion:

N+j

:= (x

N+j−1

& 128-bit MASK)⊕

M+j

S) ⊕ (x

M+j

[2][0][3][1]) ⊕ (x

[0][3][2][1]).

(2)

12 M. Matsumoto et al.

perm-shift is to mix the information among four 32-bit memories in the ﬁlter,

and to send the information of the upper bits to the lower bits. This supplements

the multiplication, which lacks this direction of transfer of the information.

The output function is

g(y):=LSB

(y ⊕ (y >>

16)). (4)

Thus, the new ﬁlter has 128-bit of memory, receives a 128-bit integer, and output

a(16× 4)-bit integer. The compression ratio of this ﬁlter is (128:64), which is

smaller than (32:8) in the previously proposed ﬁlter. This change of the ratio is

for the speed, but might weaken the security. To compensate, the output function

takes the exclusive-or of the 16 MSBs and the 16 LSBs of y[i], i =3, 2, 1, 0.

2.4 Conversion to 8-Bit Integers

Since the outputs of the ﬁlter are (16 × 4)-bit integers and the speciﬁcation

required is 8-bit integer outputs, we need to dissect them into 8-bit integers.

Because of the nature of the 128-bit SIMD instructions, the following strategy

is adopted for the speed. Let

LOWER16 := (0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff)

UPPER16 := (0xffff0000, 0xffff0000, 0xffff0000, 0xffff0000)

be the 128-bit masks.

Let y

, y

,...,y

, y

2i+1

,... be the content of the memory in the ﬁlter at

every step, i.e., generated by y

i+1

:= f(y

, x

) in (3). Then, y

and y

2i+1

are

used to generate the i-th 128-bit integer output z

, by the formula

:= [(y

⊕ (y

16))&LOWER16] | [(y

2i+1

⊕ (y

2i+1

16))&UPPER16]

where | denotes the bit-wise-or. Then, z

is separated into 16 of 8-bit integers

from the lower bits to the upper bits, and used as the 8-bit integer outputs.

2.5 A New Booter for the Initialization

SFMT in §2.2 requires N = 156 of 128-bit integers as the initial state. We need

to expand the key and IV to an initial state at the initialization, but this is

expensive when the message length is much less than N ×128 bits. Our strategy

introduced in [7] is to use a smaller PRNG called the booter. Its role is to expand

the key and IV to a sequence of 128-bit integers. The output of the booter is

passed to the ﬁlter discussed above to generate the pseudorandom integer stream,

and at the same time, used to ﬁll the state of SFMT. Once the state of SFMT

is ﬁlled up, then the generation is switched from the booter to SFMT.

The booter we adopted here is described in Figure 4. We choose an integer

H later in §2.6 according to the sizes of the Key and IV. The state space of the

booter is a shift register consisting of H 128-bit integers. We choose an initial

state x

, x

,...,x

H−1

and the initial value a

of the accumulator (a 128-bit

剩余300页未读，继续阅读

xuypqy

粉丝: 0

eSTREAM决赛流密码设计：计算机科学讲座笔记4986

Axioms and Hulls (Lecture Notes in Computer Science).pdf

Lecture Notes in Computer Science -22nd International Symposium, GD 2014.pdf

Lecture Notes in Computer Science: 5931 Series Milestone & Key Figures in Cloud Computing

Great Ideas in Theoretical Computer Science Lecture Notes (MIT 6.045)

Advances in Computer Science and Ubiquitous Computing

Scipy - Scipy Lecture Notes

Algorithmic Game Theory Lecture Notes (Cornell CS6840)

Computer_Science_for_Everyone_CS50-2019：부스트코스-과학（CS50 2019）

UIUC CS233 Discrete Structure Lecture note

Notes on Discrete Mathematics

最新资源