一、引入背包問題
超市裡有N件物品,第一件物品的重量是m1,價值是v1,第二件物品的重量是m2,價值是v2…..第N件物品的重量是mN,價值是vN。現在有一個背包Bag,最多能裝下的重量為M,請問在不超過背包容量的前提下,怎樣使得裝在背包裡的商品價值總和最大。
背包加密算法是非對稱密鑰算法的一種。
二、背包加密過程
(一) 生成公鑰和私鑰
i. 構造超遞增背包
要求：前面元素的和總是小于等于第三個元素。
我們取一個簡單的超遞增背包：{2,5,7,13}
該背包就是私鑰
ii. 擷取乘數e和模數m
乘數和模數用于計算公鑰中的每個元素。乘數e和模數m要滿足：
1)、e和m互質;
2)、m大于私鑰背包所有元素之和.
我們令 e = 3 , m = 50
求e對于m的模反元素d：e*d≡1(mod m)
e*d / m = k 餘 1
這是一個二進制一次方程
3d = 50k +1;
使用窮舉法發現,k=1時，d = 17
故(d,k) = (17,1)
iii. 利用私鑰,乘數e和模數m生成公鑰：k = e * I mod m
k是公鑰中的元素,i是與k對應的私鑰中的元素
k1 = e * i1 mod m = 3 * 2 mod 50 = 6
k2,k3,k4也用同樣方法計算
最後得出公鑰為：{6,15,21,39}
(二) 加密
背包算法加密和解密都涉及到進制的轉換。一段明文必須先轉成雙方事先約定好的進制(例如常見的二進制,八進制和不常見的七進制等),過長的資訊必須分割成與密鑰長度相等資訊片段,然後分段加密。
假設我們的明文是mc = 18 , 使用二進制進行加密
mc用二進制表示 ： 00010010
密鑰長度為4,是以,對明文的二進制進行分段
mc1 = 0001, mc2 = 0010
加密：明文和密文和公鑰的關系是
二進制片段的每一位,都與公鑰數字對齊,如果二進制位為1,則用公鑰數字對應位置的數字乘以1,如果二進制位為0,則公鑰數字對應位置數字乘以0.最後将所得結果相加,就是密文片段的密碼。
公鑰數組：{6,15,21,39}
mc1 = 0 0 0 1
mc1= 6*0+15*0+21*0+39*0 = 39
同理
mc2= 21
是以mc的密文c 就是{39 , 21}
(三) 解密
密文明文和私鑰的關系為：c*d mod m = mc
mc1 = 39 * 17 % 50 = 13
mc2 = 21 * 17 % 50 = 7
将解密後的明文片段分解成幾個加數相加的形式：這幾個加數必須都包含在私鑰中
(由于本例的特殊情況,明文片段本身就包含在私鑰數組)。
将明文片段的所有加數按從小到大排序,然後對應私鑰轉換進制。就是如果私鑰背包中的某項元素位于mc1片段的加數内，則該位為1,反之為0
私鑰: {2,5,7,13}
mc1= 0 0 0 1 由于mc1的加數隻有13一個，是以隻有13這位為1
mc2= 0 0 1 0
最後拼接二進制：
mc的二進制就是： 00010010
轉換成十進制就是： 16 + 2 = 18。
三、關于密文解密成明文
關于密文解密成明文過程中,即：已經求得mc = 13時候,使用13和私鑰得到加密時傳入的13的二進制形式的數字,用到了如下思路：
例如：一個私鑰 prikey = {2,3,6,10 }和解密後得到的解密後密文 = 8,可以這樣計算
1. 設一個長度與私鑰長度相等的數組arr[]令k = mc ,用k和私鑰最後一位10比較：k = 8 < 10 ,
：在arr[]最後一位寫入0 ,表示mc的和數裡沒有10
2. 然後用k和私鑰中的倒數第二位6進行比較：k = 10 > 6 :
1) ：在arr[]倒數第二位寫入1,表示在mc的和數裡有6
2) ：重新給k指派,k = k - 6 = 8 – 6 = 2
3. 使用k和私鑰的倒數第三位比較：k = 2 < 3
在arr[]的倒數第三位寫入0,表示mc的和數裡沒有3
4. 使用k和私鑰的倒數第四位比較：k =2
1) ：在arr[]的倒數第四位裡寫入1,表示mc的和數裡有2
2) 重新給k指派,k = k – 2 = 2 – 2 = 0 結束
這時看arr[]中的資料為：1010，這個才是真正的明文。即：明文m = 5
package com.joe.main;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
/**
* @Description:超遞增加法背包加密Demo, 匆忙寫成,加密内容不能超過Integer.MAX_VALUE。隻能加密數字.
* @company XXX通信技術（北京）有限公司
* @author Joe
* @date 2013-9-10 下午4:47:36
*/
public class BagEncript {
private static int[] privateKeys;// 私鑰數組
private static int sn; // 私鑰數組所有元素和
private static int[] publicKeys;// 公鑰數組
private static int m = 1; // 模數m
private static int e = 1; // 乘數e
private static int d = 1; // e對m的模反元素d,滿足e*d % m == 1恒成立
private static String lastEightBinaryString; // 明文二進制數的後八位
// ,明文的二進制每一位都和密鑰數組是一一對應的,是以必須将過長的明文分割成與密鑰等長的子數組
private static char[] charLBS;// 明文二進制數的後八位 對應的字元數組
private static List<Integer> listOfCipherPieces; // 存放密文片段的集合
private static List<char[]> listOfCharLBS; // listOfCharLBS用于存放明文片段的二進制數組
private static String resultPlaintext = "";// 解密密文後得到的二進制結果
public static void main(String[] args) {
// 1、生成超遞增背包私鑰
createPriKey();
// 2、取乘數e和模數m,他們的模反 d
getEAndM();
// 3、生成公鑰
createPubKey();
// 4、加密,解密
encript(Integer.MAX_VALUE);
}
// 生成私鑰4位超遞增背包
private static void createPriKey() {
privateKeys = new int[8];
int num1 = 1;
int num2 = 1;
do {
num1 = (int) (Math.random() * 5);
num2 = (int) (Math.random() * 5);
} while (num1 == num2 || num1 == 0 || num2 == 0);
if (num1 > num2) {
int temp = num1;
num1 = num2;
num2 = temp;
}
privateKeys[0] = num1;
privateKeys[1] = num2;
int num3 = 1;
for (int i = 2; i < privateKeys.length; i++) {
do {
num3 = (int) (Math.random() * Math.pow(3, i));
} while (num3 <= (privateKeys[i - 2] + privateKeys[i - 1]));
privateKeys[i] = num3;
}
for (int i = 0; i < privateKeys.length; i++) {
sn += privateKeys[i];
System.out.println("privateKeys[" + i + "] = " + privateKeys[i]);
}
}
// 2、取乘數e和模數m
private static void getEAndM() {
do {
m = (int) (Math.random() * 10000);
} while (sn >= m);
do {
e = (int) (Math.random() * 10000);
} while (gcd(e, m) != 1 || e > 10000);
loop: for (int i = 0;; i++) {
if ((i * m + 1) % e == 0) {
d = (i * m + 1) / e;
break loop;
}
}
System.out.println("m = " + m + " , e = " + e + " ,d = " + d);
}
// 3、生成公鑰
private static void createPubKey() {
publicKeys = new int[privateKeys.length];
for (int i = 0; i < publicKeys.length; i++) {
publicKeys[i] = (e * privateKeys[i]) % m;
System.out.println("publicKeys[" + i + "] = " + publicKeys[i]);
}
}
// 4、加密
private static void encript(int msg) {
System.out.println("要加密的明文 ： " + msg);
// 初始化listOfCharLBS,用于存放明文片段的二進制數組
listOfCharLBS = new ArrayList<char[]>();
// 初始化 listOfCipherPieces,是明文片段加密後對應的密文片段的存放數組
listOfCipherPieces = new ArrayList<Integer>();
String binaryString = Integer.toBinaryString(msg);
// 判斷二進制數組是否是8位或8的整數倍
int leftZero = binaryString.length() % 8;
// 将不足8位或8位整數倍的左邊二進制位補0
for (int i = 0; i < 8 - leftZero; i++) {
binaryString = "0" + binaryString;
}
System.out.println("明文的二進制數組 ： " + binaryString);
// 計算明文二進制字元串按照8位一組可以分機組
int k = binaryString.length() / 8;
for (int i = 0; i < k; i++) {
// 從二進制數組的右邊開始向左,每8位一組
lastEightBinaryString = binaryString.substring(
binaryString.length() - 8, binaryString.length());
// 将二進制數組重新指派,新數組中隻要原數組的前 n - 8位(其中n代表原數組長度)
binaryString = binaryString.substring(0, binaryString.length() - 8);
// 将二進制片段存入list中
charLBS = lastEightBinaryString.toCharArray();
listOfCharLBS.add(0, charLBS);
}
System.out.println("binaryString.length() = " + binaryString.length());
System.out.println("binaryString = " + binaryString);
for (int j = 0; j < listOfCharLBS.size(); j++) {
char[] eightBinary = (char[]) listOfCharLBS.get(j);
System.out.println("listOfCharLBS中的第" + j + "個char 數組 = "
+ String.copyValueOf(eightBinary));
int cipherPart = 0; // 密文片段
// 加密過程 每個二進制位上的數乘以公鑰對應位置的元素,之後求和,就是目前明文片段對應的密文
for (int i = 0; i < eightBinary.length; i++) {
cipherPart += publicKeys[i]
* Integer.parseInt(eightBinary[i] + "");
}
// 密文片段放入密文數組
listOfCipherPieces.add(0, cipherPart);
}
// 輸出檢視密文數組
for (int i = 0; i < listOfCipherPieces.size(); i++) {
Integer cipherPart = listOfCipherPieces.get(i);
System.out.println("密文片段 " + i + " = " + cipherPart);
}
// 解密
System.out.println("密文數組長度 = " + listOfCipherPieces.size());
for (int i = 0; i < listOfCipherPieces.size(); i++) {
int cipherPart = (Integer) listOfCipherPieces.get(i);
// 解密方法
decript(cipherPart);
}
// 列印解密後的明文
System.out.println("解密後的明文二進制數組 ： " + resultPlaintext);
// for (int i = 0; i < listOfPlaintext.size(); i++) {
// System.out.print(listOfPlaintext.get(i));
// }
// 将二進制結果轉成10進制輸出
getPlainText();
resultPlaintext = null;
}
// 解密
public static void decript(int cipherPart) {
int plainText = cipherPart * d % m; // 密文片段解密後得到明文片段
int cha = plainText;
for (int i = privateKeys.length - 1; i >= 0; i--) {
if (cha >= privateKeys[i]) {
// listOfPlaintext.add(0, 1);
resultPlaintext = "1" + resultPlaintext;
cha = cha - privateKeys[i];
} else {
// listOfPlaintext.add(0, 0);
resultPlaintext = "0" + resultPlaintext;
}
}
}
// 将二進制結果轉成10進制輸出
public static void getPlainText() {
BigInteger bi = new BigInteger(resultPlaintext, 2);
System.out.println(bi.toString(10));
}
// 求最大公約數
public static int gcd(int a, int b) {
int gcd;
if (b == 0)
gcd = a;
else
gcd = gcd(b, a % b);
return gcd;
}
}
點選此處下載下傳免積分Demo
完
![MyBatis逆向工程Mapper方法不全原因[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)