No description available.

Cryptosystems are used to provide security in communications and data transmissions. Stream ciphers are private key systems that are often used to transform large volumn data. In order to have security, key streams used in stream ciphers must be fully analyzed so that they do not contain specific patterns, statistical infomation and structures with which attackers are able to quickly recover the entire key streams and then break down the systems. Based on different schemes to generate sequences and different ways to represent them, there are a variety of stream cipher analyses. The most important one is the linear analysis based on linear feedback shift registers (LFSRs) which have been extensively studied since the 1960's. Every sequence over a finite field has a well defined linear complexity. If a sequence has small linear complexity, it can be efficiently recoverd by Berlekamp-Messay algorithm. Therefore, key streams must have large linear complexities. A lot of work have been done to generate and analyze sequences that have large linear complexities. In the early 1990's, Klapper and Goresky discovered feedback with carry shift registers over Z/(p) (p-FCSRS), p is prime. Based on p-FCSRs, they developed a stream cipher analysis that has similar properties to linear analysis. For instance, every sequence over Z/(p) has a well defined p-adic complexity and key streams of small p-adic complexity are not secure for use in stream ciphers. This disstation focuses on stream cipher analysis based on feedback with carry shift registers. The first objective is to develop a stream cipher analysis based on feedback with carry shift registers over Z/(N) (N-FCSRs), N is any integer greater than 1, not necessary prime. The core of the analysis is a new rational approximation algorithm that can be used to efficiently compute rational representations of eventually periodic N-adic sequences. This algorithm is different from that used in $p$-adic sequence analysis which was given by Klapper and Goresky. Their algorithm is a modification of De Weger's rational approximation algorithm. The second objective is to generalize feedback with carry shift register architecture to more general algebraic settings which are called algebraic feedback shift registers (AFSRs). By using algebraic operations and structures on certain rings, we are able to not only construct feedback with carry shift registers, but also develop rational approximation algorithms which create new analyses of stream ciphers. The cryptographic implication of the current work is that any sequences used in stream ciphers must have large N-adic complexities and large AFSR-based complexities as well as large linear complexities.

This thesis is concerned with the design and analysis of strong de Bruijn sequences and span n sequences, and nonlinear feedback shift register (NLFSR) based pseudorandom number generators for radio frequency identification (RFID) tags. We study the generation of span n sequences using structured searching in which an NLFSR with a class of feedback functions is employed to find span n sequences. Some properties of the recurrence relation for the structured search are discovered. We use five classes of functions in this structured search, and present the number of span n sequences for 6 <= n <= 20. The linear span of a new span n sequence lies between near-optimal and optimal. According to our empirical studies, a span n sequence can be found in the structured search with a better probability of success. Newly found span n sequences can be used in the composited construction and in designing lightweight pseudorandom number generators. We first refine the composited construction based on a span n sequence for generating long de Bruijn sequences. A de Bruijn sequence produced by the composited construction is referred to as a composited de Bruijn sequence. The linear complexity of a composited de Bruijn sequence is determined. We analyze the feedback function of the composited construction from an approximation point of view for producing strong de Bruijn sequences. The cycle structure of an approximated feedback function and the linear complexity of a sequence produced by an approximated feedback function are determined. A few examples of strong de Bruijn sequences with the implementation issues of the feedback functions of an (n+16)-stage NLFSR are presented. We propose a new lightweight pseudorandom number generator family, named Warbler family based on NLFSRs for smart devices. Warbler family is comprised of a combination of modified de Bruijn blocks (CMDB) and a nonlinear feedback Welch-Gong (WG) generator. We derive the randomness properties such as period and linear complexity of an output sequence produced by the Warbler family. Two instances, Warbler-I and Warbler-II, of the Warbler family are proposed for passive RFID tags. The CMDBs of both Warbler-I and Warbler-II contain span n sequences that are produced by the structured search. We analyze the security properties of Warbler-I and Warbler-II by considering the statistical tests and several cryptanalytic attacks. Hardware implementations of both instances in VHDL show that Warbler-I and Warbler-II require 46 slices and 58 slices, respectively. Warbler-I can be used to generate 16-bit random numbers in the tag identification protocol of the EPC Class 1 Generation 2 standard, and Warbler-II can be employed as a random number generator in the tag identification as well as an authentication protocol for RFID systems.

The class of generalized feedback shift register (GFSR) random number generators was a promising method for random number generation in the 1980's, but was abandoned because of some flaws such as poor performance on certain tests for randomness. The poor performance may be due to the choice of primitive polynomials used in the generators, rather than inherent flaws in the method. The original GFSR generators were all based on primitive trinomials. This project examines several alternative choices of primitive polynomials with more than one "interior" term to address this problem and hopefully provide access to good random number generators.

One of the two project reports: The other part is designated PART A: MCMASTER (Off-Campus) PROJECT / <P> A simple and inexpensive pseudo-random number generator has been designed and built using linear feedback shift registers to generate rectangular and gaussian distributed numbers. The device has been interfaced to a Nova computer to provide a high speed source of random numbers. The two distributions have been checked with the following tests: (i) Frequency test (ii) Autocorrelation test and (iii) d 2-test. Results of each test have been compared with the expected theoretical values. Finally, a comparison of the generating speed has been made between this new generator and the existing old software generators. This 28-bit generator is especially desirable in random simulation and Monte Carlo application if randomness, speed and cost are the main consideration in the design. </P> / Thesis / Master of Engineering (MEngr)

Mixed-signal processing systems especially data converters can be reliably tested at high frequencies using on-chip testing schemes based on memory. In this thesis, an on-chip testing strategy based on shift registers/memory (2 k bits) has been proposed for digital-to-analog converters (DACs) operating at 5 GHz. The proposed design uses word length of 8 bits in order to test DAC at high speed of 5 GHz. The proposed testing strategy has been designed in standard 65 nm CMOS technology with additional requirement of 1-V supply. This design has been implemented using Cadence IC design environment. The additional advantage of the proposed testing strategy is that it requires lower number of I/O pins and avoids the large number of high speed I/O pads. It therefore also solves the problem of the bandwidth limitation that is associated with I/O transmission paths. The design of the on-chip tester based on memory contains no analog block and is implemented entirely in digital domain. In the proposed design, low frequency of 1 MHz has been used outside the chip to load the data into the memory during the write mode. During the read mode, the frequency of 625 MHz is used to read the data from the memory. A multiplexing system is used to reuse the stored data during read mode to test the intended functionality and performance. In order to convert the parallel data into serial data at high frequency at the memory output, serializer has been used. By using the frequencies of 1.25 GHz and 2.5 GHz, the serializer speeds up the data from the lower frequency of 625 MHz to the highest frequency of 5 GHz in order to test DAC at 5 GHz.

Les travaux réalisés au cours de cette thèse se situent au carrefour de la cryptographie symétrique et du monde des environnements contraints. Le but de cette cryptographie, dite cryptographie à bas coût, est de fournir et d'évaluer des algorithmes symétriques pouvant être implémentés sur des systèmes très limités en ressources. Les contributions de cette thèse portent d'une part sur l'évaluation de la sécurité des registres à décalage à rétroaction avec retenue (FCSR) face à de nouvelles attaques et d'autre part sur une vision unifiée des différents schémas de Feistel généralisés (GFN) qui permet de mieux cerner leurs propriétés cryptographiques. Ces études ont donné lieu à deux nouveaux algorithmes à bas coût~; d'une part GLUON une fonction de hachage à base de FCSR et d'autre part le chiffrement LILLIPUT basé sur une famille étendant plus avant la notion de GFN. Enfin, une méthode générique permettant de réaliser des attaques différentielles en fautes sur des GFN est esquissée. / The work done during this Ph.D. lies at the crossroads of symmetric cryptography and constraints environments. The goal of such cryptography, called lightweight cryptography, is to propose and evaluate symmetric algorithms that can be implemented on very ressource limited devices. The contributions of this thesis are first on the security evaluations of feedback with carry shift registers (FCSR) to some new attacks and second on a unified vision of generalized Feistel networks (GFNs) that allows to better understand their cryptographic properties. These studies gave rise to two new lightweight algorithms: first GLUON a hash function based upon FCSRs and second the cipher LILLIPUT based on a family further extanding the notion of generalized Feistel network. Finally, a generic method for carrying out a differential fault attack on GFNs is outlined.

This dissertation investigates four methods for attacking stream ciphers that are based on nonlinear combining generators: -- Two exhaustive-search correlation attacks, based on the binary derivative and the Lempel-Ziv complexity measure. -- A fast-correlation attack utilizing the Viterbi algorithm -- A decimation attack, that can be combined with any of the above three attacks. These are ciphertext-only attacks that exploit the correlation that occurs between the ciphertext and an internal linear feedback shift-register (LFSR) of a stream cipher. This leads to a so-called divide and conquer attack that is able to reconstruct the secret initial states of all the internal LFSRs within the stream cipher. The binary derivative attack and the Lempel-Ziv attack apply an exhaustive search to find the secret key that is used to initialize the LFSRs. The binary derivative and the Lempel-Ziv complexity measures are used to discriminate between correct and incorrect solutions, in order to identify the secret key. Both attacks are ideal for implementation on parallel processors. Experimental results show that the Lempel-Ziv correlation attack gives successful results for correlation levels of p = 0.482, requiring approximately 62000 ciphertext bits. And the binary derivative attack is successful for correlation levels of p = 0.47, using approximately 24500 ciphertext bits. The fast-correlation attack, utilizing the Viterbi algorithm, applies principles from convolutional coding theory, to identify an embedded low-rate convolutional code in the pn-sequence that is generated by an internal LFSR. The embedded convolutional code can then be decoded with a low complexity Viterbi algorithm. The algorithm operates in two phases: In the first phase a set of suitable parity check equations is found, based on the feedback taps of the LFSR, which has to be done once only once for a targeted system. In the second phase these parity check equations are utilized in a Viterbi decoding algorithm to recover the transmitted pn-sequence, thereby obtaining the secret initial state of the LFSR. Simulation results for a 19-bit LFSR show that this attack can recover the secret key for correlation levels of p = 0.485, requiring an average of only 153,448 ciphertext bits. All three attacks investigated in this dissertation are capable of attacking LFSRs with a length of approximately 40 bits. However, these attacks can be extended to attack much longer LFSRs by making use of a decimation attack. The decimation attack is able to reduce (decimate) the size of a targeted LFSR, and can be combined with any of the three above correlation attacks, to attack LFSRs with a length much longer than 40 bits. / Dissertation (MEng (Electronic Engineering))--University of Pretoria, 2007. / Electrical, Electronic and Computer Engineering / unrestricted

Error-control codes provide a mechanism to increase the reliability of digital data being processed, transmitted, or stored under noisy conditions. Cyclic codes constitute an important class of error-control code, offering powerful error detection and correction capabilities. They can easily be generated and verified in hardware, which makes them particularly well suited to the practical use as error detecting codes.A cyclic code is based on a generator polynomial which determines its properties including the specific error detection strength. The optimal choice of polynomial depends on many factors that may be influenced by the underlying application. It is therefore advantageous to employ programmable cyclic code hardware that allows a flexible choice of polynomial to be applied to different requirements. A novel method is presented in this thesis to realise programmable cyclic code circuits that are fast, energy-efficient and minimise implementation resources.It can be shown that the correction of a single-bit error on the basis of a cyclic code is equivalent to the solution of an instance of the discrete logarithm problem. A new approach is proposed for computing discrete logarithms; this leads to a generic deterministic algorithm for analysed group orders that equal Mersenne numbers with an exponent of a power of two. The algorithm exhibits a worst-case runtime in the order of the square root of the group order and constant space requirements.This thesis establishes new relationships for finite fields that are represented as the polynomial ring over the binary field modulo a primitive polynomial. With a subset of these properties, a novel approach is developed for the solution of the discrete logarithm in the multiplicative groups of these fields. This leads to a deterministic algorithm for small group orders that has linear space and linearithmic time requirements in the degree of defining polynomial, enabling an efficient correction of single-bit errors based on the corresponding cyclic codes.

No description available.