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

1、第第5章章 原根和原根和階階信息安全數(shù)學(xué)基礎(chǔ) 第5章 引子在密碼學(xué)中, 有很多基于離散對數(shù)問題的密碼算法和協(xié)議, 比如elgamal公鑰密碼算法, diffie-hellman密鑰協(xié)商算法, 美國的數(shù)字簽名算法dsa等等. 學(xué)習(xí)原根的知識有助于理解離散對數(shù)問題.進(jìn)一步地，理解離散對數(shù)問題也是理解橢圓曲線密碼學(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】, 整數(shù)7模17的階為16.

3、信息安全數(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章 信息安全數(shù)學(xué)基礎(chǔ) 第5章 【例5.1.1

4、1】 由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ù)的原根素?cái)?shù)的原根信息安全數(shù)學(xué)基礎(chǔ) 第5章 信

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

6、基礎(chǔ) 第5章 離散對數(shù)離散對數(shù)- -性質(zhì)性質(zhì)信息安全數(shù)學(xué)基礎(chǔ) 第5章 離散對數(shù)離散對數(shù)- -舉例舉例信息安全數(shù)學(xué)基礎(chǔ) 第5章 離散對數(shù)離散對數(shù)- -舉例舉例信息安全數(shù)學(xué)基礎(chǔ) 第5章 5.35.3離散對數(shù)在密碼學(xué)中的應(yīng)用離散對數(shù)在密碼學(xué)中的應(yīng)用離散對數(shù)問題在密碼學(xué)中的應(yīng)用, 主要包括了elgamal密碼算法、diffie-hellman密鑰協(xié)商算法、數(shù)字簽名標(biāo)準(zhǔn)(dss)等. 這里我們介紹elgamal密碼算法, 以及dss參數(shù)選取時(shí)用到的本章的相關(guān)知識.信息安全數(shù)學(xué)基礎(chǔ) 第5章 5.3.1 elgamal5.3.1 elgamal密碼算法密碼算法elgamal密碼算法是一個(gè)非對稱加密算法, 由elgamal在1985提出. 既可以用于加密, 也可以用于簽名, 其安全性依賴于離散對數(shù)問題. 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年, 在考慮了公眾的建議后, 該