第1章 密碼學和數據安全導論

1.1 密碼學及本書內容概述

1.密碼學（cryptology）：密碼編碼學（cryptography）和密碼分析學（破譯密碼）舷蒲。

2.密碼使用學的三個主要分支：對稱算法（Symmetric Algorithm）遵蚜，非對稱算法（Asymmetric Algorithm）或公鑰算法（Public-Key Algorithm）脱货，密碼協議（Cryptographic Protocol）维咸。

1.2 對稱密碼學

1.基本概念：明文帚湘，密文咙咽，密鑰玛瘸，密鑰空間（所有可能密鑰組成的集合）栓霜，安全信道（用于在通信雙方間安全地分配密鑰）翠桦。

2.安全地傳輸消息地問題最后可以歸結為安全地傳輸和存儲密鑰地問題。

3.簡單對稱加密：替換密碼

例如胳蛮，A被k替換销凑，B被d替換。

替換表是這種密碼體制地關鍵仅炊，需要在Alice和Bob之間安全傳輸斗幼。

第一個攻擊：蠻力攻擊或窮盡密鑰搜索。x(明文)抚垄，y(密文)蜕窿，K={k1,k2,...,kk}，攻擊將檢查每個ki呆馁，判斷是否等于桐经。

第二種攻擊：字母頻率分析。密文中某個出現頻率最高地字母可能是英文語言中最常用的一個字母的替換字母浙滤。

（1）確定每個密文字母的頻率阴挣；（2）連續(xù)的兩個，三個或四個等密文字母的頻率瓷叫；（3）高頻的短單詞屯吊。

好的密碼應該隱藏被加密文本的統計屬性送巡，僅僅密鑰空間大是不夠的。

1.3 密碼分析

1.破譯密碼體制的一般思路

①經典密碼分析：從密文y中恢復明文x盒卸，或從密文y中恢復密鑰k骗爆。

密碼分析可分為兩類：一類是發(fā)現加密方法內部結構的分析攻擊；另一類是將加密算法看作是黑盒蔽介，試圖測試所有可能密鑰摘投。

②實施攻擊：旁道分析。

③社會工程攻擊：強迫某個人說出密鑰虹蓄，騙取密鑰犀呼。

2.可靠的密碼體制必須遵守Auguste Kerckhoffs在1883年提出的Kerckhoffs原理。

Kerckhoffs原理：即使除密鑰外的整個系統的一切都是公開的薇组，這個密碼體制也必須是安全的外臂。尤其是即使攻擊者知道系統的加密算法和機密算法，此系統也必須是安全的律胀。

3.關于密鑰長度的討論

只有在蠻力攻擊是最好的攻擊方法時宋光，討論對稱加密算法中密鑰長度的問題才有意義。

在安全性相當的情況下炭菌，對稱算法和非對稱算法所要求的密鑰長度完全不同罪佳。

使用蠻力攻擊成功破解不同長度密鑰的對稱算法預計時間：56~64位——短期幾小時或幾天，112~128位——長期幾十年黑低，256位——量子計算機幾十年赘艳。

1.4 模運算與多種古典密碼

1.模運算

定義：假設a,r,mZ(所有整數的集合)，如果m除a的余數為r克握，則可記作ar mod m蕾管，m為模數，r為余數玛荞。

計算余數：r = a - q*m

等價類：余數不唯一娇掏。模數9存在9個等價類：

{...,-27,-18,-9,0,9,18,27,...}呕寝，{...,-26,-17,-8,1,10,19,28,...}勋眯，...，{...,-19,-10,-1,8,17,26,35,...}

等價類中所有成員的行為等價：對于一個給定模數m下梢，選擇同一個等價類中任何一個元素用于計算的結果都是一樣的客蹋。

例如：

通常選擇余數為

2.整數環(huán)

，其中任意兩個數的加法和乘法運算模m的結果仍屬于

加法逆元始終存在：

乘法逆元不一定存在：孽江，當且僅當時讶坯，即a和m的最大公約數為1時，a存在乘法逆元岗屏。

思考：為什么a和m互質時辆琅，a存在乘法逆元漱办？

3.經典替換密碼

凱撒密碼：將明文中的每個字母在字母表中移動固定長度的位置。

仿射密碼：將銘文乘以密鑰的一部分婉烟，然后再加上密鑰的剩余部分娩井。

缺點：密鑰空間小，易窮舉破解似袁；明文和密文之間的映射關系是固定的洞辣，易用頻率分析方法破解。

第二章 序列密碼

2.1 引言

1.對稱密碼可以分為序列密碼和分組密碼昙衅。

序列密碼：單獨加密每個位扬霜，將密鑰序列中對應的一位與明文的一位相加后模2。

分組密碼：每次使用相同的密鑰加密整個明文位分組而涉。

2.序列密碼中加密和解密使用相同的函數著瓶。

可以證明解密函數的確可以得到明文位，即將代入到解密函數中啼县，能得到明文蟹但。

這得益于的值總是0。

3.為什么可使用簡單的模2加法來進行加密谭羔？

模2加法與XOR（異或）運算是等價的华糖。

對于一位明文無論是0或1，如果密鑰位完全隨機瘟裸，密文為0或1的概率完全相等客叉。

4.密鑰序列位的本質是什么？

密鑰序列（即所有)是序列密碼安全性的核心問題话告。序列密碼的安全性完全取決于密鑰序列兼搏。

密鑰序列位的核心要求是對攻擊者而言它必須看上去是隨機的。

2.2 隨機數與牢不可破的分組密碼

1.隨機性對于序列密碼的安全性十分重要沙郭，三種隨機數生成器（RNG）：

真隨機數生成器（TRNG）：輸出不可復制佛呻，基于物理過程（例如拋硬幣，擲色子等）生成序列病线。

偽隨機數生成器（PRNG）：從一個初始種子值開始通過各種計算得到序列吓著。一個廣泛使用的例子是ANSI C中的rand()函數，它的參數為：對PRNG的一個一般要求是送挑，它必須擁有良好的統計屬性绑莺，意味著它的輸出近乎與真隨機數序列相同。

加密安全的偽隨機數生成器：是PRNG的一個特例惕耕，具有不可預測性纺裁。即給定密鑰序列中的n個連續(xù)位，不存在一個時間復雜度為多項式的算法使得成功預測下一位概率超過50%。之前的任何一位也是不可計算的欺缘。

2.無條件安全

如果一個密碼體制在無限計算資源的情況下也不能被破譯栋豫，則說明它是無條件安全的或信息理論上安全的。

2.一次一密：一個簡單的無條件安全的密碼

通過真隨機數生成器得到密鑰序列谚殊；只有合法的通信方才知道密鑰序列笼才；每個密鑰序列位僅使用一次。

缺點1：密鑰長度必須和明文長度一樣络凿。

缺點2：密鑰只能使用一次骡送，傳輸代價高。

3. 實際使用的序列密碼

使用偽隨機數生成器替換真隨機密鑰序列位絮记，其中密鑰k是種子摔踱。

是計算安全，而非無條件安全怨愤。

4.計算安全

如果為破解一個密碼體制派敷，最好的已知算法需要至少t個操作，則說明此密碼體制是計算安全的撰洗。

5.利用PRNG構建密碼流

PRNG可以用來生成密鑰流篮愉，但是對序列密碼而言是不夠的，因為對手攻擊也很聰明差导。

假設一個基于線性同于發(fā)生器的PRNG试躏，其密鑰包含值（A，B）设褐。假如攻擊者知道明文的前300位颠蕴，由于模數m是公開已知的，在密文的基礎上助析，可以推出密鑰序列的前300位犀被，進而推出A和B（的多個解）。如果得到已知明文的第四片信息外冀，就可以唯一的檢測出密鑰寡键。

也就是說，如果已知一些明文片段雪隧，我們可以計算出密鑰并解密整個密文西轩。

6.利用CSPRNG構建密鑰序列

相當一部分在密碼學之外使用的偽隨機數生成器都不是密碼學安全的。

實際中的序列密碼有三種：①針對軟件實現優(yōu)化的密碼膀跌，計算一個密鑰序列為通常需要更少的CPU指令遭商；②針對硬件實現優(yōu)化的密碼，一個典型的例子是反饋移位寄存器捅伤；③將分組密碼作為基本塊來實現序列密碼。

2.3 基于移位寄存器的序列密碼

一種得到長偽隨機序列的簡單方法就是使用線性反饋移位器寄存器（LFSR）巫玻，典型的LFSR是A5/1密碼和A5/2密碼丛忆，它們作為標準被用于GSM手機網絡中手機與基站之間的語音加密祠汇。

1. 線性反饋移位寄存器（LFSR）

由若干時鐘存儲元件（觸發(fā)器）和一個反饋路徑組成。

一個擁有m個觸發(fā)器的LFSR可以稱為“度為m”熄诡。

反饋路徑計算一位寄存器中某些觸發(fā)器的XOR和可很，并將其作為上一個觸發(fā)器的輸入。

某條反饋路徑是否活躍則取決于反饋系數凰浮，將觸發(fā)器的輸出與它對應的系數相乘?,表示反饋是活躍的我抠，對應觸發(fā)器的輸出均為0。

LFSR有時也稱為線性遞歸袜茧。

度為的LFSR可以產生的最大序列長度為菜拓。

在針對單個LFSR的已知明文攻擊中，一旦敵手知道了反饋系數笛厦，就可以構建LFSR纳鼎，并加載他已經知道的任意個連續(xù)的輸出位。

2. Trivium

是一個較新的序列密碼裳凸，它的密鑰長度位80位贱鄙，是基于三個移位寄存器的組合。

這三個寄存器的長度分別為93姨谷、84和111位逗宁，總長度288。

每個寄存器的輸出都與另一個寄存器的輸入相連梦湘，寄存器以一種類似環(huán)的形式排列疙剑。

使用Trivium加密時需要兩個輸入參數（密鑰和初始向量），主要目的是即使在密鑰不改變的情況下践叠，此密碼產生的兩個密鑰序列也必須不同言缤。如果不適用變化的，序列密碼也是高度確定的禁灼。

與絕大多數的分組密碼（比如AES）相比管挟，這個硬件實現相對較小但卻非常快弄捕。

3. eSTREAM項目

為推動序列密碼設計為項目目標僻孝。

分為兩種配置，分別是針對要求高吞吐量的軟件應用程序而設計的密碼和針對資源有限（比如有限存儲守谓、有限門數量或有限功耗）的硬件應用程序而設計的密碼穿铆。

在收到的34個候選密碼中，滿足希望屬性的由4個面向軟件（配置1）的密碼和3個面向硬件（配置2）的密碼斋荞。

面向軟件：HC-128荞雏、Rabbit、Salsa/12和SOSEMANUK。

面向硬件：Grain V1凤优、MICKEY V2和Trivium悦陋。

4. 真隨機數的生成

所有TRNG都需要利用一些熵源，即一些真正隨機的過程筑辨。

大致分為兩類：一類是使用專門設計的硬件作為熵源的方法俺驶，例如半導體噪音、不相關的振蕩器棍辕；另一類是利用外部隨機源的TRNG暮现，例如在網絡接口中計算觸鍵間隔或包的到達時間的計算機系統。

第三章 數據加密標準與替換算法

在過去30年的大多數時間里楚昭，數據加密標準（Data Encryption Standard栖袋， DES）是最主流的分組密碼。

3.1 DES簡介

1. 起源

1972哪替，美國標準局（NBS）號召在美國實行標準密碼栋荸。

1974，NBS從IBM的一個密碼研究小組提供的方法中找到一個基于Lucifer密碼的加密算法DES凭舶。

1977晌块，NBS發(fā)布了修訂后的IBM密碼的所有規(guī)范，將其命名為數據加密標準（FIPS PUB 46）帅霜，此時DES的有效期設置為1987年匆背。

1987，NIST重新聲明對DES的使用推遲至1999年身冀。

1999钝尸，DES最終被高級加密標準（AES）所取代。

2. 基本操作

混淆（Confusion）：一種使密鑰與密文之間的關系盡可能模糊的加密操作搂根。常用的方式是替換珍促。

擴散（Diffusion）：一種為了隱藏明文的統計屬性而將一個明文符號的影響擴散到多個密文符號的加密操作。最簡單的方式是位置換剩愧。

乘積密碼（Product cipher）：將擴撒操作串聯起來建立的更為強壯的密碼猪叙。

擴散屬性：意味著修改明文中的1位將會導致平均一半的輸出位發(fā)生改變，即第二位密文看上去與第一位密文完全沒有關系仁卷。例如：明文和采用分組密碼擴散之后得到的密文分別是和穴翩。

3.2 DES算法概述

1. DES是一種使用56位密鑰對64位長分組進行加密的密碼。

2. DES的整體設計

DES是一種對稱密碼锦积，其加密過程和解密過程使用相同的密鑰芒帕。

DES是一種迭代算法，每個分組的加密過程都包含16輪丰介，每輪的操作完全相同背蟆。

DES使用的是Feistel網絡鉴分，其結構主要包括對明文進行初始置換、進行16輪操作淆储、逆初始置換得到密文冠场。

在每一輪操作中家浇，明文會被分為和兩部分本砰，會被送入函數中，的輸出將與進行異或钢悲，最后左右兩部分進行交換進入下一輪点额。每輪中的輪密鑰均來自56位的主密鑰，生成過程是通過密鑰編排（key schedule）實現的莺琳。函數內部實現擴散和混淆还棱。

3. DES的內部結構

初始置換和逆初始置換：均是按位置換，可以看作是簡單的交叉連接惭等，即將第58位放在第1位珍手，將第50位放在第2位等，存在一個初始置換表和逆初始置換表辞做，兩個表互逆琳要。

函數：將輸入分成位的分組，然后將其擴展為位（E-盒）秤茅，然后再將每組位數放入S-盒中進行置換成位稚补。擴展的方法是將某一位插入到不同的分組中，存在一張擴展表框喳。所有S-盒中的置換表都不相同课幕，作用是將位值映射為位，表格的讀取方式是將最高位和最低位組合起來選擇行五垮，中間4位選擇列乍惊。例如市埋，S-盒的輸入佩耳，行為，列為书幕，查表得到08匙监，即凡橱。S-盒是DES中最重要的元素，因為S-盒在密碼中引入了非線性亭姥，即稼钩。S-盒 可以抵抗各種高級的數學攻擊，尤其是差分密碼分析达罗，而差分密碼分析直到1990年的一次學術論壇上才第一次被公開坝撑，當時IBM小組宣稱設計者早在16年前就已經直到此攻擊的存在静秆，并說明DES就是專門為了抵抗差分密碼分析而設計的。

密鑰編排：從原始的56位密鑰中得到16個輪密鑰巡李，輪密鑰又稱子密鑰抚笔。56位密鑰首先及逆行一次置換選擇，然后分為和兩部分侨拦，然后分別對每一部分進行循環(huán)移位殊橙，每循環(huán)移位一次得到56位密鑰，進行一次置換選擇后輸出為一個子密鑰狱从。

3.4 解密

DES的優(yōu)勢之一是其解密過程與加密過程在本質上是完全相同的膨蛮。解密過程中輪密鑰采用密鑰編排逆轉生成。解密函數的每輪操作都是DES加密中對應輪的逆季研。第一輪解密后得到的結果實際上與最后一輪加密前的結果相等敞葛。

3.5 DES的安全性

1. 密碼攻擊可以分為窮盡密鑰搜索攻擊（或蠻力攻擊）與分析攻擊。

2. 在DES提出后不久与涡，針對DES密碼強度的批評主要圍繞以下兩個方面：(1) 密鑰空間太腥切场；（2）可能存在利用S-盒數學屬性的分析攻擊驼卖。利用窮盡密鑰搜索攻擊就可以較容易地破解單重DES氨肌，但至今還沒發(fā)現能高效破解多重DES地攻擊方式。

3. DES窮盡密鑰搜索

輸入：至少一個明文密文對

輸出：滿足的

攻擊：測試所有個可能的密鑰款慨，直到以下條件成立：

（找到錯誤密鑰的可能性只有儒飒，錯誤密鑰指的是只能正確解密一個密文而不能正確解密后續(xù)密文的密鑰。）

普通計算機并不適合用來執(zhí)行次密鑰測試檩奠，但可以選擇專門用來搜索密鑰的機器桩了。

（1）1993 CRYPTO，Michael Wiener提出了一種非常高效的密鑰搜索機器設計方案埠戳，該方案使用的是管道技術井誉。

（2）1988年，EFF構建了一個硬件機器整胃，叫Deep Crack颗圣，它使用蠻力攻擊可以在56個小時內破解DES。

（3）2006年屁使，來自德國波鴻大學和基爾大學一個研究學者小組基于商業(yè)集成電路構建了COPACOBANA機器破解DES的搜索時間平均不到7天在岂。

56位的密鑰大小已經不足以保證當今機密數據的安全性。

4. 分析攻擊

1990蛮寂，Eli Biham和Adi Shamir發(fā)現了所謂的差分密碼分析（DC）理論上可以破解任何分組密碼蔽午，但DES的S-盒可以很好地抵抗這種攻擊。

1993酬蹋，公布了線性分析攻擊（LC）及老。

DC和LC成功地發(fā)動一次攻擊分別需要知道和個明文-密文對抽莱，這些數字看上去非常不切實際，因為：（1）攻擊者需要知道相當多的明文骄恶；（2）搜集和存儲這樣大地數據量需要花費相當長地時間食铐，也需要相當大地內存資源；（3）攻擊只能恢復一個密鑰僧鲁。

3.6 軟件實現與硬件實現

軟件實現是指在桌面CPU或類似智能卡或手機地嵌入式微處理器上運行DES虐呻。硬件實現是指在諸如專用集成電路（ASIC）或現場可編程門陣列（FPGA）的IC上運行DES實現。

1. 軟件實現：最常見的思路是使用一些表悔捶，這些表里的數據來自于一些DES操作預計算的值铃慷，例如一些S-盒預計算的值盒置換預計算的值单芜。DES中使用的小型S-盒在硬件實現上非常高效蜕该，但在現代CPU上的效率一般。加快DES軟件實現的一個值得注意的方法是位分片（bitslicing）洲鸠。

2. 硬件實現：DES的一個設計標準就是硬件實現的效率堂淡，類似E置換、P置換扒腕、IP置換和IP^-1置換的置換操作非常易于用硬件實現绢淀，因為它們只需要布線而不需要邏輯，通常使用布爾邏輯實現瘾腰，即邏輯門皆的。

3.7 DES的替換算法

1. AES（Advanced Encryption Standard，高級加密標準）：密鑰長度有128位蹋盆、192位和256位三種费薄，目前沒有出現成功破譯AES的分析攻擊。

2. 3DES與DESX：三重DES栖雾，即由三個連續(xù)的DES加密組成楞抡，可以表示為，其中是三個不同的密鑰析藕。3DES在硬件實現上非常高效召廷，但在軟件實現上卻不那么高效。增強DES的另一種方法是使用密鑰漂白账胧，做法為在DES算法之前和之后將明文和密文分別與另外兩個64位密鑰和進行異或操作竞慢，可以表示為。

3. 輕量級密碼PRESENT：輕量級是指實現復雜度非常低的算法治泥，尤其指硬件實現方面筹煮。PRESENT是一個替換-置換網絡，由31輪組成车摄。

第四章 高級加密標準

高級加密標準（AES）是目前使用最為廣泛的一種對稱密碼寺谤。

1. AES的發(fā)展歷程

3DES的軟件實現并不高效仑鸥，其分組大小相對較小，如果要防止量子計算機攻擊DES变屁，密鑰長度最好應該接近256位眼俊。

1997年，NIST提出向社會征集新的高級密碼標準（AES）粟关。

2001年疮胖，NIST宣布分組密碼Rijndael成為新的AES，它由比利時的兩位年輕密碼學家Joan Daemen和Vincent Rijmen設計闷板。

2. AES算法概述

AES的輸入澎灸、密鑰、輸出均為128位遮晚。明文在AES中的每一次迭代都成為一種狀態(tài)性昭。

AES由三種類型的層組成，分別由10輪的字節(jié)代換層县遣、擴散層和密鑰加法層組成糜颠。

字節(jié)代換層（S-盒）：狀態(tài)中的每個元素都使用具有特殊數學屬性的查找表進行線性變換。

擴散層：包括ShiftRow（行移位變化）層盒MixColumn（列混淆變換）層萧求。

密鑰加法層：128位輪密鑰（又稱子密鑰）來自于密碼編排中的主密鑰其兴，它在該層與狀態(tài)進行異或操作。

3. AES的內部結構

16字節(jié)的輸入按字節(jié)輸入到S-盒中夸政，16字節(jié)的輸出先在ShiftRows層按字節(jié)進行置換元旬，然后由MixColumn變換進行混淆。最后將128位的子密鑰與中間結果進行異或計算守问。

AES是一個面向字節(jié)的密碼匀归，DES使用了大量的位置換，可以看作是擁有面向位的結構酪碘。

AES的16個字節(jié)按照4字節(jié)乘4字節(jié)的矩陣排列朋譬。

字節(jié)代換層的S-盒代換是一個雙向映射，即個可能的輸入元素都與一個輸出元素一一對應兴垦。S-盒通常使用一個擁有固定項的徙赢、256位乘8位的查找表實現。字節(jié)代換層的操作可以表示為探越，不存在的輸入值狡赐。

擴散層由兩個子層組成，分別為ShiftRow變換和MixColumn變換钦幔。ShiftRow變換循環(huán)往復地將狀態(tài)矩陣地第二行向右移動三個字節(jié)枕屉，將第三行向右移動兩個字節(jié)，將第四行向右移動一個字節(jié)鲤氢。MixColumn步驟是一個線性變換搀擂，它混淆了狀態(tài)矩陣地每一列西潘。長度為4字節(jié)地每列都可以看作是一個向量（向量的每個元素是一個字節(jié)），該向量與一個固定的的矩陣相乘哨颂，此矩陣包含常量的項喷市。

密鑰加法層的兩個輸入分別是16字節(jié)的當前狀態(tài)矩陣和長度為16字節(jié)的子密鑰，這兩個輸入是通過按位異或操作組合在一起威恼。

密鑰編排將原始輸入密鑰（128位品姓、192位或256位）作為輸入，得到AES每輪使用的子密鑰箫措。子密鑰的個數等于輪數加一腹备，這是因為第一個密鑰加法層進行密鑰漂白時也需要密鑰。AES子密鑰的計算是遞歸的斤蔓，即為了得到子密鑰植酥，子密鑰必須是已知的。AES的密鑰編排是面向單詞的附迷，其中1個單詞=32位惧互，子密鑰存儲在一個由單詞組成的擴散密鑰數組中。

128位密鑰AES的密鑰編排：11個子密鑰存儲在元素為的擴散密鑰數組中喇伯，其中對應。11個密鑰可以預先被計算出來拨与，然后再對明文進行加密或對密文進行解密稻据。也可以在對明文（密文）進行加密（解密）的過程中，每輪都會產生一個新的子密鑰买喧。