System and method for providing defence to a cryptographic device against side-channel attacks targeting the extended euclidean algorithm during decryption operations
View Patent ↗A system, method and computer-readable storage medium for decrypting a code c using a modified Extended Euclidean Algorithm (EEA) having an iteration loop independent of the Hamming weight of inputs to the EEA and performing a fixed number of operations regardless of the inputs to the EEA thereby protecting a cryptographic device performing the decryption from side-channel attacks.
1. A method for protecting a cryptography device against side-channel attack while performing decryption according to a specified encryption scheme thereby rendering the cryptography device less vulnerable to attacks designed to cause the cryptography device to reveal information an attacker may use to discern cryptographic material stored on the cryptography device, the method comprising:
receiving by the processor a code c, wherein c is a function of a key pair (having a public key and a secret key) and an error e;
decrypting by the processor the code c by deriving the error e by:
computing a polynomial syndrome S(z) which is a univariate polynomial deduced from c, but depending only on e,
using a modified Extended Euclidean Algorithm having inputs a(z), b(z), and d, where a(z) and b(z) are polynomials and d is a public parameter of the encryption scheme to compute an error locator polynomial σ(z), by:
iteratively performing a computation L a number of times defined by the parameter d, the computation L performing a fixed number of arithmetic operations regardless of Hamming weight of inputs a(z) and b(z), the arithmetic operations performing polynomial subtraction operations resulting in a result related to the result of a standard Extended Euclidean Algorithm,
finding by the processor roots of σ(z); and
inferring by the processor the error e from the roots of σ(z).
2. The method for protecting a cryptography device performing decryption using an Extended Euclidean Algorithm against side-channel attack of claim 1 wherein the modified Extended Euclidean Algorithm produces a result related to the Extended Euclidean Algorithm formulated as follows:
Extended Euclidean Algorithm (EEA):
Input: a(z), b(z), deg(a) ≥ deg(b), d fin
Output: u(z), r(z) with b(z)u(z) = r(z) mod a(z) and deg(r) ≤ d fin
1: r −1 (z) ← a(z), r 0 (z) ← b(z),u −1 (z) ← 1, u 0 (z) ← 0,
2: i ← 0
3: while deg(r i (z)) > d fin do
4: i ← i + 1
5: q i ← r i−2 (z)/r i−1 (z)
6: r i ← r i−2 (z) − q i (z)r i−1 (z)
7: u i ← u i−2 (z) − q i (z)u i−1 (z)
8: end while
9: N ← i
10: return u N (z), r N (z)
wherein d fin =1/2 d, i.e., d fin equals to ½ the public parameter d of the encryption scheme,
and the computation L is related to the while loop in the Extended Euclidean Algorithm such that polynomials u n (z) and r n (z) may be derived from the outputs of the modified Extended Euclidean Algorithm.
3. The method for protecting a cryptography device performing decryption using an Extended Euclidean Algorithm against side-channel attack of claim 2 wherein the operation L has the form:
1: {circumflex over (R)} −1 (z) ← a(z), {circumflex over (R)} 0 (z) ← zb(z),
2: Û −1 (z) ← 1, Û 0 (z) ← 0,
3
:
δ
←
-
1.
4
:
for
j
=
1
,
…
,
d
do
5
:
α
j
←
R
^
j
-
1
,
d
,
β
j
←
R
^
j
-
2
,
d
.
6
:
temp
R
(
z
)
←
z
(
α
j
R
^
j
-
2
(
z
)
-
β
j
R
^
j
-
1
(
z
)
)
.
7
:
temp
U
(
z
)
←
z
(
α
j
U
^
j
-
2
(
z
)
-
β
j
U
^
j
-
1
(
z
)
)
.
8
:
if
α
j
=
0
(
ie
deg
(
R
^
j
-
1
)
<
deg
(
R
^
j
-
2
)
)
then
9
:
δ
←
δ
+
1.
10
:
else
11
:
δ
←
δ
-
1.
12
:
end
if
13
:
if
δ
<
0
then
14
:
(
R
^
j
(
z
)
,
R
^
j
-
1
(
z
)
)
←
(
R
^
j
-
1
(
z
)
,
temp
R
)
15
:
(
U
^
j
(
z
)
,
U
^
j
-
1
(
z
)
)
←
(
U
^
j
-
1
(
z
)
,
temp
U
)
16
:
δ
←
0.
17
:
else
18
:
(
R
^
j
(
z
)
,
R
^
j
-
1
(
z
)
)
←
(
temp
R
,
R
^
j
-
2
(
z
)
)
19
:
(
U
^
j
(
z
)
,
U
^
j
-
1
(
z
)
)
←
(
temp
U
,
U
^
j
-
2
(
z
)
)
20
:
δ
←
δ
.
21
:
end
if
22
:
end
for
}
L
23: return Û d (z), {circumflex over (R)} d (z).
4. The method for protecting a cryptography device performing decryption using an Extended Euclidean Algorithm against side-channel attack of claim 3 wherein r N (z), and u N (z), are related to {circumflex over (R)} d (z) and Û d (z) as follows:
{circumflex over (R)} d ( z )=μ z d−w(e)+1 r N ( z )
Û d ( z )=μ z d−w(e)+1 u N ( z ).
5. The method for protecting a cryptography device performing decryption using an Extended Euclidean Algorithm against side-channel attack of claim 1 wherein the EEA is used in an Alternant decoder and the EEA is used to compute the error locator polynomial a(z), wherein the polynomial a(z) is z 2t and the polynomial b(z) is S(z), and d is 2t.s.
6. The method for protecting a cryptography device performing decryption using an Extended Euclidean Algorithm against side-channel attack of claim 1 wherein the EEA is used in a Patterson algorithm decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial a(z) is g(z) and the polynomial b(z) is τ, d=t, τ=√{square root over (S(z) −1 +1)} mod g(z), and g(z) is a generator function from which the public key is generated.
7. A cryptographic device protected against side-channel attacks while performing decryption according to a specified encryption scheme thereby rendering the cryptography device less vulnerable to attacks designed to cause the cryptography device to reveal information an attacker may use to discern cryptographic material stored on the cryptography device, comprising:
a processor;
a memory connected to the processor and comprising instructions executable by the processor, the instructions including instructions to cause the processor to:
receiving by the processor a code c, wherein c is a function of a key pair (having a public key and a secret key) and an error e;
decrypting by the processor the code c by deriving the error e by:
computing a polynomial syndrome S(z) which is a univariate polynomial deduced from c, but depending only on e,
using a modified Extended Euclidean Algorithm having inputs a(z), b(z), and d, where a(z) and b(z) are polynomials and d is a public parameter of the encryption scheme to compute an error locator polynomial α(z), by:
iteratively performing a computation L a number of times defined by the termination criteria d, the computation L performing a fixed number of arithmetic operations regardless of Hamming weight of inputs a(z) and b(z), the arithmetic operations performing polynomial subtraction operations resulting in a result related to the result of a standard Extended Euclidean Algorithm,
finding by the processor roots of σ(z); and
inferring by the processor the error e from the roots of σ(z).
8. The cryptographic device protected against side-channel attacks of claim 7 wherein the modified Extended Euclidean Algorithm produces a result related to the Extended Euclidean Algorithm formulated as follows:
Extended Euclidean Algorithm (EEA):
Input: a(z), b(z), deg(a) ≥ deg(b), d fin
Output: u(z), r(z) with b(z)u(z) = r(z) mod a(z) and deg(r) ≤ d fin
1: r −1 (z) ← a(z), r 0 (z) ← b(z),u −1 (z) ← 1, u 0 (z) ← 0,
2: i ← 0
3: while deg(r i (z)) > d fin do
4: i ← i + 1
5: q i ← r i−2 (z)/r i−1 (z)
6: r i ← r i−2 (z) − q i (z)r i−1 (z)
7: u i ← u i−2 (z) − q i (z)u i−1 (z)
8: end while
9: N ← i
10: return u N (z), r N (z)
and the computation L is related to the while loop in the Extended Euclidean Algorithm such that polynomials u n (z) and r n (z) may be derived from the outputs of the modified Extended Euclidean Algorithm.
9. The cryptographic device protected against side-channel attacks of claim 8 wherein the operation L has the form:
1: {circumflex over (R)} −1 (z) ← a(z), {circumflex over (R)} 0 (z) ← zb(z),
2: Û −1 (z) ← 1, Û 0 (z) ← 0,
3
:
δ
←
-
1.
4
:
for
j
=
1
,
…
,
d
do
5
:
α
j
←
R
^
j
-
1
,
d
,
β
j
←
R
^
j
-
2
,
d
.
6
:
temp
R
(
z
)
←
z
(
α
j
R
^
j
-
2
(
z
)
-
β
j
R
^
j
-
1
(
z
)
)
.
7
:
temp
U
(
z
)
←
z
(
α
j
U
^
j
-
2
(
z
)
-
β
j
U
^
j
-
1
(
z
)
)
.
8
:
if
α
j
=
0
(
ie
deg
(
R
^
j
-
1
)
<
deg
(
R
^
j
-
2
)
)
then
9
:
δ
←
δ
+
1.
10
:
else
11
:
δ
←
δ
-
1.
12
:
end
if
13
:
if
δ
<
0
then
14
:
(
R
^
j
(
z
)
,
R
^
j
-
1
(
z
)
)
←
(
R
^
j
-
1
(
z
)
,
temp
R
)
15
:
(
U
^
j
(
z
)
,
U
^
j
-
1
(
z
)
)
←
(
U
^
j
-
1
(
z
)
,
temp
U
)
16
:
δ
←
0.
17
:
else
18
:
(
R
^
j
(
z
)
,
R
^
j
-
1
(
z
)
)
←
(
temp
R
,
R
^
j
-
2
(
z
)
)
19
:
(
U
^
j
(
z
)
,
U
^
j
-
1
(
z
)
)
←
(
temp
U
,
U
^
j
-
2
(
z
)
)
20
:
δ
←
δ
.
21
:
end
if
22
:
end
for
}
L
23: return Û d (z), {circumflex over (R)} d (z).
10. The cryptographic device protected against side-channel attacks of claim 8 wherein r n (z), and u n (z), are related to {circumflex over (R)} d (z) and Û d (z) as follows:
{circumflex over (R)} d ( z )=μ z d−w(e)+1 r N ( z )
Û d ( z )=μ z d−w(e)+1 u N ( z ).
11. The cryptographic device protected against side-channel attacks of claim 7 wherein the EEA is used in an Alternant decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial a(z) is z 2t , the polynomial b(z) is S(z), and d is 2t.
12. The cryptographic device protected against side-channel attacks of claim 7 wherein the EEA is used in a Patterson algorithm decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial a(z) is g(z) and the polynomial b(z) is τ, d is t,
τ=√{square root over (S(z) −1 +1)} mod g(z), and g(z) is a generator function from which the public key is generated.
13. The cryptographic device protected against side-channel attacks of claim 7 wherein the cryptographic device is a smart card.
14. The cryptographic device protected against side-channel attacks of claim 7 wherein the cryptographic device is a mobile device.
15. A non-transitory computer readable storage medium storing instructions protecting a cryptography device against side-channel attack while performing decryption according to a specified encryption scheme thereby rendering the cryptography device less vulnerable to attacks designed to cause the cryptography device to reveal information an attacker may use to discern cryptographic material stored on the cryptography device, the instructions operable to cause a processor of a cryptographic device, when loaded onto and executed by the processor of the cryptographic device, to:
receive a code c, wherein c is a function of a key pair (having a public key and a secret key) and an error e;
decrypt the code c by deriving the error e by:
computing a polynomial syndrome S(z) which is a univariate polynomial deduced from c, but depending only on e,
using a modified Extended Euclidean Algorithm having inputs a(z), b(z), and d, where a(z) and b(z) are polynomials and d is a public parameter of the encryption scheme to compute an error locator polynomial α(z), by:
iteratively performing a computation L a number of times defined by the termination criteria d, the computation L performing a fixed number of arithmetic operations regardless of Hamming weight of inputs a(z) and b(z), the arithmetic operations performing polynomial subtraction operations resulting in a result related to the result of a standard Extended Euclidean Algorithm,
finding by the processor roots of σ(z); and
inferring by the processor the error e from the roots of σ(z).
16. The computer readable storage medium of claim 15 wherein the modified Extended Euclidean Algorithm produces a result related to the Extended Euclidean Algorithm formulated as follows:
Extended Euclidean Algorithm (EEA):
Input: a(z), b(z), deg(a) ≥ deg(b), d fin
Output: u(z), r(z) with b(z)u(z) = r(z) mod a(z) and deg(r) ≤ d fin
1: r −1 (z) ← a(z), r 0 (z) ← b(z),u −1 (z) ← 1, u 0 (z) ← 0,
2: i ← 0
3: while deg(r i (z)) > d fin do
4: i ← i + 1
5: q i ← r i−2 (z)/r i−1 (z)
6: r i ← r i−2 (z) − q i (z)r i−1 (z)
7: u i ← u i−2 (z) − q i (z)u i−1 (z)
8: end while
9: N ← i
10: return u N (z), r N (z)
and the computation L is equivalent to the while loop in the Extended Euclidean Algorithm such that polynomials u n (z) and r n (z) may be derived from the outputs of the modified Extended Euclidean Algorithm.
17. The computer readable storage medium of claim 16 wherein the operation L has the form:
1: {circumflex over (R)} −1 (z) ← a(z), {circumflex over (R)} 0 (z) ← zb(z),
2: Û −1 (z) ← 1, Û 0 (z) ← 0,
3
:
δ
←
-
1.
4
:
for
j
=
1
,
…
,
d
do
5
:
α
j
←
R
^
j
-
1
,
d
,
β
j
←
R
^
j
-
2
,
d
.
6
:
temp
R
(
z
)
←
z
(
α
j
R
^
j
-
2
(
z
)
-
β
j
R
^
j
-
1
(
z
)
)
.
7
:
temp
U
(
z
)
←
z
(
α
j
U
^
j
-
2
(
z
)
-
β
j
U
^
j
-
1
(
z
)
)
.
8
:
if
α
j
=
0
(
ie
deg
(
R
^
j
-
1
)
<
deg
(
R
^
j
-
2
)
)
then
9
:
δ
←
δ
+
1.
10
:
else
11
:
δ
←
δ
-
1.
12
:
end
if
13
:
if
δ
<
0
then
14
:
(
R
^
j
(
z
)
,
R
^
j
-
1
(
z
)
)
←
(
R
^
j
-
1
(
z
)
,
temp
R
)
15
:
(
U
^
j
(
z
)
,
U
^
j
-
1
(
z
)
)
←
(
U
^
j
-
1
(
z
)
,
temp
U
)
16
:
δ
←
0.
17
:
else
18
:
(
R
^
j
(
z
)
,
R
^
j
-
1
(
z
)
)
←
(
temp
R
,
R
^
j
-
2
(
z
)
)
19
:
(
U
^
j
(
z
)
,
U
^
j
-
1
(
z
)
)
←
(
temp
U
,
U
^
j
-
2
(
z
)
)
20
:
δ
←
δ
.
21
:
end
if
22
:
end
for
}
L
23: return Û d (z), {circumflex over (R)} d (z).
18. The computer readable storage medium of claim 16 wherein r n (z), and u n (z), are related to {circumflex over (R)} d (z) and Û d (z) as follows:
{circumflex over (R)} d ( z )=μ z d−w(e)+1 r N ( z )
Û d ( z )=μ z d−w(e)+1 u N ( z ).
19. The computer readable storage medium of claim 15 wherein the EEA is used in an Alternant decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial a(z) is z 2t , the polynomial b(z) is S(z), and d=2t.
20. The computer readable storage medium of claim 15 wherein the EEA is used in a Patterson algorithm decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial a(z) is g(z) and the polynomial b(z) is τ; d is t and wherein τ=√{square root over (S(z) −1 +1)} mod g(z) and g(z) is a generator function from which the public key is generated.