1

山登りによって、特定の暗号の暗号解読で数億回実行される次のアルゴリズムを実装する必要があります。このアルゴリズムは、次のように、同じアルファベットの 7 文字のキー K を使用して、標準アルファベット {A,B,C,...,Y,Z} の順列を生成します。

  • K = INGXNDM = {9, 14, 7, 24, 14, 4, 13} と仮定します。
  • 右から左に、K1 = アルファベットの 9 桁を数えます。R に達したので、順列の最初の要素は R です: P = {R,...}
  • R を使用済みとしてマークします。後で「ジャンプ」する必要があります。
  • R から左に K2=14 の位置をカウントし、D に到達して使用済みとしてマークします。P={R,D,...}
  • 次のカウントは 7 です。A に到達するとループし、Z が A に続くと見なされるため、W に到達します: 使用済みとしてマークします。P={R,D,W,...}
  • 次のカウントは 24 で、R、D、W を飛び越えて V に到達します。
  • など... K7=13 を使用した場合は、K1=9 で再起動します
  • 得られた転置アルファベットは次のとおりです。 RDWVGBL ZHUKNFI PJSAMXT CQOYE

実際、解読コードに逆順列が必要です。私のコードは、使用された文字をスキップするための連鎖リストを実装しています。これは基数 0 であるため、A = 0、... Z = 25 であり、文字 i が位置 j にあることを意味する逆順列 Pinv(i)=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;
    }
}

2 つの質問があります。

  1. KeyToPermut のコードを最適化するにはどうすればよいですか? プロファイラーは明らかに、チェーン全体の for ループがボトルネックであることを示しています。リンクされたリストを回避する方法があるかもしれません...？
  2. 明らかに、キー スペースは 26 ではありません。しかし、はるかに小さい: 26^7 なので、26 のサブセットのみです! 生成することができます。生成された順列がどれほど具体的か知っていますか? それらは順列の既知のクラスに属していますか? たとえば、これらの順列のサイクルのパターンを（これまでのところ）特定できませんでした。

私は VS2013 と C を使用しています。プロジェクトの他の部分は CUDA コードです。(x64 プラットフォーム)

ご清聴ありがとうございました。

背景情報: 暗号で使用される暗号化スキームは、長さ 7 の 4 つの鍵 K を使用します。したがって、平文を見つけるために探索される理論的な鍵空間は 26^28、つまり 131 ビットです。メソッドは他のキーの長さを使用できます: 1 から 25 までの任意の値が機能します。

4

1 に答える 1