3

私はプロジェクトオイラーで問題セットにしばらく取り組んでおり、提示された課題を楽しんでいます。私は現在、暗号化と復号化のプロセスを含む問題59に取り組んでいます。

問題は、合理的な基準によれば、非常に単純な復号化の問題です。

  • 暗号化キーは小文字の3文字で構成されていると言われています。
  • 暗号化/復号化プロセスについて説明しました。
  • 暗号化された一般的な英語の単語のみを含む暗号化されたテキストファイルが提供されました

データをインポートし、可能なすべてのキーを循環し、可能な各キーを使用してファイルデータを復号化するプロセスを完全に理解しています。私の問題は、キーの1つを使用して復号化を試みた後、そのキーが正しい復号化キーであったかどうかをどのように判断できるかということです。コンピュータに関する限り、すべての復号化キーはデータをある値から別の値に変換するだけです。その値の意味は、純粋に主観的/解釈されます。復号化キーがデータを意味のあるもの（つまり、一般的な英語の単語）に復号化したかどうかを確認するにはどうすればよいですか？

これが私がこれまでに持っているコードです（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を返します。

復号化キーがファイルデータを意味のあるデータに復号化したかどうかをどのように判断できますか？私はソリューションコードやプロジェクトオイラーの問題に対する答えを探していません。復号化の試みが成功したことを確認する方法の説明を探しています。

4

4 に答える 4

2

さまざまなキーを試して、通常の英語の文字頻度に対してスコアを付けます。スペース、続いてE、T、A、O、I、N、S、H、R、D、L、U。トライアル。

于 2012-08-31T00:26:47.670 に答える
1

有効なASCII値のみが許可されていると想定できます（プレーンテキストである必要があるため）。したがって、デコードするすべての文字について、結果のXORが有効な値になることを確認するだけです。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:43:52.537 に答える
0

暗号化されたメッセージと一緒に元のメッセージのチェックサムを送信できますか？復号化後、チェックサムを計算し、それらが一致するかどうかを確認します。

それが利用できない場合、テストメッセージはどうですか？最初に「これは私のテストメッセージです」などのテストメッセージを送信し、復号化されたメッセージが逐語的に一致するかどうかを確認できます。それは絶対確実ではありませんが、それはあなたをカバーするかもしれません。

于 2012-08-30T16:38:27.107 に答える