Почему проверка на наличие определенного значения в HashMap занимает очень много времени в цикле for? - PullRequest
Новая
       9

Почему проверка на наличие определенного значения в HashMap занимает очень много времени в цикле for?

0 голосов
/ 22 ноября 2018

Я работаю с атакой "встречай посередине" на Double-DES.Я реализовал шифрование / дешифрование DES и выполнил шифрование, и теперь я хотел бы выполнить MITM-атаку на Double-DES, чтобы найти ключи.Я пытаюсь достичь этого путем сохранения в цикле for промежуточных шифров в качестве ключа HashMap и возможных ключей в качестве значений HashMap.Однако в этом цикле for я также хочу убедиться, что возможные ключи уникальны, т.е. у меня есть оператор if, который проверяет, существует ли возможный ключ в HashMap.Если нет, то он использует его для шифрования простого текста и сохранения зашифрованного текста и возможного ключа в HashMap.Далее я пытаюсь найти ключи, которые имеют соответствующий промежуточный текст шифрования, перебирая HashMap с foreach, и сравнивать каждый промежуточный текст шифра из шифров с текстом промежуточного шифра из расшифровок.

Тем не менее, я не могу найти совпадение, так как это занимает слишком много времени, чтобы закончить.Я ждал около 2 часов безрезультатно.Если я удаляю оператор if, который проверяет, находится ли возможный ключ в HashMap, он завершается примерно через 10 секунд. 

for (int size = intermediateCipher.size(); size < Math.pow(2, 20); size++) { // intermediateCipher is my HashMap consisting of <String, byte[]>
    byte[] possibleKey = generateDesKey(); // generateDesKey generates a key of 64 bits
    if (!intermediateCipher.containsValue(possibleKey)) {
        intermediateCipher.put((encrypt(possibleKey, plainText)).toString(), possibleKey);
    }
}

int count = 0;
for (Entry<String, byte[]> arr : intermediateCipher.entrySet()) {

    String temp = (decrypt(arr.getValue(), cipherText)).toString();

    if (intermediateCipher.containsKey(temp)) {
        count++;
    }
}

Я должен упомянуть, что эффективен только 20 бит ключа DES.Вот почему есть 2 ^ 20 возможных ключей.Кроме того, если у меня нет оператора if, который проверяет, находится ли возможный ключ в HashMap, я получаю 510 совпадений, что слишком много.

ОБНОВЛЕНИЕ:

У меня естьпопытался использовать Set для того, чтобы сначала сохранить ключи, а затем использовал ключи из Set для шифрования и т. д. Однако вместо использования for, которое перебирает от 0 до 2 ^ 20, я попытался с циклом while, который проверяетповторяется до тех пор, пока Set имеет элементы.Тем не менее, я пытался запустить этот подход в течение более 10 минут без какого-либо результата.Он никогда не выходит из цикла. 

for (int i = 0; i < Math.pow(2, 20); i++) {
            possibleKeySet.add(generateDesKey());
        }
        System.out.println(possibleKeySet.size());

        for (int i = 0; i < possibleKeySet.size(); i++) {

            intermediateCipher.put((encrypt(possibleKeySet.iterator().next(), plainText)).toString(),
                    possibleKeySet.iterator().next());
        }

        System.out.println("ss " + intermediateCipher.size());

        int count = 0;
        for (Entry<String, byte[]> arr : intermediateCipher.entrySet()) {

            String temp = ((decrypt(arr.getValue(), cipherText)).toString());
            if (intermediateCipher.containsKey(temp)) {
                count++;
            }
        }

Я читал, что для набора hasNext () всегда возвращает true для непустой коллекции.Итак, я пробовал использовать a для каждого, но размер hashMap никогда не совпадает с размером набора ключей, что не имеет смысла для меня, поскольку я использую каждый ключ в наборе: 

for (int i = 0; i < Math.pow(2, 20); i++) {
            possibleKeySet.add(generateDesKey());
        }

        System.out.println(possibleKeySet.size());

        for (byte[] key : possibleKeySet) {
            intermediateCipher.put((encrypt(key, plainText)).toString(),
                    key);
        }

Ответы [ 2 ]

0 голосов
/ 22 ноября 2018

Map.containsValue() необходимо проверить каждую запись на карте.Это стоит O (n) в размере карты.Предположим, что количество дубликатов не превышает фиксированную долю всех сгенерированных ключей, проверка containsValue() на каждой итерации вашего цикла приводит к совокупной O (n 2 ) в количестве сгенерированных ключей.Для миллиона ключей это ужасно дорого.

Попробуйте вместо этого сохранить вспомогательные Set ключей, хранящихся до сих пор, и проверить членство в этом наборе вместо непосредственного тестирования значений в карте.

0 голосов
/ 22 ноября 2018

Map.containsValue() будет иметь линейное время, так как вы будете перебирать вслепую по всем значениям карты.Согласно методу javadoc:

Возвращает true, если эта карта отображает один или несколько ключей на указанное значение.Более формально, возвращает true тогда и только тогда, когда эта карта содержит хотя бы одно отображение на значение v, такое что Objects.equals (value, v). Эта операция, вероятно, потребует линейного времени в размере карты для большинства реализаций интерфейса Map.

Чтобы воспользоваться преимуществом поиска в хэше, вы должны проверить ключи с помощью Map.containsKey(): 

if (!intermediateCipher.containsKey(possibleKey)) {
  ...
}
...