Page 146 - 《软件学报》2025年第10期
P. 146

程石 等: 基于两种新标量表示的安全高效标量乘算法                                                       4543


                 椭圆曲线点乘运算的效率和安全性被专门研究.
                    由于非相邻型表示        (non-adjacent form, NAF) 相较二进制表示能够减少标量的汉明重量, 因此基于窗口的
                 NAF  算法能够显著提高标量乘算法的效率. Okeya 等人            [4] , Anagreh  等人  [5] 和  Hu  等人  [6] 通过对标量  k 进行了  NAF
                           k 的汉明重量, 进一步提高了算法效率.
                 编码, 降低了
                    随着侧信道攻击的不断发展, 诸如简单功耗分析               (simple power analysis, SPA) 攻击  [7] , 差分能量分析  (differential
                 power analysis, DPA) 攻击  [7] 等对密码算法造成了巨大的威胁, wNAF     算法的安全隐患也日渐显露, 使用时可能存
                 在侧信道泄漏并被攻击者加以利用. 2022           年, Cao  等人  [8] 通过一种扩展的密钥恢复攻击了基于        wNAF  的  SM2  签名
                 算法; 2023  年, Ma 等人  [9] 通过  Flush+Reload  攻击来破解基于  wNAF  的  ECDSA  算法.
                    因此, 许多学者从兼顾安全与性能两方面对椭圆曲线标量乘算法进行研究, 其中针对                           NAF  编码的安全高效算
                 法有着较多方案. 张涛等人        [10] 提出了一种基于改进     wNAF  的标量乘算法     RWNAF (refined width-w NAF), 将原先
                 wNAF  算法生成的    NAF  序列变得规则, 并借助掩码, 实现了抗          SPA, DPA  等攻击的安全标量乘算法; Yao      等人  [11]
                 在文献   [10] 的基础上通过采用碎片窗口         NAF  的处理, 所实现的     FWNAF (fractional width-w NAF) 算法相较于
                 RWNAF  算法对存储资源的利用率更高; 史量等人               [12] 在此基础上通过采用带门限的动态窗口方法, 所实现的
                 DWNAF (dynamic width-w NAF) 算法大大减少了预计算开销, 但生成算法的时间消耗相较                 RWNAF   和  FWNAF
                 算法更大, 适用于水下声传感器等信道时延较大的应用场景. 目前已有的工作中, 改进                          NAF  编码的安全高效算法
                 大部分与   RWNAF  算法相关, RWNAF    算法中采用随机掩码的方式来规避             DPA  攻击, 存在被  Flush+Reload  攻击进
                 而获取密钥等隐私信息的可能. 如果在            RWNAF  算法的基础上进行适当的优化, 就能得到更高效, 更安全的算法.
                                                                                        l
                    多标量乘算法也是椭圆曲线密码体制的重要组成部分, 通常表示为                      [k]P+[l]Q, 其中  k 和   表示两个整数,  P, Q
                 表示椭圆曲线上两点. 同样由于侧信道攻击的影响, 许多密码学者研究安全高效的多标量乘法. Lee                            [13] 首先提出了
                 一种抗   SPA  的多标量乘法, Ciet 等人   [14] 和  Liu  等人  [15] 也给出了不同格式的抗  SPA  的多标量乘法. 陈厚友等人    [16]
                 在此基础上提出了一种改进算法, 有效提升了多标量乘算法的效率. Akishita 等人                    [17] 提出了一种名为联合正则形
                 式  (joint regular form, JRF) 的算法, 并基于此实现了抗  SPA  的多标量乘法. 但是目前的主流多标量乘算法大多只
                 针对  SPA  攻击而没有考虑     DPA, RPA, ZPA  攻击等, 在安全性上还有所欠缺.
                    本文主要工作如下.
                    (1) 提出了一种新的      NAF  生成算法   OWNAF (ordered window width non-adjacent form), 并通过生成的
                 OWNAF  序列和随机密钥分割的方法实现了新的高效标量乘算法, 在增加一定存储开销的基础上提升了计算效
                 率, 同时能够有效地抵抗       SPA, DPA  等侧信道攻击, 并对    Flush+Reload  攻击方法产生了一定的干扰.
                    (2) 从  JRF  算法生成序列的特点出发, 通过对标量乘算法的适当变换, 给出基于                  JRF  的安全标量乘算法, 在保
                 证安全的前提下存储开销较小, 非常适合智能卡等存储资源受限的环境, 并且更进一步将                            JRF  推广为  wJRF, 并基
                 于  wJRF  提出一种安全高效多标量乘算法, 在减少计算量的同时能有效抵抗                    DPA, RPA, ZPA  等侧信道攻击, 提高
                 了安全性.
                    本文第   1  节主要介绍所需要的预备知识. 第          2  节主要介绍   OWNAF  的生成算法以及相应的标量乘算法. 第            3
                 节描述   wJRF  标量形式和基于    wJRF  的多标量乘法. 最后总结全文.

                  1   基础知识

                    本文所提方法主要基于         RWNAF  算法和联合正则形式算法进行优化, 下面就相关概念和基本知识予以介绍.
                 相关符号说明见后文表        1.
                  1.1   RWNAF  标量乘法
                    非相邻型表示      (NAF) 是带符号数的一种表示方法, 顾名思义, NAF          表示中的非     0 值不能相邻, 取值为    {0,1,−1},
                                                                                                 ∑ len−1
                 引入窗口算法即为       wNAF  形式, 任何连续的    w  个位中最多有    1  位非  0. 将一个标量  k 表示为  NAF w (k) =   k i 2 i
                                                                                                   i=0
                 的形式, 其中非    0  的   k i  均为奇数且  |k i | < 2 w−1 .
   141   142   143   144   145   146   147   148   149   150   151