第0章-數(shù)論引導(dǎo)篇

1、李鋒lfgzdx7210513@sina.com2010.3,信息安全數(shù)學(xué)基礎(chǔ)數(shù)論篇,2024/3/19,2,課程內(nèi)容的設(shè)置,初等數(shù)論抽象代數(shù)：群論關(guān)心素?cái)?shù)、余數(shù)、有限域,,,2024/3/19,3,課程要求,本課程屬于數(shù)學(xué)理論及應(yīng)用課程，既強(qiáng)調(diào)對數(shù)學(xué)理論的掌握 ( 一些數(shù)學(xué)定理的證明 ) ，更強(qiáng)調(diào)數(shù)學(xué)理論的應(yīng)用，特別是在信息安全和密碼學(xué)方面的應(yīng)用。希望在教師引導(dǎo)下，學(xué)生逐步學(xué)會和掌握現(xiàn)代數(shù)學(xué)語言，進(jìn)而了解信息安全學(xué)科的最新進(jìn)

2、展，以利今后的創(chuàng)新工作。,2024/3/19,4,實(shí)驗(yàn)（上機(jī)）內(nèi)容和基本要求 本課程無實(shí)驗(yàn)和上機(jī)的教學(xué)安排，但要求學(xué)生結(jié)合本專業(yè)的特點(diǎn)和所研究的課題，選擇部分算法自己上機(jī)實(shí)現(xiàn)。要求學(xué)生熟悉至少一門數(shù)學(xué)軟件平臺（ Mathematica/ matlab/Maple ）和至少一種編程語言。,2024/3/19,5,課程的重點(diǎn)是密碼學(xué)（對稱密碼學(xué)和非對稱密碼學(xué)）所涉及數(shù)學(xué)理論和有效算法實(shí)現(xiàn)： 計(jì)算復(fù)雜性、歐幾里

3、得除法、模同余、歐拉定理、模重復(fù)平方計(jì)算、蒙哥馬利算法、中國剩余定理、二次同余、原根、有限群、對稱群、多項(xiàng)式、本原多項(xiàng)式、有限域及其構(gòu)造、橢圓曲線、素?cái)?shù)產(chǎn)生、大數(shù)分解。特別對 2002 年印度數(shù)學(xué)家發(fā)現(xiàn)的 AKS 素性檢驗(yàn)給出了詳細(xì)證明。,2024/3/19,6,康德Immanuel Kant (1724-1804),2024/3/19,7,關(guān)于數(shù)論,整數(shù)的理論：最古老的以整除性為中心數(shù)學(xué)是科學(xué)之王，數(shù)論是數(shù)學(xué)之王純數(shù)學(xué)：一切

4、都為了解方程以嚴(yán)格和簡潔著稱，既豐富又深刻問題淺顯易懂但特別迷人 從經(jīng)驗(yàn)歸納但難于證,2024/3/19,8,傳奇人物,,歐幾里德 畢達(dá)格拉斯,2024/3/19,9,傳奇人物,,費(fèi)馬,歐拉,,2024/3/19,10,傳奇人物,,拉格朗日 高斯,2024/3/19,11,數(shù)學(xué)基礎(chǔ)的意義,計(jì)算機(jī)的大家都是數(shù)學(xué)家離散數(shù)學(xué)不可或缺的一部分所有深奧的內(nèi)容背后其實(shí)都是一個簡單的思想重計(jì)算方法，重應(yīng)

5、用數(shù)學(xué)思維最基本的兩大方面應(yīng)該是“證”和“算”但證明更有意義,2024/3/19,12,對稱,,2024/3/19,13,互聯(lián)網(wǎng)安全,計(jì)算機(jī)安全,保密通信數(shù)據(jù)安全,信息安全,,,,,2024/3/19,14,一個欺騙的例子：中間人,A：誠實(shí)的人,B：保單填寫者,C對B說“我是A”；對A說“我是B”通過制作假網(wǎng)站,假公鑰,讓B上當(dāng),,,,,,2024/3/19,15,簡單數(shù)字簽名,原始信息,Hash算法,Hash值,加密,加

6、密結(jié)果（稱為簽名）,私鑰,原始信息,Hash算法,Hash值,解密,公鑰,Hash值,,,,,,,=?,Sender,Receiver,2024/3/19,16,原始信息,Hash算法,Hash值,加密,加密結(jié)果（數(shù)字簽名）,發(fā)送者私鑰,,,原始信息,Hash算法,Hash值,解密,發(fā)送者公鑰,Hash值,,,,=?,Receiver,加密信息,接收者公鑰,解密信息,,,接收者私鑰,Sender,帶加密的數(shù)字簽名,,,

7、2024/3/19,17,數(shù)論與密碼,隨著計(jì)算機(jī)技術(shù)，信息技術(shù)，通信技術(shù)的迅速發(fā)展，以及網(wǎng)絡(luò)的普及，我們已經(jīng)進(jìn)入到信息社會．人們對信息的需求是與日俱增，不僅從語言交談和報(bào)紙，電視及廣播等獲取信息，而且也從互聯(lián)網(wǎng)上獲取信息，特別是電子郵件使得人們的文字交流更為快捷．此外，人們也將信息用于日常的政務(wù)活動和商業(yè)活動中，如電子政務(wù)和電子商務(wù)等，在這些信息交流中，人們自然要考慮信息的機(jī)密性、真實(shí)性、完整性和不可抵賴性。機(jī)密性是保證信息不能被未經(jīng)

8、授權(quán)者閱讀。真實(shí)性或可鑒性是保證收到的信息確實(shí)是由發(fā)送者發(fā)送的。完整性是保證信息在傳遞過程中沒有被篡改，更換。不可抵賴性是保證發(fā)送者不能否認(rèn)其發(fā)送過信息以及接受信息否認(rèn)接受信息。 密碼技術(shù)是保證信息安全的核心技術(shù)。,2024/3/19,18,傳統(tǒng)密碼,通常保密通信模型 A 方將 明文M通過安全信道發(fā)給對方B。實(shí)現(xiàn)保密通信的條件：1、面對面的交談。2、沒有竊聽可能。存在問題：1、不能面對面交談。2、有

9、竊聽可能。,2024/3/19,19,對稱密碼模型,對稱密碼（私鑰密碼） 加解密用同一個密鑰，大多數(shù)常用的軟件如Word、WinRAR都采用這類方法。,明文,密文,,密鑰k,,2024/3/19,20,對稱密碼,實(shí)現(xiàn)保密通信的條件：1、雙方有相同的密鑰K，2、第三方無法破解密文C，得到明文M。存在問題：1、需要多人保守密鑰的機(jī)密性。（密鑰數(shù)量（多于2個）不能實(shí)現(xiàn)數(shù)字簽名）。2、需要定期或不定期的更換密鑰。3、密鑰管理較為

10、困難。（n個人的密碼系統(tǒng)要n(n-1)/2個）例如：愷撒密碼系統(tǒng)，密碼本，3-DES，AES。涉及數(shù)學(xué)問題，模運(yùn)算，置換，域的構(gòu)造,2024/3/19,21,非對稱密碼,非對稱密碼（公鑰密碼）　加解密采用不同的密鑰，在通信中具有重要意義。如果你想把密鑰告訴一個遠(yuǎn)在美國的朋友，難道要坐飛機(jī)趕過去嗎……,明文,密文,,密鑰k1,,密鑰k2,2024/3/19,22,非對稱密碼,實(shí)現(xiàn)保密通信的條件：1、保密解密密鑰d.2、第三方無法

11、破解密文C，得到明文M。3、由加密密鑰e無法推導(dǎo)出d,除非知道某些線索。優(yōu)點(diǎn)：1、只需一人保守解密密鑰的機(jī)密性。（可實(shí)現(xiàn)數(shù)字簽名）2、可以隨時更換密鑰。3、密鑰管理較為簡單。（n個人的密碼系統(tǒng)只需要n把加密密鑰，且可以在公開途徑獲得）,2024/3/19,23,公鑰密碼學(xué)概述： 1976年，Diffie和Hellman在美國國家計(jì)算機(jī)會議上首次提出了公開密鑰密碼學(xué)的概念，并發(fā)表了開創(chuàng)性的論文“New Direction

12、 in Cryptography”（“密碼學(xué)的新方向”）。人們就積極尋求滿足上述需求的公鑰密碼系統(tǒng)，也就是說，要尋求單向陷門函數(shù)，其從一方是很容易計(jì)算的（知道加密密鑰），而從另一方無法計(jì)算（不知道解密密鑰）例1、從門內(nèi)出來容易，但進(jìn)入門內(nèi)需要鑰匙。例2、將信放進(jìn)郵箱容易，但取出郵件需要鑰匙。,2024/3/19,24,第一個公鑰密碼系統(tǒng)：基于背包問題的背包公鑰密碼系統(tǒng)。目前，大家所公認(rèn)的高效安全的公鑰密碼體制，按其所基于的數(shù)學(xué)難題

13、可分為三類：一、基于大整數(shù)分解難題的公鑰體制，例如RSA和Rabin-William體制；二、基于有限域上離散對數(shù)難題的公鑰體制，例如美國政府的數(shù)字簽名算法DSA,Diffie-Hellman的密鑰交換體制,ElGamal加密和簽名體制等;三、基于橢圓曲線離散對數(shù)難題的公鑰體制，即橢圓曲線密碼系統(tǒng)簡稱ECC，絕大多數(shù)是基于有限域上離散對數(shù)的數(shù)學(xué)難題，優(yōu)勢較大，如同等強(qiáng)度的橢圓曲線與RSA比較，密鑰較短。,2024/3/19,25,

14、RSA公鑰密碼系統(tǒng)RSA公鑰密碼系統(tǒng)以其 發(fā)明者R.Rivest, A.Shamir 和 L.Adleman的三個姓的首個字母命名的，它是應(yīng)用最廣泛的公鑰密碼系統(tǒng)，其于大整數(shù)因數(shù)分解問題。RSA公鑰密碼系統(tǒng)的描述：每個使用者產(chǎn)生各自的公鑰e和私鑰d。1、隨機(jī)產(chǎn)生兩個不同的大素?cái)?shù)p和q，具有相同的階；（何謂素?cái)?shù)）2、計(jì)算n=pq和(p-1)(q-1);（何謂歐拉函數(shù)）3、隨機(jī)選取整數(shù)e,1<e< (p-1)(q-1)

15、,其中 e 與(p-1)(q-1）沒有公約數(shù)；（何謂公約數(shù)）3、運(yùn)用廣義歐幾里得算法，計(jì)算唯一的整數(shù)d, e,1<d< (p-1)(q-1),使得ed-1被(p-1)(q-1）整除；（何謂廣義歐幾里得算法和整除）4、公鑰是n,e，私鑰是d;加密過程：解密過程：,2024/3/19,26,涉及數(shù)學(xué)問題,整除b|a,因數(shù) 二次剩余歐幾里得算法

16、 指標(biāo)廣義歐幾里得算法 原根或素域生成元素?cái)?shù) 素?cái)?shù)的產(chǎn)生 整數(shù)的分解 有限群公因數(shù) 最大公因數(shù) 置換群模運(yùn)算 環(huán)中國剩余定理

17、 域歐拉函數(shù) 有限域的生成歐拉定理 安全橢圓曲線費(fèi)馬小定理 要學(xué)習(xí)數(shù)學(xué)語言，并用數(shù)學(xué)語言描述信息安全問題例如，密碼系統(tǒng)，安全性證明,2024/3/19,27,用數(shù)學(xué)語言描述RSA系統(tǒng),每個使用者產(chǎn)生各自的公鑰和私鑰1、隨機(jī)產(chǎn)生兩個不同的大素?cái)?shù)p和q，具有

18、相同的階；以下略；,2024/3/19,28,學(xué)習(xí)主要內(nèi)容,分為三類：數(shù)論、代數(shù)、橢圓曲線具體是：整除b|a,因數(shù) 二次剩余歐幾里得算法 指標(biāo)廣義歐幾里得算法 原根或素域生成元素?cái)?shù) 素?cái)?shù)的產(chǎn)生 整數(shù)的分解 安全橢圓曲線公因數(shù) 最大公因

19、數(shù)模運(yùn)算中國剩余定理歐拉函數(shù)歐拉定理費(fèi)馬小定理,2024/3/19,29,根據(jù)公鑰解釋如下特性,機(jī)密性真實(shí)性完整性不可抵賴性唯一性 認(rèn)證,2024/3/19,30,抽象代數(shù),近世代數(shù)，代數(shù)結(jié)構(gòu)正整數(shù)與正偶數(shù)那個多？整體大于部分？n=2m：一一對應(yīng)？一條直線上的點(diǎn)與一個平面上的點(diǎn)哪個多？理想、群、環(huán)、域、格、流形…,2024/3/19,31,信息安全數(shù)學(xué)基礎(chǔ),上課要求:1) 不準(zhǔn)遲到，不準(zhǔn)曠課；2）

20、成績分布情況； 平時+作業(yè)：30分 考試：70分交流方式：lfgzdx7210513@sina.com 課外討論等,2024/3/19,32,參考書目,1、《信息安全數(shù)學(xué)基礎(chǔ)》陳恭亮，清華大學(xué)出版社，2004.6 2、《信息安全數(shù)學(xué)基礎(chǔ)》覃中平等編著，清華大學(xué)出版社，2006.83、《信息安全數(shù)學(xué)基礎(chǔ)》裴定一等編著，人民郵電出版社，2007.44、《Number Theories and Relat