一种可重构椭圆曲线密码处理器

摘要

本发明公开了一种可重构椭圆曲线密码处理器，包括：控制单元，用于完成指令存取、指令译码、指令存储器地址生成及协调处理器内部指令与外部用户命令的正确执行；数据通路单元，包括：向量寄存器堆子单元，用于存储待进行椭圆密码处理的数据；多个向量功能子单元，用于根据所述控制单元的协调指令对椭圆密码处理的数据进行相应运算处理；配置寄存器子单元，用于接收所述控制单元输出的可重构配置指令，对所述功能子单元的运算进行可重构配置；回写子单元，用于将所述功能单元的输出数据及回写数据回传至相应向量寄存器堆；输入/输出单元，用于实现待进行椭圆密码处理的数据的输入和处理结果的输出。以提高椭圆曲线密码处理器的处理灵活性和效率。

权利要求

1.一种可重构椭圆曲线密码处理器，其特征在于，所述处理器包括：

控制单元，用于完成指令存取、指令译码、指令存储器地址生成及协调处理器内部指令与外部用户命令的正确执行；

数据通路单元，包括：向量寄存器堆子单元，用于存储待进行椭圆密码处理的数据；多个向量功能子单元，用于根据所述控制单元的协调指令对所述待进行椭圆密码处理的数据进行相应运算处理；配置寄存器子单元，用于接收所述控制单元输出的可重构配置指令，对所述向量功能子单元的运算进行可重构配置；回写子单元，用于将所述向量功能子单元的输出数据及回写数据回传至相应向量寄存器堆；

输入/输出单元，用于实现待进行椭圆密码处理的数据的输入和处理结果的输出。

2.根据权利要求1所述的可重构椭圆曲线密码处理器，其特征在于，所述向量寄存器堆子单元包括：多簇向量寄存器堆。

3.根据权利要求2所述的可重构椭圆曲线密码处理器，其特征在于，每一簇向量寄存器堆包括多个通用向量寄存器、多个基点向量寄存器；则，对于所述每一簇向量寄存器堆存在一个或多个所述向量功能子单元。

4.根据权利要求1所述的可重构椭圆曲线密码处理器，其特征在于，所述向量功能子单元包括：有限域运算模块及逻辑运算模块。

5.根据权利要求4所述的可重构椭圆曲线密码处理器，其特征在于，所述有限域运算模块包括：模加/减有限域运算子模块、模乘有限域运算子模块及模逆有限域运算子模块。

6.根据权利要求1所述的可重构椭圆曲线密码处理器，其特征在于，所述控制单元还用于采用超长指令字并行指令结构进行指令存取及指令译码。

7.根据权利要求5所述的可重构椭圆曲线密码处理器，其特征在于，所述模加/减有限域运算子模块具体为：针对素数域与二元域、基于字进行运算的模加/减器。

8.根据权利要求5所述的可重构椭圆曲线密码处理器，其特征在于，所述模乘有限域运算子模块具体为：针对素数域与二元域、采用字级-字级类型的FIOS模乘算法实现。

9.根据权利要求5所述的可重构椭圆曲线密码处理器，其特征在于，所述模逆有限域运算子模块具体为：针对素数域与二元域、采用Montgomery模逆算法实现。

说明书

一种可重构椭圆曲线密码处理器

技术领域

[0001] 本发明涉及电子信息安全技术领域，更具体地说，涉及一种可重构椭圆曲线密码处理器。

背景技术

[0002] 在当今信息时代，随着电子商务，电子政务，军事通信的蓬勃发展，信息安全问题受到了人们广泛的关注。公钥密码体制有效地解决了在公共信道上保护信息的抗抵赖性、身份认证、密钥分发等问题。由于基于椭圆曲线离散对数问题(ECDLP)的椭圆曲线密码(ECC，Elliptic Curve Cryptography)已经被证明是一种比RSA更安全、计算上更高效的公钥密码体制。因此，ECC逐步取代RSA成为下一代公钥密码标准。

[0003] 椭圆曲线密码算法的实现通常有软件和硬件两种方式。采用软件方式即通用CPU方式实现具有灵活性高、维护容易，升级方便等优点，但由于通用微处理器指令系统的局限性，使该实现方式下的性能难以达到高速处理需求；采用专用硬件实现ECC密码处理时，虽然可使密码处理性能达到最高，但由于该方式只是针对特定的一种或几种特定的ECC密码算法进行硬件优化，因而导致了其灵活性差，不便于进行二次开发。一旦ECC密码算法或标准发生改变，ECC密码算法专用硬件就需要重新设计生产。造成了密码芯片品种多、装备成本高，给固定ECC算法芯片的使用带来了很大的局限性。

[0004] 由于灵活性与高效性是密码处理追求的两大主要目标。近年来采用可重构计算技术和专用指令系统的微处理器(ASIP)来实现密码处理成为研究的热点。例如：2003年5n月，美国Sun公司设计出支持GF(2)域上任意曲线的椭圆曲线密码专用指令集处理器，在该处理器上可以支持NIST推荐的15个标准椭圆曲线及其它定义在二元扩域上的任意曲线，并且性能比较通用微处理器改善明显，但对素数域支持不够。2004年奥地利格拉茨大学J.Grobschadl等通过在MIPS32处理器核中添加乘累加单元扩展微处理器指令集实现了ECC的加速。这种实现方式占用资源少，更加灵活，但速度较慢。H.Eberle等采用类似的思想在SPARC处理器上扩展指令集，速度有了较大提高。2006年比利时鲁汶大学K.Sakiyama等采用了指令级并行体系结构设计了ECC协处理器，实现了有限域层上的并行处理，速度提升明显，但只能实现固定的曲线，灵活性受限。2003年IBM公司日本研究实验室基于通用微处理器+协处理器体系结构，采用0.13μm CMOS标准单元库设计了一款可伸缩双域椭圆曲线密码处理器，其协处理器核心运算模块均基于32-bit×32-bit双域乘法器，能够n
支持GF(p)域上的任意素数和GF(2)域上任意的不可约多项式，该协处理器具有较高的灵活性，但该处理器无法提供专用的有限域运算指令，对有限域运算的调度缺乏灵活性；2008年台湾国立清华大学的Jyu-Yuan Lai根据该思想，也提出了类似的实现方案，其核心是四个并行的双域乘法器，可以根据实际需要在面积和速度之间进行折衷，但同样缺乏专用的有限域运算指令对有限域层次的调度灵活性不够；2005年复旦大学的曾晓洋等采用了通用ARM处理器+协处理器体系架构方案，利用扩展微代码指令两级译码方式设计了硬件可配置ECC密码协处理器；2006年国防科学技术大学的童元满、2008年解放军信息工程大学的仲先海也给出了类似的ECC实现方案。这类实现方式利用协处理器作为加速部件，利用通用微处理器进行调度控制，实现了椭圆曲线密码处理性能的提升。但该种方式依赖于通用微处理器对协处理器的调度，并且协处理器的专用有限域运算密码指令通过译码电路产生对于用户不可见，造成用户开发困难。

[0005] 可见，尽管可重构计算技术在一定程度上提升了专用ECC密码芯片的灵活性，专用指令密码处理器设计技术使微处理器在ECC密码处理性能上有了一定程度提高，但是采用这些新技术仍然无法满足现代网络通信对ECC密码处理实现方式灵活性和高速性的要求。

[0006] 因此，现有技术无法从根本上缓解ECC密码处理的灵活性与性能之间的矛盾。

发明内容

[0007] 有鉴于此，本发明实施例提供一种可重构椭圆曲线密码处理器，实现提高椭圆曲线密码处理器的处理性能和处理效率。

[0008] 本发明实施例提供一种可重构椭圆曲线密码处理器，所述处理器包括：控制单元，用于完成指令存取、指令译码、指令存储器地址生成及协调处理器内部指令与外部用户命令的正确执行；

[0009] 数据通路单元，包括：向量寄存器堆子单元，用于存储待进行椭圆密码处理的数据；多个向量功能子单元，所述用于根据所述控制单元的协调指令对所述待进行椭圆密码处理的数据进行相应运算处理；配置寄存器子单元，用于接收所述控制单元输出的可重构配置指令，对所述功能子单元的运算进行可重构配置；回写子单元，用于将所述功能单元的输出数据及回写数据回传至相应向量寄存器堆；

[0010] 输入/输出单元，用于实现待进行椭圆密码处理的数据的输入和处理结果的输出。

[0011] 优选的，所述向量寄存器堆子单元包括：多簇向量寄存器堆。

[0012] 优选的，每一簇向量寄存器堆包括多个通用向量寄存器、多个基点向量寄存器；则，对于所述每一簇向量寄存器堆存在一个或多个所述向量功能子单元。

[0013] 优选的，所述向量功能子单元包括：有限域运算模块及逻辑运算模块。

[0014] 优选的，所述有限域运算模块包括：模加/减有限域运算子模块、模乘有限域运算子模块及模逆有限域运算子模块。

[0015] 优选的，所述控制单元还用于采用超长指令字并行指令结构进行指令存取及指令译码。

[0016] 优选的，所述模加/减有限域运算子模块具体为：针对素数域与二元域、基于字进行运算的模加/减器。

[0017] 优选的，所述模乘有限域运算子模块具体为：针对素数域与二元域、采用字级-字级类型的FIOS模乘算法实现。

[0018] 优选的，所述模逆有限域运算子模块具体为：针对素数域与二元域、采用Montgomery模逆算法实现。

[0019] 同现有技术相比，本发明提供的技术方案通过向量寄存器堆和向量功能子单元实现数据级并行运算，能够大大提升系统整体工作性能。本发明的结构在充分利用VLIW指令级并行性基础上，进一步发掘了椭圆曲线密码算法中存在的数据级并行性，通过采用超长指令字与向量处理相结合的体系结构支持了指令级和数据级的并行，能够有效提升ECC密码专用指令集处理器的计算性能。

附图说明

[0020] 为了更清楚地说明本发明实施例的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍。显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0021] 图1为现有技术中椭圆曲线密码运算体系示意图；

[0022] 图2为本发明实施例提供的椭圆曲线密码处理器结构示意图；

[0023] 图3为现有技术中的ECDSA签名验证并行调度算法流程示意图；

[0024] 图4为现有技术中的二进制点乘算法流程示意图；

[0025] 图5为本发明实施例提供的可重构ECC密码处理器体系结构模型示意图；

[0026] 图6为本发明实施例提供的寄存器堆示意图；

[0027] 图7为本发明实施例采用的Clustered VLIW结构示意图；

[0028] 图8为本发明实施例提供的一种分离分簇式寄存器堆示意图；

[0029] 图9为本发明实施例提供的可重构椭圆曲线密码处理器体系结构电路结构示意图；

[0030] 图10为本发明实施例提供的椭圆曲线密码处理器指令结构示意图；

[0031] 图11为本发明实施例提供的O类型和C类型指令束结构示意图。

具体实施方式

[0032] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0033] 椭圆曲线密码体制是建立在有限域椭圆曲线有理点上的新一代公钥密码体制，是基于有限域上椭圆曲线离散对数的困难问题。在密码学中，最常用的域一般为素数域GF(p)n n或阶为2 的二元域GF(2)。椭圆曲线密码系统包括四个层次的运算，如图1所示。其中，椭圆曲线上群运算层的点乘运算是核心的运算，它通过调度曲线层点加和倍点运算服务来完成，同时又服务于上层的应用层运算，而点加和倍点运算是通过调度有限域上的基本算术实现的。

[0034] 从目前椭圆曲线密码处理器体系结构的研究状况来看，尽管有一些结构都采用专用指令的方式来实现椭圆曲线密码专用微处理器，并取得了一定成果，但在体系结构设计上大多采用RISC处理器体系结构，由于该体系结构不能支持指令级的并行，无法有效提升椭圆曲线密码处理性能。另一方面，采用通用处理器+协处理器体系结构实现的椭圆曲线密码处理器，协处理器作为主处理器的加速部件来使用的，硬件结构相对固定，无法提供专用的有限域运算指令，造成用户开发的灵活性不够。因此，椭圆曲线密码处理器在体系结构设计方面，性能与灵活性之间的矛盾尚未得到完全有效解决。主要体现在：

[0035] (1)性能改善不够明显

[0036] 为了提高通用处理器的执行密码处理的速度，部分椭圆曲线密码处理器体系结构是在确保通用微处理器体系结构不变的情况下，通过增加密码处理单元和扩展专用密码处理指令来实现。例如：J.Grobschadl通过在MIPS32处理器核中添加乘累加单元扩展微处理器指令集实现了ECC加速，由于MIPS32处理器体系结构自身并不适合椭圆曲线密码处理特点，指令集抽象不够充分，导致密码处理性能改善不够明显，密码处理性能仅能得到有限的提升。

[0037] (2)算法的广泛适应性不足

[0038] ECC密码应用范围广、标准多，椭圆曲线类型与椭圆曲线参数可选性强，群运算层与曲线层运算算法多样，有限域运算的实现方法异常丰富。很多椭圆曲线密码处理器体系结构只针对某个域上的椭圆曲线群特定参数长度的运算特点而设计，因此可以达到较好的加速功能。但这些处理器体系结构很难支持任意域上任意椭圆曲线群运算性能的提升，而且支持的参数长度有限。当更换椭圆曲线类型或椭圆曲线参数时，性能的下降十分明显。例n如：Sun公司设计的密码专用指令集处理器，只支持GF(2)域上任意曲线的椭圆曲线密码运算，无法实现素数域上椭圆曲线密码的处理，而且该结构不支持任意长度参数的运算。

[0039] 因此，本发明实施例技术方案提供的椭圆曲线密码处理器体系结构，能够将素数域与二元域统一在一个密码专用指令微处理器体系结构内，实现支持任意椭圆曲线群、任意不可约多项式以及参数长度可配置的椭圆曲线密码处理器，有效的提升椭圆曲线密码处理速度以及灵活性。

[0040] 下面首先对本发明提供的椭圆曲线密码处理器进行说明，参照图2所示，所述椭圆曲线密码处理器包括：

[0041] 控制单元，用于完成指令存取、指令译码、指令存储器地址生成及协调处理器内部指令与外部用户命令的正确执行；

[0042] 数据通路单元，包括：向量寄存器堆子单元，用于存储待进行椭圆密码处理的数据；多个向量功能子单元，所述用于根据所述控制单元的协调指令对所述待进行椭圆密码处理的数据进行相应运算处理；配置寄存器子单元，用于接收所述控制单元输出的配置指令，对所述功能子单元的运算进行配置；回写子单元，用于将所述功能单元的输出数据及回写数据回传至相应向量寄存器堆；

[0043] 输入/输出单元，用于实现待进行椭圆密码处理的数据的输入和处理结果的输出。

[0044] 本发明实施例提供的椭圆曲线密码处理器案通过向量寄存器堆实现数据级并行运算，能够大大提升系统整体工作频率。

[0045] 为了便于对本发明进一步的理解，下面结合本发明的具体实施方式对本发明进行详细描述。

[0046] 本发明实施例中，椭圆曲线密码处理器实际采用了可重构椭圆曲线密码处理器体系结构设计，该设计主要包括以下几个重要方面：

[0047] (1)椭圆曲线密码算法各运算层次并行调度算法设计

[0048] 椭圆曲线密码算法各运算层次并行调度算法是设计可并行的椭圆曲线密码处理器体系结构的依据与基础。设计各运算层次并行调度算法需要深入分析椭圆曲线密码算法，具体研究其应用层、群运算层、曲线层和有限域运算层各层次运算之间数据相关性，深入挖掘各层次运算存在并行性。

[0049] (2)椭圆曲线密码处理器体系结构设计

[0050] 椭圆曲线密码处理器是一种面向特定一类应用进行优化设计的处理器，其体系结构设计应当是立足通用微处理器体系结构，并且具有高度的针对性，体系结构应能更准确和高效地满足应用处理的需求。因此，在建立体系结构模型时应当充分考虑椭圆曲线密码处理特点，以提升处理器的指令级并行度为出发点，研究椭圆曲线密码处理的结构特征、存储特性、计算粒度、数据并行处理等特征。

[0051] (3)椭圆曲线密码处理器可重构功能单元设计

[0052] 功能单元是处理器的基本运算部件，它直接决定了处理器指令运算的效率，是可重构椭圆曲线密码处理器体系结构设计的关键技术。在面向椭圆曲线密码运算的处理器体系结构中，功能单元的设计应当密切结合椭圆曲线密码处理特点，采用高效灵活的有限域算法。同时根据可重构计算原理，采用可重构设计思想设计具备指令级可重构特性的椭圆曲线密码处理功能单元。

[0053] 要研究椭圆曲线密码算法是否具有可开发并行性，必须从椭圆曲线密码算法的各个层次和并行算法入手，从分析各层基本运算的数据相关性能开始，设计合适的并行调度算法，并结合资源占用等各种因素，研究最适合椭圆曲线密码算法的并行结构。

[0054] 椭圆曲线密码算法中顶层应用层对需要对点乘运算、点加运算以及各个有限域运算层进行调度。各顶层应用中使用到的点乘、点加、模乘、模加与模逆运算的次数如表1所示。

[0055] 表1椭圆曲线密码应用协议运算构成

[0056]

[0057] 从表1中可以看到，每种应用都调用了群运算层和有限域运算层的运算，而且大都算法都可以支持群运算层和有限域运算层的并行调度；例如签名验证算法应用使用了两次点乘运算，并且两次点乘运算可并行执行。下面选取一个典型的ECDSA签名验证协议为例，说明其并行调度的特性。

[0058] 假设Alice对消息进行签名并发送给Bob，Bob接收到消息后对签名进行验证。签名算法如下所示：

[0059]

[0060] 验证算法如下：

[0061]

[0062]

[0063] 该协议运算改进的并行调度流程如图3所示，

[0064] 从图3中可以看出，Alice或Bob可以进行两个点乘并行的计算，并且点乘运算可以和有限域运算同时执行。

[0065] 因此，可以得出顶层应用层可以在群运算层之间、群运算层和有限域运算层之间并行调度。

[0066] 在椭圆曲线密码算法体制中，群运算层中的点乘运算是椭圆曲线密码算法中的主要运算，是由点加和倍点运算组成。目前常用的主要有以下几种点乘算法：二进制(Double-and-Add)点乘算法、w-ary点乘算法、NAF点乘算法、固定窗口点乘算法和Montgomery点乘算法。

[0067] 通过对这些点乘调度算法的分析得出部分点乘算法具有并行调度曲线层运算的特点，可以开发曲线层上点加和倍点的并行性。下面以常见的从右到左Double-and-Add点乘算法为例分析其并行调度可行性。从右到左扫描二进制double-and-add点乘调度算法如算法3所示。

[0068]算法3：从右到左二进制double-and-add点乘调度算法
输入：k＝(km-1km-2…k0)2，P∈E
输出：O＝kP
步骤：
1.O←0
2.For i＝0 to m-1 do
2.1 If ki＝1 then Q←Q+P
2.2 P←2P
3.Return O

[0069] 图4依据算法给出了二进制点乘算法的流程图，图中假设算法输入大整数为(km-1，km-2…k0)2，根据算法循环次数为m次。

[0070] 从图中可以看出每次循环都需要做一次倍点运算，而点加运算需要判断ki是否为1才可以进行。由于算法每次循环倍点运算和点加运算不存在数据相关，倍点运算和点加运算可以同时计算出来，然后再根据ki选择正确的值做下一轮运算，因此二进制点乘算法可以对点加和倍点的并行调度。运算效率可以提高约1/3，性能改善相当明显。

[0071] 曲线层上点加和倍点运算作为构成点乘运算的基本操作，具备了更明显的并行调度有限域运算层的特点。下面以分析二进制域上的点加和倍点算法为例分析其并行调度性能。

[0072] 二元域上的点加、倍点调度在Lopez&Dahab射影坐标下的执行效率是最高的，下面以Lopez&Dahab射影坐标下的点加和点倍为例，使用两路模乘(U0 U1)和模加(U2 U3)单元，说明其并行性。Lopez&Dahab射影坐标下的点加调度算法如下所示，其中M表示模乘运算时间，S代表模平方时间，A代表模加减时间，是临时变量。

[0073]

[0074] 并行调度算法如下所示：

[0075]

[0076]

[0077] 使用并行的调度算法，运算时间为7M+2A，计算过程中所需要的最大存储变量空间为8个。与相比普通的调度算法，并行改进后一次点加运算流程可以减少7次模乘运算时间、6次模加运算时间，可以使点加运算的运算速度提高50％以上。

[0078] Lopez&Dahab射影坐标下的点倍调度算法如下所示：

[0079]

[0080] 并行调度如下所示：

[0081]

[0082]

[0083] 使用并行的调度算法，运算时间为5M+3A，计算过程中所需要的最大存储变量空间为6个。相比普通调度算法，并行倍点调度算法可以节约5次模乘运算和1次模加运算，运算速度可以提高50％，性能提升非常明显。

[0084] 通过对椭圆曲线密码算法特点的分析，可以得出椭圆曲线密码处理具有计算密集型特点，数据处理算法中常常具有较大的内在并行性，因此，可以通过在可重构椭圆曲线密码处理器体系结构设计中开发并行的处理功能，以提升系统整体工作频率。

[0085] 有限域上大整数运算可划分成具有较小数据位宽的模乘模加操作序列，适合横向适度并行，纵向深度流水处理，因此可开发的数据级并行(DLP)度较大。目前数据级并行性的开发的典型代表是向量处理结构，它采用的是单指令处理多个数据的方式，是一种数据级并行结构。

[0086] 考虑到指令系统是整个微处理器系统软/硬件之间的接口，是处理器体系结构的主要表现形式。微处理器的指令系统与其总体结构及整体设计思想密切相关，确定了指令系统，也就确定了处理器的体系结构。因此，椭圆曲线密码专用指令处理器的指令结构设计对于体系结构密不可分，是椭圆曲线密码专用指令处理器设计的关键技术。就椭圆曲线密码专用指令处理器而言，一方面，指令结构设计应当吻合椭圆曲线密码处理的特征；另一方面，指令结构设计应当立足所选用的并行体系结构。这是解决椭圆曲线密码专用指令处理器体系结构设计的关键问题。

[0087] 由于椭圆曲线密码算法控制流较为简单，具有相对规则的处理结构和有规律的分支跳转，并且具有并行调度的特点，因此，可开发出一定的指令级并行(ILP)。面向椭圆曲线密码处理的专用指令集处理器体系结构宜采用超长指令字(VLIW)体系结构，VLIW结构本身具备了专用密码处理的诸多特点，如较大的数据处理位宽、多处理单元并行结构、指令译码便捷、集中控制逻辑简单等。因此，VLIW结构非常适合于椭圆曲线密码处理的指令级并行开发。

[0088] 因此，本发明实施例提供的可重构椭圆曲线密码处理器针对椭圆曲线密码算法的数据处理特征，对其指令集、整体架构及可重构功能单元进行设计，能够加速数据的处理、减小处理器芯片面积，又具备可编程的灵活性。椭圆曲线密码算法处理是计算强度大、计算复杂度高的任务，具有较明显的并行数据处理特征。在深入研究这些算法特征的基础上，对整体架构及关键部件进行优化设计，提出适合椭圆曲线密码运算处理特点的专用指令集处理器体系结构，强化数据通路的计算能力、简化控制通路的复杂度，满足椭圆曲线密码处理的灵活性以及高性能需求。

[0089] 根据以上对目前并行微处理器体系结构的分析，结合椭圆曲线密码处理结构特点，可重构椭圆曲线密码处理器体系结构在设计上采用超长指令字与向量处理相结合的体系结构以支持指令级和数据级的并行。该结构在充分利用VLIW指令级并行性基础上，进一步发掘了椭圆曲线密码算法有限域运算任务中存在的数据级并行性，有效提升了椭圆曲线密码专用指令集处理器的计算性能。本发明提出的支持并行处理的可重构椭圆曲线密码处理器体系结构模型如图5所示，在该结构主要由超长指令字发射与译码模块、可重构向量处理单元、向量寄存器以及存取单元所构成。通过该结构模型，指令经过指令队列按照VLIW方式发射，通过译码模块进入到可重构向量处理单元。可重构向量处理单元作为可重构椭圆曲线密码处理器体系结构中的核心运算部件，具备数据并行理功能，执行有限域上大位宽整数的运算任务；向量寄存器与可重构向量处理单元相对应，储存运算过程中的临时数据以及运算中所需的常数值；存取单元用来与外部进行数据交换。

[0090] 在椭圆曲线密码算法的处理过程，可重构向量处理单元中的寄存器、存储器中的主要数据包括以下三类：

[0091] (1)椭圆曲线密码参数

[0092] 主要包括基点P的x和y坐标、素数域上的阶p、二元域上不可约多项式f(z)、基点P的阶、有限域类型等，这些数据存储在向量功能单元内部设置的静态配置存储器中，与寄存器结构设计无关。

[0093] (2)预计算的固定点Pi/常数值

[0094] 基于窗口的点乘算法以及固定基点的点乘算法，需要根据基点P预计算出某些点Pi，在椭圆曲线密码点乘算法处理中，通过调用这些预计算的数据以提高点乘的运算速度。预计算的数据量的大小根据窗口w的宽度不同而定。存储空间随着窗口宽度的增大而增加。预计算的数据在加解密ECC点乘处理过程中保持不变，只有在基点P更换时，才会由预计算算法重新计算生成固定点Pi。对于此类数据采用基点寄存器堆进行存储，此外基点寄存器堆还存储计算过程中需要储存常数值参与运算，如椭圆曲线参数a，b，n值以及有限域运算需要的一些常数值。

[0095] (3)输入/输出/临时数据

[0096] 包括存储输入、输出和计算过程中临时数据，其中输入数据包括了基点P的x、y坐标；输出的数据即是最终的运算结果，运算中频繁改变的临时数据，如点乘算法处理和P值预计算中形成的临时数据等，对于此类数据的采用通用向量寄存器堆进行存储。

[0097] 在以往的椭圆曲线密码微处理器设计中，由于受内部寄存器数量限制，内部仅能存放输入、输出和临时数据，预计算的固定点P需要存储在片外存储器中。当执行固定点Pi预计算程序时，将计算得到的固定点Pi写入外部存储器中；在椭圆曲线密码计算过程中，再将每个循环计算所需的固定点Pi调入内部寄存器，如此在整个椭圆曲线密码处理过程中，存在较多访存指令。因此，造成了椭圆曲线密码处理器性能的下降。

[0098] VLIW处理器提高并行处理能力的基本出发点就是通过增加向量功能单元数量，实现并行计算，通过大容量寄存器堆，实现数据存储与交换。由于两类数据有着不同的用途和使用特点，对存储容量的要求也存在较大差别。为此，本发明提供的可重构椭圆曲线密码处理器体系结构中将向量寄存器堆子单元设计了两个寄存器堆，实现对两类不同数据的存储，如图6所示。其中VFU表示可重构向量功能单元。

[0099] 其中，在每个VFU处理过程中，有两个数据源，其中一个来自通用向量寄存器堆，另外一个来自基点向量寄存器堆或者通用向量寄存器堆，运算完成后得到的运算结果再存放到基点向量寄存器堆或者通用向量寄存器堆中。

[0100] 图7所示的整个通用向量寄存器堆具有8个读端口，4个写端口，即可同时从通用向量寄存器堆中读取8个源数据，可同时往通用向量寄存器堆写入4个结果数据；基点寄存器堆具有4个读端口，4个写端口，即可同时从基点向量寄存器堆中读取4个源数据，可同时往基点向量寄存器堆写入4个结果数据。

[0101] 通用向量寄存器堆完成输入的基点P的x、y坐标、临时数据、输出数据的暂存。这类数据在椭圆曲线密码处理过程中的前后数据相关性强，一般中间数据的生命周期很短，即参与运算完毕后，源数据不会再次使用，结果可以直接覆盖源操作数。

[0102] 影响通用向量寄存器堆容量的主要因素有：密码算法的运算长度、运算模式、算法处理结构等，考虑到目前椭圆曲线密码算法的运算长度，最终确定通用向量寄存器堆位宽为192bit，向量长度为32。根据指令构成研究，每个基本有限域运算处理指令槽有两个源操作数，其中一个来自通用向量寄存器堆，另外一个来自基点向量寄存器堆或者通用向量寄存器堆，每条指令操作得到一个运算结果回写寄存器堆，因此通用向量寄存器需要8个192位读端口、4个192位的写端口，该容量足以满足目前公开的椭圆曲线密码算法的需求。

[0103] 基点向量寄存器堆用于存储椭圆曲线密码处理过程的所使用的预计算出的固定点Pi以及计算过程中需要储存常数值。影响基点向量寄存器堆的存储容量与结构的主要因素有：固定点Pi参与运算数据位宽、密码算法的运算长度、算法窗口、支路数。

[0104] 一般情况下，基点向量寄存器堆存储容量由算法窗口大小、密码算法的运算长度、运算数据位宽三个方面确定。表2给出了椭圆曲线密码算法中常用的预计算点乘算法，固定点Pi储存量的分析数据。

[0105] 表2椭圆曲线密码算法中常用的预计算点乘算法所需存储量

[0106]

[0107]

[0108] 从表中可以看出，随着窗口宽度w的增加，储存的预计算值的数量成指数级的增加，因此需要考虑支持适当的宽度，同时考虑储存资源的利用率。从算法角度来看一般w不超过6个。对于特殊的窗口宽度w所需的大于基点向量寄存器堆容量的储存值，可以考虑放到处理器外部的大容量RAM进行存储。

[0109] 考虑到存储点应用需求和硬件实现资源消耗，椭圆曲线密码处理器最终确定基点向量寄存器堆位宽为192bit，向量长度为72，存储容量为192×72bit，读端口4个，写端口4个。该存储容量当VL＝1时最大支持36个点的储存，当VL＝2时最大支持18个点的储存，当VL＝3时最大支持12个点的储存。

[0110] VLIW处理器在提高指令级并行度的同时，对寄存器堆的容量、端口数量提出了更高的要求，其结果是导致了寄存器堆结构复杂，系统整体工作频率的下降。为了解决这一问题，在本发明的另一个实施例中，提出了分簇(Clustered)VLIW结构，即将寄存器堆分成若干组，每组寄存器堆对应若干功能单元。Clustered VLIW结构示意图如图7所示。

[0111] Clustered VLIW结构的工作原理为：分簇式结构通过对复杂的处理器硬件架构进行合理地分割，形成可以相对独立执行指令的多个簇结构(例如图8中的ClusterA，ClusterB)，每个簇分配了指令执行所需的寄存器(例如图8中的RF_A，RF_B)、功能单元(例如图8中每个簇对应的FU)等资源，簇与簇之间通过特定的通道进行数据交互(例如图8中BUS总线)。例如图8的结构中，整个寄存器划分为了两个寄存器簇结构，即RF_A，RF_B两个簇。每个寄存器簇中又有相应的功能单元FU，功能单元读取各自簇内的寄存器数据进行运算，然后将结果数据写入到相应的簇内的寄存器中。RF_A，RF-B两个寄存器簇中的数据再通过总线通道进行交互传递。VLIW分簇式结构，降低了寄存器堆的复杂度以及规模，减小了各部件间的数据交互，减小了处理器关键路径的延迟，提高处理器的工作频率。

[0112] 通过前面分析可知，椭圆曲线密码处理中的两类数据按基本椭圆曲线密码处理长度，即向量寄存器位宽192bit分成子块，分别进行处理，并存储于两个向量寄存器堆之中，适合于采用分簇结构。此时，处理器内部两个向量寄存器堆均被分为ABCD四簇，如图8所示，每个Cluster向量寄存器堆位宽为192bit。其中，GPVR表示通用向量寄存器堆、SPVR表示基点向量寄存器堆。

[0113] 根据以上对并行体系结构模型的研究，以及分簇式寄存器堆结构的设计，本发明提出了可重构分簇式椭圆曲线密码处理器体系结构电路的设计方案。该体系结构整体电路基于VLIW与向量处理相结合的处理器架构，采用以下分簇式电路结构设计：

[0114] (1)向量寄存器堆的分簇式结构设计

[0115] 该电路所有簇分享原有的向量寄存器堆，原有向量寄存器堆按照相同比例分配到不同簇中，特定的子向量寄存器堆只属于特定的簇结构。该电路能够有效降低向量寄存器的容量，减少向量寄存器堆访问端口的数量，减少向量寄存器堆的访问延迟。

[0116] (2)向量功能单元的分簇式结构设计

[0117] 分簇结构中的向量功能单元电路设计采用了异构功能单元的设计方案，即将所有向量运算单元不等地分配到不同簇的功能单元中，每个簇中向量功能单元所包含的向量运算单元不同，操作数输入、输出结构不同。通过指令控制的方式，将专用指令椭圆曲线密码处理器动态重构为多个簇并行执行模式，解决了有限向量寄存器堆资源与多个功能单元之间的矛盾，增强了处理的灵活性。

[0118] 根据上述处理器架构，可重构椭圆曲线密码处理器体系结构电路如图9所示，整个电路可划分为数据通路单元、控制单元、输入/输出单元等三部分。数据通路由通用向量寄存器堆、基点向量寄存器堆、配置寄存器、向量功能单元(VFU)、回写单元等五个部分构成。

[0119] 控制单元实现对处理器的整体协调控制，主要完成指令存取、指令译码、指令存储器地址生成、协调处理器内部指令与外部用户命令正确执行等工作，而且数据通路正确有序的工作也必须在控制单元正确调度控制下才得以进行。在具体实施时，可以包括指令存储器、寻址电路、分支控制模块、堆栈、专用计数器与标志寄存器模块。

[0120] 输入/输出单元包括输入/输出接口控制模块、输入/输出寄存器等电路模块及含命令寄存器和密钥、各类曲线参数输入接口电路。

[0121] 其中，数据通路单元中通用向量寄存器堆及基点向量寄存器堆被分为4簇；功能单元包含四个向量功能单元VFU0～VFU3，各对应一簇向量寄存器堆；回写单元则对功能单元的输出、输入寄存器等回写数据进行选择，并将结果写回至相应通用向量寄存器堆、基点向量寄存器堆及输出寄存器。

[0122] 可重构椭圆曲线密码处理器在工作前，首先需要外部注入算法的可重构配置信息到控制单元中的指令存储器中，形成指令控制整个数据通路的数据传递；然后外部通过接口单元注入密码运算所需要的各类参数，处理器在控制单元的协调下开始密码处理工作；运算完成后，将结果数据通过接口单元的输出寄存器读至外部。

[0123] 数据通路是处理器的关键部件之一，其中执行操作的向量功能部件与存储数据的向量寄存器通过传输总线进行互连，总线存在不同的数据宽度，使向量功能单元可触发多种密码运算，运算结果再回写到向量寄存器中。根据椭圆曲线密码处理的并行性及位宽需求，共设置四个向量功能单元VFU0～VFU3。每个向量功能单元内部运算模块组成与结构各不相同，分别由一个有限域运算单元和一个逻辑运算单元构成。四个向量功能单元可并发执行即支持四个向量操作的并行处理。

[0124] 由于任何一个密码算法都是由一系列操作按照一定的时序关系(并行或者串行)构成的，每个操作的执行则是靠指令译码得到控制信号后驱动相应运算单元而实现的。在椭圆曲线密码算法中，将能够并行执行的操作(相互之间没有数据或者存储相关性)指令集中到一起执行，这无疑会大大提高系统性能。

[0125] 为了指令能够驱动多个操作，达到并行处理的目的，本发明在单个指令操作中设计了组合指令，其设计思想是开发单数据通路的指令级并行度，同一时刻最多能驱动2～4个普通指令操作。

[0126] 椭圆曲线密码并行结构特征对可重构处理器指令系统构造提出了以下要求：

[0127] (1)构造面向单个基本密码处理指令；

[0128] (2)构造面向2～4个普通指令(运算处理指令或者控制指令)同时进行处理的密码组合处理指令；

[0129] 椭圆曲线密码处理器指令结构要素包括：特征域、指令槽、操作数，如图10所示。

[0130] 椭圆曲线密码处理都是针对大整数操作数进行处理，因此可重构椭圆曲线密码处理器在指令系统上构造了面向大整数处理的指令槽，每个指令槽用于实现576位以下的椭圆曲线密码有限域运算层单个处理操作，如二元域与素数有限域上的模加、模减、模约减、模平方、模乘、模逆运算，以及数据传输等。基本运算指令可以独立使用，也可以组合为并行的长指令，提高处理器的执行效率。

[0131] 针对椭圆曲线密码处理的控制调度特点，设计了专门的分支控制指令槽，实现分支控制指令，包括以下六类：

[0132] 控制计数器操作指令：计数器清零、置数、加1、减1操作；

[0133] 控制计数器分支判断指令：当前计数值判断(大于、等于、小于)指令，计数值加1后判断(大于、等于、小于)指令，计数值减1后判断(大于、等于、小于)指令；

[0134] K值寄存器操作指令：K值寄存器清零、移位操作；

[0135] K值寄存器分支判断指令：当前K值寄存器移出的值判断(大于、等于、小于)指令；

[0136] 无条件转移指令：无条件跳转到指定地址；

[0137] 子程序调用和返回指令：实现子程序调用与返回；

[0138] 分支控制指令可以独立使用，也可以将分支判断指令与控制操作指令进行拼装成为一条超长指令字，实现椭圆曲线密码处理过程中的无延迟跳转，从而提高循环的执行效率。

[0139] 对于椭圆曲线密码处理指令而言，按照源操作数的数目，可以分为两类：一类是只有一个源操作数的指令，如模逆、模平方、模约减、立即数移位等指令；另一类是具有两个源操作数的指令，如模加/减、模乘等大部分形式的指令。这样就能够将操作数的格式控制在两个源操作数地址、一个目的操作数地址之内，经过组合后达到4～8个源操作数地址、2～4个目的操作数地址的形式。

[0140] 此外，特征域用于表示指令束结构，指示各个指令槽在指令束中的位置，其目的是为了简化编译系统和硬件的设计。不同赋值的特征域对应不同的指令束，特征域的取值分为0和1两种，分别对应普通指令和组合指令。

[0141] VLIW指令字又称为指令束，由一个特征域和多个独立的指令槽(或称为指令段)构成，本发明椭圆曲线密码处理器的一个指令束，依据指令槽的类型，指令束共设计两种类型，分别称为O类型、C类型。

[0142] (1)O类型

[0143] O型指令束由四个基本运算处理指令槽构成，每个指令槽对应一系列基本的大整数有限域密码处理指令，包括二元域与素数有限域上的模加、模减、模约减、模平方、模乘、模逆运算以及基本逻辑运算等一系列运算指令。四个基本运算处理指令槽指令结构相同，能够独立控制相应的功能单元，支持多个有限域运算并行处理，指令槽中的操作码分别被送往相应的功能单元FU0～FU3，使能基本的密码处理指令，经指令译码后，将数据从寄存器堆中读出、运算，运算结果回写到寄存器堆内部。

[0144] (2)C类型

[0145] C型指令束由2个分支控制指令槽构成。每个分支控制指令槽由分支判断指令或控制操作指令组成。分支判断指令包括了控制计数器分支判断指令和K值寄存器分支判断指令，控制操作指令包括了控制计数器操作指令和K值寄存器操作指令。每个分支控制指令槽中的操作码被送往控制分支部件，经指令译码后，控制相应的电路模块工作，控制程序计数器跳转。2个分支控制指令槽进行拼装，实现跳转分支和控制操作并行进行，从而提高椭圆曲线密码算法处理过程中循环的分支控制执行效率。

[0146] 图11给出了O类型和C类型指令束结构示意图。

[0147] 本发明实施例中，对于通用向量寄存器堆，每条指令的目的操作数只能写入本簇寄存器堆中，即簇中的VFU单元运算的结果在指令的控制下存放至本簇寄存器堆中；两个源操作数可以来自任意簇寄存器堆中，即簇中的VFU单元的输入数据在指令的控制下可以来自任意簇寄存器堆中。

[0148] 对于基点向量寄存器堆，每条指令的目的操作数只能写入本簇寄存器堆中，即簇中的VFU单元运算的结果在指令的控制下存放至本簇寄存器堆中；源操作数可以来自任意簇基点向量寄存器堆中，但每个簇基点向量寄存器堆每次只能读出一个数据，即簇中VFU单元的输入数据在指令的控制下只能有一个来自任意簇基点向量寄存器堆中。

[0149] 各个簇中的数据传递正是通过以上访问原则完成数据的传递。分簇VLIW处理器结构在简化VLIW结构寄存器堆设计，提升系统整体工作频率的同时，也给处理器的灵活使用上带来了一定问题。因此，合理规划操作数的簇间分配问题，确定功能单元访问异簇寄存器堆数据方式，是椭圆曲线密码处理器设计中的一个关键问题。

[0150] 通用向量寄存器堆内部存储有输入的基点P的x、y坐标、临时数据、每循环运算结果、输出数据等，每一Cluster的存储容量小，灵活性要求高。为此，确定通用向量寄存器堆的访问原则如下：

[0151] 每条指令的目的操作数只能写入本簇寄存器堆中。

[0152] 每条指令的两个源操作数可以来自任意簇寄存器堆中。

[0153] 根据这一原则，当对通用向量寄存器堆进行写操作时，通用向量寄存器堆的每一Cluster分属不同的运算支路和功能单元。Cluster A对应功能单元VFU0，Cluster B对应VFU1，Cluster C对应VFU2，Cluster D对应VFU3。即功能单元VFU0的运算结果只能够写入Cluster A，功能单元VFU1的运算结果只能够写入Cluster B，功能单元VFU2的运算结果只能够写入Cluster C，功能单元VFU3的运算结果只能够写入Cluster D。

[0154] 与通用向量寄存器堆相比，基点向量寄存器堆规模更大，其存储容量为192×72bit，读端口4个，写端口4个。实验表明，当采用与通用向量寄存器堆相同的读操作方式，其互联网络的资源占用是通用向量寄存器堆的2.5倍，延迟也增加20％，这些将对处理器的性能造成极大影响。

[0155] 通过对椭圆曲线密码算法的深入研究，可以发现，对于群运算层上的点乘算法而言，其运算中需要的固定值Pi，只会作为一个源输入值参与到底层的各个有限域运算。为此，确定基点向量寄存器堆的访问原则如下：

[0156] 每条指令的目的操作数只能写入本簇寄存器堆中。

[0157] 每条指令的源操作数可以来自任意簇寄存器堆中，但任意一簇寄存器堆每次只能读出一个数据。

[0158] 这种数据读取方式与通用向量寄存器堆相比，灵活性有所下降，但性能得到有效提升。与读完全固定方式相比，提高了灵活性。

[0159] 本发明实施例中，向量功能单元采用可重构设计方案。由此，根据椭圆曲线密码处理特点，可重构的功能单元需要设计可配置模加/减有限域运算单元、可配置模乘有限域运算单元以及可配置模逆有限域运算单元，具体包括：

[0160] (1)对有限域运算单元的双有限域可配置硬件实现结构进行设计[0161] 二进制有限域上的加减运算为域元素对应系数的异或，硬件实现非常简单。素数有限域上的加减运算会产生进位和借位，对于大数运算而言是比较耗时的。与传统的可配置设计思路不同，在进行双有限域可配置硬件结构设计时，采用可重构设计的思想设计可重构的运算数据路径，能够同时支持两个有限域上的运算。相比较于分别设计两个单独的有限域运算单元，本发明设计能够节省近50％的硬件资源。

[0162] (2)对有限域运算单元的运算数据长度可配置硬件实现结构进行设计[0163] 目前椭圆曲线密码算法中，NIST推荐使用的二进制有限域和素数有限域的最大域值分别为571和521，因此本发明设计的有限域运算单元最高可以支持576位数据的运算，能够兼容576位以下数据的运算，而对于大于576位的有限域运算可以通过上层调度实现。运算数据长度可配置的硬件实现结构，将重点从两个方面进行设计：一是设计能够适用于任意不可约多项式和素数运算的算法，并根据算法设计硬件；二是从减少硬件资源开销出发，设计可配置的硬件实现结构。

[0164] (3)从提高有限域运算单元的运算速度出发，优化算法设计高效的硬件电路[0165] 通过对有限域运算算法进行分析，最大程度地对算法进行优化，一是设计双有限域算法，以最小的代价实现双有限域运算的统一；二是简化算法中的运算步骤；然后基于优化算法，从提高运算并行性和电路时钟频率出发，研究硬件实现电路，设计高效优化的硬件电路。

[0166] 对于传统的模加/减运算电路，输入的操作数字长是固定的，无法实现操作数的可配置性。通过借鉴数字信号处理系统设计中常用的折叠技术，设计一种基于字的双域统一模加/减器，把较长字长操作数的模加/减运算转换成基于字的模加/减操作，不但可以减小模加/减运算模块的面积，而且使得模加/减运算具有了可配置性，从而实现了多精度操作数模加/减运算。由于二元域上的模加/减运算，实质上为两操作数的异或运算，完全可以复用素数域模加中的部分运算。基于可重构的思想，在同一电路结构中实现素数域上的模加/减运算与二元域上的模加/减运算则可以进一步减小芯片面积。

[0167] 模加/减运算若按照单精度实现方式，n位全加器和全减器的延迟会严重影响电路的时钟频率。为降低数据路径延迟，一般的做法是将运算数据分成若干个字，对运算数据按字进行处理，以提高电路时钟频率。首先从算法角度出发，对模加和模减算法进行优化，以简化硬件设计。

[0168] 对模加算法进行优化，达到以下两个目的：一是将第一次整数加法产生的进位不带入第二次的模约简运算中，使两次运算的数据路径相同。二是前后两次运算均采用相同的加法运算电路完成，即电路中只设计加法运算数据路径即能完成模加运算。

[0169] 对模减算法进行优化，达到以下目的：以加法完成模减运算，第一次的整数减法和第二次的整数加法运算均采用加法运算完成，即电路中只设计加法运算数据路径即能完成模减运算。

[0170] 考虑到经过优化的模加和模减算法，其数据路径均为相同位宽的加法运算单元，所以可以设计统一的模加和模减运算单元，即模加和模减运算共用运算单元的数据路径。这样可以达到节省50％硬件资源开销的目的。

[0171] 模乘运算是ECC密码处理中最关键的运算，它的运算速度快慢决定了密码处理的整体性能。截止目前，所有模乘算法可以大体分为三种类型：传统模乘方法、交叉模乘算法、Montgomery模乘算法。其中，Montgomery模乘算法是应用最为广泛的也最高效的模乘算法，它将素数域上模乘运算中的除法运算替换成移位操作，大大加快了模乘运算的速度和效率。

[0172] Montgomery模乘算法存在的主要问题是模乘运算数据长度固定，不具备可配置性。另一个缺陷就是模乘运算的数据路径延迟达到2级n位全加器的延迟，极大限制了电路的时钟频率。所以在对算法进行硬件实现时，一般是将运算数据分成若干个字，对运算数据按字进行处理，以提高算法并行度和电路时钟频率。

[0173] 目前Montgomery模乘运算的扩展和优化实现算法主要可以分为以下四种类型：比特级-完全长度(Bit-Level Full-Precision，BLFP)算法，即对一个运算数据按比特进行处理，对另一个运算数据按完全长度进行处理；比特级-字级(Bit-Level Word-Level，BLWL)算法，即对一个运算数据按比特进行处理，对另一个运算数据按字进行处理；字级-完全长度(Word-Level Full-Precision，WLFP)算法，即对一个运算数据按字进行处理，对另一个运算数据按完全长度进行处理；字级-字级(Word-Level Word-Level，WLWL)算法，即对一个运算数据按字进行处理，对另一个运算数据同样也按字进行处理。因为BLFP和WLFP类型的算法与原始Montgomery模乘算法存在相同的缺陷，所以要设计可配置的模乘运算单元，一般采用BLWL和WLWL这两种类型的算法。

[0174] 基于这两种类型的算法，并按求乘法部分积与约简方式的不同，又相继提出了SOS、CIOS、FIOS、FIPS、CIHS这五种不同类型的Montgomery扩展算法，表2列出了这五种算法的总运算量的比较结果。表中的s代表运算数据的字数，M、A、S和Shift分别代表一次字乘法运算、字加法运算、字减法运算和字移位操作。

[0175] 表3 SOS、CIOS、FIOS、FIPS、CIHS五种算法的运算量比较

[0176]算法 总运算量
SOS s2(2M+4A)+Sm+(s+1)S+(s+1)Shift
CIOS s2(5M+10A+Shift)
FIOS s2(2M+4A)-sA
FIPS (s2-s)(7M+10A+6Shift)/2-(s-1)(5M+6A+3Shift)
CIHS s2(3M+9A)-s(M+8A)

[0177] 根据以上分析，在不考虑流水线实现算法的前提下，FIOS算法的运算量是这五种算法中最少的。

[0178] 下面以运算周期和硬件实现的复杂度对这五种算法进行分析。先求乘法部分积后进行约简的SOS算法，需要四次循环，运算周期太长；将求乘法部分积与约简运算粗略结合的CIOS算法，在完成对一个运算数据全部比特的处理后，进行一次约简运算，所以在一个外部循环内需要嵌套两个内部循环，第一个内部循环求乘法部分积，第二个内部循环进行约简运算，所需运算周期数较前一种方式少，但运算周期数仍然较大；将求乘法部分积与约简运算精细结合的FIPS算法，需要对部分积做进一步处理，并在每次完成对运算数据一个字的处理后，即进行一次约简运算，所以该算法需要两个外部循环，每个外部循环内嵌套一个内部循环；将求乘法部分积与约简运算精细结合的FIOS算法，在每次完成对运算数据一个字的处理后，即进行约简运算，所以只需要一个外部循环，并且外部循环内只嵌套一个内部循环，所需运算周期是最少的；将求乘法部分积与约简运算粗略结合的CIHS算法，对运算数据和部分积均要进行处理，所以需要两个外部循环，并且第二个外部循环内嵌套两个内部循环。另一方面，SOS、CIOS、FIPS、CIHS这四种算法，对运算数据和乘法部分积的读取非常复杂，而且并不按照它们在寄存器中的先后存储次序，而是由外部循环以及内部循环的次数决定，这样将大大增加控制电路的设计难度。而FIOS算法中对运算数据按照它们在寄存器中的先后存储次序逐字进行处理，对中间变量的读取也按照写入寄存器的先后次序，因而更便于设计硬件电路。本专利采用了WLWL类型的FIOS模乘算法进行设计。

[0179] 有限域求逆运算是ECC密码算法的关键运算之一，同时也是效率最低的有限域运算。通常情况下，有限域求逆运算的开销至少是乘法运算的4倍，因此求逆运算的效率将直接影响到整个ECC密码系统的效率。

[0180] 有限域上的求逆算法主要分为以下三种类型：

[0181] 第一种类型是基于Fermat小定理方法。这种方法比较简单，只需要进行一次模幂(若干次连续模乘)运算即可，但所需运算周期数较多，并且不支持二元域上所有的不可约多项式。

[0182] 第二种类型是基于欧几里德定理，由Stein提出的两个求最大公约数算法衍生而来。该算法仅仅依赖于下列运算：加法，减法，奇偶校验，求二倍值(对应于在二进制表示中的左移)，偶数折半(对应于在二进制表示中的右移)。

[0183] 第三种类型是Montgomery模逆算法。该算法首先对运算数据进行转换，进一步提高运算效率，使之更适合硬件实现。算法仅仅依赖于加法、减法、奇偶校验、求二倍值(对应于在二进制表示中的左移)、偶数折半(对应于在二进制表示中的右移)运算。

[0184] 第二种类型与第三种类型的求逆算法适合硬件实现，并且运算效率较高，但基于欧几里德定理的算法存在两点不足：一是该算法每次循环需要对多种情况进行判断，若采用串行判断的方式，判断延迟较长，若采用并行判断的方式，电路中需要更多的中间变量寄存资源；二是该算法不能支持Montgomery数域上的运算，与Montgomery模乘算法不能有效统一起来，需要额外的数域转换步骤。

[0185] 根据以上对不同类型求逆算法的分析，本发明对Montgomery模逆算法进行了研究，并基于算法设计了可配置硬件实现结构。

[0186] Montgomery模逆算法。该算法分为两个运算部分，第一部分为近似Montgomery模逆算法，第二部分是对近似结果进行进一步转换，求得逆元。Montgomery模逆算法近似求逆运算得到近似Montgomery逆元，此时可以通过移位加操作得到普通数域逆元或Montgomery逆元。但在实际应用中，需要根据具体情况求得这两种不同的逆元，若通过移位加操作完成数域转换，需要改动控制电路。因此通过分析求普通数域内的普通逆元、求Montgomery域内的Montgomery逆元、求普通数域内的Montgomery逆元和求Montgomery域内的普通逆元这四种类型的模逆运算，可以得出若以Montgomery模乘运算代替移位加操作，并以不同的预计算参数值作为模乘器的输入，这样就能够达到设计一个统一的硬件结构在不同数域之间进行转换的目的，而不需要对硬件电路进行任何改变。从而达到了灵活高效的目的。

[0187] 可见，本发明提供的可重构椭圆曲线密码处理器，基于椭圆曲线密码算法可并行处理特征，在设计上遵循了通用处理器体系结构设计方法，采用超长指令字(VLIW)与向量处理相结合的体系结构。该结构能够满足椭圆曲线密码处理的基本特点，具有较高的指令级并行度，同时结合可重构方法设计了具有支持指令重构的专用密码处理并行指令结构，从而达到更高的处理效率，为高速网络数据保密通信提供一种新的高效灵活的处理模式，因此，相比目前现有的椭圆曲线密码处理器具有较大的性能优势。

[0188] 以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。

[0189] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(Read-OnlyMemory，ROM)或随机存储记忆体(Random Access Memory，RAM)等。

[0190] 对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明实施例的精神或范围的情况下，在其它实施例中实现。因此，本发明实施例将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。