Tesis sobre el tema "Linear feedback shift registers"

Information Technology has revolutionized the way of our life, the raise of information technology has given birth to the information security. The design and implementation of information security techniques especially for wireless systems such as Mobiles, and RFIDs is receiving a lot of attentions. Stream ciphers are very good candidates for providing information security to wireless systems specially for RFIDs, because they are fast as compared to block ciphers, easy to implement, have small footprint, and consume less power. LFSRs can be use to implement the stream ciphers but they care exposed to different kind of cryptanalytic attacks on the other hand NLFSR based stream ciphers are resistant to cryptanalytic attacks to which pure LFSR based stream cipher are exposed. Just like LFSRs the NLFSRs can also be implemented in two types of configurations i.e. Fibonacci and Galois. The critical path of the Galois based NLFSRs is smaller than the Fibonacci NLFSRs this make Galois NLFSRs favorite for applications which need to run at a faster speed. Fibonacci NLFSRs can be converted to Galois NLFSRs but the conversion from Fibonacci to Galois is one-to-many relation i.e. for a single Fibonacci NLFSR we can have many equivalent Galois NLFSRs. The dilemma is that not all the equivalent Galois NLFSRs are optimal so in order for efficient implementation one has to search for the best possible Galois NLFSR. The complexity of search space is 0(nk), here represents the n − bit NLFSR and represents the number of products in the ANF of the feedback function of Fibonacci NLFSR, the NLFSR used in existing stream cipher usually havek less than or equal to 32( for hardware efficiency reasons) and n is of order of 128 (for cryptographic security reasons). The complexity of the search space shows that the normal brute force method will take considerable amount of time to produce the results. To address this problem a heuristic algorithm is proposed in [6] which uses the Primary Cost Function to estimate the critical path of the NLFSRs and produce the results, however the algorithm in [6] did not addressed a lot of issues for example it was unable to divide the products among the functions equally, it was unable to divide the product in such a way which would lead to optimization by synthesis tool. The Primary Cost Function proposed in [6] had flaws it was unable to find the difference between the function which can be optimized and which cannot be. This thesis proposes another heuristic algorithm which addresses the problem present in the [6]. The Primary Cost Function used in the [6] is also used in the proposed algorithm but with some modification and improvements. Besides using Primary Cost function, the proposed algorithm also uses other cost functions such Secondary Cost, XOR reduced Cost and Number of Literals Cost functions to find the best possible Galois NLFSR. The algorithm proposed in this thesis was tested on Vest, Achterbahn, Gain-128/80 ciphers and Cipher [8]. The Vest improved by 5.28% in delay and 17.39% in terms of area as compared to the results of [6], similarly Achterbahn, Gain, and Cipher [8] improved by 1.79%, 16.63%, 1.43% in delay and improvement in area were 2.09%, 1.001% , - 0.101% respectively.

In this thesis an optimized Built-In Self Test (BIST) scheme based on reseeding of multiple polynomial Linear Feedback Shift Registers (LFSRs) is proposed. The same LFSR that is used to generate pseudo-random patterns, is loaded with seeds from which it produces vectors that cover the testcubes which detect faults that are hard to test. The scheme is compatible with scan-design and achieves full coverage as it is based on random patterns combined with a deterministic test set.
Two methods for processing a test set to allow for efficient encoding of testcubes as LFSR seeds are proposed. The first method involves merging pairwise consistent testcubes in the test set. The second method involves concatenating the original testcubes to form longer testcubes. This allows multiple testcubes to be encoded into a single LFSR seed. Algorithms to perform merging and concatenation of the test set are presented. An algorithm for calculating LFSR seeds from the test set is described. A method to balance testcubes with respect to the feedback polynomials of the multiple polynomial LFSR is proposed. This allows the encoding of feedback polynomials to be done implicitly by the ordering of testcubes. An algorithm for the selection and ordering of feedback polynomials is presented.
Experimental results are provided for the ISCAS-85 and ISCAS-89 benchmark circuits to demonstrate the effectiveness of the scheme. The scheme allows an excellent trade-off between test data storage and test application time (number of test patterns) with a very small hardware overhead. We show the trade-off between test data storage and number of test patterns under the scheme.

Stream ciphers are encryption algorithms used for ensuring the privacy of digital telecommunications. They have been widely used for encrypting military communications, satellite communications, pay TV encryption and for voice encryption of both fixed lined and wireless networks. The current multi year European project eSTREAM, which aims to select stream ciphers suitable for widespread adoptation, reflects the importance of this area of research. Stream ciphers consist of a keystream generator and an output function. Keystream generators produce a sequence that appears to be random, which is combined with the plaintext message using the output function. Most commonly, the output function is binary addition modulo two. Cryptanalysis of these ciphers focuses largely on analysis of the keystream generators and of relationships between the generator and the keystream it produces. Linear feedback shift registers are widely used components in building keystream generators, as the sequences they produce are well understood. Many types of attack have been proposed for breaking various LFSR based stream ciphers. A recent attack type is known as an algebraic attack. Algebraic attacks transform the problem of recovering the key into a problem of solving multivariate system of equations, which eventually recover the internal state bits or the key bits. This type of attack has been shown to be effective on a number of regularly clocked LFSR based stream ciphers. In this thesis, algebraic attacks are extended to a number of well known stream ciphers where at least one LFSR in the system is irregularly clocked. Applying algebriac attacks to these ciphers has only been discussed previously in the open literature for LILI-128. In this thesis, algebraic attacks are first applied to keystream generators using stop-and go clocking. Four ciphers belonging to this group are investigated: the Beth-Piper stop-and-go generator, the alternating step generator, the Gollmann cascade generator and the eSTREAM candidate: the Pomaranch cipher. It is shown that algebraic attacks are very effective on the first three of these ciphers. Although no effective algebraic attack was found for Pomaranch, the algebraic analysis lead to some interesting findings including weaknesses that may be exploited in future attacks. Algebraic attacks are then applied to keystream generators using (p; q) clocking. Two well known examples of such ciphers, the step1/step2 generator and the self decimated generator are investigated. Algebraic attacks are shown to be very powerful attack in recovering the internal state of these generators. A more complex clocking mechanism than either stop-and-go or the (p; q) clocking keystream generators is known as mutual clock control. In mutual clock control generators, the LFSRs control the clocking of each other. Four well known stream ciphers belonging to this group are investigated with respect to algebraic attacks: the Bilateral-stop-and-go generator, A5/1 stream cipher, Alpha 1 stream cipher, and the more recent eSTREAM proposal, the MICKEY stream ciphers. Some theoretical results with regards to the complexity of algebraic attacks on these ciphers are presented. The algebraic analysis of these ciphers showed that generally, it is hard to generate the system of equations required for an algebraic attack on these ciphers. As the algebraic attack could not be applied directly on these ciphers, a different approach was used, namely guessing some bits of the internal state, in order to reduce the degree of the equations. Finally, an algebraic attack on Alpha 1 that requires only 128 bits of keystream to recover the 128 internal state bits is presented. An essential process associated with stream cipher proposals is key initialization. Many recently proposed stream ciphers use an algorithm to initialize the large internal state with a smaller key and possibly publicly known initialization vectors. The effect of key initialization on the performance of algebraic attacks is also investigated in this thesis. The relationships between the two have not been investigated before in the open literature. The investigation is conducted on Trivium and Grain-128, two eSTREAM ciphers. It is shown that the key initialization process has an effect on the success of algebraic attacks, unlike other conventional attacks. In particular, the key initialization process allows an attacker to firstly generate a small number of equations of low degree and then perform an algebraic attack using multiple keystreams. The effect of the number of iterations performed during key initialization is investigated. It is shown that both the number of iterations and the maximum number of initialization vectors to be used with one key should be carefully chosen. Some experimental results on Trivium and Grain-128 are then presented. Finally, the security with respect to algebraic attacks of the well known LILI family of stream ciphers, including the unbroken LILI-II, is investigated. These are irregularly clock- controlled nonlinear filtered generators. While the structure is defined for the LILI family, a particular paramater choice defines a specific instance. Two well known such instances are LILI-128 and LILI-II. The security of these and other instances is investigated to identify which instances are vulnerable to algebraic attacks. The feasibility of recovering the key bits using algebraic attacks is then investigated for both LILI- 128 and LILI-II. Algebraic attacks which recover the internal state with less effort than exhaustive key search are possible for LILI-128 but not for LILI-II. Given the internal state at some point in time, the feasibility of recovering the key bits is also investigated, showing that the parameters used in the key initialization process, if poorly chosen, can lead to a key recovery using algebraic attacks.

Recently, covering arrays have been the subject of considerable research attention as they hold both theoretical interest and practical importance due to their applications to testing. In this thesis, we perform the first comprehensive study of a generalization of covering arrays called variable strength covering arrays, where we dictate the interactions to be covered in the array by modeling them as facets of an abstract simplicial complex. We outline the necessary background in the theory of hypergraphs, combinatorial testing, and design theory that is relevant to the study of variable strength covering arrays. We then approach questions that arise in variable strength covering arrays in a number of ways. We demonstrate their connections to hypergraph homomorphisms, and explore the properties of a particular family of abstract simplicial complexes, the qualitative independence hypergraphs. These hypergraphs are tightly linked to variable strength covering arrays, and we determine and identify several of their important properties and subhypergraphs. We give a detailed study of constructions for variable strength covering arrays, and provide several operations and divide-and-conquer techniques that can be used in building them. In addition, we give a construction using linear feedback shift registers from primitive polynomials of degree 3 over arbitrary finite fields to find variable strength covering arrays, which we extend to strength-3 covering arrays whose sizes are smaller than many of the best known sizes of covering arrays. We then give an algorithm for creating variable strength covering arrays over arbitrary abstract simplicial complexes, which builds the arrays one row at a time, using a density concept to guarantee that the size of the resultant array is asymptotic in the logarithm of the number of facets in the abstact simplicial complex. This algorithm is of immediate practical importance, as it can be used to create test suites for combinatorial testing. Finally, we use the Lovasz Local Lemma to nonconstructively determine upper bounds on the sizes of arrays for a number of different families of hypergraphs. We lay out a framework that can be used for many hypergraphs, and then discuss possible strategies that can be taken in asymmetric problems.

Streamciphers are common cryptographic algorithms used to protect the confidentiality of frame-based communications like mobile phone conversations and Internet traffic. Streamciphers are ideal cryptographic algorithms to encrypt these types of traffic as they have the potential to encrypt them quickly and securely, and have low error propagation. The main objective of this thesis is to determine whether structural features of keystream generators affect the security provided by stream ciphers.These structural features pertain to the state-update and output functions used in keystream generators. Using linear sequences as keystream to encrypt messages is known to be insecure. Modern keystream generators use nonlinear sequences as keystream.The nonlinearity can be introduced through a keystream generator's state-update function, output function, or both. The first contribution of this thesis relates to nonlinear sequences produced by the well-known Trivium stream cipher. Trivium is one of the stream ciphers selected in a final portfolio resulting from a multi-year project in Europe called the ecrypt project. Trivium's structural simplicity makes it a popular cipher to cryptanalyse, but to date, there are no attacks in the public literature which are faster than exhaustive keysearch. Algebraic analyses are performed on the Trivium stream cipher, which uses a nonlinear state-update and linear output function to produce keystream. Two algebraic investigations are performed: an examination of the sliding property in the initialisation process and algebraic analyses of Trivium-like streamciphers using a combination of the algebraic techniques previously applied separately by Berbain et al. and Raddum. For certain iterations of Trivium's state-update function, we examine the sets of slid pairs, looking particularly to form chains of slid pairs. No chains exist for a small number of iterations.This has implications for the period of keystreams produced by Trivium. Secondly, using our combination of the methods of Berbain et al. and Raddum, we analysed Trivium-like ciphers and improved on previous on previous analysis with regards to forming systems of equations on these ciphers. Using these new systems of equations, we were able to successfully recover the initial state of Bivium-A.The attack complexity for Bivium-B and Trivium were, however, worse than exhaustive keysearch. We also show that the selection of stages which are used as input to the output function and the size of registers which are used in the construction of the system of equations affect the success of the attack. The second contribution of this thesis is the examination of state convergence. State convergence is an undesirable characteristic in keystream generators for stream ciphers, as it implies that the effective session key size of the stream cipher is smaller than the designers intended. We identify methods which can be used to detect state convergence. As a case study, theMixer streamcipher, which uses nonlinear state-update and output functions to produce keystream, is analysed. Mixer is found to suffer from state convergence as the state-update function used in its initialisation process is not one-to-one. A discussion of several other streamciphers which are known to suffer from state convergence is given. From our analysis of these stream ciphers, three mechanisms which can cause state convergence are identified.The effect state convergence can have on stream cipher cryptanalysis is examined. We show that state convergence can have a positive effect if the goal of the attacker is to recover the initial state of the keystream generator. The third contribution of this thesis is the examination of the distributions of bit patterns in the sequences produced by nonlinear filter generators (NLFGs) and linearly filtered nonlinear feedback shift registers. We show that the selection of stages used as input to a keystream generator's output function can affect the distribution of bit patterns in sequences produced by these keystreamgenerators, and that the effect differs for nonlinear filter generators and linearly filtered nonlinear feedback shift registers. In the case of NLFGs, the keystream sequences produced when the output functions take inputs from consecutive register stages are less uniform than sequences produced by NLFGs whose output functions take inputs from unevenly spaced register stages. The opposite is true for keystream sequences produced by linearly filtered nonlinear feedback shift registers.

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.

International Telemetering Conference Proceedings / October 25-28, 1999 / Riviera Hotel and Convention Center, Las Vegas, Nevada
Because of the limits of feedback devices, high-speed pseudo-noise code generators cannot depend simply on the improvement of clock rate. Based on the characteristic equation of linear feedback registers and the m-sequence sampling theory as well, deduction is made to indicate a novel way to improve the speed of pseudo-noise code generators 2^l (2^l < n, n is the length of registers) times as fast as the conventional one. Also, we extend our applications to non-reducible and non-primitive polynomials. It could be a good way to generate these linear codes at higher rates.

Introducción El acelerado ritmo al que se genera y crece la información en la sociedad actual y la posible llegada de la tecnología de transistor a sus límites de tamaño exige la puesta en marcha de soluciones para el procesado eficiente de datos en campos específicos de aplicación. Contenido Esta tesis doctoral de carácter transdisciplinar a medio camino entre la ingeniería electrónica y la química computacional presenta soluciones optimizadas en hardware y en software para la construcción y el procesado eficiente de bases de datos moleculares. En primer lugar se propone y se estudia el funcionamiento de bloques digitales que implementan funciones en lógica pulsante estocástica orientadas a tareas de reconocimiento de objetos. Especialmente se proponen y analizan diseños digitales para la construcción de generadores de números aleatorios (RNG) como base de estos sistemas que han sido implementados en dispositivos Field Programable Gate Array (FPGA). En segundo lugar se propone y se evalúa un conjunto reducido de descriptores moleculares para la caracterización de compuestos orgánicos y la generación de bases de datos moleculares. Estos descriptores recogen información sobre la distribución de la carga molecular en el espacio y la energía electrostática. Las bases de datos generadas con estos descriptores se han procesado utilizando sistemas de computación convencionales en software y mediante sistemas de computación estocástica implementados en hardware mediante el uso de circuitería digital programable. Finalmente se proponen optimizaciones para la estimación del potencial electrostático molecular (MEP) y para el cálculo de los puntos de interacción molecular derivados (SSIP). Conclusiones Por una parte, los resultados obtenidos ponen de manifiesto la importancia de la uniformidad de los RNG en el período de evaluación para poder implementar sistemas de computación estocástica de alta fiabilidad. Además, los RNG propuestos tienen una naturaleza aperiódica que minimiza las posibles correlaciones entre señales, haciendo que sean adecuados para la implementación de sistemas de computación estocástica. Por otra parte, el conjunto de descriptores moleculares propuestos PED han demostrado obtener muy buenos resultados en comparación con otros métodos presentes en la literatura. Este hecho se ha discutido mediante los parámetros Area Under The Curve (AUC) y Enrichment Factor (EF) obtenidos de las curvas promedio Receiving Operating Characteristic (ROC). Además, se ha mostrado como la eficacia de los descriptores aumenta cuando se implementan en sistemas de clasificación con aprendizaje supervisado, haciéndolos adecuados para la construcción de un sistema de predicción de dianas terapéuticas eficiente. En esta tesis, además, se ha determinado que los MEP calculados utilizando la teoría DFT y el conjunto de bases B3LYP/6-31*G en la superficie con densidad electrónica 0,01 au correlacionan bien con datos experimentales debido presumiblemente a la mayor contribución de las propiedades electrostáticas locales reflejadas en el MEP. Las parametrizaciones propuestas en función del tipo de hibridación atómica pueden haber contribuido también a esta mejora. Los cálculos realizados en dichas superficies suponen mejoras en un factor cinco en la velocidad de procesamiento del MEP. Dado el aceptable ajuste a datos experimentales del método propuesto para el cálculo del MEP aproximado y de los SSIP, éste se puede utilizar con el fin de obtener los SSIP para bases de datos moleculares extensas o en macromoléculas como proteínas de manera muy rápida (ya que la velocidad de procesamiento obtenida puede alcanzar del orden de cinco mil átomos procesados por segundo utilizando un solo procesador). Estas técnicas resultan de especial interés dadas las numerosas aplicaciones de los SSIP como por ejemplo el cribado virtual de cocristales o la predicción de energías libres en disolución.
Introducció El creixement accelerat de les dades en la societat actual i l'arribada de la tecnologia del transistor als límits físics exigeix la proposta de metodologies per al processament eficient de dades. Contingut Aquesta tesi doctoral, de caràcter transdisciplinària i a mig camí entre els camps de l'enginyeria electrònica i la química computacional presenta solucions optimitzades en maquinari i en programari per tal d’accelerar el processament de bases de dades moleculars. En primer lloc es proposa i s'estudia el funcionament de blocs digitals que implementen funcions de lògica polsant estocàstica aplicades a tasques de reconeixement d'objectes. En concret es proposen i analitzen dissenys específics per a la construcció de generadors de nombres aleatoris (RNG) com a sistemes bàsics per al funcionament dels sistemes de computació estocàstics implementats en dispositius programables com les Field Programable Gate Array (FPGA). En segon lloc es proposen i avaluen un conjunt reduït de descriptors moleculars especialment orientats a la caracterització de compostos orgànics. Aquests descriptors reuneixen la informació sobre la distribució de càrrega molecular i les energies electroestàtiques. Les bases de dades generades amb aquests descriptors s’han processat emprant sistemes de computació convencionals en programari i mitjançant sistemes basats en computació estocàstica implementats en maquinari programable. Finalment es proposen optimitzacions per al càlcul del potencial electroestàtic molecular (MEP) calculat mitjançant la teoria del funcional de la densitat (DFT) i dels punts d’interacció que se’n deriven (SSIP). Conclusions Per una banda, els resultats obtinguts posen de manifest la importància de la uniformitat del RNG en el període d’avaluació per a poder implementar sistemes de computació estocàstics d’alta fiabilitat. A més, els RNG proposats presenten una font d’aleatorietat aperiòdica que minimitza les correlacions entre senyals, fent-los adequats per a la implementació de sistemes de computació estocàstica. Per una altra banda, el conjunt de descriptors moleculars proposats PED, han demostrat obtenir molts bons resultats en comparació amb els mètodes presents a la literatura. Aquest fet ha estat discutit mitjançant l’anàlisi dels paràmetres Area Under The Curve (AUC) i Enrichment Factor (EF) de les curves Receiving Operating Characteristic (ROC) analitzades. A més, s’ha mostrat com l’eficàcia dels descriptors augmenta de manera significativa quan s’implementen en sistemes de classificació amb aprenentatge supervisat com les finestres de Parzen, fent-los adequats per a la construcció d’un sistema de predicció de dianes terapèutiques eficient. En aquesta tesi doctoral, a més, s’ha trobat que els MEP calculats mitjançant la teoria DFT i el conjunt de bases B3LYP/6-31*G en la superfície amb densitat electrònica 0,01 au correlacionen bé amb dades experimentals possiblement a causa de la contribució més gran de les propietats electroestàtiques locals reflectides en el MEP. Les parametritzacions proposades en funció del tipus d’hibridació atòmica han contribuït també a la millora dels resultats. Els càlculs realitzats en aquestes superfícies suposen un guany en un factor cinc en la velocitat de processament del MEP. Donat l’acceptable ajust a les dades experimentals del mètode proposat per al càlcul del MEP aproximat i dels SSIP que se’n deriven, aquest procediment es pot emprar per obtenir els SSIP en bases de dades moleculars extenses i en macromolècules (com ara proteïnes) d’una manera molt ràpida (ja que la velocitat de processament obtinguda arriba fins als cinc mil àtoms per segon amb un sol processador). Les tècniques proposades en aquesta tesi doctoral resulten d’interès donades les nombroses aplicacions que tenen els SSIP com per exemple, en el cribratge virtual de cocristalls o en la predicció d’energies lliures en dissolució.
Introduction Because of the generalized data growth in the nowadays digital era and due to the fact that we are possibly living on the last days of the Moore’s law, there exists a good reason for being focused on the development of technical solutions for efficient data processing. Contents In this transdisciplinary thesis between electronic engineering and computational chemistry, it's shown optimal solutions in hardware and software for molecular database processing. On the first hand, there's proposed and studied a set of stochastic computing systems in order to implement ultrafast pattern recognition applications. Specially, it’s proposed and analyzed specific digital designs in order to create digital Random Number Generators (RNG) as a base for stochastic functions. The digital platform used to generate the results is a Field Programmable Gate Array (FPGA). On the second hand, there's proposed and evaluated a set of molecular descriptors in order to create a compact molecular database. The proposed descriptors gather charge and molecular geometry information and they have been used as a database both in software conventional computing and in hardware stochastic computing. Finally, there's a proposed a set of optimizations for Molecular Electrostatic Potential (MEP) and Surface Site Interaction Points (SSIP). Conclusions Firstly, the results show the relevance of the uniformity of the RNG within the evaluation period in order to implement high precision stochastic computing systems. In addition, the proposed RNG have an aperiodic behavior which avoid some potential correlations between stochastic signals. This property makes the proposed RNG suitable for implementation of stochastic computing systems. Secondly, the proposed molecular descriptors PED have demonstrated to provide good results in comparison with other methods that are present in the literature. This has been discussed by the use of Area Under the Curve (AUC) and Enrichment Factor (EF) of averaged Receiving Operating Characteristic (ROC) curves. Furthermore, the performance of the proposed descriptors gets increased when they are implemented in supervised machine learning algorithms making them appropriate for therapeutic target predictions. Thirdly, the efficient molecular database characterization and the usage of stochastic computing circuitry can be used together in order to implement ultrafast information processing systems. On the other hand, in this thesis, it has been found that the MEP calculated by using DFT and B3LYP/6-31*G basis at 0.01 au density surface level has good correlation with experimental data. This fact may be due to the important contribution of local electrostatics and the refinement performed by the parameterization of the MEP as a function of the orbital atom type. Additionally, the proposed calculation over 0.01 au is five times faster than the calculation over 0.002 au. Finally, due to acceptable agreement between experimental data and theoretical results obtained by using the proposed calculation for MEP and SSIP, the proposed method is suitable for being applied in order to quickly process big molecular databases and macromolecules (the processing speed can achieve five thousand molecules per second using a single processor). The proposed techniques have special interest with the purpose of finding the SSIP because the big number of applications they have as for instance in virtual cocrystal screening and calculation of free energies in solution.

This diploma’s thesis discourses the cryptographic systems and ciphers, whose function, usage and practical implementation are analysed. In the first chapter basic cryptographic terms, symmetric and asymetric cryptographic algorithms and are mentioned. Also usage and reliability are analysed. Following chapters mention substitution, transposition, block and stream ciphers, which are elementary for most cryptographic algorithms. There are also mentioned the modes, which the ciphers work in. In the fourth chapter are described the principles of some chosen cryptographic algorithms. The objective is to make clear the essence of the algorithms’ behavior. When describing some more difficult algorithms the block scheme is added. At the end of each algorithm’s description the example of practical usage is written. The chapter no. five discusses the hardware implementation. Hardware and software implementation is compared from the practical point of view. Several design instruments are described and different hardware design programming languages with their progress, advantages and disadvantages are mentioned. Chapter six discourses the hardware implementation design of chosen ciphers. Concretely the design of stream cipher with pseudo-random sequence generator is designed in VHDL and also in Matlab. As the second design was chosen the block cipher GOST, which was designed in VHDL too. Both designs were tested and verified and then the results were summarized.

碩士
國立交通大學
資訊工程系
87
The theory of the stream cipher has developed quickly these years. The most important part of the architecture of the stream cipher is the Running Key Generator(RKG). For security reasons, the key stream generated by the RKG should satisfy a few demands such as long period, high linear complexity, good randomness, etc. The primary objective of this thesis is to study the RKG which is based on the Linear Feedback Shift Register(LFSR). We adopt a conventional method to construct the maximal-length LFSR which can generate the sequence with very long period. But these sequences do not have high linear complexity. To overcome the drawback, we give another model which is based on the LFSR with nonlinear feedforward logic. By this model, we can promote the linear complexity of the output sequences easily. Moreover, we also introduce some methods to test the randomness of any sequence.

碩士
東海大學
數學系
95
The main purpose of this thesis is to research the tests of the reduced functional faults of the consuming electronic product: NAND flash memory. The linear congruential method and linear feedback shift registers (LFSR) are used to product random numbers that locate the page address for testing the reduced functional faults of the NAND flash memory. The purpose of this study is to develop a software testing environment to drive a low cost hardware device in identifying the page with reduced functional faults for NAND flash memory. The test result shows that LFSR has better performance than the others.

碩士
中原大學
資訊工程研究所
102
With the progress of IC manufacturing, the number of transistors on the chip is increased. Thereby, the IC designer will spend more time to verify the correctness of chip. There are two main ways for IC testing. The first one is external testing such as Automatic Test Equipments (ATE). It can auto generate the test pattern and have better fault coverage. However, the ATE is very expensive. The second method is Build-In-Self-Test (BIST). Different from ATE, the BIST can accomplish the testing without spending too much hardware overhead. Linear Feedback Shift Registers (LFSR) is widely adopted as the pseudo-random test pattern generator for BIST, due to its low hardware overhead. However, there are many faults are hardly detected by the traditional LFSR. To achieve the better fault coverage and testing cycle, we want to propose a new test pattern generation LFSR architecture by using bidirectional shifter register. By analyzing target test vectors, we can systematically design a test pattern generator which has better fault coverage and shortest generation sequence. Because each shifting only cost one bit change, we can also reduce the power consumption. Our benchmark is provided by CAD96 [12]. By comparing the difference between one-way and two-way test pattern generator, we can observe that the generation sequence length of two-way test pattern generator is shorter than one way. Although the two-way test pattern generator expenses more gates to design the circuit, we can come to better testing time.

碩士
國立高雄第一科技大學
電腦與通訊工程所
92
In wireless system, and time of technology, the system is required faster speed rate of transmission. Orthogonal frequency division multiplexing is a kind of multi-carrier modulation system. It is good for high data rate in orthogonal frequency channel, and it is effective to reduce multi-path fading on wireless channel. However, there is a main drawback in OFDM system, where the signal is higher PAPR. The amplifier needs larger linear range in order to avoid producing non-linear distortion which leads to increase bit error rate and spread outside band, but it will enlarge linear range of operation, and waste the efficiency of amplifier. Therefore, in this thesis, we want to solve the PAPR problem in OFDM system. First we discuss the method of signal clipping to reduce high PAPR value, and then it causes a serious distortion in output signals. In order to avoid serious distortion for PAPR problem, we use random sequence to produce new sequence to change the original sequence. Then we choose sequence of the smallest PAPR value to transmit, and also construct encoder and insert labels to provide recognition. Therefore, we can know which sequence was transmitted in the receiver. Finally, we can not only reduce the PAPR value, but also reduce bit error rate. All outcomes will be introduced in this thesis.

碩士
義守大學
資訊工程學系
90
In recent years, cyclic redundancy code (CRC) has been applied widely in storage devices and data communication because of its simple coding structure and keeping the integrity of transmitted data. In traditional way, data in serial performs the CRC computation one bit at a time. It must waste much time according to an increasing number of data. In this paper, we use a simple linear feedback shift register (LFSR) circuit for parallel CRC computation based on the theory of Galois Field and we are absorbed in developing our parallel approach based on lookahead technique for the other LFSR applications.

碩士
國立清華大學
資訊系統與應用研究所
104
Steganography and cryptography are techniques that try to protect message from being captured during data transmission. Algorithms which combined steganography and cryptography can provide a higher security. In this thesis, we propose a least significant bit (LSB) based steganography. In order to enhance the security, we use linear feedback shift register (LFSR) to generate random sequences to do exclusive-or (XOR) operations with the secret message and then embed the ciphered message into biometric images. In the capacity aspect, our algorithm can support up to four least significant bits (4LSB) replacement according to the size of message. The effectiveness of the proposed method is estimated by peak signal-to-noise ratio (PSNR), embedding rate and execution time. The results show that high PSNR values with short execution time is feasible.

Thesis (M.S.)--University of Wisconsin--Madison, 1990.
Typescript. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 74-76).

碩士
國立臺灣科技大學
資訊管理系
107
With the rapid growth of Industry 4.0, the manufacturing industries apply cyber-physical systems (CPS) to their industrial control system (ICS) to improve the efficiency of operations, product quality and reduce costs. By the information technology and operational technology of CPS to achieve real-time monitoring, interoperability, and virtualization. However, unless the convenience and benefits of CPS, the characteristics of CPS lead to the isolation between the industrial control system and the external network or system be getting lower and lower, so the vulnerabilities and attacks are rising rapidly. Therefore, we propose a symmetric encryption scheme based on a linear feedback shift register to encrypt each data by dynamically generating the symmetric key to protect the internal data transmission of the industrial control system. Through the simulation result, the proposed encryption scheme could encrypt 2MB per second approximately so it is capable to execute on device and equipment of industrial control systems. Furthermore, we do the security analysis against the proposed encryption scheme, it could prevent hacker eavesdropping and man-in-the-middle attacks.

碩士
高苑科技大學
電子工程研究所
102
In recent years, due to explosive development of Internet technology, a great deal of multimedia (images, sounds, videos, etc.) data message is delivering on internet. But in the process how we ensure the security of such information, it has become a problem of concern to the people. At present, image encryption technologies are gaining more and more attentions for researchers. Since the digital images can be transmitted through the Internet, it indirectly generate images safety issues. Image encryption is a way that can ensure the safety of image. However, the traditional encryption methods cannot satisfy image due to big quantity. According to the characteristic of image, researchers produce a variety of image encryption methods. A novel iterative image encryption scheme using the image dyadic displacement, the linear feedback shift registers and discrete wavelet transform in the cascading way is proposed to defeat the disadvantages of the conventional image encryption. Multi-keys are used in the proposed scheme to promote the security level of the image encryption. Furthermore, the results of the simulations show that the decrypted image is a picture filled with noises and hardly to be identified if any key used in the decryption process is wrong.

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