使用混合仿射雅可比坐标进行ECC点加的硬件架构和方法

摘要

一种引入了简单算术处理器的优化的硬件架构和方法，所述优化的硬件架构和方法允许高效地实现针对混合仿射雅可比坐标的椭圆曲线密码学点加算法。此外，优化的架构减少了对中间值的所需存储。

说明书

背景技术

电子设备正成为日常生活无处不在的部分。所用的智能电话和个 人平板计算机的数目正在迅速增长。越来越多地使用智能电话和个人 平板电脑的副作用在于设备被越来越多地用于存储诸如个人和银行数 据等的机密数据。保护这种数据不被窃取是十分重要的。

密码学领域提供用于使这种机密数据保持安全的保护工具。基于 难以解决数学问题，密码学通常需要较高计算强度的计算，所述较高 计算强度的计算是在云计算和普适计算(ubicomp)中更广泛应用的主 要障碍。如果无法足够快速地执行密码操作，则通常不接受将密码学 工具用于互联网。为了在提供安全性和数据完整性的同时使密码工具 是透明的，密码学工具需要遵循由于移动应用中对高速度和低功耗的 需求而推动的趋势。

通常，公钥算法是密码学中计算最密集的计算。例如，以椭圆曲 线密码学(ECC)，即，计算效率最高的公钥算法之一，为例。256位 版本的ECC提供等同于128位对称密钥的安全性。256位ECC公钥 应提供与3072位RSA公钥可比的安全性。ECC的基本运算是点乘， 点乘是大量基于模乘的运算，即，执行一个ECC 256点乘需要大约256 位整数的3500个模乘。更高安全性等级(更大位整数)需要甚至更多 的计算工作。

构建ECC的高效实现方式通常是有意义的，并且涉及多个阶段。 图1示出了实现椭圆曲线数字签名算法(ECDSA)所需的阶段101、 102和103，所述ECDSA是ECC的应用之一。阶段101处理包括模 加、模逆和模乘的有限域算术。阶段102处理点加和点倍(point  doubling)，包括联合稀疏形式(JSF)、非相邻形式(NAF)、加窗和 投影坐标。最后，阶段103处理ECDSA以及数字签名的接受或拒绝。

可以将任意椭圆曲线写成由以下形式的方程定义的平面几何曲 线(假定系数域的特性不等于2或3)：

y²＝x³+ax+b    ((1)

该方程是非奇异的；也就是说，该方程没有尖端(cusp)或自相交， 公知为短维尔斯特拉斯(Weierstrass)形式，其中，a和b是整数。通 常在例如由NIST、SEC和ANSI颁布的若干标准中使用a＝-3的情况， 这使得该情况成为通常感兴趣的情况。

在用于高效实现点加(PADD)和点倍(PDBL)运算的文献中， 已经提出了许多算法。对这些算法中的很多算法进行优化以便软件实 现。虽然它们通常在特定平台上是高效的，但是一旦调整底层硬件以 适应算法，则该算法通常不是最优的。

Cohen、Miyaji以及Ono在Proceedings of the International  Conference on the Theory and Applications of Cryptography and  Information Security；Advances in Cryptology，ASIACRYPT 1998，pages  51-65，Springer-Verlag，1998中已经描述了混合仿射雅可比 (affine-Jacobian)坐标的PADD算法。雅可比坐标是投影坐标，每个 点被表示为三个坐标(X，Y，Z)，其中x＝X/Z²、y＝y/Z³，仿射坐标是 常见的(x，y)坐标。应注意坐标都是整数。PADD算法200需要8个 模乘、3个模平方、6个模减以及一个与2模乘，如图2所示。为了执 行PADD，该算法还需要最少4个临时寄存器，其中对于ECC 256位， 每个寄存器需要256位大小。在有限域K内进行所有运算，其中椭圆 曲线E被定义在有限域K上。通过质数p定义有限算术域K，使得以 p为模执行所有算术运算。加性单位元素是无穷远点。

发明内容

经优化的硬件架构和方法通过只需要两个临时存储寄存器以及 引入用于执行模减和与2模乘的简单算术单元，降低了存储需要，并 加速了对ECC PADD算法的执行。

附图说明

图1示出了实现椭圆曲线数字签名算法(ECDSA)所需的阶段 101、102和103。

图2示出了现有技术的点加算法。

图3示出了根据本发明的实施例。

图4示出了根据本发明的实施例。

图5示出了根据本发明的实施例。

图6示出了根据本发明的实施例。

图7示出了根据本发明的实施例。

具体实施方式

图3示出了根据本发明的PADD算法300。相较于针对相同的两 点模加的PADD算法200，PADD算法300需要更少步骤，并且降低 了存储需要。PADD算法300仅需要两个临时存储寄存器T₁和T₂。应 注意，PADD算法300使用混合仿射雅可比坐标执行模点加，以避免 需要模逆运算，其中模逆运算通常比模乘运算慢一至两个数量级。相 较于同样避免需要模逆运算的仅以雅可比坐标执行点加，使用混合坐 标提供了速度优势。PADD算法300被实现在优化硬件架构上，该优 化硬件架构如图6和图7所示并且被特定地设计为利用PADD算法300。

作为步骤301的输入，图3所示的PADD算法300采用雅可比坐 标下的点P＝(X₁，Y₁，Z₁)以及仿射坐标下的点Q＝(x₂，y₂)，作为要按照 P+Q相加的两个点。T₁和T₂是临时存储变量。应注意，所有数学运 算都以模算术示出。在PADD算法300的步骤302，如果Q＝∞，则 由于无穷远点是单位元素，将点P的值返回作为P+Q的模加的结果。 类似地，在步骤303，如果P＝∞，则由于无穷远点是加性单位元素， 将点Q的值返回作为P+Q的模加的结果。在步骤304，对雅可比坐 标Z₁进行平方，将得到的值存储在临时寄存器T₁中。在步骤305，计 算Z₁*T₁，将得到的值存储在临时寄存器T₂中。在步骤306，计算 T₂*y₂-Y₁，其中y₂在仿射坐标下，Y₁在雅可比坐标下，将结果存储 在临时寄存器T₂中。在步骤307，将临时寄存器T₁所存储的值与x₂相乘，然后从该结果中减去X₁，其中x₂在仿射坐标下，X₁在雅可比 坐标下，将结果存储在临时寄存器T₁中。如果T₁和T₂都是零，则由 于这意味着P＝Q，步骤308提供返回，如果T₁为零且T₂不为零，则 由于这意味着P＝-Q，步骤309提供返回。在步骤310，将雅可比坐 标Z₁乘以临时寄存器T₁中的值，将该结果存储为雅可比坐标Z₃。在 步骤311，对临时寄存器T₁所存储的值进行平方，并将其存储为雅可 比坐标Y₃。在步骤312，对临时寄存器T₂所存储的值进行平方，并将 其存储为雅可比坐标X₃。在步骤313，计算Y₃*T₁，并将结果存储在 临时寄存器T₁中。在步骤314，计算T₁+2Y₃*X₁，并从雅可比坐标 X₃中减去该值，将结果存储为雅可比坐标X₃。在步骤315，计算Y₃* X₁-X₃，将该值乘以T₂，并将结果存储为雅可比坐标Y₃。应注意， 在步骤314，计算Y₃*X₁，在步骤315使用该值，且不在步骤315再 次计算该值。在步骤316，计算T₁*Y₁，从雅可比坐标Y₃中减去该值， 并将结果存储为雅可比坐标Y₃。最后，在步骤317，将P+Q的点加 的结果：(X₃，Y₃，Z₃)以雅可比坐标返回。

图3的PADD算法300中的计算最密集的运算是由“*”表示的 模乘。由于PADD算法300中所述的大部分步骤依赖于该算法的先前 步骤，通常最有效的是在硬件中使用单个模乘器来执行PADD算法300， 但是根据本发明可以使用多于一个模乘器。仅使用一个模乘器将 PADD算法300中的每个步骤限制为具有不超过一个模乘。尽管步骤 315似乎包含两个模乘，但是在步骤314已计算出Y₃*X₁的结果，该 结果被直接馈送到硬件模乘器的输入端。

需要注意的是，除了在PADD算法300的步骤306、307、314、 315和316中执行的模乘步骤之外，还执行两个附加的比较简单的运 算：模减和与2模乘。应注意，乘以或除以2的幂在二进制中仅是移 位运算。为了加速执行PADD算法300以及消除对附加临时寄存器的 需要，根据本发明的简单算术单元(SAU)400的实施例具有如图4 所示的输入和输出。

图5示出了如何分解图3的PADD 300的步骤306、307、314、 315和316，以便使用具有输入A、B和C以及输出D的SAU 400。 应注意，SAU 400的输入和输出标签与图5中的相应变量名称相对应。 块501示出了如何使用SAU 400分解PADD算法300的步骤306，并 涉及设置输入A＝T₂*y₂和B＝Y₁，输出D＝A-B。将输出D写入临 时寄存器T₂。块501示出了如何使用SAU 400分解PADD算法300 的步骤307，并涉及设置输入A＝T₁*x₂和B＝X₁，输出D＝A-B。 然后将输出D写入临时寄存器T₁。块503示出了如何使用SAU 400 分解PADD算法300的步骤314，并涉及设置输入A＝X₃、B＝T₁、C ＝y₂*X₁，输出D＝A-B-2C。将输出D写成雅可比坐标X₃。块504 示出了如何使用SAU 400分解PADD算法300的步骤315，并涉及设 置输入A＝Y₃*X₁和B＝X₃，输出D＝A-B。将输出D写成雅可比 坐标Y₃。块505示出了如何使用SAU 400分解PADD算法300的步 骤316，并涉及设置输入A＝Y₃和B＝T₁*Y₁，输出D＝A-B。将输 出D写成雅可比坐标Y₃。应注意，“不理会”指示该值与在相应步骤 中执行的计算不相关。

图6示出了根据本发明的实施例600，包括具有输出寄存器(未 示出)的多循环乘法器610、SAU 400、乘法器(MUX)620和MUX 630、以及输入寄存器X₁、Y₁、Z₁、x₂、y₂、输出寄存器X₃、Y₃、Z₃和临时寄存器T₁和T₂，所述寄存器均是寄存存储器695的一部分。 应注意，相应寄存器标签与图3和图5中的变量名称相对应。由执行 PADD算法300的微处理器(未示出)控制MUX 620、630和740(SAU 400的一部分，参照图7)。如上所述，PADD算法300中的每个步骤 涉及至多一个模乘(不计算乘以或除以2，乘以或除以2在二进制表 示中仅是移位运算)。

图7所示的SAU 400包括减法器710和720、逻辑1位左移位器 715和MUX 720。输入A通过线缆670连接到减法器710的被减数输 入，输入B通过线缆675连接到减法器710的减数输入。输入C通过 线缆650连接到逻辑1位左移位器715，所述逻辑1位左移位器715 执行输入C与2的乘法。减法器710在线缆730上输出A-B，线缆730 连接到减法器720的被减数输入以及MUX 740的“0”输入。逻辑1 位左移位器715在线缆735上将2C输出到减法器720的减数输入。 减法器720在线缆750上将A-B-2C输出到MUX 740的“1”输入。 MUX 740在线缆690上发送D。

多循环乘法器610通过将输入635和640上的值相乘并输出结果 来运作。在微处理器(未示出)中执行步骤301-303，而不使用多循 环乘法器610和SAU 400。

步骤304使用多循环乘法器610。寄存存储器695在多循环乘法 器610的输入635和640二者上提供Z₁，多循环乘法器610计算Z₁²， 在线缆650上将Z₁²发送到寄存存储器695，并将其存储在临时寄存器 T₁中。

步骤305使用多循环乘法器610。寄存存储器695在多循环乘法 器610的输入635上提供T₁并在多循环乘法器610的输入640上提供 Z₁。多循环乘法器610计算T₁*Z₁，并在线缆650上将T₁*Z₁发送到 寄存存储器695，其中将其存储在临时寄存器T₂中。

步骤306使用多循环乘法器610和SAU 400。寄存存储器695分 别在线缆635和线缆640上将T₂和y₂提供给多循环乘法器610。多循 环乘法器610计算T₂*y₂，在线缆650上将T₂*y₂输出到MUX 620 的输入“1”，MUX 620被设置为“1”。MUX 630输入被设置为“0”。 MUX 620在线缆670上向SAU 400的输入A发送T₂*y₂。线缆670 直接连接到减法器710的被减数输入。寄存存储器695在线缆660上 将Y₁提供给MUX 630的输入“0”，MUX 630被设置为“0”。MUX 630 在线缆675上向SAU 400的输入B发送Y₁。线缆675直接连接到减 法器710的减数输入。减法器710计算A-B(即T₂*y₂-Y₁)，并在 线缆730上将A-B输出到MUX 740的输入“0”，MUX 740被设置 为“0”。MUX 740在线缆690上将D(即，A-B)发送到寄存存储 器695，其中将其存储在寄存存储器T₂中。

步骤307使用多循环乘法器610和SAU 400。寄存存储器695分 别在线缆635和线缆640上将T₁和x₂提供给多循环乘法器610。多循 环乘法器610计算T₁*x₂，在线缆650上将T₁*x₂输出到MUX 620 的输入“1”，MUX 620被设置为“1”。MUX 620在线缆670上向SAU 400的输入A发送T₁*x₂。线缆670直接连接到减法器710的被减数 输入。寄存存储器695在线缆660上将X₁提供给MUX 630的输入“0”， MUX 630被设置为“0”。MUX 630在线缆675上向SAU 400的输入 B发送X₁。线缆675直接连接到减法器710的减数输入。减法器710 计算A-B(即T₁x₂-X₁)，并在线缆730上将A-B输出到MUX 740 的输入“0”，MUX 740被设置为“0”。MUX 740在线缆690上将D (即，A-B)发送到寄存存储器695，其中将其存储在寄存存储器T₁中。

在微处理器(未示出)中执行步骤308-309，而无需使用多循环 乘法器610和SAU 400。

步骤310使用多循环乘法器610。寄存存储器695在线缆635上 向多循环乘法器610提供T₁并且在线缆640上向多循环乘法器610提 供Z₁。多循环乘法器610计算T₁*Z₁，并且在线缆650上将结果输出 到寄存存储器695，其中将所述结果存储在临时寄存器T₂中。

步骤311使用多循环乘法器610。寄存存储器695在线缆635和 线缆640二者上向多循环乘法器610提供T₁。多循环乘法器610计算 T₁²，并且在线缆650上将结果输出到寄存存储器695Y₃，其中将所述 结果存储在Y₃中。

步骤312使用多循环乘法器610。寄存存储器695在线缆635和 线缆640二者上向多循环乘法器610提供T₂。多循环乘法器610计算 T₂²，并且在线缆650上将结果输出到寄存存储器695，其中将所述结 果存储在X₃中。

步骤313使用多循环乘法器610。寄存存储器695在线缆635上 向多循环乘法器610提供T₁并且在线缆640上向多循环乘法器610提 供Y₃。多循环乘法器610计算T₁*Y₃，并且在线缆650上将结果输出 到寄存存储器695，其中将所述结果存储在临时寄存器T₁中。

步骤314使用多循环乘法器610和SAU 400二者。寄存存储器 695在线缆665上将X₃提供给MUX 620的输入“0”，其中MUX 620 被设置为“0”。MUX 620在线缆670上向SAU 400的输入A发送X₃。 线缆670直接连接到减法器710的被减数输入。寄存存储器695在线 缆660上将T₁提供给MUX 630的输入“0”，MUX 630被设置为“0”。 MUX 630在线缆675上向SAU 400的输入B发送T₁。线缆675直接 连接到减法器710的减数输入。减法器710计算A-B(即X₃-T₁)， 并在线缆730上将A-B输出到减法器720的被减数输入。寄存存储 器695在线缆635上向多循环乘法器610提供X₁并且在线缆640上向 多循环乘法器610提供Y₃。多循环乘法器610计算Y₃*X₁。在线缆 650上将该结果输出到SAU 400的输入C，SAU 400的输入C直接连 接到逻辑1位左移位器715，其中所述逻辑1位左移位器715将输入 C乘以2，并在线缆735上将2C(即2Y₃*X₁)输出到减法器720的 减数输出。减法器720计算A-B-2C，并在线缆750上将A-B-2C 输出到MUX 740的输入“1”，MUX 740被设置为“1”。MUX 740在 线缆690上将D(即A-B-2C＝X₃-T₁-2Y₃*X₁)发送到寄存存储 器695，其中将D存储在X₃中。

步骤315使用多循环乘法器610和SAU 400二者。在步骤314， 通过多循环乘法器610计算Y₃*X₁。因此，Y₃*X₁仍存在于多循环乘 法器610的输出寄存器(未示出)中，在步骤315，在线缆650上将 Y₃*X₁发送到MUX 620的输入“1”，MUX 620被设置为“1”。MUX 620在线缆670上将Y₃*X₁发送到SAU 400的输入A。线缆670直接 连接到减法器710的被减数输入。寄存存储器695在线缆660上将X₃提供给MUX 630的输入“0”，MUX 630被设置为“0”。MUX 630在 线缆675上将X₃发送到SAU 400的输入B。线缆675直接连接到减 法器710的减数输入。减法器710计算A-B，并且在线缆730上将 结果发送到MUX 740的输入“0”，其中MUX 740被设置为“0”。 MUX 740在线缆690上将D(即A-B＝Y₃*X₁-X₃)发送到寄存存 储器695，寄存存储器695通过线缆635将D传递到多循环乘法器610， 并在线缆640上将T₂提供给多循环乘法器610。多循环乘法器610计 算D*T₂(即(Y₃*X₁-X₃)*T₂)，并在线缆650上将结果输出到寄存 存储器695，其中将所述结果存储在Y₃中。

步骤316使用多循环乘法器610和SAU 400二者。寄存存储器 695在线缆665上将Y₃提供给MUX 620的输入“0”，其中MUX 620 被设置为“0”。MUX 620在线缆670上向SAU 400的输入A发送Y₃。 线缆670直接连接到减法器710的被减数输入。寄存存储器695在线 缆635上将T₁提供给多循环乘法器610并且在线缆640上将Y₁提供 给多循环乘法器610。多循环乘法器610计算T₁*Y₁，并在线缆650 上将T₁*Y₁输出到MUX 630的输入“1”，MUX 630被设置为“1”。 MUX 630在线缆675上将T₁*Y₁发送到SAU 400的输入B。线缆675 直接连接到减法器710的减数输入。减法器710计算A-B(即Y₃-T₁*Y₁)，并且在线缆730上将结果提供给MUX 740的输入“0”，MUX 740被设置为“0”。MUX 740在线缆690上将D(即Y₃-T₁*Y₁)发 送到寄存存储器695，其中将所述结果存储在Y₃中。

步骤317以雅可比坐标返回P+Q相加的结果，即(X₃，Y₃，Z₃)。