1

我是第二年的 B. Comp。科学。学生并且有一个密码学作业真的让我很伤心。我们得到了一个转置加密的英语短语的文本文件和一个英语词典文件，然后要求我们编写一个程序来自动破译这些短语，而无需任何用户输入。

我的第一个想法是简单地暴力破解密文的所有可能排列，这应该是微不足道的。但是，然后我必须决定哪一个最有可能成为实际的明文，这就是我正在努力解决的问题。

SO上有大量关于分词的信息，包括this和this以及其他帖子。使用这些信息以及我在大学已经学到的知识，这是我目前所掌握的：

string DecryptTransposition(const string& cipher, const string& dict)
{
    vector<string> plain;

    int sz = cipher.size();
    int maxCols = ceil(sz / 2.0f);
    int maxVotes = 0, key = 0;

    // Iterate through all possible no.'s of cols.
    for (int c = 2; c <= maxCols; c++)
    {
        int r = sz / c;     // No. of complete rows if c is no. of cols.
        int e = sz % c;     // No. of extra letters if c is no. of cols.

        string cipherCpy(cipher);
        vector<string> table;
        table.assign(r, string(c, ' '));

        if (e > 0) table.push_back(string(e, ' '));
        for (int y = 0; y < c; y++)
        {
            for (int x = 0; x <= r; x++)
            {
                if (x == r && e-- < 1) break;
                table[x][y] = cipherCpy[0];
                cipherCpy.erase(0, 1);
            }
        }
        plain.push_back(accumulate(table.begin(),
            table.end(), string("")));

        // plain.back() now points to the plaintext
        // generated from cipher with key = c
        int votes = 0;
        for (int i = 0, j = 2; (i + j) <= sz; )
        {
            string word = plain.back().substr(i, j);
            if (dict.find('\n' + word + '\n') == string::npos) j++;
            else
            {
                votes++;
                i += j;
                j = 2;
            }
        }
        if (votes > maxVotes)
        {
            maxVotes = votes;
            key = c;
        }
    }
    return plain[key - 2];      // Minus 2 since we started from 2
}

这个算法有两个主要问题：

  1. 它非常慢，大约需要 30 秒。解密一个 80 字符。信息。
  2. 它并不完全准确（如果我还没有占据一整页，我会详细说明这一点，但您可以使用完整的 VC++ 2012 项目自己尝试一下）。

任何有关如何改进此算法的建议将不胜感激。MTIA :-)

4

0 回答 0