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

Question

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

然而，我找不到比赛，因为比赛要花很长时间才能结束。我等了大概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字节的字节[]，cipherText2是在PlainText上2DES的加密结果，generateDesKey是生成64位的方法，其中跳过奇偶校验位以确保20位有效，并将这些位转换为字节[]，因为DES要求

Answer 1

阅读您的代码后，我有几个优化建议：

1. 最重要的是：如果只访问一次，不要浪费精力访问两次地图：而不是：

if(intermediateCipher.contentsKey(temp(({byte[]k1=intermediateCipher.get(temp(；。。。}

。。。将其简化为：

byte[]k1=intermediateCipher.get(temp(；if(k1！=null({。。。}

2. 循环中分配的内存太多，因为只为临时操作创建一个新的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);
   }
   

在第二个循环中，可以进行类似的转换。

3. 正如@Thilo在评论中所建议的那样，根据预期的最大大小预先调整地图大小始终是一种很好的做法。它应该是这样的： Map<...> intermediateCipher=new HashMap<...>((int)(1.7d * expectedSize));

4. 回路while (intermediateCipher.size() < Math.pow(2, 20))应简化为 int len=Math.pow(2, 20); for (int i=0;i<len;i++)

更新

5. 如果调用generateDesKey()在每次迭代中都返回相同的结果，则可以在循环之前将其设置为

Answer 2

以下是您可以尝试缩短运行时间的一些方法。

首先，从HashMap切换到TreeMap。当HashMap变得太大时，如2^20，在最坏的情况下，搜索应该从O(1(到O(n(，因为哈希表中的所有槽都充满了大量条目。然而，树映射搜索总是在O(lg n(中运行。

其次，从Map<Integer, Integer>切换到Map<Integer, byte[]>。您只需要将Map键转换为整数；您可以将值保留为字节数组，从而显著减少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);
}
}
}