CN1280726A - 优化椭圆曲线密码计算的变换方法 - Google Patents

Abstract

本发明提出了一种变换方法,用以取得优化的椭圆曲线密码系统的硬件和软件工具,包括椭圆曲线加密、解密以及签名功能。本方法适用于定义在任何域F上的任何椭圆曲线群G。特别是本发明的特点在于提高了椭圆曲线点乘运算的速度,这种运算由计算Q=eP组成,这里P为G的一个元素,e为一个整数。这种提高是通过将P=(x,y)变换到另一点P’=(x’,y’),以计算Q’=(u,v=e P’)来取得的。点P’并不一定是在椭圆曲线上,但通过完成对P’的计算并将结果Q’变换回G,就可能比利用直接方法计算Q更有效。本发明还包括了一种用于密码运算的优化计算方法,该计算方法包括了对于有限域算法中的任意表达式使用一种变换方法,使得可以用有效方式利用任何域F。本发明还包括了在任何有限域中优化任意的有限计算的一种方法。本发明还讲授了一个密码计算变换的集合,该集合使得人们可以使用其它的已知计算方法,而在本发明之前这些方法只能应用于某些有限的特例。

Description

优化椭圆曲线密码计算的变换方法

                发明的技术领域

本发明特别涉及椭圆曲线密码系统的软件和硬件工具，也一般地涉及在有限域内包括有限的任意域运算的要求进行计算的系统。

                发明背景

在现代信息社会中，对于全球计算机及网络安全的需求正在变得日益迫切。在各种不同的领域中，例如电子商务、企业安全、知识产权的数字式分布，以及国家安全等等，密码系统都是基本工具，被用于建立保障隐私、信用以及存取控制的系统。

“公共密钥”密码系统就为需要在对象(人或计算机系统)间进行安全的信息交换的系统提供了必不可少的能力，而在过去，这种彼此间的数据交换可能是完全无法进行的。大多数现代信息系统，包括互联网在内都属于这种系统。例如，一个客户可能从未与某一特定在线经销商有过任何接触，他或她却可以以一种安全的方式从这个经销商那里购物。公共密钥加密系统通过提供诸如加密、解密、数字化签名、签名校核等能力使这种购买得以进行。在公共密钥密码系统中，有兴趣接收来自他人的安全信息的机构公布他或她自己的“公共密钥”，其它人用这个公共密钥来为送给该机构的信息加密。这些信息只有用仅有该机构自己知道的“专用密钥”才能解密。该机构也可用这个专用密钥来为一段数据作数码化签名，其他人其后可以用公共密钥来核实签名，确认该段数据确实是由签名机构所签发。

公共密钥加密系统的安全性由取决于相应的、已知的公共密钥推导出专用密钥的困难程度。从数学上推导出专用密钥越复杂，计算机就需要越多的时间来使用“猜想”相应专用密钥的方法来“突破”一个公共密钥。现在最常使用的公共密钥加密系统是RSA公共密钥加密系统。RSA的公共及专业密钥间的关系由大复合整数分解的数学关系所决定。RSA的公共及专用密钥均是大整数，以二进制表示。一个密钥越长，则用一台计算机通过推导出其专用密钥的方法突破该密钥就越难、越费时。例如，现在在分解算法和分布式计算上取得的进展已使得突破400比特的RSA密钥成为可能。但是突破长度为1024比特或2048比特的RSA密钥，则被认为依靠现有的计算资源实际上是不可能做到的。为使安全性保持在可接受的水平，现代系统已在使用更长的RSA密钥。由于使用更长的密钥来实施公共密钥密码系统要求更多的计算资源，使用一种替代性的、可以用较短的密钥提供同样水平的安全性的公共密钥密码系统，这看来从经济性上是理想的。

在近十年里，椭圆曲线密码系统(“ECC”)已表现出对于一种有效的密码系统是一个可能的替代方案。ECC可用长度约为RSA密钥长度六分之一的密钥提供与RSA相同水平的安全保护，但迄今为止现有的ECC软件工具效能过低，无法作商业化运用。为进行商业化运用，ECC需以可比速度以及硬件和软件上的更低成本来达到与RSA相同的功能。高效能的ECC将实现许多预期的现代系统的实用化，而这用其它方法本来从经济上是不可行的。正因如此，学术界和产业界的许多研究工作都将重点放在了取得高效能的ECC。下面简述一下取得高效能ECC的最常用方法。

为完成公共密钥加密，ECC方法利用了被称为“椭圆曲线”的数学“群”的特殊性质。一条椭圆曲线对应一个数学“域”并“建立在”该域上。可选择任一有限域以构造一条椭圆曲线，但正是对该域所作的这一选择会明显影响到椭圆曲线的性质以及计算机工具的效率，这种计算机工具代表了定义在该条椭圆曲线内的“运算”。在所有ECC的应用中使用的、计算强度最高的运算中，其中之一被认为是“椭圆曲线点乘法”。在点乘法中需要计算eP，这里P是椭圆曲线上的一个“点”，e为一个正整数。这种运算是许多椭圆曲线密码系统操作的核心，这些操作包括加密、解密、随机数生成、密钥交换、数字化签名以及签名校核。

在过去十年中，密码学界内对于哪些范畴的域最适于ECC应用存有争议。电气和电子工程师协会(IEEE)选择了被称为GF(p)和GF(2k)的两大范畴的域作为椭圆曲线密码系统的国际标准。虽然现在大多数学术性的和商业性的研究都集中于实现建立在GF(p)和GF(2k)上的ECC应用，但对选择某个范畴的域后，这种选择究竟有何与密码系统有关的优缺点并不十分清楚。而且GF(p)和GF(2^K)均在其自身内包含有无数的特定元素域，每个特定元素域都有其自己的特性，而这些特性会影响到ECC工具的计算特性，并且在GF(p)或GF(2^K)内给定了一个特定元素域后，可在该域上构造起无数的椭圆“曲线”。曲线的选择同样会影响到所得到的ECC工具的计算特性。

为开发高效能的ECC工具，以前的尝试是基于在GF(p)或GF(2^K)中找到具体的特定元素域或者是定义在这样的元素域上的具体曲线，这些特定元素域应具有“特殊的”数学或计算特性。这些特殊的特性可用于优化ECC的计算。这一方法并不寻求在所有的数学域上得到高效的ECC，相反，它集中于仔细寻找特定的域，以便使用专门的数学或计算技术来进行高效的ECC计算。

Agnew等人提出了这种方法的一个范例，应用了被称为“正交基”的方法，在GF(2^K)中的特定域上取得快速ECC。在大多数学术界和工业界的研究都集中于在GF(2^K)的域上使用一种被称为“多项式基”的替代方法时，Agnew等人的方法在GF(2^K)内的六个特定域上使用正交基，从而可使一个特定的ECC工具实现商业化。这一方法的缺点是密钥长度被限定在这些特定域所允许的六个值上。

                  本发明的数学背景

本节列出了本文件中所使用的一些数学名词。本节还简单说明了在后面的本发明的方法论中很有用的一些关键概念。本节中的说明并不意味着数学上是准确严格的。

一个“集合”指任何一群对象，包括数学对象和物理对象。通常在打印中表示一个集合时，将由逗号分开的对象放在波形括号“{”和“}”内。例如用F代表所有小于7的非负整数，这一集合即可写成F={0，l，2，3，4，5，6}。属于一个集合的对象就是这个集合的一个“元”或“元素”。再举一例，F代表所有的4次多项式的集合，而p(x)表示特定的多项x⁴-x²-x+1，则由于p(x)是一个4次多项式，因此p(x)是F的一个元素。在数学上简化表示为p(x)∈F，在这里符号“∈”通常读为“属于”或者“是...的一个元素”。如果某个特定集合S中的每个元素同时又是另一个集合F的一个元素，则集合S即为集合F的一个“子集”。这一关系用简化符号表示为 $S\⋐F$ 。例如 $\left\{\mathrm{5,1,3}\right\}\⋐\left\{\mathrm{0,1,2,3,4,5,6}\right\}$ ，符号 $\⋐$ 读为“是…的一个子集”。每个集合都是其自身的子集，给出任何集合S，都有 $S\⋐S$ 。 映射

一个“映射”是指一个集合中的每个元素与另一个集合中一个特定元素的对应关系。例如，T可以被定义为这样的关系：将人类这个集合中的每个成员“映射”为代表该人年龄的整数。如果汤姆32岁，则写成T(汤姆)=32以表示在整数32和人类汤姆间建立的关系。32被称为汤姆“在映射T下”的“映象”。

再举一例，设p为一质数，n表示任何非负整数，r表示n除以p时结果的余数。数学上对这一关系的简化表达式为：r：n mod p，例如p=7，n=15，则r=15 mod 7=1，这里1是15除以7后的余数，因为15=2·7+1。在所有非负整数的集合N={O，1，2，3，…}与集合R={O，1，2，3，4，5，6，7，8}之间可以用下面的方式建立起映射T：设p=7，并设有任一非负整数n∈N，令T(n)=r=n模p，则有T(37)=r=37 mod 7=2。请注意，无论n取何值，T(n)都是小于7的整数。换言之，设有任何n∈N，则T(n)∈R。习惯上，称T将集合N映射“到”集合R上。这可简化表示为T：N→R，该表示式可读为“T是从集合N到集合R的映射”。N被称为是映射T的定义域，而R被称为是映射T的“值域”。

在映射T下，集合N的“映象”是R的特殊子集，它的每个元素都是N的至少一个元素的映象。换言之，如果F表示N在T下的映象，则对任一元素y∈F，存在至少一个元素x∈N，使得T(x)=y。因为任何正整数除以7的余数都是从0到6中的一个数，上例中的N在T下的映象为集合F={O，1，2，3，4，5，6}，因为 $F\⋐R$ (请记住R={0，1，2，3，4，5，6，7，8})，而且N中没有元素被映射到任何F之外的R的元素上，因此T也是从N到F的映射。换言之，即是T：N→F。由于F的每一个元素都是N的某个元素在T下的的映象，于是称T将N映射到F上。有时也用“变换”一词来指映射。集合运算

一个“有序对“是一个数学概念，指的是这种情况下的客体对：人们有必要掌握何为该对中的“第一个”元素，而何为该对中的“第二个”元素。例如，所有丈夫和妻子组成的对的集合就是一个有序对的集合，其成员可用符号(x，y)表示，这里，x是所有丈夫的集合中的一个元素，y是所有妻子的集合中的一个元素。令x和Y为任意集合，X和Y的“叉积”为这样的有序对的集合：它们的第一个元素来自于X而第二个元素来自于Y。按照数学语言，X和Y的叉积写为X×Y，定义为所有有序对的集合。这里x∈X，y∈Y。例如，令X={0，1}，Y={0，1，2}，则X×Y={(0，0)，(0，1)，(0，2)，(1，0)，(1，1)，(1，2)}。

设有任一集合S，则从S×S到S的映射可被称为定义在S内的“双元集合运算”，(双元一词强调了这个事实：这个映射的定义域中，每个元素均为一个有序对)。例如，令F={0，1，2，3，4，5，6}，然后建立映射T：F×F→F如下：对任一有序对(x，y)∈F×F，这里x∈F，y∈F，令在T下(x，y)的映象为表达式(x+y)mod7的计算结果的整数。换言之，令T(x，y)=(x+y)mod 7，则可相对简单地验证T的值域实际上就是集合F。例如，T(4，6)=(4+6)mod 7=10 mod 7=3，与x+y的值无关，作为表达式(x+y)mod7的结果的整数是除以7的余数，因此即为从0到6的整数，亦即F的一个元素。因此T是定义在F内的一个双集合运算。

为方便起见，在涉及一个给定的双元运算时，T((x，y))经常写成x·y，符号“·”被称为“双元运算算子”，用于表示双元运算T。例如，设T如上定义时，不写T((4，6))=3而写成4·6=(4+6)模7=3。其它符号也会被用作双元运算符号。常用的两个这样的其它符号是+和^_。集合S中组成有序对的两个元素通过一个双元运算而映射到集合S的另一个元素上，则这两个元素被称为在这个运算中的“运算对象”，而称这个运算“作用于”这些运算对象。例如在等式4·6=3中，运算对象为4和6。群

一个“群”为一个集合G，连同定义在该集合G上的、满足下面三个条件的一个双元运算“·”：

(ⅰ)设有x，y，z ∈G，则x·(y·z)=( x·y)·z，这被

    称为这个群的结合性。

(ⅱ)存在唯一的元素I∈G，使得对所有的x∈G，

    均有x·I=I·x=x，这个元素I被称为是G

    中的“单位”元素。

(ⅲ)对于任何x∈G，都存在元素x^-1∈G，使得x·x^-1

    =I。元素x^-1被称为x在·运算下的“逆”。

而·运算则被称为“群运算”。正是由于在集合G内定义的群运算的存在，才使得G成为一个群，实际上，G被称为在·运算下的群。一个阿贝耳群是这样的一个群G：给定任何x，y∈G，则有x·y=y·x。

举一个阿贝耳群的例子，设有集合F={1，2，3，4，5，6}，与·运算一起，对于所有的元素x，y∈F，均给定为或定义为x·y=(x·y)模7(式中第二个“·”为整数乘法的普通运算)。可知F即为在这一“乘法运算”下的一个群。为说明这一点，在下面列出表1，表1中包括对于元素x，y∈F的所有可能组合情况下，x·y=(x·y)模7的数值，这里x，y∈F。使用该表时，标号为x的行和标号为y的列相交叉处的单元格内即可查到x·y值。

表1在F={1，2，3，4，5，6}中由x·y=(x·y)模7所

                  设定的乘法运算

	1	2	3	4	5	6
							1	1	2	3	4	5	6
2	2	4	6	1	3	5
							3	3	6	2	5	1	4
4	4	1	5	2	6	3
							5	5	3	1	6	4	2
6	6	5	4	3	2	1

作为一个例子，请注意，如果x=5，y=6，则表格给出x·y=2。为验证其准确性，请注意x·y=5·6=(5·6)模7=30模7=2。

按照上面对于·和F的定义，F是否为一个群的工作等同于验证前述的条件(ⅰ)、(ⅱ)和(ⅲ)能否均得到满足。(ⅰ)条件(ⅰ)规定x·(y·z)=(x·y)·z。令x=3，y=5，z=2，则有3·(5·2)=3·((5·2) mod 7)=3·(10 mod 7)=3·3=(3·3) mod 7=9 mod 7=2；而(3·5)·2=((3·5)mod 7)·2=(15 mod 7)·2=1·2=(1·2) mod 7=2。因此(3·5)·2=3·(5·2)。(ⅱ)表1表明在群运算·下，单位元素是1。因为如表格所示，

对于所有的x∈F，均有x·1=1·x=1。(ⅲ)使用表1可得F的每一个元素x的逆x^-1的如下数值(这

里x·x^-1=1)：1^-1=1，2^-1=4，3^-1=5，4^-1=3，

5^-1=3，6^-1=1。(ⅳ)分析表1还可以得到如下关系：对于所有的x，y∈F，均有x·y

=y·x，因此F是在乘法运算下的阿贝耳群。

有时用符号+来表示F中的群运算。在这种情况下，在+下的任一元素x∈F的逆将用-x表示，而非x^-1。举另一阿贝耳群的例子，设有集合F={0，1，2，3，4，5，6}，其相应的运算+设定为或定义为对于所有的元素x，y∈F均有x+y=(x+y) mod 7

(第二个“+”表示普通的整数加法运算。可知F为在这个“加法运算”下的一个群。为表明这一点，列出表2。表2中包括对于元素x，y∈F的所有可能组合情况下，x+y=(x+y) mod 7的数值，这里x，y∈F。

表2在F={0，1，2，3，4，5，6}中，由x+y=(x+y)模7所设定的加法运算

	0	1	2	3	4	5	6
								0	0	1	2	3	4	5	6
1	1	2	3	4	5	6	0
								2	2	3	4	5	6	0	1
3	3	4	5	6	0	1	2
								4	4	5	6	0	1	2	3
5	5	6	0	1	2	3	4
								6	6	0	1	2	3	4	5

作为一个例子，请注意，如果x=5，y=6，则表中给出x+y=4。为验证其准确性，请注意x·y=5·6=(5·6)模7=11模7=4。

按照上面对于+和F所下的定义，验证F是否为一个群的工作，等同于验证前述的条件(ⅰ)、(ⅱ)和(ⅲ)能否均得到满足。(ⅰ)作为条件(ⅰ)成立的例子，请考虑(3+5)+2=((3+5) mod 7)+2=(8 mod 7)+2=1+2=(1+2) mod 7=3；而3+(5+2)=3+((5+2)mod 7)=3+(7 mod 7)=3+0=(3+0) mod 7=3 mod 7=3，因此(3+5)+2=3+(5+2)。(ⅱ)表2表明在群运算+下，F的单位元素是0，因为如表格所示，

对所有的x∈F均有x+0=0+x=0。(ⅲ)可用表2得到F的每个元素x的逆x-1的如下数值(这里x-(-x)

=0)：_0=0，_1=6，_2=5，_3=4，_4=3，_5=2以及_6

=1 。(ⅳ)分析表2还可以得到如下关系：对于所有的x，y∈F，均有x+y

=y+x，因此F是在加法运算下的阿贝耳群。域

一个域是一个集合F及与该集合结合在一起的两个双集合运算+和·，这两个运算定义在F内，并应满足下列条件：(ⅰ)F为在+运算下的一个阿贝耳群。+运算被称为域的“加法运算”。

在加法运算下，域的单位元素表示为0。对于任意元素x∈F，x

在域的加法运算下的逆表示为-x，这里-x被称为x的“加法

逆”。(ⅱ)如果将0从集合F中移走，则得到的集合就会是在·运算下

的一个阿贝耳群。·运算被称作是该域的“乘法运算”。在乘法运

算下，该域的单位元素表示为1，1是与0不同的F的一个元素。

对于任一元素x∈F，在域的乘法运算下，x的逆表示为x^-1，这

里x^-1被称为是x的“乘法逆”。(ⅲ)对于任何x∈F，均有x·0=0·x=0。(ⅳ)对于任何x，y，z∈F，均有x·(y+z)=(x·y)+(x·z)，

这被称作是域的“分配性”。

集合F={0，1，2，3，4，5，6}以及与该集合结合在一起的、定义为对所有x，y∈F均成立的+运算x+y=(x+y)模7，和·运算x·y=(x·y)模7就是一个域的例子。可知在加法和乘法运算下，F就形成了一个域。为表明这一点，有必要证明上述的四个条件均得到满足。在上一节里已表明条件(ⅰ)和(ⅱ)均得到满足。从下面表3中则可明显看到条件(ⅲ)满足。

表3在F={0，1，2，3，4，5，6}中的乘法运算

	0	1	2	3	4	5	6
								0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6
								2	0	2	4	6	1	3	5
3	0	3	6	2	5	1	4
								4	0	4	1	5	2	6	3
5	0	5	3	1	6	4	2
								6	0	6	5	4	3	2	1

作为条件(ⅳ)成立的一个实例，我们将表明3·(5+6)=(3·5)+(3·6)。实际上3·(5+6)=3·((5-6) mod 7))=(3·(11 mod7)) mod 7=3·4 mod 7=12 mod 7=5；而(3·5)+(3·6)=(((3·5)mod 7)-((3·6) mod7 )) mod 7=((15 mod 7)-(18 mod 7)) mod 7=(1+4) mod 7=5 mod 7=5。

如果一个域F的元素数目有限，则它即为一个“有限域”。上面所说的域F是被称为GF(p)的一有限域族中的一个特例，这里p可以是任一质数。对于一个给定的特定质数p，GF(p)定义为小于p的非负整数的集合{0，1，…p^-1}，以及由整数加法模p所给出的加法运算和由整数乘法模p所给出的乘法运算。在上例使用的域F即为域GF(7)。域计算

域的数学概念是更为人所熟悉的“有理”数系统的一个抽象。有理数是所有整数以及所有可表为分子、分母均为非零整数的分数的集合。全体有理数的集合实际上可表明是在普通分数加法和乘法运算下的一个域。因此算术上的普通数学方法也被应用于域的更抽象领域。设有特定域F，则数学域理论允许写下“有效的”算术表达式或方程，并对其求值。这里该有效的算术表达式或方程的常数和变量“来自该域”，亦即它们是域F的元素。

例如，考虑等式y=(2·x)+1，满足这一方程的有理数的所有有序对(x，y)的集合包括有这样一些元素：(0，1)，(2，5)，(4，9)和(3．45，7．9)等。但是由于这个方程中的常数2和1也是域GF(7)的元素，“表达式”(2·x)+1就是GF(7)中的一个有效表达式，亦即只要在表达式中，为x代入的值为GF(7)的一个元素，则保证这个表达式可以“求值”得出FG(7)的一个有效元素。因此，这个方程本身也是FG(7)中的一个有效方程。实际上，这个等式的所有“解”的集合，亦即满足GF(7)中这个方程的所有有序对的集合等于{(0，1)，(1，3，)，(2，5)，(3，0)，(4，2)，(5，4)，(6，6)}。

为便于处理更加复杂的表达式，在域运算中使用了一些数学简化写法。设有任一域F，任一元素y∈F，以及任意正整数k，则表达式x^k表示F的特殊元素，其结果为用F中的乘法运算，将x与其自身相乘k次。换言之xk=x+x…+x，这里在表达式中有k-1个·算符。依照惯例，x0被定义为等于1。

设有任一整数k及F中任一元素x，则表达式kx表示F的特殊元素，其结果为用F中的加法运算，将x与其自身相加k次。换言之，kx=x+x+…+x，这里在表达式中有k-1个+算符。

设c为F中的一个常数，x为定义在F上的一个变量，则表达式c·x通常写成cx。此外设有F的任两个元素x和y，则表达式x+(-y)通常写为x-y。

设有一个域F和F中任一元素x，计算x的加法逆-x或者乘法逆x-1的工作可能是计算强度很高的。有可能将这项计算x的逆的工作作为一个集合运算。定义在集合S内的“一元集合运算”T是从S到S的一个映射。一元这个词强调这个事实，与双集合运算不同，T的范畴由S的单次的、独立的元素组成。设有S的任一元素x，令T将x映射为x^-1。换言之，令T(x)=x^-1，则T就是一个一元集合运算。

设有任一特定域F和正整数k，则一个定义在F上的阶数为k的多项式p(x)即为具如下形式的表达式p(x)=a_k x^k+a_k-1x^k-1+…+a₁x+a₀。在这一定义中，x是F中的变量，意即在对表达式求值前，必须将表达式中的x用F的某个特定元素代入。用于代入x的F中的这个特定元素即为x要被“赋给”的值，a_i(0≤i≤k)则是大家知道的p(x)的多项式系数，为F中的常数，这就是说在x的值被选定之前，这些系数即已决定了，无论x取何值，这些多项式系数都保持不变。

当F=GF(2)时，所有定义在GF(2)上的、阶数为k的多项式的集合，即为GF(2^k)，大家知道，设有任一大于1的k，则可在GF(2^k)内定义特定的加法和乘法运算，使得GF(2^k)在这种运算下形成一个域。集合GF(2^k)是所有阶数为k的多项式的集合，其多项式系数为0或1。例如，p(x)=x⁵+x²+1是GF(25)的一个元素，它的多项式系数为a₅=1，a₄=0，a₃=0，a₂=1，a₁=0及a₀=1。优化域的计算

在信息安全和密码技术的领域之外，在商业和科学上还有许多的问题，这些问题或是基于或是利用了有限域的数学。处理这些问题的计算机应用程序常常需要进行涉及有限域运算的计算。这种计算的通常形式是为一个数学表达式f求值，该表达式涉及了常数、变量、系数和定义在有限域F内的运算。请注意，变量和常数必须是域F的元素，但是系数可以是任何整数。系数，例如在表达式x-5y中的5，不是域F的元素，而仅仅是一个简化的符号，用于表示重复性的相加，在本例中5y=2y+2y+y，而2y=y+y。由于关心的是计算效率，我们将假定，如果同样的量在表达式中出现一次以上，例如象(x2-x1)-1在下面的表达式中那样，则每个这样的量只被计算一次。同样，在不失一般性的情况下，表达式f可以、而且将被假定是采用了充分简化的形式。在这种形式中，表达式中所有的仅涉及常数的计算都已完成了，并且所得到的常数已代入表达式中。

作为这种表达式的一个例子，令F∈GF(p)。再令x₁，x₂，y₁，y₂为定义在F内的变量。令a为一个常数，它是F的元素。定义

f=((y₂-y₁)·(x₂-x₁)^-1)·((y₂-a)·(x₂-x₁)^-1)-x₁-5x₂

由于在表达式f中，仅有的变量和常数是x₁，x₂，y₁，y₂和a，表达式f包括了有限量的域元素。而且表达式f包括了四个一元加法逆运算以计算-x₁，-x₂，-y₁和-a，一个单次的一元乘法运算逆运算以计算(x2-x1)-1，三个双元乘法运算，三个双元加法运算以计算5×2，四个双元加法运算以计算括弧内表达式，二个双元加法运算以计算(…)-x₁-5x₂。因此表达式f还包括了有限的域运算。所以，当为表达式f求值时，也就是说当表达式f中指定计算被完成时，计算的结果就将是域F中的一个单元元素。

任何定义在有限域F内的给定表达式通常都由“子表达式”组成。表达式f中的任何部分，如果其自身即为F中的一个有效表达式，则它是f的一个子表达式。例如，如果x2和x1是F的元素，则表达式s=(x2-x1)-1是F中的一个有效表达式。因此，s=(x2-x1)-1是表达式f=((y2-y1)·(x2-x1)-1)·((y2-y1)·(x2-x1)-1)-x1-x2的一个子表达式。f的其它一些子表达式有s=-x1，s=-y1和s=(y2-y1)·(x2-x1)-1等。但是请注意，s=x2-x1)-1-x1不是f的一个子表达式，因为s不是F的一个有效表达式。每个表达式f都是其自身的子表达式。

假设在有限域内定义了一个表达式，则为表达式f求值的工作可能有很高的计算强度。因而在计算机软件和／或硬件中，可进行高效计算的技术就有显著的商业或科学价值。当用于这些计算的应用程序的确切性能已定，则会有不同的指标，用以确定究竟是什么构成了“高效”的计算。在某些应用程序中，可能希望优化计算以取得更高的计算速度。而在其它应用程序中，重要的可能是进行优化以尽可能少地使用硬件设备的硅区域。还可能有其它的应用程序会从允许并行计算的优化中获益。特别是在FG(p)和GF(2k)中使用Fermat方法进行求逆运算时，计算强度是非常高的。为避免这种高强度计算，Menezes及其他人已开发出了在“投影坐标”中列公式求解问题的方法。这种方法使计算可以重新列公式进行，不必进行任何求逆运算，通常付出的代价是增加了其它运算的数量。蒙哥马利算法

在1985年，P．L．蒙哥马利发表了一种算法，它可用于优化具有f=a·b·r^-1形式的表达式的计算工作，这里a，b和r是域F∈GF(p)的元素，并且·是F中的乘法运算。自1985年以来，在工业界和科学界中的有些工作集中于将蒙哥马利算法推广使用到比f=a·b·r^-1具有更普遍形式的表达式上。为便于讨论这些努力，本专利定义“蒙哥马利标准形式”一词。给定一个域F中的一个特定元素r，则一个在F中的表达式根据与r的如下关系被递推定义为属于蒙哥马利标准形式，(ⅰ)表达式f如果不含任何域乘法运算也不含r，则依r而言，该表

达式属于蒙哥马利标准形式。该条件也可说成：如果不存在形式

为s=s2·s1的子表达式s，其中s1和s2是S的子表达式。

例如表达式f=(x₁-x₁-a)和表达式f=x₁都依r而言属于蒙

哥马利标准形式。(ⅱ)一个表达式如果可以写成f=f₁·f₂·r^-1的形式，式中f₁，f₂

都是f的子表达式，而且它们自身相对于r而言属于蒙哥马利标

准形式，则表达式f属于蒙哥马利标准形式。请注意，确认是否

相对于r而言一个表达式属于蒙哥马利标准形式时，应将该表达

式隔离开进行考虑。例如表达式f=(x₁+x₁+x₁)·x₁·r^-1

相对于r而言属于蒙哥马利标准形式。但f=x₁·(x₂·x₂)·r^-1

相对于r而言，不属于蒙哥马利标准形式，因为虽然(x₂·x₂)·r^-1

相对于r而言属于蒙哥马利标准形式，单一因子r^-1不能同时既

作为子表达式(x₂·x₂)·r^-1的一部分又作为整体表达式的一部分，

因此相对r而言(x₂·x₂)不属于蒙哥马利标准形式。(ⅲ)一个表达式f如果可写成f=(s)^-1·r²的形式，式中s是f

的一个子表达式而且其自身相对r而言属于蒙哥马利标准形式，

则f依r而言属于蒙哥马利标准形式。例如，f=(x₂-x₁)-1·r²

相对r而言属于蒙哥马利标准形式。最后，(ⅳ)如果只要存在f的一个子表达式s，它可写成s=s₁·s₂，式

中s₁和s₂均为f的子表达式且相对r而言属于蒙哥马利标准形

式，则总存在一个唯一的f的子表达式s₃，使得s₃=s₁·s₂·r^-1，

则表达式f依r而言属于蒙哥马利标准形式。例如，表达式f

=(((x₁-x₁+x₁)·x₁·r^-1+a)·z·r^-1)·(((x₁-x₁+x₁)·x₁·r^-1

+a)·z·r^-1)·r^-1-x₁-x₁相对r而言属于蒙哥马利标准形

式。

给定一个域F∈GF(p)和一个元素r∈F，则蒙哥马利算法可有效地用于优化F中的任何属于蒙哥马利标准形式的表达式f的计算。对于任意表达式f，则通过将其从表达式f“变换”为属于蒙哥马利标准形式的其它表达式f′(读作“f撇”)可取得高的效率。在过去十五年中，在企业界和科学界的专用应用程序范围内，已遇到无数的表达式涉及到GF(p)中的有限域内的有限运算。在有些情况下，研究人员和工程师们已经将某些这样的表达式变换成属于蒙哥马利标准形式的其它表达式，从而令这些表达式的计算更快。但在本发明以前，尚无通用的已知方法，用于将任何任意的涉及GF(p)中有限的域运算的表达式变换为大家所知道的，在GF(p)中依某个r而言属于蒙哥马利标准形式的表达式。

涉及在GF(p)中的域的、在企业界和学术界应用程序中常碰到的一种特殊表达式是某种形式的f=x^k，这里k是某个正整数，x是F∈GF(p)的一个元素。计算f=x^k即为大家所知的x的取幂。大家知道，本文件下一节所述的特别“替代方法”可应用于表达式f=x^k，将其变换为另一表达式f′，而f′则依F中的某一特定元素r而言属于蒙哥马利标准形式。通常，将蒙哥马利算法应用于所得的表达式f′上，为x的取幂提供高效方法。

虽然在GF(p)里的快速取幂中蒙哥马利算法已使用了十多年，但是在本发明之前，还没有办法将其速度上的改进扩大到用于一般的有限域计算。

在1998年，C．K．Koc和T．Acar公布了一种算法，可用来优化具有形式为f=a·b·r^-1的表达式的计算工作，式中a，b和r均为域f∈GF(2^K)的元素，而·是F中的乘法运算。这种算法被称为是GF(2^k)中的蒙哥马利算法。在过去，GF(2^K)中的蒙哥马利算法已被用于加速在GF(2^k)中的取幂，其方式类似于加速GF(p)中的取幂的方法。但是在本发明之前还没有办法将这个算法扩大到用在一般的有限域计算上。替代方法

本节描述一种特别的替代方法，这种方法常被用于处理含有定义在域F内的元素和运算的表达式。这种方法包括将f中的某种特定模式的元素和／或运算量的所有实例全部用另一种特定模式替代。例如令x和y表示F中的任何元素，并令a，b，c和r为F中的特定元素。于是，如果在f=(a·b)+(c·b)中，所有的模式x·y出现的地方均用模式x·y·r来代替，则所得表达式f′由f′=(a·b·r)+(c·b·r)给定。为方便这种方法的讨论，令s为一个表达式，它代表要被替代的模式。表达式s被称为“源”表达式。令t为一个表达式，它代表用以替代s的模式。表达式t被称为“目标”表达式。本节的其余部分就描述如何将这种替代方法应用于源表达式的三种简单类型上。类型1    源表达式s不含运算符

在这种情况下，源表达式由s=x给出，这里x表示在表达式f内的任一单一变量。替代方法为简单地在所有由源表达式s表示的变量出现的地方，用由目标表达式t给定的模式替代。类型2    源表达式包含单一的一元运算符

在这种情况下，源表达式由s=-x或s=x^-1给出，这里x表示在表达式f中的任一子表达式。在这里替代方法需要建立f的子表达式中，“对应”于目标表达式s的所有子表达式的集合S。换言之，集合S由具有形式为s=-x或s=x^-1的、表达式f的所有子表达式s的集合所给出，这里x自身也是f的一个子表达式。请注意，在集合S中给出任两个子表达式，则可能其中一个是另一个的子表达式。使用替代方法时，集合S的每个元素都应用目标表达式t所给出的相应模式来替代，除非在将替代施加到集合S的任一元素s之前，已先对S中的其它元素进行了替代，而s是该元素的子表达式。类型3   源表达式包含单一双元运算符

在这种情况下，源表达式由s=x+y或s=x·y给出，这里x和y代表表达式f内的任意子表达式。在这里替代方法需要建立f的子表达式中，“对应”于目标表达式s的所有子表达式的集合S。换言之，集合S由具有形式为s=x+y或s=x·y的、表达式f的所有子表达式的集合所给出，这里x和y自身也是f的子表达式。请注意，在集合S中给出任两个子表达式，则可能其中一个是另一个的子表达式。使用替代方法时集合S的每个元素都应用目标表达式t所给出的相应模式来替代，除非在将替代施加到集合S的任一元素s之前已先对S中的其它元素进行了替代，而s是该元素的子表达式。

过去在商业和工业上已使用过一种与此类似的替代方法，分两步将具有形式f=x^k的简单表达式的实例变换为属于蒙哥马利标准形式的另一表达式f′。为了用例子说明，以k=4时的情况说明这一方法，这意味着表达式f由f=x 4=x·x·x·x=((x·x)·x)·x所给出。(ⅰ)令源表达式s由s=x·y所给出，令目标表达式t由t=x·y·r^-1

所给出，式中r为域F中的一个常数。将替代方法用于表达式f

=((x·x)·x)·x，就产生了表达式f=((x·x·r^-1)·x·r

^-1)·x·r^-1。请注意，表达式f′属于蒙哥马利标准形式，这是

因为f′在括号内的每一个子表达式都对于r而言属于蒙哥马利

标准形式。正由于此，下一步就可应用蒙哥马利算法高效计算f

′。(ⅱ)令源表达式s由s=x所给出，式中x表示在f中的一个变量或常数。令目标表达式由t=x·r所给出。将替代方法用于表达式f₁=((x·x·r^-1)·x·r^-1)·x·r^-1，用x·r替代式中所有的x，就产生了表达式f′=(((x·r)·(x·r)·r^-1)·(x·r)·r^-1)·(x·r)·r^-1

这种替代方法使f=x^k得以高效计算，因为可表明表达式f相当于f=f′·r^-1。在k=4情况下说明这点，请注意：

f′=(((x·r)·(x·r)·r^-1)·(x·r)·r^-1)·(x·r)·r^-1

=((x·r·x·r^-1)·x·r·r^-1)·x·r·r^-1

=((r·x·x·r·r^-1)·x·r·r^-1)·x·r·r^-1

=((r·x·x·1)·x·1)·x·1=((r·x·x)·x=r·(((x·x)·x)=r·x⁴

因此，f′·r-1=r·x⁴·r-1=x⁴·r·r^-1=x⁴·1=f。因为f′相对r而言属于蒙哥马利标准形式，所以与直接计算f相比，计算f′·r^-1通常效率更高，而f′·r^-1自身也属蒙哥马利标准形式。椭圆曲线群

一条椭圆曲线G是根据有赖于F的确切性质的一组特定规则，在特定域F上建立的一个数学群。通常，G是FxF的一个子集，并且在G中的·运算是根据域运算·和F的元素上的·来定义的，F的这些元素组成了G的有序对元素。研究得最多的两组椭圆曲线是建立在属于GF(p)或者GF(2^k)的域上的椭圆曲线。在GF(p)上的椭圆曲线

在GF(p)上的椭圆曲线是由特定的参数a和b(二者均为GF(p)的元素)来定义的。它是所有为方程式y²=x³+ax+b解的有序对的集合，式中x，y为GF(p)的元素，集合还包括一个附加点0，通常称此点为无穷远点。假定p是一个大于3的质数，在GF(p)中选择a，b使得在GF(p)中4a3-27b 2≠0。已确认，根据下面的点加法定则，这条椭圆曲线上的点和0形成了一个阿贝耳群：

公式A1．0+0=02．(x，y)+0=(x，y)3．(x，y)+(x，-y)=04．两个相异点的加法：(x₁，y₁)-(x₂，y₂)=(x₃，y₃)

L=(y₂-y₁)-(x₂-x₁)^-1

x3=(L·L)-x₁-x₂

y3=L·(x₁-x₃)-y₁5．点的加倍：(x₁，y₁)+(x₁，y₁)=(x₃，y₃)L=(3x₁·x₁+a)·(2y₁)^-1x3=(L·L)-(2x1)y3=L·(x₁-x₃)-y₁

式中运算+、-、·和逆运算(^-1)都在域GF(p)中进行。以上定则就定义了一个方法，根据这个方法，椭圆曲线上的两点相加就得到了第三个点，这些公式将在以后称为公式A。实例

将说明在域GF(23)上的椭圆曲线方程y²=x³=+x+1。可知在这条曲线上包括特殊点0在内共有28点。

点0

(0，1)和(0，22)

(1，7)和(1，16)

(3，10)和(3，13)

(4，0)

(5，4)和(5，19)

(6，4)和(6，19)

(7，11)和(7，12)

(9，7)和(9，16)

(11，3)和(11，20)

(12，4)和(12，19)

(13，7)和(13，16)

(17，3)和(17，20)

(18，3)和(18，20)

(19，5)和(19，18)

例如，(1，7)在这条椭圆曲线上，因为它在域GF(23)(亦即模数为23)中，满足方程y²=x³+x+1，因为7²=1³+1+1 mod 23；49=3 mod 23；以及3=3 mod 23

用算术模23或者GF(23)的域运算来计算(3，10)和(9，7)的点相加：

L=(7-10)·(9-3)^-1=(-3)·6^-1=(-3)·4=-12=11

x₃=(11·11)-3-9=121-12=109=17

y₃=(11·(3-17))-10=-164=20

因此，(3，10)和(9，7)相加等于(17，20)。本例说明根据上面定则，曲线上的两个点相加后，得到曲线上的第三个点。在GF(2^k)上的椭圆曲线

在域GF(2^k)上的一条非超奇异椭圆曲线是由GF(2^k)中的参数a和b所定义的，b≠0，这条曲线是方程式y²+xy=x³+ax²+b的解(x，y)和附加点0组成的集合。根据加法定则，点的这一集合形成一个群：公式B1．0+0=02．(x，y)+0=(x，y)3．(x，y)+(x，x+y)=04．两个相异点的加法：(x₁，y₁)+(x₂，y₂)=(x₃，y₃)L=(y₁-y₂)·(x₁+x₂)^-1x₃=(L·L)-L+x₁-x₂+ay₃=(L·(x₁+x₃))+x₃-y₁5．点的加倍：(x₁，y₁)+(x₁，y₁)=(x₃，y₃)x₃=x₁·x₁+b·(x₁ ^-1)·(x₁ ^-1)y₃=x₁·x1+(x₃+y₁·x₁ ^-1)·x₃+x₃点乘

一个椭圆曲线密码操作，无论它是加密、解密、签名或是密钥通过操作，都涉及给定e和P的计算，这里P是曲线上的一个点，e是一个正整数。这一运算的求逆，亦即在给定P和eP时，对e的计算，大家知道是非常困难的。这被称为椭圆曲线离散对数问题。目前对这一问题尚无已知的高效算法。

    由于在椭圆曲线群G中的加法运算是用一系列的基础域中的域运

算来定义的，给定G中的两点P和Q，计算P+Q或P+P就需要对域

内的一系列运算进行计算。特别是如果F∈GF(2^k)，上面的第四组公

式表明对P+Q的计算需要进行一次域求逆，三次域乘和九次域加。

另一方面，如第五组公式所示，对P+P的计算需要进行一次域求逆，

三次域乘和五次域加。

    如果域的长度大约为500比特，计算eP所必须的椭圆曲线运算

(加法和乘法)的数量可表明大约为750。某个椭圆曲线运算包括有

若干次(约15-20)有限域运算。如果k(为F∈GF(2k)的元素)的

值也很高(＞100)，则这项计算就要花费可观的时间，特别是在软件

中。因此在密码技术中迫切需要椭圆曲线点乘的快速硬件和软件工

具。

    在GF(23)中的下面例子说明了一些可用于优化eP计算的方法。

令e=18，P=(3，10)，则对eP=18(3，10)可使用公式A中定义的群加法，

将(3，10)连续地自身相加18次：P+P+…+P(有18个P)，这需要

进行17次椭圆曲线点加运算。

    但有一种更快的算法称为“取幂法”，这种方法的一个例子就是

下面所示的“二元法”，它使18P可用以下步骤计算：

    第一步：(P)+(P)=2P

    第二步：(2P)+(2P)=4P

    第三步：(4P)+(4P)=8P

    第四步：(8P)+(8P)=16P

    第五步：(16P)+(2P)=18P

    这样，只用了5次点加或是群运算。中间结果及最后结果均为曲

线上的点，如下所示：

第一步：(P)+(P)=2P      ：      (3，10)+(3，10)=(7，12)

第二步：(2P)+(2P)=4P      ：    (7，12)+(7，12)=(17，3)

第三步：(4P)+(4P)=8P      ：    (17，3)+(17，3)=(13，16)

第四步：(8P)+(8P)=16P     ：    (13，16)+(13，16)=(5，19)

第五步：(16P)+(2P)=18P    ：    (5，19)+(7，12)=(6，19)

这样18(3，10)就是(6，19)。椭圆曲线离散对数问题于是就变成：已知(3，10)和(6，19)，以及(6，19)是(3，10)的一个整数倍，问该整数是多少?在本例中所用的整数等于18。

经e以二元表示法给出为e_k-1e_k-2…e₂e₁e₀，就可以用二元法或者任何其它M元法来完成eP的计算。例如，为计算Q=eP，二元法的处理过程如下：

Q：=0

令i=k-1下降至0

Q：=Q+Q

如果e₁=1，则Q=Q+P

返回Q

这样Q的计算是由一系列的椭圆曲线点加倍(Q：=Q+Q)和点加(Q：=Q+P)来完成的。

                        本发明摘要

本发明通过一种变换方法优化了椭圆曲线密码技术中的计算，这种变换方法允许以一种安全、高效的方式使用定义在任何域F上的任何椭圆曲线。本发明包括了一种方法和装置，用以得出椭圆曲线点乘积Q=eP。本发明利用了一个任意整数e和定义在域F上的一个椭圆曲线群G上的一点P，这里群G为域F叉积的一个子集。本发明建立了一个集合G′，一个从G到集合G′的映射T，一个从G′到G的映射T^-1，以及在G′上定义的一个运算^_，这样使得(a)给定点P，T^-1(T(P))=P，(b)P+P=T-1(P′^_P′)，式中P′=T(P)。求一个椭圆曲线点乘积Q时，用映射T将点P变换到P′，完成对P′的运算^_，从而得到Q′=eP′，再用映射T^-1将点Q′变换为乘积Q。乘积Q用于椭圆曲线密码操作中。

本发明还包括了一种优化涉及有限域算法中任意表达式的密码操作计算的方法，它通过一种变换方法使得任意域F都可用高效的方式使用。本发明包括了一种将任何有限域内的任意有限计算变换为标准形式的方法，在这种标准形式里可使用其它的过去已知的算法，从而提高了计算速度和效率。本发明讲授了密码计算变换的一个集合，这种变换使得在本发明之前仅能运用于某些特例的其它已知方法得以使用。

本发明的详细说明

通过集中处理在所有ECC工具中计算强度最高的运算之一，被称为“椭圆曲线点乘积”的运算，本发明提出了一种优化在任何域内任何曲线上的ECC计算的方法。点乘要求计算eP，这里P是椭圆曲线内的一个点，e是一个正整数。这一运算是许多椭圆曲线密码操作，包括加密、解密、随机数生成、密钥交换、数字化签名、签名核实等的核心。通过提出一种优化椭圆曲线点乘运算工具的方法，本发明取得了高效的ECC。本发明可用于将ECC使用于任何域的任何曲线上，包括GF(P)和GF(2k)内的所有特殊元素域。

本发明还进一步提出了一种方法，用于优化涉及在任何有限域中的、有限的任意域运算的计算。在无数系统，包括椭圆曲线密码系统的计算机应用中，这些计算都起着关键作用。

本发明提出了一种“变换方法”，它可用于优化椭圆曲线密码系统在硬件和软件里的工具。

由于使用了椭圆曲线G的元素上的可逆变换，本发明不会以任何方式改变用于椭圆曲线密码术的数学算法的基本安全特性。全部ECC算法的安全性决定于椭圆曲线方程的选择、数码表达方式的选择、算术算法以及其它工具方面的选择。只要根据可靠标准确定了这些选择，这些工具的安全性不会因使用本发明而受影响。

本发明可用于任一个以及所有可能的ECC应用，从用于诸如电影和歌曲等数字化产品的安全分布的软件，到诸如手持电话和智能卡这样的消费电子产品中所嵌人的硬件芯片。本发明节省成本的潜力能够极大地增强现有的商业化应用并使得过去不现实的商业机会现在变得在经济上可行了。A部分

设有 $G\⋐F\×F,$ 一条定义在域F上的椭圆曲线。本发明提出了一种改进了的方法，用于优化eP的计算，这里e是一个整数，P为G的一个元素。

本发明包括：(1)建立了一个集合G＇，以及在软件和／或硬件中表示G＇的元素的方法。(2)建立并使用了一种算法，用于在软件和／或硬件中的从G到G＇的第一次映射。(3)建立并使用了一种算法，用于在软件和／或硬件中的从G＇到G的第二次映射T^-1，其作用与T相反，并且(4)建立并使用了一种算法，在软件和／或硬件中用于定义在G＇内的集合运算^_。对于每一发明应满足以下三个条件：

(ⅰ)设有任一P∈G，则T^-1(T(P))=P：

(ⅱ)设有G中任两个点P和S，则P+S=T＇(P＇^_S＇)，式中P＇=T(P)，S＇=T(S)；

(ⅲ)选择G＇、T、^_和，T^-1及相应的算法，使得给定P₁，P₂…P_N∈G，这里N是一个整数，则T^-1(T(P₁)^_(T(P₂)^_…(T(P_N))的计算总的说，要更优化于P₁-P₂-…-P_N

换言之，本发明计算Q=eP时，首先使用用于第一次映射T的算法，将给定点P变换到变换后的点P′；然后在“变换后”范畴中，以椭圆曲线加法运算的从计算上更优化了的形式(^_)对于倍数和Q′=eP′进行计算，最后用用于第二次变换T-1的算法将Q′变换回Q。请注意，上述条件(ⅰ)和(ⅱ)得到满足即保证本方法可用于属于G的任何点P。

在特定情况下，当仔细选择了G′、T、T^-1和^_时，就可能优化点乘运算的计算。映射G中元素的附加成本可能会、也可能不会超过由于在交换后的范畴中进行更优化计算所得到的改善，这要依所需完成的点加法的数量而定。B部分

本发明进一步提出了一种特别方法，用于建立可以在任何椭圆曲线群G上运用的G′、T和T^-1。

因为G是F×F的一个子集，G中的点可以写为有序对(x，y)，这里x和y是域F的元素。本发明规定，首先选择F的一个特定元素r，这个元素r可以选为域F的任一元素。令t为从G到F×F的一个映射，它可将G中任一点P=(x，y)映射为G′中某点P′=(x′，y′)。本发明规定t(P)=t((x，y))=(x·r，y·r)=P′。因为x，y和r都是F的元素，所以x·r和y·r也是如此。本发明规定G′是G在t下的映象。换言之，G′是F×F的所有被t从G中的点映射来的元素的集合。本发明进一步规定T为从G到G′的变换，它使得在G中给定任何点P，则T(P)=t(P)=P′。虽然P′=(x，y)必定是F×F的一个元素，但它不一定是椭圆曲线群G中的一点。可计算x=x·r和y=y·r来得到P′。

令Q′为G′的任一元素，因G′∈F×F，我们可以写成Q′=(u′，v′)，式中u′和v′是F的元素。由于G′是G在t下的映象，于是一定存在F的两个元素u和v，使得(u，v)∈G并且u′=u·r，v′=v·r。因为u、v和r都是域F的元素，于是u=u′·r^-1，v=v′·r^-1，式中r^-1是r在F的乘法运算下的倒数。因此可以通过令T^-1映射G′的任一元素Q′=(u′，v′)到(u′·r^-1，u′·r^-1)来建立一个逆映射T^-1：G′→G。

用正规用语，本发明更详细的具体方法包括步骤：(1)建立F×F的子集G，它是G在映射t：G→F×F下的映象。通过首先选择F的任一元素r，然后令t((x，y))=(x·r，y·r)来建立此处的t，式中的·为F中的乘法运算；(2)令T(P)=t(P)以建立第一次映射T：G→G′，这里P是G中的任一点(3)令T^-1((u′，v′))=(u′·r^-1，v′·r^-1)以建立第二次映射T^-1：

G→G′，这里(u′，v′)是G′的任一元素。

给定了对G′、T和T^-1的如上选择，则通过认真定义G′中的^_运算和仔细选择r就可能优化eP的计算。例如r的某些特定值就可以构造更快的软件工具，而其它值则可能提供更大的计算平行度。C部分

本发明的另一详细的具体方法是将A部分和B部分中的方法应用于椭圆曲线，而这些椭圆曲线定义在属于GF(P)的特定域上。在这一具体方法中，建立了一个新的变换运算^_，以使A部分中的条件(ⅰ)、(ⅱ)和(ⅲ)得到满足。

本发明包括了一种在F为GF(P)中的单一元素域时优化eP计算的方法。在这一具体方法中，G是在F∈GF(P)上的一个椭圆曲线群，并且根据本发明在上面B部分描述的方法，通过选择F的一个任意元素r来构造G′、T和T^-1。本发明在G′中构造“变换后的”运算^_如下。设有G′的任两个元素(x₁′，y₁′)和(x₂′，y₂′)，则本发明定义(x₁′，y₁′)^_(x₂′，y₂′)由(x₃′，y₃′)给出，这里，公式A′

z′=(x2′-x1′)^-1·r²

L′=(y2′-y1′)·z′·r^-1

x₃′=L′·L′·r^-1)-x₁′-x₂′

y₃ ′=L′·(x₁′-x₃′)·r^-1-y₁′

将上面^_的定义用于G中的“加法”运算，本发明即得到了下面的一组域公式，用于将G′中的任一“点”(x₁′，y₁′)加到其自身上的运算：

(x₁′，y₁′)^_(x₁′，y₁′)=(x₃′，y₃′)，式中

z′=(y₁＇+y₁′)^-1·r²

L′=((x₁＇+x₁′-x₁′)·x₁′·r^-1+a′)·z′·r^-1

x₃＇=L′·L′·r^-1)-x₁′·x₁′

y₃′=L′·(x₁′-x₃′)·r^-1-y₁′

现在证明本发明是如何确保G′、T、T^-1和^_均满足A部分中提出的条件(ⅰ)、(ⅱ)和(ⅲ)的。(ⅰ)令P为椭圆曲线群G中的任一点，则存在F的某些元素x和y，使得P=(x，y)。于是T^-1(T(P))=T^-1(T(x，y)))=T^-1((x·r，y·r))=(x·r·r^-1，y·r·r^-1)=(x，y)=P。因此A节中条件(ⅰ)得到满足。(ⅱ)给定G中的任意两点P和S，则我们需要表明P+S=T^-1(P′^_S′)，式中P′=T(P)，S′=T(S)。令P=(x₁，y₁)，P′=(x₁′，y₁′)，S=(x₂，y₂)，S′=(x₂′，y₂′)，Q=P-S=(x₃，y₃)和Q′=P′+S′=(x₃′，y₃′)，然后运用公式A给出的关于在椭圆曲线群中的点加法运算的规则，可由x₃=L·L-x₁-x₂和y₃=L·(x₁-x₃)-y₁得到Q的坐标。式中L=(y₂-y₁)·z，z=(x₂-x₁)^-1，另一方面上面的公式A′则给出了Q′的坐标，于是，可表明Q′的坐标为：

z′=(x₂′-x₁′)^-1·r²

   =(x₂·r-x₁·r)^-1·r²

   =(x₂-x₁)^-1·r

   =z·r

L′=(y₂′-y₁′)·z′·r^-1

   =(y₂·r-y₁·r)·(z·r·)·r^-1

   =(y₂-y₁)·z·r

   =L·r

x₃′=L′·L′·r^-1-x₁′-x₂′

    =(L·r)·(L·r)·r^-1-x₁·r-x₂·r

    =(L·L-x₁-x₂)·r

    =x₃·r

y₃′=L′·(x₁′-x₃′)·r^-1-y1′

    =(L·r)·(x₂·r-x₃·r)·r^-1-y₁·r

    =(L·(x₁-x₃)-y₁)·r

    =y₃·r

因此，(x₃′，y₃′)=(x₃·r，y₃·r)，这意味着P′^_S′=T(P-S)，如所要求的那样。所以，A部分中的条件(ⅱ)得到满足。(ⅲ)本发明为G′、T、^_、T^-1和它们相应算法的选择构造了一种方法。构造这种方法的方式使得设有P₁，P₂…P_N∈G，这里N是一个整数，则在一般情况下，对T^-1(T(P₁))^_T(P₂)^_…^_T(P_N)的计算要优于对P₁+P₂+…+P_N的计算。为证明这点，请注意T(P₁)^_T(P₂)^_…^_T(P_N)的计算中包括了对公式A′中的表达式的重复使用。但是还请注意，这些表达式相对r而言均属于蒙哥马利标准形式。正因如此，可以很容易地将GF(p)中的蒙哥马利算法应用于T(P₁)^_T(P₂)^_…^_T(P_N)的计算，以生成优化的硬件和／或软件工具。因此，在A部分中的条件(ⅱ)得到满足。D部分

本发明的另一具体方法是将A部分和B部分的方法应用于椭圆曲线，而这些椭圆曲线定义在属于GF(2^k)的特定域上。在这一具体方法中，构造了一个新的、经过变换的运算^_，以使A部分中的条件(ⅰ)、(ⅱ)和(ⅲ)得以满足。

本发明进一步地包括了一种方法，用于优化在F为GF(2^k)的一个单一元素域时对eP的计算。在这一具体方法中，G是在F∈GF(2^k)上的一个椭圆曲线群，G′、T、T^-1是根据在上面B部分所述的本发明的方法，通过选择F的一个任意元素r来构造的。

本发明在G′中构造了一个“经过变换的”运算^_，如后面所示。设有G′的任两个元素，例如(x₁′，y₁′)和(x₂′，y₂′)，于是本发明定义(x₁′，y₁′)_(x₂′，y₂′)由(x₃′，y₃′)给出，公式B′

z′ =(x₁′·x₂′)^-1·r²

L′ =(y₁′·y₂′)·z′·r^-1

x₃′=(L′·L′·r^-1)+L′+x₁′+x₂′+a′

y₃′=(L′·(x₁′+x₃′)·r^-1+x₃′+y₁′

将上面^_的定义应用于G′中的点的加法运算，本发明即得到了下面的一组域运算公式，用于“加倍一个点”的运算，亦即将G′中的一点(x1′，y1′)与其自身相加：

(x₁′，y₁′)^_(x₁′，y₁′)=(x₃′，y₃′)，式中

z′=(x₁′)^-1·r2

x₃′=x₁′·x₁′·r^-1+(z′·z′·r^-1)·b′·r^-1

y₃′=x₁′·x₁′·r^-1+(x₁′+y₁′·z′·r_-1)·x₃′·r^-1-x₃′现在说明本发明如何确保G′、T、T^-1和^_一起，满足A部分中提出的条件(ⅰ)、(ⅱ)和(ⅲ)。(ⅰ)令P为椭圆曲线群G中的任一点，则存在F的某些元素x和y，

使得P=(x，y)，于是T^-1(T(P))=T^-1(T((x，y)))=T^-1((x·r，

y·r))=(x·r·r^-1，y·r·r^-1)=(x，y)=P。因此A部分中的条

件(ⅰ)得到满足。(ⅱ)设有G中两点P和S，则我们需要表明P+S=T^-1(P′^_ S′)

式中P′=T(P)，S′=T(S)。令P=(x₁，y₁)，P′=(x₁′，y₁′)，S=(x₂，

y₂)，S′=(x₂′，y₂)，Q=P+S=(x₃，y₃)和Q′=P′+S′=(x₃′，y₃′)。

然后用公式A中给出的在椭圆曲线群中的点加法规则，Q坐标由下式给出：x₃=L·L+L+x₁+x₂+a和y₃=L·(x₁+x₃)+x₃+y₁)，

式中L=(y1+y2)·z，z=(x1-x2)-1。另一方面上面的公式A′则给出了Q′的坐标。于是，可表明Q′的坐标为：

z′=(x₁′·x₂′)^-1·r²

    =(x₁·r·x₂·r)^-1·r²

    =(x₂-x₁)^-1·r

    =z·r

L′=(y₁′+y₂′)·z′·r^-1

    =(y₂·r-y₁·r)·(z·r)·r^-1

    =(y₁+y₂)·z·r

    =L·r

x₃′=L′·L′·r^-1+L′+x₁＇-x₂′+a′

    =(L·r)·(L·r)·r^-1+L·r+x₁·r+x₂·r-a′·r

    =(L·L+L+x₁+x₂+a′)·r

    =x₃·r

y₃′=L′·(x₁′+x₃′)·r^-1+y₁′

    =(L·r)·(x1·r-x3·r)·r-1+x3·r+y1·r

    =(L·(x₁+x₃)+x₃+y₁)·r

    =y₃·r

因此，我们就有(x₃′，y₃′)=(x₃·r，y₃·r)，这意味着如所要求的那样，P′^_ S′=T(P+S)，所以，A部分中的条件(ⅱ)得到满足。(ⅲ)本发明为选择G′、T、^_、T^-1以及它们相应算法提供了一种方法。这种方法的方式使得设有P₁，P₂…P_N∈G，这里N是一个整数，则在一般情况下，对T^-1(T(P₁)^_T(P₂)^_…^_T(P_N)的计算要优于对P₁+P₂+…+P_N的计算。为证明这点，请注意T(P₁)_T(P₂)^_…^_T(P_N)的计算中包括了对公式B′中的表达式的重复使用。但是还请注意，这些表达式对于r而言均属于蒙哥马利标准形式。正因如此，可以很容易地将GF(2^k)中的蒙哥马利算法应用于T(P₁)^_T(P₂)^_…^_T(P_N)的计算，以建立优化的硬件和／或软件工具。因此在A部分中的条件(ⅱ)得到满足。E部分

本发明进一步提出了一种方法，通过提出r的特定选择，从而使得利用C部分和D部分的方法时取得更高效率。

本发明适用于椭圆曲线群G定义于其上的域F的任何元素。但是对元素r的选取会影响到所得计算的计算特性。本发明讲授了，r的选取可以优化在特定计算机环境中一个软件和／或硬件工具的特定方面。例如选择r为32的倍数对32位计算机能有良好影响。给定r的一个特定选择后，则可用不只一种方法完成对a·b·r-1的计算，而其中一些可能具有更高的计算效率。优先采用r的如下选择：1．域GF(P)：选择r为大于P的2的最小幂。

2．域GF(P)：r可被选为k质数的乘积，它使所得算法具有更高程度的平行性。3．域GF(2k)：r被选为x^k mod n(x)，这里n(x)是生成域GF(2^k)的最简多项式。

对于其它的域也可能选择其它的r。变换算法的使用与这一选择无关。F部分

本发明进一步提出了一种方法，该方法用于优化任何有限域上的有限次的任意域运算的计算。令f为定义在F内的一个有限表达式，它包括有限量的变量和有限次的域运算+、·、-和^-1。本发明提出了优化f的计算的方法，它包括依次完成下列步骤：(1)选择r为域F的任一单一元素。这个常数元素r将被用于将表达式f变换成一个新的表达式f′，这种变换是通过一系列替代来完成的，替代按照本文件前面所述的替代方法进行。如果表达式f已包含一个由符号r代表的常数或变量，则在此程序中逐步地将符号r更名为某个特定的值，并在本程序的随后步骤中视作r在里面被适当地更名了。请注意，表达式f可能同时包含常数或变量，它们与所选元素r有相同的域值，这并不影响本程序。本程序的随后步骤将依赖原本不含“带撇号的”、象d′或j′这种符号的表达式。如果表达式f原本就含有由“带撇号的”的符号所表示的变量或常数，则用特定的、不带撇号的名称取代所有的带撇号的变量或常数。本程序随后的替代步骤将使用包含带撇号的符号的源表达式，而在本专利中，按惯例这种源表达式不允许匹配不带撇号的符号。请注意，包含不带撇号的、象x这样符号的源表达式在本专利中按惯例允许匹配带撇号的或者不带撇号的变量或常数符号。(2)通过用目标表达式x′取代所有出现的源表达式x，将表达式f    变换为表达式f₁。在这一替代中，x代表表达式f中的一个变量或常数。这样就用带撇号的符号替代了所有变量及常数。请注意，这种替换丝毫不影响表达式f中可能有的系数。(3)通过用目标表达式x^_y替代所有出现的源表达式x·y，将表达式f₁变换为表达式f₂。在这一替换中x和y代表f₁的子表达式，它们应当只包含带撇号的符号，而^_用来作为表示域F中的乘法运算的替代符号。这一步骤的目的是将表达式f中出现的、所有初始的·运算符号都以^_来标记，以使其有别于·运算符号。而在本方法后面的步骤中还要将·运算符号引入变换后的表达式。(4)通过用目标表达式x^-1·r²替代所有出现的源表达式x^-1，将表达式f₂变换为f₃。在这一替代中x表示f₂的一个子表达式。(5)通过用目标表达式x·y·r^-1替代所有出现的源表达式x^_y，将表达式f₃变换为表达式f₄。在这一替代中x和y表示f₃的子表达式。(6)通过用目标表达式x·r替代所有出现的源表达式x′，将表达式f₄变换为表达式f′。在这一替代中，x′表示f₃中出现的带撇号的变量或常数，特殊的是它还包含了所有不带撇号的常数r。这一步骤的作用是将所有带撇号的符号都用其不带撇号的的形式乘以r来代替。

在完成以上步骤后，表达式f即被变换为新的表达式f′。本发明以这种形式详细规定了上述步骤以确保f=f′·r^-1。为证明这点，用f=x+y，f=x-y，f=x·y和f=x^-1时的四个特例来演示结果，在这里x和y是域f中的元素。根据域交换、结合和分配等性质可推出一般结果。例1 变换后的加法

令f=x+y，对于表达式f应用本发明的替代方法，得到变换后的表达式f′=x·r+y·r。为证实f=f′·r^-1，请注意f=x+y=(x+y)·r·r^-1=(x·r-y·r)·r^-1=f′·r^-1。例2 变换后的减法

令f=x-y，对于表达式f应用本发明的替代方法，得到变换后的表达式f′=x·r-y·r。为证实f=f′·r^-1，请注意f=x-y=(x-y)·r·r^-1=(x·r-y·r)·r^-1=f′·r^-1。例3 变换后的乘法

令f=x·y，对于表达式f应用本发明的替代方法得到变换后的表达式f′=(x·r)·(y·r)·r^-1，为证实f=f′·r^-1，请注意f=x·y=x·y·r²·r^-2=x·y·r·r·r^-1·r^-1=x·r·y·r·r^-1·r^-1=(x·r)·(y·r)·r^-1·r^-1=f′·r^-1。例4 变换后的求逆

令f=x^-1，对于表达式f应用本发明的替代方法得到变换后的表达式f′=(x·r)^-1·r²，为证实f=f′·r^-1，请注意f=x^-1·r^-2·r^-2=x^-1·r^-1·r^-2·r^-1=(x·r)^-1·r^-2·r^-1=f′·r^-1。

这样本发明就提出了一种方法，将包括有限域内的有限次域运算的任何表达式f变换为f′·r^-1的形式。而且由本发明所构造的表达式f′·r^-1保证属于蒙哥马利标准形式。为证明这一点，请注意，(i)本发明方法的替换步骤确保了当初始表达式f包括形式为x·y的子表达式时，这样的子表达式被变换成(x·r)·(y·r)·r^-1的形式，而它属于蒙哥马利标准形式；(ⅱ)只要本发明方法的替代步骤将一种新的乘法运算引入变换后的表达式，这种运算就会随之带来一个单一的附加运算对象，而它总是r的乘方，这样，就保持了所引入的子表达式为蒙哥马利标准形式。

根据F的确切特性和表达式f中乘法的运算数量，以及f′的计算中所包含的运算的确切数量和特性，计算表达式f′·r^-1与直接计算表达式f相比可能更为高效。当域F是GF(P)或GF(2^k)的元素时，这一可能性是很大的。于是可将蒙哥马利算法应用于表达式f′·r^-1以确保得到优化的表达式f的求值运算。G部分

本发明可以以“投影坐标”使用，使用“投影坐标”是为了避免进行求逆。

例如在“投影坐标”中，椭圆曲线群G上的一个点有3个坐标值：(x₁，y₁，z₁)，而仿射坐标只要求有2个值(x₁，y₁)

例如，对于定义在GF(2^k)上的椭圆曲线，给定相异点P和Q，用投影坐标表示：

P：=(x₁，y₁，z₁)

Q：=(x₂，y₂，z₂)

在椭圆曲线上的2个点之和的投影坐标为：

P+Q：=(x₃，y₃，z₃)

运用下面的加法规则：

A=x₂·z₁-x₁

B=y₂·z₁-y₁

C=A+B

D=A²·(A+a·z₁)+z₁·B·C

x₃=A·D

y₃=C·D+A²·(B·x₁+A·y₁)

z₃=A³·z₁

这一运算要求进行13次域乘，没有求逆。

与此类似，计算2P的加法公式给定为：

A=x₁·z₁

B=b·z₁ ⁴+x₁ ⁴

x₃=A·B

y₃=x₁ ⁴·A+B·(x₁ ²+y₁·z₁+A)

z₃=A₃

这一运算要求进行7次域乘，没有求逆。

这样使用投影坐标就避免了求逆，而付出代价为储存了3个GF(2k)值以表示P，并进行了更多的乘法运算。

本发明还可以和投影坐标一起使用。于是加法规则可以修改如下：

A′=x₂′·z₁′·r^-1+x₁′

B′=y₂＇·z₁＇·r^-1+y₁′

C′=A′+B′

D′=(A′·A′·r^-1)·(A′+a′·z₁′·r^-1)·r^-1+(z₁′·B

′·r^-1)·C′·r^-1

x₃′=A′·D′·r^-1

y₃′=C′·D′·r^-1·(A′·A′·r^-1)·(B′·x₁′·r

^-1·A′·y1′·r^-1)·r^-1

z₃′=((A′·A′·r^-1)·A′·r^-1)·z₁′·r^-1

类似地，计算2P的规则修改为：

A′= x₁′·z₁′·r^-1

B′=(((b′·z₁′·r^-1)·z₁′·r^-1)·z₁′·r^-1)·z₁′·r^-1)

+((x₁′·x₁′·r^-1)·x₁＇·r^-1)·x₁′·r^-1

x₃′=A′·B′·r^-1

y₃′=(((x₁′·x₁′·r^-1)·x₁′·r^-1)·x₁′·r^-1)·

A＇·r^-1+B′·x₁′·x₁′·r^-1+y₁′·z₁′·r^-1+A

′)·r^-1

实施

本发明可以实施在任何普通的或通用的PC计算机系统上，它也可与任何网络系统共同使用，包括互联网。为实施本发明，优先选用的计算机系统具体装置是奔腾Ⅱ PC233 MHZ，运行视窗NT4．0。

本发明可以用任何编程语言实施，包括C语言和Java语言。下面是适于于实施本发明的伪代码的例子。Set up：a， b：Parameters of the elliptic curve (EC)

       F：The field upon which the EC is based

           Either GF (p) or GF (2^k)

    ^*：Field multiplication

    +：Field addition

    -：Field subtraaction

    -¹：field inversion

    P = (P (x)， P (y))：A point on the EC

    P (X) & P (y) are affine coordinates

    Algorithm Identifier：ExpPoint

    Input：e：k-bit integer

           P：Point on the EC， P = (P (X)， P (Y))

    Output：Q：Point on the EC， Q = (Q (X)， Q (Y))

              Q：= eP = (P + P +…P) (e times P)

    Function ExpPoint

    Begin

        /^* Transform P to P′ using r ^*/

    P′ (x) = P (x) ^* r

  P′ (y) = P (y) ^* r

    /^* Start with O′ point at infinity ^*/

    Q′=O′

    /^* Binary method loop ^*/

    Fori=k-1 downto O do

        Q′：= Doublepoint (Q′)

        If e_i=1 then Q′： =AddPoint (Q′，P′)

    /^* Transform Q′ to Q using r ^*/

    Q (x) = Q′ (x) ^* r^-1

    Q (y) = Q′ (y) ^* r^-1

    Return Q

    End

    Algorithm Identifier：AddPoint

    Input：P′：Transformed Point on the EC

           Q′：Traansformed Point on the EC

    Output：T′：Tranforrmed Point on the EC

              T＇：=P′ +Q′ using the EC point addition rules fuction

    AddPoint

    Begin

    /^* If the underlying field is GF (p)   ^*/

       Lambda′=Multiply ((Q′ (y) - P′(y))， Inverse (Q′(x)- P′(x))

      T′ (x)= Multiply (lanmbda′， lanmbda′) - P′ (x) - Q′ (x)

       T′(y)= Multiply (lanmbda′， (P′ (x) -T′(x)))-P′(y)

       Reture T

    /^* If the underlying field is GF (2^K)  ^*/

       Lambda′= Multiply((P′(y)+Q′(y))，Inverse (P′(x)+ Q＇(x))

       T′(x)=Multiply(lanmbda′，lanmbda′)+lanmbda′+P′(x)+Q′(x)+a′

       T′(y)= Multiply(lanmbda′，(P′(x)+T＇(x))) +T′(x)+P′(y)

    Return T

    EndAlgorithm Identifier: DoublePointInput：P′：Transformed point on the ECOutput：T′：Transformed point on the EC

    T′：= P′+P using the EC point doubling rules functionDoublePointBegin/^* If the underlying field is GF (P)          ^*/Lambda′=Multiply(Multiply(3P′(x)，P′(x))-a′)，Interverse (2P′(y)))T′(x)=Multiply(lambda′，lambda′)-2P′(x)T′(y)=Multiply(lambda′，(P′(x)-T′(x))) -P′(y)RetureT/^* Else ifthe underlying field is GF 2^K)    ^*/T′(x) = Multiply (P′(x)，P′(x))+

        Multiply (b′，Multiply (Inverse (P′(x)，P′(x))))T′(y)=Multiply((P′(x)，P′(x)) +

      Multiply (P′(x)+Multiply (P′(y)，Inverse(P′(x)))，T′(x))+T＇(x)Return TEndAlgorithm Idetifier：InverseInput：u：Field elementOutput：t：Field elementFuction InverseBegin

t=u^{-1 *}r²Return tEndAlgorithm Identifier：MultiplyInput：u， v：Field elementsOutput：t：Field elementFuction MultiplyBegin

T=u^*v^*r^-1Return tEnd

有若干参考资料描述了本发明的数学背景，这些参考资料包括：P．L Montgomery， Modular multiplication without trial division，“Mathematics of Computation，”44 (170)：519-521， April 1985； D．E．Knuth，“The Art of Computer Programming：SeminumericalAlgorithms，”volume2， Second edition， Reading， MA：Addison-Wesley， 1981；C．K．Koc and T．Acar， Montgomery multiplicationin GF(2k)，“Proceedings of Third Annual Workshop on SelectedAreeas in Cryptography，”pages 95-106，  Queen’s University，Kingston，Ontario， Canada， August 15-16，  1996；C．K．Koc andT. Acar．，Fast software exponentiation in GF(2k)，”proceedings，13th Symposium on Computer Arithmetic，”pages 225-231， Asilomar，California，July 6-9，1997，Los Alamitos，CA：IEEE ComputerSociety Press；J．C．Bajard，L．S．Didier，and P．Kornerup，An RNSMontgomery multiplication algorithm，“Proceedings，13thSymposium on Computer Arithmetic，”pages234-239， Asilomar，California，July 6-9，1997，Los Alamitos，CA：IEEE ComputerSociety Press；D．R．Stinson.“Cryptography Theory andPractice，”CRC Press，1995；V．Miller，Usesof Elliptic curvesin cryptography，“Advances in Cryptology-CRYPTO 85，Proceedings．” Pages 417-426，New York，NY：Springer-Verlag，1985；N．Koblitz， Elliptic curve cryptosystems，“Mathematics ofComputation，“48：203-209，1987；N．Koblitz，A Course in NumberTheory and Cryptography，” New York， NY： Springer-Verlag，1987；A．J．Menezes，“Elliptic Cureve Public Key Cryptosystems，”Boston，MA：Kluwer Academic Publishers，1993；R．L．Riveswt，A．Shamir，and L．Adleman，A method for Obtaining DigitalSignatures and Public-key Cryptosystems．” Communications of theACM，21(2)：120-126，1978，T．Beth，M．Frisch，and G．J．Simmons，Public-key cryptography：State of the Art and Future Directions．Springer-Verlag，NY，1991；IEEE Working Group P1262，WorkingDraft：IEEE 1363：Standard for RSA，Diffie-Hellman and RelatedPublic-key Cryptography．In preparation，1995；RSALaboratories，Answers to Frequently Asked Questions about Today’sCryptography．Version 3．0，1996；G．B．Agnew，R．C．Mullin，I．M．Onyszchuk，and S．A．Vanstone，An implementation of a fastpublic-key cryptosystem．Journal of Cryptology，3(2)：63-79，1991．

所有这些出版物都在这里引用为参考资料，可视为在这里每种出版物是被单独引用的。

以一个优先选用的实施例描述和说明了我们的发明的原理。很明显，本发明可以在结构和细节上加以修改，而不脱离这些原理。因此，应该明白，这一详尽的实施例仅为说明性质，不应将它看作限制了我们发明的范围。相反，我们申明所有的可能属于本发明权利要求及等同物范围和原则内的这类实施例为我们的发明。

Claims (23)

1．一种用任意整数e，在一个椭圆曲线群G上的一点P得到椭圆曲线点乘积Q=eP的方法，该椭圆曲线群G定义在域F上，G∈F×F，这种方法由下列步骤组成：建立一个集合G′；建立从G到集合G′的映射T，构造从G′到G的映射T^-1，构造定义在G′上的运算^_，使得(a)给定P∈G，T^-1(T(P))=P，并且(b)P+P=T^-1(P′^_P′)，式中P′=T(P)；通过用映射T将点P映射到点P′，完成在点P′上的运算^_，以求得点Q′=eP′。再用映射，T^-1将点Q′映射到结果Q，这样来取得椭圆曲线点乘结果Q；和将结果Q用于密码术运算。

2．如权利要求1的方法，其中集合G、集合G′、映射T、运算^_及映射T^-1是这样构造的，使得给定P₁，P₂，…P_N∈G，这里N为一个整数，则计算T^-1(T(P₁)^_T(P₂)^_…^_T(P_N))与计算P₁+P₂+…+PX相比，要更为高效。

3．如权利要求1的方法，其中：通过选定域F的任一元素r，并定义T为T：(x，y)→(x·r，y·r)，来建立映射T，式中P=(x，y)∈G，并且·是F中的乘法算符；以及通过定义T：(u，v)→(u·r^-1，v·r^-1)来建立T，式中P′=(u，v)∈G′。

4．如权利要求3的方法，其中域F是GF(P)的一个元素。

5．如权利要求4的方法，其中运算r选择为大于P的2的最小乘方。

6．如权利要求4的方法，其中元素r选择为质数的乘积。

7．如权利要求4的方法，其中构造运算^_使得集合G′中两点的加法由下列公式给出：(x₃′，y₃′)=(x₁′，y₁′)^_(x₂′，y₂′)；z′=(x₂′-x₁′）^-1·r²L′=(y₂′-y₁′)·z′·r^-1x₃′=L′·L′·r^-1-x₁′-x₂′y₃′=L′·(x₁′-x₃′)·r^-1-y₁′

8．如权利要求4的方法，其中构造运算^_，使得集合G′中一点的加倍由下列公式给出：(x₁′，y₁′)^_(x₁′，y₁′)=(x₃′，y₃′)z′=(y₁′+y₁′)^-1·r²L′=((x₁′+x₁′+x₁′)·x₁′·r^-1+a)·z′·r^-1x₃′=L′·L′·r^-1-x₁′-x₁′y₃′=L′·(x₁′-x₃′)·r^-1-y₁′

9．如权利要求4的方法，其中GF(P)中的蒙哥马利算法被用于完成对点P′的运算^_以求得点Q′=eP′。

10．如权利要求3的方法，其中域F是GF(2^k)的一个元素。

11．如权利要求10的方法，其中构造运算^_，使得集合G′中的两点的相加由下式给出：(x₃′，y₃′)=(x₁′，y₁′)^_(x₂′，y₂′)；z′=(x₁′-x₂′)^-1·r²L′=(y₁′-y₂′)·z′·r^-1x3′=(L′·L′·r^-1)+L′+x₁′+x₂′+a′和y3′=(L′·(x₁′+x₃’)·r^-1)+x₃′+y₁′

12．如权利要求10的方法，其中构造运算^_，使得一点的加倍由下式给出：(x₁′，y₁′)^_(x₁′，y₁′)=(x₃′，y₃′)z′=(x1′)^-1·r²x₃′=x₁′·x₁′·r^-1+(z′·z′·r^-1)·b·r^-1y₃′=x₁′·x₁′·r^-1+(x₁′+y₁′·z′·r^-1)·x₃′·r^-1+x₃′

13．如权利要求10的方法，其中元素r选择为x^kmod n(x)，这里n(x)是生成域GF(2^k)的最简多项式。

14．如权利要求10的方法，其中GF(2^k)中的蒙哥马利算法用于完成对点P′的运算^_，以求得点Q′=eP′。

15．如权利要求1的方法，其中在完成对点P′的运算^_的步骤中，使用了双元法。

16．如权利要求1的方法，其中在完成对点P′的运算^_的步骤中，使用了M元法。

17．如权利要求1的方法，其中利用投影坐标，求出了集合G和G′的元素。

18．一种优化表达式f=f(x₁，…，x_I，…，x_n)的计算方法，这里表达式f由任一有限域上的、有限次的域运算所组成，x₁，…，x_i，…，X_n都是F的元素。这一方法由下列步骤组成：从域F中选择任一常数元素r；通过下列步骤将表达式f=f(x₁，…，x_i，…，x_n)变换到f=f(x₁′，…，x_i′，…，x_n′)：用x′替代表达式f中出现的、所有的x，以得到f₁，这里x代表f的一个变量或常数；用x^_y替代表达式f₁中出现的所有x·y，得到f₂，这里x和y代表f₁的子表达式；用x^-1·r2替代表达式f₂中出现的所有x^-1，得到f₃，这里x代表f₂的一个子表达式；用x·y·r^-1替代表达式f₃中出现的所有x^_y，得到f₄，这里x和y代表f₃的子表达式；用x·r替代表达式f₄中出现的所有x＇，得到f＇，这里x代表f₄中带撇号的变量或常数；对f=f＇·m^-1求值；并且使用f＇·m^-1进行密码操作中的计算。

19．如权利要求18的方法，其中当域F是GF(P)的元素时，对于每例x＇·y＇·m^-1均使用蒙哥马利算法加以计算。

20．如权利要求18的方法，其中当域F是GF(2^K)的元素时，对于每例x＇·y＇·m^-1均使用GF(2^K)中的蒙哥马利算法加以计算。

21．一种用于求得椭圆曲线点相加结果Q=P+P的方法，它使用在一个椭圆曲线群G上的一点P，而该椭圆曲线群G定义在域F上，G∈F×F。这一方法由下列步骤组成：建立一个集合G＇；建立从G到集合G＇的映射T，建立从G＇到G的映射T^-1，并构造定义在G＇上的运算^_，使得(a)给定P∈G，则T^-1(T(P))=P，并且(b)P+P=T^-1(P＇^_P＇)，式中P＇=T(p)；通过用映射T将点P变换到点P＇；完成在点P＇和点P＇上的运算^_以求得点Q＇；再用映射T^-1将点Q＇变换到结果Q。这样来取得椭圆曲线点加结果Q；并将结果Q用于密码系统运算。

22．一种用于求得椭圆曲线点加结果Q=P+S的方法。它使用了在椭圆曲线群G上的点P和S，该曲线群定义在一个域F上， $G\⋐F\×F,$ 这一方法由下列步骤组成：建立一个集合G；建立从G到集合G′的映射T，建立从G′到G的映射T^-1，并构造定义在G′上的运算^_，使得(a)给定P∈G，则T^-1(T(P))=P，并且(b)P+S=T^-1(P′^_S′)，式中P′=T(p)，S′=T(s)；通过用映射T将点P变换到点P′，用映射T将点S变换到点S′，完成对点P′和点S′的运算^_以求得点Q′，再用映射T^-1将点Q′变换到结果Q，这样取得椭圆曲线点加结果Q；并将结果Q用于密码系统运算。

23．用于求得椭圆曲线点乘结果Q=eP的装置，它使用了一个任意整数e和在椭圆曲线群G上的一点P，椭圆曲线群G定义在域F上，G∈F×F，该装置包括：建立集合G′的装置；完成以下工作的装置：建立从G到集合G′的映射T，建立从G′到G的映射T^-1，并构造定义在G′上的运算^_，使得(a)给定P∈G，则T^-1(T(P))=P，(b)P+P=T^-1(P′^_P′)式中P′=T(p)；完成以下工作的装置：通过用映射T将点P变换到点P′并完成在点P′上的运算^_，求得点Q′=eP′，再用映射T^-1将点Q′变换到结果Q，这样取得椭圆曲线点乘结果Q；用于在密码系统运算中使用结果Q的装置。