橢圓曲線密碼體制是代替RSA公鑰密碼體制的非常有力的競爭者之一。從現有的研究結果看,RSA和ElGamal密碼體制的安全強度是亞指數的,橢圓曲線密碼體制的安全強度是指數的。

橢圓曲線密碼系統的安全性基於橢圓曲線離散對數問題的困難性,现在求解橢圓曲線離散對數問題主要有通用方法和特殊方法2類。

通用方法適合全部有限循環群上的離散對數問題,主要包括大步小步法、Pollard rho算法和Pohlig-Hellman算法等。通用方法沒有利用具體的橢圓曲線的特徵,都是完全指數時間的。

特殊方法主要含素域異常曲線攻擊、MOV約化攻擊和Weil下降攻擊等,這些攻擊方法利用了特殊曲線明顯的特徵,因而效率較高。但這些特殊曲線在構建橢圓曲線密碼系統時很易被檢測出來。比如FIPS 186-3就對選擇橢圓曲線的參數做了限制,並給出了一些檢測算法,防止攻擊者用較弱的參數攻擊。

對於設計完善的橢圓曲線密碼系統,现在最有效的攻擊算法是Pollard rho算法。該算法基於生日攻擊,由Pollard在1978年提出。2001年以後,Pollard rho算法在理論上逐漸成熟,攻擊效率主要依賴於硬件條件及在具體平台上的實現。

為了提高密碼學界對橢圓曲線密碼系統安全性的認識,加拿大的Certicom公司在1997年公佈了一系列橢由線密碼系統挑戰,這些挑戰分為三個級別:練習級、一級和二級,其中練習級挑戰的規模為79bit、89bit和97bit,一級挑戰的規模為109bit和131bit,二級挑戰的規模為163bit、191bit、239bit和359bit。每個規模的挑戰有三個,一個基於素數域上的橢圓曲線,另外兩個分別基於二進制擴域上的一般橢圓曲線和Koblitz曲線。練習級的挑戰在2000年之前就被全部解決,一級挑戰中109bit規模上的三個挑戰2004年之前被解決，131bit規模上的挑戰到2015年9月都還沒有解決。

现在已解決的ECC挑戰都是由Pollard rho算法完成的,由於該算法是一個完全指數時算法,因此對ECC的攻擊需要巨大的計算量。2002年,Monico在攻擊ECCp-109中利用了100多台計算機,耗時549天;2004年,Monico在攻擊EC2109中利用了2600台計算機,耗時17個月。现在ECC攻擊的最新進展為Bos等學者在2009年解決了SEC2密碼標準中的ECCp-112。