- About project
- Results and Awards
- Affiliate Programs
- International services
Alexander Babash, doctor of of mathematics and physics, full professor
Russian State Social University, Russia
Championship participant: the National Research Analytics Championship - "Russia";
Pseudorandom number generator ARCFOUR is modeled by two consecutively connected finite state machines. Using this model some characteristics of ARCFOUR internal permutation sequence period are calculated and provided.
Keywords: ARCFOUR, pseudorandom, generator, machine, model
ARCFOUR is a pseudorandom number generator known as RC4. The name RC4 is a trademark, so RC4 is often called ARCFOUR or ARC4 (Alleged RC4) to avoid trademark problems. 
Pseudorandom number generator RC4 was designed by Ron Rivest of RSA Security in 1987. The RC acronym usually understood by Ron’s Code. 
Initially RC4 was a RSA company's property, but In September 1994 a description of it was anonymously posted on the Cypherpunks web page and in sci.crypt newsgroup. Then this information spreaded in the Internet. The posted code provided the same output sequences that licensed RC4 did, so posted code was considered to be genuine. 
RSA hasn't officially published the algorithm yet. 
RC4 use is very wide because of such features as speed and simplicity. It’s a part of standards like TLS, WEP and WPA. 
ARCFOUR is a set of pseudorandom number generators. It’s internal state depends on n parameter. ARCFOUR with n=8 is used in practical applications.
Let be an internal state set, where ZN is a ring of integers modulo N, SN is a symmetric group and N=2n. So the internal state for n=8 is .
At a point of time t ARCFOUR internal state is
ARCFOUR include two stages, called Key Scheduling Algorithm (KSA) and Pseudorandom Generation Algorithm (PRGA). The first one is an algorithm, which derives the initial state of ARCFOUR from a key. PRGA is an algorithm, which generates output data on initial state basis.
Initial state of ARCFOUR is derived from internal state achieved after KSA and equals , where s is a permutation in internal state achieved after KSA.
At every moment of PRGA ARCFOUR turns into the new internal state and one output number Yt is generated:
- is addition modulo N operation,
- is a z-th number in permutation
- permutation composition operation in symmetric group
- is a transposition of x-th and y-th elements in symmetric group
- is identity permutation).
Let Zn be a set of possible internal states of Moore machine A, is its transition function, is its output function. Let B to be the Mealy machine, X is its input alphabet, ? is its state set, are its partial transition functions, are its partial output functions, Y is its output alphabet. We will use to denote a B internal states sequence, derived from initial state ? and input sequence . c|u means c divides u.
We would remind that sequence b1,b2,…,bt,… of some alphabet elements is called periodic if there is a natural number d which fulfills the condition that bt=bt+kd for any natural numbers t, k. Minimal d that fulfills this condition is a period of the sequence.
Finite-state machine PRGA model is a consecutively connected machine A and B. Machine A input parameters are . It’s clear, that ?=?. We should note, that if the initial state of machine A is i=0, then its output sequence is Q=1,2,…N-1,0,… with a period of N. Machine B parameters are
Further machine B with such parameters will be denoted as B*.
The initial state of PRGA is . So the output sequence is and equals output sequence of machine B*, generated from the initial state (0,s0) and input sequence Q=1,2,…N-1,0,1,2….
We are interested in possible and impossible periods of B* output sequence ?(?). The information about B* internal state permutation sequence ?(s) is also important. It’s clear that ?(?)|?(s) and ?(s) divides internal state sequence period of machine B* with internal state s0 and input sequence Q.
Statement 1. Sequences are periodic.
Statement 1 proving. If we prove that B* internal state sequence corresponded to initial state s0 is periodic we will prove the Statement 1. The proof that B* is a permutative machine (means that are bijective) is enough to prove it.
Let’s prove that machine B* is permutative. Let’s assume that B* is not permutative machine. So for some input symbol and some internal states (j,s), (j*,s*) from ZnxSn the equation is true. So
It means that s=s* and consequently j=j*. It is a collision, which proves Statement 1.
Most valuable result of current article is contained in further theorem.
Theorem. If input sequence is Q=1,2,…N-1,0,1,2… then the permutation sequence period of machine B* is multiple of 2n-1 for any initial permutation S0. If inequality S0(1)≠1+2n-1 is satisfied for substitution S0 then the permutation sequence period of machine B* is a multiple of N=2n.
We provide two lemmas in order to prove the theorem.
Lemma 1. There are two natural numbers n(1), n(2), which satisfy an(1)-bn(2)=d, for any two natural numbers a, b satisfied equality (a,b)=d.
Lemma 1 may be proven with the well-known statement about existence of two integers n(1), n(2) fulfilled condition given above.
Let’s look at machine B defined earlier. Let B(?) be a connected component of machine B which contains state is an output sequence of permutative machine B with initial state ? and input sequence P. Denote Рj=х(j),х(j+1),… forР=x(1),х(2),… .
Lemma 2 Proof. Machine B is permutative so for any machine B state ? and any periodic sequence P the output sequence B(?, P)=y1,y2,...yL, i,...s periodic.
Denote further in this proof. It’s evident that if (w,W)=wthen lemma 2 is true.
Assume that (w,W)=d¹w. Let k is non-negative integer. In according to lemma 1 there are integers n(1), n(2) satisfied kn(1)w– kn(2)W=kd. So
Let’s choose natural number n(3) which fulfis the condition w|n(2)+n(3) and rewrite (1) (note that w(Pkd+1)=w):
So lemma 2 is proven too.
Let’s prove theorem 1. In order to apply lemma 2 to B* permutation (generated from input sequence Q=1,2,…N-1,0,1,2,…) sequence period research we will review permutation sequence of machine B* generated from input sequence Q=1,2,…N-1,0,1,2,… as output sequence of machine differed from machine B* only by partial output functions for any permutation . Let’s review internal states sequence of machine generated from initial state (0, So) and input sequence Q=1,2,…N-1,0,1,2,… with a period of N. Note that there is a shift of output sequence
Equality (3) is possible just if d=2-1. So the assumption (2n, W)=2m, m<n is possible just if S0(1)=1+2n-1. The theorem is proven.
1. Schneier, Bruce / «Applied cryptography Second Edition : protocols, algorithms, and source codes in C» / 1996.
2. Rivest, Ron L. «Ronald L. Rivest : FAQ» / MIT Computer Science and Artificial Intelligence Laboratory. http://people.csail.mit.edu/rivest/faq.html#Ron М. (30.08.2012).