密码处理椭圆曲线数据的方法、电子设备及计算机程序的制作方法
密码处理椭圆曲线数据的方法、电子设备及计算机程序的制作方法
【技术领域】
[0001] 本发明涉及密码学，更确切地涉及楠圆曲线密码学。本公开具有大量应用，并且适 用于嵌入式设备中。一般地，本发明可W被应用到基于使用楠圆曲线的所有的密码协议和 算法。
【背景技术】
[0002] 本部分旨在向读者介绍本领域的各方面，该些方面可能与下面所描述和/或所要 求保护的本发明的各个方面有关。相信本讨论有助于向读者提供背景信息，W促进对本发 明的各个方面的更好理解。因此，应当理解，该些陈述就此而被阅读，并非作为对现有技术 的承认。
[0003] 楠圆曲线密码学巧CC)利用与常规的RSA密码系统（次指数安全性）相比更小的 密钥尺寸来提供高水平的安全性（指数安全性）。随着越来越多的人们依赖于小型电子设 备，日常生活中ECC的应用不断增加。较小的密钥尺寸使得ECC对于诸如PDA或智能卡之 类的受限设备具有吸引力。ECC的有效性由被称为标量乘法（或点乘）的操作来控制。问 题在于，给定楠圆曲线（通过有限域或有限环来定义）上的点P和标量k来尽可能在成本 上有效地生成点kP(即，P+…+P化-1次））。该问题明显类似于对功率进行求值。因此，对 功率进行快速求值的方法在此可W被用来获得有效的实现方式。
[0004] 楠圆曲线群操作可定义环中的多个操作来表达。决定性的问题变为W最小化 环操作的数目的方式找出表示楠圆曲线的正确模型。实际上，由于楠圆曲线被定义为双有 理变换化irationaltransformations),因此对于其表示方式存在大量可能的选择。然而， 为了不使坐标和操作的数目激增，实际上只考虑存在于低维空间的楠圆曲线模型。
[0005] 另外，涉及点加公式（即，环加/环减、环乘和环逆（inversion))的基本操作相互 之间不等同。具体地，环逆需要特别关注，因为它可能显著影响整体性能。对于使用楠圆曲 线密码应用，通过在潜在的有限环中的乘法进行的求逆的典型比率范围为3至30。为此，对 无需求逆的点加公式十分感兴趣。该通常通过求助于投影表示（包括广泛使用的齐次坐标 和雅克比（Jacobian)坐标）来实现。
[0006] 使用各种坐标系及其相应代价的许多有用的楠圆曲线形式被编译在由 D. Bernstein等提供的精确公式数据库中，网址为http ;//www. hyperelliptic. org/E抑。
[0007] 当仿射坐标系被用来表示楠圆曲线的点时，当前不存在阻止在有限环中使用求逆 操作的技术。本技术的目的在于在标量乘法的求值中摆脱环逆操作。所提出的技术当然可 W被应用到在点之间只执行基本操作（加法）（如ECDSA算法的校验）的另一上下文中。
【发明内容】
[0008] 本说明书中对"一个实施例"、"实施例"、"示例实施例"的指代指示所描述的实施 例可W包括特定的特征、结构或特性，但每个实施例不一定包括特定的特征、结构或特性。 而且，该样的短语不一定指代相同的实施例。另外，当结合实施例对特定的特征、结构或特 性进行描述时，主张结合其他实施例（无论是否明确描述）来影响该样的特征、结构或特 性，该对于本领域的技术人员而言是熟知的。
[0009] 本发明针对对数据进行密码处理的方法，该方法由电子设备来运行，并且该方法 包括获得属于相同楠圆曲线的至少两个点，每个点由至少两个坐标来表示，其中，所述相同 楠圆曲线被定义在为有限环的代数结构上。该方法的显著之处在于其包括：
[0010] -获得所述楠圆曲线与另一楠圆曲线之间的同构的参数化，所述参数化定义一些 配置参数，每个配置参数具有一系列可能的值；
[0011] -在所述至少两个点的坐标值的函数中确定所述配置参数，递送所确定的配置参 数；
[0012] -通过所述同构获得与所述至少两个点的加法的像相对应的另一点的坐标，所述 另一点属于所述另一楠圆曲线，并且由于所确定的配置参数，执行所述获得不需要在所述 代数结构中的求逆操作。
[0013] 因此，在对同构的参数化的配置参数进行选择的函数中，可能在点的加法中避免 运行求逆操作，在该些点的坐标值的函数中执行选择。应当注意，选择配置参数不是显而易 见的，因为本领域的技术人员对于配置参数习惯使用随机值。
[0014] 在优选实施例中，该方法的显著之处在于；当所述至少两个点相同时，所述加法为 加倍（doubling)操作。
[0015] 在优选实施例中，该方法的显著之处在于；每个点被表示在仿射坐标系中。
[0016] 在优选实施例中，该方法的显著之处在于；该方法通过属于第一楠圆曲线的第一 点被用在标量乘法操作中。
[0017] 在优选实施例中，该方法的显著之处在于；该方法包括将所述标量乘法操作的输 出点（该输出点属于最新的楠圆曲线）转换为属于所述第一楠圆曲线的转换后的输出点。
[0018]因此，所提出的技术不使用当前技术中的求逆操作。它使得能够在楠圆曲线上有 效实现标量乘法。所提出的技术依赖于将曲线同构（isomorphisms)用作避免在点加公式 中计算逆的方式。有趣的是，所提出的技术应用于用来表示楠圆曲线的任何模型，并且应用 于用来表示点的任何坐标系。因此，所提出的技术可W被应用到仿射表示、雅克比表示等。
[0019] 在优选实施例中，该方法的显著之处在于；所述代数结构为具有等于2的特性的 有限域（field)。
[0020] 在优选实施例中，该方法的显著之处在于；所述代数结构为具有等于3的特性的 有限域。
[0021] 在优选实施例中，该方法的显著之处在于；所述代数结构为具有等于素数P> 3的 特性的有限域。
[0022] 根据示例性实现方式，该方法的不同步骤由一个或多个计算机软件程序来实现， 该软件程序包括软件指令，该些软件指令被设计为根据本公开由中继模块的数据处理器来 执行，并且被设计为控制本方法的不同步骤的运行。
[0023] 因此，本公开的一方面还涉及易于由计算机或由数据处理器运行的程序，该程序 包括命令本文上面提到的方法的步骤的运行的指令。
[0024] 该程序可W使用任意编程语言，并且采用源代码、目标代码或介于源代码和目标 代码之间的代码（例如，部分编译的形式或任意其他合适的形式）的形式。
[00巧]本公开还涉及可由数据处理器读取的信息介质，并且该信息介质包括本文上面提 到的程序指令。
[0026] 该信息介质可W是能够存储程序的任意实体或设备。例如，该介质可W包括存储 装置，例如，ROM(表示"只读存储器"）（例如，CD-ROM(表示"压缩盘-只读存储器"）或微 电子电路ROM)或磁记录装置（例如，软盘驱动或硬盘驱动）。
[0027] 另外，该信息介质可W是诸如可W通过电缆或光缆、通过无线电或通过其他装置 来传递的电信号或光信号之类的传播载体。程序可W特别地被下载到互联网式的网络中。
[0028] 替代地，该信息介质可W是集成电路，程序被合并到该集成电路中，该电路适于运 行所讨论的方法或被用在所讨论的方法的运行中。
[0029] 根据一个实施例，本公开的实施例通过软件部件和/或硬件部件的方式来实现。 从该视角，术语"模块"在本文件中可W与软件部件和硬件部件二者相对应，或者与硬件部 件和软件部件的集合相对应。
[0030] 软件部件与一个或多个计算机程序、程序的一个或多个子程序相对应，或者更具 体地与能够根据本文下面针对所涉及的模块进行的描述来实现功能或功能集的程序或软 件程序的任意要素相对应。一个该样的软件部件由物理实体（终端、服务器等）的数据处 理器来运行，并且能够访问该物理实体的硬件资源（存储器、记录介质、通信总线、输入/输 出电子板、用户界面等）。
[0031] 类似地，硬件部件与能够根据本文下面针对所涉及的模块进行的描述来实现功能 或功能集的硬件单元的任意元件相对应。它可W是可编程硬件部件或者是具有用于运行软 件的集成电路（例如，用于运行固件的电子板、集成电路、智能卡、存储器卡等）的部件。在 变体中，硬件部件包括为集成电路的处理器，例如，中央处理单元、和/或微处理器、和/或 专用集成电路（ASI C)、和/或专用指令集处理器（ASI巧、和/或图形处理单元（GPU)、和/或 物理处理单元（PPU)、和/或数字信号处理器值SP)、和/或图像处理器、和/或协处理器、和 /或浮点单元、和/或网络处理器、和/或音频处理器、和/或多核处理器。而且，硬件部件 还可W包括基带处理器（例如包括存储器单元和固件）和/或（可W包括天线的）接收或 发送无线电信号的无线电电子电路。在一个实施例中，硬件部件依从一个或多个标准（例 女口，IS0/IEC18092/ECMA-340、IS(VIEC21481/ECMA-352、GSMA、StoLPaN、ETSI/SCP(智能卡 平台）、GlobalPlat化rm(即，安全元件））。在变体中，硬件部件为射频识别（RFID)标签。 在一个实施例中，硬件部件包括使得能够进行蓝牙通信、和/或Wi-Fi通信、和/或Zigbee 通信、和/或USB通信、和/或固件通信的电路。
[0032] 应当注意，本文件中获得要素/值的步骤可W被看作为在电子设备的存储器单元 中读取该样的要素/值的步骤或者经由通信装置从另一电子设备接收该样的要素/值的步 骤。
[0033] 在另一实施例中，提出被配置为对数据执行密码处理的电子设备，所述电子设备 包括用于获得属于相同楠圆曲线的至少两个点的装置，每个点由至少两个坐标来表示，其 中，所述相同楠圆曲线被定义在为有限环的代数结构上。该电子设备的显著之处在于包 括：
[0034]-用于获得所述楠圆曲线与另一楠圆曲线之间的同构的参数化的装置，所述参数 化定义一些配置参数，每个配置参数具有一系列可能的值；
[00巧]-用于在所述至少两个点的坐标值的函数中确定所述配置参数，递送所确定的配 置参数的装置；W及
[0036]-用于通过所述同构获得与所述至少两个点的加法的像相对应的另一点的坐标的 装置，所述另一点属于所述另一楠圆曲线，并且由于所确定的配置参数，执行所述获得不需 要在所述代数结构中的求逆操作。
[0037] 在变体中，该电子设备的显著之处在于；当所述至少两个点相同时，所述加法为加 倍操作。
[0038] 在变体中，该电子设备的显著之处在于；每个点被表示在仿射坐标系中。
[0039] 在变体中，该电子设备的显著之处在于；所述装置被用来利用属于第一楠圆曲线 的第一点执行标量乘法操作。
[0040] 在变体中，该电子设备的显著之处在于；其包括用于将所述标量乘法操作的输出 点（该输出点属于最新的楠圆曲线）转换为属于所述第一楠圆曲线的转换后的输出点的装 置。
[0041] 在另一实施例中，该电子设备的显著之处在于：所述代数结构为具有等于素数P > 3的特性的有限域。
【附图说明】
[0042] 本发明的W上方面和其他方面将参照附图通过下面对示例性实施例的详细描述 变得更加显然，其中：
[0043]-图1根据本发明的一个实施例展示了楠圆曲线上的标量乘法；
[0044]-图2展示了用于在楠圆曲线上执行标量乘法的两个经典的方法（加倍和相加方 法，W及相加和加倍方法）；
[0045]-图3根据本技术展示了用于在楠圆曲线上执行标量乘法的两个方法；
[0046]-图4根据本技术展示了用于在楠圆曲线上执行标量乘法的方法的另一实施例；
[0047]-图5展示了用于在楠圆曲线上执行标量乘法的两个经典的方法（蒙哥马利梯 (Montgomeirladder)、W及乔伊的加倍相加梯Qoye'Sdouble-addladder));
[0048]-图6根据本发明的一个实施例，展示了图5中所公开的用于在楠圆曲线上执行标 量乘法的方法的两个修改；
[0049] -图7根据本发明的一个实施例，展示了图5中所公开的用于在楠圆曲线上执行标 量乘法的蒙哥马利梯方法的修改；
[0050]-图8展示了可W被用来执行本文件所公开的方法的一个或多个步骤的设备。
【具体实施方式】
[0051] 在完整地描述所提出的方法之前，首先对维尔斯特拉斯（Weierstra目）模型做个 评论。为简化阐述，我们关注通过具有与2或3不同的特性的环而定义的楠圆曲线。按照 惯例，我们让胺*来表示时的乘法群，让Char(K)来表示:国的特性。
[005引考虑环松上的楠因曲线El,Qiar(M.)声2, 3,给出
[0053] Ei;y 2= x3+a ? x+b
[0054]对于任意we肢％楠圆曲线El为喃同构楠圆曲线
[00巧]Eu;y2=X3+a?u* ?x+b?u?
[005引 经由逆映射
[0057]
[005引给定El上两个有限点Pi= (Xi，yi)和P2= (X2，y2)，W使得Pi声±?2(即，W使得Xl声X2)，假设佑-如G胶％其和由Ps=Pi+P2= (X3，y3)给出，其中，
[0059]
(方程式1)
[0060] 假叛於GK*，Pi=(Xi，yi)的加倍（double)由P4= 2P1=Pi+Pi= (x"y4)给出， 其中
[006。
（方程式。
[0062] 在本发明的一个实施例中，本技术使用^下属性；通过定义<5?二％ -^2，我们从 上面的加法方程式公式（参照方程式1)中得到
[0063]
[0064] 换言之，给定楠圆曲线El上的点P1和P2,便可W在同构的楠圆曲线馬上容易地获 得点？3=斬(Pl+P2)=如2鮮麥3仍）。值得注意的是，在对：?3的求值中无需求逆。我们 让iA孤来表示获得e馬的操作。
[0065] 应当注意，类似的处理应用到点加倍操作中（加倍操作可W被看作两个相同的点 之间的特殊加法。然而，无论点是否相等，用来执行加法的公式不一定相同）。现在定义 與：=2化，我们从加倍公式（参照方程式2)得出
[0067]也就是说，给定El上的点P1，便可W容易地获得点P* =如P口Pi)= 如2X4，<P3y4)，该点属于楠圆曲线。至于点加，值得注意的是，在对节4的求值中无需求 逆。我们让iD化来表示获得e￡"<^做操作。
[006引让环:K上的楠圆曲线。考虑同构楠圆曲线族^{e?}，在如下同构下，该同构楠 圆曲线族由参数I;来索引
[0069] 咕本.巨1 一E寺
[0070] 参数I为同构的描述（description)(目P，定义同构的参数化）。我们使用符号 | =Desc(i/'i石）值esc为描述（description)的缩写）。所有可能的参数I的集合被标记为 巧。
[0071] 下面的H个加法操作（标记为iADD、iADDU和iADDC)通过如下方程式来定义：
[0072]
[0073] 出于效率的目的，选择参数:和W使得给定卸上的两个不同的点Pi和P2,加法操 作的输出不需要环逆。
[0074] 我们还给出两个加倍操作iD化和iDBLU，它们由如下方程式来定义：
[00巧]
[007引同样，选择参数多，W使得给定属于-却的点Pi，加倍操作的输出无需环逆。
[0077] 更一般地，给定同构于町的两个楠圆曲线％和％,，如果斬二与7.表示楠圆 曲线E否和E私之间的同构，则我们类似地定义操作
[0078]
[0079] 运算符定义中的下标I;指示输入点属于楠圆曲线E否。
[0080] 下面的示例说明原理。对于在环眩J：定义（无论什么特性）的一般的Weierstra目 模型，我们有
[0081] 丘i:y2 + 牛 =X3 牛 〇2乂2 + + 〇6，其中，参数a!，a],a],a*和 ae属于胚，并且 '皆矿￡歹一E兩:具有'(x,y) +r,w3y+ ^2就+t),其中，同构 的描述帘由四个参数u，r，s和t来给出。因此，豕=(M,r,s,〇，并且1 = (1,〇,〇斯。 我们还有：F= {(u,/〇',ne胺4|Ue胺* }，其中，岐是而的定义环。因此，同构 斬使得％y2 + =X3 + 〇2X2 + 〇4乂 + 〇6的点P能够向属于楠圆曲线
的点进行映射，其中，参 数a'1，a'2，a'3,a'4和a'e属于肢。相应的曲线参数与如下方程式有关：
[0087] 当阻的特性不为2或3时，便可W不失一般性地选择ai=a2=a3=0。同样，当 KI的特性为2时，假设楠圆曲线为非超奇异，便可W选择ai= 1和33= 34= 0。
[0088] 在W下部分中，采用根据较短的Weierstra目模型而定义的楠圆曲线，在具有不 等于2或3的特性的环上，给出要执行的用于获得运算符iA孤、iA孤U、iA孤C、iD化和iDBLU 的输出精确计算。
[008引更准确地，从点P郝P2(点Pi和P2属于在具有不等于2或3的特性的环 监_上定义的楠圆曲线而y2 =X3 +a?X+ 6 (根据较短的Weierstra目模型））对 而=巧，尉=知(P1+P2)=如2抑扣仍)进行求值可W按照如下来完成：
[0090]-获得胚中的取=A-X2;
[0091]-获得胺中的C=與2;
[009引-获得肢中的Wi= X iC ;
[009引-获得胺中的胖2=XsC;
[0094] -获得肢I中的D = (yi_y2)2;
[0095]-获得啦中的Ai= (Wi-W2)yi;
[009引然后，肠1中的巧=D - 和肢中妳巧=(Wi -巧(仍-扔）-矣。
[0097] 该系列操作与iADD操作相对应，iADD操作具有4M+2S的总成本，其中，M和S分别 表示:肢中乘法的成本和平方的成本。
[0098] 应当注意，在对乎3:进行求值的过程中免费获得町二巧'，究）=如，(Pi)二 如2知护扔）。实际上，我们立即得到町=(巧，巧，其中，巧=，并且巧=^1。
[0099] 如前所述，与;Pi-起获得梦3的操作被标记为iA孤U。
[0100]从点Pi和P2 (点Pi和P2属于在具有不等于2或3的特性的有限环:松上定义的楠 圆曲线
进行 求值可W按照如下来完成：
[OW]-获得防中的Wi=XiC;
[010引-获得K中的胖2=XsC;
[0103]-获得啦中的Ai=师1-胖2化；
[0104]然后，胶中的'x'3 =(y!+仍)2- - Wz和肢中的y'3 = (Wi-X'3)(Yi + Yz)- i4玉。
[010引实际上，由于斗2=(X2,-y2)，因此，口1斗2= (X' 3，y' 3)满足
因此，被 标记为iA孤C的获取.皆-f*2)帕操作只需要5M+3S。
[0106] 从点Pi(点Pi属于在具有不等于2或3的特性的有限环上定义的楠圆曲线
进行求值可W按照如下来完成：
[0107]-获得肢中的B=xi2;
[010引-获得胶中的E=yi2;
[0109]-获得肢中的L=E2;
[0110]-获得带中的M= 3B+a;
[01川-获得胚中的S= 2((xi+巧2-B-L);
[011引然后，胚中的巧=M2- 2S和胺i中脚；r* =MCS-巧-8L
[om] 对P4 =拓，巧进行求值被标记为iDBL，并且该样的操作只需要1M+5S。而且，在 对梦4慨求值过程中免费获得町=(巧，沉）=斬(Pi)。实际上，我们有'巧=义和巧=8L。 包括获得W及Pi的操作被标记为iDBLU，如前所述。
[0114] 使用楠圆曲线的密码方案中最常用的操作之一为标量乘法。
[0115] 图1根据本发明的一个实施例展示了楠圆曲线上的标量乘法。
[0116] 更准确地，标量乘法包括通过使用在标量乘法处理的过程中确定的同构链或一系 列同构来使用加倍和相加操作。
[0117] 在步骤1处，让E(g) = ￡V表示原始的楠圆曲线，让EW= ￡;,表示当 前的楠圆曲线，并且让￡南W表示最终的楠圆曲线，我们有PeE?和
[om] 步骤i处的当前曲线和原始曲线之间的同构由如i=斬i° 斬1给出。稍微调 整符号，我们还可W使用符号。来表示相应描述上的操作，即Desc(^^i)=薪。…。巧1。 由于
，结果点Q二k.PEE由Q= 二1伯）给 出。"组成的"（composed)同构兩W可W通过观察峰&=咕兩。少否来迭代获得，其 中，的。=M(即，身份映射K由于成=Desc(班南)，我们得到系=焉。禹_1，其中， 批,二Dcsc(W) := 1。
[0119]W下示例说明该样的原理。对于一般的Weierstra目模型，我们有
[0120]
[012引其中，氣-，二.!a'_1,7^)、知=如并且 1 二CM),0,0)。因 此，方程式少'，=捉。最'_1转换为扣i，Ri，Si,Ti)=相，心Si,ti)。扣而_1，Sh,Ty)，其 中，
[0124]
[012引i> 1，并且扣0，R0,S0，T0) = (1，0,0,0)。
[0126] 图2展示了用于在楠圆曲线上执行标量乘法的两个经典的方法（加倍和相加方 法，W及相加和加倍方法）。
[0127] 用于对Q=kP求值（即，楠圆曲线上的标量乘法）的经典方法考虑标量k的二进 制表示1^=化。_1，...，1〇2，其中，1^1￡{0，1}，0《1《11-1。有利地，该方法需要较少数目 的寄存器，因此较好地适于如智能卡之类的存储器受限设备。该方法依赖于如下显然的关 系；如果k是偶数，则fcP= 2(lk/2j/〇,如果k是奇数，则2如/引巧+P。对该处理 进行迭代得到左到右标量乘法算法，被称为加倍和相加方法。该样的方法需要两个（点） 寄存器R。和R1。寄存器R。作为累加器，而寄存器R1被用来存储输入点P的值。
[012引存在右到左变体。结果算法（被称为相加和加倍方法）在图2的算法2中进行描 绘。该方法也需要两个（点）寄存器R。和Ri，但在该情形中，该两个寄存器均作为累加器。
[0129]图3根据本技术展示了用于在楠圆曲线上执行标量乘法的两个方法。
[0130] 更准确地，图3中所展示的算法或方法是根据本发明的一个实施例利用相加和加 倍公式对经典方法的直接实现方式。我们利用原始曲线使用变量多> 来累加当前同构[的描 述]。该变量被初始化为= 1 (与身份映射Id相对应）。如前所述，符号。表示楠圆曲 线同构[的描述]的组成。
[0131]图4根据本技术展示了用于在楠圆曲线上执行标量乘法的方法的另一实施例。
[0132] 该样的实施例是左到右方法的变体，该变体比图3中所描绘的方法更加有效。需 要注意，当ki等于1时，寄存器R1被加到寄存器R。，并且寄存器Ri的内容在整个计算过程 中保持不变化1总是包含输入点P)，则没必要不断地将其更新为当前楠圆曲线上的点。实 际上，在迭代i处，其在当前楠圆曲线（E京）上的表示可W从输入点P作为呼如巧来计算。
[0133] 图5展示了用于在楠圆曲线上执行标量乘法的两个经典的方法（蒙哥马利梯、W 及乔伊的加倍相加梯）。
[0134] 为了存储一些操作结果，该些经典的方法使用H个寄存器（寄存器R。、寄存器Ri和 寄存器T)。
[0135] 图6根据本发明的一个实施例，展示了图5中所公开的用于在楠圆曲线上执行标 量乘法的方法的两个修改。
[0136] 对于若干个楠圆曲线模型，两个不同点的点加公式独立于曲线参数。在该情形中， 有趣的是，依赖于可W被写作一系列iADDU和iADDC操作的标量乘法算法。
[0137] 算法6的主循环为Ri_b-Rb+Ri_^Rb^ 2Rb(其中，b等于0或1)，对于算法7， 为而_6^1^+21?^因此，算法6和算法7可^很容易地适于本文件所提出的新的操作。值 kw= 1导致巧。，T) = (P，P)，并且然后导致算法6的第一次迭代中的Ri=P+P。最后的 操作是点加倍。为了不必处理潜在的特殊情形，我们假设kw= 1，因此在i=n-2处开始 for循环，并且将巧。，而）初始化为（P，2巧。对于更好的性能，该归功于iDBLU操作而实现。 出于相同的原因，我们在右到左算法中假设k。= 1。在算法9中，我们在i= 2处开始化r 循环，并且将初始化为（P，3巧。再次 ，该可W利用新的操作来完成。当k?=0 时，需要在计算的结尾处减去点PW获得正确的结果。
[013引图7根据本发明的一个实施例，展示了图5中所公开的用于在楠圆曲线上执行标 量乘法的蒙哥马利梯方法的修改。
[0139] 原始的蒙哥马利梯使得Ri-R。的差值保持不变，该差值等于P。等同地，算法6中的 变量^^咕-!?^)等于（-l)wp。因此，在迭代1 =〇处，在我们的蒙哥马利梯的版本（算 法8)中的变量Rb在第4行处包含值
该可W允许精确恢复聲衣，W的描 述，因此皆^的描述为
。因此，我们可W获 得不需要跟踪当前同构的类蒙哥马利算法；iADDC和iADDU操作只需要返回点，不需要结果 曲线的同构的描述（即，参数廣）。该由运算符上的符号'来指示。蒙哥马利梯的该变体还 需要iADDC和iADDU操作独立于曲线参数；该由运算符中缺少下标来指示。
[0140] 图8展示了可W被用来执行本文件所公开的方法（或算法）的一个或多个步骤的 设备。
[0141] 该样的设备（参考800)包括计算单元（例如，CPU,为"中央处理单元"）（参考 801) W及一个或多个存储器单元（例如，RAM("随机存取存储器"）框，在运行计算机程序 指令的过程中，中间结果可W被临时存储于该RAM框中；或者ROM框，特别是计算机程序被 存储于该ROM框中；或者EEPR0M("电可擦除可编程只读存储器"）框；或者闪存框）（参考 802) 。计算机程序由可W由计算单元来运行的指令组成。该样的设备800还可W包括专用 单元（参考803)，该专用单元包括允许设备800与其他设备进行通信的输入-输出接口。 具体地，该专用单元803可W与天线相连接（为了执行无接触的通信），或者与串行端口相 连接（W承载通信"接触"）。应当注意，图8中的箭头意味着所链接的单元可W通过总线 例如一起来交换数据。
[0142] 在替代的实施例中，前面所描述的方法中的一些步骤或全部步骤可硬件形式 被实现在可编程FPGA("现场可编程口阵列"）部件或ASIC("专用集成电路"）部件中。
[0143] 在替代的实施例中，前面所描述的方法中的一些步骤或全部步骤可W在包括图8 中所公开的存储器单元和处理单元的电子设备上被运行。
[0144] 对于某些模型（包括通用的Weierstra目模型），中立要素（即，无穷远点0)需要 特殊处理。该可W通过适当地修改初始化步骤来避免。对于经典的左到右梯，假设kw= 1，我们可^在i=n-2处开始for循环，并且在算法3和5中在初始化步骤中设置P 和Ri^P。
[0145] 类似地，对于右到左梯，假设ku= 1，我们可W在i= 1处开始for循环，并且在算 法4中设置R。一P和R2.P。当k。= 0时，我们做法相同，但在计算的结尾处减去P来 获得正确的结果。
[0146] 应当注意，对于组合的操作（例如，R= 2.P+Q的求值），可W根据本技术来完成。 该可^采用两个步骤来完成，首先确定T^P+Q，然后确定R^P+T。如果同时需要点R与 更新后的点P，则该可W利用两个连续的iADDU操作的应用来实施：
[0147]
[0148] 如果我们希望在计算的结尾处同时获得点R与更新后的点Q(而不是点巧，则事情 会稍微复杂。该可W通过对iA孤U进行求值并且之后对iA孤C进行求值来实施：
[0149]
[0150] 最后，应当注意，基于同构楠圆曲线所提出的技术遵从在每次运行该技术时防止 旁路攻击（例如，曲线随机化）的技术。
【主权项】
1. 一种对数据进行密码处理的方法，所述方法由电子设备来运行，并且所述方法包括 获得属于相同椭圆曲线的至少两个点，每个点由至少两个坐标来表示，其中，所述相同椭圆 曲线被定义在为有限环的代数结构上，所述方法的特征在于其包括： -获得所述椭圆曲线与另一椭圆曲线之间的同构的参数化，所述参数化定义一些配置 参数，每个配置参数具有一系列可能的值； -确定作为所述至少两个点的坐标值的函数的所述配置参数，递送所确定的配置参 数； -通过所述同构获得与所述至少两个点的加法的像相对应的另一点的坐标，所述另一 点属于所述另一椭圆曲线，并且由于所述所确定的配置参数，执行所述获得不需要在所述 代数结构中的求逆操作。2. 如权利要求1所述的方法，其特征在于：当所述至少两个点相同时，所述加法为加倍 操作。3. 如权利要求1至2中任一权利要求所述的方法，其特征在于：每个点被表示在仿射 坐标系中。4. 如权利要求1至3中任一权利要求所述的方法，其特征在于：所述方法通过属于第 一椭圆曲线的第一点被用在标量乘法操作中。5. 如权利要求4所述的方法，其特征在于：所述方法包括将所述标量乘法操作的输出 点转换为属于所述第一椭圆曲线的转换后的输出点，所述标量乘法操作的所述输出点属于 最新的椭圆曲线。6. 如权利要求1至5中任一权利要求所述的方法，其特征在于：所述代数结构为具有 等于2的特性的有限域。7. 如权利要求1至5中任一权利要求所述的方法，其特征在于：所述代数结构为具有 等于3的特性的有限域。8. 如权利要求1至5中任一权利要求所述的方法，其特征在于：所述代数结构为具有 等于素数P> 3的特性的有限域。9. 一种计算机可读且非暂态存储介质，所述计算机可读且非暂态存储介质存储包括计 算机可执行指令的集合的计算机程序，从而当所述指令被计算机运行时，实现用于密码计 算的方法，其中，所述指令包括当被运行时将所述计算机配置为执行权利要求1至8所述的 方法的指令。10. -种被配置为对数据执行密码处理的电子设备，所述电子设备包括用于获得属于 相同椭圆曲线的至少两个点的装置，每个点由至少两个坐标来表示，其中，所述相同椭圆曲 线被定义在为有限环的代数结构上，所述电子设备的特征在于其包括： _用于获得所述椭圆曲线与另一椭圆曲线之间的同构的参数化的装置，所述参数化定 义一些配置参数，每个配置参数具有一系列可能的值； -用于确定作为所述至少两个点的坐标值的函数的所述配置参数，递送所确定的配置 参数的装置；以及 -用于通过所述同构获得与所述至少两个点的加法的像相对应的另一点的坐标的装 置，所述另一点属于所述另一椭圆曲线，并且由于所述所确定的配置参数，执行所述获得不 需要在所述代数结构中的求逆操作。11. 如权利要求10所述的电子设备，其特征在于：当所述至少两个点相同时，所述加法 为加倍操作。12. 如权利要求10至11中任一权利要求所述的电子设备，其特征在于：每个点被表示 在仿射坐标系中。13. 如权利要求10至12中任一权利要求所述的电子设备，其特征在于：所述装置被用 来利用属于第一椭圆曲线的第一点来执行标量乘法操作。14. 如权利要求13所述的电子设备，其特征在于：所述电子设备包括用于将所述标量 乘法操作的输出点转换为属于所述第一椭圆曲线的转换后的输出点的装置，其中，所述标 量乘法操作的所述输出点属于最新的椭圆曲线。15. 如权利要求10至14中任一权利要求所述的电子设备，其特征在于：所述代数结构 为具有等于素数P> 3的特性的有限域。
【专利摘要】本发明涉及密码处理椭圆曲线数据的方法、电子设备及计算机程序。提出了对数据进行密码处理的方法，该方法由电子设备来运行，并且该方法包括获得属于被定义在为有限环的代数结构上的相同椭圆曲线的至少两个点，每个点由至少两个坐标来表示。该方法的特征在于，包括：获得所述椭圆曲线与另一椭圆曲线之间的同构的参数化，参数化定义一些配置参数，每个配置参数具有一系列可能的值；在至少两个点的坐标值的函数中确定配置参数，递送所确定的配置参数；以及通过同构获得与至少两个点的加法的像相对应的另一点的坐标，另一点属于另一椭圆曲线，并且由于所确定的配置参数，执行所述获得不需要在代数结构中的求逆操作。
【IPC分类】H04L9/06
【公开号】CN104901792
【申请号】CN201510093017
【发明人】马克·乔伊, 拉文·贡德尔
【申请人】汤姆逊许可公司
【公开日】2015年9月9日
【申请日】2015年3月2日
【公告号】EP2916215A1, EP2916216A1, US20150256340
【技术领域】
[0001] 本发明涉及密码学，更确切地涉及楠圆曲线密码学。本公开具有大量应用，并且适 用于嵌入式设备中。一般地，本发明可W被应用到基于使用楠圆曲线的所有的密码协议和 算法。
【背景技术】
[0002] 本部分旨在向读者介绍本领域的各方面，该些方面可能与下面所描述和/或所要 求保护的本发明的各个方面有关。相信本讨论有助于向读者提供背景信息，W促进对本发 明的各个方面的更好理解。因此，应当理解，该些陈述就此而被阅读，并非作为对现有技术 的承认。
[0003] 楠圆曲线密码学巧CC)利用与常规的RSA密码系统（次指数安全性）相比更小的 密钥尺寸来提供高水平的安全性（指数安全性）。随着越来越多的人们依赖于小型电子设 备，日常生活中ECC的应用不断增加。较小的密钥尺寸使得ECC对于诸如PDA或智能卡之 类的受限设备具有吸引力。ECC的有效性由被称为标量乘法（或点乘）的操作来控制。问 题在于，给定楠圆曲线（通过有限域或有限环来定义）上的点P和标量k来尽可能在成本 上有效地生成点kP(即，P+…+P化-1次））。该问题明显类似于对功率进行求值。因此，对 功率进行快速求值的方法在此可W被用来获得有效的实现方式。
[0004] 楠圆曲线群操作可定义环中的多个操作来表达。决定性的问题变为W最小化 环操作的数目的方式找出表示楠圆曲线的正确模型。实际上，由于楠圆曲线被定义为双有 理变换化irationaltransformations),因此对于其表示方式存在大量可能的选择。然而， 为了不使坐标和操作的数目激增，实际上只考虑存在于低维空间的楠圆曲线模型。
[0005] 另外，涉及点加公式（即，环加/环减、环乘和环逆（inversion))的基本操作相互 之间不等同。具体地，环逆需要特别关注，因为它可能显著影响整体性能。对于使用楠圆曲 线密码应用，通过在潜在的有限环中的乘法进行的求逆的典型比率范围为3至30。为此，对 无需求逆的点加公式十分感兴趣。该通常通过求助于投影表示（包括广泛使用的齐次坐标 和雅克比（Jacobian)坐标）来实现。
[0006] 使用各种坐标系及其相应代价的许多有用的楠圆曲线形式被编译在由 D. Bernstein等提供的精确公式数据库中，网址为http ;//www. hyperelliptic. org/E抑。
[0007] 当仿射坐标系被用来表示楠圆曲线的点时，当前不存在阻止在有限环中使用求逆 操作的技术。本技术的目的在于在标量乘法的求值中摆脱环逆操作。所提出的技术当然可 W被应用到在点之间只执行基本操作（加法）（如ECDSA算法的校验）的另一上下文中。
【发明内容】
[0008] 本说明书中对"一个实施例"、"实施例"、"示例实施例"的指代指示所描述的实施 例可W包括特定的特征、结构或特性，但每个实施例不一定包括特定的特征、结构或特性。 而且，该样的短语不一定指代相同的实施例。另外，当结合实施例对特定的特征、结构或特 性进行描述时，主张结合其他实施例（无论是否明确描述）来影响该样的特征、结构或特 性，该对于本领域的技术人员而言是熟知的。
[0009] 本发明针对对数据进行密码处理的方法，该方法由电子设备来运行，并且该方法 包括获得属于相同楠圆曲线的至少两个点，每个点由至少两个坐标来表示，其中，所述相同 楠圆曲线被定义在为有限环的代数结构上。该方法的显著之处在于其包括：
[0010] -获得所述楠圆曲线与另一楠圆曲线之间的同构的参数化，所述参数化定义一些 配置参数，每个配置参数具有一系列可能的值；
[0011] -在所述至少两个点的坐标值的函数中确定所述配置参数，递送所确定的配置参 数；
[0012] -通过所述同构获得与所述至少两个点的加法的像相对应的另一点的坐标，所述 另一点属于所述另一楠圆曲线，并且由于所确定的配置参数，执行所述获得不需要在所述 代数结构中的求逆操作。
[0013] 因此，在对同构的参数化的配置参数进行选择的函数中，可能在点的加法中避免 运行求逆操作，在该些点的坐标值的函数中执行选择。应当注意，选择配置参数不是显而易 见的，因为本领域的技术人员对于配置参数习惯使用随机值。
[0014] 在优选实施例中，该方法的显著之处在于；当所述至少两个点相同时，所述加法为 加倍（doubling)操作。
[0015] 在优选实施例中，该方法的显著之处在于；每个点被表示在仿射坐标系中。
[0016] 在优选实施例中，该方法的显著之处在于；该方法通过属于第一楠圆曲线的第一 点被用在标量乘法操作中。
[0017] 在优选实施例中，该方法的显著之处在于；该方法包括将所述标量乘法操作的输 出点（该输出点属于最新的楠圆曲线）转换为属于所述第一楠圆曲线的转换后的输出点。
[0018]因此，所提出的技术不使用当前技术中的求逆操作。它使得能够在楠圆曲线上有 效实现标量乘法。所提出的技术依赖于将曲线同构（isomorphisms)用作避免在点加公式 中计算逆的方式。有趣的是，所提出的技术应用于用来表示楠圆曲线的任何模型，并且应用 于用来表示点的任何坐标系。因此，所提出的技术可W被应用到仿射表示、雅克比表示等。
[0019] 在优选实施例中，该方法的显著之处在于；所述代数结构为具有等于2的特性的 有限域（field)。
[0020] 在优选实施例中，该方法的显著之处在于；所述代数结构为具有等于3的特性的 有限域。
[0021] 在优选实施例中，该方法的显著之处在于；所述代数结构为具有等于素数P> 3的 特性的有限域。
[0022] 根据示例性实现方式，该方法的不同步骤由一个或多个计算机软件程序来实现， 该软件程序包括软件指令，该些软件指令被设计为根据本公开由中继模块的数据处理器来 执行，并且被设计为控制本方法的不同步骤的运行。
[0023] 因此，本公开的一方面还涉及易于由计算机或由数据处理器运行的程序，该程序 包括命令本文上面提到的方法的步骤的运行的指令。
[0024] 该程序可W使用任意编程语言，并且采用源代码、目标代码或介于源代码和目标 代码之间的代码（例如，部分编译的形式或任意其他合适的形式）的形式。
[00巧]本公开还涉及可由数据处理器读取的信息介质，并且该信息介质包括本文上面提 到的程序指令。
[0026] 该信息介质可W是能够存储程序的任意实体或设备。例如，该介质可W包括存储 装置，例如，ROM(表示"只读存储器"）（例如，CD-ROM(表示"压缩盘-只读存储器"）或微 电子电路ROM)或磁记录装置（例如，软盘驱动或硬盘驱动）。
[0027] 另外，该信息介质可W是诸如可W通过电缆或光缆、通过无线电或通过其他装置 来传递的电信号或光信号之类的传播载体。程序可W特别地被下载到互联网式的网络中。
[0028] 替代地，该信息介质可W是集成电路，程序被合并到该集成电路中，该电路适于运 行所讨论的方法或被用在所讨论的方法的运行中。
[0029] 根据一个实施例，本公开的实施例通过软件部件和/或硬件部件的方式来实现。 从该视角，术语"模块"在本文件中可W与软件部件和硬件部件二者相对应，或者与硬件部 件和软件部件的集合相对应。
[0030] 软件部件与一个或多个计算机程序、程序的一个或多个子程序相对应，或者更具 体地与能够根据本文下面针对所涉及的模块进行的描述来实现功能或功能集的程序或软 件程序的任意要素相对应。一个该样的软件部件由物理实体（终端、服务器等）的数据处 理器来运行，并且能够访问该物理实体的硬件资源（存储器、记录介质、通信总线、输入/输 出电子板、用户界面等）。
[0031] 类似地，硬件部件与能够根据本文下面针对所涉及的模块进行的描述来实现功能 或功能集的硬件单元的任意元件相对应。它可W是可编程硬件部件或者是具有用于运行软 件的集成电路（例如，用于运行固件的电子板、集成电路、智能卡、存储器卡等）的部件。在 变体中，硬件部件包括为集成电路的处理器，例如，中央处理单元、和/或微处理器、和/或 专用集成电路（ASI C)、和/或专用指令集处理器（ASI巧、和/或图形处理单元（GPU)、和/或 物理处理单元（PPU)、和/或数字信号处理器值SP)、和/或图像处理器、和/或协处理器、和 /或浮点单元、和/或网络处理器、和/或音频处理器、和/或多核处理器。而且，硬件部件 还可W包括基带处理器（例如包括存储器单元和固件）和/或（可W包括天线的）接收或 发送无线电信号的无线电电子电路。在一个实施例中，硬件部件依从一个或多个标准（例 女口，IS0/IEC18092/ECMA-340、IS(VIEC21481/ECMA-352、GSMA、StoLPaN、ETSI/SCP(智能卡 平台）、GlobalPlat化rm(即，安全元件））。在变体中，硬件部件为射频识别（RFID)标签。 在一个实施例中，硬件部件包括使得能够进行蓝牙通信、和/或Wi-Fi通信、和/或Zigbee 通信、和/或USB通信、和/或固件通信的电路。
[0032] 应当注意，本文件中获得要素/值的步骤可W被看作为在电子设备的存储器单元 中读取该样的要素/值的步骤或者经由通信装置从另一电子设备接收该样的要素/值的步 骤。
[0033] 在另一实施例中，提出被配置为对数据执行密码处理的电子设备，所述电子设备 包括用于获得属于相同楠圆曲线的至少两个点的装置，每个点由至少两个坐标来表示，其 中，所述相同楠圆曲线被定义在为有限环的代数结构上。该电子设备的显著之处在于包 括：
[0034]-用于获得所述楠圆曲线与另一楠圆曲线之间的同构的参数化的装置，所述参数 化定义一些配置参数，每个配置参数具有一系列可能的值；
[00巧]-用于在所述至少两个点的坐标值的函数中确定所述配置参数，递送所确定的配 置参数的装置；W及
[0036]-用于通过所述同构获得与所述至少两个点的加法的像相对应的另一点的坐标的 装置，所述另一点属于所述另一楠圆曲线，并且由于所确定的配置参数，执行所述获得不需 要在所述代数结构中的求逆操作。
[0037] 在变体中，该电子设备的显著之处在于；当所述至少两个点相同时，所述加法为加 倍操作。
[0038] 在变体中，该电子设备的显著之处在于；每个点被表示在仿射坐标系中。
[0039] 在变体中，该电子设备的显著之处在于；所述装置被用来利用属于第一楠圆曲线 的第一点执行标量乘法操作。
[0040] 在变体中，该电子设备的显著之处在于；其包括用于将所述标量乘法操作的输出 点（该输出点属于最新的楠圆曲线）转换为属于所述第一楠圆曲线的转换后的输出点的装 置。
[0041] 在另一实施例中，该电子设备的显著之处在于：所述代数结构为具有等于素数P > 3的特性的有限域。
【附图说明】
[0042] 本发明的W上方面和其他方面将参照附图通过下面对示例性实施例的详细描述 变得更加显然，其中：
[0043]-图1根据本发明的一个实施例展示了楠圆曲线上的标量乘法；
[0044]-图2展示了用于在楠圆曲线上执行标量乘法的两个经典的方法（加倍和相加方 法，W及相加和加倍方法）；
[0045]-图3根据本技术展示了用于在楠圆曲线上执行标量乘法的两个方法；
[0046]-图4根据本技术展示了用于在楠圆曲线上执行标量乘法的方法的另一实施例；
[0047]-图5展示了用于在楠圆曲线上执行标量乘法的两个经典的方法（蒙哥马利梯 (Montgomeirladder)、W及乔伊的加倍相加梯Qoye'Sdouble-addladder));
[0048]-图6根据本发明的一个实施例，展示了图5中所公开的用于在楠圆曲线上执行标 量乘法的方法的两个修改；
[0049] -图7根据本发明的一个实施例，展示了图5中所公开的用于在楠圆曲线上执行标 量乘法的蒙哥马利梯方法的修改；
[0050]-图8展示了可W被用来执行本文件所公开的方法的一个或多个步骤的设备。
【具体实施方式】
[0051] 在完整地描述所提出的方法之前，首先对维尔斯特拉斯（Weierstra目）模型做个 评论。为简化阐述，我们关注通过具有与2或3不同的特性的环而定义的楠圆曲线。按照 惯例，我们让胺*来表示时的乘法群，让Char(K)来表示:国的特性。
[005引考虑环松上的楠因曲线El,Qiar(M.)声2, 3,给出
[0053] Ei;y 2= x3+a ? x+b
[0054]对于任意we肢％楠圆曲线El为喃同构楠圆曲线
[00巧]Eu;y2=X3+a?u* ?x+b?u?
[005引 经由逆映射
[0057]
[005引给定El上两个有限点Pi= (Xi，yi)和P2= (X2，y2)，W使得Pi声±?2(即，W使得Xl声X2)，假设佑-如G胶％其和由Ps=Pi+P2= (X3，y3)给出，其中，
[0059]
(方程式1)
[0060] 假叛於GK*，Pi=(Xi，yi)的加倍（double)由P4= 2P1=Pi+Pi= (x"y4)给出， 其中
[006。
（方程式。
[0062] 在本发明的一个实施例中，本技术使用^下属性；通过定义<5?二％ -^2，我们从 上面的加法方程式公式（参照方程式1)中得到
[0063]
[0064] 换言之，给定楠圆曲线El上的点P1和P2,便可W在同构的楠圆曲线馬上容易地获 得点？3=斬(Pl+P2)=如2鮮麥3仍）。值得注意的是，在对：?3的求值中无需求逆。我们 让iA孤来表示获得e馬的操作。
[0065] 应当注意，类似的处理应用到点加倍操作中（加倍操作可W被看作两个相同的点 之间的特殊加法。然而，无论点是否相等，用来执行加法的公式不一定相同）。现在定义 與：=2化，我们从加倍公式（参照方程式2)得出
[0067]也就是说，给定El上的点P1，便可W容易地获得点P* =如P口Pi)= 如2X4，<P3y4)，该点属于楠圆曲线。至于点加，值得注意的是，在对节4的求值中无需求 逆。我们让iD化来表示获得e￡"<^做操作。
[006引让环:K上的楠圆曲线。考虑同构楠圆曲线族^{e?}，在如下同构下，该同构楠 圆曲线族由参数I;来索引
[0069] 咕本.巨1 一E寺
[0070] 参数I为同构的描述（description)(目P，定义同构的参数化）。我们使用符号 | =Desc(i/'i石）值esc为描述（description)的缩写）。所有可能的参数I的集合被标记为 巧。
[0071] 下面的H个加法操作（标记为iADD、iADDU和iADDC)通过如下方程式来定义：
[0072]
[0073] 出于效率的目的，选择参数:和W使得给定卸上的两个不同的点Pi和P2,加法操 作的输出不需要环逆。
[0074] 我们还给出两个加倍操作iD化和iDBLU，它们由如下方程式来定义：
[00巧]
[007引同样，选择参数多，W使得给定属于-却的点Pi，加倍操作的输出无需环逆。
[0077] 更一般地，给定同构于町的两个楠圆曲线％和％,，如果斬二与7.表示楠圆 曲线E否和E私之间的同构，则我们类似地定义操作
[0078]
[0079] 运算符定义中的下标I;指示输入点属于楠圆曲线E否。
[0080] 下面的示例说明原理。对于在环眩J：定义（无论什么特性）的一般的Weierstra目 模型，我们有
[0081] 丘i:y2 + 牛 =X3 牛 〇2乂2 + + 〇6，其中，参数a!，a],a],a*和 ae属于胚，并且 '皆矿￡歹一E兩:具有'(x,y) +r,w3y+ ^2就+t),其中，同构 的描述帘由四个参数u，r，s和t来给出。因此，豕=(M,r,s,〇，并且1 = (1,〇,〇斯。 我们还有：F= {(u,/〇',ne胺4|Ue胺* }，其中，岐是而的定义环。因此，同构 斬使得％y2 + =X3 + 〇2X2 + 〇4乂 + 〇6的点P能够向属于楠圆曲线
的点进行映射，其中，参 数a'1，a'2，a'3,a'4和a'e属于肢。相应的曲线参数与如下方程式有关：
[0087] 当阻的特性不为2或3时，便可W不失一般性地选择ai=a2=a3=0。同样，当 KI的特性为2时，假设楠圆曲线为非超奇异，便可W选择ai= 1和33= 34= 0。
[0088] 在W下部分中，采用根据较短的Weierstra目模型而定义的楠圆曲线，在具有不 等于2或3的特性的环上，给出要执行的用于获得运算符iA孤、iA孤U、iA孤C、iD化和iDBLU 的输出精确计算。
[008引更准确地，从点P郝P2(点Pi和P2属于在具有不等于2或3的特性的环 监_上定义的楠圆曲线而y2 =X3 +a?X+ 6 (根据较短的Weierstra目模型））对 而=巧，尉=知(P1+P2)=如2抑扣仍)进行求值可W按照如下来完成：
[0090]-获得胚中的取=A-X2;
[0091]-获得胺中的C=與2;
[009引-获得肢中的Wi= X iC ;
[009引-获得胺中的胖2=XsC;
[0094] -获得肢I中的D = (yi_y2)2;
[0095]-获得啦中的Ai= (Wi-W2)yi;
[009引然后，肠1中的巧=D - 和肢中妳巧=(Wi -巧(仍-扔）-矣。
[0097] 该系列操作与iADD操作相对应，iADD操作具有4M+2S的总成本，其中，M和S分别 表示:肢中乘法的成本和平方的成本。
[0098] 应当注意，在对乎3:进行求值的过程中免费获得町二巧'，究）=如，(Pi)二 如2知护扔）。实际上，我们立即得到町=(巧，巧，其中，巧=，并且巧=^1。
[0099] 如前所述，与;Pi-起获得梦3的操作被标记为iA孤U。
[0100]从点Pi和P2 (点Pi和P2属于在具有不等于2或3的特性的有限环:松上定义的楠 圆曲线
进行 求值可W按照如下来完成：
[OW]-获得防中的Wi=XiC;
[010引-获得K中的胖2=XsC;
[0103]-获得啦中的Ai=师1-胖2化；
[0104]然后，胶中的'x'3 =(y!+仍)2- - Wz和肢中的y'3 = (Wi-X'3)(Yi + Yz)- i4玉。
[010引实际上，由于斗2=(X2,-y2)，因此，口1斗2= (X' 3，y' 3)满足
因此，被 标记为iA孤C的获取.皆-f*2)帕操作只需要5M+3S。
[0106] 从点Pi(点Pi属于在具有不等于2或3的特性的有限环上定义的楠圆曲线
进行求值可W按照如下来完成：
[0107]-获得肢中的B=xi2;
[010引-获得胶中的E=yi2;
[0109]-获得肢中的L=E2;
[0110]-获得带中的M= 3B+a;
[01川-获得胚中的S= 2((xi+巧2-B-L);
[011引然后，胚中的巧=M2- 2S和胺i中脚；r* =MCS-巧-8L
[om] 对P4 =拓，巧进行求值被标记为iDBL，并且该样的操作只需要1M+5S。而且，在 对梦4慨求值过程中免费获得町=(巧，沉）=斬(Pi)。实际上，我们有'巧=义和巧=8L。 包括获得W及Pi的操作被标记为iDBLU，如前所述。
[0114] 使用楠圆曲线的密码方案中最常用的操作之一为标量乘法。
[0115] 图1根据本发明的一个实施例展示了楠圆曲线上的标量乘法。
[0116] 更准确地，标量乘法包括通过使用在标量乘法处理的过程中确定的同构链或一系 列同构来使用加倍和相加操作。
[0117] 在步骤1处，让E(g) = ￡V表示原始的楠圆曲线，让EW= ￡;,表示当 前的楠圆曲线，并且让￡南W表示最终的楠圆曲线，我们有PeE?和
[om] 步骤i处的当前曲线和原始曲线之间的同构由如i=斬i° 斬1给出。稍微调 整符号，我们还可W使用符号。来表示相应描述上的操作，即Desc(^^i)=薪。…。巧1。 由于
，结果点Q二k.PEE由Q= 二1伯）给 出。"组成的"（composed)同构兩W可W通过观察峰&=咕兩。少否来迭代获得，其 中，的。=M(即，身份映射K由于成=Desc(班南)，我们得到系=焉。禹_1，其中， 批,二Dcsc(W) := 1。
[0119]W下示例说明该样的原理。对于一般的Weierstra目模型，我们有
[0120]
[012引其中，氣-，二.!a'_1,7^)、知=如并且 1 二CM),0,0)。因 此，方程式少'，=捉。最'_1转换为扣i，Ri，Si,Ti)=相，心Si,ti)。扣而_1，Sh,Ty)，其 中，
[0124]
[012引i> 1，并且扣0，R0,S0，T0) = (1，0,0,0)。
[0126] 图2展示了用于在楠圆曲线上执行标量乘法的两个经典的方法（加倍和相加方 法，W及相加和加倍方法）。
[0127] 用于对Q=kP求值（即，楠圆曲线上的标量乘法）的经典方法考虑标量k的二进 制表示1^=化。_1，...，1〇2，其中，1^1￡{0，1}，0《1《11-1。有利地，该方法需要较少数目 的寄存器，因此较好地适于如智能卡之类的存储器受限设备。该方法依赖于如下显然的关 系；如果k是偶数，则fcP= 2(lk/2j/〇,如果k是奇数，则2如/引巧+P。对该处理 进行迭代得到左到右标量乘法算法，被称为加倍和相加方法。该样的方法需要两个（点） 寄存器R。和R1。寄存器R。作为累加器，而寄存器R1被用来存储输入点P的值。
[012引存在右到左变体。结果算法（被称为相加和加倍方法）在图2的算法2中进行描 绘。该方法也需要两个（点）寄存器R。和Ri，但在该情形中，该两个寄存器均作为累加器。
[0129]图3根据本技术展示了用于在楠圆曲线上执行标量乘法的两个方法。
[0130] 更准确地，图3中所展示的算法或方法是根据本发明的一个实施例利用相加和加 倍公式对经典方法的直接实现方式。我们利用原始曲线使用变量多> 来累加当前同构[的描 述]。该变量被初始化为= 1 (与身份映射Id相对应）。如前所述，符号。表示楠圆曲 线同构[的描述]的组成。
[0131]图4根据本技术展示了用于在楠圆曲线上执行标量乘法的方法的另一实施例。
[0132] 该样的实施例是左到右方法的变体，该变体比图3中所描绘的方法更加有效。需 要注意，当ki等于1时，寄存器R1被加到寄存器R。，并且寄存器Ri的内容在整个计算过程 中保持不变化1总是包含输入点P)，则没必要不断地将其更新为当前楠圆曲线上的点。实 际上，在迭代i处，其在当前楠圆曲线（E京）上的表示可W从输入点P作为呼如巧来计算。
[0133] 图5展示了用于在楠圆曲线上执行标量乘法的两个经典的方法（蒙哥马利梯、W 及乔伊的加倍相加梯）。
[0134] 为了存储一些操作结果，该些经典的方法使用H个寄存器（寄存器R。、寄存器Ri和 寄存器T)。
[0135] 图6根据本发明的一个实施例，展示了图5中所公开的用于在楠圆曲线上执行标 量乘法的方法的两个修改。
[0136] 对于若干个楠圆曲线模型，两个不同点的点加公式独立于曲线参数。在该情形中， 有趣的是，依赖于可W被写作一系列iADDU和iADDC操作的标量乘法算法。
[0137] 算法6的主循环为Ri_b-Rb+Ri_^Rb^ 2Rb(其中，b等于0或1)，对于算法7， 为而_6^1^+21?^因此，算法6和算法7可^很容易地适于本文件所提出的新的操作。值 kw= 1导致巧。，T) = (P，P)，并且然后导致算法6的第一次迭代中的Ri=P+P。最后的 操作是点加倍。为了不必处理潜在的特殊情形，我们假设kw= 1，因此在i=n-2处开始 for循环，并且将巧。，而）初始化为（P，2巧。对于更好的性能，该归功于iDBLU操作而实现。 出于相同的原因，我们在右到左算法中假设k。= 1。在算法9中，我们在i= 2处开始化r 循环，并且将初始化为（P，3巧。再次 ，该可W利用新的操作来完成。当k?=0 时，需要在计算的结尾处减去点PW获得正确的结果。
[013引图7根据本发明的一个实施例，展示了图5中所公开的用于在楠圆曲线上执行标 量乘法的蒙哥马利梯方法的修改。
[0139] 原始的蒙哥马利梯使得Ri-R。的差值保持不变，该差值等于P。等同地，算法6中的 变量^^咕-!?^)等于（-l)wp。因此，在迭代1 =〇处，在我们的蒙哥马利梯的版本（算 法8)中的变量Rb在第4行处包含值
该可W允许精确恢复聲衣，W的描 述，因此皆^的描述为
。因此，我们可W获 得不需要跟踪当前同构的类蒙哥马利算法；iADDC和iADDU操作只需要返回点，不需要结果 曲线的同构的描述（即，参数廣）。该由运算符上的符号'来指示。蒙哥马利梯的该变体还 需要iADDC和iADDU操作独立于曲线参数；该由运算符中缺少下标来指示。
[0140] 图8展示了可W被用来执行本文件所公开的方法（或算法）的一个或多个步骤的 设备。
[0141] 该样的设备（参考800)包括计算单元（例如，CPU,为"中央处理单元"）（参考 801) W及一个或多个存储器单元（例如，RAM("随机存取存储器"）框，在运行计算机程序 指令的过程中，中间结果可W被临时存储于该RAM框中；或者ROM框，特别是计算机程序被 存储于该ROM框中；或者EEPR0M("电可擦除可编程只读存储器"）框；或者闪存框）（参考 802) 。计算机程序由可W由计算单元来运行的指令组成。该样的设备800还可W包括专用 单元（参考803)，该专用单元包括允许设备800与其他设备进行通信的输入-输出接口。 具体地，该专用单元803可W与天线相连接（为了执行无接触的通信），或者与串行端口相 连接（W承载通信"接触"）。应当注意，图8中的箭头意味着所链接的单元可W通过总线 例如一起来交换数据。
[0142] 在替代的实施例中，前面所描述的方法中的一些步骤或全部步骤可硬件形式 被实现在可编程FPGA("现场可编程口阵列"）部件或ASIC("专用集成电路"）部件中。
[0143] 在替代的实施例中，前面所描述的方法中的一些步骤或全部步骤可W在包括图8 中所公开的存储器单元和处理单元的电子设备上被运行。
[0144] 对于某些模型（包括通用的Weierstra目模型），中立要素（即，无穷远点0)需要 特殊处理。该可W通过适当地修改初始化步骤来避免。对于经典的左到右梯，假设kw= 1，我们可^在i=n-2处开始for循环，并且在算法3和5中在初始化步骤中设置P 和Ri^P。
[0145] 类似地，对于右到左梯，假设ku= 1，我们可W在i= 1处开始for循环，并且在算 法4中设置R。一P和R2.P。当k。= 0时，我们做法相同，但在计算的结尾处减去P来 获得正确的结果。
[0146] 应当注意，对于组合的操作（例如，R= 2.P+Q的求值），可W根据本技术来完成。 该可^采用两个步骤来完成，首先确定T^P+Q，然后确定R^P+T。如果同时需要点R与 更新后的点P，则该可W利用两个连续的iADDU操作的应用来实施：
[0147]
[0148] 如果我们希望在计算的结尾处同时获得点R与更新后的点Q(而不是点巧，则事情 会稍微复杂。该可W通过对iA孤U进行求值并且之后对iA孤C进行求值来实施：
[0149]
[0150] 最后，应当注意，基于同构楠圆曲线所提出的技术遵从在每次运行该技术时防止 旁路攻击（例如，曲线随机化）的技术。
【主权项】
1. 一种对数据进行密码处理的方法，所述方法由电子设备来运行，并且所述方法包括 获得属于相同椭圆曲线的至少两个点，每个点由至少两个坐标来表示，其中，所述相同椭圆 曲线被定义在为有限环的代数结构上，所述方法的特征在于其包括： -获得所述椭圆曲线与另一椭圆曲线之间的同构的参数化，所述参数化定义一些配置 参数，每个配置参数具有一系列可能的值； -确定作为所述至少两个点的坐标值的函数的所述配置参数，递送所确定的配置参 数； -通过所述同构获得与所述至少两个点的加法的像相对应的另一点的坐标，所述另一 点属于所述另一椭圆曲线，并且由于所述所确定的配置参数，执行所述获得不需要在所述 代数结构中的求逆操作。2. 如权利要求1所述的方法，其特征在于：当所述至少两个点相同时，所述加法为加倍 操作。3. 如权利要求1至2中任一权利要求所述的方法，其特征在于：每个点被表示在仿射 坐标系中。4. 如权利要求1至3中任一权利要求所述的方法，其特征在于：所述方法通过属于第 一椭圆曲线的第一点被用在标量乘法操作中。5. 如权利要求4所述的方法，其特征在于：所述方法包括将所述标量乘法操作的输出 点转换为属于所述第一椭圆曲线的转换后的输出点，所述标量乘法操作的所述输出点属于 最新的椭圆曲线。6. 如权利要求1至5中任一权利要求所述的方法，其特征在于：所述代数结构为具有 等于2的特性的有限域。7. 如权利要求1至5中任一权利要求所述的方法，其特征在于：所述代数结构为具有 等于3的特性的有限域。8. 如权利要求1至5中任一权利要求所述的方法，其特征在于：所述代数结构为具有 等于素数P> 3的特性的有限域。9. 一种计算机可读且非暂态存储介质，所述计算机可读且非暂态存储介质存储包括计 算机可执行指令的集合的计算机程序，从而当所述指令被计算机运行时，实现用于密码计 算的方法，其中，所述指令包括当被运行时将所述计算机配置为执行权利要求1至8所述的 方法的指令。10. -种被配置为对数据执行密码处理的电子设备，所述电子设备包括用于获得属于 相同椭圆曲线的至少两个点的装置，每个点由至少两个坐标来表示，其中，所述相同椭圆曲 线被定义在为有限环的代数结构上，所述电子设备的特征在于其包括： _用于获得所述椭圆曲线与另一椭圆曲线之间的同构的参数化的装置，所述参数化定 义一些配置参数，每个配置参数具有一系列可能的值； -用于确定作为所述至少两个点的坐标值的函数的所述配置参数，递送所确定的配置 参数的装置；以及 -用于通过所述同构获得与所述至少两个点的加法的像相对应的另一点的坐标的装 置，所述另一点属于所述另一椭圆曲线，并且由于所述所确定的配置参数，执行所述获得不 需要在所述代数结构中的求逆操作。11. 如权利要求10所述的电子设备，其特征在于：当所述至少两个点相同时，所述加法 为加倍操作。12. 如权利要求10至11中任一权利要求所述的电子设备，其特征在于：每个点被表示 在仿射坐标系中。13. 如权利要求10至12中任一权利要求所述的电子设备，其特征在于：所述装置被用 来利用属于第一椭圆曲线的第一点来执行标量乘法操作。14. 如权利要求13所述的电子设备，其特征在于：所述电子设备包括用于将所述标量 乘法操作的输出点转换为属于所述第一椭圆曲线的转换后的输出点的装置，其中，所述标 量乘法操作的所述输出点属于最新的椭圆曲线。15. 如权利要求10至14中任一权利要求所述的电子设备，其特征在于：所述代数结构 为具有等于素数P> 3的特性的有限域。
【专利摘要】本发明涉及密码处理椭圆曲线数据的方法、电子设备及计算机程序。提出了对数据进行密码处理的方法，该方法由电子设备来运行，并且该方法包括获得属于被定义在为有限环的代数结构上的相同椭圆曲线的至少两个点，每个点由至少两个坐标来表示。该方法的特征在于，包括：获得所述椭圆曲线与另一椭圆曲线之间的同构的参数化，参数化定义一些配置参数，每个配置参数具有一系列可能的值；在至少两个点的坐标值的函数中确定配置参数，递送所确定的配置参数；以及通过同构获得与至少两个点的加法的像相对应的另一点的坐标，另一点属于另一椭圆曲线，并且由于所确定的配置参数，执行所述获得不需要在代数结构中的求逆操作。
【IPC分类】H04L9/06
【公开号】CN104901792
【申请号】CN201510093017
【发明人】马克·乔伊, 拉文·贡德尔
【申请人】汤姆逊许可公司
【公开日】2015年9月9日
【申请日】2015年3月2日
【公告号】EP2916215A1, EP2916216A1, US20150256340
最新回复(0)