用于固定执行流乘数再译码和标量乘法的方法和装置

摘要

一个特征涉及包含存储器电路和处理电路的电子装置。所述处理电路计算标量乘法输出Z，其中Z＝k·P，方法是接收输入乘数k和底数P，并且将修改符s添加到所述输入乘数k以产生k'。所述处理电路还计算中间标量乘法输出Z'，其中Z'＝k'·P，方法是使用包含属于数字集合D的数字ki的序列的k'的数字展开式。另外，如果k'是奇数，那么所述处理电路从Z'中减去s·P以获取所述标量乘法输出Z，或者如果k'是偶数，那么从Z'中减去(s+1)·P以获取所述标量乘法输出Z。所述标量乘数输出Z可用于密码安全算法中以确保数据安全。

说明书

相关申请的交叉参考

本申请主张2015年5月6日在美国专利和商标局递交的第14/705,686号非临时申请的优先权和权益，并且所述申请的全部内容以引用的方式并入本文中。

技术领域

各种特征大体上涉及密码安全，且更确切地说，涉及用于在密码安全算法中使用的固定执行流乘数再译码和标量乘法的方法和装置。

背景技术

椭圆曲线点乘法，且一般而言乘以具有g个元素的循环群中的常数，是接受乘数k(其中k≥0)和底数P的计算，并且如下计算结果：

此运算被称为标量乘法，并且它是许多密码协议中的基本运算，例如，Diffe-Hellman密钥交换和产生数字签名。

一般而言，可以通过首先将乘数k写出为来计算k·P，其中k_i是整数数字集合D的元素。首先，假设存在初始化到附加的标识的Z，这对于椭圆曲线来说称之为在无限处的点。接下来，从最高有效到最低有效检测k的数字k_i。对于数字k_i，如果k_i为0，那么Z:＝2*Z。如果k_i≠0，那么Z:＝2*Z+k_i*P。当已经处理了所有位时，那么结果是Z的当前值。然而，使用此类展开的方法易受侧信道分析攻击和计时分析攻击的影响，这是因为零和非零数字的序列是不规则的，由此漏泄关于乘数k的一些信息。

由Nicholas Theriault开发的现有技术方法减少了侧信道分析和计时分析的风险。Nicholas Theriault，抗SPA从左到右整数记录(SPA Resistant Left-to-RightInteger Recodings)，密码术中的选定区域(Selected Areas in Cryptography，2005)：第345-358页。Theriault将乘数k展开为展开式其中w是窗口长度参数，且k_i选自整数的两个集合中的一个：

数字集合#1：窗口w的{±1}∪{±2,±4,…,±2^w}；

数字集合#2：窗口w的{±1,±3,±5,…,±2^w-1}。

但是，Theriault的方法具有一些显著的缺点。首先，数字集合#2仅可展开奇数数字。因此，Theriault提出通过奇数阶次的群组使用这一乘数展开式，并且如果初始乘数k是偶数，那么添加一个群组阶次g的奇乘数使得新的乘数k'＝k+n*g为奇数。这是有缺点的，它使得乘数更长，并且因此标量乘法变慢。其次，由于k'>g，所以中间计算中的一个可能结果为等于g·P。这引起在通过椭圆曲线计算的公式中的例外的情况，其结果为出现泄漏信息并且可通过旁信道攻击检测到。

第三，使用数字集合#2计算乘数展开式将产生0或1的运载，这需要额外的运算或虚拟运算以修正结果。然而，额外运算将可通过旁信道攻击检测到，并且虚拟运算将可通过故障攻击检测到。因此，在两种情况下信息都被泄漏，并且可以揭露乘数的奇偶。

因而，存在对可以时间和存储器有效的方式(也抗旁信道攻击和故障攻击)执行标量乘法的方法和装置的需求。

发明内容

一个特征提供包括存储器电路和通信耦合到存储器电路的处理电路的电子装置。处理电路适用于计算标量乘法输出Z，其中Z＝k·P，方法是接收输入乘数k和底数P、将修改符s添加到输入乘数k以产生k'，其中无论k是奇数或偶数，添加相同的修改符s到输入乘数k以产生k'，计算中间标量乘法输出Z'，其中Z'＝k'·P，方法是使用包含属于数字集合D的数字k_i的序列的k'的数字展开式，并且如果k'是奇数，那么从Z'中减去s·P以获取标量乘法输出Z，或者如果k'是偶数，那么从Z'中减去(s+1)·P以获取标量乘法输出Z，并且其中标量乘数输出Z用于密码安全算法中以确保数据安全。根据一个方面，k'的数字展开式是基于的，并且数字k_i的序列来自数字集合D＝{±1,±3,±5,…,±2^w-1}，w是大于或等于一(1)的整数值，并且c等于0或1。根据另一方面，修改符s等于一(1)或二(2)。

根据一个方面，计算中间标量乘法输出Z'包含初始化进位值c等于零(0)，并且通过针对i＝l至减小到i＝0的所有整数值执行运算确定数字序列(k_l,k_l-1,…,k₁,k₀)：

k_i:＝k_i-2^wc；

如果k_i是偶数，那么：

k_i:＝k_i+1；

c:＝1；

否则：

c:＝0。

根据另一方面，计算中间标量乘法输出Z'进一步包含以下操作中的一个：初始化Z'为Z'＝k_l·P，并且针对i＝l-1至减小到i＝0执行运算：

Z'＝2·Z'等于w的次数；

Z'＝Z'+k_i·P；或者

初始化Z'为Z'＝0，并且针对i＝l至减小到i＝0执行运算：

Z'＝2·Z'等于w的次数；

Z'＝Z'+k_i·P。

根据另一个方面，处理电路进一步适用于针对所有值|d|(其中|d|∈D)预先计算多个值d·P和/或-d·P中的至少一个，并且将预先计算的多个值d·P和/或-d·P存储在存储器电路中。

根据一个方面，运算Z'＝Z'+k_i·P通过从存储在存储器电路中的预先计算的多个值d·P和/或-d·P中检索k_i·P执行。根据另一方面，数字集合D包含多个整数值{d₀,d₁,…,d_n}，并且处理电路进一步适用于针对i＝0到i＝n预先计算和存储多个值d_i·P。根据又一个方面，处理电路进一步适用于针对至少一个整数中间值m预先计算和存储m·P，其中m大于数字集合D中的最小值并且小于数字集合D中的最大值，并且其中修改符s和s+1都在集合{d₀,d₁,…,d_n}∪{m}中。根据另一方面，计算中间标量乘法输出Z'包含初始化进位值c等于零(0)，并且针对等于或大于一(1)的窗口长度值w确定数字序列(k_l,k_l-1,…,k₁,k₀)，方法是针对i＝l至减小到i＝0的所有整数值执行运算：

k_i:＝k_i-2^wc；

c:＝1-LSB(k_i)；

k_i＝k_i+c。

另一特征提供用于计算标量乘法输出Z的方法，其中Z＝k·P，所述方法包括接收输入乘数k和底数P、将修改符s添加到输入乘数k以产生k'，其中无论k是奇数或偶数，添加相同的修改符s到输入乘数k以产生k'，计算中间标量乘法输出Z'，其中Z'＝k'·P，方法是使用包含属于数字集合D的数字k_i的序列的k'的数字展开式，并且如果k'是奇数，那么从Z'中减去s·P以获取标量乘法输出Z，或者如果k'是偶数，那么从Z'中减去(s+1)·P以获取标量乘法输出Z，并且其中标量乘数输出Z用于密码安全算法中以确保数据安全。根据一个方面，计算中间标量乘法输出Z'包含初始化进位值c等于零(0)，并且针对等于或大于一(1)的窗口长度值w确定数字序列(k_l,k_l-1,…,k₁,k₀)，方法是针对i＝l至减小到i＝0的所有整数值执行运算：

k_i:＝k_i-2^wc；

如果k_i是偶数，那么：

k_i:＝k_i+1；

c:＝1；

否则：

c:＝0。

根据另一方面，计算中间标量乘法输出Z'进一步包含初始化Z'为Z'＝k_l·P，并且针对i＝l-1至减小到i＝0执行运算：

Z'＝2·Z'等于w的次数；

Z'＝Z'+k_i·P。

根据一个方面，所述方法进一步包括针对所有值|d|(其中|d|∈D)预先计算多个值d·P和/或-d·P中的至少一个，并且将预先计算的多个值d·P和/或-d·P存储在存储器电路中。根据另一方面，运算Z'＝Z'+k_i·P通过从存储在存储器电路中的预先计算的多个值d·P和/或-d·P中检索k_i·P执行。根据又一个方面，数字集合D包含多个整数值{d₀,d₁,…,d_n}，并且所述方法进一步包括针对i＝0到i＝n预先计算和存储多个值d_i·P。

根据一个方面，所述方法进一步包括针对至少一个整数中间值m预先计算和存储m·P，其中m大于数字集合D中的最小值并且小于数字集合D中的最大值，并且其中修改符s和s+1都在集合{d₀,d₁,…,d_n}∪{m}中。根据另一方面，计算中间标量乘法输出Z'包含初始化进位值c等于零(0)，并且针对等于或大于一(1)的窗口长度值w确定数字序列(k_l,k_l-1,…,k₁,k₀)，方法是针对i＝l至减小到i＝0的所有整数值执行运算：

k_i:＝k_i-2^wc；

c:＝1-LSB(k_i)；

k_i＝k_i+c。

另一特征提供适用于计算标量乘法输出Z的电子装置，其中Z＝k·P，并且所述电子装置包括：用于接收输入乘数k和底数P的装置；用于将修改符s添加到输入乘数k以产生k'的装置，其中无论k是奇数或偶数，添加相同的修改符s到输入乘数k以产生k'；用于计算中间标量乘法输出Z'的装置，其中Z'＝k'·P，方法是使用包含属于数字集合D的数字k_i的序列的k'的数字展开式；以及如果k'是奇数，那么用于从Z'中减去s·P以获取标量乘法输出Z的装置，或者如果k'是偶数，那么用于从Z'中减去(s+1)·P以获取标量乘法输出Z的装置，并且其中标量乘数输出Z用于密码安全算法中以确保数据安全。根据一个方面，用于计算中间标量乘法输出Z'的装置包含用于初始化进位值c等于零(0)的装置，以及用于针对等于或大于一(1)的窗口长度值w确定数字序列(k_l,k_l-1,…,k₁,k₀)的装置，方法是针对i＝l至减小到i＝0的所有整数值执行运算：

k_i:＝k_i-2^wc；

如果k_i是偶数，那么：

k_i:＝k_i+1；

c:＝1；

否则：

c:＝0。

根据另一方面，用于计算中间标量乘法输出Z'的装置进一步包含用于初始化Z'为Z'＝k_l·P的装置，以及用于针对i＝l-1至减小到i＝0执行运算的装置：

Z'＝2·Z'等于w的次数；

Z'＝Z'+k_i·P。

根据一个方面，电子装置进一步包括用于针对所有值|d|(其中|d|∈D)预先计算多个值d·P和/或-d·P中的至少一个的装置；以及用于将预先计算的多个值d·P和/或-d·P存储在存储器电路中的装置。根据另一方面，运算Z'＝Z'+k_i·P通过用于从存储在存储器电路中的预先计算的多个值d·P和/或-d·P中检索k_i·P的装置执行。根据又一个方面，数字集合D包含多个整数值{d₀,d₁,…,d_n}，并且所述电子装置进一步包括针对i＝0到i＝n用于预先计算多个值d_i·P的装置和用于存储多个值d_i·P的装置。

根据一个方面，所述电子装置进一步包括用于针对至少一个整数中间值m预先计算m·P的装置和用于存储m·P的装置，其中m大于数字集合D中的最小值并且小于数字集合D中的最大值，并且其中修改符s和s+1都在集合{d₀,d₁,…,d_n}∪{m}中。根据另一方面，用于计算中间标量乘法输出Z'的装置包含用于初始化进位值c等于零(0)的装置，以及用于针对等于或大于一(1)的窗口长度值w确定数字序列(k_l,k_l-1,…,k₁,k₀)的装置，方法是针对i＝l至减小到i＝0的所有整数值执行运算：

k_i:＝k_i-2^wc；

c:＝1-LSB(k_i)；

k_i＝k_i+c。

一种适用于存储一或多个指令以计算标量乘法输出Z的计算机可读存储媒体，其中Z＝k·P，所述指令在由至少一个处理器执行时使得所述处理器接收输入乘数k和底数P、将修改符s添加到输入乘数k以产生k'，其中无论k是奇数或偶数，添加相同的修改符s到输入乘数k以产生k'，计算中间标量乘法输出Z'，其中Z'＝k'·P，方法是使用包含属于数字集合D的数字k_i的序列的k'的数字展开式，并且如果k'是奇数，那么从Z'中减去s·P以获取标量乘法输出Z，或者如果k'是偶数，那么从Z'中减去(s+1)·P以获取标量乘法输出Z，并且其中标量乘数输出Z用于密码安全算法中以确保数据安全。根据一个方面，用于使得处理器计算中间标量乘法输出Z'的指令进一步包含用于使得处理器进行以下操作的指令：初始化进位值c等于零(0)，并且针对等于或大于一(1)的窗口长度值w确定数字序列(k_l,k_l-1,…,k₁,k₀)，方法是针对i＝l至减小到i＝0的所有整数值执行运算：

k_i:＝k_i-2^wc；

如果k_i是偶数，那么：

k_i:＝k_i+1；

c:＝1；

否则：

c:＝0。

根据另一方面，用于使得处理器计算中间标量乘法输出Z'的指令进一步包含用于使得处理器初始化Z'为Z'＝k_l·P、针对i＝l-1至减小到i＝0执行运算的指令：

Z'＝2·Z'等于w的次数；

Z'＝Z'+k_i·P。

根据一个方面，在由至少一个处理器执行所述指令时进一步使得所述处理器针对所有值|d|(其中|d|∈D)预先计算多个值d·P和/或-d·P中的至少一个；并且将预先计算的多个值d·P和/或-d·P存储在存储器电路中。根据另一方面，在由至少一个处理器执行所述指令时进一步使得所述处理器从存储在所述存储器电路中的所述预先计算的多个值d·P和/或-d·P中检索k_i·P以执行运算Z'＝Z'+k_i·P。根据又一个方面，数字集合D包含多个整数值{d₀,d₁,…,d_n}，并且在由至少一个处理器执行时所述指令进一步使得所述处理器针对i＝0到i＝n预先计算和存储多个值d_i·P。

根据一个方面，在由至少一个处理器执行时所述指令进一步使得所述处理器针对至少一个整数中间值m预先计算和存储m·P，其中m大于数字集合D中的最小值并且小于数字集合D中的最大值，并且其中修改符s和s+1都在集合{d₀,d₁,…,d_n}∪{m}中。根据另一方面，用于使得处理器计算中间标量乘法输出Z'的指令进一步包含用于使得处理器初始化进位值c等于零(0)、并且针对等于或大于一(1)的窗口长度值w确定数字序列(k_l,k_l-1,…,k₁,k₀)的指令，方法是针对i＝l至减小到i＝0的所有整数值执行运算：

k_i:＝k_i-2^wc；

c:＝1-LSB(k_i)；

k_i＝k_i+c。

另一特征提供一种集成电路，所述集成电路包括存储器电路和通信耦合到所述存储器电路的处理电路，所述处理电路适用于通过以下操作来计算标量乘法输出Z，其中Z＝k·P：接收输入乘数k和底数P，将修改符s添加到输入乘数k以产生k'，其中无论k是奇数或偶数，添加相同的修改符s到输入乘数k以产生k'，计算中间标量乘法输出Z'，其中Z'＝k'·P，方法是使用包含属于数字集合D的数字k_i的序列的k'的数字展开式，并且如果k'是奇数，那么从Z'中减去s·P以获取标量乘法输出Z，或者如果k'是偶数，那么从Z'中减去(s+1)·P以获取标量乘法输出Z，并且其中标量乘数输出Z用于密码安全算法中以确保数据安全。根据一个方面，

附图说明

图1说明电子装置的示意性框图。

图2说明密码电路的示例性框图。

图3说明在标量乘法电路处执行的算法。

图4A和4B说明可在标量乘法电路处执行的方法的流程图。

图5说明存储值d·P的示例性预先计算表。

图6A和6B说明对k、w、D和s的样本数值的椭圆点标量乘法的第一示例性执行。

图7A和7B说明对k、w、D和s的样本数值的椭圆点标量乘法的第二示例性执行。

图8A和8B说明对k、w、D和s的样本数值的椭圆点标量乘法的第三示例性执行。

图9说明可在处理电路处执行的方法的流程图。

图10说明示例性标量乘法电路的示意性框图。

具体实施方式

在以下描述中，给出具体细节以提供对本发明的各种方面的透彻理解。然而，所属领域的技术人员将理解，可在没有这些具体细节的情况下实践所述方面。举例来说，电路和结构可以在框图中示出以避免以不必要的细节混淆所述方面。在其它例子中，可不详细示出众所周知的电路、结构和技术以便不混淆本发明的方面。词语“例示性”在本文中用于意指“充当实例、例子或说明”。本文中描述为“示例性”的任何实施方案或方面未必应解释为比本发明的其它方面优选或有利。

概述

本文中所描述的一些方法和装置涉及计算标量乘法输出Z，其中Z＝k·P。方法和装置接收输入乘数k和底数P，并且将修改符s添加到输入乘数k以产生k'，其中无论k是奇数或偶数，添加相同的修改符s到输入乘数k以产生k'。方法和装置还计算中间标量乘法输出Z'，其中Z'＝k'·P，方法是使用包含属于数字集合D的数字k_i的序列的k'的数字展开式。根据一个实例，数字集合D＝{±1,±3,±5,±7,±9,±11,±13,±15}。另外，如果k'是奇数，那么方法和装置从Z'中减去s·P以获取标量乘法输出Z，或者如果k'是偶数，那么从Z'中减去(s+1)·P以获取标量乘法输出Z。所述标量乘数输出Z可用于密码安全算法中以确保数据安全。

固定执行流乘数再译码和标量乘法的示例性方法

图1说明根据本发明的一个方面的电子装置100的示意性框图。电子装置100可以为任何电子装置，其包含(但不限于)：无线通信装置、平板计算机、智能电话、有线电视机顶盒、膝上型计算机、桌上型计算机、智能手表、可穿戴光学头戴式显示器、服务器等。电子装置100可以包含至少一个处理电路102(处理器、中央处理单元(CPU)、应用处理单元(APU)等)、至少一个存储器电路104、至少一个显示器106、I/O装置108和/或至少一个通信接口110。这些组件102、104、106、108、110可以(例如)通过通信总线112通信耦合到彼此。

处理电路102可大体上执行存储在存储器电路104中的软件和指令。处理电路102还可包含执行密码安全算法的密码电路112。举例来说，密码电路112可以产生密码安全密钥(例如，对称密钥、不对称公共私有密钥对等)、产生密码数字签名、认证或验证数字签名和/或凭证等。如下文将更详细地解释，执行上述密码安全算法中的一或多个可以使得密码电路112执行标量乘法的快速、存储器有效、安全且稳健的算法。

存储器电路104可以包含易失性存储器和非易失性存储器，并且可以存储通过处理电路102执行的软件和指令。举例来说，存储器电路104可以存储与执行本文中所描述的密码安全算法和/或过程中的任一者相关联的指令。

显示器106可以为任何显示装置，其包含(但不限于)：液晶显示器(LCD)、等离子体屏幕、平板监测器，和/或触摸屏显示器。举例来说，它可以是智能电话、工作台、膝上型计算机、智能手表等上的显示器。此外，I/O装置108可以包含键盘、鼠标、触摸屏显示器、状态指示灯、扬声器和/或按钮。

通信接口110可允许与其它电子装置短程和/或远程通信。举例来说，通信接口110可以包含一或多个无线通信接口。此类无线通信接口可允许短程或远程通信协议，所述短程或远程通信协议包含(但不限于)：蜂窝式通信、等。通信接口110也可以允许与其它电子装置有线通信，例如，直接地和/或通过一或多个通信网络。

图2说明根据本发明的一个方面的密码电路112的示例性框图。密码电路112可以包含标量乘法电路202和密码算法模块204。密码模块204可以执行多种密码算法，所述密码算法包含(但不限于)：产生密钥206的密钥产生函数和产生和/或认证/验证数字签名208的数字签名函数。如下文中更详细地解释，标量乘法电路202可以接收输入参数且提供输出值。具体地说，标量乘法电路202可以接收输入乘数k和底数P，并且提供椭圆曲线点乘法输出Z＝k·P。标量乘法电路202使用数字电路以如本文中所述的快速、存储器有效、安全且稳健的方式执行运算k·P。

图3说明根据一个方面在标量乘法电路202(参见图2)处执行的算法300。参考图3，将固定的非零整数值s加到302输入乘数k以产生k'。因此，k'＝k+s。随后，将经调整的乘数k'输入到第一算法(例如，算法X)304，最终输出k·P。根据算法X 304，其中c∈{0,1}，值k_i属于数字集合D>i∈D)，且值l等于k_i中的数字的个数。根据一个实例，数字集合D＝{±1,±3,±5,…,±2^w-1}，且w≥1。展开式可以使用第二算法(例如，算法Y)308计算。

对于算法Y 308，其中每个整数k_i满足0≤k_i<2^w，且c初始地设置成等于0，且因此因此，对于i＝l至减小到0，如下执行312：

k_i:＝k_i-2^wc；

如果k_i是偶数，那么：

k_i:＝k_i+1；

c:＝1；

否则：

c:＝0

这一运算312可以无分支执行为c:＝1-LSB(k_i)以及k_i:＝k_i+c。运算LSB(k_i)返回k_i的最低有效位。接下来，返回314数字序列(k_l,k_l-1,…,k₁,k₀)和进位c。

返回到算法X 304，针对所有d∈D的d·P是预先计算316的且存储在表中。如果d和-d两者都在数字集合D中，那么简单地预先计算且存储d·P，并且-d·P可以简单地衍生自d·P。接下来，Z'可以设置成标识元素，Z'＝0。因此，对于i＝l至减小到i＝0，如下执行318：

执行w次倍增运算Z':＝2·Z'；

Z':＝Z'+(k_i·P)。

其中k_i·P或者从表中检索出或从来自-k_i·P中的运行中计算出(如果后者存储在表中)，其随后返回Z'。可以通过首先初始化Z'为Z':＝k_i·P等效地执行运算318，并且随后对于i＝l-1至减小到i＝0执行：

执行w次倍增运算Z':＝2·Z'；

Z':＝Z'+(k_i·P)。

值Z'随后用于计算Z＝k·P。这可以通过320完成：如果k'是奇数，那么简单地将-(s·P)加到Z'以获取Z，或者如果k'是偶数，那么将-((s+1)·P)加到Z'以获取Z。也就是说，如果k'是奇数，那么从Z'中减去s·P以获取Z，或者如果k'是偶数，那么从Z'中减去(s+1)·P以获取Z。因此，算法X 304的输出322是Z＝k·P。作为一个实例，如果s＝1，那么在k'是奇数的情况下将-P加到Z'以获取Z；并且在k'是偶数的情况下将-2P加到Z'以获取Z。作为另一实例，如果s＝2，那么在k'是奇数的情况下将-2P加到Z'以获取Z；并且在k'是偶数的情况下将-3P加到Z'以获取Z。

值得注意的是，在上述算法中将修改符s加到k确保：无论k是偶数还是奇数，在算法300的结尾处执行减法运算以获取Z＝k·P。因此，对于给定值w的算法300的数学运算的顺序将为：倍增Z'的当前值w次且加上k_i·P、倍增Z'的当前值w次且加上k_i·P、……、倍增Z'的当前值w次且加上k_i·P以及减去s·P或(s+1)·P。换句话说，数学运算的顺序是倍增w次随后加上、倍增w次随后加上、……，以及最后减去(即，加上)。最后的减法运算是“有效运算”，因为它对算法300的输出值有实际影响并且它不是“虚拟运算”。

相比之下，如果没有添加修改符s到k(例如，Theriault的现有技术方法)且k是奇数，那么算法结束(而无需最后的减去/加法运算)，并且如果k是偶数，那么需要最后的减去/加法运算以校正结果。这意味着当k是奇数时需要运算的一个顺序(倍增w次随后加上、倍增w次随后加上、……、倍增w次随后加上)，并且当k是偶数时需要运算的不同顺序(倍增w次随后加上、倍增w次随后加上、……、倍增w次随后加上、加上/减去)。运算中的差异可用于旁信道攻击以推断和揭露关于k值的信息。即使当k是奇数时在Theriault算法的结尾处使用虚拟加法/减法运算，此类虚拟运算也对算法的最终输出值没有影响，并且因此不能安全的抵抗故障攻击。

此外，在不考虑k是奇数还是偶数的情况下，相同的修改符值s被添加到k以获取k'。因此，取决于k'是奇数还是偶数从Z'中减去不同的值(例如，(s·P)或((s+1)·P))以获取Z。根据本发明的一个方面，不同值s可以添加到在标量乘法电路202处接收到的每个乘数值k。因此，作为一个非限制性、非排他性的实例，s＝1可用于接收到的第一乘数值k_A，并且不同值s＝2可用于接收到的另一个随后乘数值k_B。

图4A和4B说明根据一个方面可以在标量乘法电路202(参见图2)处执行的方法400的流程图。参考图4A，可以选择402修改符值s。接下来，接收404输入乘数k以及底数P。随后，通过添加406修改符值s到乘数k产生经调整的乘数值k'。因此，k'＝k+s。在不考虑k是偶数还是奇数的情况下相同修改符值s被添加到k。接下来，经调整的修改符k'被写入/设置408为根据等式(1)的展开式：

其中c∈{0,1}并且值k_i来自数字集合D(即，k_i∈D)。根据一个实例，数字集合D＝{±1,±3,±5,…,±2^w-1}。随后，多个值d·P得到预先计算410并且被存储在表中，其中d∈D。根据一个方面，针对每个值|d|仅d·P或-d·P是预先计算和存储的，这是因为按需要在运行中-d·P可以简单地从d·P中确定，并且d·P可以简单地从-d·P中确定。

图5说明存储值d·P的示例性预先计算表500。在示出的实例中，可假定数字集合D包含多个整数值{d₀,d₁,…,d_n}。表500随后存储针对i＝0到i＝n的多个值d_i·P。表500也可以存储针对至少一个整数中间值m的m·P，其中m大于数字集合D中的最小值并且小于数字集合D中的最大值。根据一个方面，修改符值s和s+1可以都在集合{d₀,d₁,…,d_n}∪{m}中。因此，s和s+1可以为负或正但是并不为零(0)。然而，其中s和s+1为负值的情况可以产生k'≤0。应当采取预防措施以确保无法出现这种情况。此外，对于s和s+1具有负值对于在协议中使用可能是不切实际的，例如，椭圆曲线数字签名算法(ECDSA)，其中k的范围无法被限于k>s。

返回参考图4A，多个值(k_l,k_l-1,…,k₁,k₀)通过针对i＝l至减小到i＝0执行/进行412产生，其中c初始地被设置成等于0：

k_i:＝k_i-2^wc；

如果k_i是偶数，那么：

k_i:＝k_i+1；

c:＝1；

否则：

c:＝0。

窗口值w是等于或大于一(1)的整数值。此运算412可以无分支执行为(c初始地设置成等于0)：

k_i:＝k_i-2^wc；

c:＝1-LSB(k_i)；

k_i:＝k_i+c。

参考图4B，中间输出值Z'＝k'·P接下来通过首先初始化414Z'到群组的标识元素(例如，Z'＝0)计算。随后，对于i＝l至减小到i＝0中的每一个，执行以下运算416：

执行w次：Z':＝2·Z'(即，倍增值Z'w次)；

Z':＝Z'+k_i·P。

对于i的每个值，值k_i·P是从存储多个值d·P的表(例如，在图5中的表500)中检索到或衍生自此类表值。等效地，Z'可以初始化为Z'＝k_l·P(k_l·P也可以从表500中检索到)，并且随后对于i＝l-1至减小到i＝0中的每一个值执行以下运算416：

执行w次：Z':＝2·Z'(即，倍增值Z'w次)；

Z':＝Z'+k_i·P。

最后，通过执行418从中间输出值Z'中确定输出值Z：

如果k'是奇数，那么Z＝Z'+[s·P]；以及

如果k'是偶数，那么Z＝Z'+[(s+1)·P]。

图6A和6B说明针对k、w、D和s的样本数值的上述算法的示例性执行。举例来说，在所说明的实例中，k＝31415、w＝4、D＝{±1,±3,±5,±7,±9,±11,±13,±15}且s＝1。过程600可以包含首先选择602修改符值s，在此情况下其等于1。接收604到输入乘数值k＝31415以及底数值P。接下来，基于k'＝k+s产生606经调整的乘数k'，并且因此由于s＝1，所以k'＝31416。在底数16中，符号k'＝(7 10 11 8)₁₆。接下来，针对|d|∈D的每个值计算出|d|·P或-|d|·P，并且将其存储在表中。因此，作为仅仅一个实例，预先计算608值{P,-3·P,5·P,7·P,-9·P,11·P,-13·P,15·P}且将其存储在表中。可以从存储的值中轻易地获取相反符号值-P,3·P,-5·P,-7·P,9·P,-11·P,13·P,-15·P。根据一个方面，也可以预先计算值m·P且将其存储在表中，其中m＝2。也可以预先计算且存储-15·P与15·P两者之间的其它值。

随后，对于i＝3至减小到i＝0，可以通过执行610获取重新编码的数字(k₃,k₂,k₁,k₀)，其中初始地c:＝0：

k_i:＝k_i-2^wc；

如果k_i是偶数，那么：

k_i:＝k_i+1；

c:＝1；

否则：

c:＝0。

这产生重新编码的值(7,11,-5,9)₁₆且进位c＝1。实际上，7*16³+11*16²-5*16+9-1＝31416。

参考图6B，中间标量乘法输出Z'初始化612为Z'＝k₃·P，其等于7·P。可以从存储在表中的值获取值7·P。接下来，对于i＝2至减小到i＝0，通过执行614计算中间标量乘法输出Z'：

Z':＝2·Z'(执行4次)；

Z':＝Z'+k_i·P。

因此，在所说明的实例中Z'＝DDDD(DDDD(DDDD(7·P)+11·P)-5·P)+9·P，其中运算DDDD(x)是指点倍增操作数x四(4)次。值11·P、-5·P和9·P可以直接地从存储在表中的值获取或衍生自存储在表中的值。最后，可以通过执行616从Z'获取标量乘法输出Z：

如果k'是奇数，那么Z＝Z'+[-s·P]；或者

如果k'是偶数，那么Z＝Z'+[-(s+1)·P]。

因此，在所说明的实例中，由于k'是偶数(k'＝31416)，所以Z＝Z'-2·P。值-2·P也可以衍生自存储在表中的值(例如，2·P)。

以此方式执行固定数量和类型的操作以获取标量输出乘法值Z，所述操作包含DDDD随后加上、DDDD随后加上、DDDD随后加上、随后减去。也就是说，倍增4次值7·P随后加上11·P，倍增4次所得的值随后加上-5·P，倍增4次所得的值随后加上9·P，并且随后减去2·P(即，加上-2·P)。

图7A和7B说明对k、w、D和s的样本数值的上述算法的示例性执行。举例来说，在所说明的实例中，k＝27182、w＝4、D＝{±1,±3,±5,±7,±9,±11,±13,±15}且s＝1。过程700可以包含首先选择702修改符值s，在此情况下其等于1。接收704到输入乘数值k＝27182以及底数值P。接下来，基于k'＝k+s产生706经调整的乘数k'，并且因此由于s＝1，所以k'＝27183。在底数16中，符号k'＝(6 10 2 15)₁₆。接下来，针对|d|∈D的每个值计算出|d|·P或-|d|·P，并且将其存储在表中。因此，作为仅仅一个实例，预先计算708值{P,3·P,5·P,7·P,9·P,11·P,13·P,15·P}且将其存储在表中。可以从存储的值中轻易地获取相反符号值-P,-3·P,-5·P,-7·P,-9·P,-11·P,-13·P,-15·P。根据一个方面，也可以预先计算值m·P且将其存储在表中，其中m＝2。也可以预先计算且存储-15·P与15·P两者之间的其它值。

随后，对于i＝3至减小到i＝0，可以通过执行710获取重新编码的数字(k₃,k₂,k₁,k₀)，其中初始地c:＝0：

k_i:＝k_i-2^wc；

如果k_i是偶数，那么：

k_i:＝k_i+1；

c:＝1；

否则：

c:＝0。

这产生重新编码的值(7,-5,-13,-1)₁₆且进位c＝0。实际上，7*16³-5*16²-13*16-1＝27183。

参考图7B，中间标量乘法输出Z'初始化712为Z'＝k₃·P，其等于7·P。可以从存储在表中的值获取值7·P。接下来，对于i＝2至减小到i＝0，通过执行714计算中间标量乘法输出Z'：

Z':＝2·Z'(执行4次)；

Z':＝Z'+k_i·P。

因此，在所说明的实例中，Z'＝DDDD(DDDD(DDDD(7·P)-5·P)-13·P)-P。值-5·P、-13·P和-P可以全部衍生自存储在表中的值。最后，可以通过执行616从Z'获取标量乘法输出Z：

如果k'是奇数，那么Z＝Z'+[-s·P]；或者

如果k'是偶数，那么Z＝Z'+[-(s+1)·P]。

因此，在所说明的实例中，由于k'是偶数(k'＝27183)，所以Z＝Z'-P。值-P也可以衍生自存储在表中的值(例如，P)。

以此方式执行固定数量和类型的操作以获取标量输出乘法值Z，所述操作包含DDDD随后加上、DDDD随后加上、DDDD随后加上、随后减去。也就是说，倍增4次值7·P随后加上-5·P，倍增4次所得的值随后加上-13·P，倍增4次所得的值随后加上-P，并且随后减去P(即，加上-P)。

图8A和8B说明对k、w、D和s的样本数值的上述算法的示例性执行。举例来说，在所说明的实例中，k＝18746、w＝4、D＝{±1,±3,±5,±7,±9,±11,±13,±15}且s＝2。过程800可以包含首先选择802修改符值s，在此情况下其等于2。接收804到输入乘数值k＝18746以及底数值P。接下来，基于k'＝k+s产生806经调整的乘数k'，并且因此由于s＝2，所以k'＝18748。在底数16中，符号k'＝(4 9 3 12)₁₆。接下来，针对|d|∈D的每个值计算出|d|·P或-|d|·P，并且将其存储在表中。因此，作为仅仅一个实例，预先计算808值{-P,-3·P,-5·P,-7·P,-9·P,-11·P,-13·P,-15·P}且将其存储在表中。可以从存储的值中轻易地获取相反符号值P,3·P,5·P,7·P,9·P,11·P,13·P,15·P。根据一个方面，也可以预先计算值m·P且将其存储在表中，其中m＝2。也可以预先计算且存储-15·P与15·P两者之间的其它值。

随后，对于i＝3至减小到i＝0，可以通过执行810获取重新编码的数字(k₃,k₂,k₁,k₀)，其中初始地c:＝0：

k_i:＝k_i-2^wc；

如果k_i是偶数，那么：

k_i:＝k_i+1；

c:＝1；

否则：

c:＝0。

这产生重新编码的值(5,-7,3,13)₁₆且进位c＝1。实际上，5*16³-7*16²+3*16+13＝18749。

参考图8B，中间标量乘法输出Z'初始化812为Z'＝k₃·P，其等于5·P。值5·P可以衍生自存储在表中的值(-5·P)。接下来，对于i＝2至减小到i＝0，通过执行814计算中间标量乘法输出Z'：

Z':＝2·Z'(执行4次)；

Z':＝Z'+k_i·P。

因此，在所说明的实例中，Z'＝DDDD(DDDD(DDDD(5·P)-7·P)+3·P)+13·P。-7·P、3·P和13·P可以都从存储在表中的值获取或衍生自存储在表中的值。最后，可以通过执行616从Z'获取标量乘法输出Z：

如果k'是奇数，那么Z＝Z'+[-s·P]；或者

如果k'是偶数，那么Z＝Z'+[-(s+1)·P]。

因此，在所说明的实例中，由于k'是奇数(k'＝18748)，所以Z＝Z'-3·P。值-3·P也可以从存储在表中的值获取。

以此方式执行固定数量和类型的操作以获取标量输出乘法值Z，所述操作包含DDDD随后加上、DDDD随后加上、DDDD随后加上、随后减去。也就是说，倍增4次值5·P随后加上-7·P，倍增4次所得的值随后加上3·P，倍增4次所得的值随后加上13·P，并且随后减去3·P(即，加上-3·P)。

图9说明根据本发明的一个方面可在处理电路处执行的方法900的流程图。首先，接收902输入乘数k和底数P。随后，将修改符s添加904到输入乘数k以产生k'，其中无论k是奇数或偶数，将相同的修改符s添加到输入乘数k以产生k'。接下来，计算906中间标量乘法输出Z'，其中Z'＝k'·P，方法是使用包含属于数字集合D的数字k_i的序列的k'的数字展开式。随后，908，如果k'是奇数，那么从Z'中减去s·P以获取标量乘法输出Z，或者如果k'是偶数，那么从Z'中减去(s+1)·P以获取标量乘法输出Z。910，标量乘数输出Z可用于密码安全算法中以确保数据安全。

图10说明根据本发明的一个方面的示例性标量乘法电路1000的示意性框图。标量乘法电路1000可以包含乘数k和底数P接收电路1002、经调整的乘数k'产生电路1004、中间标量输出产生电路1006和标量输出产生电路1008。一或多个电路组件1002、1004、1006、1008可以(例如)通过通信总线1010通信耦合到彼此。

乘数k和底数P接收电路1002是可为硬接线且具体地说被设计成接收输入乘数k和底数P的电路。因此，乘数k和底数P接收电路1002可以用作用于接收输入乘数k和底数P的装置的一个实例。类似地，经调整的乘数产生电路1004是可为硬接线且具体地说被设计成将修改符s添加到输入乘数k以产生k'(无论k是奇数或偶数)的电路。因此，经调整的乘数产生电路1004可以用作用于将修改符s添加到输入乘数k以产生k'(无论k是奇数或偶数)的装置的一个实例。

中间标量输出产生电路1006是可为硬接线且具体地说被设计成计算中间标量乘法输出Z'的电路，其中Z'＝k'·P，方法是使用包含属于数字集合D的数字k_i的序列的k'的数字展开式。因此，中间标量输出产生电路1006是用于计算中间标量乘法输出Z'的装置的一个实例，其中Z'＝k'·P，方法是使用包含属于数字集合D的数字k_i的序列的k'的数字展开式。标量输出产生电路1008是可为硬接线的电路，并且具体地说所述电路被设计成：如果k'是奇数，那么从Z'中减去s·P以获取标量乘法输出Z，或者如果k'是偶数，那么从Z'中减去(s+1)·P以获取标量乘法输出Z。因此，标量输出产生电路1008是某一装置的一个实例，所述装置用于：如果k'是奇数，那么从Z'中减去s·P以获取标量乘法输出Z，或者如果k'是偶数，那么从Z'中减去(s+1)·P以获取标量乘法输出Z。

在图1、2、3、4、5、6、7、8、9和/或10中所说明的组件、步骤、特征和/或功能中的一或多者可经重新布置和/或组合为单个组件、步骤、特征或功能，或实施于若干组件、步骤或功能中。在不脱离本发明的情况下，还可添加额外的元件、组件、步骤和/或功能。图1、2和/或10中所说明的设备、装置和/或组件可经配置以执行在图3、4A、4B、5、6A、6B、7A、7B、8A和/或8B中所描述的方法、特征或步骤中的一或多者。本文中所描述的算法还可有效地实施于软件中和/或嵌入于硬件中。

此外，在本发明的一个方面中，在图1中说明的处理电路102可以是专业处理器(例如，专用集成电路(例如，ASIC))，其具体地说被设计成和/或硬接线以执行在图3、4A、4B、5、6A、6B、7A、7B、8A和/或8B和相关文本中所描述的算法、方法和/或步骤。因此，此类专业处理器(例如，ASIC)可以是用于执行在图3、4A、4B、5、6A、6B、7A、7B、8A和/或8B中所描述的算法、方法和/或步骤的装置的一个实例。

此外，应注意，可以将本发明的各方面描述为过程，所述过程被描绘为流程图、流图、结构图或框图。虽然流程图可将操作描述为顺序过程，但许多操作可并行或同时执行。此外，操作的顺序可重新布置。当过程的操作完成时，所述过程终止。过程可以对应于方法、函数、步骤、子例程、子程序等。当过程对应于函数时，过程的终止对应于函数返回到调用函数或主函数。

此外，存储媒体可表示用于存储数据的一或多个装置，包含只读存储器(ROM)、随机存取存储器(RAM)、磁盘存储媒体、光学存储媒体、快闪存储器装置和/或其它机器可读媒体以及处理器可读媒体，和/或用于存储信息的计算机可读媒体。术语“机器可读媒体”、“计算机可读媒体”和/或“处理器可读媒体”可包含(但不限于)非暂时性媒体(例如，便携式或固定存储装置)、光学存储装置以及能够存储或容纳指令和/或数据的各种其它媒体。因此，本文中所描述的各种方法可以完全或部分地通过可存储在“机器可读媒体”、“计算机可读媒体”和/或“处理器可读媒体”中且由一或多个处理器、机器和/或装置执行的指令和/或数据来实施。

此外，本发明的方面可由硬件、软件、固件、中间件、微码或其任何组合来实施。当以软件、固件、中间件或微码实施时，用以执行必要任务的程序代码或代码段可存储在机器可读媒体中，例如，存储媒体或其它存储装置。处理器可以执行必要任务。代码段可以表示过程、函数、子程序、程序、例程、子例程、模块、软件包、类，或指令、数据结构或程序语句的任何组合。一个代码段可通过传递和/或接收信息、数据、自变量、参数或存储器内容耦合到另一代码段或硬件电路。信息、自变量、参数、数据等可经由包含存储器共享、消息传递、令牌传递、网络传输等任何合适的手段传递、转发或传输。

结合本文中所揭示的实例描述的各种说明性逻辑块、模块、电路、元件和/或组件可使用通用处理器、数字信号处理器(DSP)、专用集成电路(ASIC)、现场可编程门阵列(FPGA)或其它可编程逻辑组件、离散门或晶体管逻辑、离散硬件组件或其被设计成执行本文中所描述的功能的任何组合来实施或执行。通用处理器可为微处理器，但在替代方案中，处理器可以为任何常规的处理器、控制器、微控制器或状态机。处理器还可以实施为计算组件的组合，例如，DSP与微处理器的组合、多个微处理器的组合、一或多个微处理器与DSP核心的结合，或任何其它此类配置。

结合本文中所揭示的实例描述的方法或算法可以处理单元、编程指令或其它方向的形式直接体现在硬件、可由处理器执行的软件模块或两者的组合中，且可包含于单个装置中或跨越多个装置而分布。软件模块可以驻留在RAM存储器、快闪存储器、ROM存储器、EPROM存储器、EEPROM存储器、寄存器、硬盘、可移动磁盘、CD-ROM，或所属领域中已知的任何其它形式的存储媒体中。存储媒体可耦合到处理器，使得处理器可从存储媒体读取信息且将信息写入到存储媒体。在替代方案中，存储媒体可集成到处理器。

所属领域的技术人员将进一步理解，结合本文所揭示的方面描述的各种说明性逻辑块、模块、电路和算法步骤可以实施为电子硬件、计算机软件或两者的组合。为了清楚地说明硬件与软件的此可互换性，上文已大体就其功能性而言描述了各种说明性组件、块、模块、电路和步骤。此功能性是实施为硬件还是软件取决于特定应用和施加于整个系统的设计约束。

本文中所描述的本发明的各种特征可在不脱离本发明的情况下实施于不同系统中。应注意，本发明的上述方面仅为实例，且不应解释为限制本发明。本发明的各方面的描述意图为说明性的，且不限制权利要求书的范围。因此，本发明的教示可容易应用于其它类型的设备，且所属领域的技术人员将明白许多替代方案、修改及变化。