第十一講-橢圓曲線課件

1984年，HendrikLenstra提出了依靠橢圓曲線性質(zhì)分解整數(shù)的精妙算法。這一發(fā)現(xiàn)激發(fā)了學(xué)者進(jìn)一步研究橢圓曲線在密碼和計(jì)算數(shù)論的其它應(yīng)用。1984年，HendrikLenstra提出了依靠橢1橢圓曲線密碼在1985年分別由NealKoblitz和VictorMiller提出。橢圓曲線密碼方案為公鑰機(jī)制，提供如同RSA一樣的功能。但是，它的安全性依賴不同的困難問題，也就是橢圓曲線離散對數(shù)問題(ECDLP)。橢圓曲線密碼在1985年分別由NealKoblitz2我們知道解決分解整數(shù)問題需要亞指數(shù)時(shí)間復(fù)雜度的算法，而目前已知計(jì)算ECDLP的最好方法都需要全指數(shù)時(shí)間復(fù)雜度。這意味著在橢圓曲線系統(tǒng)中我們只需要使用相對于RSA短得多的密鑰就可以達(dá)到與其相同的安全強(qiáng)度。例如，一般認(rèn)為160比特的橢圓曲線密鑰提供的安全強(qiáng)度與1024比特RSA密鑰相當(dāng)。使用短的密鑰的好處在于加解密速度快、節(jié)省能源、節(jié)省帶寬、存儲空間。我們知道解決分解整數(shù)問題需要亞指數(shù)時(shí)間復(fù)雜度的算法，而3本講提要Weierstrass方程實(shí)域上的橢圓曲線有限域上的橢圓曲線橢圓曲線密碼橢圓曲線在分解中的應(yīng)用本講提要Weierstrass方程41Weierstrass方程1Weierstrass方程5第十一講-橢圓曲線課件62實(shí)域上的橢圓曲線

2.1簡化Weierstrass方程2實(shí)域上的橢圓曲線

2.1簡化Weierstrass方程72.2實(shí)域上的橢圓曲線2.2實(shí)域上的橢圓曲線82.3加法法則2.3加法法則9弦和切線法則2.3加法法則(續(xù))弦和切線法則2.3加法法則(續(xù))10弦和切線法則(續(xù))2.3加法法則(續(xù))弦和切線法則(續(xù))2.3加法法則(續(xù))112.3加法法則(續(xù))2.3加法法則(續(xù))122.3加法法則(續(xù))2.3加法法則(續(xù))13代數(shù)公式2.3加法法則(續(xù))代數(shù)公式2.3加法法則(續(xù))142.3加法法則(續(xù))2.3加法法則(續(xù))153有限域上的橢圓曲線3.1模素?cái)?shù)p的橢圓曲線，p≠2，3情形3.1.1加法法則3有限域上的橢圓曲線3.1模素?cái)?shù)p的橢圓曲線，p≠2，3163.1.2

例子3.1.2例子173.1.2

例子(續(xù))3.1.2例子(續(xù))183.2有限域GF(2n)上的橢圓曲線3.2有限域GF(2n)上的橢圓曲線193.2.1簡化Weierstrass方程3.2.1簡化Weierstrass方程203.2.2加法法則3.2.2加法法則213.2.2加法法則(續(xù))3.2.2加法法則(續(xù))223.2.2加法法則(續(xù))3.2.2加法法則(續(xù))233.2.2加法法則(續(xù))3.2.2加法法則(續(xù))243.2.3例子3.2.3例子253.3點(diǎn)的數(shù)量3.3點(diǎn)的數(shù)量263.3點(diǎn)的數(shù)量(續(xù))3.3點(diǎn)的數(shù)量(續(xù))273.4橢圓曲線上的離散對數(shù)3.4橢圓曲線上的離散對數(shù)283.4橢圓曲線上的離散對數(shù)(續(xù))3.4橢圓曲線上的離散對數(shù)(續(xù))294橢圓曲線密碼4.1明文表示4橢圓曲線密碼4.1明文表示304.1明文表示(續(xù))4.1明文表示(續(xù))314.2橢圓曲線ElGamal密碼系統(tǒng)4.2橢圓曲線ElGamal密碼系統(tǒng)324.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))4.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))334.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))4.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))344.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))4.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))354.3橢圓曲線數(shù)字簽名算法(ECDSA)4.3橢圓曲線數(shù)字簽名算法(ECDSA)364.3橢圓曲線數(shù)字簽名算法(ECDSA)(續(xù))4.3橢圓曲線數(shù)字簽名算法(ECDSA)(續(xù))375橢圓曲線在分解中的應(yīng)用

5.1橢圓曲線分解算法5橢圓曲線在分解中的應(yīng)用

5.1橢圓曲線分解算法385.1橢圓曲線分解算法(續(xù))5.1橢圓曲線分解算法(續(xù))395.1橢圓曲線分解算法(續(xù))5.1橢圓曲線分解算法(續(xù))405.1橢圓曲線分解算法(續(xù))5.1橢圓曲線分解算法(續(xù))415.1橢圓曲線分解算法(續(xù))5.1橢圓曲線分解算法(續(xù))425.1橢圓曲線分解算法(續(xù))5.1橢圓曲線分解算法(續(xù))435.2退化曲線5.2退化曲線445.2退化曲線(續(xù))5.2退化曲線(續(xù))455.2退化曲線(續(xù))5.2退化曲線(續(xù))461984年，HendrikLenstra提出了依靠橢圓曲線性質(zhì)分解整數(shù)的精妙算法。這一發(fā)現(xiàn)激發(fā)了學(xué)者進(jìn)一步研究橢圓曲線在密碼和計(jì)算數(shù)論的其它應(yīng)用。1984年，HendrikLenstra提出了依靠橢47橢圓曲線密碼在1985年分別由NealKoblitz和VictorMiller提出。橢圓曲線密碼方案為公鑰機(jī)制，提供如同RSA一樣的功能。但是，它的安全性依賴不同的困難問題，也就是橢圓曲線離散對數(shù)問題(ECDLP)。橢圓曲線密碼在1985年分別由NealKoblitz48我們知道解決分解整數(shù)問題需要亞指數(shù)時(shí)間復(fù)雜度的算法，而目前已知計(jì)算ECDLP的最好方法都需要全指數(shù)時(shí)間復(fù)雜度。這意味著在橢圓曲線系統(tǒng)中我們只需要使用相對于RSA短得多的密鑰就可以達(dá)到與其相同的安全強(qiáng)度。例如，一般認(rèn)為160比特的橢圓曲線密鑰提供的安全強(qiáng)度與1024比特RSA密鑰相當(dāng)。使用短的密鑰的好處在于加解密速度快、節(jié)省能源、節(jié)省帶寬、存儲空間。我們知道解決分解整數(shù)問題需要亞指數(shù)時(shí)間復(fù)雜度的算法，而49本講提要Weierstrass方程實(shí)域上的橢圓曲線有限域上的橢圓曲線橢圓曲線密碼橢圓曲線在分解中的應(yīng)用本講提要Weierstrass方程501Weierstrass方程1Weierstrass方程51第十一講-橢圓曲線課件522實(shí)域上的橢圓曲線

2.1簡化Weierstrass方程2實(shí)域上的橢圓曲線

2.1簡化Weierstrass方程532.2實(shí)域上的橢圓曲線2.2實(shí)域上的橢圓曲線542.3加法法則2.3加法法則55弦和切線法則2.3加法法則(續(xù))弦和切線法則2.3加法法則(續(xù))56弦和切線法則(續(xù))2.3加法法則(續(xù))弦和切線法則(續(xù))2.3加法法則(續(xù))572.3加法法則(續(xù))2.3加法法則(續(xù))582.3加法法則(續(xù))2.3加法法則(續(xù))59代數(shù)公式2.3加法法則(續(xù))代數(shù)公式2.3加法法則(續(xù))602.3加法法則(續(xù))2.3加法法則(續(xù))613有限域上的橢圓曲線3.1模素?cái)?shù)p的橢圓曲線，p≠2，3情形3.1.1加法法則3有限域上的橢圓曲線3.1模素?cái)?shù)p的橢圓曲線，p≠2，3623.1.2

例子3.1.2例子633.1.2

例子(續(xù))3.1.2例子(續(xù))643.2有限域GF(2n)上的橢圓曲線3.2有限域GF(2n)上的橢圓曲線653.2.1簡化Weierstrass方程3.2.1簡化Weierstrass方程663.2.2加法法則3.2.2加法法則673.2.2加法法則(續(xù))3.2.2加法法則(續(xù))683.2.2加法法則(續(xù))3.2.2加法法則(續(xù))693.2.2加法法則(續(xù))3.2.2加法法則(續(xù))703.2.3例子3.2.3例子713.3點(diǎn)的數(shù)量3.3點(diǎn)的數(shù)量723.3點(diǎn)的數(shù)量(續(xù))3.3點(diǎn)的數(shù)量(續(xù))733.4橢圓曲線上的離散對數(shù)3.4橢圓曲線上的離散對數(shù)743.4橢圓曲線上的離散對數(shù)(續(xù))3.4橢圓曲線上的離散對數(shù)(續(xù))754橢圓曲線密碼4.1明文表示4橢圓曲線密碼4.1明文表示764.1明文表示(續(xù))4.1明文表示(續(xù))774.2橢圓曲線ElGamal密碼系統(tǒng)4.2橢圓曲線ElGamal密碼系統(tǒng)784.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))4.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))794.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))4.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))804.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))4.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))814.3橢圓曲線數(shù)字簽名算法(ECDSA)4.3橢圓曲線數(shù)字簽名算法(ECDSA)824.3橢圓曲線數(shù)字簽名算法(ECDSA)(續(xù))4.3橢圓曲線數(shù)字簽名算法(ECDSA)(續(xù))835橢圓曲線在分解中的應(yīng)用

5.1橢圓曲線分解算法5橢圓曲線在分解中的應(yīng)用

5.1橢圓曲線分解算法845.1橢圓曲線分解算法(續(xù))5.1橢圓曲線分解算法(續(xù))855.1橢圓曲線分解算法(續(xù))5.