3密碼的加密與解密

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

2、，它可能是比特流、文本文件、位圖、數(shù)字化的語音流或者數(shù)字化的視頻圖像等。密文用C（Cipher）表示，也是二進(jìn)制數(shù)據(jù)，有時(shí)和M一樣大，有時(shí)稍大。通過壓縮和加密的結(jié)合，C有可能比P小些。加密函數(shù)E作用于M得到密文C，用數(shù)學(xué)公式表示為：E（M）=C。解密函數(shù)D作用于C產(chǎn)生M，用數(shù)據(jù)公式表示為：D（C）=M。先加密后再解密消息，原始的明文將恢復(fù)出來，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,仿射變換密碼,上面移位置換密碼的一個(gè)簡單變種就是仿射變換密碼，其數(shù)學(xué)表示為,在上面例子移位置換密碼下，明文中相鄰的字母對應(yīng)的密文字母也

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

5、由26個(gè)英文字母組成，取m=26.由于與26互素，a有12種不同的取法，b有26種不同的取法，所以放射變換有12*26=321種?？刹扇「F舉法來破譯。可以用頻率法，即密文中出現(xiàn)次數(shù)最多的字母與英文中最常見的字母對應(yīng)。在密文中 在平常統(tǒng)計(jì)中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,利用上述解密公式對密文進(jìn)行解密得到：,這是一串沒有意義的字符串，解密失敗,最后破譯文為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ù)學(xué)手段是矩陣運(yùn)算。,,加密過程：,1）將英文的26個(gè)字母與0到25之間的整數(shù)建立一一對應(yīng)關(guān)系，稱為字母的表值，然后根據(jù)明文字母的表值，將明文信息用數(shù)字表示。設(shè)明文信息只用26個(gè)大寫字母表示，通訊雙方給出這26個(gè)字母的表值如下：,2）選擇一個(gè)二階可逆整數(shù)方陣A

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

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

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

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

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

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

14、,a與b的最大公因數(shù)：gcd (a, b)gcd(20, 24)=4 , gcd (15, 16)=1如果gcd(a, b)=1 ，稱a與b 互素模運(yùn)算 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ù)論基礎(chǔ)（續(xù)）,模運(yùn)算是可交換的、可結(jié)合的、可分配的,(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,冪,模運(yù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ù)論基礎(chǔ)（續(xù)）,歐拉函數(shù)ф(n) n是正整數(shù)， ф(n) 是比n小且與n 互素的正整數(shù)的個(gè)數(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是素?cái)?shù)，則ф(p)=p-1, 比如ф(2), ф(5)， ф(11)如果p,q 是素?cái)?shù)，則ф(pq)=ф(p) ф(q)＝ (p-1)(q-1) 。比如，ф(10)= ф（2*5）= ф（2） ф（5）=1*4=4,數(shù)論基礎(chǔ)（續(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 互素，則,等價(jià)形式,數(shù)論基礎(chǔ)（續(xù)）,推論：給定兩個(gè)素?cái)?shù)p, q , 兩個(gè)正整數(shù) n, m ，使得n=pq, 0<m<n ； 則對于任意正整數(shù)k ，下列關(guān)系

20、成立： m kф(n)+1 ≡ m mod n,RSA算法操作過程,密鑰產(chǎn)生1. 取兩個(gè)大素?cái)?shù) p, q , 保密; 2. 計(jì)算n=pq，公開n; 3. 計(jì)算歐拉函數(shù)ф(n) =（p-1）(q-1)；4. 任意取一個(gè)與ф(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ù)字，設(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