3密碼的加密與解密

1、密碼的加密與解密的數(shù)學模型,密碼學的基本概念,密碼學基本模型,,發(fā)送方,接收方,,Encryption加密,Decryption解密,加密：c= EK (m),解密：m= DK (c),,,不安全信道,Plaintext 明文,,,Key解密密匙,Key加密密匙,Plaintext 明文,Ciphertext 密 文,明文用M（Message，消息）或P（Plaintext，明文）表示

2、，它可能是比特流、文本文件、位圖、數(shù)字化的語音流或者數(shù)字化的視頻圖像等。密文用C（Cipher）表示，也是二進制數(shù)據(jù)，有時和M一樣大，有時稍大。通過壓縮和加密的結合，C有可能比P小些。加密函數(shù)E作用于M得到密文C，用數(shù)學公式表示為：E（M）=C。解密函數(shù)D作用于C產(chǎn)生M，用數(shù)據(jù)公式表示為：D（C）=M。先加密后再解密消息，原始的明文將恢復出來，D（E（M））=M必須成立。,置換密碼,Caesar 密碼,ABCDEFGHIGKLM

3、NOPQRSTUVWXYZ,DEFGHIGKLMNOPQRSTUVWXYZABC,Caesar was a great soldier,密碼本,密文,Fdhvdu zdv d juhdw vroglhu,明文,密文,CAESAR 密碼 ： c=( m+ 3) Mod 26,仿射變換密碼,上面移位置換密碼的一個簡單變種就是仿射變換密碼，其數(shù)學表示為,在上面例子移位置換密碼下，明文中相鄰的字母對應的密文字母也

4、是相鄰的，如A和B對應的密文字母分別為D和E,但在仿射變換下， 對應的密文字母分別為F((3*0+5)mod26=5=F)和I，它們有3個字母的間隔(a=3),例8.3,假設下面是仿射變換加密的，試破譯此文FSFPR EDLFS HRLER KFXRS KTDMM PRRKF SFUXA FSDHKFSPVM RDSKA RLVUU RRIFE FKKAN EHOFZ FUKRE SVVS,假設此問題

5、由26個英文字母組成，取m=26.由于與26互素，a有12種不同的取法，b有26種不同的取法，所以放射變換有12*26=321種。可采取窮舉法來破譯?？梢杂妙l率法，即密文中出現(xiàn)次數(shù)最多的字母與英文中最常見的字母對應。在密文中 在平常統(tǒng)計中F：出現(xiàn)12次 E：出現(xiàn)頻率 13.04%R：出現(xiàn)12次 T：出現(xiàn)頻率 13.04%S：出現(xiàn)9次 Z：出現(xiàn)頻率 0.

6、08%K：出現(xiàn)8次,GTGAE RCSGT KESRE …… RKLGU GXDER TMMT,利用上述解密公式對密文進行解密得到：,這是一串沒有意義的字符串，解密失敗,最后破譯文為ANAME RICAN SECRE TAGEN TWILL MEETA NAFGH ANISTANMOL EINTH ECOFF EEBAR ATTHU RSDAY AFTER NOON即AN AMERICAN SECRET AGENT WILL

7、 MEET AN AFGHANISTAN MOLE IN THE COFFEE BAR AT THURSDAY AFTERNOON破譯成功,HILL密碼,Hill2密碼中所用的數(shù)學手段是矩陣運算。,,加密過程：,1）將英文的26個字母與0到25之間的整數(shù)建立一一對應關系，稱為字母的表值，然后根據(jù)明文字母的表值，將明文信息用數(shù)字表示。設明文信息只用26個大寫字母表示，通訊雙方給出這26個字母的表值如下：,2）選擇一個二階可逆整數(shù)方陣A

8、，稱為Hill2密碼的加密矩陣，它是加密體制的“密鑰”，是加密的關鍵，僅通訊雙方掌握。,3）將明文字母分組。 Hill2 使用的是二階矩陣，所以將明文字母每2個一組（可以推廣至Hilln密碼），若最后僅有一個字母，則補充一個沒有實際意義的啞字母。這樣使得每組都有2個字母，查出每個字母的表值，構成一個二維列向量 。,4）令 ，由 的兩個分量反查字母表值得到的兩個字母即為密文字母。,解密過程：加密過程的逆過程。,字母（

9、明文）,,表值,一組數(shù),,分組,向量,,A,左乘,向量,,反查表值,密文,,ＨILL密碼的數(shù)學模型,例：設明文為“MEET求這段明文的 Hill2 密文。,將明文分為： ME ET,對應密文UUQR,設方陣 滿足命題8.1的條件容易驗證,對上面例子,det(A)=5,它與26互素，所以滿足8.1的條件，故A關于模26的逆為,對密文UUQR進行解密得到,即明文MEET,Hill密碼的加密

10、與解密過程類似于在n維向量空間中進行線性變換及其逆變換。每個明文向量是一個Zm上的n維向量，乘以加密矩陣并對m取余，仍為Zm上的一個n維向量。由于加密矩陣A為模m的可逆矩陣，所以如果知道了n個線性無關的n維明文向量及其對應的密文向量，就可以求出它的加密矩陣A及其模m的逆矩陣A-1(mod)例子詳見P88,例8.5,公開密鑰系統(tǒng),Hill密碼的加密和解密都只需要加密矩陣這個密鑰就可以了。這種系統(tǒng)稱為單密鑰系統(tǒng)。如果加密和解密使用兩個不

11、同的密鑰，則稱為雙密鑰系統(tǒng)，也稱為公開密鑰系統(tǒng)。密鑰的擁有者將其中一個密鑰公開，另一個保密。雙密鑰系統(tǒng)（1）W.Diffie 和 M.Hellman最早提出 （2）R.L.Rivest, A.Shamir和 L.Adleman 提出第一個方法雙密鑰系統(tǒng)的程序是這樣的收方先告訴發(fā)方如何把情報制成密碼（敵人也聽到）發(fā)方依法發(fā)出情報的密文（敵

12、人也可能收到密文）收方將密碼還原成原文（敵人卻解不開密文）,公鑰密碼系統(tǒng)的加密原理,每個通信實體有一對密鑰（公鑰，私鑰）。公鑰公開，用于加密，私鑰保密，用作解密A向B 發(fā)送消息，用B的公鑰加密B收到密文后，用自己的私鑰解密,PlainText,加密算法,解密算法,A,B,,,C的公鑰,,,,任何人向B發(fā)送信息都可以使用同一個密鑰(B的公鑰)加密沒有其他人可以得到B 的私鑰，所以只有B可以解密,公鑰密碼系統(tǒng)的簽名原理,A向B

13、發(fā)送消息，用A的私鑰加密（簽名）B收到密文后，用A的公鑰解密（驗證）,PlainText,加密算法,解密算法,cipher,PlainText,A,B,A的私鑰,,,,,,,A的公鑰,,3.3.2 RSA算法簡介,Ron Rivest, Adi Shamir , Leonard AdlemanRSA的安全性基于大數(shù)分解的難度RSA在美國申請了專利（已經(jīng)過期），在其他國家沒有RSA已經(jīng)成了事實上的工業(yè)標準，在美國除外,數(shù)論基礎

14、,a與b的最大公因數(shù)：gcd (a, b)gcd(20, 24)=4 , gcd (15, 16)=1如果gcd(a, b)=1 ，稱a與b 互素模運算 moda= q n +r 0≤r<n ; q=[a/n] ; [x] 表示小于或等于x的最大整數(shù)a=[a/n]n + (a mod n) , r = m mod n 如果 (a

15、 mod n )= (b mod n) ，則稱a 與b 模n同余，記為 a ≡ b mod n 例如， 23 ≡8 mod 5 , 8 ≡1 mod 7,數(shù)論基礎（續(xù)）,模運算是可交換的、可結合的、可分配的,(a+b) mod n = ((a mod n ) + (b mod n) ) mod n(a-b) mod n = ( (a mod n) – (b mod n) ) mod n(a×b) m

16、od n = ( (a mod n )× （b mod n) ) mod n (a × (b+c) ) mod n = （( a ×b) mod n + (a ×c) mod n）mod n,冪,模運算 ma mod n,m2 mod n = (m×m) mod n = (m mod n ) 2 mod n m4 mod n = (m2 mod n ) 2 mod n

17、m8 mod n = ( (m2 mod n )2 mod n )2 mod n m25 mod n = (m × m8 × m16) mod n,數(shù)論基礎（續(xù)）,歐拉函數(shù)ф(n) n是正整數(shù)， ф(n) 是比n小且與n 互素的正整數(shù)的個數(shù)ф(3)=|{1, 2}| =2 ф(4)=|{1, 3}| =2 ф(5)=|{1, 2, 3, 4 }| =4 ф(6)=|{1, 5}| =4 ф(

18、7)=|{1, 2, 3, 4, 5, 6}| =6ф(10)=|{1, 3, 7, 9}| =4 ф(11)=|{1, 2,3,4,5,6, 7,8, 9,10}| =10 如果p是素數(shù)，則ф(p)=p-1, 比如ф(2), ф(5)， ф(11)如果p,q 是素數(shù)，則ф(pq)=ф(p) ф(q)＝ (p-1)(q-1) 。比如，ф(10)= ф（2*5）= ф（2） ф（5）=1*4=4,數(shù)論基礎（續(xù)）,例如：

19、 m=3, n=10; ф(10)=4 mф(n)=34=81 ; 81 mod 10 = 1 即 81≡ 1 mod 10 34+1 = 243 ≡ 3 mod 10,歐拉定理 若整數(shù)m 和n 互素，則,等價形式,數(shù)論基礎（續(xù)）,推論：給定兩個素數(shù)p, q , 兩個正整數(shù) n, m ，使得n=pq, 0<m<n ； 則對于任意正整數(shù)k ，下列關系

20、成立： m kф(n)+1 ≡ m mod n,RSA算法操作過程,密鑰產(chǎn)生1. 取兩個大素數(shù) p, q , 保密; 2. 計算n=pq，公開n; 3. 計算歐拉函數(shù)ф(n) =（p-1）(q-1)；4. 任意取一個與ф(n) 互素的小整數(shù)e, 即 gcd (e, ф(n) )=1; 1<e< ф(n)

21、 e作為公鑰公開;5. 尋找d, 使得 de ≡1 mod ф(n) , ed =k ф(n) +1 d 作為私鑰保密。,p=7,q=17,n=119,Ф(n)=96,選擇e=5,5d=k×96＋1,令 k=4, 得到求得d=77,RSA 算法加密/解密過程,密鑰對（KU, KR）:KU={e, n} , KR={d, n}加密過程把待加密的內(nèi)容分成k比特的分組，k≤ log2n，并寫成

22、數(shù)字，設為M,則：C= Me mod n解密過程M = Cd mod n,{5,119},{77,119},c=m5 mod 119,m=c77 mod 119,RSA加密過程舉例,p=7,q=17, n=7*17=119ф(n)=(7-1)×(17-1)=96選 e=5, gcd (e, ф(n)) = gcd (5, 96)=1;尋找 d，使得 ed ≡1 mod 96 , 即 ed