从背包问题看如何构造公钥密码体制，含简单例子讲解

从背包问题看如何构造公钥密码体制，含简单例子讲解

通过一个简单的例子来举例说明下，比如A等于（43,129,215,473,903,302,561,1165,697,1523），而s的值是3231 ，因为3231等于129加上473加上903加上561加上1165 ，所以从A这个集合当中能够找出来的满足相应要求的数分别是129、473、903、561、|1165 。根据背包问题构造明文变化的公钥密码体制，同样是要构造一个单向函数f，把x（1≤x≤2n - 1）写成长度为n的二元表示，像0…001、0…010、0…011、…、1…111，f(x)被定义为A中所有ai的和，这里x的二元表示的第i位要是1，也就是，f(1)=f(0…001)=an，f(2)=f(0…010)=an - 1，f(3)=f(0…011)=an - 1 + an，…，f(2n - 1)=f(1…111)=a1 + a2 + … + an，运用向量乘，有f(x)=A·Bx，其Bx是把x的二元表示写成的列向量。简例之中，A等于（43，129，215，473，903，302，561，1165，697，1523），在上例情形下，f(364)等于f()，其值为129加上473加上903加上561加上1165，结果是3231，与之类似地情形时，能够求出：f(609)等于2942，f(686)等于3584，f(32)等于903，f(46)等于3326，f(128)等于215，f(261)等于2817，f(44)等于2629，f(648)等于819。32等于28等于，依据f的定义能够看出，已知x的情况下很容易去求f(x)，然而已知f(x)去求x实际上就是要解决背包问题。密码体制进行举例，例4.10中，A等于(1,3,5,11,21,44,87,175,349,701)是一个超递增背包向量，选取k等于1590，t等于43，gcd(43,1590)等于1，由此得到B等于(43,129,215,473,903,302,561,1165,697,1523)。先对t减1等于37这条信息进行如下加密操作：将43与473相加，再加上903，接着加上1523，得出结果为2942。然后对2942进行如下解密操作：用37乘以2942，得到结果734。通过解超递增背包，最终得出网络工程系。背包体制以及Rabin背包公钥密码算法是由某人提出的，它是一个基于组合数学中背包问题的公钥密码系统。这个背包系统被称作MH背包问题。背包问题的具体情况是这样的：已知存在n个物品，它们各自的重量分别是a1、a2等一直到an。现在有一个重量为b的背包，里面装有某些物品，那么要问装的究竟是哪些物品呢？就是要去求xi等于0或者1，其中i等于1,2,…,n，使得能够满足：算法复杂性理论已然证实：背包问题归属于NP完备类，也就是NP类问题里难度最为大的那一类，求解这一类型的问题迄今还不存在有效的算法。所以呢，要是打算对NP问题施以求解，从理论上来说仅仅能够采用穷举搜索，那么这样一来就需要针对2n之中所有的可能情形展开穷举搜索(为何会这样呢？)，而这实际上是根本不可能达成的。以n等于100作为例子：2的100次方等于1.27乘以10的30次方，用每秒能够搜索10的7次方种方案的超高速计算机去进行穷举，一年仅仅能够完成3.1536乘以10的14次方次，要是完成全部的穷举那就需要4.02乘以10的15次方（年），这明显是不可能完成的。背包公钥密码算法需要留意的是，并非所有的背包问题都不存在有效算法来求解。要是序列a1，a2，…，an满足条件：，i等于2，3，…，n ，。

在其成立之际，存在着多项式的求解办法 。像这般的序列被称作超递增序列 。举例来说，像那种1,3,6,13,27,52 的序列属于超递增序列 ，然而那个1,3,4,9,15,25 序列却并非如此 。超递增背包问题的答案是比较容易寻觅到的 。把总质量拿来跟序列里最大的那个数去做比较 ，要是总质量小于这个数 ，那么它就不在背包之中 ；要是总质量大于这个数 ，那么它就在背包里头 ，运用背包质量减去这个数 ，转而考查序列下一个最大的数 ，接着重复进行此操作一直到结束情况 ，要是总质量变成了零 ，那么就存在着一个解 ，不然就是无解 。超递增背包示例：来考查一个总质量是70kg的背包，质量序列如下：2, 3, 6, 13, 27, 52 。解答如下：(1)最大的质量是52kg，它小于70kg，故而52kg在背包之中。(2)用70kg减去52kg后剩余18kg，下一个质量27kg比18kg大，所以27kg不在背包里面。(3)再下一个质量13kg小于18kg，因此13kg在背包当中。(4)从18kg里减去13kg后剩下5kg，紧接着下一个质量6kg比5kg大，故而6kg不在背包当中，(5)持续这个过程会得出2kg和3kg都在背包里。所以，我们所得到的解是。超递增背包进行举例，超递增背包转变为MH背包，MH背包公钥系统所选的背包序列是经由超递增序列开展以下变换而获得的。假设有b1,b2,…,bn是超递增序列，选定k2bn，挑出t且k与t互素，t-1是w(modk)的逆 。通过进行变换，使得ak等于tbk对k取模，其中k取值为1,2,...,n。这样一来，便得到了一个序列，这个序列是a1,a2,...,an。而这个序列就是MH背包，从其外表来看，已经不再具备超递增的特性了。MH背包公钥密码系统是以这样的序列{ai}作为公钥的。已知1,3,5,13,26,65,120,250是超递增序列。取1加上3加上5加上13加上26加上65加上120加上250等于483中的k等于501，t等于251，那么t减去1等于2乘以a1，这相当于251乘以1，又相当于251乘以3，还相当于251乘以5，也相当于251乘以13，同样相当于251乘以26，并且相当于251乘以65，再者相当于251乘以120，同时相当于251乘以250，其结果为(251,252,253,257,13,283,60,125)，将此作为公钥予以公布。背包加密体制举例(1)，对于明文m把它加密从而得到密文，那就是a1加上a4加上a6等于251加上257加上283等于791 ，接收方收到密文791之后，用它乘以以t - 1去求模k得791乘以，这是要解超递增序列背包问题，即d1加上3倍d2加上5倍d3加上13倍d4加上26倍d5加上65倍d6加上120倍d7加上250倍d8等于79 ，所以d1等于d4等于d6等于1 ，d2等于d3等于d5等于d7等于d 8 等于哦，这样就算出明背包加密体制举例(2)，假定已知，其d等于由d 1、d 2一直到d n组成，其中d 1、d 2、…、d n是n位的0且或1这样的符号串，令c等于a 1 乘以d 1加上a 2 乘以d 2加上…··加上a n 乘以d n ，c就是由背包序列a 1、a 2、...、a n加密明文d ，对于d等于由d 1·d 2 ．a -dn的密文，这样一来，则t的负1次方乘以c等于用l的负1次方乘以a 1乘以d 1加上w的负l次方a 2乘以d 2 加上…加上w的负1次方a n乘以d n ，因为啊a k要是等tb k去求模k ，其k等于1、2、...、n ，故这么一来啊t的负1次方乘以c就等于t的负加上t的负加上…加上w的负等于b 1 乘以d 1加上b 2 乘以d 2加上…加上b n 乘以d n ，这是一个超递增背包问题，很容易解出来的有。MH背包加密体制针对RSA密码体制有这样的证明，一旦n被成功分解的话，那么这个密码则会被破译，也就是说破译RSA的难度小于等于大整数的分解，可是却没办法证明破译RSA跟分解大整数是等价的。现已证明，Rabin密码体制的破译和分解与大整数相关，二者等价，它具备两种特性：其一，它并非基于一一对应的单向陷门函数，对于同一密文，或许存在两个以上相对应的明文；其二，破译该体制等同于分解大整数，Rabin算法要概述密码体制，密钥产生时需随机挑选两个大素数p、q，这两个大素数要满足p≡q≡3mod4，也就是说其形式为4k+3，然后计算n=p*q 。按照公钥为n，密钥是p、q来进行，2、加密时，c≡是明文分组，c是对应的密文分组密码体制（2），3、解密就是求解x2≡c≡，依据中国剩余定理可知该方程等同于求解方程组x2≡≡cmodq，因为p≡q≡3mod4，下面会看到，方程组的解能够容易求出，其中每个方程都存在两个解，也就是x≡mmodp，x≡-≡mmodq，x≡-mmodq，经过组合能够得到4个同余方程组：x≡-≡-≡≡≡-≡≡-≡mmodp，依据中国剩余定理能够解出每一方程组的解，总共4个，即每一密文所对应的明文并非唯一。能够有效去确定明文，可于m里添加一些双方所商定的信息，像是日期，还有发送者的ID等等。解密网络工程系?