椭圆曲线上的密码学方法
专利名称：椭圆曲线上的密码学方法
技术领域：
本发明涉及椭圆曲线上的密码学方法。这种方法是基于公共密钥算法的使用并且可以应用于消息的概率的数字信号的生成和/或应用于密钥交换协议和/或应用于消息加密算法。
生成并且验证数字签名的算法包括计算称为签名的一个或多个整数，一般成对，并且与一个给定消息相关联以便证明签名完全一致以及所签消息的完整性。当算法在生成签名时使用随机变量时该签名被认为是概率的，这个随机变量是秘密的并且在每个新的签名处重新生成。因此相同用户发送的相同的消息可具有几个不同的签名。
密钥交换协议以及加密算法还使用在该算法的每个新的应用处生成的秘密随机变量k。
椭圆曲线上的公共密钥密码学算法越来越多地被使用。这种算法是基于使用曲线E上满足下列等式的点P(x，y)y2+xy＝x3+ax2+b，其中a和b是有限域的两个元素。
在曲线E的点P上执行加或减运算。包括增加k次相同的点P的运算称为P与k的纯量乘法，并且对应于定义如下的椭圆曲线上的点C，C(x’，y’)＝k·P(x，y)。
这样算法的一个例子可由ECDSA(来自英语椭圆曲线数字标准算法)来说明，其是用于生成和验证概率的数字签名的算法。
ECDSA的参数是-E，在集合Zp上定义的椭圆曲线，曲线E上的点数可由一个大的质数N划分，一般N＞2160，-P(x，y)，椭圆曲线E上一个给定的点。
密钥d是0和N-1之间的随机固定数，并且公共密钥Q通过纯量乘法等式Q(x1，y1)＝d·P(x，y)与d相关。
令m为要发送的消息。m的ECDSA签名是包含在范围[1，N-1]内的一对整数(r，s)并且定义如下-令k是在范围[1，N-1]内选择的随机数，k是在每个签名处生成的随机变量；-通过纯量乘法C(x’，y’)＝k·P(x，y)获得点C的计算；
-rX’mod N；-s＝k-1(h(m)+d·r)mod N；h(m)是哈希函数h(其是一个伪随机密码学函数)应用到原始消息m的结果。
利用公共参数(E，P，N，Q)执行如下的签名验证执行中间计算-w＝s-1mod N；-u1＝h(m)·w mod N；-u2＝r·w mod N；-通过计算对应于u1P+u2Q＝(x0，y0)的曲线E上的点执行加法和纯量乘法运算。
检查是否 如果这个等式为真，则签名是真实的。
通过密钥d和对每个签名不同的秘密随机数k执行签名(r，s)的生成，以及其与公共密钥参数的验证。因此任何人可以在不持有其密钥的情况下验证卡及其持有人。
在椭圆曲线上执行这样一个签名算法的代价与用于定义点C＝k·P的纯量乘法运算的复杂性和速度直接相关。
已经开发出对椭圆曲线上密码学方法的改进以便促进并且加速这个纯量乘法运算。特别地，在Springer Verlag，Crypto’97会议录中出现的J.A.Solinas的文章“An Improved Algorithm for Arithmeticon a Family of Elliptic Curves(用于在椭圆曲线族上运算的改进算法)”，描述了一种可能的改进。
为了加速在椭圆曲线E上算法上下文中用于计算纯量乘法的方法，因此已经设想在称为非正态二进制椭圆曲线或科布李兹(koblitz)曲线的特定椭圆曲线族上操作，其中称为弗若贝涅斯(Frobenius)运算符的特定运算符可用，有可能更快速地计算纯量乘法运算。
科布李兹曲线由下列等式在数学集合GF(2n)上定义y2+xy＝x3+ax2+1 with a∈(0，1]弗若贝涅斯运算符T定义如下具有等式τ2+2＝(-1)1-aτ的τ[P(x，y)]＝(x2，y2)。
在椭圆曲线E上将运算符τ应用于给定点P上建立了一个快速运算，因为工作在数学集合GF(2n)上完成，n是有限域的大小，例如n＝163。
为了促进纯量乘法C(x1，y1)＝k·P(x，y)的运算，整数k被分解以便等于加法和减法运算。按这种方法由NAF(来自英语的非相邻形式)定义整数k的非相邻形式，其包括以合计形式写的整数kk＝∑(I＝0 to 1-1)ei2i其中ei∈(-1，0，1)且1 n在科布李兹椭圆曲线的情况下，可以利用弗若贝涅斯运算符表示NAFk＝∑(i-0 to 1) eiτi因此P与k的纯量乘法运算等于将弗若贝涅斯运算符应用于点P，其简单并且快速。
除此之外，通过一些对(ki，Pi＝ki·P)的预先计算和存储，这些对能够有利地存储在实现签名算法的设备的存储器中，可以进一步加速纯量乘法运算k·P。实际上P形成了一部分签名算法的密钥的公共参数。
对于163比特随机变量k，因此可能通过存储42个纯量乘法对(k1，Pi)，来在没有任何预先计算的情况下将加法/减法运算减少到19个来代替52个。
本发明的目的是使进一步减少纯量乘法的加法数量成为可能的椭圆曲线上的密码学方法。
本发明特别与用于生成概率的数字签名和/或用于密钥交换协议和/或用于加密算法的密码学方法相关，所述方法基于在非正态二进制椭圆曲线(E)(科布李兹曲线)上使用公共密钥算法，该曲线上选择点P(x，y)，存储对(ki，Pi)，其中Pi是对应于点P与ki的纯量乘法的点，所述方法包括生成随机变量k以及计算对应于点P与k的纯量乘法的点C(C＝k·P)的步骤，其特征在于所述随机变量k的生成以及点C的计算同时执行。
根据一个应用，用于生成概率的数字签名的密码学算法是ECDSA(来自英语的椭圆曲线数字标准算法)。
根据另一个应用，密钥交换协议密码学算法是ECDH(来自英语的椭圆曲线迪夫-哈尔曼(Diffie-Hellmann))。
根据一个特征，本方法基于在数学集合GF(2n)上定义的科布李兹曲线的使用，在其上可用所谓的弗若贝涅斯运算符τ[P(x，y)]＝(x2，y2)，本方法的特征在于其包括以下步骤-初始化随机变量k＝0以及点C＝0，-对于j从1到niter执行循环，所述循环包括-在每个新的迭代处生成下列随机变量-a，在0和n之间，n是其上定义曲线的有限域的大小，-u{-1，1}，-i在0和t之间，t是存储的对(ki，Pi)的数量，-计算点Cj＝Cj-1+u·τa·Pi-生成随机变量Kj＝Kj-1+u·ki·τa-在循环的末尾将k转换为整数，-同时提供随机变量k和点C＝k·P。
根据一个特征，存储的对(ki，Pi)的的数量t在35和45之间。
根据另一个特征，循环(niter)的迭代数固定在10和12之间。
根据另一个特征，在其上定义科布李兹曲线的数学域的大小n等于163。
本发明还涉及具有电子组件能够实现根据本发明的签名方法的智能卡类型的安全设备，或者提供有加密软件的计算机类型的计算设备。
根据本发明的方法的优点是首先通过与纯量积k·P的计算同时生成随机变量k并且其次通过对ki，Pi＝ki·P的预先计算减少加法运算的数量来减少作为在椭圆曲线上使用密码学方法中的一个基本步骤的计算P和k的纯量积所需时间。
本发明的特性和优点从参考ECDSA算法以及通过说明性和非限制性例子的下列描述的解释中显现地更加清楚。根据本发明的方法实际上可以应用于例如密钥交换协议或加密算法中。
令E是在集合GF(2n)上定义的科布李兹椭圆曲线，n＝163在其上执行工作的数学域的大小，并且令P(x，y)是这个曲线上给定的点。
然后可用弗若贝涅斯运算符τ[P(x，y)]＝(x2，y2)，并且形成了在其上执行工作的域GF(2n)的快速运算。
首先计算特定数量的对(ki，Pi＝k·P)，其存储在实现签名方法的组件(例如一种智能卡微控制器)中。对的数量固定为35和45之间的t，其形成签名生成计算方法所占存储空间和需要的加速之间的折衷。
根据本发明的方法在于通过使用预先计算以及存储对(ki，Pi)在计算点C＝k·P的同时生成随机变量k来加速生成概率的签名的方法。
首先C和k的值初始化为0。
然后执行迭代niter的j上的循环，其执行下列运算-在每个新的迭代j处生成下列随机变量-r，0和n之间，-u{-1，1}，-i在0和t之间，-计算Cj＝Cj-1+u·τr·Pi-计算kj＝kj-1+u·ki·τr然后在循环的输出处获得，随机变量k，其被转换为整数，并且点C对应P与k的纯量乘法。
然后根据ECDSA的常规过程，或者使用科布李兹椭圆曲线的另一种算法，利用根据本发明的方法定义的k和C的值生成签名(r，s)。
与点C的计算同时生成k，特别是通过减少计算P与k的纯量乘法所需的加法的数量，加速了签名生成方法。计算点C的加法的数量实际上是niter-1。
根据需要的保密和性能的程度，niter固定在10和12次迭代之间。
因此，通过作为整数163的k以及通过存储大约40个对(ki，Pi)，通过仅执行9到11次加法运算可能计算出纯量乘法k·P。
权利要求
1.一种用于生成概率的数字签名和/或用于密钥交换协议和/或用于加密算法的密码学方法，所述方法基于在非正态二进制椭圆曲线(E)(科布李兹曲线)上使用公共密钥算法，在所述曲线上选择一个点P(x，y)，存储对(ki，Pi)，其中Pi是对应于点P与ki的纯量乘法的点，所述方法包括生成随机变量k以及计算对应于点P与k的纯量乘法的点C(C＝k·P)的步骤，其特征在于所述随机变量k的生成以及点C的计算同时执行。
2.根据权利要求1的方法，其特征在于用于生成概率的数字签名的密码学算法是ECDSA(椭圆曲线数字标准算法)。
3.根据权利要求1的方法，其特征在于密钥交换协议密码学算法是ECDH(椭圆曲线迪夫-哈尔曼)。
4.根据前面任何一个权利要求的方法，所述方法基于在数学集合GF(2n)上定义的科布李兹曲线的使用，在其上可用所谓的弗若贝涅斯运算符τ[P(x，y)]＝(x2，y2)，所述方法的特征在于其包括以下步骤-初始化随机变量k＝0以及点C＝0，-对于j从1到niter执行循环，所述循环包括-在j的每个新的迭代处生成下列随机变量-a，在0和n之间，n是其上定义曲线(E)的有限域的大小，-u{-1，1}，-i在0和t之间，t是存储的对(ki，Pi)的数量，-计算点Cj＝Cj-1+u·τa·Pi-生成随机变量ki＝ki-1+u·ki·τa-在循环的末尾将k转换为整数，-同时r jwa随机变量k和点C＝k·P。
5.根据权利要求4的方法，其特征在于存储的对(ki，Pi)的的数量(t)在35和45之间。
6.根据权利要求4的方法，其特征在于循环(niter)的迭代数固定在10和12之间。
7.根据权利要求4的方法，其特征在于在其上定义科布李兹曲线(E)的数学域的大小n被定义等于163。
8.一种智能卡类型的安全设备，其特征在于其包括能够实现根据权利要求1到7的签名方法的组件。
9.一种提供有加密软件的计算机类型的计算设备，其特征在于其具有能够实现根据权利要求1到7的签名方法的电子组件。
全文摘要
本发明涉及一种用于生成概率的数字签名和/或用于密钥交换协议和/或用于加密算法的密码学方法，所述方法基于在非正态二进制椭圆曲线(E)(科布李兹曲线)上使用公共密钥算法，在所述曲线上选择一个点P(x，y)，存储对(k
文档编号G09C1/00GK1425231SQ0180822
公开日2003年6月18日 申请日期2001年4月18日 优先权日2000年4月18日
发明者J·-S·科伦, C·蒂门 申请人:格姆普拉斯公司
技术领域：
本发明涉及椭圆曲线上的密码学方法。这种方法是基于公共密钥算法的使用并且可以应用于消息的概率的数字信号的生成和/或应用于密钥交换协议和/或应用于消息加密算法。
生成并且验证数字签名的算法包括计算称为签名的一个或多个整数，一般成对，并且与一个给定消息相关联以便证明签名完全一致以及所签消息的完整性。当算法在生成签名时使用随机变量时该签名被认为是概率的，这个随机变量是秘密的并且在每个新的签名处重新生成。因此相同用户发送的相同的消息可具有几个不同的签名。
密钥交换协议以及加密算法还使用在该算法的每个新的应用处生成的秘密随机变量k。
椭圆曲线上的公共密钥密码学算法越来越多地被使用。这种算法是基于使用曲线E上满足下列等式的点P(x，y)y2+xy＝x3+ax2+b，其中a和b是有限域的两个元素。
在曲线E的点P上执行加或减运算。包括增加k次相同的点P的运算称为P与k的纯量乘法，并且对应于定义如下的椭圆曲线上的点C，C(x’，y’)＝k·P(x，y)。
这样算法的一个例子可由ECDSA(来自英语椭圆曲线数字标准算法)来说明，其是用于生成和验证概率的数字签名的算法。
ECDSA的参数是-E，在集合Zp上定义的椭圆曲线，曲线E上的点数可由一个大的质数N划分，一般N＞2160，-P(x，y)，椭圆曲线E上一个给定的点。
密钥d是0和N-1之间的随机固定数，并且公共密钥Q通过纯量乘法等式Q(x1，y1)＝d·P(x，y)与d相关。
令m为要发送的消息。m的ECDSA签名是包含在范围[1，N-1]内的一对整数(r，s)并且定义如下-令k是在范围[1，N-1]内选择的随机数，k是在每个签名处生成的随机变量；-通过纯量乘法C(x’，y’)＝k·P(x，y)获得点C的计算；
-rX’mod N；-s＝k-1(h(m)+d·r)mod N；h(m)是哈希函数h(其是一个伪随机密码学函数)应用到原始消息m的结果。
利用公共参数(E，P，N，Q)执行如下的签名验证执行中间计算-w＝s-1mod N；-u1＝h(m)·w mod N；-u2＝r·w mod N；-通过计算对应于u1P+u2Q＝(x0，y0)的曲线E上的点执行加法和纯量乘法运算。
检查是否 如果这个等式为真，则签名是真实的。
通过密钥d和对每个签名不同的秘密随机数k执行签名(r，s)的生成，以及其与公共密钥参数的验证。因此任何人可以在不持有其密钥的情况下验证卡及其持有人。
在椭圆曲线上执行这样一个签名算法的代价与用于定义点C＝k·P的纯量乘法运算的复杂性和速度直接相关。
已经开发出对椭圆曲线上密码学方法的改进以便促进并且加速这个纯量乘法运算。特别地，在Springer Verlag，Crypto’97会议录中出现的J.A.Solinas的文章“An Improved Algorithm for Arithmeticon a Family of Elliptic Curves(用于在椭圆曲线族上运算的改进算法)”，描述了一种可能的改进。
为了加速在椭圆曲线E上算法上下文中用于计算纯量乘法的方法，因此已经设想在称为非正态二进制椭圆曲线或科布李兹(koblitz)曲线的特定椭圆曲线族上操作，其中称为弗若贝涅斯(Frobenius)运算符的特定运算符可用，有可能更快速地计算纯量乘法运算。
科布李兹曲线由下列等式在数学集合GF(2n)上定义y2+xy＝x3+ax2+1 with a∈(0，1]弗若贝涅斯运算符T定义如下具有等式τ2+2＝(-1)1-aτ的τ[P(x，y)]＝(x2，y2)。
在椭圆曲线E上将运算符τ应用于给定点P上建立了一个快速运算，因为工作在数学集合GF(2n)上完成，n是有限域的大小，例如n＝163。
为了促进纯量乘法C(x1，y1)＝k·P(x，y)的运算，整数k被分解以便等于加法和减法运算。按这种方法由NAF(来自英语的非相邻形式)定义整数k的非相邻形式，其包括以合计形式写的整数kk＝∑(I＝0 to 1-1)ei2i其中ei∈(-1，0，1)且1 n在科布李兹椭圆曲线的情况下，可以利用弗若贝涅斯运算符表示NAFk＝∑(i-0 to 1) eiτi因此P与k的纯量乘法运算等于将弗若贝涅斯运算符应用于点P，其简单并且快速。
除此之外，通过一些对(ki，Pi＝ki·P)的预先计算和存储，这些对能够有利地存储在实现签名算法的设备的存储器中，可以进一步加速纯量乘法运算k·P。实际上P形成了一部分签名算法的密钥的公共参数。
对于163比特随机变量k，因此可能通过存储42个纯量乘法对(k1，Pi)，来在没有任何预先计算的情况下将加法/减法运算减少到19个来代替52个。
本发明的目的是使进一步减少纯量乘法的加法数量成为可能的椭圆曲线上的密码学方法。
本发明特别与用于生成概率的数字签名和/或用于密钥交换协议和/或用于加密算法的密码学方法相关，所述方法基于在非正态二进制椭圆曲线(E)(科布李兹曲线)上使用公共密钥算法，该曲线上选择点P(x，y)，存储对(ki，Pi)，其中Pi是对应于点P与ki的纯量乘法的点，所述方法包括生成随机变量k以及计算对应于点P与k的纯量乘法的点C(C＝k·P)的步骤，其特征在于所述随机变量k的生成以及点C的计算同时执行。
根据一个应用，用于生成概率的数字签名的密码学算法是ECDSA(来自英语的椭圆曲线数字标准算法)。
根据另一个应用，密钥交换协议密码学算法是ECDH(来自英语的椭圆曲线迪夫-哈尔曼(Diffie-Hellmann))。
根据一个特征，本方法基于在数学集合GF(2n)上定义的科布李兹曲线的使用，在其上可用所谓的弗若贝涅斯运算符τ[P(x，y)]＝(x2，y2)，本方法的特征在于其包括以下步骤-初始化随机变量k＝0以及点C＝0，-对于j从1到niter执行循环，所述循环包括-在每个新的迭代处生成下列随机变量-a，在0和n之间，n是其上定义曲线的有限域的大小，-u{-1，1}，-i在0和t之间，t是存储的对(ki，Pi)的数量，-计算点Cj＝Cj-1+u·τa·Pi-生成随机变量Kj＝Kj-1+u·ki·τa-在循环的末尾将k转换为整数，-同时提供随机变量k和点C＝k·P。
根据一个特征，存储的对(ki，Pi)的的数量t在35和45之间。
根据另一个特征，循环(niter)的迭代数固定在10和12之间。
根据另一个特征，在其上定义科布李兹曲线的数学域的大小n等于163。
本发明还涉及具有电子组件能够实现根据本发明的签名方法的智能卡类型的安全设备，或者提供有加密软件的计算机类型的计算设备。
根据本发明的方法的优点是首先通过与纯量积k·P的计算同时生成随机变量k并且其次通过对ki，Pi＝ki·P的预先计算减少加法运算的数量来减少作为在椭圆曲线上使用密码学方法中的一个基本步骤的计算P和k的纯量积所需时间。
本发明的特性和优点从参考ECDSA算法以及通过说明性和非限制性例子的下列描述的解释中显现地更加清楚。根据本发明的方法实际上可以应用于例如密钥交换协议或加密算法中。
令E是在集合GF(2n)上定义的科布李兹椭圆曲线，n＝163在其上执行工作的数学域的大小，并且令P(x，y)是这个曲线上给定的点。
然后可用弗若贝涅斯运算符τ[P(x，y)]＝(x2，y2)，并且形成了在其上执行工作的域GF(2n)的快速运算。
首先计算特定数量的对(ki，Pi＝k·P)，其存储在实现签名方法的组件(例如一种智能卡微控制器)中。对的数量固定为35和45之间的t，其形成签名生成计算方法所占存储空间和需要的加速之间的折衷。
根据本发明的方法在于通过使用预先计算以及存储对(ki，Pi)在计算点C＝k·P的同时生成随机变量k来加速生成概率的签名的方法。
首先C和k的值初始化为0。
然后执行迭代niter的j上的循环，其执行下列运算-在每个新的迭代j处生成下列随机变量-r，0和n之间，-u{-1，1}，-i在0和t之间，-计算Cj＝Cj-1+u·τr·Pi-计算kj＝kj-1+u·ki·τr然后在循环的输出处获得，随机变量k，其被转换为整数，并且点C对应P与k的纯量乘法。
然后根据ECDSA的常规过程，或者使用科布李兹椭圆曲线的另一种算法，利用根据本发明的方法定义的k和C的值生成签名(r，s)。
与点C的计算同时生成k，特别是通过减少计算P与k的纯量乘法所需的加法的数量，加速了签名生成方法。计算点C的加法的数量实际上是niter-1。
根据需要的保密和性能的程度，niter固定在10和12次迭代之间。
因此，通过作为整数163的k以及通过存储大约40个对(ki，Pi)，通过仅执行9到11次加法运算可能计算出纯量乘法k·P。
权利要求
1.一种用于生成概率的数字签名和/或用于密钥交换协议和/或用于加密算法的密码学方法，所述方法基于在非正态二进制椭圆曲线(E)(科布李兹曲线)上使用公共密钥算法，在所述曲线上选择一个点P(x，y)，存储对(ki，Pi)，其中Pi是对应于点P与ki的纯量乘法的点，所述方法包括生成随机变量k以及计算对应于点P与k的纯量乘法的点C(C＝k·P)的步骤，其特征在于所述随机变量k的生成以及点C的计算同时执行。
2.根据权利要求1的方法，其特征在于用于生成概率的数字签名的密码学算法是ECDSA(椭圆曲线数字标准算法)。
3.根据权利要求1的方法，其特征在于密钥交换协议密码学算法是ECDH(椭圆曲线迪夫-哈尔曼)。
4.根据前面任何一个权利要求的方法，所述方法基于在数学集合GF(2n)上定义的科布李兹曲线的使用，在其上可用所谓的弗若贝涅斯运算符τ[P(x，y)]＝(x2，y2)，所述方法的特征在于其包括以下步骤-初始化随机变量k＝0以及点C＝0，-对于j从1到niter执行循环，所述循环包括-在j的每个新的迭代处生成下列随机变量-a，在0和n之间，n是其上定义曲线(E)的有限域的大小，-u{-1，1}，-i在0和t之间，t是存储的对(ki，Pi)的数量，-计算点Cj＝Cj-1+u·τa·Pi-生成随机变量ki＝ki-1+u·ki·τa-在循环的末尾将k转换为整数，-同时r jwa随机变量k和点C＝k·P。
5.根据权利要求4的方法，其特征在于存储的对(ki，Pi)的的数量(t)在35和45之间。
6.根据权利要求4的方法，其特征在于循环(niter)的迭代数固定在10和12之间。
7.根据权利要求4的方法，其特征在于在其上定义科布李兹曲线(E)的数学域的大小n被定义等于163。
8.一种智能卡类型的安全设备，其特征在于其包括能够实现根据权利要求1到7的签名方法的组件。
9.一种提供有加密软件的计算机类型的计算设备，其特征在于其具有能够实现根据权利要求1到7的签名方法的电子组件。
全文摘要
本发明涉及一种用于生成概率的数字签名和/或用于密钥交换协议和/或用于加密算法的密码学方法，所述方法基于在非正态二进制椭圆曲线(E)(科布李兹曲线)上使用公共密钥算法，在所述曲线上选择一个点P(x，y)，存储对(k
文档编号G09C1/00GK1425231SQ0180822
公开日2003年6月18日 申请日期2001年4月18日 优先权日2000年4月18日
发明者J·-S·科伦, C·蒂门 申请人:格姆普拉斯公司
最新回复(0)