第十一講 橢圓曲線

第十一講橢圓曲線第1頁，共47頁，2023年，2月20日，星期三1984年，HendrikLenstra提出了依靠橢圓曲線性質分解整數(shù)的精妙算法。這一發(fā)現(xiàn)激發(fā)了學者進一步研究橢圓曲線在密碼和計算數(shù)論的其它應用。第2頁，共47頁，2023年，2月20日，星期三

橢圓曲線密碼在1985年分別由NealKoblitz和VictorMiller提出。橢圓曲線密碼方案為公鑰機制，提供如同RSA一樣的功能。但是，它的安全性依賴不同的困難問題，也就是橢圓曲線離散對數(shù)問題(ECDLP)。第3頁，共47頁，2023年，2月20日，星期三

我們知道解決分解整數(shù)問題需要亞指數(shù)時間復雜度的算法，而目前已知計算ECDLP的最好方法都需要全指數(shù)時間復雜度。這意味著在橢圓曲線系統(tǒng)中我們只需要使用相對于RSA短得多的密鑰就可以達到與其相同的安全強度。例如，一般認為160比特的橢圓曲線密鑰提供的安全強度與1024比特RSA密鑰相當。使用短的密鑰的好處在于加解密速度快、節(jié)省能源、節(jié)省帶寬、存儲空間。第4頁，共47頁，2023年，2月20日，星期三本講提要Weierstrass方程實域上的橢圓曲線有限域上的橢圓曲線橢圓曲線密碼橢圓曲線在分解中的應用第5頁，共47頁，2023年，2月20日，星期三1Weierstrass方程第6頁，共47頁，2023年，2月20日，星期三第7頁，共47頁，2023年，2月20日，星期三2實域上的橢圓曲線

2.1簡化Weierstrass方程第8頁，共47頁，2023年，2月20日，星期三2.2實域上的橢圓曲線第9頁，共47頁，2023年，2月20日，星期三2.3加法法則第10頁，共47頁，2023年，2月20日，星期三弦和切線法則2.3加法法則(續(xù))第11頁，共47頁，2023年，2月20日，星期三弦和切線法則(續(xù))2.3加法法則(續(xù))第12頁，共47頁，2023年，2月20日，星期三2.3加法法則(續(xù))第13頁，共47頁，2023年，2月20日，星期三2.3加法法則(續(xù))第14頁，共47頁，2023年，2月20日，星期三代數(shù)公式2.3加法法則(續(xù))第15頁，共47頁，2023年，2月20日，星期三2.3加法法則(續(xù))第16頁，共47頁，2023年，2月20日，星期三3有限域上的橢圓曲線3.1模素數(shù)p的橢圓曲線，p≠2，3情形3.1.1加法法則第17頁，共47頁，2023年，2月20日，星期三3.1.2

例子第18頁，共47頁，2023年，2月20日，星期三3.1.2

例子(續(xù))第19頁，共47頁，2023年，2月20日，星期三3.2有限域GF(2n)上的橢圓曲線第20頁，共47頁，2023年，2月20日，星期三3.2.1簡化Weierstrass方程第21頁，共47頁，2023年，2月20日，星期三3.2.2加法法則第22頁，共47頁，2023年，2月20日，星期三3.2.2加法法則(續(xù))第23頁，共47頁，2023年，2月20日，星期三3.2.2加法法則(續(xù))第24頁，共47頁，2023年，2月20日，星期三3.2.2加法法則(續(xù))第25頁，共47頁，2023年，2月20日，星期三3.2.3例子第26頁，共47頁，2023年，2月20日，星期三3.3點的數(shù)量第27頁，共47頁，2023年，2月20日，星期三3.3點的數(shù)量(續(xù))第28頁，共47頁，2023年，2月20日，星期三3.4橢圓曲線上的離散對數(shù)第29頁，共47頁，2023年，2月20日，星期三3.4橢圓曲線上的離散對數(shù)(續(xù))第30頁，共47頁，2023年，2月20日，星期三4橢圓曲線密碼4.1明文表示第31頁，共47頁，2023年，2月20日，星期三4.1明文表示(續(xù))第32頁，共47頁，2023年，2月20日，星期三4.2橢圓曲線ElGamal密碼系統(tǒng)第33頁，共47頁，2023年，2月20日，星期三4.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))第34頁，共47頁，2023年，2月20日，星期三4.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))第35頁，共47頁，2023年，2月20日，星期三4.2橢圓曲線ElGamal密碼系統(tǒng)(續(xù))第36頁，共47頁，2023年，2月20日，星期三4.3橢圓曲線數(shù)字簽名算法(ECDSA)第37頁，共47頁，2023年，2月20日，星期三4.3橢圓曲線數(shù)字簽名算法(ECDSA)(續(xù))第38頁，共47頁，2023年，2月20日，星期三5橢圓曲線在分解中的應用

5.1橢圓曲線分解算法第39頁，共47頁，2023年，2月20日，星期三5.1橢圓曲線分解算法(續(xù))第40頁，共47頁，2023年，2月20日，星期三5.1橢圓曲線分解算法(續(xù))第41頁，共47頁，2023年，2月20日，星期三5.1橢圓曲線分解算法(續(xù))第42頁，共47頁，2023年，2月20日，星期三5.1橢圓曲線分解算法(續(xù))第43頁，共47頁，2023年，2月20日，星期三5.1橢圓曲線分解算法(續(xù))第44頁，共47頁，2023年，2月20