RABIN公开金钥密码系统

RABIN公開金鑰密碼系統EncryptionKey:(b,n)→公開DecryptionKey:(b,p,q)→保密C=E(M)=M(M+b)modn(1)取法：M<n,b任意取M:明文C:密文p,q:100-digit的質數n=p*q以上皆為加密過程1如何解密？M2+Mb-C0(modn)(2)針對(2)式解出M值(2)式相等於下列(3),(4)兩式

M2+Mb-C0(modp)(3)M2+Mb-C0(modq)(4)-b/2(modp)M=D(C)=-b/2(modq)函數D所解得的明文，會有下列四種情況：2(a)If(b/2)2+C0(modp),then(3)hastworootsMp1-b/2+(modp)Mp2-b/2-(modp)(b)If(b/2)2+C0(modp),then(3)hasonerootMp-b/2(modp)3(c)If(b/2)2+C0(modq),then(4)hastworootsMq1-b/2+(modq)Mq2-b/2-(modq)(b)If(b/2)2+C0(modq),then(4)hasonerootMq-b/2(modq)4四種情況分別如下：(1)If(b/2)2+C0(modp)and

If(b/2)2+C0(modq)MMp1(modp)MMq1(modq)MMp2(modp)MMq1(modq)MMp1(modp)MMq2(modq)MMp2(modp)MMq2(modq)M

M1(1)(modn)M

M2(1)(modn)M

M3(1)(modn)M

M4(1)(modn)5(2)If(b/2)2+C

0(modp)and

If(b/2)2+C0(modq)MMp(modp)MMq1(modq)MMp(modp)MMq1(modq)(3)If(b/2)2+C

0(modq)and

If(b/2)2+C0(modp)MMp1(modp)MMq(modq)

M

M1(2)(modn)M

M2(2)(modn)M

M1(3)(modn)6

MMp2(modp)MMq(modq)(3)If(b/2)2+C

0(modq)and

If(b/2)2+C0(modp)MMp(modp)MMq(modq)

MM2(3)(modn)MM1(4)(modn)7M

C

或

或

或M1(4)問題：如何決定那一個才是真正的明文呢？答：在明文中，包含一些重要的資訊，eg.senderID,receiverID,dateandtime,etc.接受者選擇四者之中，資訊正確的。EM1(3)M2(3)M1(1)M2(1)M3(1)M4(1)M1(2)M2(2)8KNAPSACK公開金鑰密碼學AlgorithmsFINITEDEFINITENESSINPUT/OUTPUTGENERALITYEFFECTIVENESS9NP-Complete問題到目前為止尚未有好的Algorithm，可在Polynomialtime解決。如0/1-Knapsack

101112an13140/1Knapsackproblem(sumofsubset)已知一整數數C及一向向量A＝(a1，a2，…，an)求一A之子子集合，其其和為C亦亦即求一二二元之向量量M=(m1，m2，…，mn)使得C＝＝M×ATExampleN=5，C=14，，及A＝（（1，10，5，22，3））則M＝(1，1，0，0，1)15SimpleKnapsackProblem為一特例，，其問題之之解可以在在Lineartime求求得向量A內之元素呈呈Supperincreasing，即ExampleN=5，C=14，，及A=(1，3，5，10，22)則m5=0----因14<22m4=1----因14>10m3=0----因4<5m2=1----因4>3m1=1----因1=1M=(1,1,0,1,0)16Merkle-HellmanKnapsack將SimpleKnapsack轉轉成一般般的0/1Knapsack選一個SimpleKnapsackA=(a1,a2,…,an)選一整數u，使得u>選一整數e為加密金金鑰，e和和u互質計算解密金金鑰d，e×d=1modu轉換A為一般的0/1KnapsackAA=(e××A)moduPublicKey=ATrapdoor=d和和u(A=dAmodu)密文C=M×AT17Merkle-HellmanKnapsack方法法（續）解密步驟轉換密文C為可用SimpleKnapsack求解解之值CC=d×Cmodu=d×MATmodu=d×M××(e×AT)modu=MAT因A為SimpleKnapsack，，故M可以以很快求得得。18Example: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=1419Merkle-HellmanKnapsack方法法的保密性性原先建議n=100，但KnapsackProblem可在在T＝0(2n/2)時間解決，，n=100，250=1015使用一個processor約11574天可可完成，1000個個處理機可在12天天完成，故故為安全起起見，取n=200Merkle-Hellman建議議使用多組組e，d來來重覆處理理A=eA。雖然0/1Knapsack是NP-complete，但但不意味著著由SimpleKnapsack轉換換之Problem一定是NP-complete20Graham-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。21Example:Graham-ShamirKnapsacks設n=5，，A如下所示jRjIjSj01101010000000101=a100100101000000011=a20