在ECC中实现位数自适应模乘运算的方法及模乘运算器

摘要

本发明公开了一种在ECC中实现位数自适应模乘运算的方法，包括：基于零位检测模块获取输入数据的位数；根据输入数据的位数选择与输入数据相接近的模乘运算档位；基于模乘运算档位所关联的64位KOA并行乘法器对所述输入数据进行运算。本发明还公开了一种ECC模乘运算器，包括：零位检测模块，用于获取输入数据的位数；模乘运算档位选择模块，用于根据输入数据的位数选择与输入数据相接近的模乘运算档位；模乘运算模块，用于基于模乘运算档位所关联的64位KOA并行乘法器对所述输入数据进行运算。通过本发明实施例，在原始的KOA算法进行改进，使其自动的根据输入乘数的位数进行计算调整，以达到最优的计算效果。

说明书

技术领域

本发明涉及椭圆曲线加密算法(ECC)技术领域，具体涉及一种在ECC 中实现位数自适应模乘运算的方法及模乘运算器。

背景技术

ECC加密算法是单位比特安全性能最高的非对称加密算法，由于硬件实 现ECC算法速度比软件快很多，很多智能卡芯片、阅读器芯片及安全芯片中， 均有ECC算法的实现电路。随着该算法的应用广泛，ECC算法实现的位数需 要也不一样，不同标签芯片在ECC加密算法位数选择也不尽相同，为了保证 安全模块的广泛使用性，在同一个安全模块内实现多位数的ECC加密算法。 但是为了保证ECC加密算法的高速性，在基本模块的实现上需要使关键模块 具有长度自适应性。

ECC加密算法中最关键的基本的运算为模乘运算，其决定了ECC加密算 法具体实现时的运算速度。对于椭圆曲线中模乘算法也有三种，通常实现模乘 算法主要直接相乘求模算法、KOA模乘算法和Montgomery模乘算法三种以 及相关算法的改进。对于直接相乘求模的算法来说，虽然实现和算法都比较直 接简单，但其在实现上占用的时间和面积也是最多的。而Montgomery模乘算 法虽然高效，但是当我们只需要计算一次模乘时，需要的额外操作较多，比较 适合RSA算法的模幂操作，ECC的标量乘算法并不一直使用模乘计算，中间 还会用到其它的操作，并且每一个循环周期内都需要各种操作的组合，接下来 要进行其它操作时，因此该算法在模乘算法上并不能取得高效的性能。

通常采用KOA乘法器来实现模乘算法。乘法器按运算周期来分，主要有 串行乘法器、全并行乘法器和串并乘法器三种。对于串行乘法器来说，它通过 不断的移位运算进行实现，该算法是以牺牲运算速度来获取较小的实现面积， 其实现面积为O(m)其实现速度也为O(m)。第二种是全并行乘法器，该乘法器 是在先分别求出部分积然后再对每一部分的部分积进行累加的操作，该算法是 以牺牲面积来获取最快的运算速度，其实现面积为O(m²)，而运算速度则为 O(1)。第三种方法是串并混合乘法器，是以上两种方法的折中，其实就是以串 行乘法器的思想调用底层并行乘法器加以实现。其面积及计算速度都介于前面 两者中间。

KOA乘法器从理论上讲，是通过多次的分治处理可以将基础乘法器的数 目减至到一位，这样算法的复杂度可以降低至但随着分治算法的进 行，辅助操作随之增加，故一般分治的次数不会太多，因此必须根据实际需要 进行合理设计。对于乘法器来说，串行乘法器和并行乘法器都不能在面积和速 度上有很好的折合，因此目前通常采用串并乘法器来实现模乘器。但是位数越 大的乘法器，消耗的时间越长。对于进行乘法操作的位数不是固定的情况，当 位数较低时，传统的方法是采用高位补0法，补齐为最高位时再输入乘法器进 行计算。但这无疑产生了极大的时间浪费，特别是位数低于最高位一半时，乘 法器花了一半的时间在计算无用的数。

发明内容

针对以上几种实现算法的不足，本发明提出了在ECC中实现位数自适应 模乘运算的方法及ECC模乘运算器，在原始的KOA算法进行改进，使其自动 的根据输入乘数的位数进行计算调整，以达到最优的计算效果。

本发明提供了一种在ECC中实现位数自适应模乘运算的方法，所述方法包 括如下步骤：

基于零位检测模块获取输入数据的位数；

根据输入数据的位数选择与输入数据相接近的模乘运算档位；

基于模乘运算档位所关联的64位KOA并行乘法器对所述输入数据进行运 算。

所述64位KOA并行乘法器包括至少两个或者以上串并在一起的64位KOA 乘法器。

所述64位KOA乘法器由9个16位乘法器构成。

所述64位KOA并行乘法器至少满足512位乘法运算。

相应的，本发明实施例还提供了一种ECC模乘运算器，包括：

零位检测模块，用于获取输入数据的位数；

模乘运算档位选择模块，用于根据输入数据的位数选择与输入数据相接近 的模乘运算档位；

模乘运算模块，用于基于模乘运算档位所关联的64位KOA并行乘法器对 所述输入数据进行运算。

所述64位KOA并行乘法器包括至少两个或者以上串并在一起的64位KOA 乘法器。

所述64位KOA乘法器由9个16位乘法器构成。

所述64位KOA并行乘法器至少满足512位乘法运算。

本发明可以实现512位数以下的长度自适应KOA模乘算法，该算法以全 并行的结构设计了64位的基础乘法器模块，根据硬件特点以及常见的椭圆曲 线位数值，也可以设计不同的模乘运算档位，比如192、256、320、384、448、 512。乘法器对输入的数据进行位数判断，自适应的选择这六档中最适当的长 度进行计算。通过这种自适应的方法，在各种位数的情况下，尤其是计算较低 位数时，显著的提高了乘法器的运算速度。

本发明的在硬件上，利用串并混合乘法器来实现，利用KOA算法原理， 把乘法运算的位数进行分治，采用全并行的64位基础乘法器模块来实现。而 对于这64位的基础乘法器模块，采用KOA的方法，将64位的乘法器由9个 16位的乘法器构成，另外加上若干加法电路，就可以利用16位的乘法器来实 现64位并行乘法器。为了满足模乘算法最高位512位的要求，实现的模乘器 必须满足512位乘法运算，对于最高位情况，利用64位的基础乘法器，通过 串行的方式来实现最高为512的乘法器。

为了满足模乘算法的长度自适应，根据常见的椭圆曲线加密算法ECC的 位数值，把不同位数的模乘算法划分为6个档，通过一个状态机来控制整个运 算的流程，同时利用一个组合逻辑电路和一个寄存器来标识输入数据的位数， 根据输入位数，利用组合逻辑电路和寄存器的状态来决定调用哪几个64位乘 法器，当输入的位数较少时，状态机根据寄存器表示的状态，跳过后面所有状 态的操作，输出运算结果。该发明虽然在牺牲掉一小部分组合逻辑电路的面积， 但能在长度自适应的同时快速的实现椭圆曲线模乘算法。

附图说明

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

图1是本发明实施例中的在ECC中实现位数自适应模乘运算的方法流程 图；

图2是本发明实施例中的ECC模乘运算器结构示意图；

图3是本发明实施例中的ECC模乘运算器功能原理结构示意图；

图4是本发明实施例中的512位KOA乘法器结构原理示意图；

图5是本发明实施例中的ECC模乘运算中程序运行流程图。

具体实施方式

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

图1示出了在ECC中实现位数自适应模乘运算的方法流程图，包括如下步 骤：

S101、基于零位检测模块获取输入数据的位数；

S102、根据输入数据的位数选择与输入数据相接近的模乘运算档位；

S103、基于模乘运算档位所关联的64位KOA并行乘法器对所述输入数据 进行运算。

这里的64位KOA并行乘法器包括至少两个或者以上串并在一起的64位 KOA乘法器。64位KOA乘法器由9个16位乘法器构成。该64位KOA并行乘法器 至少满足512位乘法运算。

相应的，图2还示出了本发明实施例中的ECC模乘运算器结构示意图，包 括：

零位检测模块，用于获取输入数据的位数；

模乘运算档位选择模块，用于根据输入数据的位数选择与输入数据相接近 的模乘运算档位；

模乘运算模块，用于基于模乘运算档位所关联的64位KOA并行乘法器对 所述输入数据进行运算。

需要说明的是，该64位KOA并行乘法器包括至少两个或者以上串并在一 起的64位KOA乘法器。该64位KOA乘法器由9个16位乘法器构成。该64位KOA 并行乘法器至少满足512位乘法运算。

本发明可以实现512位数以下的长度自适应KOA模乘算法，该算法以全 并行的结构设计了64位的基础乘法器模块，根据硬件特点以及常见的椭圆曲 线位数值，也可以设计不同的模乘运算档位，比如192、256、320、384、448、 512。乘法器对输入的数据进行位数判断，自适应的选择这六档中最适当的长 度进行计算。通过这种自适应的方法，在各种位数的情况下，尤其是计算较低 位数时，显著的提高了乘法器的运算速度。当然根据根据这种串并原理，其可 以满足不同位数的长度适应性KOA模乘运算，也不限于512位数的运算。

本发明的在硬件上，利用串并混合乘法器来实现，利用KOA算法原理， 把乘法运算的位数进行分治，采用全并行的64位基础乘法器模块来实现。而 对于这64位的基础乘法器模块，采用KOA的方法，将64位的乘法器由9个 16位的乘法器构成，另外加上若干加法电路，就可以利用16位的乘法器来实 现64位并行乘法器。为了满足模乘算法最高位512位的要求，实现的模乘器 必须满足512位乘法运算，对于最高位情况，利用64位的基础乘法器，通过 串行的方式来实现最高为512的乘法器。

为了满足模乘算法的长度自适应，根据常见的椭圆曲线加密算法ECC的 位数值，把不同位数的模乘算法划分为6个档，通过一个状态机来控制整个运 算的流程，同时利用一个组合逻辑电路和一个寄存器来标识输入数据的位数， 根据输入位数，利用组合逻辑电路和寄存器的状态来决定调用哪几个64位乘 法器，当输入的位数较少时，状态机根据寄存器表示的状态，跳过后面所有状 态的操作，输出运算结果。该发明虽然在牺牲掉一小部分组合逻辑电路的面积， 但能在长度自适应的同时快速的实现椭圆曲线模乘算法。

相应的，图3示出了本发明实施例中的ECC模乘运算器功能原理结构示 意图，主要包括一个控制状态机、1个寄存器组、2个零位检测模块以及乘法 位数选择模块、数据选择模块、64位KOA并行乘法器模块。本发明主要利用 状态机来控制整个算法的计算流程，通过零位检测模块来判断输入数据的位 数，根据输入数据位数，利用乘法位数选择模块来选择与输入数据位数相接近 的档，并和数据选择模块共同利用控制状态机来控制当前模乘算法的执行，合 理的跳出不需要执行的算法状态，通过寄存器和64位KOA并行乘法器暂存 运算结果和计算。当运算结束后通过接口输出运算结果。

具体来说，零位检测器来判断输入位数，通过乘法位数选择模块和数据选 择模块进行模乘算法运算的档的选择，根据档的选择，通过状态机调用64位 KOA并行乘法器模块串行实现模乘算法，在位数不固定的情况下，每次都能 合理选择串行乘法的位数，跳出后面无须执行的状态，实现长度自适应的快速 模乘算法。

图4示出了本发明实施例中的512位KOA乘法器结构原理图，该64位 KOA乘法器由9个16位乘法器构成。该64位KOA并行乘法器至少满足512 位乘法运算。利用串并混合乘法器来实现，利用KOA算法原理，把乘法运算 的位数进行分治，采用全并行的64位基础乘法器模块来实现。而对于这64 位的基础乘法器模块，采用KOA的方法，将64位的乘法器由9个16位的乘 法器构成，另外加上若干加法电路，就可以利用16位的乘法器来实现64位并 行乘法器。为了满足模乘算法最高位512位的要求，实现的模乘器必须满足 512位乘法运算，对于最高位情况，利用64位的基础乘法器，通过串行的方 式来实现最高为512的乘法器。

在乘法器具体的实现过程中，定义wire类型的数组isZero[0..4]，每一位 反映宽度为64位的两个乘数的输入的数据段是否全为0，例如isZero[4]表示 最高64位，由组合逻辑电路确定该数组的值。用wire类型的数组isSkip[0..4] 表示宽度为64位的两个乘数部分计算可否跳过。则有，当isSkip[i+1]为1且 isZero[i]为1时，isSkip[i]为1。此处组合逻辑电路大约占整个乘法器面积的 1/20，不会太影响乘法器的面积。完成整个乘法器的计算需要一个小状态机， 用来控制数据流程。在设计中，我们将状态机的计算顺序加以优化，使得状态 机可以根据isSkip的值正确的跳过一些状态操作。例如，若isZero[0..4]＝01111， 也就是说，输入的两个乘数最高256位都为0，192-256位不全为0， isSkip[0..4]＝01111当前乘法器最佳长度为256位。状态机经过多次状态转换后， 会根据isSkip的值，跳过后面所有状态的操作，输出运算结果。其状态流程图 如图5所示。

本领域普通技术人员可以理解上述实施例的各种方法中的全部或部分步 骤是可以通过程序来指令相关的硬件来完成，该程序可以存储于一计算机可读 存储介质中，存储介质可以包括：只读存储器(ROM，Read Only Memory)、 随机存取存储器(RAM，Random Access Memory)、磁盘或光盘等。

以上对本发明实施例所提供的在ECC中实现位数自适应模乘运算的方法 及模乘运算器进行了详细介绍，本文中应用了具体个例对本发明的原理及实施 方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心 思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方 式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发 明的限制。