漳州网站开发制作棋牌,世界杯数据分析,上海最新新闻,湛江网红打卡餐厅SM2 算法中底层模块抗侧信道 标量乘 ( [ k ] G [k]G [k]G) 运算过程中需要用到大量的倍点运算与点加运算。传统倍点运算与点加运算之间由于需要的运算次数不同#xff0c;功耗存在明显区别#xff0c;攻击者可以通过功耗波形特征分析密钥信息。传统算法如下图所示#xff1a…SM2 算法中底层模块抗侧信道 标量乘 ( [ k ] G [k]G [k]G) 运算过程中需要用到大量的倍点运算与点加运算。传统倍点运算与点加运算之间由于需要的运算次数不同功耗存在明显区别攻击者可以通过功耗波形特征分析密钥信息。传统算法如下图所示 在传统算法中 d i d_i di 等于 0 0 0 和 1 1 1 对应不同的执行指令图中符号 Π 0 \Pi_0 Π0 代表倍点运算符号 Π 1 \Pi_1 Π1 代表点加运算。可参考侧信道原子算法调整点加和倍点运算过程中寄存器运算顺序采用原子块形式将点加运算和倍点运算都划分为若干个原子小块每个小块先进行模乘运算再进行模加运算最后进行模减运算其结构表示为 Γ \Gamma Γ。用 ☆’表示不影响最终结果的一次加/减的空操作。如此实际计算过程中总在执行一组组相同操作点加和倍点之间的功耗曲线将变得更加连续从而达到抗SPA攻击的目的。以固定参数倍点运算和固定点加运算为例如表1所示是改进的原子小块点加运算如表2所示是改进的原子小块倍点运算。
表1 改进的原子小块点加运算
表2 改进的原子小块倍点运算
SM2 算法中标量乘抗侧信道模块 NAF 标量乘法算法是标量乘法算法的一种增强该算法使用了非邻接形式Non-Adjacent Form表达减少了算法的期望运行时间。下面是具体算法细节 将 标量表示为 k ∑ i 0 l − 1 k i × 2 i k \sum_{i0}^{l-1}k_i\times 2^i k∑i0l−1ki×2i其中 k i ∈ { 0 , , − } k_i\in \{0,,-\} ki∈{0,,−}。一个十分有用的有符号整数表达规定 k l − 1 ≠ 0 k_{l-1}\neq 0 kl−10且没有两个相邻的 k i 0 k_i 0 ki0。 NAF 表示有如下性质
每个正整数 k k k 都有独一无二的 NAF 表达。记作 N A F ( k ) NAF(k) NAF(k) N A F ( k ) NAF(k) NAF(k) 有所有 k k k的有符号表达最少得非零数字 N A F ( k ) NAF(k) NAF(k) 的长度最多比二进制表达多1位;如果 N A F ( k ) NAF(k) NAF(k)长度为 l l l那么有 2 l 3 k 2 l 1 3 \frac{2^l}{3}k\frac{2^{l1}}{3} 32lk32l1;在所有长度为 l l l 的 NAF中非零系数的概率约为 1 / 3 1/3 1/3 N A F ( k ) NAF(k) NAF(k) 能够通过以下算法计算 输入 : 正整数 k k k 输出 : N A F ( k ) NAF(k) NAF(k) i ← 0 i\leftarrow 0 i←0 当 k ≥ 0 k \geq 0 k≥0 执行 若 k k k 为奇数则 k i ← 2 − ( k m o d 4 ) k_i\leftarrow 2-(k \mod 4) ki←2−(kmod4) k ← k − k i k\leftarrow k-k_i k←k−ki 否则 k i ← 0 k_i\leftarrow 0 ki←0 k ← k / 2 k\leftarrow k/2 k←k/2 i ← i 1 i \leftarrow i1 i←i1 返回 ( k i − 1 , k i − 2 , ⋯ k 1 , k 0 k_{i-1},k_{i-2},\cdots k_1,k_0 ki−1,ki−2,⋯k1,k0)
最后可以通过 N A F ( k ) NAF(k) NAF(k) 代替 k k k 的二进制表示来修改标量乘从左至右的二进制方法 输入 : 正整数 k k k 输出 : [ k ] P [k]P [k]P 根据上一个算法将正整数 k k k 表示为 N A F ( k ) NAF(k) NAF(k) Q ← O Q\leftarrow O Q←O i i i 从 l − 1 l-1 l−1 至 0 0 0 执行 Q ← 2 Q Q \leftarrow 2Q Q←2Q 若 k i 1 k_i 1 ki1 则 Q ← Q P Q\leftarrow QP Q←QP 若 k i − 1 k_i -1 ki−1 则 Q ← Q − P Q\leftarrow Q-P Q←Q−P 返回(Q)
随机NAF窗口法 传统的NAF因为扰乱了带有规律的点加和倍点二进制编码顺序因而可以成功抵抗 SPA 攻击又由于传统的NAF在进行点加运算时点为固定值标量乘中 k k k 的值固定时NAF编码数值也就确定了攻击者可以通过采集大量的功耗曲线并进行相关性波形分析通过波形分析猜测出倍点与点加的位置及点加运算对应的操作点从而恢复 k k k 值实现 DPA 攻击。 对于以上的情况可以将随机数应用于 NAF 标量乘通过随机数将 NAF 编码进行随机化来躲避固定值运算带来的隐患。第一步先选取一个随机数 l l l其 l ∈ [ 0 , ( n − 1 ) / m ] l\in [0,(n-1)/m] l∈[0,(n−1)/m] n n n为值 k k k的位数 m m m为自选值第二步再选取一个随机数 w w w ,使 w ∈ [ 2 , m w ] w\in [2,m_w] w∈[2,mw] m w m_w mw 的大小要在预计算表的范围内。第三步循环进行计算 NAF 值当 i l , 2 l , ⋯ , m l il,2l,\cdots,ml il,2l,⋯,ml 时重新选取 w w w。 N A F w ( k ) NAF_w(k) NAFw(k) 能够通过以下算法计算 输入 : 正整数 k k k 输出 : N A F w ( k ) NAF_w(k) NAFw(k) i ← 0 i\leftarrow 0 i←0 选择随机数 l ∈ [ 0 , ( n − 1 ) / m ] , w ∈ [ 2 , m w ] l \in[0,(n-1)/m], w\in[2,m_w] l∈[0,(n−1)/m],w∈[2,mw] 当 k ≥ 0 k \geq 0 k≥0 执行 判断 i i i 是否等于 l , 2 l , ⋯ , m l l,2l,\cdots,ml l,2l,⋯,ml相等则重新选取 随机数 w w w 否则 若 k k k 为奇数则 k i ← k m o d 2 w k_i\leftarrow k \mod 2^w ki←kmod2w k ← k − k i k\leftarrow k-k_i k←k−ki 否则 k i ← 0 k_i\leftarrow 0 ki←0 k ← k / 2 k\leftarrow k/2 k←k/2 i ← i 1 i \leftarrow i1 i←i1 返回 ( k i − 1 , k i − 2 , ⋯ k 1 , k 0 k_{i-1},k_{i-2},\cdots k_1,k_0 ki−1,ki−2,⋯k1,k0) 根据以上算法可以看出NAF值存在不固定的变化每一次执行标量乘 k k k 对应的NAF编码各不相同含有很大程度的随机性因包含不确定的 k i k_i ki 值所以攻击者做相关性功耗分析时就要有庞大的功耗波形及数据分析来做支持所以也可以抗DPA攻击。在进行模板攻击时因为 NAF 的编码形式存在多样性故攻击者也没法建立所有模板因此也适用在抗模板攻击方法中。
改进的蒙哥马利阶梯算法 标准的蒙哥马利标量乘算法如下 标准的蒙哥马利算法容易受到倍点攻击当 k 157 ( 10011101 ) 2 k 157 (10011101)_2 k157(10011101)2 时蒙哥马利计算过程如下表所示其中标蓝的部分为倍点运算相同处。当 k i k i 1 k_ik_{i1} kiki1 时 [ k ] P [k]P [k]P 的第 i 1 i1 i1 步和 [ k ] 2 P [k]2P [k]2P 的第 i i i步计算的倍点步骤一样对两条曲线对齐看临近的倍点运算曲线相同就能知道 k i k i 1 k_ik_{i1} kiki1攻击者能知道 k k k 的相邻比特位之间的关系只需猜测首位是 0 0 0 还是 1 1 1再根据关系推测其他位置就能推测全部标量值 k k k。 采用改进的蒙哥马利标量乘法如以下算法。标量 k k k 不论为 1 1 1 或 0 0 0 都需做一次点加和一次倍点可抗 SPA。添加随机点 R R R 与随机坐标 Z l Z_l Zl, 使得中间值含有随机成分可抗DPA。随机成分的存在使得无法建立模板可以抗TA。基于盲化后不能自己选择输入点 P P P因此可抗 DA RPAZPA。
变换公式法 在数据传输过程中数据的不可否认性非常重要为此人们提出了数字签名技术。SM2签名算法中包含了大数模乘 r ⋅ d A r\cdot d_A r⋅dA其中 r r r 是已知变量 d A d_A dA 是未知常量。大数模乘会涉及大量的中间数据攻击者能够根据已知的 r r r 反推出与 d A d_A dA相关的中间数据然后分析功耗与中间数据之间的相关性来确定私钥 d A d_A dA。这种方法攻击的实质是对乘法器进行攻击为了预防这种攻击对签名中公式进行如下变形。 s ( ( 1 d A ) − 1 ⋅ ( k − r ⋅ d A ) ) m o d n [ ( 1 d A ) − 1 ⋅ k − ( 1 d A ) − 1 ⋅ r ⋅ d A ] m o d n [ ( 1 d A ) − 1 ⋅ k − ( 1 d A ) − 1 ⋅ ( 1 d A − 1 ) ⋅ r ] m o d n [ ( 1 d A ) − 1 ⋅ k − ( 1 d A ) − 1 ⋅ ( 1 d A ) ⋅ r ( 1 d A ) − 1 ⋅ r ] m o d n [ ( 1 d A ) − 1 ⋅ k − ( 1 d A ) − 1 ⋅ r − r ] m o d n [ ( 1 d A ) − 1 ⋅ ( k r ) − r ] m o d n \begin{align} s ((1d_A)^{-1}\cdot (k-r \cdot d_A))\mod n\\ [(1d_A)^{-1}\cdot k - (1d_A)^{-1}\cdot r \cdot d_A]\mod n\\ [(1d_A)^{-1}\cdot k - (1d_A)^{-1}\cdot (1d_A-1)\cdot r] \mod n\\ [(1d_A)^{-1}\cdot k - (1d_A)^{-1}\cdot (1d_A)\cdot r (1d_A)^{-1}\cdot r ] \mod n\\ [(1d_A)^{-1}\cdot k - (1d_A)^{-1}\cdot r - r] \mod n\\ [(1d_A)^{-1}\cdot (kr)-r]\mod n \end{align} s((1dA)−1⋅(k−r⋅dA))modn[(1dA)−1⋅k−(1dA)−1⋅r⋅dA]modn[(1dA)−1⋅k−(1dA)−1⋅(1dA−1)⋅r]modn[(1dA)−1⋅k−(1dA)−1⋅(1dA)⋅r(1dA)−1⋅r]modn[(1dA)−1⋅k−(1dA)−1⋅r−r]modn[(1dA)−1⋅(kr)−r]modn 公式变形之后公式中不再含有易受攻击的 r ⋅ d A r\cdot d_A r⋅dA。攻击者便无法针对 r ⋅ d A r\cdot d_A r⋅dA 进行差分功耗攻击。此外利用此公式只需进行一次模逆和一次模乘比原公式减少了一次模乘在运算上也有减少。
