Detect Repeating Key Length

Problem

Estimate the length of a repeating XOR key. For each candidate k from 1 to max_len, compute the average Hamming distance in bits between data[i] and data[i + k] over all overlapping positions (normalized by the number of pairs), and return the k with the smallest average. Ties go to the smaller k.

Hint

At the true key length, aligned bytes come from the same key byte and agree more often.

Test cases

case 1

in: [[1,2,3,4,1,2,3,4,1,2,3,4],6]

expected: 4

case 2

in: [[7,1,5,7,1,5,7,1,5,7,1,5],5]

expected: 3

case 3

in: [[9,9,9,9,9,9,9,9],4]

expected: 1

case 4

in: [[1,2,1,2,1,2,1,2],3]

expected: 2

Starter codePython

def detect_key_length(data, max_len):
    # Your code here
    pass

4 test cases · run your code against them in the editor