One of the foundations of cryptography is number theory. As building blocks, primes are central to the field and are used in many cryptographic algorithms. Of course, this means these algorithms require access to random prime numbers. When choosing them, we must be careful as certain primes allow for the Chinese remainder theorem to be used to efficiently compute our secret keys. These attacks can be prevented by using so called "strong" primes. We study them and present two algorithms for generating such numbers. We prove their correctness and determine their time complexity. Since these algorithms use random primes, we continue with an analysis of LFSR based random number generators. These can be used as building blocks in the CCSR generator and similar ideas are used by the Mersenne Twister generator. After this, we briefly discuss primality tests, focusing on probabilistic tests. These components are then combined into a efficient random strong prime number generator. Finally, the quality and speed of the generator are tested and the results are presented.
|
