Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Consider this algorithm:

def ksa(k):
    L = length(k)
    j = 0
    for i from 0 to L: #[0..L-1] (non inclusive "to")
            j = (j + k[k[i] % L])%L
            swap(k[i], k[j])

k is an array of integers $0 \leq x < 256$. The questions is how to enumerate all possible arrays k resulting in an array with given prefix $P$. In other words if k'=ksa(k), and if $P=[1,2,3]$, then how to generate all k, so that $prefix(k',length(P))=P$? Enumeration would be best, but constructing just one such k is good too. Solution for a variant with for i from 0 to C where $C \leq L$ would be interesting too.

This is a variation of the key schedule for encryption algorithm RC4.

share|improve this question
    
Cross-posted to math.SE: math.stackexchange.com/questions/173909/… –  Ilmari Karonen Jul 22 '12 at 18:08
    
Is array k[] bound to be a permutation, and length(k) 256, as in RC4? –  fgrieu Jul 23 '12 at 11:19
    
@fgrieu: k can have arbitrary content and arbitrary length. –  qwer Jul 23 '12 at 11:28
    
@fgrieu: you are right, fixed. –  qwer Jul 23 '12 at 16:23
1  
Also, should the loop be from 0 to L-1 rather than L? Otherwise, it looks like i will point past the end of the array on the last iteration. –  Ilmari Karonen Jul 23 '12 at 17:09
show 3 more comments

1 Answer

up vote 2 down vote accepted

The algorithm you describe seems to have a class of special states (similar to the Finney states of RC4) consisting of the states such that $i = j$ and $k_x \bmod L = 1$, where $x := k_i \bmod L$.

If we are at a state that belongs to this class at the beginning of the loop, the effect of the loop will be simply to swap $k_i$ and $k_{i+1}$ and to increment both $i$ and $j$ by one. Thus, as long as we also have $x \notin \{k, k+1\}$, the state at the next iteration of the loop will also belong to this class of special states.

In particular, consider what happens if, before the algorithm, we have $k_0 = L-1$ and $k_{L-1} = 1$. Then the initial state $i = j = 0$ belongs to the special class described above, and this will continue to hold almost to the end of the algorithm. The second to last iteration, where $i = L-2$, does take us out of the class, leaving us with $i = j = x = k_x = L-1$, but this just causes the last two elements of the array $k$ to be swapped a second time on the last iteration, leaving us with $k_{L-2} = L-1$ and $k_{L-1} = 1$.

Meanwhile, all the other elements of the array, between the $L-1$ at the beginning and the $1$ at the end, just get shifted down by one position as the $L-1$ element bubbles up past them. Thus, from an initial array $$(L-1, a, b, c, \dotsc, y, z, 1) \tag{1}$$ we end up with the final state $$(a, b, c, \dotsc, y, z, L-1, 1) \tag{2}$$ regardless of the values of the unknown elements $a, b, c, \dotsc, y, z$. Conversely, to end up in any final state of the form given in $(2)$ above, it suffices to start with the corresponding initial state $(1)$.

(The same trick works also for loops terminating at some $i = C < L-1$, except that the initial $L-1$ element then ends up at $k_{C+1}$ rather than at $k_{L-2}$.)


In fact, I just wrote a little program to test this. Here's a sample run with $L = 10$, one line per iteration, starting with eight random values bracketed between $L-1 = 9$ and $1$:

k = (9, 144, 165, 42, 43, 56, 231, 72, 53, 1), i = 0, j = 0
k = (144, 9, 165, 42, 43, 56, 231, 72, 53, 1), i = 1, j = 1
k = (144, 165, 9, 42, 43, 56, 231, 72, 53, 1), i = 2, j = 2
k = (144, 165, 42, 9, 43, 56, 231, 72, 53, 1), i = 3, j = 3
k = (144, 165, 42, 43, 9, 56, 231, 72, 53, 1), i = 4, j = 4
k = (144, 165, 42, 43, 56, 9, 231, 72, 53, 1), i = 5, j = 5
k = (144, 165, 42, 43, 56, 231, 9, 72, 53, 1), i = 6, j = 6
k = (144, 165, 42, 43, 56, 231, 72, 9, 53, 1), i = 7, j = 7
k = (144, 165, 42, 43, 56, 231, 72, 53, 9, 1), i = 8, j = 8
k = (144, 165, 42, 43, 56, 231, 72, 53, 1, 9), i = 9, j = 9
k = (144, 165, 42, 43, 56, 231, 72, 53, 9, 1), j = 8, end of loop
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.