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$

closed as unclear what you're asking by Raphael Mar 16 '16 at 10:53

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.

$\endgroup$

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