【文章內容簡介】 ? 明文分組 = 011000 110101 101110 ? 計算背包總重量，第一組 011000對應 93 + 81 = 174，其它類似 ? 密文 = 174， 280， 333 y k y _ w e n f e n g @ 1 6 3 . c o m2022/8/29 Page: 27 背包密碼體制 ： 解密 ? 解密 —— 解密者知道私人密鑰“ 超遞增背包序列 ” ? 首先計算出 n1以滿足 n1 n modm ≡ 1； ? 用 n1模 m乘密文值的每項； ? 用私人背包對它進行劃分可獲得明文。 ? 例一 ：密文 {174， 280， 333}，私人密鑰 {2,3,6,13,27,52} ? n = 31， m = 105， 則 n1 = 61； ? 所有密文值乘 61模 105， 例 174 61mod105 ≡9≡3+6對應 011000； ? 恢復出的明文為“ 011000 110101 101110‖。 y k y _ w e n f e n g @ 1 6 3 . c o m2022/8/29 Page: 28 背包密碼體制 ： 實現及安全性 ? 背包密碼方案實現的限制 ? 超遞增序列至少要包含 250項，每一項的值應在 200~400位之間； ? 模數一般在 100~200位之間。 ? 背包密碼方案的安全性 ? 采用窮舉法攻擊：一臺每秒運行百萬次的計算機，要 1046年，即使 100萬臺計算機并行處理，太陽毀滅之前也解決不了這個問題； ? Shamir和 Zippel發(fā)現了背包問題易與難之間轉化的缺陷，可以從非超遞增背包序列中重構出超遞增背包序列。 y k y _ w e n f e n g @ 1 6 3 . c o m2022/8/29 Page: 29 非對稱密碼體制組成 ? 非對稱密碼體制的基本概念 ? DiffieHellman密碼體制 ? 背包密碼體制 ? RSA密碼體制 ? Elgamal密碼體制 ? 橢圓曲線密碼體制 y k y _ w e n f e n g @ 1 6 3 . c o m2022/8/29 Page: 30 非對稱密碼體制： RSA密碼體制 ? 由 Rivest、 Shamir、 Adleman三位密碼學家 1978年發(fā)明的 RSA算法是一種用數論構造的，迄今為止最為成熟完善的一個可逆的公鑰密碼體制，問題難度基于大整數分解。 ? RSA體制的幾個組成部分 ? 密鑰生成 ? 加密 ? 解密 y k y _ w e n f e n g @ 1 6 3 . c o m2022/8/29 Page: 31 RSA密碼體制： 密鑰生成 ? 首先選取兩個大素數 p和 q，計算 n = pq； ? 隨機選取加密密鑰 e，使 e和 (p 1)(q 1)互素； ? 用擴展歐幾里德算法計算解密密鑰 d，以滿足： ed = 1mod(p 1)(q 1)，即 d = e1mod(p 1)(q 1)； ? 公開鑰為 (e, n)，秘密鑰為 (d, n)。 y k y _ w e n f e n g @ 1 6 3 . c o m2022/8/29 Page: 32 RSA密碼體制： 加 /解密 ? 加密過程 ? 加密的數學變換： C = Memodn ? 解密過程 ? 解密的數學變換： M = Cd modn ? 正確性驗證 Cdmodn = (Me)dmodn = Medmodn = Mk(p1)(q1)+1modn = M Mk(p1)(q1)modn (歐拉定理 ？？？？ ) y k y _ w e n f e n g @ 1 6 3 . c o m2022/8/29 Page: 33 RSA密碼體制： 加 /解密 ? M. Mk(p1)(q1)modn (歐拉定理 ？？？？ ) ? M與 n互素 ， 則由歐拉定理 Mk(p1)(q1)modn ≡1modn得 M Mk(p1)(q1)modn ≡ Mmodn ? gcd(M,n) ≠1， 由于 n = pq， 且 p和 q都是素數 ， 則 M是 p或 q的倍數 。 設 M = tp， 其中 t為一正整數 ， 而 gcd(M,q) =1(m n)。 由歐拉定理 Mq1modq ≡1modq得 1) Mk(p1)(q1)modq≡1modq ? Mk(p1)(q1) = 1 + rq(兩邊同時乘以 M = tp) 2) M Mk(p1)(q1) =(1 + rq) tp = tp + rtpq = M + rtn 3) M Mk(p1)(q1)modn ≡ (M + rtn)modn ≡ M modn y k y _ w e n f e n g @ 1 6 3 . c o m2022/8/29 Page: 34 RSA密碼體制： 舉例 ? 選 p = 7， q = 17。求 n = p q = 119， 。取 e = 5，滿足 1 e ，且 。 ? 確定滿足 d e ≡1mod96且小于 96的 d，因為 77 5 =385= 4 96+ 1，所以 d為 77； ? 公開密鑰為 {5,119}，私密鑰為 {77,119} ； ? 設明文 m = 19，加密 c≡195mod119 ≡2476099mod119≡66； ? 解密 6677mod119 ≡19。 ( ) ( 1 ) ( 1 ) 96n p q? ? ? ? ?()m? g cd( ( ), ) 1ne? ?y k y _ w e n f e n g @ 1 6 3 . c o m2022/8/29 Page: 35 RSA密碼體制： RSA算法中的計算問題 ? 6677mod119，先求 6677再求模，中間結果遠遠超出了計算機所允許的整數取值范圍。 ? (a b) modn ≡[(a modn) (b modn)]modn ? 求 am ? m = bk2k + bk12k1 +…+ b12 + b0，其中 bi＝ 0或 1(i = 0,…, k) ? am = (((abk)2abk1)2abk2)2… ab1)2ab0 ? 例如 19 = 1 24 + 0 23 + 0 22 + 1 21 + 1 20 a19= (((a1)2a0)2a0)2a1)2a0 y k y _ w e n f e n g @ 1 6 3 . c o m2022/8/29 Page: 36 RSA密碼體制： RSA算法中的計算問題 指數分解成二進制 void Depose(int m, int* link int* z) // m 0 { *z = 0。 for(。 m != 1。 m = 1) { if(m%2 == 0) *(link + *z) = 0。 else *(link + *z) = 1。 (*z)++。 } *(link + *z) = 1。 } 快速冪計算 int PowerCompute(int a, int* link, int z, int n) { int y = 1。 for(。 z 0。 z) { if(*(link + z) != 0) y = (((y*a)%n) * ((y*a)%n))%n。 else y = (y*y)%n。 } if(*li