MH背包公钥密码算法

posted at 2022.4.29 11:50 by Administrator

1976年,Diffie-Hellman首次提出了“公钥密码体制”的思想,随后,MerkleHellman利用这种思想,提出了基于背包问题的第一个可实现的公钥加密算法MH(Merkle-Hellman)背包公钥密码算法。两年之后,Shamir利用生成公钥的模乘变换的陷门,在多项式的时间内恢复出来MH背包公钥密码系统的私钥,轻易了破解了MH背包公钥密码系统。为了抵抗这种攻击,MerkleHellman 1981年提出了多级背包公钥密码算法,即反复使用MH变换对超递增序列和一般序列进行迭代得出公钥。MH背包公钥密码算法的核心是密钥的生成和相配套的加密/解密算法。

一、算法描述

 MH背包公钥密码系统中公钥序列a1a2,···,an是由超递增序列通过Merkle-Hellman变换(即MH变换)得到。假设b1b2,···,bn是超递增序列,其中bi≥Σi-1k=1 bki=23···n选取模数m>2bn ≥Σi bi 和乘数ω,要求ωm互素,解同余方程ω-1·ω≡1(mod m),得到ω-1。然后作MH变换:

ak=(ω·bk)(mod m)其中k=1,2,···,n

于是由超递增序列b1b2···bn,得到背包序列a1a2···an。超递增序列b1b2···bn作为MH背包公钥密码系统的私钥SK,予以保密;序列a1a2···an作为背包公钥密码系统的公钥PK,予以公开。在核心的密钥对生成之后,就可以用利用相关的加密/解密理论进行加密和解密文档了。

二、具体实现

1、    参数产生

MH背包公钥密码系统的参数就是私钥SK={b1b2···bn},乘ω以及模数m,其产生过程如下:

第一步,MH背包公钥密码系统的私钥序列SK={b1b2···bn},首先由计算机产生一个随机数,然后将随后的b2b1的基础上加上另外一个正随机数,以后每一项为前面超递增序列总和加上一个正随机数,直到生成n个元素的超递增序列,即为私钥序列SK

第二步,选取模数m>2bn ≥Σi bi  

第三步,选取乘数ω,要求ωm互素,利用欧几里德扩展算法解同余式ω-1·ω≡1(mod m),求得ω的逆ω-1

2、    密钥产生

MH背包公钥密码系统的密钥分为公钥PK和私钥SK,私钥序列

的生成是基于计算机随机数的生成,其生成过程如前述,记为SK={b1b2,···,bn},然后作MH变换:ak=(ω· bk)(mod m),其中k=1,2,···,n,其中,即可得到公钥序列,记为PK={a1a2,···,an}

3、    加密/解密过程

已知公钥序列a1a2···an,假设二进制转换后消息明文

字符串m=m1m2···mnn01字符串,其中mi{01},经过加密后的密文C=Σai·mi,其中{ai}为公钥,i=12,···,n

消息的合法接收者知道私钥SK,即原始的超递增背包序列{bi},实现解密步骤如下:

第一步,通过同余式计算出ω-1·ω≡1(mod m),求得ω的逆ω-1

第二步,用ω-1乘以密文值C后模m

第三步,用私钥序列SK={bi},即超递增序列划分求解得到明文。

当然,{ai}从外表上看不再具有超递增背包序列的特性。在MH背包公钥密码系统中,假定已知c=Σai·mi cm的密文ak≡(ω·bk)(mod m)óakω-1bk(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},生成的私钥序列为{101439681332775481104219643908789175703514070290140578281158}乘数ω=5437模数N=562320乘数ω关于模数N的逆元ω-1=505333生成的公钥序列为{5437076118212043369716160801381409167876379248130932250990550913496010429700351450129706270286}加密后的密文形式1751a2为,输出解密后明文0110001001100001程序运行时间总计1ms

程序运行后,需要设置私钥的长度,然后由计算机的随机生成超递增序列,即为私钥;接着选取合适的模N以及乘数ω,需要保证gcd(ω,N)=1,同时生成模数ω的逆元ω-1,再由模数N、乘数ω以及超递增序列生成公钥即可,最后利用公私钥分别进行加/解密。流程如下:

开始 =>

输入私钥个数 =>

私钥(超递增序列)生成 =>

模数N、乘数ω、逆元ω-1的生成  =>

公钥(背包序列)生成 =>

加(解)密文档 =>

结束

六、C程序源

MH背包公钥密码算法C程序源代码.zip (2.30 kb) 

七、效果 

 

Tags: , , , , , , ,

IT技术

Add comment

  Country flag

biuquote
  • Comment
  • Preview
Loading