ECC kP+lQ点乘算法的优化研究

作为椭圆曲线密码体制的核心运算,点乘和kP+lQ点乘在ECC的多方密码协议中都要用到,其运行效率决定ECC的实现效率,对ECC的推广应用具有重要意义。本文以计算多点乘的Shamir NAF算法为基础,通过对NAF加减法链序列的观察,改进预运算针对kP+lQ对算法进行优化,实验显示优化后的算法效率有了一定程度提高。     

一种基于半点运算与双基表示的双标量乘算法

椭圆曲线密码体制的核心运算是标量乘法运算,在一些椭圆曲线公钥密码体制中需要计算双标量乘法。为了提高椭圆曲线双标量乘法的效率,在现有半点运算和双基表示的基础上提出了一种新的双标量表示形式,并给出基于该表示形式的双标量乘算法。该算法用快速的半点运算替代传统的倍点运算,从而有效提高了双标量乘法的效率。实验结果表明,在NIST推荐的椭圆曲线上,新算法的效率比基于双基表示的并列点乘算法大约提高了32%,比基于JSF表示的双标量乘算法提高了35%。     

椭圆曲线密码体制中的快速点乘算法

点乘运算是实现椭圆曲线密码体制的基本运算，同时也是最耗时的运算，它的运算效率直接决定着ECC的性能。本文从三方面分析了椭圆曲线密码体制中快速点乘的实现，并将Marc Joye和Sung—Ming Yen提出的具有最小汉明重的从左到右带符号二进制编码应用于椭圆曲线密码体制的点乘算法中，生成了一个能快速实现的二进制编码新点乘算法，适用于计算能力和集成电路空间受限，要求高速实现的情况。     

椭圆曲线密码体制中的快速点乘算法

点乘运算是实现椭圆曲线密码体制的基本运算,同时也是最耗时的运算,它的运算效率直接决定着ECC的性能。本文从三方面分析了椭圆曲线密码体制中快速点乘的实现,并将Marc Joye和Sung-Ming Yen提出的具有最小汉明重的从左到右带符号二进制编码应用于椭圆曲线密码体制的点乘算法中,生成了一个能快速实现的二进制编码新点乘算法,适用于计算能力和集成电路空间受限,要求高速实现的情况。     

椭圆曲线标量乘算法的改进

椭圆曲线密码体制的快速实现依赖于标量乘(nP)的有效计算,该文改进 的二进制和三进制的混合表示方法,并且将其推广到 的二进制、三进制和五进制的混合表示。该算法在已知二倍点、三倍点和五倍点运算量的基础上,经过恰当的运算计算标量乘。试验结果表明,该算法减少计算标量乘的运算量,能有效地计算标量乘。     

椭圆曲线快速点乘算法优化

转换乘法为平方运算,是一种快速计算椭圆曲线密码点乘的代数方法。利用此方法,提出了素域Fp上雅可比坐标系下的3P和3kP算法,其运算量分别为6[M]+10[S]和(6k)[M]+(10k)[S],与已有的最好算法相比,算法效率分别提升了11.8%和10.5%。另外,还在文献[1,2]基础上,对素域Fp上仿射坐标系下的2kP和3kP的算法进行了改进,其算法效率比文献[1,2]分别提高了6.3%和3.3%。     

基于整数拆分的椭圆曲线密码体制上的快速点乘算法

在椭圆曲线密码系统中,其核心操作是点乘运算κP,P是椭圆曲线上的点,忌是整数。怎样提高点乘计算速度,已成为热点研究领域。本文提出了一种新的基于整数拆分与预计算相结合的快速点乘算法。     

NAF点乘算法的并行计算研究

分析了目前常用的NAF点乘算法,并提出了改进的并行NAF点乘算法,改进后的算法具有并行调度点加和点倍的特点,实验表明改进后的算法比原算法效率有明显提高。     

面向RFID应用的GF(2~m)域上ECC点乘运算的轻量化改进研究

针对RFID等资源受限的特殊应用,选取安全性能较高的椭圆曲线算法进行轻量化改进研究,对其核心部分点乘运算中的模乘、模逆算法进行了改进,采用整体串行、部分并行的方式对算法执行结构进行了重新设计。经在FPGA上仿真验证,对比其他方案,改进后的算法在芯片占用面积和执行速度上有明显的综合优势,适用于RFID等资源受限的应用场合。     

一种通用GF(2m)模乘加速器的快速实现

在椭圆曲线密码体制(ECC)中,有限域GF(2m)上模乘运算是最基本的运算,加速模乘运算是提高ECC算法性能的关键。针对不同不可约多项式广泛应用的现状,提出了一种通用GF(2m)模乘加速器设计方案。该加速器通过指令调度的方式,能快捷地完成有限域上模乘运算。实现结果表明,该设计完全适用于智能卡等应用要求。     

一种新的余数系统下快速计算素域椭圆曲线点乘的方法

椭圆曲线密码运算主要是椭圆曲线点乘,后者由一系列的模乘构成。利用余数系统下的蒙哥马利模乘算法,素域中对阶取模余的模乘可以转化为对余数系统基底取模余。提出一种新的余数系统下的方法以加速计算椭圆曲线点乘。（1）与传统上取两个几乎对称的余数系统不同,该方法取了两个非对称的余数系统。其中,余数系统Γ包括两个模数{2L, 2 L-1}; 余数系统Ω包括八个模数,它们都具有如2L－2Ki+1的形式。这种选择使其模算术变得简单。（2）在上述非对称的余数系统中,大部分原来需要对椭圆曲线域特征值取模的模乘运算可以在余数系统中直接用乘法代替。此外,计算椭圆曲线点乘时用到了仅计算x坐标的蒙哥马利梯子。在每次并行的倍点和点加结束时,需要四次余数系统下的蒙哥马利模乘,以压缩中间结果的值域。因此,计算一个N位的椭圆曲线点乘,需要的时间约为55.5N·I, 其中,I是一个L/2位的乘法、一次保留进位加法、一个L/2位的加法的总延时。     

基于Montgomery的分段并行标量乘快速算法

在椭圆曲线二进制域上,Montgomery算法利用在计算kP过程中只需计算x坐标,在最后才恢复y坐标的特性,使该算法的计算量更少。在此基础上提出基于Montgomery的分段并行标量乘算法来更进一步提高算法的效率,经分析,将整数标量分两段并行计算,算法效率可提高约25%,将其分三段时其效率可提高约37%。通过编程实现验证了新算法的效率确实有明显提高,新算法对椭圆曲线标量乘快速实现有实际意义。     

GF(2m)域椭圆曲线点乘算法安全FPGA设计与实现

点乘算法是椭圆曲线密码体制中决定速度和硬件资源的关键部分。在深入分析混合结构乘法器并在FPGA上实现经典椭圆曲线点乘算法基础上,设计与实现了一种基于NAF编码混合结构乘法器思想的椭圆曲线点乘算法。对实现的点乘算法进行仿真测试和性能评估表明,新设计实现的基于混合结构乘法器的点乘算法在计算速度和资源使用上具有明显优势。     

基于折半运算的快速双基数标量乘算法

为了提高椭圆曲线标量乘法效率,对二元域上椭圆曲线的基于双基数的标量乘法进行改进。在底层域推导出直接计算3^kP的快速算法,该算法只需一次求逆;新设计的以1/2和3为基的双基数编码可结合高效的直接计算3^kP和折半运算,基于该双基数编码的标量乘算法只涉及到点加运算、折半运算、三倍点和直接计算3^kP,底层域运算复杂性得到降低,在NIST推荐的椭圆曲线上比Dimitrov算法效率提高70%以上,比Wong方法提高10%以上。     

Edwards曲线上的快速标量乘法算法

在特征不等于2的域上,将椭圆曲线转换为与其双有理等价的Edwards曲线,可以有效提高ECC的软、硬件实现速度。首先简化了Edwards曲线上倍点的计算公式,然后根据连续倍点2mP(m=2,3,…)的坐标具有统一表示形式的特征,基于递归技术提出了一种计算2mP的连续倍点算法(CDA)。通过算法的复杂性分析与实例计算表明：CDA可使Edwards曲线上标量运算的速度提高10%以上。     

Edwards曲线快速标量乘算法研究

标量乘法是椭圆曲线密码算法中最核心的运算,其运算速度影响着整个密码体制的实现效率。首先,详细地介绍了Edwards曲线的基本概念。其次,为了提高标量乘法的运算速度,针对椭圆曲线标量乘算法进行了研究,引入了一种可以用来计算连续倍点2◢△mP◣的算法CDA。为了提高CDA的计算效率,提出了将标量◢k◣表示为4-NNAF形式以减少◢k◣的长度,再结合CDA计算标量乘法可以有效地减少运算量。最后根据算法的运算量分析和具体例子得出,减少标量◢k◣长度后的计算效率提高了13%以上。为了进一步加快运算速度,又提出了对CDA中乘法运算和模逆运算采用并行结构来减少标量乘法的运算次数。计算结果表明,并行后的计算效率提高了36%以上。     

椭圆曲线密码体制上的一种快速算法

本文分析了已有的一些计算椭圆曲线上点乘运算的快速算法,定义了整数阶乘展开式,并提出一种新的基于阶乘展开式的计算椭圆曲线上点乘的快速算法。对于200位的大整数点乘,与二进制算法相比,本文算法的倍点数减少了11％,点加数也有较大的减少。     

基于ECC算法的UKey安全认证与应用*

针对文件安全问题,提出高安全椭圆曲线加密方案,并将其结合到UKey中,研制出基于ECC算法的UKey管理工具。通过UKey安全身份认证功能,有效解决了文件的安全存储和安全传输两大难题,并提出了软件与网站知识产权保护的解决思路。