09 / 16 / 2012 - 12:32 — kudravchik

Kudiyarov Dmitry, postgraduate student

Alexander Babash, doctor 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. [1]

Pseudorandom number generator RC4 was designed by Ron Rivest of RSA Security in 1987. The RC acronym usually understood by Ron’s Code. [1]

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. [2]

RSA hasn't officially published the algorithm yet. [1]

RC4 use is very wide because of such features as speed and simplicity. It’s a part of standards like TLS, WEP and WPA. [2]

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 Z_{N} is a ring of integers modulo N, S_{N} is a symmetric group and N=2^{n}. 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:

where

- 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 b_{1},b_{2},…,b_{t},… of some alphabet elements is called periodic if there is a natural number d which fulfills the condition that b_{t}=b_{t+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,s_{0}) 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 s_{0} and input sequence Q.

**Statement 1**. Sequences are periodic.

**Statement 1 proving**. If we prove that B* internal state sequence corresponded to initial state s_{0 }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 Z_{n}xS_{n} 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 2^{n-1} for any initial permutation *S*_{0}. If inequality S_{0}(1)≠1+2^{n-1} is satisfied for substitution *S*_{0} then the permutation sequence period of machine B* is a multiple of N=2^{n}.

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**.

**Lemma 2 Proof**. Machine B is permutative so for any machine B state ? and any periodic sequence P the output sequence B(?, P)=y_{1},y_{2},...y_{L, }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(P^{kd+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, S_{o}) 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 (2^{n}, W)=2^{m}, m<n is possible just if S_{0}(1)=1+2^{n-1}. The theorem is proven.

**Literature:**

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).

(5 votes)

Comments: 4

HOW TO UNDERSTAND: Kudiyarov Dmitry, postgraduate student, doctor of mathematical and physical sciences, full professor?

It's a site bug. The correct authors are:
Alexander Babash, doctor, professor
Russian State Social University, Russian Federation
Dmitry Kudiyarov, postgraduate
Russian State Social University, Russian Federation

By discussion: nondeterministic finite-state automata, deterministic finite-state automata, regular grammars, and regular expressions are all characterizations of the languages that finite-memory programs accept. Moreover, there are effective procedures for moving between the different characterizations. These procedures provide the foundation for many systems that produce finite-memory-based programs from characterizations of the previous nature.

## 09 / 23 / 2012 - 13:10

## Elena Artamonova

09 / 23 / 2012 - 09:43## Kudiyarov Dmitry

09 / 23 / 2012 - 13:20## Elena Artamonova

09 / 23 / 2012 - 09:36