密码学复习（上）
目錄
一、密碼學概述
密碼學定義
密碼學與信息安全：
攻擊：
密碼學分類
密碼編碼學：
對稱密碼體制
非對稱密碼體制：
保密體制模型：
密碼分析學：
密碼體制的攻擊類型：
不同時期的密碼學
二、古典密碼學
1.置換密碼
置換
周期置換
列置換
2.代換密碼
補充數論、模運算知識
單表代換密碼
多表代換密碼
3.古典密碼的分析
三、分組密碼
1.分組密碼（塊密碼）概述 ?????
分組密碼的設計要求
分組密碼的設計原則
?Feistel網絡
SP網絡
2.DES
DES的安全性
3.AES
4.分組密碼的工作模式
電子密碼本模式（Electronic Code Book, ECB）
密碼分組鏈接模式（Cipher Block Chaining，CBC）
密碼反饋模式（Cipher Feedback Block，CFB）
輸出反饋模式（Output Feedback Block，OFB）
計數器模式（Counter，CTR）?
?錯誤影響
一、密碼學概述
密碼學定義
密碼學一種狹義定義:
????? 是一種保密通信技術，通過對信息進行加密和解密，在第三方監聽的情況下，實現信息的安全傳輸。
廣義上講，密碼學不只是保密通信技術，已經延伸至信息安全諸多領域（是信息安全的基礎和核心）
如：
? 數據完整性檢測
? 消息認證
? 數字簽名
更多地 ：
?保密通信、存儲加密、用戶身份驗證、區塊鏈、隱私計算、零知識證明、安全多方計算
聽起來很高大上，但其實大部分核心技術就是用之后講的哈希函數。。。
在狹義密碼學中，根據定義，自然離不開明文--加密--》密文-- 解密--》明文的過程。
與國際接軌，常用英文來表示（之后會經常用到）
消息：
?? 明文 （Plaintext) 常用p表示
?? 密文?? （Ciphertext） 常用c表示
算法? ：
????? 使用密鑰? 一般用k表示
?????? 加密（Encryption) 加密函數一般用 E（）表示? c=(p)
????? 解密? （Decryption)? 解密函數一般用 D( )表示??
密碼學與信息安全：
? 經典信息安全三要素:? 機密性、完整性、可用性 confidentiality、Intergerity availability
（CIA！！）
? 拓展：機密性，完整性，可用性，隱私性，可認證性與可信賴性，不可抵賴性，可說明性，可審計性。
? 其中與密碼學相關的：機密性，完整性，可用性，認證性、不可抵賴性
攻擊：
如圖所示
中斷 （拒絕服務）? 阻止或禁止通信設施的正常使用 兩種實現方式：1.攻擊者刪除傳輸過程中某個地方的鏈接。2.DDos，對特定目標濫發消息使之過載
截取
篡改
偽造
重放??? 是指攻擊者發送一個目的主機已接收過的包，來達到欺騙系統的目的
對安全性的攻擊
中斷:? 可用性
截取：機密性
篡改：完整性、真實性、有序性
偽造、重放：認證性
分類：
?? 被動攻擊：截取。通常難以檢測
?? 主動攻擊：中斷、篡改、偽造、重放。是指攻擊者對連接中通過的協議數據單元進行各種處理
密碼學分類
密碼學的技術分兩部分，一個是密碼編碼學、一個是密碼分析學。
密碼編碼學研究如何對信息編碼以實現信息和通信安全
密碼分析學研究如何破解或攻擊受保護的信息
密碼編碼學：
從安全目標來看，分為保密體制和認證體制
根據使用密鑰策略，分為對稱密碼體制和非對稱密碼體制
對稱密碼體制
密鑰完全保密，加密密鑰和解密密鑰相同，或根據一個可以很容易推出另一個
優點：
? 運算速度比較快、密鑰相對較短、密文長度往往與明文長度相同
缺點：
?密鑰分發需要安全通道、密鑰量大，難以管理（不同人給的密鑰要不同）、難以解決不可否認問題
非對稱密碼體制：
?使用兩個密鑰：一個公鑰對外公開，一個私鑰只有擁有者知道 理論上不能從公鑰推出私鑰
例如電子郵件機制:任何人可以用接收者的公鑰進行加密（找到接受者的郵箱地址發送），接收者用私鑰解密（登錄賬號密碼，來查看郵件)
???????????????????????????????????????????????????? 加解密算法和數字簽名算法
優點：
密鑰分發容易、密鑰管理簡單、可以有效實現數字簽名
缺點：
運算速度較慢、密鑰位數相對多些、密文長度往往大于明文長度。（？？學到時再回來看）
保密體制模型：
明文空間P：所有可能的明文
密文空間C：所有可能的密文
密鑰空間K：所有可能的密鑰 ?? K1 加密密鑰空間 K2 解密密鑰空間
? 加密算法 ? c=(p)
?解密算法??
密碼分析學：
現代密碼學的密碼系統設計必須遵循柯克霍夫原則，秘密必須完全寓于密鑰中，加密和解密的安全性取決于密鑰的安全性，加密解密算法是公開的。只要密鑰安全，攻擊者就無法得到明文。
安全性分為無條件安全性（理論安全性）和有條件安全性（實際安全性）
密碼體制的攻擊類型：
在不知道密鑰的情況下，不同條件下的攻擊
唯密文攻擊：只知道一定數量密文
已知明文攻擊：除了一部分密文，還有一些明密文對
選擇明文攻擊：對任意明文可得到其密文，比如掌握加密機時
選擇密文攻擊：對任意密文可得到其明文，比如掌握解密機時
選擇文本攻擊:? 選擇明文和選擇密文的結合，同時掌握加密機和解密機時
不同時期的密碼學
按照1949年香農發表的那篇論文《保密系統的通信理論》為分界
古典密碼學：主要分為代換式密碼和置換式密碼兩大類
現代密碼學：計算機的出現提供了新的加密技術，也提供了破譯密碼的新武器
主要有 對稱密碼體制下的分組密碼，序列密碼
二、古典密碼學
主要通過置換和代換的簡單方式實現
1.置換密碼
置換：根據一定的規律重新排列明文，一遍打破明文的結構特性。
本質是X域上的雙射函數
常見的有列置換和周期置換兩種
置換
表示方式：
密鑰空間大小為 |x|!
逆置換：函數的逆函數
由得到
1.雙行表示法的上下顛倒，重新排序
2.循環表示法每個括號第一個不變，其余顛倒
置換的組合? 類比函數關系的組合
周期置換
密鑰：對m個元素集合的一個置換σ 加密：將明文p按固定長度m分組，對每個分組用σ進行置換，將各分組重新組合得到密文c 解密：將密文c按固定長度m分組，對每個分組用σ的逆置換σ-1進行置換，將各個分組重新組合得到明文p 使用矩陣形式表達更易于操作列置換
明文按照密鑰的規則按列換位并且按列讀出明文序列得到密文
2.代換密碼
將明文中的字符替換為其他字符的密碼體制 所采取的代換機制本身就構成了密鑰，通常是一個代換表 按一個明文字母是否總是被一個特定的字母代替進行劃分，分為： 單表代換 多表代換補充數論、模運算知識
對任意正整數m,整數n，存在唯一的q，r 使 n = qm + r 成立
q稱為商(quotient)，r稱為m除n的余數(remainder)
r=0時
? m整除n，寫作 m | n
m稱為n的因數或約數（divisor)，n是m的倍數(multiple)
若r！=0 則m n
素數或質數：因數只有1和自身的大于等于2的正整數
合數：不是素數的大于等于2的正整數
0，1 既不是素數也不是合數
最大公約數? m,n約數中最大的 記作gcd(m,n)
互質 ：gcd（m,n)=1 （素數之間一定互質，互質的不一定是素數）
最小公倍數? m，n共同的倍數最小的? lcm(m,n) =m*n/gcd(m,n)
任意一個大于1的正整數都可以分解為一串素數的乘積，分解是唯一的
?
線性同余
m,n互質，存在整數x,y 使 mx+ny=1
同余定理
a≡b(mod m)
如果兩個整數a和b滿足a-b能夠被m整除，即(a-b)/m得到一個整數，那么就稱整數a與b對模m同余
完全剩余系?? 完全剩余系內的加乘運算
乘法逆元
?對于模運算的除法，都用乘法逆元轉化為乘法（小數無法取模啊）
簡化剩余系
歐拉函數
ax+by=gcd(a,b),求x,y
裴蜀定理
利用拓展歐幾里得算法
費馬定理求逆元 前提p是質數
費馬小定理 a^(p-1) 模p 與1同余
a mod p的逆元 就是 a^(p-2)mod p
p不是質數是用拓展歐幾里得ax+by=1 算
b*i mod p x b*i*xmod p
（r了，寫到這垃圾csdn出了bug沒自動保存還退回去了？，就寫個簡化版的算了）
單表代換密碼
1.基于密鑰的單表代換密碼 給出一串無重復字母的字符串，明文a,b,c,d..依次對應于該字符串，明文中后面的其他字母順序對應于剔除了該字符串的字母表 密文空間=明文空間=26 密鑰空間=26！ 2.仿射密碼 是一個線性變換 稱e(x)為仿射加密函數 要求a與26互素，不然會有兩個數被加密為同一個密文 凱撒密碼 ： a=1,b=3 （是移位密碼，仿射密碼的特例） 密鑰空間：12*26=312 逆變換： 注意！：a~z被映射為數字0~25 a對應0多表代換密碼
明文消息中出現的同一個字母，不是完全被同一固定的字符代換，而是根據其出現的位置次序用不同的字母代換。
代換既取決于具體字母，也取決于字符的相對位置(不同的地方用不同的代換表）
多表代換中有理論上的非周期多表代換密碼，實際使用的都是周期多表代換
周期為1時就成了單表代換（不同地方使用同一代換表）
密鑰空間K={一個分組內所有字母組合間的所有置換} |K|= ()!如果代換表序列是非周期的無限序列，則相應的密碼稱為非周期多表代換密碼，稱為一次一密密碼。（序列密碼的一種）
優點：能更好抵抗統計密碼分析
1.Playfair密碼
2.維吉尼亞密碼
每一分組密鑰空間為?? ? （置換是固定的）
? 查表法
?或者用模運算實現
3. 希爾密碼
明文按n分組
密鑰矩陣: n*n的非奇異矩陣 且gcd(det(k),26)=1?
矩陣的行列式滿足和26互質，則存在模26下的乘法逆元（逆矩陣存在）。
加強版的希爾密碼? 補充常數項，c=mk+b
4.輪轉密碼機
目的：通過轉輪的轉動來實現復雜的多表代換，從而打破明文與密文之間的固定替代關系
三個轉速不一的轉輪構成：慢輪子、中輪子、快輪子。每個輪子是一個代換表
一個周期內，不同位置的相同明文代換成不同的密文
快輪子轉一圈，中輪子轉一個
中輪子轉一圈，慢輪子轉一個
密鑰周期為26*26*26
解密時密文倒著解密，密碼機倒著轉（一步一步恢復狀態）
3.古典密碼的分析
單表密碼和部分多表代換密碼可以用統計分析法進行唯密文攻擊，Hill密碼等需要用已知明文攻擊
三、分組密碼
明文、密文和密鑰都采用二進制編碼，也就是字符集是簡單的0和1。1.分組密碼（塊密碼）概述 ?????
將明文消息編碼的表示后二進制序列，劃分成固定大小的塊，每塊分別在密鑰的控制下變換成等長的二進制序列
注：傳統密碼也分組，但不是分組密碼
分組密碼屬于對稱密碼體制
分組密碼的設計要求
明文密文分組長度相同即可。 分組長度n要足夠長，即明文空間大小2n足夠大（防止明文窮舉攻擊）。 密鑰長度t要足夠長，即密鑰空間大小2t足夠大（防止密鑰窮舉攻擊）。但亦不能過長，否則影響加解密速度和密鑰管理。 由密鑰k確定的明文空間到密文空間的映射足夠復雜（注：可認為是個元素上的一個置換）。 已知密鑰時的加解密運算簡單，便于軟硬件的快速實現。密文空間與明文空間都是
理想分組密碼是每種輸入都會被代換成唯一的輸出，因此密鑰空間是，對應的密鑰長度是
?
實際的密鑰長度和分組長度差不多，密鑰空間為，就是說對任意的密鑰，一種明文不會加密成所有的密文
分組密碼的設計原則
擴散（Diffusion）： 明文和密文間的統計特性盡可能復雜，使得使得一比特明文的變化盡可能多的影響到輸出密文的比特，以隱藏明文的統計特性。 理想狀態下，明文改變一比特，密文里改變大約一半比特位。同樣，密文改變一比特，相應的明文改變大約一半比特位。 混亂（Confusion）： 使明文、密文和密鑰之間的關系盡可能復雜。 設計分組密碼時一般我們通過乘積密碼體制來實現擴散和混亂。 （類似于函數的復合，函數復合不一定滿足交換律，滿足結合律，乘積密碼體制同樣） 迭代密碼體制：大部分分組密碼用的都是迭代結構
主要是兩種迭代網絡：
Feistel網絡（如DES） SP網絡（如AES） 均能引起雪崩效應，即少量的明文變化引起密文巨大變化??Feistel網絡
?答：由于異或的特性 a xor a =0?? a xor 0 =a
SP網絡
2.DES
分組長度為64bit，密鑰長度為64bit，有效位為56bit（8位奇偶校驗碼）
已經可以被密鑰窮舉法破解，也不再作為正式的加密標準
DES過程：
1）64位的明文經初始置換（IP）重新排序，分為左右兩組（Lo，Ro)
2）在密鑰參與下，對左右兩組進行16輪迭代，最后一輪輸出64位，左右不交換
3）最后通過逆初始置換（) 產生密文
輪函數：
拓展置換（E盒）、密鑰加非線性代換（S盒）、線性置換（P盒）
E盒：改變了位的次序，重復了某些位
作用： 1.產生與子密鑰相同的數據，能夠進行異或運算
???????????? 2. 拓展后的數據能夠經過S盒壓縮，實現非線性
??????????? 3.1位輸入可能影響兩位輸出，快速實現雪崩效應
S盒：唯一的非線性部分，48位數據分成6*8 每組b1，b6作為行號，b2~b4作為列號，查表得到的數變成二進制4位
密鑰編排：
1.置換選擇PC-1 得到56位有效密鑰，分成兩組28位的
每次迭代，左右分別循環左移一位或者兩位，每一輪子密鑰是48位
DES的安全性
1.互補性?? 明文，密鑰取補，則密文也取補， 密文，密鑰取補，明文也取補
?
2.弱密鑰
由于密鑰的結構特點，生成子密鑰全部相同，則稱該密鑰為弱密鑰 ，有4種
?弱密鑰加密兩次等于原來的明文（把第二次加密看成解密）
半密鑰成對出現稱為互逆對
3.迭代輪數
4.三重DES
二重DES能抵御窮舉攻擊但不能抵御中途相遇攻擊
3.AES
密鑰長度：128bit、192bit、256bit
分組長度：128bit
每一輪包括：
?字節代換
?行移位
?列混合
?輪密鑰加
?
?
加密最開始和解密最開始要用初始密鑰加
S盒：
DES與AES的對比
?
?
4.分組密碼的工作模式
實際應用中需要處理的消息數據長度往往遠遠大于分組密碼的數據塊大小
根據應用的需要，人們設計了許多分組密碼的工作模式，一般需要滿足以下幾點： 工作模式本身的運算應當簡單 工作模式不應當損害分組密碼算法的安全性 工作模式不會明顯降低效率工作模式易于實現
電子密碼本模式（Electronic Code Book, ECB）
§分組數據塊長度(Block Size): b bits §明文長度: nb §明文長度如果不是b的整數倍則要補足(padding)成b的整數倍 §明文可寫成序列𝑃1,𝑃2,?,𝑃𝑛P_1,P_2,?,P_n?特點：
§實現起來最簡單 §加密解密都可以并行處理 §缺點：假定兩個不同的明文數據塊里的數據相同，則相應的密文數據塊也相同。ECB安全性不夠高（不需要解密也可以通過統計分析獲取信息）密碼分組鏈接模式（Cipher Block Chaining，CBC）
?加密采用串行結構，須知到前一數據塊的密文才能對下一數據塊加密。
?
?
密碼反饋模式（Cipher Feedback Block，CFB）
?
輸出反饋模式（Output Feedback Block，OFB）
?
計數器模式（Counter，CTR）?
?錯誤影響
電子密碼本模式（ECB) ：明文或密文中某一位出錯，解密時只會影響對應的分組，若明文或密文被插入或刪除，則后面的所有分組都受影響
密碼分組鏈接模式（CBC):明文一位出錯，該組及其后面的所有密文組都受影響，但是解密時會反轉這種影響，只有一組受影響，密文一位出錯，解密時只影響該分組和它下一分組
密碼反饋模式（CFB):明文一位出錯，該組及其后面的所有密文組都受影響，但是解密時會反轉這種影響，只有一組受影響，密文一位出錯，解密時只當錯誤在移位寄存器中產生影響。
所以密碼反饋模式是自同步序列密碼的典型
輸出反饋模式（OFB) :反饋機制獨立于明文和密文存在
密文一位錯誤，只會影響一組明文。但是失去同步很致命，其為同步序列密碼
這幾種方式若是密文被插入或刪除就會影響后面所有的，所以要有檢測失步的機制，重新同步
要有某種幀結構重新排列分組的邊界
總結
- 上一篇： 黑客X档案的《黑客免杀入门》
- 下一篇： 22考研清华电子系957，390+高分上