网站的详细设计,室内设计和平面设计区别,wordpress 获取文章文字,福建漳州网站建设费用本篇博文介绍针对椭圆曲线签名算法的基于格攻击的密钥恢复方法#xff0c;本研究将这种方法应用于椭圆曲线签名算法。针对椭圆曲线算法的攻击研究一般主要集中于算法的两个运算阶段#xff0c;即标量乘阶段和组合阶段。对于椭圆曲线签名算法#xff0c;针对标量乘阶段的攻击…本篇博文介绍针对椭圆曲线签名算法的基于格攻击的密钥恢复方法本研究将这种方法应用于椭圆曲线签名算法。针对椭圆曲线算法的攻击研究一般主要集中于算法的两个运算阶段即标量乘阶段和组合阶段。对于椭圆曲线签名算法针对标量乘阶段的攻击目标是恢复标量即随机数的值。在只能获取随机数一部分比特信息的情况下结合格基归约的方法仍然可以恢复密钥。这使得我们在攻击带有防护的算法实现时可以考虑尝试恢复随机数一部分信息而不是必须恢复完整的数值。这种使用格基归约的攻击方法称作格攻击需要我们解决的问题就是如何将恢复密钥的问题归约到格上的最短向量问题。
签名算法密钥恢复问题的转化方法
格和隐数问题
给定一个素数 p p p, 记 ⌊ s ⌋ p \lfloor s \rfloor _p ⌊s⌋p 为 s s s 除以 p p p的模数则隐数问题表述如下给定若干数量随机选取的整数 t i ∈ F p t_i \in F_p ti∈Fp 和一个固定的未知整数 α \alpha α, 在二进制表示下已知 ⌊ α t i ⌋ p \lfloor \alpha t_i \rfloor _p ⌊αti⌋p的最高 l l l 比特信息要求恢复 α \alpha α的值整数 x ∈ F p x \in F_p x∈Fp的最高 l l l 比特信息记为 M S B l , p ( x ) MSB_{l,p}(x) MSBl,p(x). 定义1格 LATTICE,设 R m R^m Rm是 m m m 维欧式空间给定 n n n 个线性无关向量 b 1 , b 2 , . . . b n ∈ R m b_1,b_2,...b_n \in R^m b1,b2,...bn∈Rm,则由这些向量生成的格 L L L定义为这 n n n格向量的所有整数线性组合组成的集合。 L { ∑ i 1 n x i b i ∣ x i ∈ Z } L \{\sum_{i1}^{n}x_i b_i | x_i \in Z\} L{i1∑nxibi∣xi∈Z} 这 n n n 个向量 { b 1 , b 2 , . . . b n ∈ R m } \{b_1,b_2,...b_n \in R^m\} {b1,b2,...bn∈Rm}设为格 L L L的一组基。如果以这 n n n 个列向量构成 m × n m \times n m×n 矩阵 B则格 L L L同样可定义为矩阵 B B B 生成 L ( B ) { B x ∣ x ∈ Z n } { v ∈ R n ∣ ( v ) ∑ i 1 n x i b i ∣ x i ∈ Z L(B) \{Bx|x\in Z^n\}\{v\in R^n|(v)\sum_{i1}^{n}x_i b_i | x_i \in Z L(B){Bx∣x∈Zn}{v∈Rn∣(v)i1∑nxibi∣xi∈Z 当 m n mn mn时格 L L L称为满格。 最近向量问题是格中一个基本问题其定义如下给定格 L L L和一个目标向量 u ∈ R n u\in R^n u∈Rn 且 u u u不在个 L L L中找到一个向量 v ∈ L v\in L v∈L使得 u u u和 v v v之间的欧式距离 ∣ ∣ u − v ∣ ∣ ||u-v|| ∣∣u−v∣∣最小。
考虑隐数问题的一个实例随机选取 t 1 , . . . t d t_1,...t_d t1,...td并定义相应的最高 l l l 比特信息 u i M S B l , p ( ⌊ α t i ⌋ p ) u_iMSB_{l,p}(\lfloor \alpha t_i \rfloor _p) uiMSBl,p(⌊αti⌋p).此时给定 t 1 , . . . t d t_1,...t_d t1,...td u 1 , . . . u d u_1,...u_d u1,...ud以及 l l l 和 p p p,我们的目标是获取隐藏数值 α \alpha α。有 u i − ⌊ α t i ⌋ p ≤ p / 2 l 1 u_i-\lfloor \alpha t_i \rfloor _p \leq p/2^{l1} ui−⌊αti⌋p≤p/2l1,这里包含了 d d d个不等式。此时我们可以将这 d d d个不等式解释成是一个由 u i u_i ui构成的向量与另一个与 α \alpha α有关的向量之间的距离很小。引入一个由如下矩阵生成的格 L ( B ) L(B) L(B). B ( p 0 ⋯ 0 0 0 p ⋱ ⋮ ⋮ ⋮ ⋱ ⋱ 0 ⋮ 0 ⋯ 0 p 0 t 1 ⋯ ⋯ t d 1 / 2 l 1 ) B \begin{pmatrix} p 0 \cdots 0 0 \\ 0 p \ddots \vdots \vdots \\ \vdots \ddots \ddots 0 \vdots \\ 0 \cdots 0 p 0\\ t_1 \cdots \cdots t_d 1/2^{l1}\\ \end{pmatrix} B p0⋮0t10p⋱⋯⋯⋯⋱⋱0⋯0⋮0ptd0⋮⋮01/2l1
构建一个属于格 L ( B ) L(B) L(B)的行向量 y ( ⌊ α t 1 ⌋ p , . . . ⌊ α t d ⌋ p , α / 2 l 1 ) y (\lfloor \alpha t_1 \rfloor _p ,...\lfloor \alpha t_d \rfloor _p ,\alpha/2^{l1}) y(⌊αt1⌋p,...⌊αtd⌋p,α/2l1)显然向量 y y y 与另一个属于格 L L L的行向量 u ( u 1 , . . . u d , 0 ) u (u_1,...u_d,0) u(u1,...ud,0)之间的距离很近即满足 ∣ ∣ y − u ∣ ∣ ∞ p / 2 l 1 ||y-u||_\infty p/2^{l1} ∣∣y−u∣∣∞p/2l1. 向量 y y y 暴露了 α \alpha α的信息将其称作隐藏向量。 此时我们向最近向量问题靠拢。 m i n { ∣ ∣ u − w ∣ ∣ ; w ∈ L ( B ) } ≤ d 1 p / 2 l 1 min \{||u-w||; w\in L(B)\} \leq \sqrt{d1}p/2^{l1} min{∣∣u−w∣∣;w∈L(B)}≤d1 p/2l1 然后应用上述最近向量问题的描述我们需要求解一个向量 v ∈ L ( B ) v \in L(B) v∈L(B)使得 ∣ ∣ u − v ∣ ∣ ≤ 2 ( d 1 ) / 4 m i n { ∣ ∣ u − w ∣ ∣ ; w ∈ L ( B ) } ≤ d 1 2 ( d 1 ) / 4 p / 2 l 1 ||u-v||\leq 2^{(d1)/4} min \{||u-w||; w\in L(B)\} \leq \sqrt{d1} 2^{(d1)/4} p/2^{l1} ∣∣u−v∣∣≤2(d1)/4min{∣∣u−w∣∣;w∈L(B)}≤d1 2(d1)/4p/2l1 进而我们得到格向量 y − v y-v y−v满足如下等式 ∣ ∣ y − v ∣ ∣ ∞ ≤ ∣ ∣ y − u ∣ ∣ ∞ ∣ ∣ u − v ∣ ∣ ≤ p ( 1 d 1 2 ( d 1 ) / 4 ) 2 l 1 ||y-v||_{\infty} \leq ||y-u||_{\infty}||u-v||\leq \frac{p(1\sqrt{d1}2^{(d1)/4})}{2^{l1}} ∣∣y−v∣∣∞≤∣∣y−u∣∣∞∣∣u−v∣∣≤2l1p(1d1 2(d1)/4)
当 l l l已知的最高比特位数和 d d d 不同 t i t_i ti的个数足够大时向量 y − v y-v y−v很大概率是一个零向量。即我们通过解决最近向量问题得到的结果 v v v在很大概率下就是我们所需要的隐藏向量 y y y。
SM2签名算法密钥恢复问题的转化
以SM2签名算法为例把密钥签名私钥的问题归约到隐数问题。假设已知随机数 k k k的最低 l l l比特信息定义这部分信息为 l s b l ( k ) lsb_l(k) lsbl(k)则 k 2 l b l s b l ( k ) k2^l b lsb_l(k) k2lblsbl(k)其中 b b b是一个不小于0的整数随机数。显然 b n / 2 l b n/2^l bn/2l。将等式带入到公式 s ( k r ) ( 1 d A ) − 1 − r m o d n s (kr) (1d_A)^{-1}-r \mod n s(kr)(1dA)−1−rmodn,得到下式 b ( s r ) 2 − l d A − ( l s b l ( k ) − s ) 2 − l m o d n b (sr)2^{-l}d_A-(lsb_l(k)-s)2^{-l} \mod n b(sr)2−ldA−(lsbl(k)−s)2−lmodn 定义 t ⌊ ( s r ) 2 − l ⌋ n t \lfloor (sr)2^{-l}\rfloor_n t⌊(sr)2−l⌋n 以及 u ⌊ ( l s b l ( k ) − s ) 2 − l ⌋ n u \lfloor(lsb_l(k)-s)2^{-l}\rfloor_n u⌊(lsbl(k)−s)2−l⌋n,则等式简化为 b d A t − u m o d n bd_A t - u \mod n bdAt−umodn。 ∣ x ∣ n |x|_n ∣x∣n表示将 x x x约减到 [ − n / 2 , n / 2 ) [-n/2,n/2) [−n/2,n/2)范围内约减的方法是不断将 x x x减去 n n n直到 x x x小于 n / 2 n/2 n/2。此时由于 b ≤ n / 2 l b\leq n/2^l b≤n/2l得到如下不等式。 0 ≤ ⌊ d A t − u ⌋ n ≤ n / 2 l 0 \leq \lfloor d_A t - u \rfloor _n \leq n/2^l 0≤⌊dAt−u⌋n≤n/2l 进而得到 ∣ d A t − u − n / 2 l 1 ∣ n ≤ n / 2 l 1 | d_A t - u - n/2^{l1}|_n \leq n/2^{l1} ∣dAt−u−n/2l1∣n≤n/2l1 令 v 2 l 1 u n v2^{l1}un v2l1un, 则得到 ∣ d A t − v / 2 l 1 ∣ n ≤ n / 2 l 1 | d_A t - v/2^{l1}|_n \leq n/2^{l1} ∣dAt−v/2l1∣n≤n/2l1 根据隐数问题的定义在这种条件下 v / 2 l 1 v/2^{l1} v/2l1 即表示 ⌊ d A t ⌋ n \lfloor d_A t \rfloor _n ⌊dAt⌋n 的最高 l l l比特信息。现在给定 d d d组签名结果 ( r i , s i ) (r_i, s_i) (ri,si)计算每一组的 ( t i , v i ) (t_i,v_i) (ti,vi)。即 t i ⌊ ( s i r i ) 2 − l ⌋ n t_i \lfloor (s_ir_i)2^{-l}\rfloor_n ti⌊(siri)2−l⌋n v i 2 l 1 ⌊ ( l s b l ( k ) − s ) 2 − l ⌋ n n v_i 2^{l1}\lfloor(lsb_l(k)-s)2^{-l}\rfloor_n n vi2l1⌊(lsbl(k)−s)2−l⌋nn 满足 ∣ d A t i − v i / 2 l 1 ∣ n ≤ n / 2 l 1 | d_A t_i - v_i/2^{l1}|_n \leq n/2^{l1} ∣dAti−vi/2l1∣n≤n/2l1 构建一个 d 1 d1 d1维的格 L ( B ′ ) L(B) L(B′)这个格由如下矩阵 B ′ B B′生成 B ′ ( n 0 ⋯ 0 0 0 n ⋱ ⋮ ⋮ ⋮ ⋱ ⋱ 0 ⋮ 0 ⋯ 0 n 0 t 1 ⋯ ⋯ t d 1 / 2 l 1 ) B \begin{pmatrix} n 0 \cdots 0 0 \\ 0 n \ddots \vdots \vdots \\ \vdots \ddots \ddots 0 \vdots \\ 0 \cdots 0 n 0\\ t_1 \cdots \cdots t_d 1/2^{l1}\\ \end{pmatrix} B′ n0⋮0t10n⋱⋯⋯⋯⋱⋱0⋯0⋮0ntd0⋮⋮01/2l1 隐藏向量 y ( ⌊ d A t 1 ⌋ n , . . . ⌊ d A t d ⌋ n , d A / 2 l 1 ) y (\lfloor d_A t_1 \rfloor _n ,...\lfloor d_A t_d \rfloor _n ,d_A/2^{l1}) y(⌊dAt1⌋n,...⌊dAtd⌋n,dA/2l1) 与向量 v ( v 1 / 2 l 1 , v 2 / 2 l 1 , . . . , v d / 2 l 1 , 0 ) v (v_1/2^{l1},v_2/2^{l1},...,v_d/2^{l1},0) v(v1/2l1,v2/2l1,...,vd/2l1,0)之间的距离很接近。因此可按上一节介绍的最近向量问题求解隐藏向量。 与SM2类似由于随机数 k k k可以表示为 k 2 l b l s b l ( k ) k 2^lb lsb_l(k) k2lblsbl(k)则有 b s − 1 r 2 − l d A − ( l s b l ( k ) − s − 1 z ) 2 − l m o d n b s^{-1} r 2^{-l}d_A-(lsb_l(k)-s^{-1}z)2^{-l} \mod n bs−1r2−ldA−(lsbl(k)−s−1z)2−lmodn 令 t s − 1 r 2 − l ts^{-1}r2^{-l} ts−1r2−l以及 u ( l s b l ( k ) − s − 1 z ) 2 − l u (lsb_l(k)-s^{-1}z)2^{-l} u(lsbl(k)−s−1z)2−l,后续推导同SM2类似不做赘述。
