背包公钥密码系统
语录:在做任何一件事的时候,总会遇到点麻烦;当把这件事做完后,回过头来再想想这个过程,解决这件事的具体步骤和过程中遇到的问题,然后用文字把这些问题给描述出来,可能会对自己有所收获。
------------------------------------------------------------------------------
最近在学背包公钥密码,由于好奇,自己尝试的去实现一个背包公钥密码系统。对这过程中遇到的问题,在下文中做个小结!
----------------------------------------------------------------------------------------------------------------------------
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个字符;以后可以改善;