密码学——构建一个简化版的PRESENT算法并实现中间相遇攻击

场景

本文的目标是实现中间相遇攻击，目标算法是一个是简化版的PRESENT算法。

PRESENT是一个07年的算法，是一个真实可用的很有名的算法，用在很多轻量级的环境中。

目标算法是简化版的PRESENT算法，在以下文章中被提出。

这个简化版的PRESENT算法大小是可变的，本文中构建的是一个16bits版本的简化PRESENT算法，master key为16bits和16轮。

仿照2DES，把key增加到32bits，也就是对明文用k1和k2进行两次加密。

然后用中间相遇攻击去恢复这个32bits的key。

本文中给出以下三组明文密文，已知这三组明文密文可以确定出唯一的k1和k2。 此外，文章中给出的轮密钥生成算法比较复杂，本文中简化了轮密钥的生成算法。

知识点

本文涉及的知识点是中间相遇攻击破解2DES算法

DES算法的key是56bits，设计之初人们并没有觉得56bits是一个很脆弱的环节。不过随着算力的不断提升，56bits可以在很短的时间被暴力破解。 但DES被用在了很多地方，一下次把DES全部换掉比较困难。

为了在不更换算法的前提下加长密钥，当时有一个设计是2DES，即加密两次，每一次使用不同的密钥k1和k2，两个56bits的密钥组合成一个112bits的主密钥。

这个设计很不安全，经典的中间相遇攻击可以将其的暴力破解的复杂度降低到接近只用一次DES加密的程度。

代码实现

构建简化版PRESENT算法

算法的基本设计如图所示。 其中输入的plaintext明文，输出的ciphertext密文，key为16bits和16轮。 实现PRESENT算法主要需要三个方法，轮密钥加密，sBoxLayer加密和pLayer加密。

轮密钥加密

文章中的轮密钥加密算法比较复杂，题目中简化了轮密钥的加密，只需要左移7位。

/** * 字符串循环左移7位 * @param ki 输入的字符串 * @return 输出循环左移7位后的字符串 */ public static String circle(String ki) { int length = ki.length(); String kii=""; for(int i=7 ;i<length ;i++){ //先输出y-（length1-1）字符 kii += ki.charAt(i); } for(int i=0 ;i<7 ;i++){ //后输出0-t字符 kii += ki.charAt(i); } /*System.out.println("circle:" + kii);*/ return kii; }

sBoxLayer加密

sBoxLayer加密是将二进制明文转换为十六进制，然后根据给出的表格进行替换，从而得到加密后的密文。

/** * sBoxLayer加密 * 转换成十六进制，然后根据替换表替换 * @param m 输入二进制字符串 * @return 输出sBoxLayer加密后的二进制字符串 */ public static String sBoxLayer(String m) { int DEC = Integer.parseUnsignedInt(m,2); //二进制字符串转换为int String HEX = Integer.toHexString(DEC); //int转换成十六进制字符串 /*if(HEX.length() < 4) { int j = HEX.length(); for(int i = 0; i < (4 - j); i++) { HEX = "0" + HEX; } }*/ /*System.out.println("HEX:" + HEX);*/ HEX = highZero(HEX, 4); //高位补零 String c = ""; for(int i = 0; i < 4; i++) { switch (HEX.charAt(i)) { case '0' : c += "1100"; break; case '1' : c += "0101"; break; case '2' : c += "0110"; break; case '3' : c += "1011"; break; case '4' : c += "1001"; break; case '5' : c += "0000"; break; case '6' : c += "1010"; break; case '7' : c += "1101"; break; case '8' : c += "0011"; break; case '9' : c += "1110"; break; case 'a' : c += "1111"; break; case 'b' : c += "1000"; break; case 'c' : c += "0100"; break; case 'd' : c += "0111"; break; case 'e' : c += "0001"; break; case 'f' : c += "0010"; break; } } return c; }

pLayer加密

pLayer加密是将二进制明文根据设定好的规则进行位替换，得到密文。

/** * player加密 * 根据规则进行位替换，具体不好描述，但规则很简单 * @param m 输入字符串 * @return 输出pLayer加密之后的字符串 */ public static String pLayer(String m) { String c = ""; for(int i = 0; i < 4; i++) { c += m.charAt(i); c += m.charAt(i + 4); c += m.charAt(i + 8); c += m.charAt(i + 12); } /*System.out.println("pLayer:" + c);*/ return c; }

PRESENT加密解密算法

加密

/** * 作业版本的PRESENT加密 * 16轮加密 * 前15轮，m和k异或，然后经过sBoxLayer和pLayer加密，k循环左移7位 * 第16轮，m和k异或 * @param m 明文 * @param k 秘钥 * @return 输出密文 */ public static String DES(String m, String k) { for(int i = 0; i < 15; i++) { m = twoStrXOR(m, k); //异或 k = circle(k); //左移7位 m = sBoxLayer(m); m = pLayer(m); } m = twoStrXOR(m, k); m = highZero(m, 16); return m; }

解密

/** * 作业版本的PRESENT解密 * 和DES反向 * 第一轮，c和k15异或，然后经过pLayer和sBoxLayer解密 * 第二轮，c和k14异或，然后经过pLayer和sBoxLayer解密 * 重复 * 第十六轮，c和k0异或 * @param c 秘闻 * @param k 秘钥 * @return 输出明文 */ public static String reDES(String c, String k) { ArrayList<String> list = new ArrayList<>(); for(int i = 0; i < 16; i++) { list.add(k); k = circle(k); //左移7位 } for(int i = 15; i > 0; i--) { c = twoStrXOR(c, list.get(i)); //异或 c = pLayer(c); c = reSBoxLayer(c); } c = twoStrXOR(c, list.get(0)); c = highZero(c, 16); return c; }

使用中间相遇攻击去攻击2PRESENT

所谓的2PRESENT就是仿照2DES，对明文用PRESENT算法和k1加密，然后对得到的中间状态用PRESENT算法和k2加密，得到密文。

中间相遇攻击就是先穷举所有的k1对明文进行加密，将得出的所有的中间状态全部存在表里， 然后穷举k2对密文进行解密，每一个k2解密密文的结果都拿去表中查，如果k2解密的结果和表中某一个k1加密的结果相同，则意味着k1和k2是一对可能的密钥。

题目中给出了三组明文密文，已知这三组明文密文是可以确定出唯一的k1和k2。

代码实现思路：

一开始想用map去存中间状态和k1，中间状态作为key值，k1作为value值。然后用k2解密密文的结果去map中碰撞key值，碰撞成功则将对应的value值(即k1)取出，此时的k1和k2就是一对可能的密钥。

但实验后发现第二组明文密文可以找出正确的k1和k2，第一组和第三组则失败了，原因是不同的k1加密密文得出的中间状态可能会相同，此时就会出现重复的中间状态，从而覆盖map中的存放的键值对。

因为需要碰撞的是中间状态，所以中间状态必须作为map的key值，而key值不能重复。所以我在存入键值对前先判断map中是否有相同的key值，没有则存入，有则存入一个辅助list。

碰撞的时候如果碰撞成功，除了取出map中存放的k1，还需要遍历辅助list取出可能存在的其他k1。

/** * 中间相遇攻击 * 先用k1加密m，产生中间密文，O(n) = 2的16次方 * tmpMap存放中间密文，中间密文为key，k1为value * 不同的k1加密密文产生的中间密文可能会重复 * 为了避免覆盖，每次放入键值对时先判断tmpMap中有无的中间密文，即对应的key * 无则存入，有则将中间密文和k1存入tmpList * * 再用k2解密c，产生中间密文，O(n) = 2的16次方 * 中间相遇攻击就是：让解密产生的中间密文和加密产生的中间密文碰撞 * 碰撞的时候先判断tmpMap中有无中间密文，即对应的key * 无则碰撞失败，有则碰撞成功 * * 使用list存放最终的k1,k2(k1和k2的组合是唯一的，但k1有可能重复，k2也有可能重复) * 碰撞成功时，将tmpMap中的键值对取出，其中的value为k1 * 将k1和此时的k2存放进list * 然后再遍历tmpList，继续碰撞 * 碰撞成功将k1和k2存放进list * * 其他思路： * IdentityHashMap,失败了，碰撞不到，因为使用的是==来判断key值 * MultiMap,没有试，应该可以 * * @param m 输入要攻击的明文 * @param c 输入要攻击的密文 * @return 返回ArrayList<K> list,存放所有可能的k1和k2的组合 */ public static ArrayList<K> attack(String m, String c) { //map的key值不能重复，而不同k产生的中间密文可能相同，存在覆盖的可能 HashMap<String, String> tmpMap = new HashMap<>(); ArrayList<K> tmpList = new ArrayList<>(); ArrayList<K> list = new ArrayList<>(); for(int i = 0; i < 65536; i++) { String k1 = DECtoBIN(i); /*tmpMap.put(DES(m, k1), k1);*/ String mid = DES(m, k1); if(tmpMap.containsKey(mid)) { tmpList.add(new K(mid, k1)); }else { tmpMap.put(mid, k1); } } for(int i = 0; i < 65536; i++) { String k2 = DECtoBIN(i); //中间相遇 String mid = reDES(c, k2); if(tmpMap.containsKey(mid)) { String k1 = tmpMap.get(mid); list.add(new K(k1, k2)); for(K it: tmpList) { if(it.s1.equals(mid)) { list.add(new K(it.s2, k2)); } } } } return list; /*IdentityHashMap可以存放相同的key值， 但它判断key值是否相等时，用的是==，而不是equals()， 导致tmpMap.containsKey(mid)语句无法达到想要的效果,即碰撞不到*/ /*IdentityHashMap<String, String> tmpMap = new IdentityHashMap<>(); HashMap<String, String> finalMap = new HashMap<>(); for(int i = 0; i < 65536; i++) { String k1 = DECtoBIN(i); String mid = DES(m, k1); tmpMap.put(mid, k1); } for(int i = 0; i < 65536; i++) { String k2 = DECtoBIN(i); //中间相遇 String mid = reDES(c, k2); if(tmpMap.containsKey(mid)) { for(Map.Entry<String, String> entry : tmpMap.entrySet()) { if(entry.getKey().equals(mid)) { finalMap.put(entry.getValue(), k2); } } } } return finalMap;*/ }

其他思路：

IdentifyMap，可以存放相同的key值，因为其判断key值相等的方法是==，而不是equals()。但是实现的时候失败了，因为其判断key值使用的是==，所以导致containsKey()无法碰撞中间状态。还未找到解决办法。

MultiMap，应该可以，还没试。

取交集

题目中给了三组明文密文，已知可以确定唯一的k1和k2。 对每一组明文密文都进行中间相遇攻击，分别得到可能的k1和k2集合，取交集即可得出唯一的k1和k2。

/** * 从3个list中找到一样的K * 已知3个list的交集为唯一的K * 思路1：使用retainAll方法来取交集，失败了，已解决 * * 原因： * 对于java内置类型，可以直接调用，自定义数据类型需要重写实体类的equals() * 因为retainAll内部通过集合contains方法，该方法用equals来判断是否相等 * * 思路2：使用for循环嵌套 * * @param list1 * @param list2 * @param list3 * @return 输出唯一的K(题目中已知) */ public static K findTheOne(ArrayList<K> list1, ArrayList<K> list2, ArrayList<K> list3) { /*for(K it1: list1) { for(K it2: list2) { if(it1.s1.equals(it2.s1) && it1.s2.equals(it2.s2)) { for(K it3: list3) { if(it1.s1.equals(it3.s1) && it1.s2.equals(it3.s2)) { K k = new K(it3.s1, it3.s2); return k; } } } } } System.out.println("未找到k1,k2"); return null;*/ //retainAll取交集，要重写一下K中的equals list1.retainAll(list2); list1.retainAll(list3); return list1.get(0); }