密碼學(xué)基礎(chǔ)課件

第1章信息安全概述信息、信息系統(tǒng)和信息安全概念信息安全的三個(gè)發(fā)展階段信息安全的五個(gè)特性信息安全威脅五個(gè)基本類型網(wǎng)絡(luò)安全與政治、軍事、經(jīng)濟(jì)和社會(huì)穩(wěn)定互聯(lián)網(wǎng)安全性分析信息安全的體系結(jié)構(gòu)2022/10/201第1章信息安全概述2022/10/151第2章密碼學(xué)基礎(chǔ)2.1密碼學(xué)基礎(chǔ)知識(shí)

2.2古典替換密碼

2.3對(duì)稱密鑰密碼

2.4公開密鑰密碼2.5消息認(rèn)證2.6密碼學(xué)新進(jìn)展

2022/10/202第2章密碼學(xué)基礎(chǔ)2.1密碼學(xué)基礎(chǔ)知識(shí) 2022/102.1密碼學(xué)基礎(chǔ)知識(shí)2.1.1引言解決信息的機(jī)密性、完整性、不可否認(rèn)性以及身份識(shí)別等問(wèn)題均需要以密碼為基礎(chǔ)。密碼技術(shù)是保障信息安全的核心基礎(chǔ)。密碼學(xué)(Cryptography)包括密碼編碼學(xué)和密碼分析學(xué)兩部分。將密碼變化的客觀規(guī)律應(yīng)用于編制密碼，用來(lái)保守通信秘密的，稱為密碼編碼學(xué)；研究密碼變化客觀規(guī)律中的固有缺陷，并應(yīng)用于破譯密碼以獲取通信情報(bào)的，稱為密碼分析學(xué)。歷史公元前一世紀(jì)，古羅馬皇帝凱撒曾使用移位密碼。宋代的曾公亮、丁度等編撰《武經(jīng)總要》中“字驗(yàn)”。20世紀(jì)初，出現(xiàn)了最初的機(jī)械式和電動(dòng)式密碼機(jī)。60年代后，電子密碼機(jī)得到較快發(fā)展和應(yīng)用。2022/10/2032.1密碼學(xué)基礎(chǔ)知識(shí)2.1.1引言2022/10/12.1.2密碼體制消息（為了溝通思想而傳遞的信息）在密碼學(xué)中被稱為明文（PlainText）。偽裝消息以隱藏它的內(nèi)容的過(guò)程稱為加密(Encrypt)被加密的消息稱為密文(CipherText)把密文轉(zhuǎn)變?yōu)槊魑牡倪^(guò)程稱為解密(Decrypt)。2022/10/2042.1.2密碼體制消息（為了溝通思想而傳遞的信息）在密碼學(xué)2.1.2密碼體制完整密碼體制要包括如下五個(gè)要素：M是可能明文的有限集，稱為明文空間；C是可能密文的有限集，稱為密文空間；K是一切可能密鑰構(gòu)成的有限集，稱為密鑰空間；E為加密算法，對(duì)于任一密鑰，

都能夠有效地計(jì)算；D為解密算法，對(duì)于任一密鑰，都能夠有效地計(jì)算。密碼體系必須滿足如下特性：

加密算法(Ek：M->C)和解密算法(Dk：C->M)滿足:Dk(Ek(x))=x,這里x?M；破譯者不能在有效的時(shí)間內(nèi)破解出密鑰k或明文x。2022/10/2052.1.2密碼體制完整密碼體制要包括如下五個(gè)要素：20222.1.3密碼的分類密碼學(xué)發(fā)展的三個(gè)階段：古代加密密碼、古典密碼、近代密碼依據(jù)密碼體制的特點(diǎn)以及出現(xiàn)的時(shí)間分類：古典替換密碼：?jiǎn)伪泶婷艽a，多表代替密碼以及輪換密碼。對(duì)稱密鑰密碼：分組密碼和流密碼。公開密鑰密碼：加密和解密使用不同的密鑰。密碼分析也稱為密碼攻擊，密碼分析攻擊主要包括：唯密文攻擊、已知明文攻擊、選擇明文攻擊、自適應(yīng)選擇明文攻擊、選擇密文攻擊、選擇密鑰攻擊。2022/10/2062.1.3密碼的分類密碼學(xué)發(fā)展的三個(gè)階段：2022/10/2.2古典替換密碼2.2.1簡(jiǎn)單代替密碼簡(jiǎn)單代替密碼指將明文字母表M中的每個(gè)字母用密文字母表C中的相應(yīng)字母來(lái)代替。例如：移位密碼、乘數(shù)密碼、仿射密碼等。移位密碼具體算法是將字母表的字母右移k個(gè)位置，并對(duì)字母表長(zhǎng)度作模運(yùn)算。每一個(gè)字母具有兩個(gè)屬性：本身代表的含義；可計(jì)算的位置序列值。

加密函數(shù)：Ek(m)=(m+k)modq。

解密函數(shù)：Dk(c)=(c–k)modq。2022/10/2072.2古典替換密碼2.2.1簡(jiǎn)單代替密碼2022/10/凱撒Caesar密碼凱撒密碼體系的數(shù)學(xué)表示：M=C={有序字母表}，q=26，k=3。其中q為有序字母表的元素個(gè)數(shù)，本例采用英文字母表，q=26。使用凱撒密碼對(duì)明文字符串逐位加密結(jié)果：明文信息M=meetmeafterthetogaparty密文信息C=phhwphdiwhowkhwrjdsduwb2022/10/208凱撒Caesar密碼凱撒密碼體系的數(shù)學(xué)表示：2022/10/乘數(shù)密碼乘數(shù)密碼將明文字母串逐位乘以密鑰k并進(jìn)行模運(yùn)算。數(shù)學(xué)表達(dá)式:Ek(m)=k*mmodq,gcd(k,q)=1。gcd(k,q)=1表示k與q的最大公因子為1。例子：M=C=Z/(26)，明文空間和密文空間同為英文字母表空間，包含26個(gè)元素；q=26；K={k∈整數(shù)集|0<k<26，gcd(k,26)=1}，密鑰為大于0小于26，與26互素的正整數(shù)；Ek(m)=kmmodq。Dk#(c)=k#cmodq，其中k#為k在模q下的乘法逆元。2022/10/209乘數(shù)密碼乘數(shù)密碼2022/10/159密鑰取值與乘法逆元K#為k在模q下的乘法逆元：其定義為k#*kmodq=1，可采用擴(kuò)展的歐幾里德算法。歐幾里德算法又稱輾轉(zhuǎn)相除法，用于計(jì)算兩個(gè)整數(shù)a和b的最大公約數(shù)。乘數(shù)密碼的密鑰k與26互素時(shí)，加密變換才是一一映射的。k的選擇有11種：3、5、7、9、11、15、17、19、21、23、25。K取1時(shí)沒(méi)有意義。k取13會(huì)如何？2022/10/2010密鑰取值與乘法逆元K#為k在模q下的乘法逆元：2022/10仿射密碼仿射密碼可以看作是移位密碼和乘數(shù)密碼的結(jié)合。密碼體制描述如下：M=C=Z/(26)；q=26；K={k1,k2∈Z|0<k1,k2<26，gcd(k1,26)=1}；Ek(m)=(k1m+k2)modq；Dk(c)=k1#(

c-k2)modq，其中k1#為k1在模q下的乘法逆元。密鑰范圍K1：所有和26互素的數(shù)。K1=1？k2：1-25的整數(shù)。K2=0？2022/10/2011仿射密碼仿射密碼2022/10/1511仿射密碼事例設(shè)k=(5,3)，注意到5#mod26=21.加密函數(shù)：Ek(x)=5x+3(mod26)，解密函數(shù)：Dk(y)=21(y-3)mod26=21y–11(mod26)。加密明文“yes”的加密與解密過(guò)程如下：2022/10/2012仿射密碼事例設(shè)k=(5,3)，注意到5#mod26=2基于統(tǒng)計(jì)的密碼分析簡(jiǎn)單代替密碼的加密是從明文字母到密文字母的一一映射攻擊者統(tǒng)計(jì)密文中字母的使用頻度，比較正常英文字母的使用頻度，進(jìn)行匹配分析。如果密文信息足夠長(zhǎng)，很容易對(duì)單表代替密碼進(jìn)行破譯。2022/10/2013基于統(tǒng)計(jì)的密碼分析簡(jiǎn)單代替密碼的加密是從明文字母到密文字母的2.2.2多表代替密碼多表代替密碼是以一系列代替表依次對(duì)明文消息的字母進(jìn)行代替的加密方法。多表代替密碼使用從明文字母到密文字母的多個(gè)映射來(lái)隱藏單字母出現(xiàn)的頻率分布。每個(gè)映射是簡(jiǎn)單代替密碼中的一對(duì)一映射。非周期多表代替密碼若映射系列是非周期的無(wú)限序列，則相應(yīng)的密碼稱為非周期多表代替密碼。對(duì)每個(gè)明文字母都采用不同的代替表(或密鑰)進(jìn)行加密，稱作一次一密密碼。2022/10/20142.2.2多表代替密碼多表代替密碼是以一系列代替表依次對(duì)明文維吉尼亞Vigenère密碼周期多表代替密碼：Vigenère、Beaufort、RunningKey、Vernam和輪轉(zhuǎn)機(jī)等密碼。維吉尼亞Vigenère密碼：是以移位代替為基礎(chǔ)的周期多表代替密碼。加密時(shí)每一個(gè)密鑰被用來(lái)加密一個(gè)明文字母，當(dāng)所有密鑰使用完后，密鑰又重新循環(huán)使用。Ek(m)=C1C2…Cn，其中Ci=（mi+ki）mod26；密鑰K可以通過(guò)周期性反復(fù)使用以至無(wú)窮。2022/10/2015維吉尼亞Vigenère密碼周期多表代替密碼：2022/102.3對(duì)稱密鑰密碼2022/10/20162.3對(duì)稱密鑰密碼2022/10/15162.3.1對(duì)稱密鑰密碼加密模式對(duì)稱密碼加密系統(tǒng)從工作方式上可分為：分組密碼、序列密碼分組密碼原理：明文消息分成若干固定長(zhǎng)度的組，進(jìn)行加密；解密亦然。2022/10/20172.3.1對(duì)稱密鑰密碼加密模式對(duì)稱密碼加密系統(tǒng)從工作方式上序列密碼（流密碼）通過(guò)偽隨機(jī)數(shù)發(fā)生器產(chǎn)生性能優(yōu)良的偽隨機(jī)序列(密鑰流)，用該序列加密明文消息流，得到密文序列；解密亦然。2022/10/2018序列密碼（流密碼）通過(guò)偽隨機(jī)數(shù)發(fā)生器產(chǎn)生性能優(yōu)良的偽隨機(jī)序列2.3.2數(shù)據(jù)加密標(biāo)準(zhǔn)DES1973年美國(guó)國(guó)家標(biāo)準(zhǔn)局NBS公開征集國(guó)家密碼標(biāo)準(zhǔn)方案；算法必須提供高度的安全性；算法必須有詳細(xì)的說(shuō)明，并易于理解；算法的安全性取決于密鑰，不依賴于算法；算法適用于所有用戶；算法適用于不同應(yīng)用場(chǎng)合；算法必須高效、經(jīng)濟(jì)；算法必須能被證實(shí)有效；算法必須是可出口的。1974年NBS開始第二次征集時(shí)，IBM公司提交了算法LUCIFER。2022/10/20192.3.2數(shù)據(jù)加密標(biāo)準(zhǔn)DES1973年美國(guó)國(guó)家標(biāo)準(zhǔn)局NBS2.3.2數(shù)據(jù)加密標(biāo)準(zhǔn)DES1975年，NBS公開了LUCIFER的全部設(shè)計(jì)細(xì)節(jié)并指派了兩個(gè)小組進(jìn)行評(píng)價(jià)。1976年，LUCIFER被采納為聯(lián)邦標(biāo)準(zhǔn)，批準(zhǔn)用于非軍事場(chǎng)合的各種政府機(jī)構(gòu)。1977年，LUCIFER被美國(guó)國(guó)家標(biāo)準(zhǔn)局NBS作為“數(shù)據(jù)加密標(biāo)準(zhǔn)

FIPSPUB46”發(fā)布，簡(jiǎn)稱為DES。2022/10/20202.3.2數(shù)據(jù)加密標(biāo)準(zhǔn)DES1975年，NBS公開了LUCS-DESS-DES加密算法S-DES是由美國(guó)圣達(dá)卡拉大學(xué)的EdwardSchaeffer教授提出的，主要用于教學(xué)，其設(shè)計(jì)思想和性質(zhì)與DES一致，有關(guān)函數(shù)變換相對(duì)簡(jiǎn)化，具體參數(shù)要小得多。輸入為一個(gè)8位的二進(jìn)制明文組和一個(gè)10位的二進(jìn)制密鑰，輸出為8位二進(jìn)制密文組；解密與加密基本一致。加密:IP-1(fk2(SW(fk1(IP(明文)))))解密:IP-1(fk1(SW(fk2(IP(密文)))))2022/10/2021S-DESS-DES加密算法2022/10/1521S-DES的密鑰產(chǎn)生P10和P8是置換函數(shù)，LS是循環(huán)左移函數(shù)例子：P10=(3,5,2,7,4,10,1,9,8,6)；P8=(6,3,7,4,8,5,10,9)K0=1010000010；K1=？；K2=？00001循環(huán)左移兩位00100，循環(huán)右移位010002022/10/2022S-DES的密鑰產(chǎn)生P10和P8是置換函數(shù)，LS是循環(huán)左移函S-DES的密鑰產(chǎn)生P10和P8是置換函數(shù)，LS是循環(huán)左移函數(shù)例子：P10=(3,5,2,7,4,10,1,9,8,6)；P8=(6,3,7,4,8,5,10,9)K0=1010000010；K1=10100100；K2=010000112022/10/2023S-DES的密鑰產(chǎn)生P10和P8是置換函數(shù)，LS是循環(huán)左移函

S-DES的加密變換過(guò)程

初始置換IP和末尾置換IP-1IP=(2,6,3,1,4,8,5,7)IP-1=(4,1,3,5,7,2,8,6)例子：11100100擴(kuò)張置換函數(shù)E/PE/P

=(

4,1,2,3,2,3,4,1)“⊕”:按位異或運(yùn)算；S盒函數(shù)S0和S1為兩個(gè)盒子函數(shù)，將輸入作為索引查表，得到相應(yīng)的系數(shù)作為輸出。置換函數(shù)P4=（2,4,3,1）。交換函數(shù)SW：將左4位和右4位交換。2022/10/2024

S-DES的加密變換過(guò)程

初始置換IP和末尾置換IP-1S盒函數(shù)S盒函數(shù)按下述規(guī)則運(yùn)算：輸入的第1位和第4位二進(jìn)制數(shù)合并為一個(gè)兩位二進(jìn)制數(shù)，作為S盒的行號(hào)索引i；將第2位和第3位同樣合并為一個(gè)兩位二進(jìn)制數(shù)，作為S盒的列號(hào)索引j，確定S盒矩陣中的一個(gè)系數(shù)（i，j）。此系數(shù)以兩位二進(jìn)制數(shù)形式作為S盒的輸出。例如：L’=（l0,l1,l2,l3）=（0，1，0，0），

（i，j）=（0,2）在S0中確定系數(shù)3，則S0的輸出為11B。（1,1,1,0）作為S1的輸入，輸出為？2022/10/2025S盒函數(shù)S盒函數(shù)按下述規(guī)則運(yùn)算：2022/10/1525DES算法2022/10/2026DES算法2022/10/1526DES的安全問(wèn)題1977年，為了破解DES的編譯，需要耗資兩千萬(wàn)美元建成一個(gè)專門計(jì)算機(jī)，同時(shí)耗費(fèi)12個(gè)小時(shí)破解才能得到結(jié)果。1994年世界密碼大會(huì)，M.Matsui提出線性分析方法，利用243個(gè)已知明文，成功破譯DES。1997年首屆“向DES挑戰(zhàn)”的競(jìng)技賽。羅克·維瑟用了96天時(shí)間破解了用DES加密的一段信息。2000年1月19日，電子邊疆基金會(huì)組織25萬(wàn)美元的DES解密機(jī)以22.5小時(shí)成功破解DES加密算法。DES的最近一次評(píng)估是在1994年，同時(shí)決定1998年12月以后，DES將不再作為聯(lián)邦加密標(biāo)準(zhǔn)。2022/10/2027DES的安全問(wèn)題1977年，為了破解DES的編譯，需要耗資兩2.3.3分組密碼的工作模式電子編碼本模式（ECB）密碼分組鏈接模式（CBC）密碼反饋模式（CFB）輸出反饋模式（OFB）2022/10/20282.3.3分組密碼的工作模式電子編碼本模式（ECB）2022.3.3分組密碼的工作模式電子編碼本模式（ECB）2022/10/20292.3.3分組密碼的工作模式電子編碼本模式（ECB）202電子編碼本模式電子編碼本模式（ECB）特點(diǎn)：簡(jiǎn)單有效；可以并行實(shí)現(xiàn)；誤差傳遞較小，一個(gè)密文快損失僅有與其對(duì)應(yīng)的明文塊無(wú)法正常解密；不能隱藏明文的模式信息，相同明文對(duì)應(yīng)相同密文；對(duì)明文的主動(dòng)攻擊是可能的，信息塊可被替換、重排、刪除、重放。2022/10/2030電子編碼本模式電子編碼本模式（ECB）特點(diǎn)：2022/10/

密碼分組鏈接模式（CBC）

2022/10/2031

密碼分組鏈接模式（CBC）

2022/10/1531

密碼分組鏈接模式（CBC）

密碼分組鏈接模式（CBC）特點(diǎn)：能隱藏明文的模式信息，相同的明文對(duì)應(yīng)不同密文；對(duì)明文的主動(dòng)攻擊是不容易的，信息塊不容易被替換、重排、刪除、重放；安全性好于ECB；沒(méi)有已知的并行實(shí)現(xiàn)算法；誤差傳遞較大，一個(gè)密文塊損壞涉及其他明文塊無(wú)法解密還原。2022/10/2032

密碼分組鏈接模式（CBC）

密碼分組鏈接模式（CBC）特點(diǎn)密碼反饋模式（CFB）2022/10/2033密碼反饋模式（CFB）2022/10/1533

密碼反饋模式（CFB）

密碼反饋模式（CFB）特點(diǎn)：能隱藏明文的模式信息，相同的明文對(duì)應(yīng)不同密文；適用分組密碼和流密碼；需要共同的移位寄存器初始值；沒(méi)有已知的并行實(shí)現(xiàn)算法；誤差傳遞較大，一個(gè)密文塊損壞涉及其他明文塊無(wú)法解密還原。2022/10/2034

密碼反饋模式（CFB）

密碼反饋模式（CFB）特點(diǎn)：202輸出反饋模式（OFB）2022/10/2035輸出反饋模式（OFB）2022/10/1535

密碼反饋模式（OFB）

密碼反饋模式（OFB）特點(diǎn)：能隱藏明文的模式信息，相同的明文對(duì)應(yīng)不同密文；適用分組密碼和流密碼；誤差傳遞較大，一個(gè)密文塊損壞涉及其他明文塊無(wú)法解密還原；沒(méi)有已知的并行實(shí)現(xiàn)算法；安全性較CFB差。2022/10/2036

密碼反饋模式（OFB）

密碼反饋模式（OFB）特點(diǎn)：202

2.3.4其他對(duì)稱密碼簡(jiǎn)介

三重DESRC5IDEAAES算法2022/10/2037

2.3.4其他對(duì)稱密碼簡(jiǎn)介

三重DES2022/10/12.4公開密鑰密碼公開密鑰密碼又稱非對(duì)稱密鑰密碼或雙密鑰密碼加密密鑰和解密密鑰為兩個(gè)獨(dú)立密鑰。公開密鑰密碼的通信安全性取決于私鑰的保密性。2022/10/20382.4公開密鑰密碼公開密鑰密碼又稱非對(duì)稱密鑰密碼或雙密鑰密2.4.1公開密鑰理論基礎(chǔ)公開密鑰密碼是1976年由WhitfieldDiffie和MartinHellman在其“密碼學(xué)新方向”一文中提出的。單向陷門函數(shù)f(x)，必須滿足以下三個(gè)條件。①

給定x，計(jì)算y=f(x)是容易的；②

給定y,計(jì)算x使y=f(x)是困難的（所謂計(jì)算x=f-1(y)困難是指計(jì)算上相當(dāng)復(fù)雜，已無(wú)實(shí)際意義）；③

存在δ，已知δ時(shí)對(duì)給定的任何y，若相應(yīng)的x存在，則計(jì)算x使y=f(x)是容易的。公開密鑰密碼的核心思想2022/10/20392.4.1公開密鑰理論基礎(chǔ)公開密鑰密碼是1976年由Whi公開密鑰的應(yīng)用：加密模型2022/10/2040公開密鑰的應(yīng)用：加密模型2022/10/1540公開密鑰的應(yīng)用：認(rèn)證模型2022/10/2041公開密鑰的應(yīng)用：認(rèn)證模型2022/10/15412.4.2Diffie-Hellman密鑰交換算法數(shù)學(xué)知識(shí)原根素?cái)?shù)p的原根（primitiveroot）的定義：如果a是素?cái)?shù)p的原根，則數(shù)amodp,a2modp,…,ap-1modp是不同的并且包含從1到p-1之間的所有整數(shù)的某種排列。例子：3是7的原根。31mod7=3；32mod7=2；33mod7=6；34mod7=4；35mod7=5；36mod7=1。2022/10/20422.4.2Diffie-Hellman密鑰交換算法數(shù)學(xué)知識(shí)Diffie-Hellman密鑰交換算法離散對(duì)數(shù)若a是素?cái)?shù)p的一個(gè)原根，則相對(duì)于任意整數(shù)b（bmodp≠0），必然存在唯一的整數(shù)i（1≤i≤p-1），使得b≡aimodp，i稱為b的以a為基數(shù)且模p的冪指數(shù)，即離散對(duì)數(shù)。對(duì)于函數(shù)y=gxmodp，其中，g為素?cái)?shù)p的原根，y與x均為正整數(shù)，已知g、x、p，計(jì)算y是容易的；而已知y、g、p，計(jì)算x是困難的，即求解y的離散對(duì)數(shù)x。注1：“b≡amodp”等價(jià)于“bmodp=amodp”，稱為“b與a模p同余”注2：離散對(duì)數(shù)的求解為數(shù)學(xué)界公認(rèn)的困難問(wèn)題。2022/10/2043Diffie-Hellman密鑰交換算法離散對(duì)數(shù)2022/1Diffie-Hellman密鑰交換算法Alice和Bob協(xié)商好一個(gè)大素?cái)?shù)p，和大的整數(shù)g，1<g<p，g是p的原根。p和g無(wú)須保密，可為網(wǎng)絡(luò)上的所有用戶共享。當(dāng)Alice和Bob要進(jìn)行保密通信時(shí)，他們可以按如下步驟來(lái)做：①Alice選取大的隨機(jī)數(shù)x<p，并計(jì)算Y=gx(modP)；②Bob選取大的隨機(jī)數(shù)x<p，并計(jì)算Y=gx(modP)；③Alice將Y傳送給Bob，Bob將Y傳送給Alice；④Alice計(jì)算K=(Y)X(modP)，Bob計(jì)算K＝(Y)X(modP)顯而易見(jiàn)K=K=gxx(modP)，即Alice和Bob已獲得了相同的秘密值K。2022/10/2044Diffie-Hellman密鑰交換算法Alice和Bob協(xié)取模運(yùn)算法則(a+b)%p=（a%p+b%p）%p(a–b)%p=（a%p-b%p）%p(a*b)%p=（a%p*b%p）%p(ab)%p=((a

%p)b)%p例1：K=K=(Y)x(modp)=(Y)x(modp)=gxx(modP)例2:Dk(y)=21(y-3)mod26=(21y–11)mod26（仿射密碼）注：%為取模運(yùn)算mod2022/10/2045取模運(yùn)算法則(a+b)%p=（a%p+b%p）2.4.3RSA公開密鑰算法歐拉定理

歐拉函數(shù)：對(duì)于一個(gè)正整數(shù)n，由小于n且和n互素的正整數(shù)構(gòu)成的集合為Zn，這個(gè)集合被稱為n的完全余數(shù)集合。Zn包含的元素個(gè)數(shù)記做(n)，稱為歐拉函數(shù)，其中φ(1)被定義為1，但是并沒(méi)有任何實(shí)質(zhì)的意義。如果兩個(gè)素?cái)?shù)p和q，且n=p×q，則(n)=(p-1)(q-1)；歐拉定理的具體表述：正整數(shù)a與n互素，則a

(n)≡1modn。例子：n=15;p=3;q=5;Zn={1,2,4,7,8,11,13,14}n=p*q;(n)=|Zn|=(3-1)*(5-1)=8；28≡1mod15.2022/10/20462.4.3RSA公開密鑰算法歐拉定理

2022/10/152.4.3RSA公開密鑰算法歐拉定理的推論：給定兩個(gè)素?cái)?shù)p和q，以及兩個(gè)整數(shù)m、n，使得n=p×q，且0<m<n，對(duì)于任意整數(shù)k下列關(guān)系成立：mk(n)+1=mk(p-1)(q-1)+1≡mmodn。2022/10/20472.4.3RSA公開密鑰算法歐拉定理的推論：2022/10大整數(shù)因子分解大整數(shù)因子分解問(wèn)題：已知p、q為兩個(gè)大素?cái)?shù)，則求N=p×q是容易的，只需要一次乘法運(yùn)算；但已知N是兩個(gè)大素?cái)?shù)的乘積，要求將N分解，則在計(jì)算上是困難的，其運(yùn)行時(shí)間復(fù)雜程度接近于不可行。算法時(shí)間復(fù)雜性：如果輸入規(guī)模為n時(shí)，一個(gè)算法的運(yùn)行時(shí)間復(fù)雜度為O(n)，稱此算法為線性的；運(yùn)行時(shí)間復(fù)雜度為O(nk)，其中k為常量，稱此算法為多項(xiàng)式的；若有某常量t和多項(xiàng)式h(n)，使算法的運(yùn)行時(shí)間復(fù)雜度為O(th(n))，則稱此算法為指數(shù)的。一般說(shuō)來(lái)，在線性時(shí)間和多項(xiàng)式時(shí)間內(nèi)被認(rèn)為是可解決的，比多項(xiàng)式時(shí)間更壞的，尤其是指數(shù)時(shí)間被認(rèn)為是不可解決的。注：如果輸入規(guī)模太小，即使很復(fù)雜的算法也會(huì)變得可行的。2022/10/2048大整數(shù)因子分解大整數(shù)因子分解問(wèn)題：2022/10/1548RSA密碼算法

RSA密碼體制：是一種分組密碼，明文和密文均是0到n之間的整數(shù)，n通常為1024位二進(jìn)制數(shù)或309位十進(jìn)制數(shù)，明文空間P=密文空間C={x∈Z|0<x<n,Z為整數(shù)集合}。RSA密碼的密鑰生成具體步驟如下：①

選擇互異的素?cái)?shù)p和q，計(jì)算n=pq，(n)=(p-1)(q-1)；②

選擇整數(shù)e，使gcd((n),e)=1，且1<e<(n)；③

計(jì)算d，de-1mod(n)，即d為模(n)下e的乘法逆元；公鑰Pk={e,n}，私鑰Sk={d,n,p,q}加密：c=memodn；解密：m=cdmodn。2022/10/2049RSA密碼算法RSA密碼體制：2022/10/1549RSA例p=101，q＝113，n=11413，(n)=100×112＝11200。e=3533，求得de-1mod112006597mod11200，d=6597。公開n=11413和e=3533，明文9726，計(jì)算97263533mod11413=5761，發(fā)送密文5761。密文5761時(shí)，用d＝6597進(jìn)行解密，計(jì)算57616597（mod11413)=9726。2022/10/2050RSA例p=101，q＝113，n=11413，(n)=1RSA的安全性RSA是基于單向函數(shù)ek(x)=xe(modn)

，求逆計(jì)算是不可行的。解密的關(guān)鍵是了解陷門信息，即能夠分解n=pq，知道(n)=(p-1)(q-1)，從而解出解密私鑰d。如果要求RSA是安全的，p與q必為足夠大的素?cái)?shù);使分析者沒(méi)有辦法在多項(xiàng)式時(shí)間內(nèi)將n分解出來(lái)。RSA開發(fā)人員建議，p和q的選擇應(yīng)該是100位的十進(jìn)制素?cái)?shù)，模n的長(zhǎng)度至少是512bit。EDI攻擊標(biāo)準(zhǔn)使用的RSA算法中規(guī)定n的長(zhǎng)度為512-1024bit，必須是128倍數(shù)。國(guó)際數(shù)字簽名標(biāo)準(zhǔn)ISO/IEC9796中規(guī)定n的長(zhǎng)度為512bit。2022/10/2051RSA的安全性RSA是基于單向函數(shù)ek(x)=xe(modRSA的安全性

為抵抗現(xiàn)有整數(shù)分解算法，對(duì)p和q還有如下的要求：|p-q|很大，通常p和q的長(zhǎng)度相同；p-1和q-1分別含有大素因子p1和q1；p1-1和q1-1分別含有大素因子p2和q2；p+1和q+1分別含有大素因子p3和q3。注：素?cái)?shù)和合數(shù)的概念。2022/10/2052RSA的安全性為抵抗現(xiàn)有整數(shù)分解算法，對(duì)p和q還有如下2.4.4其他公開密鑰密碼簡(jiǎn)介基于大整數(shù)因子分解問(wèn)題:RSA密碼、Rabin密碼基于有限域上的離散對(duì)數(shù)問(wèn)題或者基于基于橢圓曲線上的離散對(duì)數(shù)問(wèn)題：Differ-Hellman公鑰交換體制、ElGamal密碼2022/10/20532.4.4其他公開密鑰密碼簡(jiǎn)介基于大整數(shù)因子分解問(wèn)題:202.5消息認(rèn)證2.5.1概述信息完整性是信息安全的三個(gè)基本目標(biāo)之一威脅信息完整性的行為主要包括：偽造：假冒他人的信息源向網(wǎng)絡(luò)中發(fā)布消息；內(nèi)容修改：對(duì)消息的內(nèi)容進(jìn)行插入、刪除、變換和修改；順序修改：對(duì)消息進(jìn)行插入、刪除或重組消息序列；時(shí)間修改：針對(duì)網(wǎng)絡(luò)中的消息，實(shí)施延遲或重放否認(rèn)：接受者否認(rèn)收到消息，發(fā)送者否認(rèn)發(fā)送過(guò)消息。2022/10/20542.5消息認(rèn)證2.5.1概述2022/10/15542.5消息認(rèn)證消息認(rèn)證是保證信息完整性的重要措施，目的包括：證明消息的信源和信宿的真實(shí)性，消息內(nèi)容是否曾受到偶然或有意的篡改，消息的序號(hào)和時(shí)間性是否正確。消息認(rèn)證由具有認(rèn)證功能的函數(shù)來(lái)實(shí)現(xiàn)的:消息加密：用消息的完整密文作為消息的認(rèn)證符；消息認(rèn)證碼MAC（MessageAuthenticationCode）：也稱密碼校驗(yàn)和，使用密碼對(duì)消息加密，生成固定長(zhǎng)度的認(rèn)證符；消息編碼：是針對(duì)信源消息的編碼函數(shù)，使用編碼抵抗針對(duì)消息的攻擊。2022/10/20552.5消息認(rèn)證消息認(rèn)證是保證信息完整性的重要措施，目的包括2.5.2認(rèn)證函數(shù)消息加密消息認(rèn)證碼MAC消息編碼2022/10/20562.5.2認(rèn)證函數(shù)消息加密2022/10/1556消息加密函數(shù)對(duì)稱密鑰密碼對(duì)消息加密，不僅具有機(jī)密性，同時(shí)也具有一定的可認(rèn)證性;公開密鑰密碼本身就提供認(rèn)證功能，主要基于私鑰加密、公鑰解密以及反之亦然的特性。2022/10/2057消息加密函數(shù)對(duì)稱密鑰密碼對(duì)消息加密，不僅具有機(jī)密性，同時(shí)也具消息認(rèn)證碼（MAC）消息認(rèn)證碼MAC的基本思想：利用事先約定的密碼，加密生成一個(gè)固定長(zhǎng)度的短數(shù)據(jù)塊MAC，并將MAC附加到消息之后，一起發(fā)送給接收者；接收者使用相同密碼對(duì)消息原文進(jìn)行加密得到新的MAC，比較新的MAC和隨消息一同發(fā)來(lái)的MAC，如果相同則未受到篡改。2022/10/2058消息認(rèn)證碼（MAC）消息認(rèn)證碼MAC的基本思想：2022/1生成消息認(rèn)證碼的方法：基于加密函數(shù)的認(rèn)證碼。例子：DES加密+CBC模式，消息認(rèn)證符可以是整個(gè)64位的On，也可以是On最左邊的M位基于消息摘要的認(rèn)證碼（在散列函數(shù)中討論）2022/10/2059生成消息認(rèn)證碼的方法：2022/10/1559消息編碼消息編碼認(rèn)證的基本思想：在消息中引入冗余度，使通過(guò)信道傳送的可能序列集M（編碼集）大于消息集S（信源集）。發(fā)送方從M中選出用來(lái)代表消息的許用序列Li，即對(duì)信息進(jìn)行編碼；接收方根據(jù)編碼規(guī)則，進(jìn)行解碼，還原出發(fā)送方按此規(guī)則向他傳來(lái)的消息。竄擾者不知道被選定的編碼規(guī)則，因而所偽造的假碼字多是M中的禁用序列，接收方將以很高的概率將其檢測(cè)出來(lái)，并拒絕通過(guò)認(rèn)證。2022/10/2060消息編碼消息編碼認(rèn)證的基本思想：2022/10/1560消息編碼信源S編碼法則L01禁用序列L0001001，11L1001101，10L2011000，11L3011100，10信源集S={0,1}，編碼集M={00,01,10,11}。定義編碼規(guī)則L包含四個(gè)不同的子規(guī)則{L0,L1,L2,L3,}。如果決定采用L0，

則以發(fā)送消息“00”代表信源“0”，發(fā)送消息“10”代表信源“1”。在子規(guī)則L0下，消息“00”和“10”是合法的，而消息“01”和“11”在L0之下不合法，收方將拒收這兩個(gè)消息。2022/10/2061消息編碼L0001001，11L1001101，10L2012.5.3散列函數(shù)散列函數(shù)（HashFunction）的目的將任意長(zhǎng)的消息映射成一個(gè)固定長(zhǎng)度的散列值（hash值），也稱為消息摘要。消息摘要可以作為認(rèn)證符，完成消息認(rèn)證。散列函數(shù)的健壯性弱無(wú)碰撞特性

散列函數(shù)h被稱為是弱無(wú)碰撞的，是指在消息特定的明文空間X中，給定消息x∈X，在計(jì)算上幾乎找不到不同于x的x'，x'∈X，使得h(x)=h(x')。

強(qiáng)無(wú)碰撞特性

散列函數(shù)h被稱為是強(qiáng)無(wú)碰撞的，是指在計(jì)算上難以找到與x相異的x'，滿足h(x)=h(x')，x'可以不屬于X。單向性

散列函數(shù)h被稱為單向的，是指通過(guò)h的逆函數(shù)h-1來(lái)求得散列值h(x)的消息原文x，在計(jì)算上不可行。2022/10/20622.5.3散列函數(shù)散列函數(shù)（HashFunction）的散列值的安全長(zhǎng)度“生日悖論”如果一個(gè)房間里有23個(gè)或23個(gè)以上的人，那么至少有兩個(gè)人的生日相同的概率要大于50%。對(duì)于60或者更多的人，這種概率要大于99%。生日悖論對(duì)于散列函數(shù)的意義n位長(zhǎng)度的散列值，可能發(fā)生一次碰撞的概率為50%的測(cè)試次數(shù)不是2n次，而是大約2n/2

次。一個(gè)40位的散列值將是不安全的，因?yàn)榇蠹s100萬(wàn)個(gè)隨機(jī)散列值中將找到一個(gè)碰撞的概率為50%，消息摘要的長(zhǎng)度不低于為128位。2022/10/2063散列值的安全長(zhǎng)度“生日悖論”2022/10/1563MD51991年Rivest對(duì)MD4的進(jìn)行改進(jìn)升級(jí)，提出了MD5（MessageDigestAlgorithm5）。MD5具有更高的安全性，目前被廣泛使用。2022/10/2064MD51991年Rivest對(duì)MD4的進(jìn)行改進(jìn)升級(jí)，提出了MMD5A、B、C、D是鏈接變量；L為調(diào)整后的信息長(zhǎng)度；n為512位信息分組的數(shù)量；X[0,15]用來(lái)存儲(chǔ)512位信息；M為調(diào)整后的信息。2022/10/2065MD5A、B、C、D是鏈接變量；2022/10/1565MD5四輪運(yùn)算涉及四個(gè)函數(shù)：E（X，Y，Z）=（X∧Y）∨（(?X）∧Z）F（X，Y，Z）=（X∧Z）∨（Y∧（?Z））G（X，Y，Z）=XYZH（X，Y，Z）=Y（X∨（?Z））第一輪：EE(a,b,c,d,Mj,s,tk)：a=b+((a+(E(b,c,d)+Mj+tk)<<s)；EE(a,b,c,d,M0,,7,0xd76aa478);EE(d,a,b,c,M1,,12,0xe8c7b756);EE(c,d,a,b,M2,,17,0x242070db);EE(b,c,d,a,M3,,22,0xc1bdceee);tk的計(jì)算方法：整個(gè)四輪操作總共是64步，在第k步tk是232Xabs(sin(k))的整數(shù)部分，k的單位是弧度。2022/10/2066MD5四輪運(yùn)算涉及四個(gè)函數(shù)：2022/10/1566MD5第二輪：FF(a,b,c,d,Mj,s,ti)：a=b+((a+(F(b,c,d)+Mj+tk)<<s)；第三輪：GG(a,b,c,d,Mj,s,ti)：a=b+((a+(G(b,c,d)+Mj+tk)<<s)；第四輪：HH(a,b,c,d,Mj,s,ti)：a=b+((a+(H(b,c,d)+Mj+tk)<<s)；2022/10/2067MD5第二輪：2022/10/15672.5.4數(shù)字簽名數(shù)字簽名（DigitalSignature）在ISO7498-2標(biāo)準(zhǔn)定義為：“附加在數(shù)據(jù)單元上的一些數(shù)據(jù)或是對(duì)數(shù)據(jù)單元所作的密碼變換，這種數(shù)據(jù)或變換可以被數(shù)據(jù)單元的接收者用來(lái)確認(rèn)數(shù)據(jù)單元來(lái)源和數(shù)據(jù)單元的完整性，并保護(hù)數(shù)據(jù)不會(huì)被人偽造”。美國(guó)電子簽名標(biāo)準(zhǔn)對(duì)數(shù)字簽名作了如下解釋：“數(shù)字簽名是利用一套規(guī)則和一個(gè)參數(shù)對(duì)數(shù)據(jù)進(jìn)行計(jì)算所得的結(jié)果，用此結(jié)果能夠確認(rèn)簽名者的身份和數(shù)據(jù)的完整性”。一般來(lái)說(shuō)，數(shù)字簽名可以被理解為：通過(guò)某種密碼運(yùn)算生成一系列符號(hào)及代碼，構(gòu)成可以用來(lái)進(jìn)行數(shù)據(jù)來(lái)源驗(yàn)證的數(shù)字信息。2022/10/20682.5.4數(shù)字簽名2022/10/15682.5.4數(shù)字簽名從簽名形式上分，數(shù)字簽名有兩種一種是對(duì)整個(gè)消息的簽名，一種是對(duì)壓縮消息的簽名，它們都是附加在被簽名消息之后或在某一特定位置上的一段數(shù)據(jù)信息。數(shù)字簽名主要目的保證收方能夠確認(rèn)或驗(yàn)證發(fā)方的簽名，但不能偽造；發(fā)方發(fā)出簽名消息后，不能否認(rèn)所簽發(fā)的消息。2022/10/20692.5.4數(shù)字簽名從簽名形式上分，數(shù)字簽名有兩種2022/2.5.4數(shù)字簽名設(shè)計(jì)數(shù)字簽名必須滿足下列條件：簽名必須基于一個(gè)待簽名信息的位串模板；簽名必須使用某些對(duì)發(fā)送方來(lái)說(shuō)是唯一的信息，以防止雙方的偽造與否認(rèn)；必須相對(duì)容易生成、識(shí)別和驗(yàn)證數(shù)字簽名；偽造該數(shù)字簽名在計(jì)算復(fù)雜性意義上具有不可行性既包括對(duì)一個(gè)已有的數(shù)字簽名構(gòu)造新的消息，也包括對(duì)一個(gè)給定消息偽造一個(gè)數(shù)字簽名。2022/10/20702.5.