1
$\begingroup$

I am trying to implement an algorithm that finds the key of the RC4 cipher from the inner permutation. For each key byte I have several options, each with different weight. Is there any way, to test first the possibilities with highest weight, than with second highest, and so on?

Basically what I need is to generate vectors like this (for 3 byte key):

[0,0,0]
[1,0,0]
[0,1,0]
[0,0,1]
[1,1,0]
[1,0,1]
[0,1,1]
[1,1,1]
[2,1,1]
...

So it is sorted by sum.

(I have the bytes stored in a table sorted by weight, highest weight on the top.)

A similar problem is solved here: application of Dijkstra's algorithm, but I don't know how to apply it to my problem.

The paper only mentions that they do it in iterative depth manner.

Is there any algorithm which solves this problem?

$\endgroup$
  • 1
    $\begingroup$ I'm afraid you haven't specified your problem completely. What tuples do you consider? What is the weight of a tuple? Is the following interpretation correct: there are $N_i$ options for the $i$th coordinate, having given arbitrary weights $w_{i,1},\ldots,w_{i,N_i}$? $\endgroup$ – Yuval Filmus Mar 15 '16 at 16:59
  • $\begingroup$ Agreed -- without the definition of weight the question can not be answered. Closing as "unclear"; you can edit in your definition and flag for reopening. $\endgroup$ – Raphael Mar 16 '16 at 10:53
1
$\begingroup$

I'm assuming the following version of the problem. We are considering all vectors in the set $[N_1] \times \cdots \times [N_d]$ (of which there are $N_1\cdots N_d$). We are given weights $w_{i,1} \leq \cdots \leq w_{i,N_i}$ for each of the $d$ sets (if you prefer, you can index the elements starting from 0 instead of starting from 1). Our goal is to enumerate $[N_1] \times \cdots \times [N_d]$ in non-decreasing order of weight, where the weight of $(x_1,\ldots,x_d)$ is $w_{1,x_1} + \cdots + w_{d,x_d}$.

One possible approach uses a heap. The heap is initialized with $(1,\ldots,1)$. At each step, we extract the element $(x_1,\ldots,x_d)$, output it, and insert the up to $d$ elements obtained by increasing each of the coordinates by 1 (unless it equals its maximum). It is hard to estimate the complexity of this algorithm, but it might work reasonably well in practice.

| cite | improve this answer | |
$\endgroup$

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