近年来基于错误的密码分析（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_{i=0}^{n-1}d_i 2^i, d_i\in\{0,1\}
d=∑i=0n−1di2i,di∈{0,1}。从而在密码芯片中对应R-L比特算法实现。
在算法1中，当
d
i
=
1
d_i = 1
di=1 时，算法执行一次模乘运算(
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_i=0
di=0时，算法只需执行一次摸平方运算。
其中，RSA 用到模乘运算
R
=
A
⋅
B
m
o
d
N
R = A\cdot B \mod N
R=A⋅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_{j=0}^{m-1}A_j(2^t)^j A_j\in\{0,1,\cdots,2^t-1\},m=\lceil n/t \rceil
A=∑j=0m−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)2t+Am−2B)2t+⋯+A1B)2t+A0B)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
A=MdmodN
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_i=1
di=1) 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
R=A⋅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⟵(R2t+AjB)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
A=MdmodN
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_i=1
di=1) 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⟵(R2t+AjB)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⟵(R2t+AjB)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
di=1时的第
i
i
i 次循环中，向寄存器
A
k
A_k
Ak 中导入错误，且满足
k
>
j
k > j
k>j，那么，由于正确的
A
k
A_k
Ak 在先前的子循环中已经使用了，所以算法三第3步的子循环不会计算出错，即，
R
R
R计算正确。而紧接着
A
⟵
R
A \longleftarrow R
A⟵R使得先前导入的错误被清除。于是算法三在以下的计算都不会受到影响。从而使得最终的计算结果是正确的。把这样导入的错误称之为**安全错误**。换言之，安全错误发生了却并没有带来错误的计算结果。
但是，导入的安全错误并不总是安全的。在一些情况下安全错误也会使得计算结果不正确。例如，在
d
i
=
0
d_i=0
di=0的第
i
i
i次循环中，向
A
k
A_k
Ak 中导入错误，且满足
k
>
j
k > j
k>j，这时导入的错误就会使得最后的计算结果出错。因为，当
d
i
=
0
d_i=0
di=0时，整个循环将跳过第3步，从而使得导入的错误不能得到纠正，并带入到下面的循环中。
通过上面分析得到以下结论。当
d
i
=
1
d_i = 1
di=1时，导入的安全错误不会影响计算结果的正确性；当
d
i
=
0
d_i=0
di=0时，导入的安全错误会使得计算结果不正确。
基于以上的分析，攻击者分别对
d
d
d的每一位
d
i
d_i
di进行攻击。为了攻击第
i
i
i 比特，在算法第
i
i
i次循环中导入安全错误。如果算法三输出正确结果，那么由以上分析，得
d
i
=
1
d_i=1
di=1；如果算法三输出错误结果，或者算法三通过附加的检测出计算结果错误，从而拒绝输出，那么攻击者可知
d
i
=
0
d_i=0
di=0。
这就是说，即是智能卡检测出错误，并拒绝输出，攻击者仍可利用这一点得到
d
i
d_i
di 的值。所以说，对算法三实现模幂运算，通过检验计算结果的方式不能防止基于安全错误的攻击。但，通过加指数掩码，每一次进行模幂运算时，在指数
d
d
d上增加随机数，可防止该攻击。
版权归原作者 m0_74043383 所有， 如有侵权，请联系我们删除。