Algorithms used in asymmetric cryptosystems

Problem definition

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:

1) select as candidate a random number of appropriate size;

2) test for primality;

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:

1) given can be checked in deterministic polynomial time whether ;

2) if is prime, then (the empty set);

3) if is composite, then .

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.

Fermat's test

Fermat's test is based on Fermat’s theorem. This theorem asserts that if is a prime and is any integer from , then .

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 .

Let's consider algorithm of Fermat's test which is represented as function FERMAT(,).

```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]

A Carmichael number is a composite integer such that for all integers which satisfy .

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.

Solovay-Strassen test

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.

The integer is called an Euler liar for , if and . And is said to be an Euler pseudo pime to the base .

Let's consider algorithm of Solovay-Strassen probabilistic primality test which is represented as function SOLOVAY-STRASSEN(,).

```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).

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 .

Let's consider algorithm of Miller-Rabin probabilistic primality test which is represented as function MILLER-RABIN(,).

```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:
2.3.2.1 Compute .
2.3.2.2 If  then return(“composite”).
2.3.2.3 .
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.

A Mersenne number is an integer of the form for . If is prime, then it is called a Mersenne prime.

Let . The Mersenne number is prime if and only if the following two conditions are satisﬁed:

1) s is prime;

2) the sequence of integers deﬁned by and for satisﬁes .

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").
```

Nowadays only 48 prime Mersenne numbers are known. The biggest one is .

There are another ways for true primality testing such as factorization of , Jacobi sum test and tests using elliptic curves. But they will not be described here because of their complexity.

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]

Let's consider algorithm of Random search for a prime using the Miller-Rabin probabilistic primality test which is represented as function RANDOM-SEARCH(,).

```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.

A prime number is said to be a strong prime if integers , and exist such that the following three conditions are satisﬁed:

1) has a large prime factor, denoted ;

2) has a large prime factor, denoted ;

3) has a large prime factor, denoted .

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().
```

Let's prove that the prime returned by Gordon’s algorithm is indeed a strong prime:

1) according to Fermat’s theorem (assuming ), and hence and ;

2) , and hence has the prime factor ;

3) , and hence has the prime factor ;

4) , and hence has the prime factor .

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:

1) is a 160-bit prime;

2) is a -bit prime, where for ;

3) divides .

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]

Let be an odd integer. Suppose that where is an odd prime and . Then:

1) if there exists an integer a satisfying and , then is prime;

2) if is prime, the probability that a randomly selected base , satisﬁes and is .

Maurer’s algorithm recursively generates an odd prime , and then chooses random integers , , until can be proven prime for some base .

```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().
```

Irreducible polynomials

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 .

The polinomial is said to be monic polynomials in if it's leading coefﬁcient is 1.

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 be a prime and let be a positive integer. Then:

1) The product of all monic irreducible polynomials in of degree dividing is equal to .

2) Let be a polynomial of degree in . Then is irreducible over if and only if .

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").
```

Now let's consider an algorithm of generating a random monic irreducible polynomial over , which is based on algorithm of testing a polynomial for irreducibility described above.

```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().
```

The algorithm of generating a random monic irreducible polynomial over complexity is operations in .

Primitive polynomials

Polynomial of degree in is called primitive polynomial if is a generator of . Such polynomials can be used in generating of linear recurring sequences of maximal period.

Let be a prime and let the distinct prime factors of be . Then an irreducible polynomial is primitive if and only if for each : .

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.

Let's consider an algorithm of an efﬁcient method for determining the order of a group element, given the prime factorization of the group order .

```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().
```

If , where and are distinct odd primes, then is a non-cyclic group of order . The maximum order of an element in is .

Let's consider an algorithm for generating such an element of maximum order in .

```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().
```

Bibliography

Go to references page of the section "Algorithms used in asymmetric cryptosystems".

Gusev P., Lovyannikov A.