Document Description

A PROPOSED DESIGN OF A STREAM CIPHER MODEL
BASED ON FEEDBACK WITH CARRY SHIFT REGISTERS
Nabil Hamdy Shaker, Amal N.Asham, Ihab Talkhan, Tarek.A. Abdel Aziz
Cairo University, Faculty of Engineering, Cairo, Egypt.
Misr International Univ., Faculty of Engineering, Cairo, Egypt.
nabil.hamdy@ miuegypt.edu.eg , amalasham@hotmail.com, italkhan@cu.edu.eg
ABSTRACT
Stream ciphers are often used when it is necessary to encrypt large amounts of data
very quickly; they are private-key encrypt

Document Share

Document Tags

Document Transcript

A PROPOSED DESIGN OF A STREAM CIPHER MODELBASED ON FEEDBACK WITH CARRY SHIFT REGISTERS
Nabil HamdyShaker,Amal N.Asham, Ihab Talkhan,Tarek.A. Abdel Aziz
C
airo University, Faculty of Engineering, Cairo, Egypt.
Misr International Univ., Faculty of Engineering, Cairo, Egypt.nabil.hamdy@ miuegypt.edu.eg , amalasham@hotmail.com, italkhan@cu.edu.eg
ABSTRACTS
tream ciphers are often used when it is necessary to encrypt large amounts of datavery quickly;they are private-key encryption algorithms that operate on the plaintext one bit or one machine word at a time.Stream ciphers areconsideredsecure if knowledge of a small number of bits of keystream cannot be usedtorecover the entire keystream. A good stream cipher should have good randomness,high period, linear span, and security against any known attack.Hence,thedevelopment of a good random number generator has been a hot topic in cryptology.Cryptographershave liked stream ciphers made up of shift registers: They are easilyimplemented in digitalhardware. The Feedback with carry shift register (FCSR) isintroducedas a source for long pseudo random binary sequences.Therefore, this paper providesthe design of a new stream cipher model, it is an FCSR based streamcipher model, main building blocks and modules of the cipher system model are presented in details. The design considerations are provided. The initialization of thenew cipher model and the operational scenario of the new model as a whole areintroduced. Finally, the new cipher model is being implemented using VHDL.
Keywords:
Stream ciphers, feedback shift registers, FCSR.
1INTRODUCTION
In the stream cipher, the
running-key
(or
keystream)
is the sequence which is combined digit by digit tothe plaintext sequence for obtaining theciphertext sequence[1], [2]. The running key isgenerated by a finite state automaton called the
running-key generator
or the
keystream generator.
Steam ciphers based on shift registers have beentheworkhorse for cryptography since the beginnings of electronics[3], [4].Shift registers[5], [6]are easilyimplemented in digital hardware.The simplest kindof feedback shift registers is theLinear Feedback Shift Register (LFSR) whichis usedfor generating awide variety of pseudo random sequences. The sizeof the smallest LFSR that generates a given periodicsequence is defined as the
linear complexity(span)
of
a
, it isan important measure of the cryptographicsecurity of the sequence.Due to the linearity of LFSR, we can determine the LFSR which generatesany outputsequence using theBerlekamp–Masseyalgorithm [7] by knowing
2n
output bits only.Klapper and Goresky [8],[9]proposeda new typeof pseudo random binary sequence generator calledFeedback with Carry Shift Register (FCSR),FCSR has a shift register, feedback function, and a smallamount of memory cells (to store the carry). The bitsof the register are added together withthe currentcontents of the memory to form sum. The parity bit(
mod 2) of the sum is fed back into the first cell,and the higher order bits (
/2
) (where
denotes the floor or integer part)are retained for thenew value ofthe memory.Fig.1showsthe maincomponents of the Fibonacci structureof FCSR [10].The main parametersrelated to the analysis of FCSR are: the connection integer
q
,the number of register cells. The connection integer is an odd positive integer
q
z
,suppose
q = p
e
with
p
an odd primewhere
2
is primitive modulo
p,
and
p
2
does notdivide
(2
p-1
–1)
and
e
2,
the output periodisgiven by:
1
()
ee
qpp
(1) Therelation between the connection integer and thenumber of register cells
r
[11]is given by:
r=
log
2
(q+1)
(2)
Figure 1:
Fibonacci FCSR
Output
a
r-1
a
r-2
….
a
1
a
0
q
1
q
2
q
r-1
q
r
Σ
m
∑
div2
∑
mod2
FCSR has many properties that are similar to the properties of LFSR; it is equipped with a richalgebraic structure that enables its analysis in muchthe same way as the algebraic structure of LFSR.However, the analysis of FCSR sequences involves acompletely different mathematical toolkit
.
Theconstructed sequences are balanced and have the de-Bruijn property which states that: in any single period, every nonzero binary string of length
r
(where
r
is the register length)occursexactly once.In the other side, FCSR sequencescan besynthesized analogue of the Berlekamp-Masseyalgorithm.As well as, it has been shown that thelinear span of an FCSR is half of the period [12].Consequently, an FCSR has much better linear spancompared to that of an LFSR. The notion of the2-adic complexity of the keystreamis also animportant measure of the security of a stream cipher [13], itis possible to increase the 2-adic complexityof FCSR sequences by introducing suitable booleanfunctions in the output of the FCSRs but thisquestion has not received serious attention so far.Thus, the purpose of our paper is to explore the possibility to designa stream cipher model usingFCSRs as our blocks for keystreamgeneration[14],[15], [16].
2 THE PROPOSED STREAM CIPHER MODEL
The proposed model is a synchronous streamcipher based on FCSRs as the main buildings blocks,and a boolean function to combine the outputs of these FCSRs. The cipher systemmodelis used as akeystream generator that outputs a pseudo randomsequence of bits. Every output 8-bits of thekeystream is XOR'ed with an equivalent byte of the plaintext data to produce the encrypted cipher data.Upon the receiving of the cipher data, it is XOR'edwith the samekeystream bytes to recover the srcinal plain data.The detailed structure of the proposed keystream generator is illustrated in Fig.2. Next, we willdemonstrate the detailed internal structure and thedesign strategy of the model.
2.1 FCSRs Module
The FCSRs module uses 8-FCSRs as themain building blocks. Foreach FCSR we shoulddetermine the fixedparameters
p, e, q, and r.
Everytime the model works one randomly
c
value(where
c
is an integer less than
q,
and coprime to
p
)for eachFCSR is chosen. For every FCSR the fixed parameters are chosen as follow:
FCSR1
(P1=11, e1= 9, q1= 2.3579e+009,r1 =31).
FCSR2
(P2=13, e2=10, q2 =1.3786e+011, r2 =37).
FCSR3
(P3=19, e3=30, q3 =2.3047e+038, r3=127).
FCSR4
(P4=11, e4=31,q4=1.9194e+032, r4 =107).
FCSR5
(P5= 3,e5=35, q5 =5.0032e+016,r5=55).
FCSR6
(P6=13, e6=19, q6=1.4619e+021, r6=70).
FCSR7
(P7=61, e7 =14, q7= 9.8768e+024, r7 = 83).
FCSR8
(P8=61, e8=17,q8 =2.2419e+030, r8 = 100).
2.2 FCSRs' c Values and Initial States
Every time the model works; random
c
value for each FCSR should be chosen. Then, the modelinitializes the FCSRs' cells by calculating an initialstate bythe following procedure
:PROCEDURE INITIAL STATE (INTRGER p,r,binq( ),q)
// Geta random value for cwhere c coprime to p1. SET index=q-1.2. SET findc=false.//Generates discrete uniform random number 3. WHILE findc=false.3.1 c=unidrnd(index)3.2 IF greatest common divisor of (c,p) =1Then findc=trueENDIFENDWHILE4. DISPLAY c// Get initial loading and initial memory5. FOR i = 1 TO r 5.1 IF i=15.1.1SET sum = cELSE5.1.1 SET sum = 05.1.2 FOR k =1 TO i-15.1.2.1sum + (binq(i-k)*a(k))ENDFOR 5.1.3 sum=sum + mENDIF5.2 SET a(i)= mod(sum,2)5.3 m=(sum -a(i))/2ENDFOR 6. RETURN a , m
END PROCEDURE2.3FCSRs' Periods
The chosen FCSRs produce
ℓ
-sequences with period as follow:
Ф
(p
e
)=p
e-1
(p-1) =q(p-1)/p
(3)which follows that they produce sequences with periods : period1 = 2.1436e+009, period 2 = 1.2725e+011, period 3 = 2.1834e+038, period 4 = 1.7449e+032, period 5 = 3.3354e+016, period 6 =1.3495e+021, period 7 = 9.7149e+024, period 8 =2.2051e+030.
2.4 FCSRs' Tapped Cells
The operation of each FCSR beginsby addingthe tapped cells to form the sum
.
10
r ninii
qa
(4)
Where the tapped cells are the following tap positions in each FCSR:
FCSR1
=
[31, 27, 26, 23, 19, 17, 16, 14, 13, 11, 10,8, 5, 3, 1]
.
FCSR2
=
[37, 28, 27, 24, 16, 15, 13, 10, 8, 7, 6, 3].
FCSR3
=
[127, 125, 123, 122, 120, 118, 117, 113,110, 104, 103, 99, 98, 96, 92, 90, 87, 86, 85, 83, 81,79.]
FCSR4=
[107, 104, 102, 101, 100, 98, 97, 95, 93,91, 89, 87, 85, 82, 81, 80, 79, 78, 76, 74, 72, 65, 64,60, 57, 56].
FCSR5
=
[55, 53, 52, 48,47, 45, 44, 43,42, 41, 40,39, 38, 36, 34, 33, 31, 30, 25, 24, 22, 21, 18, 17, 16].
FCSR6=
[70, 67, 66, 65, 64, 62, 53, 52, 51, 45, 44,42, 41, 39, 33, 31, 30, 26, 22, 21].
FCSR7=
[83, 77, 75, 73, 72, 70, 69, 68, 67, 66, 65,62, 61, 58, 57, 55, 52, 51, 50, 49, 47, 46, 42, 41,39, 38].
FCSR8=
[100, 99, 98, 94, 91, 89, 88, 87, 86, 85, 84,83, 77,76, 74, 73, 72, 68, 67, 66, 63, 62, 57, 56,53,52, 51, 49, 48, 36, 35,33, 32, 31].000000
106
0
FCSR6
∑
m6
div 2 mod 2
69
∑
m3
div2 mod 2FCSR3126
∑
m2
div2 mod 2FCSR236
∑
m4
div 2 mod 2FCSR4
∑
m5
div 2 mod 2FCSR554
∑
m7
div 2 mod 2FCSR782
∑
m8
div 2 mod 2FCSR899
B o o l e a n F u n c t i o n
KeyStream
∑
m1
div 2 mod 2FCSR1030Figure 2:
The detailed internal structure and the design strategy of the model.
2.5 Boolean Function Used
Weadded to the cipher system design is an8-bit variable combining Boolean function
f
d
of dimensionality (256
x
1).the Boolean function weused has been chosen to be balanced and highlynonlinear.The truth table of the Boolean function inhexadecimal format is given as follows:
6F4FC635EE280B7135159C4BB472512BCA8A932DD2E4A84D90D0C977CABEF217
3OPERATIONAL SCENARIO OF THEPROPOSED MODEL
After the previous details, we will form thewholescenario of our proposed model. The system'soperation starts bythe keystream generator initialization process at the beginning of every newcall setup or data transmission session. Then thesystem continues to repeat a group of sequentialsteps to generating an output stream of bits. Thesteps to produce one output keystream byte processed as follows:1) Each FCSR operates the following steps to produce 1-bit-form the sum
10
r ninii
qa
.-Output the rightmost bit a
0
by shifting theFCSR one right step.-The parity bit
(mod 2) is feedback into thefirst cell of the FCSR (leftmost cell a
r
).-The higher order bits
/ 2
are retained as anew memory value.
2) The output bits from the FCSRs' are used asinputs to the Boolean fumction
fd
to ouput a 1- bit.3)Repeat the steps (1), (2) eight times to produce one output keystream bytes.The flowchart of the key Generator operationalscenariois shown in Fig.3.
4 THE PERIOD OF THE OUTPUT SEQUENCE
The feedback function of the FCSR is highlynonlinear,and hence FCSR sequences are resistant tolinear attackssuch as the Berlekamp-Masseyalgorithm. They state that therefore linear functionsare adequate to mask the 2-adic structure of theFCSR and to protect against 2-adic attacks such as deWeger’s algorithm. Further, using a simple Boleanfunction as shown previously to combine theFCSRs provide some measure of immunity against certaincorrelation attacks, beside the simplicity toimplement .The period of the combining FCSR sequences using the Boolean function yields asequence whose period, is approximately the productof the individual FCSR sequences[15].For the proposed stream cipher model the observed period isgiven as follows:
Total Period = 1.0021e+184
Figure 3:
The Flowchart of the Key Generator operational scenario
5VHDL SIMULATIONS
The proposed stream cipher model is represented by blocks and re-usable components connected bysignals, buses or bundles, then, each block is definedusing HDL text views that defines the behavior of each component design unit. Fig.4illustrates the block diagram of the proposed stream cipher model.To illustrate the functionality of the designed streamcipher model the designed test bench has been runand the available signal was applied as the input withclock period equals to 200 ns. Fig.5 illustrates the
Choose random c values for every FCSR
START
Calculate the initial statesand initialmemor value for each FCSR Clock once each FCSR Index the Boolean function
fd
Full the buffer with the output bit
Buffer full
?
Outputkeystream byteReset Buffer END NoYes

Similar documents

Search Related

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x