Main Programs
Writings
Algorithms
Contact

 Using ARC4 for a random number generator
Implementation using ARC4
ARC4 works well as a stream cipher for a random number generator for a number of reasons.  First, it's a stream cipher that works with 8-bits at a time.  This is nice because we can retrieve arbitrary lengths of data with no extra steps.  Secondly, ARC4 is quite small and fast.  This is nice because any program using the random number system won't suffer a large size increases or performance loss by using the generator.  ARC4 has one added benefit as well, which will be discussed below.
First, let us look at the design of ARC4.  The heart of the ARC4 algorithm is a strong random number generator in which the key is the seed value.  For encryption, the random data generated by the algorithm is XORed with the plaintext to produce the encrypted text.

The state of ARC4 consists of an array of 256 8-bit values and two 8-bit indexes.
State : array[ 0..255 ] of byte;
x     : byte;
y     : byte;

ARC4's key scheduling is laid out like this:
Loop 256 times
Set State[ LoopCount ] to LoopCount
Set x to 0
Set y to 0
Loop 256 times the following
y = y + Key[ KeyIndex ] + State[ x ] modules 256
Swap( State[ x ] , State[ y ] )
KeyIndex = KeyIndex + 1 modules KeyLength
x = x + 1 modules 256
Reset x to 0
Reset y to 0

The cipher works on a block of data like this:
Loop for number of bytes to cipher
x = x + 1 modules 256
y = y + State[ x ] modules 256
Swap( State[ x ] , State[ y ] )
XOR_Byte = State[ State[ x ] + State[ y ] modules 256 ]
OutputData[ LoopCount ] = InputData[ LoopCount ] xor XOR_Byte

We can quickly convert ARC4 into just random number generator by simply using 'XOR_Byte' instead of XORing with anything.  The loop above would then turn into this:
Loop for number of bytes to retrieve
x = x + 1 modules 256
y = y + State[ x ] modules 256
Swap( State[ x ] , State[ y ] )
OutputData[ LoopCount ] = State[ State[ x ] + State[ y ] modules 256 ]

Now look at the key scheduler and the stream generator and note the relationship of 'x', 'y' and 'State' in these two processes.  'x' is continually counting up and is used as an index info 'State' when modifying 'y'.  The state at index 'x' and index 'y' and then swapped.  In both scheduling and generation, 'y' is modified by adding 'State[ x ]'. The difference is, during scheduling, the key is also added to 'y'.
We could merge the processes of these two functions by making a new function we'll call 'ClockARC4'.  It will look like this:
x = x + 1 modules 256
y = y + KeyByte + State[ x ] modules 256
Swap( State[ x ] , State[ y ] )

Now, the key scheduling becomes this:
Loop 256 times
Set State[ LoopCount ] to LoopCount
Set x to 255
Set y to 0
Loop 256 times the following
y = y + Key[ KeyIndex ] + State[ x ] modules 256
Swap( State[ x ] , State[ y ] )
KeyIndex = KeyIndex + 1 modules KeyLength
x = x + 1 modules 256
Reset x to 0
Reset y to 0

Note that 'x' is set to 255 instead of 0.  This is because in the key scheduling, 'x' is incremented at the end of the loop rather than at the beginning.  To address this, we set 'x' to 255 so that after being incremented, 'x' becomes 0-- thus working with incrementing 'x' at the beginning of the loop rather than the end.

The random stream generation now becomes this:
Loop for number of bytes to retrieve
ClockARC4( 0 )
OutputData[ LoopCount ] = State[ State[ x ] + State[ y ] modules 256 ]

See now that we call 'ClockARC4' with 0, because we are not modifying the state with any external data.  We could actually place any static number in this parameter and not effect the strength of the algorithm-- but we would effect output.  Doing this would nether add nor subtract from the strength of the generator.
Now the relationship between the key scheduling and stream generation is clear.  We can see the difference is that we add external data to the 'y' index during key scheduling.  What's useful about this relationship is that we can continue to clock in external data while also getting stream data.  When used as a cipher, this isn't too useful because you must modify the state in exactly the same way as in manner to create the XOR stream used to decipher the data.  Since this can all be done when the algorithm starts, why bother?
However, when trying to generate random data, the ability to clock in external data is useful.  The random number generator is initialized by running the key scheduler with real-world random data as the key, we're essentially just calling 'ClockARC4' with the real-world random data.  If we acquire more real-world random data, we can immediately apply it to state by clocking it in, thus effecting the future output of the algorithm.
With this we can see how measuring the key delay as a source for random data can be applied when the data becomes available.  The key delay function then would become:
function GetChar : char;
var RandomData : byte;
begin
{ Measure time until key is pressed }
RandomData := 0;
while not KeyPressed do
Inc( RandomData );

{ Pass random data to generator }
ClockARC4( RandomData );

{ Return key that was pressed }