Description RC4

1 description

1.1 key-scheduling algorithm (ksa)
1.2 pseudo-random generation algorithm (prga)
1.3 rc4-based random number generators
1.4 implementation
1.5 test vectors

description

rc4 generates pseudorandom stream of bits (a keystream). stream cipher, these can used encryption combining plaintext using bit-wise exclusive-or; decryption performed same way (since exclusive-or given data involution). (this similar vernam cipher except generated pseudorandom bits, rather prepared stream, used.) generate keystream, cipher makes use of secret internal state consists of 2 parts:

the permutation initialized variable length key, typically between 40 , 2048 bits, using key-scheduling algorithm (ksa). once has been completed, stream of bits generated using pseudo-random generation algorithm (prga).

key-scheduling algorithm (ksa)

the key-scheduling algorithm used initialize permutation in array s . keylength defined number of bytes in key , can in range 1 ≤ keylength ≤ 256, typically between 5 , 16, corresponding key length of 40 – 128 bits. first, array s initialized identity permutation. s processed 256 iterations in similar way main prga, mixes in bytes of key @ same time.

for 0 255
s[i] := i
endfor
j := 0
for 0 255
j := (j + s[i] + key[i mod keylength]) mod 256
swap values of s[i] , s[j]
endfor

pseudo-random generation algorithm (prga)

the lookup stage of rc4. output byte selected looking values of s[i] , s[j], adding them modulo 256, , using sum index s; s(s[i] + s[j]) used byte of key stream, k.

for many iterations needed, prga modifies state , outputs byte of keystream. in each iteration, prga increments i, looks ith element of s, s[i], , adds j, exchanges values of s[i] , s[j], , uses sum s[i] + s[j] (modulo 256) index fetch third element of s, (the keystream value k below) bitwise exclusive or ed (xor ed) next byte of message produce next byte of either ciphertext or plaintext. each element of s swapped element @ least once every 256 iterations.

i := 0
j := 0
while generatingoutput:
:= (i + 1) mod 256
j := (j + s[i]) mod 256
swap values of s[i] , s[j]
k := s[(s[i] + s[j]) mod 256]
output k
endwhile

rc4-based random number generators

several operating systems include arc4random, api originating in openbsd providing access random number generator based on rc4. in openbsd 5.5, released in may 2014, arc4random modified use chacha20. implementations of arc4random in netbsd , linux s libbsd use chacha20. in 2017 release of desktop , mobile operating systems, apple replaced rc4 aes in implementation of arc4random. man pages new arc4random include backronym replacement call random arc4 mnemonic, provides better random data rand() does.

proposed new random number generators compared rc4 random number generator.

several attacks on rc4 able distinguish output random sequence.

implementation

many stream ciphers based on linear-feedback shift registers (lfsrs), which, while efficient in hardware, less in software. design of rc4 avoids use of lfsrs , ideal software implementation, requires byte manipulations. uses 256 bytes of memory state array, s[0] through s[255], k bytes of memory key, key[0] through key[k-1], , integer variables, i, j, , k. performing modular reduction of value modulo 256 can done bitwise , 255 (which equivalent taking low-order byte of value in question).

test vectors

these test vectors not official, convenient testing own rc4 program. keys , plaintext ascii, keystream , ciphertext in hexadecimal.