背包公钥密码系统

语录：在做任何一件事的时候，总会遇到点麻烦；当把这件事做完后，回过头来再想想这个过程，解决这件事的具体步骤和过程中遇到的问题，然后用文字把这些问题给描述出来，可能会对自己有所收获。

------------------------------------------------------------------------------

最近在学背包公钥密码，由于好奇，自己尝试的去实现一个背包公钥密码系统。对这过程中遇到的问题,在下文中做个小结！

----------------------------------------------------------------------------------------------------------------------------

1.什么是MH背包问题？

描述：

在1978年，Merkle与Hellman提出来的。

大致的思想是这样的：

现在有一堆重量不同的物品，从中任意选取n个物品放入一背包里；公开背包里物品的总重量和这一堆物品；但是所选的物品种类是不公开的。

2.MH背包算法

描述：

Merkle与Hellman合作设计了使用背包问题实现信息加密的方法。

大致的思想是这样的：

假如现在甲想干这样一件事，凡是给甲发消息，则这条消息一定要加密；

为实现这个目的，甲必须有专用密钥，而这个密钥是通过背包问题产生的；有这个专用密钥产生一个公共密钥；然后凡是给甲发消息，要先用这个公共密钥加密，然后甲接收消息用专用密钥解密；

为实现这个过程，我们需要做的步骤：

1) 产生密钥

i)  确定密钥序列的长度n (也可以自己固定长度)；

     ii)  随机产生秘密密钥序列B =（b1,b2,…,bn）

         (其中：B满足bj > b1+...+bj1,j>1),

                  N, W(其中：满足N>b1+...+bn且gcd(W,N)=1;）；

     iii) 生成公开密钥序列A(a1,a2,…,an)

        （其中ai满足ai = bi*W(modN),n>=i>=1)； 

2) 加密

     目的：乙欲将明文M = (m1,m2,…,mn)传送给甲；

     具体做法：

     乙根据甲的公开密钥A(a1,a2,…,an)，并计算出对应得S(S=a1*m1+...+an*mn)，并将S传给甲；

3)  解密

 

1)甲收到S后，利用秘密密钥将S转换成S'；

     (其中：S' = SW'(mod N) = (b1*m1+...+bn*mn)(mod N),(W'是W的逆元) )；

2)利用贪心算法计算M序列；

 S' = MX'(X'是X的转置矩阵)

 

for(int i = n; i > 0; i--)
{
     if(S' >= b[i]){
        S' -= b[i];
        x[i] = 1;
     }else{
        x[i] = 0;
    }
}

  

3，实现过程中遇到的问题

1）构建超递增序列B

 

对于i<= n, 满足

Bi = ∑Bj+ (rand()%5+1)   （1<=j<=i）；

nInt=∑Bj+ (rand()%5+1)   （1<=j<=n）；

2）求解W的逆元

逆元W'应满足的条件：W' * W % n == 1，暂时没有好方法！

3）求解S’

S’= S*W(mod N)

4） 我现在的程序暂时一次性最多只能传29个字符；以后可以改善；