【文章內(nèi)容簡介】 x n??41 歐拉定理（證明） ( ) ( )11( ) ( )11( ) ( )()11()( m od ) ( m od ) ( m od ) 1 ( m od )nniiiinniiiinnniiiinax n xax x na x x nan???????????????????????????????2023/2/11 現(xiàn)代密碼學理論與實踐 08 42/68 Chinese Remainder Theorem ? 中國余數(shù)定理 CRT說明某一范圍內(nèi)的整數(shù)可通過它對兩兩互素的整數(shù)取模所得的余數(shù)來重構(gòu) ? Z10(0,1,…,9) 中的 10個整數(shù)可通過它們對 2和 5(10的素因子 )取模所得的兩個余數(shù)來重構(gòu) . 假設數(shù) x的余數(shù) r2=0 且r5=3, 即 x mod 2=0, x mod 5=3, 則 x是 Z10中的偶數(shù)且被 5除余 3, 唯一解 x=8. ? 一種 CRT的表示形式 令 M= mi, 其中 mi兩兩互素 , 1=i, j=k, i≠ j, gcd(mi, mj)=1 將 Zm中的任一整數(shù)對應一個 k元組 , 該 k元組的元素均在Zmi中 , 對應關(guān)系為 A? (a1,a2,…,a k), 其中 A∈ Zm, 對1=i=k, ai∈ Zmi, 且 ai = A mod mi ??k1i2023/2/11 現(xiàn)代密碼學理論與實踐 08 43/68 Chinese Remainder Theorem 斷言一 對任何 A， 0≤A≤M，有唯一的 k元組 (a1,a2,…,a k)與之對應， 其中 0≤aimi，并且對任何這樣的 k元組 (a1,a2,…,a k)， ZM中 有唯一的 A與之對應。 1 1 1 12 2 2 2m o d m o dm o d m o d m o d m o dk k k ka A m A a ma A m A a ma A m A a m????????????????或2023/2/11 現(xiàn)代密碼學理論與實踐 08 44/68 Chinese Remainder Theorem ? 由 A到 (a1,a2,…,a k)的轉(zhuǎn)換顯然是唯一確定的。即只需取 ai = A mod mi 。對給定的 (a1,a2,…,a k)，可如下計算 A。 1 2 1 1110 ( m o d )( m o d )( m o d ) ()( )i i i i kiiji i i ii i i i iikiiiMi k M M m m m m mmj i M mc M M m i kM M m M mcA a c MA????? ? ? ? ? ? ? ? ? ???? ? ? ?????????對 1 ， 令 ， 因 為 ，所 以 對 所 有 的 ， 有 。 令， 1根 據(jù) 的 定 義 有 與 互 素 ， 所 以 有 唯 一 的 模 的 乘 法 逆 元 ， 因 此 可得 到 唯 一 的 。 計 算要 證 明 式 產(chǎn) 生 的 是 正 確 的 ， 必 須 證 明 對 1 m o d0 ( m o d ) 1 ( m o d ) m o diij j i i i i ii k a A mj i c M m c m a A m? ? ?? ? ? ? ?有 。由 于 時 ， ， 而 且 ， 故 。2023/2/11 現(xiàn)代密碼學理論與實踐 08 45/68 孫子定理 (孫子算經(jīng) , 35世紀 ) 今有物不知其數(shù) , 三三數(shù)之剩二 , 五五數(shù)之剩三 , 七七數(shù)之剩二 , 問物幾何。 x mod 3=2 n=3*5*7=105 x mod 5=3 d1=3, d2=5, d3=7 x mod 7=2 x1=2, x2=3, x3=2 2023/2/11 現(xiàn)代密碼學理論與實踐 08 46/68 孫子定理 (孫子算經(jīng) , 35世紀 ) 今有物不知其數(shù) , 三三數(shù)之剩二 , 五五數(shù)之剩三 , 七七數(shù)之剩二 , 問物幾何。 x mod 3=2 n=3*5*7=105 x mod 5=3 d1=3, d2=5, d3=7 x mod 7=2 x1=2, x2=3, x3=2 (1) 求 yi， ( )yi mod di=1 ( )y1 mod 3=1 ( )y2 mod 5=1 ( )y3 mod 7=1 得： 35 y1 mod 3=1 y1=2 21 y2 mod 5=1 y2=1 15 y3 mod 7=1 y3=1 (2) x = (35 2 2＋ 21 1 3＋ 15 1 2) mod 105=23 idn3105571052023/2/11 現(xiàn)代密碼學理論與實踐 09 47/32網(wǎng)絡信息安全 Chapter 9 Publickey Cryptography and RSA 2023/2/11 現(xiàn)代密碼學理論與實踐 09 48/32 公開密鑰加密過程 2023/2/11 現(xiàn)代密碼學理論與實踐 09 49/32 公開密鑰認證過程 2023/2/11 現(xiàn)代密碼學理論與實踐 09 50/32 ? 算法流程 ? 隨機選擇兩個秘密大素數(shù) p和 q； ? 計算公開模數(shù) n=p*q； ? 計算秘密的歐拉指數(shù)函數(shù) φ(n)=(p1)(q1)； ? 選擇一個與 φ(n)互素的數(shù)，作為 e或 d； ? 用 Euclid算法計算模 φ(n)的乘法逆元素，即根據(jù) ed mod φ(n)=1, 求 d或 e； ? 加密： C = Me mod n ? 解密： M= Cd mod n = (Me mod n)d mod n = M 這里， φ(n)為歐拉函數(shù) , 即集合 (1, 2, ..., n1)中與 n 互素的數(shù)的個數(shù)。 RSA密碼體制基本原理 2023/2/11 現(xiàn)代密碼學理論與實踐 09 51/32 2023/2/11 現(xiàn)代密碼學理論與實踐 09 52/32 2023/2/11 現(xiàn)代密碼學理論與實踐 09 53/32 一個例子 ? p=17,q=11,e=7, M=88 ? 求公鑰 KU和私鑰 KR分別為多少？ ? 加密計算后所得到的 C為多少？ ? 并驗證解密運算后，是否能恢復出明文 M。 2023/2/11 現(xiàn)代密碼學理論與實踐 09 54/32 一個例子 ? p=17,q=11,n=pq=17x11=187, φ(n)=(p1)(q1) =16x10=160 ? 選擇 e=7, gcd(7,160)=1, 23x7=161, 所以 d=23 ? 公鑰 KU={7,187}, 私鑰 KR={23,187}, M=88 ? 加密計算 C=887 mod 187 ? 887 mod 187 =[(884mod187)x882mod187)x881mod187)]mod187 ? 881mod187=88 ? 882mod187=7744mod187=77 ? 884mod187=59969536mod187=132 ? 887mod187=(88x77x132)mod187=894432mod187=11 ? 解密計算 M=1123 mod 187 = 88 2023/2/11 現(xiàn)代密碼學理論與實踐 09 55/32 RSA密碼體制基本原理 ? RSA算法滿足公開密鑰加密的要求 , 必須符合下列條件： ? 有可能找到 e, d, n的值 , 使得對所有 Mn有 Med mod n = M ? 對于所有 Mn的值 , 要計算 Me和 Cd是相對容易的 ? 在給定 e和 n時 , 計算 d是不可行的 ? 幾個關(guān)系 ? φ(n) = φ(pq)=φ(p)φ(q)=(p1)(q1), p,q are prime ? ed mod φ(n)=1, ed = kφ(n)+1, 即 ed≡1 mod φ(n), d≡e1 mod φ(n) 2023/2/11 現(xiàn)代密碼學理論與實踐 10 56/59網(wǎng)絡信息安全 Chapter 10 Key Management。 Other Public Key Cryptosystem 2023/2/11 現(xiàn)代密碼學理論與實踐 10 57/60 ? 公開密碼的主要作用之一就是解決密鑰分配問題， 公鑰密碼實際上可以用于以下兩個不同的方面 ? 公鑰的分配 ? 公鑰密碼用于傳統(tǒng)密碼體制的密鑰分配 ? 幾種公鑰分配方法 ? 公開發(fā)布、公開可訪問的目錄 ? 公鑰授權(quán)、公鑰證書 ? 公鑰的公開發(fā)布 ? 用戶將他的公鑰發(fā)送給另一通信方，或者廣播給通信各方，比如在電子郵件