數(shù)論與信息安全(已修改)
2024-11-04 21:01 本頁面
【正文】 數(shù)論與信息安全 王曉峰 深圳大學(xué)數(shù)學(xué)與計算科學(xué)學(xué)院 目錄 1. 引言 2. 歷史背景與若干基本概念 3. 初等數(shù)論 4. 公鑰密碼 5. 量子計算與量子密碼介紹 * 6. 實用例子： PGP* 1. 引言 ? 研究秘密通信 ? 保證通信安全 目的及意義 1) 分組密碼 （ block ciphers） 第一類 對稱密碼 2) 流密碼 （ stream ciphers） 第二類 對稱密碼 密碼分類 非 對稱密碼 （ asymmetric ciphers） 1) 秘密密鑰 密碼 2) 公開密鑰 密碼 對稱密碼 （ symmetric ciphers） 數(shù)學(xué)基礎(chǔ) 1) 數(shù)論知識 2) 群論基礎(chǔ) 3) 有限域 4) 信息論 5) 概率論 6) 可計算理論 2. 歷史背景與密碼學(xué)基本概念 ? 傳輸密文的發(fā)明地 古希臘 公元前 2世紀(jì)，一個叫 Polybius的希臘人設(shè)計了一種將字母編碼成符號對的方法，他使用了一個稱為 Polybius的校驗表 : 1 2 3 4 51 a b c d e2 f g h i j k3 l m n o p4 q r s t u5 v w x y z ? 兩次世界大戰(zhàn)扮演重要角色 Arthur Scherbius于 1919年設(shè)計出了歷史上最著名的密碼機(jī) —德國的 Enigma機(jī) , 在二次世界大戰(zhàn)期間 , Enigma曾作為德國陸 、 海 、 空三軍最高級密碼機(jī) . Enigma機(jī)使用了 3個正規(guī)輪和 1個反射輪 . 這使得英軍從1942年 2月到 12月都沒能解讀出德國潛艇發(fā)出的信號 . 4輪 Enigma機(jī)在 1944年裝備德國海軍 . 轉(zhuǎn)輪密碼機(jī)的使用大大提高了密碼加密速度 , 但由于密鑰量有限 , 到二戰(zhàn)中后期時 , 引出了一場關(guān)于加密與破譯的對抗 . 二次大戰(zhàn)期間 , 波蘭人和英國人破譯了 Enigma密碼 , 美國密碼分析者攻破了日本的 RED, ORANGE和PURPLE密碼 , 這對聯(lián)軍在二次世界大戰(zhàn)中獲勝起到了關(guān)鍵性作用 , 是密碼分析最偉大的成功 . ? 19701977： 近代密碼學(xué)與計算機(jī)技術(shù)、電子通信技術(shù)緊密相關(guān) . 在這一階段 , 密碼理論蓬勃發(fā)展 , 密碼算法設(shè)計與分析互相促進(jìn) , 出現(xiàn)了大量的密碼算法和各種攻擊方法 . 另外 , 密碼使用的范圍也在不斷擴(kuò)張 , 而且出現(xiàn)了許多通用的加密標(biāo)準(zhǔn) , 促進(jìn)網(wǎng)絡(luò)和技術(shù)的發(fā)展 . 七十年代早期 Feistel 在 IBM做的工作和 1977年美國官方宣布將 DES作為數(shù)據(jù)加密標(biāo)準(zhǔn)算法 . 標(biāo)志著密碼學(xué)的理論與技術(shù)的劃時代的革命性變革 , 宣布了近代密碼學(xué)的開始 . ? 1976: 1976年 “密碼學(xué)的新方向” (New Directions in Cryptography)一文 , 提出了適應(yīng)網(wǎng)絡(luò)上保密通信的公鑰密碼思想 , 開辟了公開密鑰密碼學(xué)的新領(lǐng)域 , 掀起了公鑰密碼研究的序幕 . 受他們的思想啟迪 , 各種公鑰密碼體制被提出 , 特別是 1978年 RSA (Rivest, Shamir, Adleman) 公鑰密碼體制的出現(xiàn) , 成為公鑰密碼的杰出代表 , 并成為事實標(biāo)準(zhǔn) , 在密碼學(xué)史上是一個里程碑 . 可以這么說 : “沒有公鑰密碼的研究就沒有近代密碼學(xué)” . ? 2020? 混沌密碼？ 量子密碼？ ? 密碼學(xué)基本概念 ? 如何達(dá)成秘密通信 密碼編碼學(xué) (cryptography)； ? 如何破譯秘密通信 密碼分析學(xué) (cryptanalysis). 密碼學(xué)泛指一切有關(guān)研究密碼通信的學(xué) 問，包括： 即： )( mEc ? )( cDm ? 信道 m 加密 c 破譯者 c 解密 m ? 基本概念 m: 明文 (Plaintext) c: 密文 (Ciphertext) 加密 (算法 )：把明文經(jīng)某種方式處理成他人難以 理解的密文 . 解密 (算法 )：將密文用特定的變換還原成明文 . )( mEc ? )( cDm ? 信道 m 加密 c c 解密 m 加密密鑰 解 密密鑰 密鑰 (K): 用以控制加密和解密的一定長度的符號串 . 采用密鑰后， 保密通信過程則為： 例如：明文為 during the last twenty years there has been an explosion of public academic research in cryptography K=5 加密算法： 1. 將明文 m按每 5個字符分組： durin gthel asttw entyy earst hereh asbee nanex plosi onofp ublic acade micre searc hincr yptog raphy 2. 每組反序得密文 c： nirudlehtgwttsayytsraehereheebsaxenanisolppfonocilbuedacaercimcraesrihgotpyyhpar ? 理論安全與實際安全 1949年， Shannon 提出如下的安全問題： 1. 當(dāng)破譯者有無限制的時間和無限制的計算能力 時一個密碼系統(tǒng)的安全性； 2. 當(dāng)破譯者在有限的時間和有限的計算能力時， 一個密碼系統(tǒng)的安全性 . ? 計算復(fù)雜性 Turing machine amp。 putability Turing machine: 一個有限控制器； 一條右端無限延長的輸入帶； 一個能左右移動的讀寫頭 . T urin g ma chine : ? 一個有限狀態(tài)控制器 C ( 狀態(tài)集 : Q ={ q1, q2, … , qm}) ； ? 一條右端無限延長的輸入帶 T ； ? 能左右移動的讀寫頭 ( 字母表： S ={ s1, s2, … , sn}). T 1 0 0 1 1 1 0 0 …….. H C: qi Turing machine 的特點(diǎn)： 非常簡單的數(shù)學(xué)模型 ； 本質(zhì)上類似于現(xiàn)代計算機(jī) 定義 ：一數(shù)論函數(shù)稱為可計算當(dāng)且僅當(dāng)它是 Turing machine可計算 . 不可計算的問題 計算問題分類 現(xiàn)實不可計算的問題 可計算的問題 現(xiàn)實可計算的問題 ? 計算問題分類 ? 計算問題的時間復(fù)雜性 記一可計算問題的輸入數(shù)據(jù)的二進(jìn)制數(shù)串的長度為 n, 則計算此問題的時間 (Turing machine
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1