RABIN公開(kāi)金鑰密碼系統(tǒng)課件

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

M2+Mb-C0(modp)(3)M2+Mb-C0(modq)(4)-b/2(modp)M=D(C)=-b/2(modq)函數(shù)D所解得的明文，會(huì)有下列四種情況：2如何解密？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(a)If(b/2)2+C0(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(c)If(b/2)2+C0(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四種情況分別如下：MM1(1)(modn)MM2(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(2)If(b/2)2+C0(modp)an

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)7MMp2(modp)MM2(3)(M

C

或

或

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

10NP-Complete問(wèn)題到目前為止尚未有好的Algori11111212an13an1314140/1Knapsackproblem(sumofsubset)已知一整數(shù)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)150/1Knapsackproblem(sumofsSimpleKnapsackProblem為一特例，其問(wèn)題之解可以在Lineartime求得向量A內(nèi)之元素呈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)16SimpleKnapsackProblem為一特例，其問(wèn)Merkle-HellmanKnapsack將SimpleKnapsack轉(zhuǎn)成一般的0/1Knapsack選一個(gè)SimpleKnapsackA=(a1,a2,…,an)選一整數(shù)u，使得u>選一整數(shù)e為加密金鑰，e和u互質(zhì)計(jì)算解密金鑰d，e×d=1modu轉(zhuǎn)換A為一般的0/1KnapsackAA=(e×A)moduPublicKey=ATrapdoor=d和u(A=dAmodu)密文C=M×AT17Merkle-HellmanKnapsack將SimpleMerkle-HellmanKnapsack方法（續(xù)）解密步驟轉(zhuǎn)換密文C為可用SimpleKnapsack求解之值CC=d×Cmodu=d×MATmodu=d×M×(e×AT)modu=MAT因A為SimpleKnapsack，故M可以很快求得。18Merkle-HellmanKnapsack方法（續(xù)）解密Example:Merkle-HellmanKnapsack設(shè)A=(1,3,5,10)，u=20和e=7，則d=3A=(7,1,15,10)設(shè)M＝13，以二進(jìn)位法表示(1,1,0,1)C=M×AT=7+1+10=18解密C=3×18mod20=1419Example:Merkle-HellmanKnapsaMerkle-HellmanKnapsack方法的保密性原先建議n=100，但KnapsackProblem可在T＝0(2n/2)時(shí)間解決，n=100，250=1015使用一個(gè)processor約11574天可完成，1000個(gè)處理機(jī)可在12天完成，故為安全起見(jiàn)，取n=200Merkle-Hellman建議使用多組e，d來(lái)重覆處理A=eA。雖然0/1Knapsack是NP-complete，但不意味著由SimpleKnapsack轉(zhuǎn)換之Problem一定是NP-complete20Merkle-HellmanKnapsack方法的保密性原Graham-ShamirKnapsack方法和Merkle-HellmanKnapsack相似，只有A`之結(jié)構(gòu)稍有改變。Aj=(Rj,Ij,Sj)以二進(jìn)位表示之。

Rj,Sj:為隨機(jī)亂數(shù)Ij:為第j個(gè)bit為1，其他位置為0的單位元素。Sj:前面的log2n位元值為0，以保證不會(huì)有進(jìn)位產(chǎn)生。((In,Sn),(In-1,Sn-1),…,(I1,S1))為一SimpleKnapsack找d,e,u,和A的方法同Merkle-HellmanKnapsack法優(yōu)點(diǎn)：解密時(shí)可以由C中直接求得M。21Graham-ShamirKnapsack方法和MerkExample:Graham-ShamirKnapsacks設(shè)n=5，A如下所示jRjIjSj01101010000000101=a100100101000000011=a201001000100000100=a301100000010000111=a400011000001000001=a5

M=(0,1,0,0,1)C`=M×AT=a2+a5=(R2+R5,I2+I5,S2+S5)=00111101001000100恰為明文22Example:Graham-ShamirKnapsacRABIN公開(kāi)金鑰密碼系統(tǒng)EncryptionKey:(b,n)→公開(kāi)DecryptionKey:(b,p,q)→保密C=E(M)=M(M+b)modn(1)取法：M<n,b任意取M:明文C:密文p,q:100-digit的質(zhì)數(shù)n=p*q以上皆為加密過(guò)程23RABIN公開(kāi)金鑰密碼系統(tǒng)EncryptionKey:(如何解密？M2+Mb-C0(modn)(2)針對(duì)(2)式解出M值(2)式相等於下列(3),(4)兩式

M2+Mb-C0(modp)(3)M2+Mb-C0(modq)(4)-b/2(modp)M=D(C)=-b/2(modq)函數(shù)D所解得的明文，會(huì)有下列四種情況：24如何解密？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)25(a)If(b/2)2+C0(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)26(c)If(b/2)2+C0(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)27四種情況分別如下：MM1(1)(modn)MM2(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)28(2)If(b/2)2+C0(modp)an

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)29MMp2(modp)MM2(3)(M

C

或

或

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

32NP-Complete問(wèn)題到目前為止尚未有好的Algori33113412an35an1336140/1Knapsackproblem(sumofsubset)已知一整數(shù)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)370/1Knapsackproblem(sumofsSimpleKnapsackProblem為一特例，其問(wèn)題之解可以在Lineartime求得向量A內(nèi)之元素呈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)38SimpleKnapsackProblem為一特例，其問(wèn)Merkle-HellmanKnapsack將SimpleKnapsack轉(zhuǎn)成一般的0/1Knapsack選一個(gè)SimpleKnapsackA=(a1,a2,…,an)選一整數(shù)u，使得u>選一整數(shù)e為加密金鑰，e和u互質(zhì)計(jì)算解密金鑰d，e×d=1modu轉(zhuǎn)換A為一般的0/1KnapsackAA=(e×A)moduPublicKey=ATrapdoor=d和u(A=dAmodu)密文C=M×AT39Merkle-HellmanKnapsack將SimpleMerkle-HellmanKnapsack方法（續(xù)）解密步驟轉(zhuǎn)換密文C為可用SimpleKnapsack求解之值CC=d×Cmodu=d×MATmodu=d×M×(e×AT)modu=MAT因A為SimpleKnapsack，故M可以很快求得。40Merkle-HellmanKnapsack方法（續(xù)）解密Example:Merkle-HellmanKnapsack設(shè)A=(1,3,5,10)，u=20和e=7，則d=3A=(7,1,15,10)設(shè)M＝13，以二進(jìn)位法表示(1,1,0,1)C=M×AT=7+1+10=18解密C=3×18mod20=1441Example:Merkle-HellmanKnapsaMerkle-HellmanKnapsack方法的保密性原先建議n=100，但KnapsackProblem可在T＝0(2n/2)時(shí)間解決，n=100，250=1015使用一個(gè)processor約11574天可完成，1000個(gè)處理機(jī)可在12天完成，