椭圆曲线密码学

对椭圆曲线来说最流行的有限域是以素数为模的整数域（参见模运算)${\displaystyle GF(p)}$，或是特征为2的伽罗瓦域 GF（2^m）。后者在专门的硬件实现上计算更为有效，而前者通常在通用处理器上更为有效。专利的问题也是相关的。一些其他素数的伽罗瓦域的大小和能力也已经提出了，但被密码专家认为有一点问题。

给定一条椭圆曲线E以及一个域${\displaystyle GF(q)}$，我们考虑具有${\displaystyle (x,y)}$形式有理数点${\displaystyle E(q)}$的阿贝尔群，其中x和y都在${\displaystyle GF(q)}$中并且定义在这条曲线上的群运算"+"（运算"+"在文章椭圆曲线中描述）。我们然后定义第二个运算"*" | Z×${\displaystyle E(q)->E(q)}$：如果P是${\displaystyle E(q)}$上的某个点，那么我们定义${\displaystyle 2*P=P+P,3*P=2*P+P=P+P+P}$等等。注意给定整数j和k，${\displaystyle j*(k*P)=(jk)*P=k*(j*P)}$。椭圆曲线离散对数问题（ECDLP）就是给定点P和Q，确定整数k使${\displaystyle k*P=Q}$。 -- 一般认为在一个有限域乘法群上的离散对数问题（DLP）和椭圆曲线上的离散对数问题（ECDLP）並不等价；ECDLP比DLP要困难的多。

在密码的使用上，曲线${\displaystyle E(q)}$和其中一个特定的基点G一起被选择和公布。一个私钥k被作为随机整数来选择；值${\displaystyle P=k*G}$被作为公钥来公布（注意假设的ECDLP困难性意味着k很难从P中确定）。如果Alice和Bob有私钥k_A和k_B，公钥是P_A和P_B，那么Alice能计算k_A*P_B=(k_A*k_B)*G；Bob能计算同样的值k_B*P_A=(k_B*k_A)*G。

这允许一个“秘密”值的建立，这样Alice和Bob能很容易地计算出，但任何的第三方却很难得到。另外，Bob在处理期间不会获得任何关于k_A的新知识，因此Alice的私钥仍然是私有的。