Discreteasymptoticdeterministicrandomnessforthegenerationofpseudorandombits

97 浏览量 2021-02-20 12:32:32 上传评论收藏 263KB PDF 举报

资源推荐

资源详情

资源评论

Physics Letters A 373 (2009) 653–660

Contents lists available at ScienceDirect

Physics Letters A

www.elsevier.com/locate/pla

Discrete asymptotic deterministic randomness for the generation

of pseudorandom bits

Kai Wang

∗

, Wenjiang Pei, Xubo Hou, Song Hong, Zhenya He

Department of Radio Engineering, Southeast University, Nanjing, China

article info abstract

Article history:

Received 13 August 2008

Received in revised form 28 August 2008

Accepted 8 December 2008

Available online 25 December 2008

Communicated by A.R. Bishop

PACS:

05.45.+b

Keywords:

Discrete asymptotic deterministic

randomness

Multi-value correspondence

PRBG

The deterministic randomness not only can become a dominant approach in exploring the relation-

ship between chaos and randomness, but also can be associated with some famous number theoretical

concepts and open problems in number theory. Compared with chaotic sequences, asymptotic determin-

istic randomness sequences have the characteristic of multi-value correspondence, which makes those

sequences unpredictable in short steps. In this Letter, we will propose the deﬁnition of the discrete

asymptotic deterministic randomness, and then analyze the dynamical characteristics such as maximum-

period and multi-value correspondence. Referring to the NIST80 0-22 statistical test suite, we will present

and discuss two examples of PRBGs based on DADR, from the point of view of FPGA design and random-

ness quality.

1. Introduction

Chaos is a random-like phenomenon generated by deterministic systems. Different from randomness sequences, the sequences gener-

ated by chaotic system are predictable in the short term, because the dynamical systems are determined. Today, chaos plays a key role

in the study of the relation between randomness and determinacy. Many works have focused on the construction of nonlinear dynamical

models which can generate unpredictable sequences in the short term [1–4].Refs.[5,6] are devoted to the analysis of the application of a

chaotic piecewise-linear map as Pseudorandom bit generators (PRBGs) and mathematically analyze the information generation process of

a class of piecewise linear 1D maps. Effective PRBGs are obtained by means of a chaotic system based on a pipeline analog-to-digital con-

verter [7]. The discretized chaos based PRBGs of low complexity are analyzed to evaluate its suitability for the integrated implementation

[8–10].

Furthermore, a remarkable work is proposed by J.A. Gonzalez, whose corresponding researches have discussed dynamics of the general

function: x

= sin

(πθ z

) when z is a relative prime fraction number. The sequence produced by this function is unpredictable in the short

term and has the characteristic of multi-value correspondence [11–14]. This phenomenon is named as “deterministic randomness (DR)”, in

order to differentiate it from chaos and randomness. Obviously, DR not only can become a dominant approach in exploring the relationship

between chaos and randomness, but also can be associated with some famous number theoretical concepts and open problems in number

theory [15]. Further studies show that we can construct generalized asymptotic deterministic randomness (ADR) systems by utilizing the

piecewise linear/nonlinear map and the noninvertible nonlinear transform [16,17], and in nature, this transformation is also similar to the

one-way function of cryptography [18].

Chaos in systems with discrete phase space can be calle d pseudo-chaos, quantum-chaos or, more generally, discrete chaos [19–24].

Refs. [19–21] propose a deﬁnition of the discrete Lyapunov exponent and discrete entropy. Furthermore, Refs. [22,23] utilize the discrete

Lyapunov exponent in chaotic cryptology and chaotic cryptanalysis. The maximum-period of digitized Renyi maps have been discussed in

Ref. [24]. The discrete asymptotic deterministic randomness (DADR) systems are constructed by utilizing the piecewise linear/nonlinear

map and the noninvertible nonlinear transform in discrete phase space. As a result, theoretical results concerning discrete chaos are

helpful for studying DADR. In this Letter, we will propose the deﬁnition of DADR, and then analyze the dynamical characteristics such

Corresponding author. Tel.: +86 025 83795996; fax: +86 025 83795996.

E-mail address: kaiwang@seu.edu.cn (K. Wang).

0375-9601/$ – see front matter

doi:10.1016/j.physleta.2008.12.037

654 K. Wang et al. / Physics Letters A 373 (2009) 653–660

(a) (b)

Fig. 1. The ﬁrst return map of Lissajous map II. (a) a

= 5/2; (b) a = 9/4.

as maximum-period and multi-value correspondence. Referring to the NIST800-22 statistical test suite, we will present and discuss two

examples of PRBGs based on DADR, from the point of view of FPGA design and randomness quality.

In detail, the Letter is organized as follows: In Section 2, we will focus on ADR. In Section 3,wewillproposethedeﬁnitionofDADR,

and then analyze the dynamical characteristics such as maximum-period and multi-value correspondence. In Section 4,wewillpresent

and discuss two examples of PRBGs based on DADR, from the point of view of FPGA design and randomness quality. Finally, concluding

remarks are given in Section 5.

2. Deterministic randomness and asymptotic deterministic randomness

Consider the equation x

= p(θ Tz

), where p(t) is the periodic function, z is an integer, θ deﬁnes the initial condition, and T is the

period of function p

(t). Take the following function as an example:

= sin





(1)

Let

θ = θ

+ q

k and let z be a rational number expressed as z = p/q, where p, q are relative prime numbers, and m, k are integers.

As given the sequence x

, x

,...,x

produced by x

= sin

(θ Tz

), the next value x

m+1

can take q possible values (this scenario is also

called “multi-value correspondence”), resulting in the sequence becoming unpredictable in the short term [11–14].Tobedistinguished

from chaos, this phenomenon is named as “deterministic randomness” [11–14]. Further studies show that we can construct generalized

asymptotic deterministic randomness (ADR) systems by utilizing the piecewise linear/nonlinear map and the noninvertible nonlinear

transform [16,17].

Compared with the chaotic sequences, ADR sequences have the particular characteristic of multi-value correspondence, which makes

those sequences unpredictable in short steps. That means ADR sequences have evident advantages in cryptography. Let us consider the

following noninvertible nonlinear transform:

n+1

= h(a, x

), y

= h(b, x

) (2)

where h

(a,t) = mod(a∗t, 1).Whena = p/q > 2 is a relative prime fraction number and b = q

, y

and y

n+m

(m = 1, 2,...,N)haveperfect

multi-value correspondence with p

: q

[17]. We call this system “Lissajous map II”. The intrinsic factor, which causes DR, is that there

are inﬁnite different initial values which make the previous values same and the next value different. For the function: x

= sin

(θ Tz

the next value can have different choices with the same possibility when the initial value

θ = θ

+ q

k can be selected with the same

possibility. Suppose that we get the any y

= Y generated by the Lissajous map II. Because the sequence {x

} has the uniform probability

density in interval

[0, 1], the initial values x

Y +i

, i = 0, 1,...,b − 1, can be generated with the same possibility. The ﬁrst return map

of Lissajous map II is shown in Fig. 1.

3. Discrete asymptotic deterministic randomness

Lissajous map II is constructed by the piecewise linear maps, which can be discretized in the ﬁnite digitized state space and can be

implemented with low complexity digital hardware requirement. As shown in Ref. [17], DADR system of Lissajous map II is described as

follow s:

n+1

=a · X





mod 2



(3a)

= b · X



mod 2



(3b)

Let us redeﬁne ADR in ﬁnite digitized state space as follows: As given the sequence Y

, Y

,...,Y

m−1

(m  M), the next value Y

can

take Q different values, where the length of maximum unpredictable steps M and the number of the multi-value Q are determined by

剩余7页未读，继续阅读

评论收藏

内容反馈

weixin_38726186

粉丝: 5
资源: 895

Discrete asymptotic deterministic randomness for the generation ...

最新资源

Discrete asymptotic deterministic randomness for the generation ...

Discrete Fourier transforms when the number of data samples is prime

A PACKING GENERATION SCHEME FOR THE GRANULAR.pdf

A Fast Computational Algorithm for the Discrete Cosine Transform

数字信号处理英文版：Ch7 LTI Discrete-Time Systems in the Transform Domain

An algorithm for the machine calculation of complex Fourier series

A discrete-time model for triply selective MIMO Rayleigh fading channels

Discrete Choice Analysis: Theory and Application to Travel Demand

Discrete-Hankel-Transform-master.zip_DHT_Discrete Hankel Tran_离散

Discrete Deterministic and Stochastic Dynamical Systems

Handbook of Discrete and Computational Geometry Third Edition

Discrete Control Systems

Clifford Stein- discrete-mathematics-for-computer-scientists

Lectures on Discrete and Polyhedral Geometry

Discrete Volterra Series and Nonlinear Echo Cancellation

Stochastic stability of the discrete-time extended Kalman filter

Quantum walks_a comprehensive review

定性数据分析Categorical Data Analysis 2nd Edition - Agresti

Models of Computation for Big Data

2010_Discrete element modeling of direct shear tests for a granular material.pdf

构建多层神经网络

The.Geometry.of.Discrete.Groups,.Beardon.A.F..(Springer.1995)(ISBN.3540907882)(T)(347s).pdf

离散傅里叶变换（DFT）的数学-音频应用Mathematics Of The Discrete Fourier Transform (DFT) - With Audio Applications

最新资源