密碼學(xué)
香農(nóng)對(duì)密碼學(xué)的貢獻(xiàn)
●評(píng)價(jià)密碼體制的安全性：計(jì)算安全性、完善完全性
●混亂和擴(kuò)散
●乘積密碼體制思想
評(píng)價(jià)密碼體系的安全性
●計(jì)算安全性：從計(jì)算量上衡量密碼體系的安全性
●可證明安全性：通常使用歸約的方法來(lái)證明所定義的安全性
●無(wú)條件安全性：即使無(wú)限資源也無(wú)法攻破
實(shí)際中廣泛使用的算法
●二次篩法
●橢圓曲線算法：適用于素因子長(zhǎng)度不同的合數(shù)
●數(shù)域篩法：適用于更大的數(shù)，目前分解的世界記錄RSA-768 768位二進(jìn)制數(shù)
信息量
對(duì)信息的直觀認(rèn)識(shí)：
●信道上傳送的是隨機(jī)變化的值
●事件發(fā)生概率與信息量的關(guān)系
●消息間的依賴關(guān)系與相互之間的信息量I(xi)=log2(1/p(xi))=-log2(P(xi))
密碼體制中熵的性質(zhì)
定理設(shè)(P,C,K,E,D)是一個(gè)密碼體制，那么有H(K|C)=H(K)+H(P)-H(C)(密鑰含混度)
含義：截獲密文后，密鑰的未知信息量等于明文和密鑰總的未知信息量減去從已知密文中獲得的信息量。
證明：
●H（KPC）=H（C|KP）+H(KP)
●明文和密鑰可確定密文，即H（C|KP）=0，因此H（KPC）=H（KP）
●P和K是統(tǒng)計(jì)獨(dú)立的，因此H（KP）=H（K）+H（P）
●同理H（KPC）=H（P|KC）+H（KC）=H（KC）
●因此H（KC）=H（KP）
●H（K|C）=H（KC）-H（C）=H（KP）-H（C）=H（K）+H（P）-H（C）
一般密碼體制
●|P|=<|C|（單射）明文空間小于等于密文空間
●H(P|KC)=H(C|KP)=0已知密鑰和密文條件下密文的熵等于已知密鑰和明文條件下密文的熵
●H(PK)=P(P)+P(K)明文和密鑰是統(tǒng)計(jì)獨(dú)立的
●H(K|C)=H(P)+H(K)-H(C)
●H(P)=<H(C)=<H(P)+H(K)
●H(P|C)=<H(K|C)
密碼學(xué)中的熵關(guān)系
●H(K|C)=H(P)+H(K)-H(C)
●H(P|C)=<H(K|C)
偽密鑰
獲得同一密鑰加密的密文越長(zhǎng)，存在偽密鑰的可能性越小
現(xiàn)代分組密碼設(shè)計(jì)原理
●混亂（Confusion）：密鑰和明文以及密文之間的依賴關(guān)系復(fù)雜
●擴(kuò)散（Diffusion）：?jiǎn)蝹€(gè)密鑰或明文位的影響盡可能擴(kuò)大到更多的密文位中
大整數(shù)因式分解
●整數(shù)分解問(wèn)題隱含了RSA的破譯問(wèn)題
●試除法是最簡(jiǎn)單和直接的方法，即用直到sqrt（n）的每個(gè)素?cái)?shù)去整除n
●n<10^20基本可行
●如果n有小的因子比較有效
費(fèi)馬定理
假定可找到a，b滿足a^2-b^2=n，若（最大公約數(shù)）gcd（a+-b，n）是n的非平凡因子，那么可找到n的兩個(gè)非平凡因子。
小加密指數(shù)攻擊
使用一個(gè)較小的e值（比如e=3），則進(jìn)行RSA簽名驗(yàn)證和加密會(huì)很快。
避免使用小的加密指數(shù)，e=2^16+1=65537
短消息加密前填充，PKCS標(biāo)準(zhǔn)
離散對(duì)數(shù)
離散對(duì)數(shù)問(wèn)題
已知：乘法群（G，·），一個(gè)n階元素α屬于G和元素β屬于<α>
問(wèn)題：找到唯一整數(shù)i，0=>i=<n-1,滿足α^i=β
我們將整數(shù)i記為ind（α）（β），稱為α為底的β的離散對(duì)數(shù)
●D-H密鑰交換
●只能交換密鑰
●存在中間人攻擊
●ElGamal體制
●加密依賴隨機(jī)數(shù)
橢圓曲線
●橢圓曲線多倍點(diǎn)運(yùn)算構(gòu)成單項(xiàng)函數(shù)
●橢圓曲線離散對(duì)數(shù)問(wèn)題求解難度大于大整數(shù)分解及有限域熵的離散對(duì)數(shù)問(wèn)題
●相同安全程度要求下，橢圓曲線密碼所需要的密鑰規(guī)模要小的多
●有限域上的橢圓曲線在點(diǎn)加運(yùn)算下構(gòu)成有限交換群，其階與基域規(guī)模相近
橢圓曲線離散對(duì)數(shù)問(wèn)題
有限域Fq上的橢圓曲線E（Fq）由點(diǎn)組成，其上點(diǎn)的數(shù)目記為#E（Fq），稱為橢圓曲線E（Fq）的階
給定有限域Fq上的橢圓曲線E（Fq）上一點(diǎn)P，P+P稱為點(diǎn)P的倍點(diǎn)運(yùn)算
橢圓曲線上同一點(diǎn)多次加稱為該點(diǎn)的多倍點(diǎn)運(yùn)算。設(shè)k是正整數(shù)，P是橢圓曲線上一點(diǎn)，稱點(diǎn)P的k次加為點(diǎn)P的k倍點(diǎn)運(yùn)算，記為Q=kP，kP=（k-1）P+P，k倍點(diǎn)可遞歸求得
橢圓曲線離散對(duì)數(shù)問(wèn)題ECDLP。已知橢圓曲線E（Fq）、階為n的點(diǎn)P屬于E（Fq）及Q屬于
，橢圓曲線離散對(duì)數(shù)問(wèn)題是指確定整數(shù)k∈[0,n-1]，使得Q=kP成立
SM2
國(guó)密關(guān)于橢圓曲線的標(biāo)準(zhǔn)算法集
●有限域Fq選擇素域Fp（p>2^191）或二元擴(kuò)域F2m(m>2^192)
●Fp的橢圓曲線方程：y^2=x^3+ax+b a,b∈Fp，(4a^3+27b^2)mod（p）≠0
●F2m的橢圓曲線方程：y^2+xy=x^3+ax^2+b a,b∈F2m,b≠0
●推薦橢圓曲線參數(shù)：使用素域256位橢圓曲線曲線方程y^2=x^3+ax+b
數(shù)據(jù)類型和數(shù)據(jù)類型之間的轉(zhuǎn)換
比特串、字節(jié)串、域元素、橢圓曲線上的點(diǎn)
橢圓曲線的解是域上的元素，消息處理時(shí)候是比特流。通過(guò)類型轉(zhuǎn)換函數(shù)進(jìn)行相應(yīng)的類型，
再進(jìn)行操作
參數(shù)：公私鑰對(duì)（d，P），P=（x，y）=dG（G為基點(diǎn)，n為其階，n、G公開(kāi)）記（dA，PA）為A的公私鑰對(duì)，階位n的基點(diǎn)G=（xG，yG），h余因子h=#E（Fq）/n
d是私鑰，P是公鑰，d是一個(gè)整數(shù)，P是橢圓曲線上的一個(gè)點(diǎn)
使用的函數(shù)
密碼雜湊函數(shù)Hv（國(guó)密SM3標(biāo)準(zhǔn)）
密鑰派生函數(shù)KDF（調(diào)用Hv）
偽隨機(jī)數(shù)發(fā)生器（國(guó)家密碼管理局批準(zhǔn)的）
SM2數(shù)字簽名
A對(duì)消息M進(jìn)行簽名，計(jì)算ZA=H256（ENTL||ID||a||b||xG||yG||xA||yA）階位n的基點(diǎn)G=（xG，yG）（dA，PA）為A的公私鑰對(duì)，PA=dA·G=（xA，yA）
簽名算法：
驗(yàn)證算法（M`,(r`,s`)）：
s`=((1+dA)-1(l-r`dA))mod(n)
s`(1+dA)+r`dA=k mod(n)
s`G+(s`+r`)dAG=kG可推導(dǎo)出s`G+tPA=kG=(x1`,y1`)
R=e`+x1`mod(n)=r`
V1:r`∈[1,n-1]?
V2:s`∈[1,n-1]?
V3:M``=ZA||M`
V4:e`=Hv(M``)
V5:t=(r`+s`)mod(n)若t=0則驗(yàn)證不通過(guò)
V6:(x1`,y1`)=s`G+tPA
V7:R=e`+x1`,R=r`?
A1：M`=ZA||M
A2：e=Hv（M`）
A3：產(chǎn)生隨機(jī)數(shù)k∈[1,n-1]
A4：（x1，y1）=kG
A5：r=（e+x1）mod（n）若r=0或r+k=n返回A3
A6：s=（（1+dA）^-1（k-rdA））mod（n）若s=0返回A3
A7：返回M的簽名（r，s）
SM2密鑰交換協(xié)議
SM2公鑰加密算法
A發(fā)送長(zhǎng)為klen的消息比特串M給B
階為n的基點(diǎn)G=（xG,yG），h余因子，（dB,PB）為B的公私鑰對(duì)
加密算法：
產(chǎn)生隨機(jī)數(shù)k∈[1,n-1]
C1=kG=(x1,y1)
S=hPB若S是無(wú)窮遠(yuǎn)點(diǎn)則報(bào)錯(cuò)并退出
kPB=（x2，y2）
t=KDF（x2||y2，klen）若t全0返回1
C2=M異或t
C3=Hash（x2||M||y2）
輸出M的密文C=C1||C2||C3
解密算法：
驗(yàn)證C1是否滿足橢圓曲線方程
S=hC1若S是無(wú)窮遠(yuǎn)點(diǎn)則報(bào)錯(cuò)并退出
dBC1=（x2，y2）
t=KDF（x2||y2，klen）若t全0報(bào)錯(cuò)并退出
M`=C2異或t
u=Hash（x2||M`||y2）若u≠C3則報(bào)錯(cuò)并退出
輸出明文M`
C1=kG=(x1,y1),kPB=(x2,y2)=>dBC1=dBkG=kdBG=kPB=(x2,y2)
數(shù)字簽名體制
公鑰密碼的使用和優(yōu)勢(shì)
遠(yuǎn)程密鑰分配
數(shù)字簽名
一個(gè)數(shù)字簽名體制是一個(gè)五元組（P，A，K，S，V），滿足：
P是所有可能的消息組成的有限集
A是所有可能的簽名組成的有限集
K是所有可能的密鑰組成的有限集（密鑰空間）
對(duì)每個(gè)k∈K，有一個(gè)秘密的簽名函數(shù)sig（k）屬于S和一個(gè)相應(yīng)的公開(kāi)驗(yàn)證函數(shù)ver（k）∈v，等于每個(gè)消息x∈P和每個(gè)簽名y∈A，，滿足：
稱（x,y）為帶簽名的消息
簽名和公鑰加密結(jié)合的方案
●第一種方案：先簽名再加密：
●第二種方案：先加密再簽名：
●第二種方案可能存在偽造簽名混淆發(fā)送者的問(wèn)題，建議使用第一種方案
數(shù)字簽名
符號(hào)：
A：消息簽名者
B：消息驗(yàn)證者
：用戶A的標(biāo)識(shí)，可以唯一確定A的公鑰
：用戶A的簽名私鑰
：簽名主公鑰
：簽名主私鑰
M：待簽名消息，任意長(zhǎng)度比特串
：待驗(yàn)證消息，任意長(zhǎng)度比特串
：生成的消息的數(shù)字簽名
：接收的消息的數(shù)字簽名
：雙線性對(duì)的三個(gè)循環(huán)群
：循環(huán)群的階，素?cái)?shù)
：元素個(gè)數(shù)為N的有限域，mod N運(yùn)算
：的生成元
：的生成元，
：中的元素，生成元
：一個(gè)字節(jié)，表示簽名私鑰生成函數(shù)識(shí)別符，KGC（密鑰生成中心）選擇并公開(kāi)
、
：調(diào)用，將比特串Z轉(zhuǎn)換程一個(gè)的整數(shù)
數(shù)字簽名流程
數(shù)字簽名驗(yàn)證
數(shù)據(jù)完整性
信息安全的三個(gè)要點(diǎn)
機(jī)密性：不能被沒(méi)有授權(quán)的人看到
完整性：在存儲(chǔ)過(guò)程中，不能被非法篡改，傳統(tǒng)加密算法可以解決機(jī)密性問(wèn)題，不能解決完整性問(wèn)題----結(jié)合區(qū)塊鏈技術(shù)，提高信息安全等級(jí)
可用性
加密算法解決了機(jī)密性問(wèn)題，能否解決完整性問(wèn)題
數(shù)據(jù)完整性是抗擊對(duì)消息未授權(quán)修改的安全服務(wù)
有些應(yīng)用不需要機(jī)密性，比如電子交易信息
如何解決完整性問(wèn)題：附加冗余
對(duì)稱技術(shù)：Hash函數(shù)（散列函數(shù)）、報(bào)文鑒別碼（MAC）
非對(duì)稱技術(shù)：數(shù)字簽名
Hash函數(shù)
Hash函數(shù)H（M）作用于一任意長(zhǎng)度的消息M，它返回一固定長(zhǎng)度（通常超過(guò)128位）的散列值h：h=H（M）
有時(shí)也稱“摘要函數(shù)”、“散列函數(shù)”或“雜湊函數(shù)”
h也被稱為消息或數(shù)據(jù)的“摘要”或“指紋”
帶密鑰的Hash函數(shù)：可將h和消息M一起在不安全的信道中傳，被稱為MAC（消息鑒別碼）
不帶密鑰的Hash函數(shù)：h必須安全存放、確保h不被篡改
隨機(jī)預(yù)言機(jī)ROM（Random Oracle Machine）
Bellare和Rogaway提出
提供“理想”Hash函數(shù)的數(shù)學(xué)模型
確定性，有效性和均勻輸出
令是為所有從的函數(shù)集合，假定，隨機(jī)從中選出一個(gè)Hash函數(shù)，對(duì)于任意的輸入，其輸出值是均勻的，且計(jì)算的唯一方法是詢問(wèn)隨機(jī)預(yù)言機(jī)。
原像問(wèn)題
Find-Rreimage(h,y,Q)
選擇任意的
for each
return(failure)
SSL協(xié)議
功能：
身份鑒別
傳輸加密
完整性保護(hù)
密鑰交互
層次結(jié)構(gòu)
握手協(xié)議
改變密碼格式協(xié)議
警告協(xié)議
應(yīng)用數(shù)據(jù)協(xié)議
記錄層協(xié)議
分段：每個(gè)上層應(yīng)用數(shù)據(jù)被分成字節(jié)或更小的數(shù)據(jù)塊
壓縮：壓縮是可選的，并且是無(wú)損壓縮，壓縮后內(nèi)容長(zhǎng)度的增加不能超過(guò)1024字節(jié)
完整性：再壓縮數(shù)據(jù)上計(jì)算消息鑒別MAC
加密：對(duì)壓縮數(shù)據(jù)及MAC進(jìn)行加密
打包：增加ssl記錄頭（內(nèi)容類型、主版本、次版本、數(shù)據(jù)長(zhǎng)度）
握手協(xié)議
第一階段：版本、算法協(xié)商
（1）：Support Version，RC，Session id，Supported Cipher suite，Supported Compress method，分別表示支持的最高版本、客戶端隨機(jī)數(shù)（4+28字節(jié)）、會(huì)話ID、支持的密碼套件名稱（SSL_DHE_RSA_WITH_DES_CBC_SHA）、支持的壓縮方法
（2）：Version，RS，Session ID，Cipher suit，Compression method，分別表示選擇的版本、服務(wù)器端隨機(jī)數(shù)（4+28字節(jié)）、會(huì)話ID、選擇的密碼套件名稱、選擇的壓縮方法
第二階段：服務(wù)器發(fā)送證書給客戶端
（3）：Certs of Server，表示服務(wù)器的相關(guān)證書RSA或者DSA證書等。
（4）（可選）：將用在密鑰交換過(guò)程的相關(guān)公鑰參數(shù)，以及這些參數(shù)的數(shù)字簽名（公鑰參數(shù)）發(fā)送給客戶端。僅當(dāng)（3）中已提供，則可??；如果選擇DH協(xié)議，則會(huì)發(fā)送以及它們的數(shù)字簽名。再選擇RSA方式交換密鑰的時(shí)候，也可以選擇重新生成一個(gè)臨時(shí)的、不同于簽名的RSA加密密鑰發(fā)送給客戶端。
（5）（可選）：Request of Client Certs，請(qǐng)求客戶端發(fā)送證書進(jìn)行驗(yàn)證，僅當(dāng)服務(wù)器強(qiáng)制客戶端認(rèn)證時(shí)，服務(wù)器端才發(fā)送此消息，消息中會(huì)包含服務(wù)器端支持的證書類型和所有Server端信任的證書發(fā)行機(jī)構(gòu)的DN（Distinguished Name）列表。
第三階段：由客戶端發(fā)送證書給服務(wù)器端
（6）（可選）：Certs of Client，表示客戶端的相關(guān)證書，僅當(dāng)服務(wù)器強(qiáng)制客戶端認(rèn)證時(shí)，客戶端才發(fā)送此消息。
（7）：或者，例如，若選擇RSA認(rèn)證，則用服務(wù)器的公鑰加密預(yù)備主密鑰PM給服務(wù)器；若選擇DH認(rèn)證，則發(fā)送給服務(wù)器，服務(wù)器可以根據(jù)自己生成PM。
（8）（可選）：（已發(fā)送接收的握手信息+主密鑰M的MD5和SHA1摘要），客戶端的簽名，僅當(dāng)服務(wù)器強(qiáng)制客戶端認(rèn)證時(shí)，客戶端才發(fā)送此消息。
第四階段：密鑰生成
客戶端和服務(wù)器端分別生成HMAC消息鑒別碼密鑰Auth.Key，分組加密初始向量IV，分組加密密鑰Enc.Key
以后，客戶端用客戶端的Auth.Key，IV，Enc.Key加密消息發(fā)送給服務(wù)器端，而服務(wù)器端則用服務(wù)器端的Auth.Key，IV，Enc.Key加密消息發(fā)送給客戶端，加密是單向的。
第五階段：分別發(fā)表握手協(xié)議結(jié)束申明
使用HMAC算法計(jì)算收到和發(fā)送的所有握手消息、主密鑰M和常數(shù)串“client/server finished”的摘要，然后通過(guò)一個(gè)偽隨機(jī)函數(shù)PRF計(jì)算出結(jié)果，用對(duì)稱加密算法機(jī)密后發(fā)送給對(duì)方，對(duì)方收到驗(yàn)證其正確性。
