Algorithms used in asymmetric cryptosystems
The efficient generation of public-key parameters is a prerequisite in public-key systems. For example, for using number and its derivatives in the Diffie-Hellman key agreement protocol, the number should be prime to define a finite field and an extra element of high order in is also required. Another example is the requirement of primes and for an RSA modulus . In this case, the prime must be of sufﬁcient size, and be “random” in the sense that the probability of selecting any particular prime must be sufﬁciently small.[KL07] The last condition precludes an adversary from gaining advantage through optimizing a search strategy based on such probability. In some cases prime numbers may be required to have certain additional properties, in order that they do not make the associated cryptosystems susceptible to specialized attacks. The last example is the requirement to find irreducible polynomial of degree over the finite field and an extra element of high order in for constructing the finite field .
This section introduces basic conceptions relevant to prime number generation, probabilistic primality tests, true primality tests, techniques for constructing irreducible and primitive polynomials, production of generators and elements of high orders in groups.
Approaches to generating large prime numbers
The most natural method to find prime number is to generate a random number of selected size and check it is primality. This can be done by checking whether is divisible by any of the prime numbers smaller or equal to , but this approach is too ineffective and doesn't apply in practice.
Let's consider the following approach:
Applying special search sequences to selecting candidate make prime number generator more effective, because special search sequences increase the probability that candidate is prime and meet additional conditions. The trivial example of special search sequence is to take as candidate only odd numbers starting from number (e.i. select from ).
In step 2, the test for primality might be either a probabilistic primarily test or true primality test. Probabilistic primality tests are tests, which are absolutely correct, when they declare candidate to be composite, but do not provide a mathematical proof that is prime. This is the reason why prime according to probabilistic test number is declared to be "probably prime". True primality tests allow one to conclude with mathematical certainty that a number is prime, but, generally, such kind of test require considerably greater computational resources.
Another distinction between different techniques for prime number generation is the use of randomness. Candidates are typically generated as a function of a random input, but the entire algorithm of primality test can either use random numbers or not. In the former, tests are called randomized, in the latter --- deterministic.[GB08]
Probabilistic primality tests
Probabilistic primality tests have the following framework. For each odd positive integer , a set is deﬁned such that three following properties hold:
These properties of the sets are utilized in the following manner. Suppose that is an integer whose primality is to be determined. An integer is randomly chosen and it's checked whether or not. At the latter case test outputs "prime" and "composite" at the former. If test outputs "composite" then is said to fail the primality test for the base and it's surely composite. If test outputs "prime" then is said to pass the primality for the base and no conclusion with absolute certainty can be made about the primality of .
Any single execution of this test which declares "composite" establishes this with certainty. But any single execution of this test which declares "prime" has the probability of error . So if one will run the test times independently on the candidate then the probability of error is at most .
Two probabilistic primality tests are covered in this section: the Solovay-Strassen test and the Miller-Rabin test. For historical reasons, the Fermat test will be also discussed, but this test is not truly a probabilistic primality test since it usually fails to distinguish between prime numbers and special composite integers called Carmichael numbers.
Therefore, given an integer whose primality is under question, ﬁnding any integer in this interval such that this equivalence is not true sufﬁces to prove that is composite. And conversely, if there is an integer from such that then is a prime in the sense that it satisﬁes Fermat’s theorem for the base .
FERMAT(,) INPUT: an odd integer and security parameter . OUTPUT: an answer to the question: "Is prime?" 1. For from 1 to do the following: 1.1 Choose a random integer , . 1.2 Compute . 1.3 If then return ("composite"). 2. return("prime").
As it has been mentioned earlier, if Fermat's test outputs "composite" then is composite, but if it outputs "prime" you have no guarantee that it's indeed prime: can be presudo prime. Nonetheless, since there is few pseudo prime numbers for a give base , Fermat's test provides a correct answer most of inputs. But even if Fermat's test output "prime" on every input, it only means that is either prime or Carmichael number.[G04]
If is a Charmichael number, then Fermat's test will output "composite" only for from , for which . Thus, if prime factors of are large, the Fermat's test will output "prime" even for big number of iterations. This is the reason why Fermat's test is removed in Solovay-Strassen and Miller-Rabin probabilistic primality tests.
The Solovay-Strassen probabilistic primality test was the ﬁrst such test which became popular when public-key cryptography, in particular the RSA cryptosystem. This test relying on more strong criteria, then Fermat's theorem. So it's main advantage in comparison with Fermat's test is that Solovay-Strassen test distinguish Carmichael numbers as composite.
The first method, which allows to distinguish Carmichael numbers, has been introduced by D. Lemmer. D. Lemmer in 1976 and separately Robert M. Solovay and Volker Strassen in 1977 proved the statement that there is no numbers which are simultaneously Euler pseudo prime and prime. Right after that Robert M. Solovay and Volker Strassen has published their test, which is based on that statement.
SOLOVAY-STRASSEN(,) INPUT: an odd integer and security parameter . OUTPUT: an answer to the question: "Is prime?" 1. For from 1 to do the following: 1.1 Choose a random integer , . 1.2 Compute . 1.3 If and then return ("composite"). 1.4 Compute the Jacobi symbol 1.5 If then return ("composite"). 2. return("prime").
If SOLOVAY-STRASSEN(,) outputs "composite" then is certainly composite. If it outputs "prime" the probability of error is at most . So if one will perform SOLOVAY-STRASSEN(,) times with independently chosen for every roud then the probability of error will be at most .
This test relying on more strong criteria than Fermat's theorem, but there is no longer any reason to use it, because there are more both more efﬁcient and always at least as correct probabilistic primality tests (e.g. Miller-Rabin test).
The probabilistic primality test most used in practice is the Miller-Rabin test, also known as the strong pseudo prime test. The test is based on the following fact.
Let be an odd composite integer and let where is odd. Let be an integer from . Then if and if for all then is called a strong witness(to compositeness) for . Otherwise is said to be a strong pseudo prime to the base . The integer is called a strong liar (to primality) for .
MILLER-RABIN(,) INPUT: an odd integer and security parameter . OUTPUT: an answer to the question: "Is prime?" 1. Write such that is odd. 2. For from 1 to do the following: 2.1 Choose a random integer , . 2.2 Compute . 2.3 If and then do the following: 2.3.1 . 2.3.2 While and do the following: 188.8.131.52 Compute . 184.108.40.206 If then return(“composite”). 220.127.116.11 . 2.3.3 If then return (“composite”). 3. Return(“prime”).
If MILLER-RABIN(,) outputs "composite" then is certainly composite. If it outputs "prime" the probability of error is at most . So if one will perform MILLER-RABIN(,) times with independently chosen for every round then the probability of error will be at most .
True Primality tests
The primality tests in this section are methods by which positive integers can be mathematically proven to be prime, and are often referred to as primality proving algorithms. These primality tests are generally more computationally intensive than the probabilistic primality tests. But efﬁcient algorithms for testing primality of some special classes of numbers are known (e.g., Mersenne and Fermat numbers).
Testing Mersenne numbers
Mersenne primes are useful because the arithmetic in the ﬁeld for such can be implemented very efﬁciently. This is the reason to consider an efficient algorithm of true primality test for Mersenne numbers. The Lucas-Lehmer test is such an algorithm.
1) s is prime;
The fact above allows to construct deterministic polynomial-time algorithm of determining primality of Mersenne number. This algorithm is shown below.
INPUT: a Mersenne number with . OUTPUT: an answer to the question: "Is prime?" 1. Use trial division to check if has any factors between 2 and . If it does, then return("composite"). 2. Set . 3. For do the following: compute . 4. If then return("prime"). Otherwise, return("composite").
Prime number generation
This section considers algorithms for the generation of prime numbers for cryptographic purposes.
Random search for probable primes
As it has been mentioned earlier, the easiest way to find prime number is to select a random candidate and check it using probabilistic primality test (e.g., Miller-Rabin primality test). But if candidate is divisible by a small prime, it is more efficiently to rule out the candidate by trial division than by using the Miller-Rabin test. Since the probability that a random integer has a small prime divisor is relatively large it's better to tested for small divisors below a pre-determined bound , before applying any probabilistic primality test. This can be done by dividing by all the primes below , or by computing GCD (greatest common divisors) of and (pre-computed) products of several of the primes . [MOV01]
RANDOM-SEARCH(,) INPUT: an integer and security parameter . OUTPUT: a random -bit probable prime. 1. Generate random odd -bit integer . 2. Use trial division to determine whether is divisible by any odd prime . If it is then go to step 1. 3. If MILLER-RABIN(,) outputs "prime" then return(). Otherwise, go to step 1.
Strong primes generation
The RSA cryptosystem uses a modulus of the form , where and are distinct odd primes. Because factorization of should be beyond computational reach, the primes and must be of sufﬁcient big size. In practice, according to system speciﬁcations, the resulting primes must also be of a pre-determined bitlength.[M03] The cryptanalysis of the RSA cryptosystem led to appearance of many classes of possible attacks. This results in many limitations of selection of primes and definition of the notion of a strong prime. But there was proved that usage of strong primes instead of real ones don't make algorithm more secure in practice.
In this definition a precise qualiﬁcation of “large” depends on speciﬁc attacks that should be guarded against.
Let's consider Gordon’s algorithm for generating a strong prime.
1. Generate two large random primes and of roughly equal bitlength. 2. Select an integer . 3. Find the ﬁrst prime in the set and denote it by . 4. Compute . 5. Select an integer . 6. Find the ﬁrst prime in the set and denote this prime by . 7. Return().
If the Miller-Rabin test is the primality test used in steps 1, 2, and 4, the expected time Gordon’s algorithm takes to ﬁnd a strong prime is only about 19% more than the expected time takes to ﬁnd a random prime.
NIST method for generating DSA primes
Some public-key schemes require primes satisfying various speciﬁc conditions. This subsection presents an algorithm for generating primes and according to NIST Digital Signature Algorithm, e.i. and satisfying the following three conditions:
In the following, denotes the SHA-1 hash function which converts bitstrings of bitlength < to 160-bit hash-codes. Where required, an integer whose binary representation is should be converted to the g-bit sequence , and vice versa.
Let's consider NIST method for generating DSA primes.
INPUT: an integer , . OUTPUT: a 160-bit prime and an -bit prime , where and . 1. Compute 2. Using long division of by 160, find , such that , where . 3. Repeat the following: 3.1 Choose a random seed (not necessarily secret) of bitlength . 3.2 Compute . 3.3 Get from by setting to 1 the most signiﬁcant and least signiﬁcant bits of U. 3.4 Test for primality using MILLER-RABIN(,) for , Until is found to be a probable prime. 4. Set , . 5. While do the following: 5.1 Set for . 5.2 Let , where . 5.3 Compute and set . 5.4 If then do the following: 5.4.1 Test for primality using MILLER-RABIN(,) for . 5.4.2 If is a probable prime then return(,). 5.5 Set , 6. Go to step 2.
Constructive techniques for provable primes
The most commonly used constructive technique for provable primes is Maurer’s algorithm. This algorithm generates random provable primes that are almost uniformly distributed over the set of all primes of a speciﬁed size. The expected time for generating a prime is only slightly greater than that for generating a probable prime of equal size using random search algorithm with security parameter .[S05]
PROVABLE PRIME() INPUT: a positive integer . OUTPUT: a -bit prime number . 1. If then repeatedly do the following: 1.1 Select a random -bit odd integer . 1.2 Use trial division by all primes less than to determine whether is prime. 1.3 If is prime then return(). 2. Set and . 3. Set . 4. If then repeatedly do the following: 4.1 Select a random number . 4.2 Set . 4.3 If go to step 4.1. Otherwise set . 5. Compute PROVABLE_PRIME(). 6. Set . 7. . 8. While () do the following: 8.1 Select a random integer in the interval 8.2 Set . 8.2 Use trial division to determine whether is divisible by any prime number < . If it is not then do the following: Select a random integer in the interval . Compute . If then do the following: Compute and . If then . 9. Return().
The polynomial of degree is said to be irreducible over if it cannot be written as a product of two polynomials in each having degree less than . Such a polynomial can be used to represent the elements of the ﬁnite ﬁeld as , the set of all polynomials in of degree less than where the addition and multiplication of polynomials is performed modulo .
This subsection presents techniques for constructing irreducible polynomials over , where is a prime. The characteristic of two ﬁnite ﬁelds are of particular interest for cryptographic applications because the arithmetic in these ﬁelds can be efﬁciently performed both in software and in hardware. For this reason, additional attention is given to the special case of irreducible polynomials over .
If is irreducible over and is a non-zero element in , then their product is also irreducible over . [F10] It's sufﬁces to restrict attention that if is an irreducible polynomial, then its constant term must be non-zero. In particular, if , then its constant term must be 1.
Let's consider algorithm of testing a polynomial for irreducibility.
INPUT: a prime and a monic polynomial of degree . OUTPUT: an answer to the question: "Is irreducible over ?" 1. Set . 2. For do the following: 2.1 Compute . 2.2 Compute . 2.3 If then return("reducible"). 3. return("irreducible").
INPUT: a prime and a positive integer . OUTPUT: a monic irreducible polynomial of degree in . 1. Repeat the following: 1.1 Randomly select set of integers where and . 1.2 Let . 1.3 Use algorithm of testing a polynomial for irreducibility to test whether is irreducible over . Until is irreducible. 2. Return().
So if be an irreducible polynomial of degree and the factorization of the integer is known, then there is an efﬁcient algorithm for testing whether or not is a primitive polynomial. If the factorization of is unknown, there is no efﬁcient algorithm known for performing this test.
Let's consider an algorithm for testing whether an irreducible polynomial is primitive or not.
INPUT: a prime , a positive integer , the distinct prime factors of , a monic irreducible polynomial of degree in . OUTPUT: an answer to the question: "Is a primitive polynomial?" 1. For do the following: 1.1 Set . 1.2 If then return("not primitive"). 2. Return("primitive")
There are precisely monic primitive polynomials of degree in , where is the Euler phi function. Since the number of monic irreducible polynomials of degree in is roughly , it follows that the probability of a random monic irreducible polynomial of degree in being primitive is approximately
Generators and elements of high order
Let is a (multiplicative) ﬁnite group. The least positive integer such that is called an order of an element . Group is said to be cyclic if there are elements in and is an element of order . In such case is called a generator or a primitive element of .
Of special interest for cryptographic applications are the multiplicative group of the integers modulo a prime , and the multiplicative group of the ﬁnite ﬁeld of characteristic two; these groups are cyclic. Also of interest is the group , where is the product of two distinct odd primes.
INPUT: a (multiplicative) ﬁnite group of order , an element , the prime factorization . OUTPUT: the ordert of . 1. Set . 2. For do the following: 2.1 Set . 2.2 Compute . 2.3 While do the following: 2.3.1 Compute 2.3.2 Set . 3. Return().
Suppose now that is a cyclic group of order . Then for any divisor of the number of elements of order in is exactly , where is the Euler phi function. In particular, has exactly generators, and hence the probability of a random element in being a generator is . This suggests the following efﬁcient randomized algorithm for ﬁnding a generator of a cyclic group.
INPUT: a cyclic group of order , and the prime factorization . OUTPUT: a generator of . 1. Choose a random element in . 2. For do the following: 2.1 Compute . 2.2 If then go to step 1. 3. Return().
INPUT: two distinct odd primes and , the factorizations of and . OUTPUT: an element of maximum order in , where . 1. Fnd a generator of . 2. Fnd a generator of . 3. Use Gauss’s algorithm to ﬁnd an integer satisfying and . 4. Return().
Go to references page of the section "Algorithms used in asymmetric cryptosystems".
Gusev P., Lovyannikov A.