Editing RC4 (section)

==Description==
RC4 generates a [[pseudo-random number generator|pseudorandom stream of bits]] (a [[keystream]]). As with any stream cipher, these can be used for encryption by combining it with the plaintext using bitwise [[exclusive or]]; decryption is performed the same way (since exclusive or with given data is an [[involution (mathematics)|involution]]). This is similar to the [[one-time pad]], except that generated ''pseudorandom bits'', rather than a prepared stream, are used. 

To generate the keystream, the cipher makes use of a secret internal state which consists of two parts:
# A [[permutation]] of all 256 possible [[bytes]] (denoted "S" below).
# Two 8-bit index-pointers (denoted "i" and "j").
The permutation is initialized with a variable-length [[key (cryptography)|key]], typically between 40 and 2048&nbsp;bits, using the ''[[key schedule|key-scheduling]]'' algorithm (KSA). Once this has been completed, the stream of bits is generated using the ''pseudo-random generation algorithm'' (PRGA).

===Key-scheduling algorithm (KSA)===
The [[Key schedule|key-scheduling]] algorithm is used to initialize the permutation in the array "S". "keylength" is defined as the number of bytes in the key and can be in the range 1 ≤ keylength ≤ 256, typically between 5 and 16, corresponding to a [[key length]] of 40–128&nbsp;bits. First, the array "S" is initialized to the [[identity permutation]]. S is then processed for 256 iterations in a similar way to the main PRGA, but also mixes in bytes of the key at the same time.

 '''for''' i '''from''' 0 '''to''' 255
     S[i] := i
 '''endfor'''
 j := 0
 '''for''' i '''from''' 0 '''to''' 255
     j := (j + S[i] + key[i [[modulo operation|mod]] keylength]) mod 256
     swap values of S[i] and S[j]
 '''endfor'''

===Pseudo-random generation algorithm (PRGA)===
[[Image:RC4.svg|right|thumbnail|320px|The lookup stage of RC4. The output byte is selected by looking up the values of {{mono|S[i]}} and {{mono|S[j]}}, adding them together modulo 256, and then using the sum as an index into {{mono|S}}; {{mono|S(S[i] + S[j])}} is used as a byte of the key stream K.]]

For as many iterations as are needed, the PRGA modifies the state and outputs a byte of the keystream. In each iteration, the PRGA: 
* increments {{mono|''i''}};
* looks up the {{mono|''i''}}th element of {{mono|S}}, {{mono|S[''i'']}}, and adds that to {{mono|''j''}};
* exchanges the values of {{mono|S[''i'']}} and {{mono|S[''j'']}}, then uses the sum {{mono|S[''i''] + S[''j''] (modulo 256)}} as an index to fetch a third element of {{mono|S}} (the keystream value {{mono|K}} below);
* then bitwise exclusive ORed ([[Exclusive or|XOR]]ed) with the next byte of the message to produce the next byte of either ciphertext or plaintext.

Each element of S is swapped with another element at least once every 256 iterations.

 i := 0
 j := 0
 '''while''' GeneratingOutput:
     i := (i + 1) mod 256
     j := (j + S[i]) mod 256
     [[Swap (computer science)|swap values]] of S[i] and S[j]
     t := (S[i] + S[j]) mod 256
     K := S[t]
     output K
 '''endwhile'''

Thus, this produces a stream of {{mono|K[0], K[1], ...}} which are [[Exclusive or|XOR]]ed with the {{mono|''plaintext''}} to obtain the {{mono|''ciphertext''}}. So {{mono|ciphertext[''l''] {{=}} plaintext[''l''] ⊕ K[''l'']}}.

===RC4-based random number generators===
Several [[operating system]]s include {{code|arc4random}}, an API originating in [[OpenBSD security features|OpenBSD]] providing access to a random number generator originally based on RC4. The API allows no seeding, as the function initializes itself using [[/dev/random]]. The use of RC4 has been phased out in most systems implementing this API. [[Man page]]s for the new arc4random include the [[backronym]] "A Replacement Call for Random" for ARC4 as a mnemonic, as it provides better random data than [[rand()]] does.<ref name=arc4random-obsd>{{cite web |url=http://man.openbsd.org/arc4random.3 |title=arc4random(3) |publisher=OpenBSD}}</ref>

* In OpenBSD 5.5, released in May 2014, {{code|arc4random}} was modified to use [[ChaCha20]].<ref>{{cite web |title=OpenBSD 5.5 |url=http://www.openbsd.org/55.html |access-date=21 September 2014}}</ref><ref>{{cite web |url=http://bxr.su/OpenBSD/lib/libc/crypt/arc4random.c |title=libc/crypt/arc4random.c |website=BSD Cross Reference, OpenBSD src/lib/ |editor=deraadt |editor-link=Theo de Raadt |date=21 July 2014 |access-date=2015-01-13 |quote=ChaCha based random number generator for OpenBSD.}}</ref> The implementations of arc4random in [[FreeBSD]], [[NetBSD]]<ref>{{cite web |url=http://bxr.su/NetBSD/lib/libc/gen/arc4random.c |title=libc/gen/arc4random.c |website=BSD Cross Reference, NetBSD src/lib/ |editor=riastradh |date=16 November 2014 |access-date=2015-01-13 |quote=Legacy arc4random(3) API from OpenBSD reimplemented using the ChaCha20 PRF, with per-thread state.}}</ref><ref>{{cite web |title=arc4random – NetBSD Manual Pages |url=http://netbsd.gw.com/cgi-bin/man-cgi?arc4random++NetBSD-current |access-date=6 January 2015 |archive-date=6 July 2020 |archive-url=https://web.archive.org/web/20200706210612/https://netbsd.gw.com/cgi-bin/man-cgi?arc4random++NetBSD-current |url-status=dead}}</ref> also use ChaCha20.
** Linux typically uses [[glibc]], which did not offer ''arc4random'' until 2022. Instead, a separate library, libbsd, offers the function; it was updated to use ChaCha20 in 2016.<ref>{{cite web |title=Update arc4random module from OpenBSD and LibreSSL |url=https://cgit.freedesktop.org/libbsd/commit/?id=874a0e5 |access-date=6 January 2016}}</ref> In 2022, [[glibc]] added its own version of ''arc4random'', also based on ChaCha20.<ref>{{cite web |title=GNU C Library Finally Adds arc4random Functions For Linux |url=https://www.phoronix.com/news/GNU-Glibc-arc4random-Functions |website=www.phoronix.com |language=en}}</ref>
* According to manual pages shipped with the operating system, in the 2017 release of [[macOS]] and [[iOS]] operating systems, Apple replaced RC4 with AES in its implementation of arc4random. 

Proposed new random number generators are often compared to the RC4 random number generator.<ref>
Bartosz Zoltak.
[//eprint.iacr.org/2013/768.pdf "VMPC-R: Cryptographically Secure Pseudo-Random Number Generator, Alternative to RC4"].
2010?
</ref><ref>
Chefranov, A. G.
[https://ieeexplore.ieee.org/document/4022919/ "Pseudo-Random Number Generator RC4 Period Improvement"].
2006.
</ref>

Several attacks on RC4 are able to [[ciphertext indistinguishability#Indistinguishable from random noise|distinguish its output from a random sequence]].<ref name="mantin" />

===Implementation===
Many stream ciphers are based on [[linear-feedback shift register]]s (LFSRs), which, while efficient in hardware, are less so in software. The design of RC4 avoids the use of LFSRs and is ideal for software implementation, as it requires only byte manipulations. It uses 256 bytes of memory for the state array, S[0] through S[255], k bytes of memory for the key, key[0] through key[k−1], and integer variables, i, j, and K. Performing a modular reduction of some value modulo 256 can be done with a [[bitwise AND]] with 255 (which is equivalent to taking the low-order byte of the value in question).

===Test vectors===
These test vectors are not official, but convenient for anyone testing their own RC4 program. The keys and plaintext are [[ASCII]], the keystream and ciphertext are in [[hexadecimal]].

{| class="wikitable"
! Key !! Keystream !! Plaintext !! Ciphertext
|-
| {{mono|Key}} || {{mono|EB9F7781B734CA72A719}}… || {{mono|Plaintext}} || {{mono|BBF316E8D940AF0AD3}}
|-
| {{mono|Wiki}} || {{mono|6044DB6D41B7}}… || {{mono|pedia}} || {{mono|1021BF0420}}
|-
| {{mono|Secret}} || {{mono|04D46B053CA87B59}}… || {{mono|Attack at dawn}} || {{mono|45A01F645FC35B383552544B9BF5}}
|}