Rust

Rust port of @Vectorized's C code.

Takes about 38 secs to run on Rust Playground for 2^24 = 16777216 trials.

Takes about 17.4 secs to run on my laptop for 2^24 = 16777216 trials.

cargo build --release && cargo run --release

Run it on Rust Playground.

extern crate rand;

use rand::Rng;
use std::time::Instant;

const KEY_LENGTH: usize = 16;
const ITERATIONS: usize = 16_777_216;

fn ksa(state: &mut [u8; 256], key: &[u8; KEY_LENGTH]) {
    let mut j = 0;
    for i in 0..256 {
        state[i] = i as u8;
    }
    for i in 0..256 {
        j = (j + state[i] as usize + key[i % KEY_LENGTH] as usize) % 256;
        state.swap(i, j);
    }
}

fn prga(state: &mut [u8; 256], out: &mut [u8; 256]) {
    let mut i = 0;
    let mut j = 0;
    for x in 0..256 {
        i = (i + 1) % 256;
        j = (j + state[i] as usize) % 256;
        state.swap(i, j);
        out[x] = state[(state[i] as usize + state[j] as usize) % 256];
    }
}

fn make_random_key(key: &mut [u8; KEY_LENGTH]) {
    let mut rng = rand::thread_rng();
    for byte in key.iter_mut() {
        *byte = rng.gen_range(0..=255);
    }
}

fn main() {
    let time_started = Instant::now();

    let mut state = [0u8; 256];
    let mut out = [0u8; 256];
    let mut key = [0u8; KEY_LENGTH];
    let mut occurrences = [[0usize; 256]; 256];

    for _ in 0..ITERATIONS {
        make_random_key(&mut key);
        ksa(&mut state, &key);
        prga(&mut state, &mut out);

        for j in 0..256 {
            occurrences[j][out[j] as usize] += 1;
        }
    }

    for byte_position in 0..256 {
        print!("{},", byte_position);
    }
    println!();

    for char_occurrence in 0..256 {
        for byte_position in 0..256 {
            print!("{},", occurrences[char_occurrence][byte_position]);
        }
        println!();
    }

    let time_taken = time_started.elapsed();
    println!(
        "Time taken, {}.{:06} s",
        time_taken.as_secs(),
        time_taken.subsec_micros()
    );
}

C (1,432,725 keys / second)

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define RAND_64() *Ks = rand(), Ks++, *Ks = rand(), Ks++, *Ks = rand(), Ks++, *Ks = rand()
#define KSA_1()   t = *s, j += t + *k, *s = S[j], S[j] = t, s++
#define KSA_4()   KSA_1(); k++; KSA_1(); k++; KSA_1(); k++; KSA_1()
#define KSA_16()  KSA_4(); k++; KSA_4(); k++; KSA_4(); k++; KSA_4(); k = K
#define KSA_64()  KSA_16(); KSA_16(); KSA_16(); KSA_16()

int main(int argc, char *argv[])
{
        int i, m = atoi(argv[1]), r = 0;
        uint8_t j, K[16], *k = K, S[256], *s, S0[256], t;
        uint16_t *Ks;
        for(i = 0; i < 256; i++) S0[i] = i;
        srand(time(NULL));

        for(i = 0; i < m; i++)
        {
                Ks = (uint16_t *) K, RAND_64(), Ks++, RAND_64();
                memcpy(S, S0, 256); s = S, j = 0;
                KSA_64(); KSA_64(); KSA_64(); KSA_64();
                j = S[1], S[1] = S[j], S[j] = j;
                t = S[2], j += t, S[2] = S[j], S[j] = t, t += S[2];
                r += (S[t] == 0);
        }
        printf("%u\n", r);
}

Benchmarking

$ gcc -Ofast rc4bias-rand.c && time ./a.out $[2**24]
130924
Real    11.71
User    11.71
Sys     0.00
$ bc <<< '2^24 / 11.71'
1432725

Tested on an Intel i7-3770 running Fedora 20.

C

Takes about 111 secs to run on my Macbook Air for 2^24 = 16777216 trials.

To compile: gcc -o rc4 rc4.c

To pipe the output to a csv: ./rc4 > rc4out.csv

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdlib.h>
#include <sys/time.h>

#define KEY_LENGTH 16
#define ITERATIONS 16777216

void ksa(unsigned char state[], unsigned char key[]) {
    int i,j=0,t; 
    for (i=0; i<256; ++i)
        state[i] = i; 
    for (i=0; i<256; ++i) {
        j = (j + state[i] + key[i % KEY_LENGTH]) % 256; 
        t = state[i]; 
        state[i] = state[j]; 
        state[j] = t; 
    }
}

void prga(unsigned char state[], unsigned char out[]) {  
    int i=0,j=0,x,t; 
    unsigned char key; 
    for (x=0; x<256; ++x) {
        i = (i + 1) % 256; 
        j = (j + state[i]) % 256; 
        t = state[i];
        state[i] = state[j];
        state[j] = t;
        out[x] = state[(state[i] + state[j]) % 256];
    }
}

void makeRandomKey(unsigned char key[]) {
    int i;
    for (i=0; i<KEY_LENGTH; ++i) 
        key[i] = rand() % 256;
} 

int main(int argc, char *argv[]) {

    struct timeval time_started, time_now, time_diff;
    gettimeofday(&time_started, NULL);

    unsigned char state[256];
    unsigned char out[256];
    unsigned char key[KEY_LENGTH];
    int occurances[256][256];
    int i,j,bytePosition,charOccurance;

    for (i=0; i<256; ++i) 
        for (j=0; j<256; ++j)
            occurances[i][j] = 0;

    srand(time(NULL));
    for (i=0; i<ITERATIONS; ++i) {
        makeRandomKey(key);
        ksa(state, key);
        prga(state, out);

        for (j=0; j<256; ++j)
            ++occurances[j][out[j]];
    }

    for (bytePosition=0; bytePosition<256; ++bytePosition) {
        printf("%d,", bytePosition);
    }
    printf("\n");
    for (charOccurance=0; charOccurance<256; ++charOccurance) {
        for (bytePosition=0; bytePosition<256; ++bytePosition) {
            printf("%d,", occurances[charOccurance][bytePosition]);
        }
        printf("\n");
    }

    gettimeofday(&time_now, NULL);
    timersub(&time_now, &time_started, &time_diff);
    printf("Time taken,%ld.%.6ld s\n", time_diff.tv_sec, time_diff.tv_usec);

    return 0;
}

Results for 16777216 trials.

Multithreaded version here. Compile with gcc -o rc4 rc4.c -pthreads.