HashMap с целыми числами в качестве ключа и значения занимает слишком много времени, чтобы закончить работу

Question

Я работаю с атакой в ​​середине встречи на 2DES.Я реализовал шифрование / дешифрование DES, и оно работает.Я пытаюсь достичь этого путем сохранения в цикле for промежуточных шифров в качестве ключа HashMap и возможных ключей в качестве значений HashMap.Оба в виде целых чисел - начались с byte [], но выяснили, что ключ не может быть массивом.Однако в этом цикле for я также хочу убедиться, что возможные ключи уникальны, т.е. у меня есть цикл while, который гарантирует, что размер HashMap равен 2 ^ 20 (эффективны только 20 бит ключа DES).Затем я пытаюсь найти ключи, которые имеют соответствующий текст промежуточного шифра, перебирая HashMap с foreach, и сравниваю каждый текст промежуточного шифра из шифров с текстом промежуточного шифра из расшифровок.

Однако яЯ не могу найти совпадение, так как это занимает слишком много времени, чтобы закончить.Я ждал около 20 минут без какого-либо результата.

while (intermediateCipher.size() < Math.pow(2, 20)) {
            byte[] key = generateDesKey();

            intermediateCipher.put(ByteBuffer.wrap(encrypt(key, plainText)).getInt() , ByteBuffer.wrap(key).getInt());
        } 

        int count = 0;
        for (Entry<Integer, Integer> arr : intermediateCipher.entrySet()) {
            byte[] k2 = ByteBuffer.allocate(8).putInt(arr.getValue()).array();
            int temp = ByteBuffer.wrap(decrypt(k2, cipherText2)).getInt();
            if (intermediateCipher.containsKey(temp)) {
                count++;
                byte[] k1 = ByteBuffer.allocate(8).putInt(intermediateCipher.get(temp)).array();

                if (encrypt(k2, encrypt(k1, plainText)) == cipherText2) {
                    System.out.println("Key is " + k1 + " " + k2);
                }
            }
        }

промежуточный шифр - это мой хэш-карта.

PlainText - это байт [] из 8 байтов, cipherText2 - это результат шифрования 2DES наplainText и generateDesKey - это метод, который генерирует 64 бита, где биты четности пропускаются, чтобы убедиться в эффективности 20 битов, и преобразовать биты в байт [], поскольку DES требует, чтобы

Answer 1

После прочтения вашего кода у меня есть несколько предложений по его оптимизации:

1. Самое важное: не тратьте усилия на доступ к карте дважды, если вы можете получить доступ только один раз: вместо:

    if (intermediateCipher.containsKey(temp)) {
        byte[] k1 = intermediateCipher.get(temp);
        ...
    }

... уменьшить до:

    byte[] k1 = intermediateCipher.get(temp);
    if (k1!=null) {
        ...
    }

Слишком много памяти выделяется внутри циклов, потому что бесполезно создавать новый ByteBuffer только для временных операций, а затем отбрасывать его (слишком много перегрузки GC).Если вы уверены, что используемые байтовые буферы будут иметь длину 8 (или меньше), вы можете использовать один буфер в первом цикле:

ByteBuffer tempBuffer=ByteBuffer.allocate(8);
while (intermediateCipher.size() < Math.pow(2, 20)) {
    // Note: A call to rewind() must be done before each put/get operation on the buffer:
    byte[] key = generateDesKey();
    tempBuffer.rewind();
    tempBuffer.put(encrypt(key, plainText));
    tempBuffer.rewind();
    int mapKey=tempBuffer.getInt();
    tempBuffer.rewind();
    tempBuffer.put(key);
    tempBuffer.rewind();
    int mapValue=tempBuffer.getInt();
    intermediateCipher.put(mapKey, mapValue);
}

Во втором цикле можно выполнить аналогичное преобразование.

Как подсказывает @Thilo в комментарии, всегда рекомендуется предварительно изменять размер вашей карты в зависимости от ожидаемого максимального размера.Он должен выглядеть следующим образом: Map<...> intermediateCipher=new HashMap<...>((int)(1.7d * expectedSize));

Петля while (intermediateCipher.size() < Math.pow(2, 20)) должна быть упрощена до int len=Math.pow(2, 20); for (int i=0;i<len;i++)

Обновление

Если вызов generateDesKey() возвращает одно и то же на каждой итерации, вы можете установить его до цикла.

Answer 2

Вот некоторые вещи, которые вы можете попробовать сократить время выполнения.

Сначала переключитесь с HashMap на TreeMap.Когда HashMap становится слишком большим, как 2 ^ 20, поиск в худшем случае должен перейти от O (1) к O (n), потому что все слоты в хэш-таблице заполнены большим количеством записей.Тем не менее, поиск TreeMap всегда выполняется в O (lg n).

Во-вторых, переключитесь с Map<Integer, Integer> на Map<Integer, byte[]>.Вам нужно только преобразовать ключи карты в целые числа;Вы можете оставить значения в виде байтовых массивов, что приведет к значительно меньшему количеству byte[] -> ByteBuffer -> int преобразований.

Map<Integer, byte[]> intermediateCipher = new TreeMap<>();

и

while (intermediateCipher.size() < Math.pow(2, 20)) {
    byte[] key = generateDesKey();
    int encrypted = ByteBuffer.wrap(encrypt(key, plainText)).getInt();
    intermediateCipher.put(encrypted, key);
} 

int count = 0;
for (Entry<Integer, byte[]> arr : intermediateCipher.entrySet()) {
    byte[] k2 = arr.getValue();
    int temp = ByteBuffer.wrap(decrypt(k2, cipherText2)).getInt();

    if (intermediateCipher.containsKey(temp)) {
        count++;
        byte[] k1 = intermediateCipher.get(temp);
        if (encrypt(k2, encrypt(k1, plainText)) == cipherText2) {
            System.out.println("Key is " + k1 + " " + k2);
        }
    }
}