密碼學——構建一個簡化版的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);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/187678.html
標籤：其他