背包密码体制是基于“子集之和问题”的难解性，开发出来的公钥密码体制。

在解释这个加密算法之前，先解释下，超递增整数集：

通俗来说，当一个有序集合的每一个整数都大于他们前面的整数之和，这个集合就是超递增整数集。

比如：有序集{3，5,11,20,41,81,167,339}就是超递增整数集。

另一个需要了解的知识就是：逆元，逆元的解释以及求法请戳下面链接：

加解密代码为：

package MerkleHellman;

import java.awt.print.Printable;

import java.util.MissingFormatWidthException;

import java.util.Scanner;

public class MHDemo {

public static int MHEncrypto(String binString, int len, int a, int p) {

//binString为要加密的二进制字符串，len为字符串长度，a为小于素数p的整数,p为素数

Scanner scanner = new Scanner(System.in);

int []dzcj = new int[len];

//输入超递增集

System.out.println("请输入超递增集");

for(int i = 0; i < len; i ++) {

dzcj[i] = scanner.nextInt();

}

int encryptoValue = 0;

int []t = new int[100];

for(int i = 0; i < len; i ++) {

t[i] = a*dzcj[i] % p; //构造加密集t[i]

}

char ch[] = binString.toCharArray();

for(int i =0; i < ch.length; i++) {

if(ch[i] == '1') {

encryptoValue += t[i];

}

}

return encryptoValue; //返回加密的密文

}

public static void MHDecrypto(int encryptoValue, int len, int a, int p) {

Scanner scanner = new Scanner(System.in);

int []dzcj = new int[len];

//输入超递增集

System.out.println("请输入超递增集");

for(int i = 0; i < len; i ++) {

dzcj[i] = scanner.nextInt();

}

int decryptovalue[] = new int[len];

for(int i = 0; i < len; i++) {

decryptovalue[i] = 0;

}

int mid = (qiuNiYuan(a, p) * encryptoValue) % p;

int lun = len-1;

while(lun >= 0) {

if((mid - dzcj[lun]) >= 0) {

decryptovalue[lun] = 1;

mid = mid - dzcj[lun];

lun--;

}else{

lun--;

}

}

System.out.print("解密后的密文为");

for(int i = 0; i < len; i++) {

System.out.print(decryptovalue[i]);

}

}

public static int qiuNiYuan(int value, int p) {

//求逆元

int niyuan = 1;

while(true) {

int flag = (value * niyuan - 1) % p;

if(flag == 0) {

return niyuan;

}

niyuan ++;

}

}

public static void main(String[] args) {

String binString = "10011101";

int encoyptovalue = MHEncrypto(binString, 8, 223,701);

System.out.println("加密后的密文为" + encoyptovalue);

MHDecrypto(encoyptovalue, 8, 223,701);

}

public static void myPrint(Object obj) {

System.out.println(obj);

}

}

超递增集，整数a以及p为加解密的密钥。

输入的超递增整数集为：{3，5,11,20,41,81,167,339}

则运行结果为：加密后的密文为2081

解密后的明文为：10011101

本人小白，如果有大佬发现错误，请指出，感激不尽。