Algorithms used in asymmetric cryptosystems

From CryptoWiki
Jump to: navigation, search

Contents

Problem definition

The efficient generation of public-key parameters is a prerequisite in public-key systems. For example, for using number 1 16 en p.png and its derivatives in the Diffie-Hellman key agreement protocol, the number 1 16 en p.png should be prime to define a finite field 1 16 en mathbb Z p.png and an extra element of high order in 1 16 en mathbb Z p .png is also required. Another example is the requirement of primes 1 16 en p.png and 1 16 en q.png for an RSA modulus 1 16 en n=pq.png. In this case, the prime must be of sufficient size, and be “random” in the sense that the probability of selecting any particular prime must be sufficiently 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 1 16 en f(x).png of degree 1 16 en m.png over the finite field 1 16 en mathbb Z p.png and an extra element of high order in 1 16 en mathbb F p m .png for constructing the finite field 1 16 en mathbb F p m.png.

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.

Back to table of contents

Approaches to generating large prime numbers

The most natural method to find prime number is to generate a random number 1 16 en n.png of selected size and check it is primality. This can be done by checking whether 1 16 en n.png is divisible by any of the prime numbers smaller or equal to 1 16 en sqrt n.png, 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 1 16 en n.png of appropriate size;

2) test 1 16 en n.png for primality;

3) if 1 16 en n.png compose, return to the first step.

Applying special search sequences to selecting candidate 1 16 en n.png 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 1 16 en n.png only odd numbers starting from number 1 16 en m.png (e.i. select 1 16 en n.png from 1 16 en m m+2 m+4 .png).

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 1 16 en n.png to be composite, but do not provide a mathematical proof that 1 16 en n.png 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]

Back to table of contents

Probabilistic primality tests

Probabilistic primality tests have the following framework. For each odd positive integer 1 16 en n.png, a set 1 16 en W(n) subset mathbb Z n.png is defined such that three following properties hold:

1) given 1 16 en a in mathbb Z n.png can be checked in deterministic polynomial time whether 1 16 en a in W(n).png;

2) if 1 16 en n.png is prime, then 1 16 en W(n) = emptyset.png (the empty set);

3) if 1 16 en n.png is composite, then 1 16 en W(n) ge frac n 2.png.

These properties of the sets 1 16 en W(n).png are utilized in the following manner. Suppose that 1 16 en n.png is an integer whose primality is to be determined. An integer 1 16 en a in mathbb Z n.png is randomly chosen and it's checked whether 1 16 en a in W(n).png or not. At the latter case test outputs "prime" and "composite" at the former. If test outputs "composite" then 1 16 en n.png is said to fail the primality test for the base 1 16 en a.png and it's surely composite. If test outputs "prime" then 1 16 en n.png is said to pass the primality for the base 1 16 en a.png and no conclusion with absolute certainty can be made about the primality of 1 16 en n.png.

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 1 16 en frac 1 2.png. So if one will run the test 1 16 en t.png times independently on the candidate 1 16 en n.png then the probability of error is at most 1 16 en (frac 1 2) t.png.


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.

Back to table of contents

Fermat's test

Fermat's test is based on Fermat’s theorem. This theorem asserts that if 1 16 en n.png is a prime and 1 16 en a.png is any integer from 1 16 en 1, 2, ... n-1.png, then 1 16 en a n-1 equiv 1(mod n).png.

Therefore, given an integer 1 16 en n.png whose primality is under question, finding any integer 1 16 en a.png in this interval such that this equivalence is not true suffices to prove that 1 16 en n.png is composite. And conversely, if there is an integer 1 16 en a.png from 1 16 en 1, 2, ... n-1.png such that 1 16 en a n-1 equiv 1(mod n).png then 1 16 en n.png is a prime in the sense that it satisfies Fermat’s theorem for the base 1 16 en a.png.

Let's consider algorithm of Fermat's test which is represented as function FERMAT(1 16 en n.png,1 16 en t.png).

FERMAT(1 16 en n.png,1 16 en t.png)
INPUT: an odd integer 1 16 en n ge 3.png and security parameter 1 16 en t ge 1.png.
OUTPUT: an answer to the question:  "Is 1 16 en n.png prime?"
 1. For 1 16 en i.png from 1 to 1 16 en t.png do the following:
  1.1 Choose a random integer 1 16 en a.png, 1 16 en a in 2, ,3 dots ,n-2.png.
  1.2 Compute 1 16 en r=a (n-1) mod n.png.
  1.3 If 1 16 en r ne 1.png then return ("composite").
 2. return("prime").

As it has been mentioned earlier, if Fermat's test outputs "composite" then 1 16 en n.png is composite, but if it outputs "prime" you have no guarantee that it's indeed prime: 1 16 en n.png can be presudo prime. Nonetheless, since there is few pseudo prime numbers for a give base 1 16 en a.png, 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 1 16 en n.png is either prime or Carmichael number.[G04]

A Carmichael number 1 16 en n.png is a composite integer such that 1 16 en a n-1 equiv 1(mod n).png for all integers 1 16 en a.png which satisfy 1 16 en gcd(a,n)=1.png.

If 1 16 en n.png is a Charmichael number, then Fermat's test will output "composite" only for 1 16 en a.png from 1 16 en 1, 2, ... n-1.png, for which 1 16 en gcd(a,n) g 1.png. Thus, if prime factors of 1 16 en n.png 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.

Back to table of contents

Solovay-Strassen test

The Solovay-Strassen probabilistic primality test was the first 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 1 16 en a.png is called an Euler liar for 1 16 en n.png, if 1 16 en gcd(a,n)=1.png and 1 16 en a frac n-1 2 equiv (frac a n) (mod n).png. And 1 16 en n.png is said to be an Euler pseudo pime to the base 1 16 en a.png.

Let's consider algorithm of Solovay-Strassen probabilistic primality test which is represented as function SOLOVAY-STRASSEN(1 16 en n.png,1 16 en t.png).

SOLOVAY-STRASSEN(1 16 en n.png,1 16 en t.png)
INPUT: an odd integer 1 16 en n ge 3.png and security parameter 1 16 en t ge 1.png.
OUTPUT: an answer to the question:  "Is 1 16 en n.png prime?"
 1. For 1 16 en i.png from 1 to 1 16 en t.png do the following:
  1.1 Choose a random integer 1 16 en a.png, 1 16 en a in 2, ,3 dots ,n-2.png.
  1.2 Compute 1 16 en r=a frac n-1 2 mod n.png.
  1.3 If 1 16 en r ne 1.png and 1 16 en r ne n-1.png then return ("composite").
  1.4 Compute the Jacobi symbol 1 16 en s=(frac a n).png
  1.5 If 1 16 en r not equiv s (mod n).png then return ("composite").
 2. return("prime").

If SOLOVAY-STRASSEN(1 16 en n.png,1 16 en a.png) outputs "composite" then 1 16 en n.png is certainly composite. If it outputs "prime" the probability of error is at most 1 16 en frac 1 2.png. So if one will perform SOLOVAY-STRASSEN(1 16 en n.png,1 16 en a.png) 1 16 en t.png times with independently chosen for every roud 1 16 en a.png then the probability of error will be at most 1 16 en (frac 1 2) t.png.

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 efficient and always at least as correct probabilistic primality tests (e.g. Miller-Rabin test).

Back to table of contents

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 1 16 en n.png be an odd composite integer and let 1 16 en n-1=2 8r.png where 1 16 en r.png is odd. Let 1 16 en a.png be an integer from 1 16 en 1, 2, ... n-1.png. Then if 1 16 en a r not equiv 1 (mod n).png and if 1 16 en a 2 j r not equiv -1 (mod n).png for all 1 16 en j= overline 0,(s-1).png then 1 16 en a.png is called a strong witness(to compositeness) for 1 16 en n.png. Otherwise 1 16 en n.png is said to be a strong pseudo prime to the base 1 16 en a.png. The integer 1 16 en a.png is called a strong liar (to primality) for 1 16 en n.png.

Let's consider algorithm of Miller-Rabin probabilistic primality test which is represented as function MILLER-RABIN(1 16 en n.png,1 16 en t.png).

MILLER-RABIN(1 16 en n.png,1 16 en t.png)
INPUT: an odd integer 1 16 en n ge 3.png and security parameter 1 16 en t ge 1.png.
OUTPUT: an answer to the question:  "Is 1 16 en n.png prime?"
 1. Write 1 16 en n-1=2 8r.png such that 1 16 en r.png is odd.
 2. For 1 16 en i.png from 1 to 1 16 en t.png do the following:
  2.1 Choose a random integer 1 16 en a.png, 1 16 en a in 2, ,3 dots ,n-2.png.
  2.2 Compute 1 16 en y=a r (mod n).png.
  2.3 If 1 16 en y ne 1.png and 1 16 en y ne n-1.png then do the following:
   2.3.1 1 16 en y leftarrow 1.png.
   2.3.2 While 1 16 en j le s-1.png and 1 16 en y ne n-1.png do the following:
    2.3.2.1 Compute 1 16 en y leftarrow y 2 mod n.png.
    2.3.2.2 If 1 16 en j=1.png then return(“composite”).
    2.3.2.3 1 16 en y leftarrow y+1.png.
   2.3.3 If 1 16 en y ne n-1.png then return (“composite”).
 3. Return(“prime”).

If MILLER-RABIN(1 16 en n.png,1 16 en a.png) outputs "composite" then 1 16 en n.png is certainly composite. If it outputs "prime" the probability of error is at most 1 16 en frac 1 4.png. So if one will perform MILLER-RABIN(1 16 en n.png,1 16 en a.png) 1 16 en t.png times with independently chosen for every round 1 16 en a.png then the probability of error will be at most 1 16 en (frac 1 4) t.png.

Back to table of contents

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 efficient algorithms for testing primality of some special classes of numbers are known (e.g., Mersenne and Fermat numbers).

Back to table of contents

Testing Mersenne numbers

Mersenne primes 1 16 en n.png are useful because the arithmetic in the field 1 16 en mathbb Z n.png for such 1 16 en n.png can be implemented very efficiently. 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 1 16 en 2 s-1.png for 1 16 en s ge 2.png. If 1 16 en 2 s-1.png is prime, then it is called a Mersenne prime.

Let 1 16 en s ge 3.png. The Mersenne number 1 16 en n=2 s-1.png is prime if and only if the following two conditions are satisfied:

1) s is prime;

2) the sequence of integers defined by 1 16 en u 0=4.png and 1 16 en u k+1=(u k 2-2) mod n.png for 1 16 en k ge 0.png satisfies 1 16 en u (s-2)=0.png.

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 1 16 en n=2 s-1.png with 1 16 en s ge 3.png.
OUTPUT: an answer to the question: "Is 1 16 en n.png prime?"
1. Use trial division to check if 1 16 en s.png has any factors between 2 and 1 16 en sqrt s.png. If it does, then return("composite").
2. Set 1 16 en u leftarrow 4.png.
3. For 1 16 en k= overline 1,(s-2).png do the following: compute 1 16 en u leftarrow (u 2-2) mod n.png.
4. If 1 16 en u=0.png then return("prime"). Otherwise, return("composite").

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

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

Back to table of contents

Prime number generation

This section considers algorithms for the generation of prime numbers for cryptographic purposes.

Back to table of contents

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 1 16 en n.png is divisible by a small prime, it is more efficiently to rule out the candidate 1 16 en n.png by trial division than by using the Miller-Rabin test. Since the probability that a random integer 1 16 en n.png has a small prime divisor is relatively large it's better to tested for small divisors below a pre-determined bound 1 16 en B.png, before applying any probabilistic primality test. This can be done by dividing 1 16 en n.png by all the primes below 1 16 en B.png, or by computing GCD (greatest common divisors) of 1 16 en n.png and (pre-computed) products of several of the primes 1 16 en el B.png. [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(1 16 en k.png,1 16 en t.png).

RANDOM-SEARCH(1 16 en k.png,1 16 en t.png)
INPUT: an integer 1 16 en k.png and security parameter 1 16 en t.png.
OUTPUT: a random 1 16 en k.png-bit probable prime.
 1. Generate random odd 1 16 en k.png-bit integer 1 16 en n.png.
 2. Use trial division to determine whether 1 16 en n.png is divisible by any odd prime 1 16 en el B.png. 
    If it is then go to step 1.
 3. If MILLER-RABIN(1 16 en n.png,1 16 en t.png) outputs "prime" then return(1 16 en n.png). 
    Otherwise, go to step 1.

Back to table of contents

Strong primes generation

The RSA cryptosystem uses a modulus of the form 1 16 en n=pq.png, where 1 16 en p.png and 1 16 en q.png are distinct odd primes. Because factorization of 1 16 en n.png should be beyond computational reach, the primes 1 16 en p.png and 1 16 en q.png must be of sufficient big size. In practice, according to system specifications, 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 1 16 en p.png is said to be a strong prime if integers 1 16 en r.png, 1 16 en s.png and 1 16 en t.png exist such that the following three conditions are satisfied:

1) 1 16 en p-1.png has a large prime factor, denoted 1 16 en r.png;

2) 1 16 en p+1.png has a large prime factor, denoted 1 16 en s.png;

3) 1 16 en r-1.png has a large prime factor, denoted 1 16 en t.png.

In this definition a precise qualification of “large” depends on specific attacks that should be guarded against.

Let's consider Gordon’s algorithm for generating a strong prime.

1. Generate two large random primes 1 16 en s.png and 1 16 en t.png of roughly equal bitlength.
2. Select an integer 1 16 en i 0.png. 
3. Find the first prime in the set 1 16 en 2it+1, i= overline i 0, infty.png and denote it by 1 16 en r=2it+1.png.
4. Compute 1 16 en p 0=2(s r-2 mod r)s-1.png.
5. Select an integer 1 16 en j 0.png. 
6. Find the first prime in the set 1 16 en p 0+2jrs, j= overline j 0, infty.png and denote this prime by 1 16 en p=p 0+2jrs.png.
7. Return(1 16 en p.png).

Let's prove that the prime 1 16 en p.png returned by Gordon’s algorithm is indeed a strong prime:

1) according to Fermat’s theorem 1 16 en s r-1 equiv 1 (mod s).png (assuming 1 16 en r ne s.png), and hence 1 16 en p 0 equiv 1 (mod r).png and 1 16 en p 0 equiv -1 (mod r).png;

2) 1 16 en p-1=p 0+2jrs-1 equiv 0 (mod r).png, and hence 1 16 en p-1.png has the prime factor 1 16 en r.png;

3) 1 16 en p+1=p 0+2jrs+1 equiv 0 (mod s).png, and hence 1 16 en p+1.png has the prime factor 1 16 en s.png;

4) 1 16 en r-1=2it equiv 0 (mod t).png, and hence 1 16 en r-1.png has the prime factor 1 16 en t.png.

If the Miller-Rabin test is the primality test used in steps 1, 2, and 4, the expected time Gordon’s algorithm takes to find a strong prime is only about 19% more than the expected time takes to find a random prime.

Back to table of contents

NIST method for generating DSA primes

Some public-key schemes require primes satisfying various specific conditions. This subsection presents an algorithm for generating primes 1 16 en p.png and 1 16 en q.png according to NIST Digital Signature Algorithm, e.i. 1 16 en p.png and 1 16 en q.png satisfying the following three conditions:

1) 1 16 en q.png is a 160-bit prime;

2) 1 16 en p.png is a 1 16 en L.png-bit prime, where 1 16 en L=512+64l.png for 1 16 en l= overline 0,8.png;

3) 1 16 en p.png divides 1 16 en p-1.png.

In the following, 1 16 en H.png denotes the SHA-1 hash function which converts bitstrings of bitlength < Gus48.gif to 160-bit hash-codes. Where required, an integer 1 16 en x in 0,2 g).png whose binary representation is Gus50.gif should be converted to the g-bit sequence Gus51.gif, and vice versa.

Let's consider NIST method for generating DSA primes.

INPUT: an integer 1 16 en l .png, 1 16 en l in 0,8.png.
OUTPUT: a 160-bit prime 1 16 en q.png and an 1 16 en L.png-bit prime 1 16 en p.png, where 1 16 en L=512+64l.png and 1 16 en q (p-1).png.
1. Compute 1 16 en L=512+64l.png
2. Using long division of 1 16 en L-1.png by 160, find 1 16 en n.png, 1 16 en b .png such that 1 16 en L-1=160n+b.png, where 1 16 en b in 0,160).png.
3. Repeat the following:
 3.1 Choose a random seed 1 16 en s.png (not necessarily secret) of bitlength 1 16 en g ge 160.png.
 3.2 Compute 1 16 en U=H(s) oplus H((s+1) mod 2 g).png.
 3.3 Get 1 16 en q.png from 1 16 en U.png by setting to 1 the most significant and least significant bits of U.
 3.4 Test 1 16 en q.png for primality using MILLER-RABIN(1 16 en q.png,1 16 en t.png) for 1 16 en t ge 18.png, 
Until 1 16 en q.png is found to be a probable prime.
4. Set 1 16 en i leftarrow 0.png, 1 16 en j leftarrow 2.png.
5. While 1 16 en i 4096.png do the following:
 5.1 Set 1 16 en V k leftarrow H((s+j+k) mod 2 g).png for 1 16 en k= overline 0,n.png.
 5.2 Let Gus54.gif, where Gus55.gif.
 5.3 Compute 1 16 en c=X mod 2q.png and set 1 16 en p=X-(c-1).png.
 5.4 If 1 16 en p ge 2 L-1.png then do the following:
  5.4.1 Test 1 16 en p.png for primality using MILLER-RABIN(1 16 en p.png,1 16 en t.png) for 1 16 en t ge 5.png.
  5.4.2 If 1 16 en p.png is a probable prime then return(1 16 en q.png,1 16 en p.png).
 5.5 Set 1 16 en i leftarrow i+1.png, 1 16 en j leftarrow j+n+1.png
6. Go to step 2.

Back to table of contents

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 specified 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 1 16 en t=1.png.[S05]

Let 1 16 en n g 2.png be an odd integer. Suppose that 1 16 en n=1+2Rq.png where 1 16 en q.png is an odd prime and 1 16 en q g R.png. Then:

1) if there exists an integer a satisfying 1 16 en a n-1 equiv 1 (mod n).png and 1 16 en gcd(a 2R -1,n)=1.png, then 1 16 en n.png is prime;

2) if 1 16 en n.png is prime, the probability that a randomly selected base 1 16 en a in 1,n-1.png, satisfies 1 16 en a n-1 equiv 1 (mod n).png and 1 16 en gcd(a 2R -1,n)=1.png is 1 16 en frac q-1 q.png.

Maurer’s algorithm recursively generates an odd prime 1 16 en q.png, and then chooses random integers 1 16 en R .png, 1 16 en R l q.png, until 1 16 en n=1+2Rq.png can be proven prime for some base 1 16 en a.png.

PROVABLE PRIME(1 16 en k.png)
INPUT: a positive integer 1 16 en k.png.
OUTPUT: a 1 16 en k.png-bit prime number 1 16 en n.png.
1. If 1 16 en k l 21.png then repeatedly do the following:
 1.1 Select a random 1 16 en k.png-bit odd integer 1 16 en n.png.
 1.2 Use trial division by all primes less than 1 16 en sqrt n.png to determine whether 1 16 en n.png is prime.
 1.3 If 1 16 en n.png is prime then return(1 16 en n.png).
2. Set 1 16 en c leftarrow 0.1.png and 1 16 en m leftarrow 20.png.
3. Set 1 16 en B leftarrow c cdot k 2.png.
4. If 1 16 en k 2m.png then repeatedly do the following: 
 4.1 Select a random number 1 16 en s in 0;1.png.
 4.2 Set 1 16 en r leftarrow 2 s-1.png.
 4.3 If 1 16 en (k-rk) g m.png go to step 4.1.
   Otherwise set 1 16 en r leftarrow 0.5.png.
5. Compute 1 16 en q leftarrow.png PROVABLE_PRIME(1 16 en lfloor r cdot k rfloor+1.png).
6. Set 1 16 en I leftarrow lfloor frac 2 k-1 2q rfloor.png.
7. 1 16 en success leftarrow 0.png.
8. While (1 16 en success=0.png) do the following:
 8.1 Select a random integer 1 16 en R .png in the interval 1 16 en I+1,2I.png
 8.2 Set 1 16 en n leftarrow 2Rq+1.png.
 8.2 Use trial division to determine whether 1 16 en n.png is divisible by any prime number < 1 16 en B.png.
  If it is not then do the following:
   Select a random integer 1 16 en a.png in the interval 1 16 en a in (1,n-1).png.
   Compute 1 16 en b leftarrow a n-1 mod n.png.
   If 1 16 en b=1.png then do the following:
    Compute 1 16 en b leftarrow a 2R mod n.png and 1 16 en d leftarrow gcd(b-1,n).png.
    If 1 16 en d=1.png then 1 16 en success leftarrow 1.png.
9. Return(1 16 en n.png).

Back to table of contents

Irreducible polynomials

The polynomial 1 16 en f(x) in mathbb Z p x.png of degree 1 16 en m g 0.png is said to be irreducible over 1 16 en mathbb Z p.png if it cannot be written as a product of two polynomials in 1 16 en mathbb Z p x.png each having degree less than 1 16 en m.png. Such a polynomial 1 16 en f(x).png can be used to represent the elements of the finite field 1 16 en mathbb F p m.png as 1 16 en mathbb F p m=mathbb Z p x (f(x)).png, the set of all polynomials in 1 16 en mathbb Z p x.png of degree less than 1 16 en m.png where the addition and multiplication of polynomials is performed modulo 1 16 en f(x).png.

This subsection presents techniques for constructing irreducible polynomials over 1 16 en mathbb Z p.png, where 1 16 en p.png is a prime. The characteristic of two finite fields 1 16 en mathbb F 2 m.png are of particular interest for cryptographic applications because the arithmetic in these fields can be efficiently performed both in software and in hardware. For this reason, additional attention is given to the special case of irreducible polynomials over 1 16 en mathbb Z 2.png.

The polinomial1 16 en f(x) in mathbb Z p x.png is said to be monic polynomials in 1 16 en mathbb Z p.png if it's leading coefficient is 1.

If 1 16 en f(x) in mathbb Z p x.png is irreducible over 1 16 en mathbb Z p.png and 1 16 en a.png is a non-zero element in 1 16 en mathbb Z p.png, then their product 1 16 en a cdot f(x).png is also irreducible over 1 16 en mathbb Z p.png. [F10] It's suffices to restrict attention that if 1 16 en f(x).png is an irreducible polynomial, then its constant term must be non-zero. In particular, if 1 16 en f(x) in mathbb Z 2 x.png, then its constant term must be 1.

Let 1 16 en p.png be a prime and let 1 16 en k.png be a positive integer. Then:

1) The product of all monic irreducible polynomials in 1 16 en mathbb Z p x.png of degree dividing 1 16 en k.png is equal to 1 16 en x p k -x.png.

2) Let 1 16 en f(x).png be a polynomial of degree 1 16 en m.png in 1 16 en mathbb Z p x.png. Then 1 16 en f(x).png is irreducible over 1 16 en mathbb Z p.png if and only if 1 16 en gcd(f(x),x p i -x)=1, i= overline 1, lfloor frac m 2 rfloor.png.

Let's consider algorithm of testing a polynomial for irreducibility.

INPUT: a prime 1 16 en p.png and a monic polynomial 1 16 en f(x).png of degree 1 16 en m in mathbb Z p x.png.
OUTPUT: an answer to the question: "Is 1 16 en f(x).png irreducible over 1 16 en mathbb Z p.png?"
1. Set 1 16 en u(x) leftarrow x.png.
2. For 1 16 en i= overline 1, lfloor frac m 2 rfloor.png do the following:
 2.1 Compute 1 16 en u(x) leftarrow u(x) p mod f(x).png.
 2.2 Compute 1 16 en d(x) leftarrow gcd(f(x),u(x)-x).png.
 2.3 If 1 16 en d(x) ne 1.png then return("reducible").
3. return("irreducible").

Now let's consider an algorithm of generating a random monic irreducible polynomial over 1 16 en mathbb Z p.png, which is based on algorithm of testing a polynomial for irreducibility described above.

INPUT: a prime 1 16 en p.png and a positive integer 1 16 en m.png.
OUTPUT: a monic irreducible polynomial 1 16 en f(x).png of degree 1 16 en m.png in 1 16 en mathbb Z p x.png.
1. Repeat the following:
 1.1 Randomly select set of integers 1 16 en (a 0,a 1, dots ,a m-1).png where 1 16 en a i in 0,p-1 ,i= overline 0,m-1.png and 1 16 en a 0 ne 0.png. 
 1.2 Let 1 16 en f(x)=x m+a m-1 x m-1+ cdots+a 1x+a 0.png.
 1.3 Use algorithm of testing a polynomial for irreducibility to test whether 1 16 en f(x).pngis irreducible over 1 16 en mathbb Z p.png.
Until 1 16 en f(x).pngis irreducible.
2. Return(1 16 en f(x).png).

The algorithm of generating a random monic irreducible polynomial over 1 16 en mathbb Z p.png complexity is Gus82.gif operations in 1 16 en mathbb Z p.png.

Back to table of contents

Primitive polynomials

Polynomial 1 16 en f(x).png of degree 1 16 en m.png in 1 16 en mathbb Z p x.png is called primitive polynomial if 1 16 en x.png is a generator of 1 16 en mathbb F p m .png. Such polynomials can be used in generating of linear recurring sequences of maximal period.

Let 1 16 en p.png be a prime and let the distinct prime factors of 1 16 en p m-1.png be 1 16 en r 1,r 2, dots,r t.png. Then an irreducible polynomial 1 16 en f(x) in mathbb Z p x.png is primitive if and only if for each 1 16 en i= overline 1,t.png: 1 16 en x frac p m-1 r i not equiv 1 (mod f(x)).png.

So if 1 16 en f(x) in mathbb Z p x.png be an irreducible polynomial of degree 1 16 en m.png and the factorization of the integer 1 16 en p m-1.png is known, then there is an efficient algorithm for testing whether or not 1 16 en f(x).png is a primitive polynomial. If the factorization of 1 16 en p m-1.png is unknown, there is no efficient algorithm known for performing this test.

Let's consider an algorithm for testing whether an irreducible polynomial is primitive or not.

INPUT: a prime 1 16 en p.png, 
       a positive integer 1 16 en m.png, 
       the distinct prime factors 1 16 en r 1,r 2, dots,r t.png of 1 16 en p m-1.png, 
       a monic irreducible polynomial 1 16 en f(x).png of degree 1 16 en m.png in 1 16 en mathbb Z p x.png.
OUTPUT: an answer to the question: "Is 1 16 en f(x).png a primitive polynomial?"
1. For 1 16 en i= overline 1,t.png do the following:
 1.1 Set 1 16 en l(x) leftarrow x frac p m-1 r i (mod f(x)).png.
 1.2 If 1 16 en l(x)=1.png then return("not primitive").
2. Return("primitive")

There are precisely 1 16 en frac varphi(p m-1) m.png monic primitive polynomials of degree 1 16 en m.png in 1 16 en mathbb Z p x.png, where 1 16 en varphi(n).png is the Euler phi function. Since the number of monic irreducible polynomials of degree 1 16 en m.png in 1 16 en mathbb Z p x.png is roughly 1 16 en frac p m m.png, it follows that the probability of a random monic irreducible polynomial of degree 1 16 en m.png in 1 16 en mathbb Z p x.png being primitive is approximately 1 16 en frac varphi(p m-1) p m.png

Back to table of contents

Generators and elements of high order

Let 1 16 en G.png is a (multiplicative) finite group. The least positive integer 1 16 en t.png such that 1 16 en a t=1.png is called an order of an element 1 16 en a in G.png. Group 1 16 en G.png is said to be cyclic if there are 1 16 en n.png elements in 1 16 en G.png and 1 16 en a in G.png is an element of order 1 16 en n.png. In such case 1 16 en a in G.png is called a generator or a primitive element of 1 16 en G.png.

Of special interest for cryptographic applications are the multiplicative group 1 16 en mathbb Z p .png of the integers modulo a prime 1 16 en p.png, and the multiplicative group 1 16 en mathbb F 2 m .png of the finite field 1 16 en mathbb F 2 m.png of characteristic two; these groups are cyclic. Also of interest is the group 1 16 en mathbb Z n .png, where 1 16 en n.png is the product of two distinct odd primes.

Let's consider an algorithm of an efficient method for determining the order of a group element, given the prime factorization of the group order 1 16 en p.png.

INPUT: a (multiplicative) finite group 1 16 en G.png of order 1 16 en p.png, 
       an element 1 16 en a in G.png,
       the prime factorization 1 16 en n=p 1 e 1 p 2 e 2 cdots p k e k.png.
OUTPUT: the ordert of 1 16 en a.png.
1. Set 1 16 en t leftarrow n.png.
2. For 1 16 en i= overline 1,k.png do the following:
 2.1 Set 1 16 en t leftarrow frac t p i e i.png.
 2.2 Compute 1 16 en a 1 leftarrow a t.png.
 2.3 While 1 16 en a 1 ne 1.png do the following: 
  2.3.1 Compute 1 16 en a 1 leftarrow a 1 p i.png
  2.3.2 Set 1 16 en t leftarrow t cdot p i.png.
3. Return(1 16 en t.png).

Suppose now that 1 16 en G.png is a cyclic group of order 1 16 en n.png. Then for any divisor 1 16 en d.png of 1 16 en n.png the number of elements of order 1 16 en d.png in 1 16 en G.png is exactly 1 16 en varphi(d).png, where 1 16 en varphi.png is the Euler phi function. In particular, 1 16 en G.png has exactly 1 16 en varphi(n).png generators, and hence the probability of a random element in 1 16 en G.png being a generator is 1 16 en frac varphi(n) n.png. This suggests the following efficient randomized algorithm for finding a generator of a cyclic group.

INPUT: a cyclic group 1 16 en G.png of order 1 16 en n.png, and the prime factorization 1 16 en n=p 1 e 1 p 2 e 2 cdots p k e k.png.
OUTPUT: a generator of 1 16 en G.png.
1. Choose a random element in 1 16 en G.png.
2. For 1 16 en i= overline 1,k.png do the following:
 2.1 Compute 1 16 en b leftarrow a frac alpha n p i.png.
 2.2 If 1 16 en b=1.png then go to step 1.
3. Return(1 16 en alpha.png).

If 1 16 en n=pq.png, where 1 16 en p.png and 1 16 en q.png are distinct odd primes, then is a non-cyclic group 1 16 en mathbb Z n .png of order 1 16 en varphi(n)=(p-1)(q-1).png. The maximum order of an element in 1 16 en mathbb Z n .png is 1 16 en lcm(p-1,q-1).png.

Let's consider an algorithm for generating such an element of maximum order in 1 16 en mathbb Z n .png.

INPUT: two distinct odd primes 1 16 en p.png and 1 16 en q.png, 
       the factorizations of 1 16 en p-1.png and 1 16 en q-1.png.
OUTPUT: an element of maximum order 1 16 en lcm(p-1,q-1).png in 1 16 en mathbb Z n .png, where 1 16 en n=pq.png.
1. Fnd a generator 1 16 en a.png of 1 16 en mathbb Z p.png.
2. Fnd a generator 1 16 en b .png of 1 16 en mathbb Z q.png.
3. Use Gauss’s algorithm to find an integer 1 16 en alpha in 1,n-1.png satisfying 1 16 en alpha equiv a (mod p).png and 1 16 en alpha equiv b (mod q).png.
4. Return(1 16 en alpha.png).

Back to table of contents

Glossary

Back to table of contents

Bibliography

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

Gusev P., Lovyannikov A.

Back