Οι γεννήτριες τυχαίων αριθμών (ΓΤΑ) βρίσκονται στη ζωή του ανθρώπου εδώ και χιλιάδες χρόνια. Η πιο συχνή εφαρμογή τους είναι σε παιχνίδια που εμπεριέχουν τύχη, θεωρείστε για παράδειγμα το ζάρι που αποτελεί μια από τις πιο παλιές και πιο γνωστές γεννήτριες τυχαίων αριθμών. Ωστόσο με την πρόοδο της τεχνολογίας βρήκαν εφαρμογή και σε άλλους τομείς και κυρίως στην κρυπτογραφία, όπως για παράδειγμα στην ασφαλή μεταφορά δεδομένων στο διαδίκτυο ή στη διατήρηση της ασφάλειας ενός τοπικού δικτύου. Στα πλαίσια αυτής τη διπλωματικής θα δούμε τις κατηγορίες στις οποίες χωρίζονται οι ΓΤΑ καθώς επίσης και διάφορες πηγές τυχαιότητας γι’ αυτές. Στη συνέχεια θα επικεντρωθούμε στις Γεννήτριες Πραγματικά Τυχαίων Αριθμών και την εφαρμογή τους σε ολοκληρωμένα κυκλώματα όπως τα FPGA και θα δούμε κατάλληλες τεχνικές για την υλοποίηση τους. Έπειτα παρουσιάζουμε τη δομή και τη λειτουργία δύο γεννητριών που βασίζονται στην τεχνική που αξιοποιεί το jitter των ταλαντωτών. Η βασική τους διαφορά, η οποία κατ’ επέκταση επηρεάζει και το συνολικό σχεδιασμό, είναι ότι η μία έχει έναν αργό και ένα γρήγορο ταλαντωτή, ενώ η άλλη δύο γρήγορους ταλαντωτές. Στο στάδιο της υλοποίησης θα χρησιμοποιήσουμε τη γλώσσα περιγραφής υλικού VHDL και θα δούμε τη συμπεριφορά των σχεδιασμών μας όσον αφορά την επιφάνεια που καταλαμβάνουν και την ισχύ που καταναλώνουν για συγκεκριμένες τεχνολογίες FPGA. Επίσης θα ελέγξουμε τη στατιστική ποιότητα των ακολουθιών bit που παράγουν οι γεννήτριες μας για να επαληθεύσουμε την αποτελεσματική λειτουργία των σχεδιασμών μας. Τέλος θα συγκρίνουμε τις δύο ΓΠΤΑ που σχεδιάσαμε στους τομείς που μόλις αναφέραμε. / -

Pulsars, as rotating magnetised neutron stars got much attention during the last 40 years since their discovery. Observations revealed them to be gamma-ray emitters with energies continuing up to the sub 100 GeV region. Better observation of this upper energy cut-off region will serve to enhance our theoretical understanding of pulsars and neutron stars. The H-test has been used the most extensively in the latest periodicity searches, whereas other tests have limited applications and are unsuited for pulsar searches. If the probability distribution of a test statistic is not accurately known, it is possible that, after searching through many trials, a probability for uniformity can be given, which is much smaller than the real value, possibly leading to false detections. The problem with the H-test is that one must obtain the distribution by simulation and cannot do so analytically. For such simulations, random numbers are needed and are usually obtained by utilising so-called pseudo-random number generators, which are not truly random. This immediately renders such generators as useless for the simulation of the distribution of the H-test. Alternatively there exists hardware random number generators, but such devices, apart from always being slow, are also expensive, large and most still don't exhibit the true random nature required. This was the motivation behind the development of a hardware random number generator which provides truly random U(0,l) numbers at very high speed and at low cost The development of and results obtained by such a generator are discussed. The device delivered statistically truly random numbers and was already used in a small simulation of the H-test distribution. / Thesis (M.Sc. (Physics))--North-West University, Potchefstroom Campus, 2005.

Communication security is a very important part of modern life. A crucial aspect of security is the ability to identify with near 100% certainty who is on the other side of a connection. This problem can be overcome through the use of random number generators, which create unique identities for each person in a network. The effectiveness of an identity is directly proportional to how random a generator is. The speed at which a random number can be delivered is a critical factor in the design of a random number generator. This thesis covers the design and fabrication of three ring oscillator based truly random number generators, the first two of which were fabricated in 0.13µ m CMOS technology. The randomness from this type of random number generator originates from phase noise in a ring oscillator. The second and third ring oscillators were designed to have a low slew rate at the inverter switching threshold. The outputs of these designs showed vast increases in timing jitter compared to the first design. The third design exhibited improved randomness with respect to the second design.

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.

Compared with algorithms specialized for a single distribution universal (also called automatic or black-box) algorithms for continuous distributions were relatively seldom discussed. But they have important advantages for the user: One algorithm coded and tested only once can do the same or even more than a whole library of standard routines. It is only necessary to have a program available that can evaluate the density of the distribution up to a multiplicative factor. In this paper we show that transformed density rejection is well suited to construct universal algorithms suitable for correlation induction which is important for variance reduction in simulation. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

A rejection algorithm - called transformed density rejection - that uses a new method for constructing simple hat functions for an unimodal, bounded density $f$ is introduced. It is based on the idea to transform $f$ with a suitable transformation $T$ such that $T(f(x))$ is concave. $f$ is then called $T$-concave and tangents of $T(f(x))$ in the mode and in a point on the left and right side are used to construct a hat function with table-mountain shape. It is possible to give conditions for the optimal choice of these points of contact. With $T=-1/\sqrt(x)$ the method can be used to construct a universal algorithm that is applicable to a large class of unimodal distributions including the normal, beta, gamma and t-distribution. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

The inversion method for generating non-uniform random variates has some advantages compared to other generation methods, since it monotonically transforms uniform random numbers into non-uniform random variates. Hence it is the method of choice in the simulation literature. However, except for some simple cases where the inverse of the cumulative distribution function is a simple function we need numerical methods. Often inversion by ``brute force" is used, applying either very slow iterative methods or linear interpolation of the CDF and huge tables. But then the user has to accept unnecessarily large errors or excessive memory requirements, that slow down the algorithm. In this paper we demonstrate that with Hermite interpolation of the inverse CDF we can obtain very small error bounds close to machine precision. Using our adaptive interval splitting method this accuracy is reached with moderately sized tables that allow for a fast and simple generation procedure. The algorithms described in this paper have been implemented in ANSI C in a library called UNURAN which is available via anonymous ftp. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

Pulsars, as rotating magnetised neutron stars got much attention during the last 40 years since their discovery. Observations revealed them to be gamma-ray emitters with energies continuing up to the sub 100 GeV region. Better observation of this upper energy cut-off region will serve to enhance our theoretical understanding of pulsars and neutron stars. The H-test has been used the most extensively in the latest periodicity searches, whereas other tests have limited applications and are unsuited for pulsar searches. If the probability distribution of a test statistic is not accurately known, it is possible that, after searching through many trials, a probability for uniformity can be given, which is much smaller than the real value, possibly leading to false detections. The problem with the H-test is that one must obtain the distribution by simulation and cannot do so analytically. For such simulations, random numbers are needed and are usually obtained by utilising so-called pseudo-random number generators, which are not truly random. This immediately renders such generators as useless for the simulation of the distribution of the H-test. Alternatively there exists hardware random number generators, but such devices, apart from always being slow, are also expensive, large and most still don't exhibit the true random nature required. This was the motivation behind the development of a hardware random number generator which provides truly random U(0,l) numbers at very high speed and at low cost The development of and results obtained by such a generator are discussed. The device delivered statistically truly random numbers and was already used in a small simulation of the H-test distribution. / Thesis (M.Sc. (Physics))--North-West University, Potchefstroom Campus, 2005.

Randomness is an important part of computer science. A large group of work, both in theoretical and practical computer science, is dedicated to the study of whether true 'randomness' is necessary for a variety of applications and protocols to work. One of the main uses for randomness is in the generation of keys, used as a security measure for many cryptographic protocols. The main measure of randomness is achieved by looking at entropy, a measure of the disorder of a system. Nature is able to provide us with many sources that are high in entropy. However, many cryptographic protocols need sources of randomness that are stronger (higher in entropy) than what is present naturally to ensure security. Therefore, a gap exists between what is available in Nature, and what is necessary for provable security. This paper looks to bridge this gap. Research in pseudorandom number generation has gone on for decades. However, many of the past constructions were lacking in either documentation or provable security of their methods. The need for a pseudorandom number generator (PRG) with provable security and strong documentation is evident. A new construction of a PRG is introduced. The new construction, labeled XRNG, looks to encompass recent research in the field of extractors along with previously known research in the field of pseudorandom number generation. Extractors, as the name suggests, looks to extract close to random information from high entropy sources.

Three different algorithms for the generation of stationary Gaussian time series with given autocorrelation function are presented in this paper. The algorithms have already been suggested in the literature but are not well known and have never been compared before. Interrelations between the different methods, advantages and disadvantages with respect to speed and memory requirements and the range of autocorrelation functions for which the different methods are stable are discussed. The time-complexity of the algorithms and the comparisons of their implementations show that the method twice using the Fourier transform is by far the most efficient if time series of moderate or large length are generated. A tested C-code of the latter algorithm is included as this method is tricky to implement and very difficult to find in the literature. (We know only one reference, that gives a correct algorithm, but there the description is very short and no proof is included.) (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing