The Open Mathematics Journal




(Discontinued)

ISSN: 1874-1177 ― Volume 8, 2015

Cryptography and Shift Registers


The Open Mathematics Journal , 2009, 2: 16-21

A.A. Bruen, R.A. Mollin

Department of Electrical and Computer Engineering, University of Calgary, Canada.

Electronic publication date 17/3/2009
[DOI: 10.2174/1874117400902010016]




Abstract:

Shift registers are at the heart of cryptography and error-correction. In cryptography they are the main tool for generating long pseudorandom binary sequences which can be used as keys for two communicating parties in symmetric cryptography. Practically all military cryptography makes use of them. Shift registers are also fundamental in signal analysis and frequency hopping, most recently in connection with European GPS codes.

The subject has a chequered history. One of the pioneers was a famous Hollywood star who, in her day, was known as the worlds most beautiful woman and wrote one of the earliest patents on frequency hopping which was developed by the US military. We speak of the Austrian-born Hedwig Maria Eva Kiesler, otherwise known as Hedy Lamarr. The development of spread spectrum technology was first proposed by Lamarr using frequency hopping. She obtained a patent after coming to Hollywood in 1942 and turned it over to the US government as a contribution to the war effort. Shortly after the patent expired in 1959 Sylvania digitize the synchronization to supply secure communication during the Cuban missile crisis.

This paper presents a user-friendly, self-contained and comprehensive discussion of the theory of shift registers. Moreover, we provide several examples (and counterexamples) in support of the theory. In the non-linear case we study the relationship between truth tables and de Bruijn sequences. In the linear case, we use a matrix-theoretic approach to describe the situations when the output is periodic and when it is not periodic. Section three describes additional periodicity properties, using the Cayley-Hamilton theorem and the theory of error-correcting codes.

In Section six, we prove a fundamental result to the effect that, for non-singular shift registers of length k, the entire output is uniquely determined by any 2k consecutive bits of the output sequence. Although the result is part of the folk lore, it is certainly not well understood and there appears to be a lack of any rigorous proof in the literature. An additional bonus of our proof here is that it can be adapted to provide a new algorithm for demonstrating a little-known, and remarkable fact. Namely, we provide the most general method for constructing two quite different shift registers of the same length that produce identical output sequences! A new result concerning such shift registers is also sketched in Section six.


Download PDF
Track Your Manuscript:


Endorsements



"Open access will revolutionize 21st century knowledge work and accelerate the diffusion of ideas and evidence that support just in time learning and the evolution of thinking in a number of disciplines."


Daniel Pesut
(Indiana University School of Nursing, USA)

"It is important that students and researchers from all over the world can have easy access to relevant, high-standard and timely scientific information. This is exactly what Open Access Journals provide and this is the reason why I support this endeavor."


Jacques Descotes
(Centre Antipoison-Centre de Pharmacovigilance, France)

"Publishing research articles is the key for future scientific progress. Open Access publishing is therefore of utmost importance for wider dissemination of information, and will help serving the best interest of the scientific community."


Patrice Talaga
(UCB S.A., Belgium)

"Open access journals are a novel concept in the medical literature. They offer accessible information to a wide variety of individuals, including physicians, medical students, clinical investigators, and the general public. They are an outstanding source of medical and scientific information."


Jeffrey M. Weinberg
(St. Luke's-Roosevelt Hospital Center, USA)

"Open access journals are extremely useful for graduate students, investigators and all other interested persons to read important scientific articles and subscribe scientific journals. Indeed, the research articles span a wide range of area and of high quality. This is specially a must for researchers belonging to institutions with limited library facility and funding to subscribe scientific journals."


Debomoy K. Lahiri
(Indiana University School of Medicine, USA)

"Open access journals represent a major break-through in publishing. They provide easy access to the latest research on a wide variety of issues. Relevant and timely articles are made available in a fraction of the time taken by more conventional publishers. Articles are of uniformly high quality and written by the world's leading authorities."


Robert Looney
(Naval Postgraduate School, USA)

"Open access journals have transformed the way scientific data is published and disseminated: particularly, whilst ensuring a high quality standard and transparency in the editorial process, they have increased the access to the scientific literature by those researchers that have limited library support or that are working on small budgets."


Richard Reithinger
(Westat, USA)

"Not only do open access journals greatly improve the access to high quality information for scientists in the developing world, it also provides extra exposure for our papers."


J. Ferwerda
(University of Oxford, UK)

"Open Access 'Chemistry' Journals allow the dissemination of knowledge at your finger tips without paying for the scientific content."


Sean L. Kitson
(Almac Sciences, Northern Ireland)

"In principle, all scientific journals should have open access, as should be science itself. Open access journals are very helpful for students, researchers and the general public including people from institutions which do not have library or cannot afford to subscribe scientific journals. The articles are high standard and cover a wide area."


Hubert Wolterbeek
(Delft University of Technology, The Netherlands)

"The widest possible diffusion of information is critical for the advancement of science. In this perspective, open access journals are instrumental in fostering researches and achievements."


Alessandro Laviano
(Sapienza - University of Rome, Italy)

"Open access journals are very useful for all scientists as they can have quick information in the different fields of science."


Philippe Hernigou
(Paris University, France)

"There are many scientists who can not afford the rather expensive subscriptions to scientific journals. Open access journals offer a good alternative for free access to good quality scientific information."


Fidel Toldrá
(Instituto de Agroquimica y Tecnologia de Alimentos, Spain)

"Open access journals have become a fundamental tool for students, researchers, patients and the general public. Many people from institutions which do not have library or cannot afford to subscribe scientific journals benefit of them on a daily basis. The articles are among the best and cover most scientific areas."


M. Bendandi
(University Clinic of Navarre, Spain)

"These journals provide researchers with a platform for rapid, open access scientific communication. The articles are of high quality and broad scope."


Peter Chiba
(University of Vienna, Austria)

"Open access journals are probably one of the most important contributions to promote and diffuse science worldwide."


Jaime Sampaio
(University of Trás-os-Montes e Alto Douro, Portugal)

"Open access journals make up a new and rather revolutionary way to scientific publication. This option opens several quite interesting possibilities to disseminate openly and freely new knowledge and even to facilitate interpersonal communication among scientists."


Eduardo A. Castro
(INIFTA, Argentina)

"Open access journals are freely available online throughout the world, for you to read, download, copy, distribute, and use. The articles published in the open access journals are high quality and cover a wide range of fields."


Kenji Hashimoto
(Chiba University, Japan)

"Open Access journals offer an innovative and efficient way of publication for academics and professionals in a wide range of disciplines. The papers published are of high quality after rigorous peer review and they are Indexed in: major international databases. I read Open Access journals to keep abreast of the recent development in my field of study."


Daniel Shek
(Chinese University of Hong Kong, Hong Kong)

"It is a modern trend for publishers to establish open access journals. Researchers, faculty members, and students will be greatly benefited by the new journals of Bentham Science Publishers Ltd. in this category."


Jih Ru Hwu
(National Central University, Taiwan)

Browse Contents



Webmaster Contact: info@benthamopen.net
Copyright © 2023 Bentham Open