橢圓曲線密碼的許多形式略有不同，都依賴於解決橢圓曲線離散對數問題的公認難度，對應於有限域上的橢圓曲線群。
橢圓曲線最流行的有限域是素數的整數域(見模運算)GF(p)，或者特征為2的伽羅瓦域GF(2m)。後者在專用硬件實現中效率更高，而前者通常在通用處理器中效率更高。專利問題也很重要。其他壹些素數的伽羅瓦域的大小和能力也有人提出過，但被密碼學家認為有點問題。
給定壹條橢圓曲線E和壹個定義域GF(q)，我們考慮壹個具有(x，y)形式的有理點E(q)的阿貝爾群，其中x和y都在GF(q)中，定義在這條曲線上的群運算+在橢圓曲線中描述。然後我們定義第二個運算* | z×E(q)-& gt；E(q):如果p是E(q)上的壹個點，那麽我們定義2 * p = p+p，3 * p = 2 * p+p = p+p等等。註意，給定整數j和k，j*(k*P)=(j*k)*P=k*(j*P)。橢圓曲線的離散對數問題(ECDLP)是確定整數k使得k*P=Q給定點P和Q。
壹般認為，有限域乘法群上的離散對數問題(DLP)不等價於橢圓曲線上的離散對數問題(ECDLP)。ECDLP比DLP難多了。
在使用密碼時，曲線e(q)；並且與壹個特定基點G壹起被選擇和公布..私鑰k被選為隨機整數；值P=k*G作為公鑰發布(註意，假設的ECDLP難度意味著k很難從P中確定)。如果愛麗絲和鮑勃有私鑰kA和kB，公鑰PA和PB，那麽愛麗絲可以計算kA * PB =(kA * kB)* G；Bob可以算出同樣的值kb * pa = (kb * ka) * g。
這允許建立壹個“秘密”值，Alice和Bob可以很容易地計算該值，但是任何第三方都很難獲得該值。另外，Bob在處理過程中不會得到任何關於kA的新知識，所以Alice的私鑰仍然是私有的。
基於這個秘密值，用於加密Alice和Bob之間的消息的實際方法適應於之前的離散對數密碼系統，該系統最初在其他組中描述。這些系統包括:
迪菲-赫爾曼-ECDH
MQV — ECMQV
ElGamal離散對數密碼系統— ECElGamal
DSA-ECD sa
對於ECC系統來說，運行系統所必需的組運算比同樣大小的因式分解系統或模整數離散對數系統要慢。然而，ECC的支持者認為，ECDLP問題比DLP或因式分解問題困難得多，因此ECC可以用小得多的密鑰長度提供相同的安全性，在這方面確實比RSA快。目前公布的結果傾向於支持這壹結論，但壹些專家持懷疑態度。
在給定密鑰長度的情況下，ECC被廣泛認為是最強大的非對稱算法，因此它在帶寬要求非常嚴格的連接中非常有用。
美國國家標準技術局和ANSI X9已經設定了最小密鑰長度要求。RSA和DSA是1024比特，ECC是160比特，對應的對稱分組密碼的密鑰長度是80比特。NIST公布了保護五種不同對稱密鑰大小(80，112，128，192，256)的推薦橢圓曲線列表。壹般來說，二進制域的ECC需要兩倍於相應對稱密鑰大小的非對稱密鑰。
Certicom是ECC的主要商業支持者，擁有超過65，438+030項專利，並以2500萬美元的交易獲得了美國國家安全局(NSA)的技術許可。他們也對ECC算法發起了許多挑戰。目前已經解決的最復雜的密鑰是109位，由壹個研究小組在2003年初破解。破解密鑰的團隊使用了基於生日攻擊的大規模並行攻擊，在超過65，438+00，000臺奔騰級PC上連續運行超過540天。對於ECC推薦的最小密鑰長度163比特，估計目前的計算資源是109比特的108倍。
2005年2月16日，NSA宣布決定采用橢圓曲線加密策略作為美國政府標準的壹部分，以保護敏感但非機密的信息。NSA推薦了壹套叫做Suit B的算法，包括密鑰交換的Menezes-Qu-Vanstone橢圓曲線和Diffie-Hellman橢圓曲線，數字簽名的橢圓曲線數字簽名算法。AES和SHA也包括在這個組中。