RABIN公开金钥密码系统

1RABIN公開金鑰密碼系統EncryptionKey:(b,n)→公開DecryptionKey:(b,p,q)→保密C=E(M)=M(M+b)modn(1)取法：M10m3=0----因4<5m2=1----因4>3m1=1----因1=1M=(1,1,0,1,0)1i1jjiaa17Merkle-HellmanKnapsack將SimpleKnapsack轉成一般的0/1Knapsack1.選一個SimpleKnapsackA=(a1,a2,…,an)2.選一整數u，使得u>3.選一整數e為加密金鑰，e和u互質4.計算解密金鑰d，e×d=1modu5.轉換A為一般的0/1KnapsackAA=(e×A)moduPublicKey=ATrapdoor=d和u(A=dAmodu)密文C=M×AT,an1ii18Merkle-HellmanKnapsack方法（續）•解密步驟轉換密文C為可用SimpleKnapsack求解之值CC=d×Cmodu=d×MATmodu=d×M×(e×AT)modu=MAT因A為SimpleKnapsack，故M可以很快求得。19Example:Merkle-HellmanKnapsack設A=(1,3,5,10)，u=20和e=7，則d=3A=(7,1,15,10)設M＝13，以二進位法表示(1,1,0,1)C=M×AT=7+1+10=18解密C=3×18mod20=1420Merkle-HellmanKnapsack方法的保密性•原先建議n=100，但KnapsackProblem可在T＝0(2n/2)時間解決，n=100，250=1015•使用一個processor約11574天可完成，1000個處理機可在12天完成，故為安全起見，取n=200•Merkle-Hellman建議使用多組e，d來重覆處理A=eA。•雖然0/1Knapsack是NP-complete，但不意味著由SimpleKnapsack轉換之Problem一定是NP-complete21Graham-ShamirKnapsack方法•和Merkle-HellmanKnapsack相似，只有A`之結構稍有改變。•Aj=(Rj,Ij,Sj)以二進位表示之。Rj,Sj:為隨機亂數Ij:為第j個bit為1，其他位置為0的單位元素。Sj:前面的log2n位元值為0，以保證不會有進位產生。•((In,Sn),(In-1,Sn-1),…,(I1,S1))為一SimpleKnapsack•找d,e,u,和A的方法同Merkle-HellmanKnapsack法•優點：解密時可以由C中直接求得M。22Example:Graham-ShamirKnapsacks設n=5，A如下所示jRjIjSj101101010000000101=a1200100101000000011=a2301001000100000100=a3401100000010000111=a4500011000001000001=a5M=(0,1,0,0,1)C`=M×AT=a2+a5=(R2+R5,I2+I5,S2+S5)=00111101001000100恰為明文