持续推进网站建设,php做网站难么,电子商务课程,wordpress左右滑动相册近年来基于错误的密码分析#xff08;fault-based cryptanalysis#xff09;已成为检测智能卡#xff08;Smartcard#xff09;安全的重要因素。这种基于错误的密码分析#xff0c;假设攻击者可以向智能卡中导入一定数量的、某种类型的错误#xff0c;那么智能卡会输出错… 近年来基于错误的密码分析fault-based cryptanalysis已成为检测智能卡Smartcard安全的重要因素。这种基于错误的密码分析假设攻击者可以向智能卡中导入一定数量的、某种类型的错误那么智能卡会输出错误的信息攻击者有可能利用这些错误信息揭露出嵌入在智能卡中的秘密参数如密钥。为此一些研究者提出了通过检验计算结果的正确性来防止这种攻击即如果检验结果不正确那么拒绝输出从而使攻击者无法得到想要的错误信息。 然而仅通过检验计算结果来防止这种攻击的方法不可行。以RSA中模指数运算为例提出了一种所谓基于安全错误的对RSA的攻击。该攻击可以攻破RSA的一些实现算法即使那些算法中加入了检验计算结果的步骤。
密码实现 RSA 算法中经常用到的是模幂运算 M d m o d N M^d\mod N MdmodN。其中将私钥表达成二进制的形式即 d ∑ i 0 n − 1 d i 2 i , d i ∈ { 0 , 1 } d \sum_{i0}^{n-1}d_i 2^i, d_i\in\{0,1\} d∑i0n−1di2i,di∈{0,1}。从而在密码芯片中对应R-L比特算法实现。 在算法1中当 d i 1 d_i 1 di1 时算法执行一次模乘运算( A ⋅ B 2 m o d N A\cdot B^2\mod N A⋅B2modN)和一次摸平方运算 B 2 m o d N B^2\mod N B2modN。当 d i 0 d_i0 di0时算法只需执行一次摸平方运算。 其中RSA 用到模乘运算 R A ⋅ B m o d N R A\cdot B \mod N RA⋅BmodN。将A表达成 2 t 2^t 2t进制的形式 A ∑ j 0 m − 1 A j ( 2 t ) j A j ∈ { 0 , 1 , ⋯ , 2 t − 1 } , m ⌈ n / t ⌉ A \sum_{j0}^{m-1}A_j(2^t)^j A_j\in\{0,1,\cdots,2^t-1\},m\lceil n/t \rceil A∑j0m−1Aj(2t)jAj∈{0,1,⋯,2t−1},m⌈n/t⌉。则 模乘运算的结果 R R R 可用以下表达式来实现。 R ( ( ⋯ ( ( A m − 1 B ) 2 t A m − 2 B ) 2 t ⋯ A 1 B ) 2 t A 0 B ) m o d N R ((\cdots( (A_{m-1}B)2^t A_{m-2}B)2^t\cdots A_1B)2^t A_0B) \mod N R((⋯((Am−1B)2tAm−2B)2t⋯A1B)2tA0B)modN
算法1 R-L 比特模幂 输入 M M M, d ( d n − 1 , ⋯ , d 0 ) 2 d (d_{n-1},\cdots ,d_0)_2 d(dn−1,⋯,d0)2, N N N 输出 A M d m o d N A M^d \mod N AMdmodN 1.1 A ⟵ 1 A \longleftarrow 1 A⟵1; B ⟵ M B \longleftarrow M B⟵M 1.2 for i i i from 0 0 0 to n − 1 n-1 n−1 1.3 if ( d i 1 d_i1 di1) then A ⟵ A ⋅ B m o d N A \longleftarrow A\cdot B \mod N A⟵A⋅BmodN 1.4 B ⟵ B 2 m o d N B \longleftarrow B^2 \mod N B⟵B2modN 1.5 endfor
算法2 底数为 2 t 2^t 2t的模乘运算 输入 A , B , N A,B,N A,B,N 输出 R A ⋅ B m o d N R A\cdot B \mod N RA⋅BmodN 2.1 R ⟵ 0 R \longleftarrow 0 R⟵0 2.2 for j j j from m − 1 m-1 m−1 downto 0 0 0 2.3 R ⟵ ( R 2 t A j B ) m o d N R \longleftarrow (R2^t A_j B)\mod N R⟵(R2tAjB)modN 2.4 endfor 将算法1和算法2合并起来那么R-L比特模幂运算可写成如下实现过程。
算法3 输入 M M M, d ( d n − 1 , ⋯ , d 0 ) 2 d (d_{n-1},\cdots ,d_0)_2 d(dn−1,⋯,d0)2, N N N 输出 A M d m o d N A M^d \mod N AMdmodN 3.1 A ⟵ 1 A \longleftarrow 1 A⟵1; B ⟵ M B \longleftarrow M B⟵M 3.2 for i i i from 0 0 0 to n − 1 n-1 n−1 3.3 if ( d i 1 d_i1 di1) then 3.4 R ⟵ 0 R \longleftarrow 0 R⟵0 3.5 for j j j from m − 1 m-1 m−1 downto 0 0 0 3.6 R ⟵ ( R 2 t A j B ) m o d N R \longleftarrow (R2^t A_j B)\mod N R⟵(R2tAjB)modN 3.7 endfor 3.8 A ⟵ R A \longleftarrow R A⟵R 3.9 endif 3.10 R ⟵ 0 R \longleftarrow 0 R⟵0 3.11 for j j j from m − 1 m-1 m−1 downto 0 0 0 3.12 R ⟵ ( R 2 t A j B ) m o d N R \longleftarrow (R2^t A_j B)\mod N R⟵(R2tAjB)modN 3.13 endfor 3.14 B ⟵ R B \longleftarrow R B⟵R 3.15 endfor
基于安全错误的攻击 考虑针对算法3进行攻击攻击者攻击目的是要找到运算中隐藏着的密钥 d d d。 所谓安全错误是指在算法中导入1比特或几比特错误但这一错误可能并不会影响最终的模幂运算结果。 例如在 d i 1 d_i 1 di1时的第 i i i 次循环中向寄存器 A k A_k Ak 中导入错误且满足 k j k j kj那么由于正确的 A k A_k Ak 在先前的子循环中已经使用了所以算法三第3步的子循环不会计算出错即 R R R计算正确。而紧接着 A ⟵ R A \longleftarrow R A⟵R使得先前导入的错误被清除。于是算法三在以下的计算都不会受到影响。从而使得最终的计算结果是正确的。把这样导入的错误称之为安全错误。换言之安全错误发生了却并没有带来错误的计算结果。 但是导入的安全错误并不总是安全的。在一些情况下安全错误也会使得计算结果不正确。例如在 d i 0 d_i0 di0的第 i i i次循环中向 A k A_k Ak 中导入错误且满足 k j k j kj这时导入的错误就会使得最后的计算结果出错。因为当 d i 0 d_i0 di0时整个循环将跳过第3步从而使得导入的错误不能得到纠正并带入到下面的循环中。 通过上面分析得到以下结论。当 d i 1 d_i 1 di1时导入的安全错误不会影响计算结果的正确性当 d i 0 d_i0 di0时导入的安全错误会使得计算结果不正确。 基于以上的分析攻击者分别对 d d d的每一位 d i d_i di进行攻击。为了攻击第 i i i 比特在算法第 i i i次循环中导入安全错误。如果算法三输出正确结果那么由以上分析得 d i 1 d_i1 di1如果算法三输出错误结果或者算法三通过附加的检测出计算结果错误从而拒绝输出那么攻击者可知 d i 0 d_i0 di0。 这就是说即是智能卡检测出错误并拒绝输出攻击者仍可利用这一点得到 d i d_i di 的值。所以说对算法三实现模幂运算通过检验计算结果的方式不能防止基于安全错误的攻击。但通过加指数掩码每一次进行模幂运算时在指数 d d d上增加随机数可防止该攻击。
