Masked nonlinear feedback shift register
An NLFSR of length k, configured to output a sequence of masked values x′ i =x i +m i according to a masked recurrence x′ n+k =f(x′ n , . . . , x′ n+k−1 ), the NLFSR including a nonlinear feedback function configured to compute f(x′ n , . . . , x′ n+k−1 ) so as to obtain a feedback value, a correction function configured to compute (m n , . . . , n n+k−1 )+m n+k +h(m n , m n+k−1 , x n , . . . , x n+k−1 ) to obtain a correction value c, and a corrector configured to correct the feedback value {circumflex over (x)}′ n+k using the correction value c to obtain a corrected feedback value which forms x′ n+k .
1. A nonlinear feedback shift registers (NLFSR) of length k, configured to output a sequence of masked values x′ i =x i +m i , according to a masked recurrence x′ n+k =f(x′ n , . . . , x′ n+k−1 ), the NLFSR comprising:
a nonlinear feedback function comprising a feedback circuit of gates and configured to compute f(x′ n , . . . , x′ n+k− ) so as to obtain a feedback value;
a correction function comprising a correction circuit of gates and configured to compute f (m n , . . . , m n+k−1 )+m n−k +h(m n , . . . , m n+k−1 ,x n , . . . , x n+k−1 )to obtain a correction value c; and
a corrector connected to the correction function and configured to correct the feedback value using the correction value c to obtain a corrected feedback value which forms x′ n+k ,
wherein m i is a mask which is applied to x i ,
wherein the NLFSR comprises a shift register of a sequence of n registers configured to store the masked values x′ n+k−1 , . . . , x′ n .
2. The NLFSR according to claim 1 , wherein the nonlinear feedback function comprises a feedback circuit of Boolean logic gates wherein inputs of the feedback circuit are connected to outputs of at least a subset of the registers of the shift register and an output of the feedback circuit is coupled to an input of the shift register.
3. The NLFSR according to claim 2 , wherein the output of the feedback circuit is connected to the input of the shift register via the corrector.
4. The NLFSR according to claim 2 , wherein the feedback circuit's inputs are disconnected from any output of the first s≧1 registers of the shift register and the corrector is connected to any of an input or output of any of the first s registers of the shift register so as to perform the correction.
5. The NLFSR according to claim 4 , wherein the mask correction function comprises a combinatorial circuit wherein inputs of which are connected to outputs of at least a subset of the registers of the shift register and an output of the combinatorial circuit is coupled to an input of the shift register wherein the combinatorial circuit's inputs are disconnected from any output of the first s≧1 registers of the shift register.
6. The NLFSR according to claim 5 , wherein the combinatorial circuit results in a number of pipeline stages smaller than or equal to s.
7. The NLFSR according to claim 1 , wherein the correction function is configured such that
h
=
∑
p
=
1
p
∏
q
=
1
Q
(
p
)
∏
r
=
1
R
(
p
)
x
s
(
q
)
′
m
t
(
r
)
with
n
≤
s
(
q
)
≤
n
+
k
-
1
for
all
1
≤
q
≤
Q
(
p
)
and
all
1
≤
p
≤
P
n
≤
t
(
r
)
≤
n
+
k
-
1
for
all
1
≤
r
≤
R
(
p
)
and
all
1
≤
p
≤
P
.
8. The NLFSR according to claim 1 , wherein the mask correction function is implemented in a DPA secure manner such that any intermediate result is statistically uncorrelated to the unmasked values.
9. The NLFSR according to claim 1 , wherein the mask correction function comprises a combinatorial circuit comprising sequential circuit elements configured to suppress glitches.
10. An apparatus for pseudo-randomly generating a sequence of masked values, comprising:
a nonlinear feedback shift registers (NLFSR) of length k, configured to output a sequence of masked values x′ i =x i +m i according to a masked recurrence x′ n+k =f(x′ n , . . . , x′ n+k−1 ), the NLFSR comprising:
a nonlinear feedback function comprising a feedback circuit of gates and configured to compute f(x′ n , . . . , x′ n+k−1 ) so as to obtain a feedback value;
a correction function comprising a correction circuit of gates and configured to compute f(m n , . . . , m n+k−1 )+m n+k +h(m n , . . . , m n+k−1 x n , . . . , x n+k−1 ) to obtain a correction value c; and
a corrector connected to the correction function and configured to correct the feedback value using the correction value c to obtain a corrected feedback value which forms x′ n+k ,
wherein the NLFSR is further configured to provide the mask values,
wherein m i is a mask which is applied to x i ,
wherein the NLFSR comprises a shift register of a sequence of n registers configured to store the masked values x′ n+k−1 , . . . , x′ n .
11. The apparatus according to claim 10 , wherein the NLFSR comprises a true random number generator for providing the mask values.
12. The apparatus according to claim 10 , wherein the NLFSR comprises a feedback shift register for providing the mask values.
13. The apparatus according to claim 12 , wherein the NLFSR comprises a true random number generator and the feedback shift register is seeded and/or an internal state of the feedback shift register intermittently influenced by, the true random number generator.
14. The apparatus according to claim 13 , wherein a length of the feedback shift register is equal to k.
15. A cryptographic apparatus, comprising:
a nonlinear feedback shift registers (NLFSR) of length k, configured to output a sequence of masked values x′ i =x i +m i according to a masked recurrence x′ n+k =f(x′ n , . . . , x′ n+k−1 ) the NLFSR comprising:
a nonlinear feedback function comprising a feedback circuit of gates and configured to compute f(x′ n , . . . , x′ n+k−1 ) so as to obtain a feedback value;
a correction function comprising a correction circuit of gates and configured to compute f(m n, . . . , m n+k−1 )+m n+k +h(m n , . . . , m n+k−1 ,x n , . . . , x n+k−1 ) to obtain a correction value c;
a corrector connected to the correction function and configured to correct the feedback value using the correction value c to obtain a corrected feedback value which forms x′ n+k ; and
two circuit parts and a transmission bus,
wherein the transmission bus is configured to use the sequence of masked values to subject data to be transmitted between the circuit parts, to masking,
wherein m i is a mask which is applied to x i ,
wherein the NLFSR comprises a shift register of a sequence of n registers configured to store the masked values x′ n+k−1 , . . . , x′ n .
16. The cryptographic apparatus according to claim 15 , wherein the cryptographic apparatus is a chip card, a cryptographic chip or a cellular phone.
17. A method, comprising:
generating a sequence of masked values x′ i =x i +m i , using a nonlinear feedback shift registers (NLFSR) of length k, the NLFSR comprising a nonlinear feedback function configured to compute f(x n+k 1 ) so as to obtain a feedback value;
computing f(m n, . . . , m n+k−1 )+m n+k +h(m n , . . . , m n+k−1 ,x n , . . . , x n+k−1 )to obtain a correction value c; and
correcting the feedback value using the correction value c to obtain a corrected feedback value which forms x′ n+k ,
wherein m i is a mask which is applied to x i ,
wherein the NLFSR comprises a shift register of a sequence of n registers configured to store the masked values x′ n+k−1 , . . . , x′ n .
18. Non-transitory computer readable digital storage medium having stored thereon a computer program having a program code for performing, when running on a computer, a method according to claim 17 .