信息安全數(shù)學(xué)基礎(chǔ)第5章原根和階ppt課件

1、第第5章章 原根和階原根和階信息安全數(shù)學(xué)基礎(chǔ) 第5章 引子在密碼學(xué)中, 有很多基于離散對(duì)數(shù)問(wèn)題的密碼算法和協(xié)議, 比如ElGamal公鑰密碼算法, Diffie-Hellman密鑰協(xié)商算法, 美國(guó)的數(shù)字簽名算法DSA等等. 學(xué)習(xí)原根的知識(shí)有助于理解離散對(duì)數(shù)問(wèn)題.進(jìn)一步地，理解離散對(duì)數(shù)問(wèn)題也是理解橢圓曲線(xiàn)密碼學(xué)的基礎(chǔ)。信息安全數(shù)學(xué)基礎(chǔ) 第5章 5.1 5.1 原根和階原根和階 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -定義定義 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -方法？方法？ 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -例題例題 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階-

2、 -例題例題 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -例題例題 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -性質(zhì)性質(zhì) 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -性質(zhì)性質(zhì) 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -性質(zhì)性質(zhì) 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -例題例題 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -例題例題 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -性質(zhì)性質(zhì) 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 【例5.1.6】 已知整數(shù)5模17的階為ord17 (5)=16. 因?yàn)?-15(mod 17), 則由【性質(zhì)5.1.1】, 整

3、數(shù)7模17的階為16. 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -例題例題 0 1 2 3 45 6 789 10 11 12 13 14 151 5 8 6 13 14 2 10 16 12 9 11 43 15 7信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -舉例舉例 012345157171311信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -性質(zhì)性質(zhì) 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -舉例舉例 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -性質(zhì)性質(zhì) 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根和階原根和階- -性質(zhì)性質(zhì) 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息

4、安全數(shù)學(xué)基礎(chǔ) 第5章 【例5.1.11】 由ord17(5)16可知5是模17的原根, 由原根5就可以求出17的所有原根.解: 模17的所有原根為51, 53, 55 , 57, 59, 511, 513, 515. 即515(mod 17), 536(mod 17), 5514(mod 17),5710(mod 17), 5912(mod 17), 51111(mod 17),51313(mod 17), 5156(mod 17).信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 原根存在的充分必要條件 信息安全數(shù)學(xué)基礎(chǔ) 第5章 5.1.3 5.1.3 素?cái)?shù)的原根

5、素?cái)?shù)的原根 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 5.2 5.2 離散對(duì)數(shù)離散對(duì)數(shù) 信息安全數(shù)學(xué)基礎(chǔ) 第5章 離散對(duì)數(shù)離散對(duì)數(shù)- -定義定義 信息安全數(shù)學(xué)基礎(chǔ) 第5章 離散對(duì)數(shù)離散對(duì)數(shù)- -例題例題【例5.2.1】 已知5是模17的原根. 求10對(duì)模17的離散對(duì)數(shù).解: 先構(gòu)造以5為底的階函數(shù)表.再構(gòu)造離散對(duì)數(shù)表. 可得, 10對(duì)模17的離散對(duì)數(shù)為7.1234567891011121314151658613142101612911431571a123456789101112131415161661312

6、1315210711945148信息安全數(shù)學(xué)基礎(chǔ) 第5章 離散對(duì)數(shù)離散對(duì)數(shù)- -性質(zhì)性質(zhì) 信息安全數(shù)學(xué)基礎(chǔ) 第5章 離散對(duì)數(shù)離散對(duì)數(shù)- -舉例舉例 信息安全數(shù)學(xué)基礎(chǔ) 第5章 離散對(duì)數(shù)離散對(duì)數(shù)- -舉例舉例 信息安全數(shù)學(xué)基礎(chǔ) 第5章 5.35.3離散對(duì)數(shù)在密碼學(xué)中的應(yīng)用離散對(duì)數(shù)在密碼學(xué)中的應(yīng)用離散對(duì)數(shù)問(wèn)題在密碼學(xué)中的應(yīng)用, 主要包括了ElGamal密碼算法、Diffie-Hellman密鑰協(xié)商算法、數(shù)字簽名標(biāo)準(zhǔn)(DSS)等. 這里我們介紹ElGamal密碼算法, 以及DSS參數(shù)選取時(shí)用到的本章的相關(guān)知識(shí).信息安全數(shù)學(xué)基礎(chǔ) 第5章 5.3.1 ELGamal5.3.1 ELGamal密碼算法密碼算法ELGamal密碼算法是一個(gè)非對(duì)稱(chēng)加密算法, 由ELGamal在1985提出. 既可以用于加密, 也可以用于簽名, 其安全性依賴(lài)于離散對(duì)數(shù)問(wèn)題. ELGamal數(shù)字簽名算法的一個(gè)變體就是數(shù)字簽名標(biāo)準(zhǔn)DSS）. 下面給出ELGamal算法的描述.信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 5.3.2 5.3.2 數(shù)字簽名標(biāo)準(zhǔn)的參數(shù)選取數(shù)字簽名標(biāo)準(zhǔn)的參數(shù)選取1991年8月, NIST頒發(fā)了一個(gè)通告, 提出將數(shù)字簽名算法DSA用于數(shù)字簽名標(biāo)準(zhǔn)DSS中. 1994年, 在考慮了公眾的建議后,