OK, here I try to elaborate it for non-cryptographers. As you have noted,
RC4 is a very popular cipher in the cryptographic domain, mainly because of its simplicity. It consists of a register (i.e., array) of length 256, each element of this register can hold up to 8 bits.
Here's a quick overview of how stream ciphers commonly work: a secret
key is taken, a Key-scheduling algorithm (KSA) is performed (which takes the
key as input), followed by a Pseudo-random generation algorithm (PRGA) (which outputs a sufficiently long random-looking
key-stream). To encrypt (resp. decrypt), one has to bit-wise XOR this
key-stream with the
key is of length 1 to 256. The KSA and PRGA are performed on the 256 byte register
S as follows:
for i from 0 to 255 S[i] := i endfor j := 0 for i from 0 to 255 j := (j + S[i] + key[i mod keylength]) mod 256 swap values of S[i] and S[j] endfor
i := 0, j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile
K's constitute the
key-stream. After getting first 256 bytes of the
key-stream, you need to count the frequency of each number from 0 to 255 in the
key-stream, occuring in each position for a given
The interesting thing is that, even if the
keys are taken at random, you will notice the
key-stream is far from random - "the frequency of the second byte is zero" is nearly double of what it actually should be (if it were truly random). This is known as distinguishing attack.
Your task is to:
- Take as much as you can random
keyof 16 bytes
- Generate the
key-streamof first 2 bytes for each
- Count the number of times zero appears at the 2nd byte of each the
You program should be capable of taking at least 2^19 - 2^20
keys, and make the code run as fast as you can.
Here's a quick try of me in Python:
def ksa(S): key = range(256) j = 0 for i in range(256): j = (j + key [i] + S [i % len(S)]) % 256 key [i], key [j] = key [j], key [i] return key def prga (key): i = 0; j = 0 while True: i = (i + 1) % 256 j = (j + key [i]) % 256 key [i], key [j] = key [j], key [i] yield key [(key [i] + key [j]) % 256] def encrypt_or_decrypt (text, S): alt_text =  key = ksa (S) prga_generator = prga(key) for byte in text: alt_text.append (prga_generator. next()) return tuple (alt_text) if __name__ == '__main__': from time import time stime = time () import sys rounds = int (sys.argv ); text_length = 256; key_length = 16 text = [0 for x in range(text_length)] out = list () import random, numpy as np for r in range (rounds): S = [random.randint(0, 255) for x in range (key_length)] out.append (encrypt_or_decrypt (text, S)) print str (range (256)) [1:-1] for o in np.transpose (out): temp = list(np.bincount (o)) while len (temp) < 256: temp.append (0) print str (temp)[1:-1] print time () - stime
Pipe the output to a CSV file and note the content of A3 cell, after opening it with an office package (it should be nearly double of each of the other cells).
This one is of 524288
keys (it took 220.447999954s of my i5 processor, 4 GB RAM):
BONUS: Create the whole 256 by 256 frequency matrix, where rows indicate the frequency of a number (in 0 to 255) and columns indicate the corresponding byte position (from 1 to 256).
- Fastest in terms of # iterations/ second in my computer
- Single-threaded execution only (multi-threaded versions are also welcome here, but not as a participant)
- For tie (or nearly tie) cases, popularity and capability of more iterations will be considered (though I suppose there will be no such situation)
- No need for true random numbers, pseudo random numbers will suffice, as it is not a cryptographic contest
Update In my computer, here are the results (2^24 iterations):
- bitpwner The 256 * 256 matrix in 50.075s
- Dennis The bias 19.22s
Since, there seems no more answer coming in, I declare Dennis as the winner. bitpwner did really good with the big matrix.