Physics Letters A 374 (2009) 44–49
Contents lists available at ScienceDirect
Physics Letters A
www.elsevier.com/locate/pla
Symbolic dynamics approach to parameter estimation without initial value
Kai Wang
∗
, Wenjiang Pei, Xubo Hou, Yi Shen, Zhenya He
Department of Radio Engineering, Southeast University, Nanjing, China
article info abstract
Article history:
Received 7 September 2008
Received in revised form 28 September
2009
Accepted 7 October 2009
Available online 12 October 2009
Communicated by A.R. Bishop
PACS:
05.45.+b
Keywords:
Cryptanalysis
Chaotic pseudorandom bit generators
Symbolic dynamics
Asymptotic deterministic randomness
Symbolic dynamics, which partitions the infinite number of finite length trajectories into a finite
number of trajectory sets, allows a simplified and “coarse-grained” description of the dynamics of a
system with a limited number of symbols. In this Letter, we will show that control parameters affect
dynamical characters of symbolic sequences. To be more specific, we will analyze how control parameters
affect statistical property of Skewed Tent map symbolic sequences. Besides, we will also analyze how
control parameters affect ergodic property of both Logistic map and Tent map symbolic sequences.
Both theoretical and experimental results show that the above mentioned effects of control parameters
discourage the use of chaotic symbolic sequences in cryptography. Furthermore, we will propose an
improved scheme utilizing asymptotic deterministic randomness to avoid the undesirable effects.
© 2009 Elsevier B.V. All rights reserved.
1. Introduction
Characteristics of chaotic systems, such as ergodicity, sensitive
dependence on initial conditions and random-like behaviors, seem
to be pretty much the same as diffusion and confusion opera-
tions in conventional cryptography [1–4].Today,wehaveexpanded
chaotic systems to the pseudorandom bit generators (PRBGs) in or-
der to utilize some unpredictable behaviors from them. In terms
of designing chaotic PRBGs, the familiar and convenient strategy
is to symbolize chaotic sequences. The chaotic symbolic sequences
play a central role in modern security schemes, such as generat-
ing cryptographic keys and initializing variables in cryptographic
protocols randomly. With researches of chaotic cryptology going
more thorough, several cryptanalytic schemes have been proposed
to analyze the security of chaotic PRBGs [5–8].Amongthem,sym-
bolic dynamical methods have been applied in the fields of chaotic
cryptanalysis [5–7].
Symbolic dynamics, which partitions the infinite number of fi-
nite length trajectories into a finite number of trajectory sets, al-
lows a simplified and “coarse-grained” description of the dynamics
of a system with a limited number of symbols [9,10]. Parameter
estimation is an important area in the research of symbolic dy-
namics. On the application of Gray codes to the ordering of 1D
quadratic map, corresponding analyses prove that the initial value
*
Corresponding author. Tel.: +86 025 83795996; fax: +86 025 83795996.
E-mail address: kaiwang@seu.edu.cn (K. Wang).
or the control parameter could be estimated from the symbolic
sequences, when either of them is known [5].Ref.[7] further stud-
ies how to estimate the control parameter only from a two-valued
chaotic symbolic sequence when its initial value is unknown. In
Ref. [11], Gray codes are applied to determine the control pa-
rameter and the initial point of a chaotic orbit generated by the
Mandelbrot map. Ref. [12] proposes the method of estimating the
control parameter of unimodal maps by means of their order pat-
terns alone, even when the exact values of their orbits are not
accessible. Besides, some other studies focus on parameter estima-
tion with misplaced generating partition [13,14]. By utilizing the
threshold crossings technique, Ref. [13] has made a general state-
ment that a severe under-representation of a dynamical system
may be made by using an arbitrary threshold crossing. By choos-
ing the Tent map as an example, all the statements are made in a
mathematically rigorous fashion [13].Ref.[14] utilizes a misplaced
statistical partition to estimate the critical point of Logistic map
with different control parameters.
Logistic map, Tent map and Skewed Tent map are three clas-
sical maps used in chaotic cryptosystems. In this Letter, we will
show that control parameters affect dynamical characters of sym-
bolic sequences. To be more specific, we will analyze how control
parameters affect statistical property of Skewed Tent map symbolic
sequences. Besides, we will also analyze how control parameters
affect ergodic property of both Logistic map and Tent map sym-
bolic sequences. Both theoretical and experimental results show
that the above mentioned effects of control parameters discourage
the use of chaotic symbolic sequences in cryptography. Further-
0375-9601/$ – see front matter © 2009 Elsevier B.V. All rights reserved.
doi:10.1016/j.physleta.2009.10.021
资源评论
