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

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

原根和階-定義

原根和階-方法？

原根和階-例題

原根和階-例題

原根和階-例題

原根和階-性質(zhì)

原根和階-性質(zhì)

原根和階-性質(zhì)

原根和階-例題

原根和階-例題

原根和階-性質(zhì)

【例5.1.6】已知整數(shù)5模17的階為ord17(5)=16.因?yàn)?-1≡5(mod17),則由【性質(zhì)5.1.1】,整數(shù)7模17的階為16.

原根和階-例題

012345678910111213141515861314210161291143157原根和階-舉例

012345157171311原根和階-性質(zhì)

原根和階-舉例

原根和階-性質(zhì)

原根和階-性質(zhì)

【例5.1.11】由ord17(5)＝16可知5是模17的原根,由原根5就可以求出17的所有原根.解:模17的所有原根為51,53,55,57,59,511,513,515.即51≡5(mod17),53≡6(mod17),55≡14(mod17),57≡10(mod17),59≡12(mod17),511≡11(mod17),513≡13(mod17),515≡6(mod17).

原根存在的充分必要條件

5.1.3素?cái)?shù)的原根

5.2離散對數(shù)

離散對數(shù)-定義

離散對數(shù)-例題【例5.2.1】已知5是模17的原根.求10對模17的離散對數(shù).解:先構(gòu)造以5為底的階函數(shù)表.再構(gòu)造離散對數(shù)表.可得,10對模17的離散對數(shù)為7.1234567891011121314151658613142101612911431571a1234567891011121314151616613121315210711945148離散對數(shù)-性質(zhì)

離散對數(shù)-舉例

離散對數(shù)-舉例

5.3離散對數(shù)在密碼學(xué)中的應(yīng)用離散對數(shù)問題在密碼學(xué)中的應(yīng)用,主要包括了ElGamal密碼算法、Diffie-Hellman密鑰協(xié)商算法、數(shù)字簽名標(biāo)準(zhǔn)(DSS)等.這里我們介紹ElGamal密碼算法,以及DSS參數(shù)選取時用到的本章的相關(guān)知識.5.3.1ELGamal密碼算法ELGamal密碼算法是一個非對稱加密算法,由ELGamal在1985提出.既可以用于加密,也可以用于簽名,其安全性依賴于離散對數(shù)問題.ELGamal數(shù)字簽名算法的一個變體就是數(shù)字簽名標(biāo)準(zhǔn)（DSS）.下面給出ELGamal算法的描述.

5.3.2數(shù)字簽名標(biāo)準(zhǔn)的參數(shù)選取1991年8月,NIST頒發(fā)了一個通告,提出將數(shù)字簽名算法DSA用于數(shù)字簽名標(biāo)準(zhǔn)DSS中.1994年,在考慮了公眾的建議后