【密碼學02】密碼系統原理及數學背景

上一篇文章【密碼學】四大主題簡單介紹?一文提到要實現信息傳輸的保密性、完整性，以及身份鑒別和抗抵賴，使用的技術手段有：

1)?????? 密碼技術（加密與解密）。

2)??????哈希技術，即散列技術。

3)??????隨機數。

4)??????時間戳。

下面先討論密碼技術。

下圖是一個典型的密碼系統，展示了密碼技術的應用場景：

?

明文：P?? 密文：C? 加密密鑰：K1?? 解密密鑰：K2?? 加密方法：E ??解密方法：D

加密與解密的關系可以用公式簡潔地表示：

C = E_K1(P) 表示用加密密鑰K1通過加密方法E對明文P進行加密得到密文C。

P = D_K2(C) 表示用解密密鑰K2通過解密方法D對密文C進行解密得到明文P。

D_K2(E_K1(P))= P? 由上面兩個式子可以得到這個式子。

由此可見，實際上，密碼算法E和D都是數學函數。

?

?????? 關于密碼學，有兩個基本原則：

1)?????? 消息必須包含一定的冗余度。

2)?????? 必須采取措施對抗重放攻擊。

另外，關于密碼系統的設計，還有一個原則叫做Kerckhoff原則：

“密碼算法必須公開，只有密鑰需要保密。”

這個原則體現了一個思想：讓入侵者知道密碼算法沒有關系，所有的秘密都隱藏在密鑰中。對密碼算法保密是不明智的，因為密碼算法的設計很困難，一旦算法原理泄露了，必須得花費大量精力重新設計。但密鑰可以隨時更換。

每個密碼算法，都有其數學背景，依賴某一種數學理論。下面是一些常見密碼算法的數學理論依據：

1)??? 信息論

由香農(Claude Elmwood Shannon)于1948年創立的現代信息論為安全的密碼系統定義了一個精確的數學模型。

2)??? 復雜性理論

復雜性理論提供了分析密碼算法的“計算復雜性”的方法。它通過對密碼算法進行比較，來確定一個密碼算法的安全性。密碼算法的“計算復雜性”通常用時間復雜度和空間復雜度兩個變量來度量。

3)??? 數論

數論中的模運算、素數、最大公因子、求模逆元、費爾馬定理、中國剩余定理、迦羅瓦域理論等等，是很多密碼學算法的數學基礎。

4)??? 因子分解

對一個數進行因子分解就是找出它的素數因子。因子分解是數論中最古老的問題，分解一個數很簡單，卻是一個耗時的過程。一些經典的因子分解算法有：數域篩選法、二次篩選法、橢圓曲線法等。

5)??? 計算有限域中的離散對數

計算離散對數是數學中公認的難題。計算離散對數與因子分解有緊密關系，如果能解決離散對數問題，就能解決因子分解問題。

【密碼學03】對稱密碼算法

前一篇文章【密碼學02】密碼系統原理及數學背景?提到了密碼算法。每個密碼算法都基于相應的數學理論。密碼學發展至今，已經產生了大量優秀的密碼算法，通常分為兩類：對稱密碼算法和非對稱密碼算法。

對稱密碼算法是指有了加密密鑰就可以推算出解密密鑰，有了解密密鑰就可以推算出加密密鑰的的算法。還是用公式表示比較簡潔：

???????E_K1(P)= C

???????D_K2(C)= P

其中E為加密算法，D為解密算法，P為明文，C為密文，K1為加密密鑰，K2為解密密鑰。在對稱密碼算法中，有了K1，就可以推算出K2，而有了K2，也可以推算出K1。實際應用的大多數對稱密碼算法中，K1與K2相同。因此對稱密碼算法的加密與解密關系如下：

???????E_K(P)= C

???????D_K(C)= P

加密與解密都使用密鑰K。

之所以叫對稱加密算法，就是加密與解密的密鑰相同。

常見的對稱密碼算法有以下這些：

1) DES，數據加密標準。由IBM于1970年代開發。DES算法使用的密鑰長度表示為64位(bit)，但每個第8為都用作奇偶校驗，所以對于使用者而言，密鑰長度是56位。DES將消息分成64位長的分組，一次加密一個分組，最后一個分組如果不滿64位，需要按照某種策略填滿64位，如下圖所示。

?

DES由于密鑰太短，而且密鑰空間中存在弱密鑰，因此現在已經不再安全了。1977年斯坦福大學的兩位密碼學大師Diffie和Helman設計了一臺機器，只要給定一小段明文和匹配的密文，一天之內即可推算出密鑰。

2)?三重DES，DES的增強版本。如下圖所示，還是利用DES密碼算法，但是利用三次，加密過程為“加密-解密-加密”，解密過程為“解密-加密-解密”。

?

?? ? 用公式可以表示為：

??? ? ?E_K1(D_K2(E_K3(P))) = C? ? //加密

??? ? ?D_K1(E_K2(D_K3(C))) = P? ? //解密

由于三次過程使用的密鑰不一樣，所以相當于增加了密鑰長度。實際應用中，K1和K3是相同的，也就是外層的兩次加密和兩次解密使用相同的密鑰。這樣，三重DES的密鑰長度就相當于K1+K2的長度，即112位(DES的密鑰長度為56位)。采用“加密-解密-加密”模式的理由是為了與DES保持兼容，只要設置K1=K2=K3，三重DES不就和DES一樣了嗎？只是多了兩道運算步驟而已。

三重DES只是DES的一個變種，還有其它變種，例如DESX、CRYPT(3)、GDES、RDES、sⁿDES等等。

3) AES，高級加密標準。也叫Rijndael算法，由兩位比利時密碼學家發明，參與了NIST（美國標準和技術委員會）1997年組織的公開密碼學競賽，最終以優異的技術特性勝出成為加密標準。AES以前一篇文章提到的迦羅瓦域理論為數學基礎。AES也是分塊對數據加密，只是塊的長度并不像DES那樣定死為64位。Rijndael的密鑰長度可以從128位起以32位為間隔遞增到256位。

Rijndael算法完全公開、安全性好、運算速度極快。如果取密鑰長度為128位，想用窮舉法破解密鑰，就算有一臺內含1000億個處理器的計算機，并且每個處理器每秒處理100億個密鑰，也要運行100億年才能搜索完整個密鑰空間。

4)?其它對稱密碼算法，有IDEA、Lucifer、Madryga、NewDES、FEAL、REDOC、LOKI、RC2、MMB、GOST、CAST、Blowfish、SAFER、3-WAY、RC5、等等，現在的密碼算法真是太多了。IDEA是International Data Encryption Algorithm（國際數據加密算法）的縮寫，該算法設計者是James Massey和Xuejia Lai（來學嘉）博士。來學嘉是瑞士籍華人，1954年出生，西安電子科大的碩士畢業生。James Massey是來學嘉的導師。

IDEA算法安全性比DES好(和AES差不多)，能抵抗差分密碼分析的攻擊，而DES不行。IDEA的加密速度比DES快，加密數據速率可達到177MB/秒，也和AES差不多。

【密碼學04】非對稱密碼算法

上一篇【密碼學03】對稱密碼算法?介紹了對稱密碼算法，其主要特性就是加密解密密鑰能互相推算，而實際應用中絕大多數對稱加密算法的加密密鑰和解密密鑰是相同的。正因為如此，加密者指定一個密鑰后，必須得想方設法把密鑰分發出去給解密者，同時還得小心翼翼確保密鑰不被泄露。這是對稱密碼算法固有的一個矛盾，如何解決呢？

還是前面提到的斯坦福兩位密碼學大師Diffie?和Helman，1976年提出了一種全新的密碼系統概念：非對稱密碼算法。下面看看非對稱密碼算法的特性。

與對稱密碼算法相反，非對稱密碼算法的加密密鑰和解密密鑰不相同，而且從加密密鑰推算出解密密鑰極其困難。簡單來說，非對稱密碼算法的特性如下：

1)???????E_K1(P) =C???//E：加密算法，K1：加密密鑰，P：明文，C：密文，下同。

D_K2(C) = P???//D：解密算法，K2：解密密鑰。

綜合上面兩個式子，可得：

D_K2(E_K1(P)) = P

2)???????從K1?_推斷出K2極其困難。如果密鑰長度足夠長，銀河系中的任何一種生物都應該不可能輕易從K1推出K2，或者從K2推算K1。

3)??某些優秀的非對稱密碼算法還具有如下特性，但不是所有的算法都具備：

E_K1(D_K2(P)) = P

也就是加密函數E與解密函數D互為反函數，解密函數可以當成加密函數來用，加密函數也可以當成解密函數來用。這個特性非常迷人。

具備前面兩個特性以后，加密密鑰就可以放心地公之于眾了。?Alice要用非對稱密碼算法秘密地傳送消息給Bob，過程是怎么樣的呢？首先Bob自己要生成一對密鑰BK1和BK2，他可以任意選擇一個密鑰比如BK1公布給所有人包括Alice，他自己保留BK2不讓任何人知道。Alice知道Bob?公開的密鑰BK1后，就可以用BK1加密明文P得到密文C，然后傳送給Bob。她不用擔心別人能解密消息，因為BK1加密的消息只有BK2才能解密，而BK2只有Bob才知道，想從BK1推算出BK2幾乎不可能。Bob收到消息，用私密的BK2解密即可得到明文。反過來，Bob要傳送消息給Alice，Alice也要先生成一對密鑰AK1和AK2，并按照同樣的過程進行。

由于非對稱密碼算法可以把加密密鑰公開，因此也叫做公開密鑰密碼算法，簡稱公鑰密碼算法，或公鑰算法。公鑰算法的確是非常優雅地解決了密鑰既要保密又要公開的矛盾。下面是一些常見的公鑰密碼算法。

1) RSA，是MIT（麻省理工學院）三個密碼學大師Rivest、Shamir、Adleman于1978年共同發表，因此名字就是三個人名的首字母。RSA是最優秀的公鑰算法，它滿足上面提到的全部三個特性。RSA算法的數學基礎是【密碼學02】密碼系統原理及數學背景?一文提到的因子分解。RSA算法經受住了密碼分析學家們三十年來的大量攻擊，雖然密碼分析學家們不能證明RSA是安全的，但也不能證明RSA是不安全的。RSA已經被廣泛使用，為整個地球村的信息安全尤其是電子商務的安全做出了極大貢獻。

2) El Gamal，該算法的數學基礎是【密碼學02】密碼系統原理及數學背景?一文中提到的“計算有限域中的離散對數”的難題。El Gamal算法也是非常優秀的公鑰密碼算法。

3)?其它公鑰密碼算法還有很多，例如背包算法、Rabin算法、Pohlig-Hellman算法、McEliece算法、基于橢圓曲線的算法、LUC算法等等。

關于背包算法，Tanenbaum的《Computer Networks》（4th）中講述了一個有趣的故事：背包算法設計這Merkle曾懸賞100美金破解該算法，RSA組合中的S，即Shamir迅速破解算法并領走獎金。Merkle于是增強了算法，再次懸賞破解，獎金加到1000美金。RSA組合中的R，即Rivest又迅速破解領走獎金。此后Merkle就沒再懸賞了，因此RSA組合中的另外一個人A，即Adleman也就沒能拿到預期的10000美金了。從這個故事可以看出RSA這個信息安全領域的黃金組合的確超級牛叉！

公鑰密碼算法非常優雅，但是幾乎所有的公鑰算法都有一個問題：速度太慢。RSA算法的速度是DES的1000分之一，并且密鑰越長，速度會急劇變慢。因此實際應用中密碼系統都是把公鑰密碼算法與對稱密碼算法結合在一起使用。

【密碼學05】加密模式

大多數密碼算法都是將明文切成固定長度的多個塊，以塊為單位進行加密，而不是逐個字節地加密數據。不管什么樣的密碼算法，任何時候當同樣的明文塊從算法前端輸入，同樣的密文塊就從后端輸出。入侵者可以充分發掘這種特性來協助攻破密碼系統。下面舉個例子來說明。

下面這個表描述的是三個人的年終獎金額度。

Alice	8000
Bob	12000
Trudy	3000

老板授權秘書MM整理好這張表后，秘書MM將其加密，然后提交給財務部門。為了清楚地描述問題，這里假設這張表的每個字段都是64位，而且剛好秘書MM用的加密算法的加密塊長度也是64位，那么加密結果可能就是像下面這個樣子：

As9d8912h3a98q 9SDJKVNI	9d89821as89982mHSLkp[anm
09djhASDFQWER78sdfHD,zx	0812UtWEQ23][;[]X/;;\DSKg5p
78723G/CC;D;LFSDF/;LXPASh	/.,;ISOFIWERIIOC7kjJKJDFNSAn

假設在秘書MM發送這段密文之前，不巧讓Trudy看到了。盡管Trudy看不懂這個表的內容，但是當秘書MM抱怨就兩個字段的表為什么么要定死每個字段長度為64位的時候，Trudy獲得了足夠的信息。她知道由于自己剛和老板吵過嘴，獎金肯定沒有其它人高，于是她嘗試將這些密文塊的順序調整了一下，變成下面這個樣子：

As9d8912h3a98q 9SDJKVNI	0812UtWEQ23][;[]X/;;\DSKg5p
09djhASDFQWER78sdfHD,zx	/.,;ISOFIWERIIOC7kjJKJDFNSAn
78723G/CC;D;LFSDF/;LXPASh	9d89821as89982mHSLkp[anm

僅僅是調整一下密文塊的順序，財務部解密消息的時候完全察覺不到有任何異常。盡管Trudy還是不知道獎金是多少，但是可以很有把握地相信自己的獎金會比原來高。

為了對抗這種問題，需要采取某種加密模式，需要把各個密文塊關聯起來，使得密文任何一處有異常更改，都會導致整個密文作廢。常見的加密模式有以下這。

1) 電子密碼本模式:ECB。這個不用再介紹了，就上面講的有問題的這種模式，每塊明文都對應自己的密文塊，互不相干。雖然有問題，但它也是一種模式，呵呵。

2) 密碼塊鏈模式:CBC。每個純文本塊在加密前，通過按位“異或”操作與前一個塊的密碼文本結合。這樣確保了即使純文本包含許多相同的塊，這些塊中的每一個也會加密為不同的密碼文本塊。在加密塊之前，初始化向量通過按位“異或”操作與第一個純文本塊結合。如果密碼文本塊中有一個位出錯，相應的純文本塊也將出錯。此外，后面的塊中與原出錯位的位置相同的位也將出錯。下圖是CBC加密模式示意圖。

3) 密碼反饋模式。將少量遞增的純文本處理成密碼文本，而不是一次處理整個塊。該模式使用在長度上為一個塊且被分為幾部分的移位寄存器。例如，如果塊大小為 8 個字節，并且每次處理一個字節，則移位寄存器被分為 8 個部分。如果密碼文本中有一個位出錯，則一個純文本位出錯，并且移位寄存器損壞。這將導致接下來若干次遞增的純文本出錯，直到出錯位從移位寄存器中移出為止。CFB加密模式示意圖如下。

?

4) 輸出反饋模式。將少量遞增的純文本處理成密碼文本，而不是一次處理整個塊。此模式與?CFB?相似；這兩種模式的唯一差別是移位寄存器的填充方式不同。如果密碼文本中有一個位出錯，純文本中相應的位也將出錯。但是，如果密碼文本中有多余或者缺少的位，則那個位之后的純文本都將出錯。

5) 流密碼模式。用一個密鑰加密一個初始向量生成一個輸出塊，然后用同樣的密鑰對這個輸出塊進行加密以得到第二個輸出塊，再用同樣的密鑰對這個輸出塊進行加密得到第三個輸出塊，以此類推。所有這些塊的序列叫做密鑰流。逐塊輸出密鑰流時，就逐塊與明文異或，輸出的就是密文。

6) 計數器模式。用一個密鑰加密一個初始向量生成輸出塊，然后將初始向量加1再用同樣的密鑰加密輸出第二個輸出塊，以此類推。輸出的塊序列也是密鑰流，逐塊輸出密鑰流時，就逐塊與明文異或，輸出的就是密文。

7) CTS(密碼文本竊用模式)。處理任何長度的純文本并產生長度與純文本長度匹配的密碼文本。除了最后兩個純文本塊外，對于所有其他塊，此模式與CBC?模式的行為相同。

【密碼學06】數據塊填充模式

大多數密碼算法都是塊密碼算法，需要將明文消息切成固定大小的塊，一塊一塊地進行加密。例如DES就需要將消息切割成一個個64位的塊。如果消息長度不是64的整數倍，最后一個消息塊就不夠64位，這時就要對最后一個消息塊進行填充。填充本身是很簡單的事情，問題在于有很多種可行的填充方式，如果加密時以某種方式填充，解密時就得理解這種填充方式并去除填充內容，否則很可能解密出來得到的數據就是臟數據。

某些加密標準指定了特定的填充方案。下面簡單描述一下這些模式的工作原理。

假定塊長度為8字節，要加密的明文數據長度為9字節。那么消息被切成兩個塊，第二塊只有1個字節，需要填充7個字節。假定9字節的明文數據如下：

F1 F2 F3 F4 F5 F6 F7 F8 F9

以下是常見的四種填充方式：

1) Zeros填充：全部填充為0的字節，結果如下：

?????? F1 F2 F3 F4 F5 F6 F7 F8?? //第一塊
?????? F9?00 00 00 00 00 00 00? //第二塊

2) X923 填充： 填充為0的字節序列，最后一個字節記錄填充的總字節數，結果如下：

?????? F1 F2 F3 F4 F5 F6 F7 F8?? //第一塊
?????? F9 00 00 00 00 00 00 07? //第二塊

2) PKCS7 填充： 每個填充的字節都記錄了填充的總字節數，結果如下：

??? F1 F2 F3 F4 F5 F6 F7 F8?? //第一塊
??? F9 07 07 07 07 07 07 07? //第二塊

3) ISO10126 填充： 填充隨機字節序列，最后一個字節記錄填充的總字節數，結果如下：
???? F1 F2 F3 F4 F5 F6 F7 F8?? //第一塊
???? F9 7D 2A 75 EF F8 EF 07? //第二塊

總結

以上是生活随笔為你收集整理的密码学基本介绍的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。