Academic literature on the topic 'Generalized feedback shift register'

Grain and Trivium are the hardware-oriented finalists of the eSTREAM. They are both based on nonlinear feedback shift registers. In this paper, we study their generalized classes of nonlinear feedback shift registers with time varying feedback functions, namely, Grain-like and Trivium-like structures. Some interesting results regarding their periods are obtained.

The proposed by Meier and Staffelbach Self-Shrinking Generator (SSG) which has efficient hardware implementation only with a single Linear Feedback Shift Register is suitable for low-cost and fast stream cipher applications. In this paper we generalize the idea of the SSG for arbitrary Galois Field . The proposed variant of the SSG is called the -ary Generalized Self-Shrinking Generator (pGSSG). We suggest a method for transformation of a non-binary self-shrunken pGSSG sequence into balanced binary sequence. We prove that the keystreams of the pGSSG have large period and good statistical properties. The analysis of the experimental results shows that the pGSSG sequences have good randomness properties. We examine the complexity of exhaustive search and entropy attacks of the pGSSG. We show that the pGSSG is more secure than SSG and Modified SSG against these attacks. We prove that the complexity of the used pGSSG attacks increases with increasing the prime . Previously mentioned properties give the reason to say that the pGSSG satisfy the basic security requirements for a stream chipper and can be useful as a part of modern stream ciphers.

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<br>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

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.

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.

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.<br>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ó.<br>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.

碩士<br>義守大學<br>資訊工程學系<br>90<br>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.