两种公钥加密算法——Merkle-Hellman背包、RSA

今天看了一些加密体制，很厉害，佩服之余顺便总结下公钥（对称密钥很多啊，历史比较有名的有DES、AES、RC系列...水平不够说不清楚，所以不写了）。自己以后也要看，所以尽量通俗易懂（其实是不怎么会很官方很学术，顺道说，明天就七夕了，我还在搞些啥跟啥，怎么过%>_<%）。这些加密算法具体的发展历程，内容即变种可以百度，蛮有意思的，。 ①Merkle-Hellman背包        先说说背包问题吧（第一次看觉得。。。wc，背包也可以拿来加密，难不成是忽悠？）。 已知东西大小（一个整数序列An，n∈Z）和背包大小（目标和T），然后问哪些东西恰好能装满背包。即找出一个01序列P(n∈Z)使得ΣAi*Pi=T。        这是个NP问题（什么是NP问题不解释了），反正要找出这个P序列复杂度还挺高的，而这个序列刚好就可以当做明文啦。序列An就是公钥，而T自然而然就是密文（加密后数据）。这里的明文P（待加密的数据）与一般的不太一样，是由0、1组成的比特流（别小看二进制，计算机所有数据存储可都是01哟）。 具体实现例子：        假设明文P=0100 1011 1010 0101，公钥An={15,13,9,16}, 加密：        那密文就等于{13,40,24,29}。第一个13由前4个Pi*Ai得到，即0*15+1*13+0*9+0*16=13，其他类似。 然后公钥An{15,13,9,16}是公开的，密文T{13,40,24,29}可能被窃取到，这个例子n只有4，所以也蛮好猜明文的。比如13刚好在公钥有，所以前四位即0100，不过n大些就不一定了。还得用私钥得到明文。  解密：        这里的私钥是简单背包Sn{1,2,4,9}，8和17，那明文可以直接由密文和私钥算，即13*8mod17=2=[0100]，40*8mod17=14=[1011]，其余类似。（mod表示求余，13*8除以17余2,，2=[0100]，由对应简单背包的0100，即0*1+1*2+0*4+0*9=2得出,）。简单背包又叫超递增背包，即前n-1项和小于第n项，上面的简单背包是1<2，1+2<4，1+2+4<9。通过简单背包推明文比直接由公钥推容易多了，遵循能减Sn直接减原则（因为S1+S2+…+Sn-1<Sn，所以如果和介于Sn和Sn+1之间，则一定包含Sn）。比如14吧，先跟9比，比9大，可以直接减14-9=5（所以1）,5>4,直接减5-4=1（所以1）,1<2（所以0）,1>=1，直接减1-1=0（所以1），因此14=[1011]（即1*1+0*2+1*4+1*9=14），同样比如密文的29，29*8mod17=11,11>9,11-9=2,2<4,2>=2,2-2=0,所以29对应的明文序列为[0101](即0*1+1*2+0*4+1*9=11)。 如何构造私钥，公钥：        ①构造私钥。序列Sn是超递增的，选S1=1，那S2>S1就行，这里选2，S3>S2+S1,这里选4，同理S4选9...继续下去，让n越大越复杂，这里就构造n=4,简单背包Sn{1,2,4,9}        ②由私钥构造公钥。选一个乘数w，这里用15，选择求余的除数m，满足大于>ΣSi，且与w互素（一般选素数，且使得mod m后发布尽量均匀），这里选17。例子中的8是15mod17的逆元，因为8*15mod17=1,所以称8是15mod17的逆元。至于求法，有公式15^（17-2）mod17=8(费马定理推导，费马定理得任何素数p和任何元a<p,有a^p mod p=a,∴a^(p-1))mod p=1，设a的逆元为x，即ax mod p =1=a^(p-1)mod p，所以x=a^(p-2)mod p，用到的定理可见《信安数学》)。然后公钥Ai=Si*w mod m，即An={15,13,9,16}。 原理： 加密过程：密文Tn=An*P= w*Sn*P mod m， 解密过程：w的逆元*Tn mod m = w的逆元*w*Sn*P mod m=Sn*P mod m，然后为得P，直接通过简单背包推得。        这算法的缺陷看着也挺复杂的，这里不写了，有兴趣自己百度。 ②RSA算法         复杂性主要来自大数的分解素数因子，稍后解释为什么这样说。  明文P的加密：T = P^e mod m (e,m为公钥) 密文T还原：    P = T^d mod m (d,m为私钥) 因此需找到公钥私钥满足P=(P^e)^d mod m   如何构造私钥，公钥：         ①选择m。m=p*q(p,q均为大素数)。        ②选择e。e与(p-1)*(q-1)互素，可以直接选为大于p-1和q-1的素数。        ③计算私钥d为e mod(p-1)*(q-1)的逆元（稍后解释），即d=e^[(p-1)*(q-1)-2]mod[ (p-1 )*(q -1)]。 故只知道公钥（e，m），不知p、q，是很难解出私钥d的，也即没有私钥很难由密文得明文。m是两个大素数的乘积，基于大数分解素数因子的复杂。 具体实现例子： 选p=11,q=13,则m=p*q=11*13=143，选e=11,则私钥d=11^[(11-1)*(13-1)-2]mod (11-1 )*(13-1 )=11 （实际应使得d≠e）。  若明文为P= 7，则加密后，密文T= P^e mod m= 7^11mod143=106，解密P= T^d mod m=106^11mod143=7   原理：         欧拉函数 φ(n)表示所有小于n且与n互素的正整数个数（具体百度），若p为素数，则 φ(p)=p-1.       由上得m=p*q且p、q互素,则有 φ(m)= φ(p)* φ(q)=(p-1)*(q-1) （ 若m,n互质，φ(mn)=φ(m)φ(n)， 证明自行百度，或见《信安数学》）         d是e mod  φ(m) 的逆元，即e*d mod  φ(m)  =1,即e*d =k* φ(m) +1(k∈Z) 由欧拉费马结论， P^(p-1)mod p=1,(p-1是   φ(m)的因子 ) 则P^  [k* φ(m)]mod p=1,同乘P得P^[k*   φ(m)+1 ] mod p=P。 同理，  P^[k*   φ(m)+1 ] mod q=P。 则(P^e)^d=P^(e*d)=P^( k* φ(m) +1 )  =P mod p=P mod q ,所以P= (P^e)^d mod m。        暂时就这些吧！好像写不少了~~ 肚子饿吃饭去咕~~(╯﹏╰)b