3

我在Project Euler研究问题集已经有一段时间了，并且很享受所面临的挑战。我目前正在处理涉及加密和解密过程的问题 59 。

从任何合理的标准来看，这个问题都是一个非常简单的解密问题。

  • 我被告知加密密钥由 3 个小写字母组成。
  • 我已经得到了加密/解密过程的描述。
  • 我收到了一个加密的文本文件，其中只包含加密的常用英文单词

我完全理解导入数据、循环遍历所有可能的密钥以及尝试使用每个可能的密钥解密文件数据的过程。我的问题是，在尝试使用其中一个密钥进行解密之后，我如何判断该密钥是否是正确的解密密钥？就计算机而言，每个解密密钥只是将数据从一个值转换为另一个值。该值的含义纯粹是主观的/解释的。如何判断解密密钥是否已将数据解密为有意义的内容（即常用英文单词）

这是我到目前为止的代码（C#）：

    static void Main(string[] args)
    {
        /* Get the data from the file and convert to byte array*/
        StreamReader inData = new StreamReader(@"C:\Users\thantos\Desktop\cipher1.txt");
        string[] strData = inData.ReadLine().Split(new char[] {','});
        byte[]  fileData = new byte[strData.Length];
        foreach (string x in strData) { byte.Parse(x); }

        /* for each three character lowercase password */
        for (uint i = 0; i < 26; i++) {
            for (uint j = 0; j < 26; j++){
                for (uint k = 0; k < 26; k++) {
                    /* create a key */
                    byte[] key = new byte[3];
                    key[0] = (byte)(i + 97);
                    key[1] = (byte)(j + 97);
                    key[2] = (byte)(k + 97);

                    /* create temp copy of data */
                    byte[] dataCopy = new byte[fileData.Length];
                    fileData.CopyTo(dataCopy, 0);

                    /* decrypt using key */
                    for (uint l = 0; l < dataCopy.Length; l++) { 
                        dataCopy[l] = (byte)(dataCopy[l] ^ key[l%key.Length]);
                    }

                    /* cannot figure out how to check 
                     * if data is meaningfully decrypted
                     */
                    bool dataIsMeaningful = isMeaningful(dataCopy);

                    if(dataIsMeaningful) {
                      /* do stuff with data if correct 
                       * decryption key was found 
                       */
                    }
                }
            }
        }
    }

我已经尝试过这种方法isMeaningful()：

public static isMeaningful(byte[] inData) {
  bool isGood = true;
    for (uint i = 0; good && i < inData.Length; i++) {
      isGood &= (char.IsLower((char)inData[i]));;
    }
   return isGood;
}

但它对所有 17576 个可能的键都返回 true。

如何确定解密密钥是否已将文件数据解密为有意义的数据？我不是在寻找解决方案代码或 Project Euler 问题的答案，我在寻找有关如何检查您的解密尝试是否成功的解释。

4

4 回答 4

2

尝试不同的键，并根据正常英语的字母频率对它们进行评分：空格，然后是 E、T、A、O、I、N、S、H、R、D、L、U。首先选择得分最高的键审判。

于 2012-08-31T00:26:47.670 回答
1

好吧，您可以假设只允许有效的 ASCII 值（因为它应该是明文）。因此，对于您解码的每个字母，只需检查生成的异或结果是否为有效值：if(dataCopy[l] < 32 || dataCopy[l] > 122) continue;这应该有助于消除绝大多数可能的组合键。

实际上，这种技术甚至可以用来缩小您的键集范围。因此，与其在整个 1200 个字符串上迭代循环 26^3 次，不如最初迭代 26 次并跟踪哪个位置的哪个字母仍然有效。

var letters = Enumerable.Repeat(Enumerable.Range((int)'a', 'z'-'a' + 1).Select(e => (char)e), 3).Select (e => e.ToList()).ToList();
for(int i = 0, j = 0; i < passwordBytes.Length; i++)
{
    j = i % 3;
    for(int k = 0; k < letters[j].Count; k++)
    {
        byte r = (byte)(letters[j][k] ^ passwordBytes[i]);
        if(r < 32 || r > 122) letters[j].RemoveAt(k--);
    }
}

这应该使您的有效字符几乎为零，此时您可以迭代剩余的值（这不应该花费太长时间）并寻找一些有效的序列（我听说寻找" the "是一个不错的选择）。

于 2012-08-30T17:58:57.510 回答
0

您可以将原始消息的校验和与加密消息一起发送吗？解密后，计算校验和并查看它们是否匹配。

如果那不可用，那么测试消息呢？您可以先发送一条测试消息，例如“这是我的测试消息”，然后检查解密的消息是否逐字匹配。这不是万无一失的，但它可能会覆盖你。

于 2012-08-30T16:38:27.107 回答
0

当您使用密钥解密数据时，它应该为您提供了一个填充了文本的文本文档。要检查合法数据，是否可以使用空格字符作为分隔符将文本拆分为文本数组，然后根据英语词典检查数组中的每个“单词”？

于 2012-08-30T16:43:52.537 回答