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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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