基于GPU的zk-SNARK中多标量乘法的并行计算方法

针对zk-SNARK(zero-knowledge succinct non-interactive argument of knowledge)中计算最为耗时的多标量乘法(multiscalar multiplication,MSM),提出了一种基于GPU的MSM并行计算方案。首先,对MSM进行细粒度任务分解,提升算法本身的计算并行性,以充分利用GPU的大规模并行计算能力。采用共享内存对同一窗口下的子MSM并行规约减少了数据传输开销。其次,提出了一种基于底层计算模块线程级任务负载搜索最佳标量窗口的窗口划分方法,以最小化MSM子任务的计算开销。最后,对标量形式转换所用数据存储结构进行优化,并通过数据重叠传输和通信时间隐藏,解决了大规模标量形式转换过程的时延问题。该MSM并行计算方法基于CUDA在NVIDIA GPU上进行了实现,并构建了完整的零知识证明异构计算系统。实验结果表明:所提出的方法相比目前业界最优的cuZK的MSM计算模块获得了1.38倍的加速比。基于所改进MSM的整体系统比业界流行的Bellman提升了186倍,同时比业界最优的异构版本Bellperson提升了1.96倍,验证了方法的有效性。

抗SPA攻击的Twisted Edwards曲线标量乘法实现

椭圆曲线密码(Elliptic Curve Cryptography,ECC)是一种非对称密码,在信息安全领域中扮演着越来越重要的角色。目前对椭圆曲线密码的研究大多针对Weierstrass曲线,对于Twisted Edwards曲线的研究较少。针对Twisted Edwards曲线上标量乘法的效率及安全性,将Twisted Edwards曲线转换为Montgomery曲线,并采用Montgomery标量乘法在每次循环中都固定进行点加和倍点计算,从而能够抵抗简单能量攻击(Simple Power Analysis,SPA)。最后在复旦微电子公司型号为JFM7K325T的现场可编程门阵列(Field Programmable Gate Array,FPGA)中进行了实现和测试。结果表明,该方法能达到较理想的效果。

基于FPGA的高速椭圆曲线标量乘法结构

椭圆曲线密码系统是最近十几年来获得迅速发展的一类密码系统.为了提高椭圆曲线密码系统的处理速度,针对其中最关键的运算——椭圆曲线标量乘法设计并实现了一种基于FPGA的硬件结构,完成GF(2m)上的椭圆曲线标量乘法计算.该结构最大程度地对标量乘算法的内部模块进行了并行处理,缩短最大延迟路径,从而达到提高运算速度的目的.这一结构在FPGA上实现后,计算一次GF(2163)上的椭圆曲线标量乘法只需要36μs,这一性能是目前国际上已知的基于FPGA的标量乘法器中最好的.

一类安全椭圆曲线的选取及其标量乘法的快速计算

安全椭圆曲线的选取和标量乘法的快速计算是有效实现椭圆曲线密码体制的两个主要问题 .本文将二者结合起来考虑给出了一类适合普通PC机实现的安全椭圆曲线 ,并详细给出了选取这类曲线的具体步骤和基于“大步 小步法”思想构造了一种新的计算这类曲线上标量乘法的快速算法 .这类曲线不仅选取容易而且利用本文所提出方法计算其标量乘法时能使所需椭圆曲线运算次数大大减少 .此外 ,选用这类曲线后基域中元素不再需要专门的表示方法 ,各种运算能非常快地得到实现 。

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

求逆是标量乘法中最耗时的运算,求逆运算次数的多少直接决定标量乘法的性能。转换求逆为乘法运算能够降低求逆次数。根据这种思想,提出了素域Fp上用仿射坐标直接计算3P+Q的算法,其运算量为1I+3S+16M,比Ciet等人提出的方法节省了一次求逆运算。同时还给出直接计算3kP的算法,该算法比重复计算k次3P更有效。最后结合3-NAFw的编码方法,把两个新算法应用到标量乘法中。结果表明,运用3P+Q、3kP的标量乘法比传统的NAF、NAF4等方法更有效,相交处I/M的值可降为5.4。

一种基于随机混合坐标表示的防功耗分析标量乘法实现方法

提出了一种新的防功耗分析(包括简单和差分功耗分析simpleanddifferentialpoweranalysis)的椭圆曲线标量乘法实现方法,该方法实现简单,并且适合于各种不同有限域上椭圆曲线标量乘法的实现.该方法以模乘和模加减操作为最小调度单位,将标量乘法转换成完全随机的模乘和模加减操作序列;基于随机混合坐标表示实现点的加法和倍加操作,并随机地从点的加法和倍加操作序列中选取后续的模乘和模加减操作;任务调度与模乘和模加减操作的执行是并行的.另外,本文定量分析了该实现方法对于功耗分析的防护能力以及运算性能.

基于Markov链的椭圆曲线标量乘法算法性能分析

在椭圆曲线密码系统中 ,采用规范重编码、滑动窗口等优化技术可以有效提高椭圆曲线上点的标量乘法k·P的运算性能 ,但在实现中 ,需要对不同优化技术的算法性能进行定量分析 ,才能确定标量乘法的最优实现 .本文运用Markov链对标量k规范重编码表示的滑动窗口划分过程进行了建模 ,提出了一种对椭圆曲线标量乘法的平均算法性能进行定量分析的方法 ,并运用该方法分析了不同参数下标量乘法运算的平均性能 ,计算了滑动窗口的最优窗口大小 .最后 ,通过比较说明 ,采用规范重编码和滑动窗口技术的椭圆曲线标量乘法的运算开销比用m ary法少 10 32～ 17 32 % ,比单纯采用滑动窗口法也要少 4 5 3～ 8 4 0 % .

Edwards曲线安全快速标量乘法运算算法——EDSM

对Edwards曲线上标量乘法的安全及快速算法进行研究,首先提出新的倍点及点加公式,分析表明,其运算效率优于Edwards曲线上的已有公式;其次给出一种新的安全快速的标量乘法运算算法——EDSM算法;最后将EDSM算法与改进的Montgomery算法以及已有的安全快速算法在安全性和效率上进行比较,结果表明,EDSM算法在运算效率方面和安全性方面均有显著的提高。

基于半点运算与多基表示的椭圆曲线标量乘法

椭圆曲线密码体制的实现速度依赖于曲线上标量乘法的运算速度。在具有极小2-挠的椭圆曲线上基于半点运算的标量乘法算法优于传统的标量乘法算法。该文将半点运算运用于基于多基表示的标量乘法算法中,得到一种新的多基表示形式和基于该表示形式的标量乘法算法,有效提高了标量乘法的运算效率。

基于滑动窗口技术的快速标量乘法

标量乘法是椭圆曲线密码体制的核心运算,它的有效实现是近年来信息安全领域研究的一个热点内容。借助于标量的wMOF表示思想,利用混合坐标表示下直接计算2kQ+P的策略,改进了基于滑动窗口技术的标量乘法算法。分析表明,所得算法效率明显提升,并降低了存储需求,能有效提升ECC的实现效率。

低存储需求的快速标量乘法算法

在椭圆曲线密码体制(ECC)中,标量乘法的运算时间和存储资源消耗较大。为此,借助标量的2MOF表示,利用混合坐标系下直接计算2Q+P的策略,提出一种低存储需求的从左向右标量乘法算法。理论及实例分析表明,该算法的时间和空间消耗较少,能有效提高ECC在资源受限环境中的实现效率。

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

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

抵抗SPA和DPA的椭圆曲线上点的标量乘法

标量乘法是椭圆曲线密码体制中的一种基本算法.针对二进制方法和抵抗SPA的二进制方法无法抵抗倍点攻击和差分攻击的缺点,提出了两种改进方法.方法一给出了区分奇数和偶数的标量乘法,计算标量乘法时完全对奇数进行操作,从而能够抵抗倍点攻击.方法二采用同时随机化标量和随机化基点的方法,从而达到更好的随机性.这两种方法计算量不大且简单易行.

两类超奇异椭圆曲线的快速标量乘法

研究了特征为2和3的域上的超奇异椭圆曲线的快速标量乘法。该两类曲线适合建立可证明安全的密码体制,利用这两类曲线的复乘性质,结合Frobenius自同态和可以简单计算的自同态,给出了一种不用预计算的快速算法,相较IEEE1363标准算法,计算效率分别提高了4倍和3倍。

椭圆曲线标量乘法中标量的有效表示

标量乘法是椭圆曲线密码(ECC)的基本运算,也是最耗时的运算,其运算效率直接决定着ECC的性能.在标量乘法运算中,标量k的表示起着至关重要的作用,其长度决定了所需倍点运算量,其汉明重量决定了所需点加运算量.本文提出了一种新的标量表示方法,与目前流行的方法相比,该表示方法具有编码方式简单,汉明重量轻等优点.使用新的标量表示方法,能有效提高ECC的实现效率,尤其对于{10}m及{10}m‖1型的标量,效率提高明显.

自适应的椭圆曲线滑动窗口标量乘法

在公共密钥密码体系中,椭圆曲线加密算法是一种非常流行的方法,影响椭圆曲线算法执行效率的因素有很多,标量乘法就是一个重要因素．文中分析了几种现有的椭圆曲线标量乘法后,提出了一种改进的计算椭圆曲线标量乘法的算法,即自适应的滑动窗口标量乘算法．文中给出了改进算法中几个重要函数的实现方法,分析了改进算法的执行效率,并给出实验结果．

基于伪四维投射坐标的多基链标量乘法

针对椭圆曲线密码系统的标量乘运算开销较大和易受能量分析攻击的问题,提出基于伪四维投射坐标的快速群运算和基于伪四维投射坐标的多基链标量乘法,对椭圆曲线密码系统的群运算层和标量乘运算层进行优化,旨在提高椭圆曲线密码系统的整体性能并抵御常见的能量分析攻击。实验表明,与现有算法相比,所提算法离散群运算的倍点运算开销降低5.71%,三倍点运算开销降低3.17%,五倍点运算开销降低8.74%。此外,在密钥长度为160位的情况下,所提算法连续群运算的三倍点运算开销降低36.32%,五倍点运算开销降低17.42%,系统整体开销降低8.70%。能量波形分析表明,所提算法可以有效抵御SPA攻击和DPA攻击。

基于FPGA的Edwards曲线标量乘法实现方法

点加和倍点是标量乘法的基本运算。首先对原始的Edwards曲线计算公式进行了研究,再结合FPGA并行计算的特点,提出了一种适合FPGA快速实现的点加和倍点计算方法;其次给出了并行和串行两种标量乘法算法。最后在ALTERA的EP2AGX260 FPGA中分别对两种标量乘法进行了实现和测试。结果表明,该实现方法能达到较理想的效果。

抗SPA攻击的快速标量乘法

标量乘法是椭圆曲线密码的基本运算,也是最耗时的运算,其运算效率直接决定着椭圆曲线密码的性能,其安全性直接影响到椭圆曲线密码系统的安全性。设计了基于NAF表示的抗SPA攻击的标量乘法算法。算法迭代体每轮处理标量NAF表示的多‘位’,消除了每轮迭代的能量消耗差异,实现了抵抗SPA攻击的目标。对比分析表明,与以往研究相比,所得算法的效率有较大幅度的提升。同时,所得算法不依赖于任何密码协处理器,具有较好的通用性。

ECDSA的算法改进及其标量乘法的选取

本文从椭圆曲线数字签名的安全性和高效性要求出发,改进了椭圆曲线数字签名算法,并对其进行了正确性验证和安全性分析,结果表明,改进算法签名方不需要进行求逆运算,具有更少的时间复杂度。为了进一步提高改进算法的运算速度,文中选取了优异的快速标量乘法并对其效果进行了分析。