兩種公鑰加密算法——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