Cryptographic Applications of Generali. Lucas-Sequences, II

Research project P 14472 Cryptographic Applications of Generali. Lucas-Sequences, II Winfried B. MÜLLER 26.6.2000 One of the major problems to be dealt with in modern cryptography is the efficient generation of large "random" prime numbers. Many of the existing crypto mechanisms and their security are based on the size and structure of their underlying primes. If the primes are too small or of a special structure, numerous attacks are known for breaking the crypto scheme or compromising the system`s security. Due to their practicality, most of the mechanisms for generating prime numbers are probabilistic. Although they are faster than their deterministic counterparts, they lead to the problem of so-called pseudoprimes. These are composite numbers that are wrongfully identified as prime by a probable prime test. The most efficient and reliable pseudo primality tests utilise Lucas sequences. In FWF Project P13088-MAT some fundamental properties of such sequences were analysed that that have helped to reveal why they present such an important tool in the area of probable prime testing. Both, a distinct characterisation of Lucas based pseudoprimes as well as some improvements of pseudoprimality testing algorithms have been presented. Yet, the studies have opened up numerous new and interesting open problems in this field. The main goals for the proposed project are an extension and improvement of the results obtained in FWF Project P13088-MAT. The principal goal consists of efficiently combining these results in order to establish further improvements of probable prime tests and to obtain a more specific characterisation of their pseudoprimes. A further goal is to generalise and extend the results of FWF P13088-MAT to other related algebraic settings. Moreover, the detailed analysis of the Lucas sequences in FWF P13088-MAT has lead to substantial number- theoretic and algebraic results of generalised Lucas sequences. Based on these, a clear characterisation of important underlying properties of these sequences was obtained. These results are not only of theoretical interest but have also been applied to various cryptographic algorithms. A further task for the proposed project consists in optimising and further extending the relevant number-theoretic and cryptographic algorithms as well as obtaining several improvements as well as a more detailed cryptanalysis of systems based on recurrence sequences.

Development of a new probabilistic prime test which is more efficient in theory and practice as all up to now known algorithms for the determination of large primes. One of the major problems to be dealt with in modern cryptography is the efficient generation of large "random" prime numbers. Many of the existing crypto mechanisms and their security are based on the size and structure of their underlying primes. If the primes are too small or of a special structure, numerous attacks are known for breaking the crypto scheme or compromising the system`s security. While theoretical studies of prime numbers go back centuries, even milleniums, the problem of practically recognizing primes has become a central subject of mathematical research only recently by the applications in cryptology. Due to their practicality, most of algorithms for generating prime numbers are probabilistic. Although these tests are faster than their deterministic counterparts, they lead to the problem of so-called pseudoprimes. These are composite numbers that are wrongfully identified as prime by a probable prime test. The main goal of the project was the design of new und better probabilistic prime tests und the calculation of upper bounds for their probability of failure. For that purpose the most important known probabilistic tests for primes have been analysed and the properties of pseudoprimes investigated. As main result a new probabilistic prime test based on the so-called Lucas sequences was established. This test turns out to be practically more efficient than all up to now known prime tests.