posted at 2022.4.29 12:50 by Administrator
1976年，Diffie-Hellman首次提出了“公钥密码体制”的思想，随后，Merkle和Hellman利用这种思想，提出了基于背包问题的第一个可实现的公钥加密算法MH(Merkle-Hellman)背包公钥密码算法。两年之后，Shamir利用生成公钥的模乘变换的陷门，在多项式的时间内恢复出来MH背包公钥密码系统的私钥，轻易了破解了MH背包公钥密码系统。为了抵抗这种攻击，Merkle和Hellman 于1981年提出了多级背包公钥密码算法，即反复使用MH变换对超递增序列和一般序列进行迭代得出公钥。MH背包公钥密码算法的核心是密钥的生成和相配套的加密/解密算法。
一、算法描述
MH背包公钥密码系统中公钥序列a1，a2，···，an是由超递增序列通过Merkle-Hellman变换（即MH变换）得到。假设b1，b2，···，bn是超递增序列，其中bi≥Σi-1k=1 bk，i=2，3，···，n。选取模数m>2bn ≥Σi bi 和乘数ω，要求ω与m互素，解同余方程ω-1·ω≡1(mod m)，得到ω-1。然后作MH变换：
ak=(ω·bk)(mod m)，其中k=1,2,···，n
于是由超递增序列b1，b2，···，bn，得到背包序列a1，a2，···，an。超递增序列b1，b2，···，bn作为MH背包公钥密码系统的私钥SK，予以保密；序列a1，a2，···，an作为背包公钥密码系统的公钥PK，予以公开。在核心的密钥对生成之后，就可以用利用相关的加密/解密理论进行加密和解密文档了。
二、具体实现
1、 参数产生
MH背包公钥密码系统的参数就是私钥SK={b1，b2，···，bn}，乘数ω以及模数m，其产生过程如下：
第一步，MH背包公钥密码系统的私钥序列SK={b1，b2，···，bn}，首先由计算机产生一个随机数，然后将随后的b2在b1的基础上加上另外一个正随机数，以后每一项为前面超递增序列总和加上一个正随机数，直到生成n个元素的超递增序列，即为私钥序列SK；
第二步，选取模数m>2bn ≥Σi bi ；
第三步，选取乘数ω，要求ω与m互素，利用欧几里德扩展算法解同余式ω-1·ω≡1(mod m)，求得ω的逆ω-1。
2、 密钥产生
MH背包公钥密码系统的密钥分为公钥PK和私钥SK，私钥序列
的生成是基于计算机随机数的生成，其生成过程如前述，记为SK={b1，b2，···，bn}，然后作MH变换：ak=(ω· bk)(mod m)，其中k=1,2,···，n，其中，即可得到公钥序列，记为PK={a1，a2，···，an}。
3、 加密/解密过程
已知公钥序列a1，a2，···，an，假设二进制转换后消息明文
字符串m=m1m2···mn是n位0和1字符串，其中mi∈{0，1}，经过加密后的密文C=Σi ai·mi，其中{ai}为公钥，i=1，2，···，n。
消息的合法接收者知道私钥SK，即原始的超递增背包序列{bi}，实现解密步骤如下：
第一步，通过同余式计算出ω-1·ω≡1(mod m)，求得ω的逆ω-1。
第二步，用ω-1乘以密文值C后模m。
第三步，用私钥序列SK={bi}，即超递增序列划分求解得到明文。
当然，{ai}从外表上看不再具有超递增背包序列的特性。在MH背包公钥密码系统中，假定已知c=Σi ai·mi ，c为m的密文，由ak≡(ω·bk)(mod m)óakω-1≡bk(mod m)，那么ω-1c=ω-1 a1m1+ω-1 a2m2+··· +ω-1 anmn≡(b1m1+b2m2+···+bnmn)(mod m)求解困难问题即转化为较为容易的超递增序列背包问题。
三、安全性分析
1、低密度子集和攻击。影响陷门背包的安全性的一个重要参数是背包密度，背包密度小于0.9408的陷门背包都容易遭受低密度子集和攻击。如果背包密度大于1，则该系统在实现过程中就会存在解密不唯一的问题。
2、暴力攻击。一种显然的暴力攻击模式是：给定密文C，穷举搜索子集，，直到探出明文为止。这种穷举搜索成功的概率为1/2n。另外一种暴力攻击模式是：给定公钥，穷举搜索，使背包向量为超递增向量，穷举搜索成功的概率为1/10n。
四、算法应用
由于MH背包公钥密码系统生成密钥效率高，加密解密速度快，
因此在大量数据的加密、保存以及传输中，起着非常重要的作用。该算法主要应用在银行数据加密、网络游戏、无线通信数据包的优化调度、冶金行业的动态规划问题、启发式搜索和分布式排样系统等。
五、算法举例
假设待加密的是16位明文序列为mi={0110001001100001}，生成的私钥序列为{10，14，39，68，133，277，548，1104，2196，4390，8789，17570，35140，70290，140578，281158}，乘数ω=5437，模数N=562320，乘数ω关于模数N的逆元ω-1=505333，生成的公钥序列为{54370，76118，212043，369716，160801，381409，167876，379248，130932，250990，550913，496010，429700，351450，129706，270286}，加密后的密文形式1751a2为，输出解密后明文列0110001001100001，程序运行时间总计1ms。
程序运行后，需要设置私钥的长度，然后由计算机的随机生成超递增序列，即为私钥；接着选取合适的模数N以及乘数ω，需要保证gcd(ω,N)=1，同时生成模数ω的逆元ω-1，再由模数N、乘数ω以及超递增序列生成公钥即可，最后利用公私钥分别进行加/解密。流程如下：
开始 =>
输入私钥个数 =>
私钥（超递增序列）生成 =>
模数N、乘数ω、逆元ω-1的生成 =>
公钥（背包序列）生成 =>
加（解）密文档 =>
结束
六、C程序源代码
MH背包公钥密码算法C程序源代码.zip (2.30 kb)
七、效果图
1e008515-301f-4b5a-b435-b3a6a4877e0d|0|.0|96d5b379-7e1d-4dac-a6ba-1e50db561b04
Tags: 程序, 代码, 公钥, 密码, 模, 数据, 算法, 余
IT技术
