Šiame darbe yra tiriami dešimt skirtingų pseudoatsitiktinių generatorių ir jų statistinės savybės. Pseudoatsitiktiniai skaičiai yra naudojami daugelyje sričių, todėl yra labai svarbu, kad jie pasižymėtų kokybišku atsitiktinumu. Atliekant kiekvieną testą yra tikrinama hipotezė, ar sekos nariai yra iš tikrųjų atsitiktiniai. Viso darbe yra naudojami 15 šiame darbe išanalizuotų testų. Yra rekomenduojama, kad testavimo metu kievienoje sekoje būtų bent 1,000,000 bitų. Kad gauti reikšmingus rezultatus, kiekvienam generatoriui ištirti yra naudojami 50,000,000 bitų suskirstyti į dešimt sekų. Seka išlaiko testą, tada, kai testavimo metu gauta p-reikšmė yra 0.01 arba didesnė, kitu atveju – testas neišlaikytas. Jeigu bent aštuonios iš dešimties sekų išlaikė testus, tai yra laikoma, kad generatoriaus generuojama seka šio testo atžvilgiu yra atsitiktinė. Tyrimo metu buvo pastebėta, kad penki iš dešimties generatorių pastoviai išlaiko visus testus. Šiame darbe generatoriai yra suskirstyti pagal kokybiškumą atsižvelgiant į testų rezultatus. Pasiūlytas originalus pseudoatsitiktinis generatorius visada išlaiko 14 iš 15 testų ir yra laikoma, kad jo generuojama skaičių seka yra atsitiktinė, tačiau už jį yra pranašesnių generatorių. / Ten different pseudorandom number generator‘s statistical features were analyzed in this work. Pseudorandom numbers are applied in many fields, that‘s why it‘s important for them to have high quality of randomness. Hypothesis that random numbers are indeed random are checked by 15 different tests that are analyzed in this work. It is recommended that at least 1,000,000 bits of data would be used during the test. To archive meaningful results 50,000,000 of random bits divided into ten sequences are used for each pseudorandom number generator. For generator to pass any of the tests it is required that 8 out of 10 sequence’s p-value would be higher or equal to 0.01. During investigation it was noticed, that only five out of ten generators constantly pass all of the tests. In this work we classify each of the generators and separate those of higher and lower quality and determine which one is the best or the worst. Proposed unique pseudorandom number generator is constantly passing 14 out of 15 tests and is considered to have a high quality of randomness, but, according to results it is not the best of in this work’s analyzed generators.

Orthogonal frequency division multiplexing (OFDM) due to the robustness to the effect of multipath fading and having high spectral efficiency, it has become a good candidate of wireless communications systems. The block transmission of signal-blocks through the channel will suffer from the inter-block interference (IBI) and inter-symbol interference (ISI). Usually in the transmitter of the OFDM systems, redundancy (or guard interval), such cyclic prefix (CP) or zero padding (ZP), with sufficient length, is inserted in the transmitted block to avoid the IBI. In this thesis, we propose a novel pseudo random cyclic postfix (PRCP-) OFDM system configuration, which adopts the PRCP as redundancy and combines with multiple antennas. In fact, the multiple transmit antenna and multiple receive antenna, which exploits the spatial diversity, can be used to further enhance the channel capacity and achieve high data-rate. The main property of PRCP-OFDM modulation is that it exploits the cyclic-postfix sequences to estimate channel information with a low complexity method. Compared with CP-OFDM, it overcomes the channel null problem. For ZP-OFDM, it uses the additional information to estimate channel which is replaced by zero samples in ZP-OFDM. Moreover, PRCP-OFDM avoids the interference of signals to the desired postfix when we estimate channel impulse response (CIR) and which is different from pseudo random postfix (PRP-) OFDM [8]. Thus, as SNR grows, PRCP-OFDM can have better performance than PRP-OFDM. With the help of [9], [12] and [13], we extend the PRCP-OFDM to the MIMO case with space-time block coding. Via computer simulation, we verify that the performance is improved, in terms of the accuracy of channel estimation and symbol error rate (SER).

The Orthogonal frequency division multiplexing (OFDM) modulator with redundancy has been adopted in many wireless communication systems for higher data rate transmissions .The block transmission of signal-blocks through the channel will suffer from the inter-block interference (IBI) and inter-symbol interference (ISI). In the traditional transmitter of the OFDM systems, redundancy (or guard interval), such cyclic prefix (CP) or zero padding (ZP), with sufficient length, is inserted in the transmitted block to avoid the IBI. In this thesis, we propose a novel pseudo random cyclic postfix (PRCP-) OFDM system configuration and joint a blind channel shortening algorithm which named MERRY algorithm [18], which adopts the PRCP as redundancy and combines with multiple antennas. In fact, the multiple input and multiple output (MIMO) system, which exploits the spatial diversity, it can be used to further enhance the channel capacity and achieve high data-rate, and we extend the PRCP-OFDM to the MIMO case with space-time block coding. In redundancy insufficient case, the blind channel shortening algorithm be adopted for suppressing the IBI. The main property of PRCP-OFDM modulation is that it exploits the cyclic-postfix sequences to estimate channel information with a low complexity method. For CP-OFDM, it overcomes the channel null problem. Compared with ZP-OFDM, it uses the additional information to estimate channel which is replaced by zero samples in ZP-OFDM. Moreover, PRCP-OFDM avoids the interference of signals to the desired postfix when we estimate channel impulse response (CIR) and which is different from pseudo random postfix (PRP-) OFDM [8]. Thus, when SNR grows, PRCP-OFDM can have better performance than PRP-OFDM. With the help of [9], [12] and [13]. Via computer simulation, we verify that the performance is improved.

The constant demand for capacity increase, together with the foreseen saturation of the single-mode optical fiber, paved the way to technological breakthroughs that have completely changed the landscape of fiber-optic telecommunications. The most important advance was, undeniably, the practical implementation of a coherent detection with the help of high-speed electronics. This has, first, enabled the use of advanced modulation formats that allowed for a more efficient use of the fiber bandwidth, compared to the classical On-Off Keying, while adapted algorithms could not be used in order to mitigate the optical signal degradation. This thesis began a little after the advent of coherent detection and its main objective was to revisit the propagation effects in optical transmission systems using "Quadrature phase shift keying" (QPSK) modulation in the context of terrestrial systems, i.e. for transmission distances of up to about 2000 km. The manuscript is divided into two parts. The first part is dedicated to a study on the data sequences that need to be used in numerical simulations, when advanced modulation is involved. Fiber propagation, and in particular the interplay between chromatic dispersion and nonlinearities, usually introduce a nonlinear inter-symbol interference (ISI) to the transmitted signal. Since this ISI depends on the actual transmitted data pattern, it is obvious that the choice of the sequence used in our numerical simulations will have a direct influence on the estimated channel quality. Since, an infinite length, random sequence is impractical; we very commonly use pseudorandom" (PR) sequences, i.e. finite-length, deterministic sequences with balanced pattern statistics that seem to be random. In the first part we describe the method of generating M-level (with M>2) pseudorandom sequences and we detail their properties. In addition, we propose numerical tools to characterize the non-pseudorandom sequences that we use in numerical simulations, or we are sometimes forced to use in laboratory experiments. Finally, we present results of numerical simulations that quantify the necessity to use PR sequences as a function of our system parameters. After having established the "fairest possible" finite sequences, in the second part of the manuscript, we focus on the study of the nonlinear propagation, in the context of a transmission system using QPSK modulation and assuming a variable dispersion management and fiber type. Specifically, we numerically study the signal statistics due to the interplay of chromatic dispersion and nonlinear effects, neglecting all polarization or multi-wavelength effects and the amplifier noise. In this context, we were first interested in determining whether some empirical laws developed for OOK systems, can be also used in the case of QPSK modulation, such as the criterion of cumulative nonlinear phase (ΦNL) or laws that allow for a quick optimization of the dispersion management. Next we reveal the importance of a global phase rotation added to the initial signal constellation, as a parameter that can provide interesting information for the post-optimization of our system. We also discuss the fact that the constellation shape critically depends on the applied dispersion management, while there are generally 3 types of constellations, concerning the complex signal statistics: (1) the phase variance is higher than the amplitude variance (2) the amplitude variance is higher than the phase variance and (3) the received signal constellation resembles to a constellation of a signal under the influence of just an Additive White Gaussian Noise. Finally, we provide a phenomenological explanation of the constellations shapes revealing the fact that different data sub-sequences suffer from a different kind of signal degradation, while we also use this information to define a parameter that quantifies the potential benefit from a MAP (Maximum A Posteriori probability) correction algorithm

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.

Kerberos is a widely-deployed network authentication protocol that is being considered for standardization. Like other standard protocols, Kerberos is no exception to security flaws and weaknesses, as has been demonstrated in several prior works. Provable security guarantees go a long way in restoring users' faith, thus making a protocol an even stronger candidate for standards. In this thesis, our goal was thus to provide provable security support for Kerberos and other practical protocols. Our contributions are three-fold: We first look at the symmetric encryption schemes employed in the current version 5 of Kerberos. Several recent results have analyzed a significant part of Kerberos v.5 using formal-methods-based approaches, which are meaningful only if the underlying encryption schemes satisfy strong cryptographic notions of privacy and authenticity. However, to our knowledge these schemes were never analyzed and proven to satisfy such notions. This thesis aims to bridge this gap. Our provable security analyses confirm that some of the encryption scheme options in Kerberos v.5 already provide privacy and authenticity, and for the remaining we suggest slight modifications for the same. We next turn our attention to the ways in which the keys and other random strings needed in cryptographic schemes employed by practical protocols are generated. Randomness needs to be carefully generated for the provable security guarantees to hold. We propose an efficient pseudorandom generator (PRG) based on hash functions. The security of our PRG relies on exponential collision-resistance and regularity of the underlying hash function. Our PRG can be used to generate various strings, like session keys, sequence numbers, confounders, etc., which are all suggested to be generated randomly in the Kerberos v.5 specification, but no algorithms are mentioned. Each of the above strings are required to satisfy different properties, all of which are trivially satisfied by the pseudorandom strings output by a PRG. Finally, we look at the problem of revocation associated with two relatively new types of encryption schemes: identity-based encryption (IBE) and attribute-based encryption (ABE). While these encryption schemes are relatively less efficient compared to public-key encryption schemes, they have already been used (and are very likely to be used in future, as well) in many practical protocols due to their attractive features. Any setting, public-key, identity-based, or attribute-based, must provide a means to revoke users from the system. However, unlike public-key encryption, there has been little prior work on studying the revocation mechanisms in an IBE or ABE. We propose new primitives and their efficient and provably secure instantiations, focusing on the revocation problem. We would like to note that even though all the results presented in this thesis are motivated mainly by provable security in practice, only the first bullet above has a direct impact on a practical and widely deployed protocol Kerberos. Our PRG is the most efficient construction among theoretical PRGs, but it may still not be efficient enough to be directly usable in practical protocols. And our results and techniques for revocation in IBE and ABE have found much wider applications in information security, such as mobile social networks, cloud-based secure health records, data outsourcing systems, vehicular ad-hoc networks, etc.

abstract: Parallel Monte Carlo applications require the pseudorandom numbers used on each processor to be independent in a probabilistic sense. The TestU01 software package is the standard testing suite for detecting stream dependence and other properties that make certain pseudorandom generators ineffective in parallel (as well as serial) settings. TestU01 employs two basic schemes for testing parallel generated streams. The first applies serial tests to the individual streams and then tests the resulting P-values for uniformity. The second turns all the parallel generated streams into one long vector and then applies serial tests to the resulting concatenated stream. Various forms of stream dependence can be missed by each approach because neither one fully addresses the multivariate nature of the accumulated data when generators are run in parallel. This dissertation identifies these potential faults in the parallel testing methodologies of TestU01 and investigates two different methods to better detect inter-stream dependencies: correlation motivated multivariate tests and vector time series based tests. These methods have been implemented in an extension to TestU01 built in C++ and the unique aspects of this extension are discussed. A variety of different generation scenarios are then examined using the TestU01 suite in concert with the extension. This enhanced software package is found to better detect certain forms of inter-stream dependencies than the original TestU01 suites of tests. / Dissertation/Thesis / Ph.D. Statistics 2013

Pseudorandom sequences have many applications in fields such as wireless communication, cryptography and built-in self test of integrated circuits. Maximal length sequences (m-sequences) are commonly employed pseudorandom sequences because they have ideal randomness properties like balance, run and autocorrelation. However, the linear complexity of m-sequences is poor. This thesis considers the use of one-dimensional Cellular Automata (CA) to generate pseudorandom sequences that have high linear complexity and good randomness. The properties of these sequences are compared with those of the corresponding m-sequences to determine their suitability. / Graduate

Dans cette thèse, nous nous intéressons à la sécurité de générateurs pseudo-aléatoires et d'implémentations de schémas de signature. Concernant les schémas de signature, nous proposons, dans le cas d'une implémentation répandue de RSA, différentes attaques par injection de faute effectives quelque soit l'encodage du message. Nous présentons par ailleurs une contre-mesure infective prouvée sûre pour protéger le schéma RSA--PSS contre un certain nombre de fautes non aléatoires. Nous étudions également le schéma ECDSA couplé aux techniques d'accélération GLV/GLS. En fonction des implémentations, nous prouvons soit la bonne distribution du nonce utilisé, soit qu'il présente un biais permettant une attaque. Enfin, nous élaborons un outil qui recherche automatiquement des attaques par faute à partir d'une implémentation et d'une politique de faute, outil appliqué avec succès sur des implémentations de RSA et de ECDSA. Concernant les générateurs pseudo-aléatoires algébriques, nous étudions les générateurs non-linéaires et améliorons certaines attaques en diminuant l'information donnée à l'adversaire. Nous nous intéressons également à la sécurité du générateur Micali-Schnorr à travers quelques attaques et une étude statistique de son hypothèse de sécurité. Finalement nous proposons une cryptanalyse de tout schéma à clé publique basé sur la factorisation ou le logarithme discret dont la clé secrète est générée à partir d'un générateur linéaire. / In this thesis, we are interested in the security of pseudorandom number generators and of implementations of signature schemes. Regarding the signature schemes, we propose, in the case of a widespread implementation of RSA, various fault attacks which apply to any padding function. In addition we present a proven secure infective countermeasure to protect the RSA--PSS scheme against some non-random faults. Furthermore we study the ECDSA scheme coupled with the GLV/GLS speed-up techniques. Depending on the implementations, we prove either the good distribution of the used nonce, or that it has a bias, thereby enabling an attack. Finally we develop a tool for automatically finding fault attacks given an implementation and a fault policy, which is successfully applied to some RSA and ECDSA implementations. Regarding pseudorandom number generators, we study the nonlinear ones and improve some attacks by reducing the information available to the adversary. We also are interested in the security of the Micali-Schnorr generator through various attacks and a statistical study of its security assumption. Finally we propose a cryptanalysis of any public-key scheme based on the factorization or the discrete logarithm when the secret key is generated using a linear generator.

No description available.