Information Technology Reference
In-Depth Information
Equation 7) and 5
size
(
c
) is the cost of a ripple carry adder which adds the
content of
size
(
c
) bits of the carry with the output of
h
.
×
5Con lu on
We have presented in this paper how to transform an FCSR into a sub-sequences
generator to increase its throughput or to reduce its power consumption. Our
results emphasize the similarity between LFSRs and FCSRs in terms of imple-
mentation properties. In both cases, the solution based on the classical synthesis
algorithm fails to provide a minimal solution. Even worse, in the case of FC-
SRs the memory needed is in practice exponentially bigger than for the original
FCSR. Thus, we need to use multiple steps implementations as for LFSRs. The
propagation of carries is the main problem in multiple steps implementations
of FCSRs: if we consider
d
sub-sequences, we obtain
d
-bit ripple carry adders
with carry instead of additions with carry in a Galois setup. In the case of a Fi-
bonacci setup, the situation is different since we can split the feedback function
into two parts. This new representation can significantly improve the hardware
implementation of FCSRs but it may also be possible to improve software im-
plementations.
References
1. Massey, J.L.: Shift-register synthesis and BCH decoding. IEEE Transactions on
Information Theory 15, 122-127 (1969)
2. Feng, G.L., Tzeng, K.: A Generalization of the Berlekamp-Massey Algorithm
for Multisequence Shift-Register Synthesis with Applications to Decoding Cyclic
Codes. IEEE Transactions on Information Theory 37(5), 1274-1287 (1991)
3. Schmidt, G., Sidorenko, V.: Linear Shift-Register Synthesis for Multiple Sequences
of Varying Length. In: IEEE International Symposium on Information Theory -
ISIT 2006, pp. 1738-1742. IEEE, Los Alamitos (2006)
4. Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with
memory. Journal of Cryptology 10, 111-147 (1997)
5. Arnault, F., Berger, T.P., Necer, A.: Feedback with Carry Shift Registers synthesis
with the Euclidean Algorithm. IEEE Transactions on Information Theory 50(5)
(2004)
6. Klapper, A., Goresky, M.: 2-adic shift registers. In: Anderson, R. (ed.) FSE 1993.
LNCS, vol. 809, pp. 174-178. Springer, Heidelberg (1994)
7. Goresky, M., Klapper, A.: Fibonacci and Galois representations of feedback-with-
carry shift registers. IEEE Transactions on Information Theory 48(11) (2002)
8. Goresky, M., Klapper, A.: Algebraic Shift Register Sequences (preprint)
9. Courtois, N., Meier, W.: Algebraic Attacks on Stream Ciphers with Linear Feed-
back. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345-359.
Springer, Heidelberg (2003)
10. Arnault, F., Berger, T.P., Minier, M.: On the security of FCSR-based pseudoran-
dom generators. In: State of the Art of Stream Ciphers - SASC (2007),
