Generate permutation with keyword

Question

I have to implement the following algorithm which will be run a few zillion times in the cryptanalysis of a specific cipher, by hill-climbing. The algorithm produces a permutation of the standard alphabet {A,B,C,...,Y,Z} with a key K of 7 letters of the same alphabet, as follows:

• Assume K = INGXNDM = {9, 14, 7, 24, 14, 4, 13}
• From right to left, count K1=9 positions on the alphabet. The R is reached, so the first element of the permutation is R: P = {R,...}
• Mark R as used, we will have to 'jump' over it later.
• From R, count K2=14 positions to the left, we reach D and mark it as used. P={R,D,...}
• The next count is 7, when reaching A we loop and consider that Z follows A, so we reach W: mark it as used, P={R,D,W,...}
• The next count is 24, so we reach V because we jump over R,D and W.
• and so on... When K7=13 has been used, we restart with K1=9
• the obtained transposed alphabet is: RDWVGBL ZHUKNFI PJSAMXT CQOYE

In fact I need the inverse permutation in the deciphering code. My code implements a chained list for skipping the used letters. It is in base 0, so A = 0, ... Z = 25 and returns the inverse permutation Pinv(i)=j meaning that the letter i is at position j.

#define ALPHALEN 26
void KeyToPermut(int *K, int * Pinv);
int previnit[ALPHALEN], prev[ALPHALEN], nextinit[ALPHALEN], next[ALPHALEN];

int main() {
    int l, Pinv[ALPHALEN], K[7] = { 8, 13, 6, 23, 13, 3, 12 }, P[ALPHALEN];
    // precalculate links between letters, ordered right to left , from Z to A
    for (l = 0; l < ALPHALEN; l++) {
        previnit[l] = l + 1;  // prev[A] = B
        if (previnit[l] >= ALPHALEN) previnit[l] -= ALPHALEN;  // prev[Z] = A
        nextinit[l] = l - 1; // next[B] = A
        if (nextinit[l] < 0) nextinit[l] += ALPHALEN; // next[A] = Z
    }

    KeyToPermut(K, Pinv); // this is the code to be optimized

    for (l = 0; l < ALPHALEN; l++) P[Pinv[l]] = l;  // calculate direct permutation
    for (l = 0; l < ALPHALEN; l++)  printf("%c", P[l] + 65);
    printf("\n");
}

void KeyToPermut(int *K, int * Permut) {
    int l, keyptr=0, cnt=0, p=0;
    // copy prev[] and next[] from precalculated arrays previnit[] and nextinit[]
    for (l = 0; l < ALPHALEN; l++) {
        prev[l] = previnit[l];
        next[l] = nextinit[l];
    }

    while (1) {
        for (l = 0; l <= K[keyptr] % (ALPHALEN-cnt); l++) p = next[p];

        Permut[p] = cnt++;
        if (cnt < ALPHALEN)
        {
            prev[next[p]] = prev[p];      // link previous and next positions
            next[prev[p]] = next[p];
            keyptr++;
            if (keyptr >= 7) keyptr = 0;  // re-use K1 after K7
        }
        else
            break;
    }
}

I have 2 questions:

1. how can I optimize the code in KeyToPermut ? The profiler obviously indicates that the for loop across the chaining is the bottleneck. There might be a method avoiding the linked list ...?
2. Obviously the key space is not 26! but much smaller: 26^7, so only a subset of the 26! can be generated. Do you know how specific the generated permutations are ? Do they belong to a known class of permutations ? For example, I could not identify (so far) any pattern in the cycles of these permutations.

I use VS2013 and C ,other parts of the project are CUDA code. (x64 platform)

Thank you for your attention.

Background information: the encryption scheme used by the cipher uses 4 keys K of length 7. So, the theoretical key-space to be explored for finding the plain-text is 26^28 i.e. 131 bits. The method could use other key lengths: any value from 1 to 25 would work.

Answer 1

how can I optimize the code in KeyToPermut ? The profiler obviously indicates that the for loop across the chaining is the bottleneck. There might be a method avoiding the linked list ...?

I didn't find a better method avoiding the linked list, but we can do with a singly instead of doubly linked one, since the needed previous position can be obtained from the last iteration of the for loop.

void KeyToPermut(int *K, int *Permut)
{
    int l, keyptr=0, cnt=0, p=0, prev;
    // copy next[] from precalculated array nextinit[]
    for (l = 0; l < ALPHALEN; l++) next[l] = nextinit[l];
    while (1)
    {
        for (l = 0; l <= K[keyptr] % (ALPHALEN-cnt); l++) prev = p, p = next[p];
        Permut[p] = cnt++;
        if (cnt < ALPHALEN)
        {
            next[prev] = next[p];         // link previous to next position
            p = prev;
            keyptr++;
            if (keyptr >= 7) keyptr = 0;  // re-use K1 after K7
        }
        else
            break;
    }
}

This saves about 10 % runtime of the function.