《[精选]RABIN公开金钥密码系统》由会员分享，可在线阅读，更多相关《[精选]RABIN公开金钥密码系统（23页珍藏版）》请在金锄头文库上搜索。
1、RABIN公開金鑰密碼系統,Encryption Key: (b, n) 公開 Decryption Key: (b, p, q) 保密 C = E(M) = M(M+b) mod n (1) 取法：Mn, b任意取 M: 明文 C: 密文 p, q: 100-digit 的質數 n= p*q 以上皆為加密過程,1,如何解密？ M2+Mb-C 0 (mod n) (2) 針對(2)式解出M值 (2)式相等於下列(3), (4)兩式 M2+Mb-C 0 (mod p) (3) M2+Mb-C 0 (mod q) (4) -b/2 (mod p) M = D(C)= -b/2 (mod q) 函數
2、D所解得的明文，會有下列四種情況：,2,(a) If (b/2)2+C 0 (mod p), then (3) has two roots Mp1 -b/2 + (mod p) Mp2 -b/2 - (mod p) (b) If (b/2)2+C 0 (mod p), then (3) has one root Mp -b/2 (mod p),3,(c) If (b/2)2+C 0 (mod q), then (4) has two roots Mq1 -b/2 + (mod q) Mq2 -b/2 - (mod q) (b) If (b/2)2+C 0 (mod q), then (4) h
3、as one root Mq -b/2 (mod q),4,四種情況分別如下： (1) If (b/2)2+C 0 (mod p) and If (b/2)2+C 0 (mod q) M Mp1 (mod p) M Mq1 (mod q) M Mp2 (mod p) M Mq1 (mod q) M Mp1 (mod p) M Mq2 (mod q) M Mp2 (mod p) M Mq2 (mod q),5,(2) If (b/2)2+C 0 (mod p) and If (b/2)2+C 0 (mod q) M Mp (mod p) M Mq1 (mod q) M Mp (mod p) M
4、Mq1 (mod q) (3) If (b/2)2+C 0 (mod q) and If (b/2)2+C 0 (mod p) M Mp1 (mod p) M Mq (mod q),M M1(2) (mod n),M M2(2) (mod n),M M1(3) (mod n),6,M Mp2 (mod p) M Mq (mod q) (3) If (b/2)2+C 0 (mod q) and If (b/2)2+C 0 (mod p) M Mp (mod p) M Mq (mod q),M M2(3) (mod n),M M1(4) (mod n),7,M C 或 或 或 M1(4) 問題：如
5、何決定那一個才是真正的明文呢？ 答：在明文中，包含一些重要的資訊，eg. sender ID, receiver ID, date and time , etc. 接受者選擇四者之中，資訊正確的。,E,8,KNAPSACK公開金鑰密碼學 Algorithms,FINITE DEFINITENESS INPUT/OUTPUT GENERALITY EFFECTIVENESS,9,NP-Complete 問題,到目前為止尚未有好的Algorithm， 可在Polynomial time解決。 如 0/1-Knapsack,10,11,12,an,13,14,0/1 Knapsack problem
6、 (sum of subset),已知一整數C及一向量A(a1，a2，an) 求一A之子集合，其和為C亦即求一二元之向量 M=(m1，m2，mn)使得CMAT Example N=5，C=14，及A（1，10，5，22，3） 則M(1，1，0，0，1),15,Simple Knapsack Problem,為一特例，其問題之解可以在Linear time求得 向量A內之元素呈Supper increasing，即,Example N=5，C=14，及A=(1，3，5，10，22) 則 m5=0-因1410 m3=0-因43 m1=1-因1=1 M=(1,1,0,1,0),16,Merkle-H
7、ellman Knapsack,將Simple Knapsack 轉成一般的0/1 Knapsack 選一個Simple Knapsack A=(a1, a2, , an) 選一整數u，使得 u 選一整數e為加密金鑰，e和u互質 計算解密金鑰d，e d=1 mod u 轉換A為一般的0/1 Knapsack A A=(e A) mod u Public Key = A Trapdoor = d 和u (A=dA mod u) 密文C = M AT,17,Merkle-Hellman Knapsack方法（續）,解密步驟 轉換密文C為可用Simple Knapsack求解之值C C=d C mo
8、d u =dMAT mod u =dM(eAT) mod u =MAT 因A為Simple Knapsack，故M可以很快求得。,18,Example: Merkle-Hellman Knapsack,設A=(1, 3, 5, 10)，u=20和e=7， 則d=3 A=(7, 1, 15, 10) 設M13，以二進位法表示(1,1,0,1) C=MAT=7+1+10=18 解密 C=318 mod 20=14,19,Merkle-Hellman Knapsack方法的保密性,原先建議n=100，但Knapsack Problem可在T0 (2n/2) 時間解決，n=100，250=1015 使
9、用一個processor約11574天可完成，1000個處理機 可在12天完成，故為安全起見，取n=200 Merkle-Hellman 建議使用多組e，d來重覆處理A=eA。 雖然0/1 Knapsack 是NP-complete，但不意味著由 Simple Knapsack轉換之Problem一定是NP-complete,20,Graham-Shamir Knapsack 方法,和Merkle-Hellman Knapsack 相似，只有A之結構稍有改變。 Aj=(Rj, Ij, Sj)以二進位表示之。 Rj, Sj: 為隨機亂數 Ij: 為第j 個bit為1，其他位置為0的單位元素。 S
10、j:前面的log2n位元值為0，以保證不會有進位產生。 (In, Sn), (In-1, Sn-1), , (I1, S1)為一Simple Knapsack 找d, e, u, 和A的方法同Merkle-Hellman Knapsack法 優點：解密時可以由C中直接求得M。,21,Example: Graham-Shamir Knapsacks,設n=5，A如下所示,j Rj Ij Sj,011010 10000 000101 =a1 001001 01000 000011 =a2 010010 00100 000100 =a3 011000 00010 000111 =a4 000110 00001 000001 =a5,M=(0,1,0,0,1) C=MAT=a2+a5 =(R2+R5, I2+I5, S2+S5)=001111 01001 000100,恰為明文,22,演讲完毕，谢谢观看！,
