java - 以整数作为键和值的 HashMap 需要很长时间才能完成工作

Question

我正在研究 2DES 上的中间相遇攻击。我已经实现了 DES 加密/解密并且它正在工作。我尝试实现此目的的方法是在 for 循环中将中间密码存储为 HashMap 的键，并将可能的键存储为 HashMap 的值。两者都是整数 - 以 byte[] 开头，但发现键不能是数组。然而，在这个 for 循环中，我还想确保可能的键是唯一的，即我有一个 while 循环，它确保 HashMap 的大小为 2^20(只有 20 位的 DES key 有效)。之后，我尝试通过使用 foreach 迭代 HashMap 来找到具有匹配中间密文的 key ，并将加密中的每个中间密文与解密中的中间密文进行比较。

但是，我无法找到比赛，因为完成时间太长。我已经等了大约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);
                }
            }
        }

intermediateCipher 是我的 HashMap 。

PlainText是一个8字节的byte[]，cipherText2是对plainText进行2DES加密的结果，generateDesKey是生成64位的方法，其中跳过奇偶校验位以确保20位有效，并将这些位转换为 byte[]，因为 DES 要求

Answer 1

阅读您的代码后，我有一些优化建议:

1. 最重要的是:如果您只能访问一次 map ，就不要浪费精力访问两次 map :而不是:

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

... reduce it to:

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

2. There is too much memory allocating within the loops, because it is useless to create a new ByteBuffer only for temporary operations and then discard it (too much GC overworking). If you are certain that the byte buffers used will have length 8 (or less), you can use a single buffer in the first loop:

   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 大小始终是一个好习惯。事情应该是这样的:
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()每次迭代都会返回相同的值，您可以在循环之前设置它。