Abstract: The cryptographic properties of 3^rd-order linear feedback shift register (LFSR) sequences over GF(p) are investigated. A fast computational algorithm for evaluating the k^th term of a characteristic sequence of order 3 is presented. Based on these properties, a new public-key distribution scheme and a RSA-type encryption algorithm are proposed. Their security, implementation, information rate, and computational cost for the new schemes are discussed.

Index words: Cubic finite field extension, linear feedback shift register sequence, characteristic sequence, public-key exchange scheme, RSA-type encryption.

Abstract: The cryptographic properties of 3^rd-order linear feedback shift register (LFSR) sequences over GF(p) are investigated. A fast computational algorithm for evaluating the k^th term of a characteristic sequence of order 3 is presented. Based on these properties, a new public-key distribution scheme and a RSA-type encryption algorithm are proposed. Their security, implementation, information rate, and computational cost for the new schemes are discussed.

Index words: Cubic finite field extension, linear feedback shift register sequence, characteristic sequence, public-key exchange scheme, RSA-type encryption.

With the rapid development of Internet applications, information security in today’s world is more important than that in any previous era. Designing cryptosystems that meet requirements of communication bandwidth, information rate, computational speed, and various security strategies, has become a very challenging task for researchers.

In the most widely used modern cryptosystems, such as the RSA [18], the Diffie-Hellman public-key distribution scheme [3], the ElGamal cryptosystem [5] and DSS [16], increasing the size of the modulus is necessary in order to strengthen their security.

From the point of the linear feedback shift register (LFSR) sequences, the exponential function which used in the RSA encryption, the Diffie-Hellman (DH) public-key exchange scheme [3], and the ElGamal digital signature scheme is a 1^st-order LFSR sequence over GF(p) or Z_n, where n is a product of two prime numbers. In the literature, there is another family of public-key cryptosystems similar to RSA, DH, and ElGamal public-key cryptosystems, which are called the Dickson polynomial scheme [13, 14, 15] or LUC [20, 21], respectively. The mathematical function used in this family of the public-key cryptosystems is the 2^nd-order LFSR sequence over GF(p) or Z_n with a special initial state. This kind of LFSR sequences are coset constant [8]. We will give their definition in Section II. (Note: throughout of this paper, we will use the term LFSR sequences over GF(p) or Z_n instead of linear recurring sequences over GF(p) or Z_n, since the term of initial state is related to a LFSR.)

In this paper, we will explore to construct public-key cryptosystems by using 3^rd-order LFSR sequences over GF(p) or Z_n. First, we will investigate the cryptographic properties of 3^rd-order LFSR sequences and propose a fast computational algorithm to evaluate the k^th term of a 3^rd-order characteristic sequence. Based on these properties, we will construct two public-key cryptographic algorithms. One is a public-key distribution scheme that can reduce the size of the modulus while speeding up the computation. The security is based on the difficulty of solving the discrete logarithm in GF(p³). Another one is a RSA-type encryption algorithm whose security is based on the difficulty of factoring a large composite integer. We will also discuss their security, implementation, information rate, and computational cost.

For the theory of LFSR sequences, the reader is refereed to [8, 12], and for the fundamental theory of finite fields, see [12].

Let F = GF(p), where p is a prime and

, (1)

be a polynomial over F. A sequence is said to be a 3^rd-order LFSR sequence with a characteristic polynomial f(x) if the elements of s satisfy

, k ³ 3. (2)

If s has the initial state: , and , then is called the characteristic sequence generated by f(x). We denote s_k as or s_k(f), and s as s(a, b) or s(f).

Assume that are all three roots of f(x) in the splitting field of f(x) over F. According to Newton's formula, the elements of s can be represented by the symmetric k^th power sum of the roots as follows

, k = 0, 1, …. (3)

Let us denote the period of f(x) as per(f). Notice that if f(x) is irreducible over F, then the period of s(f) is equal to per(f).

Lemma 1. Let be a polynomial over F, be three roots of f(x) in the splitting field of f(x) over F, and s be the characteristic sequence generated by f(x). Let .

1. , where .
2. If f(x) is irreducible over F, then f(x) and f_k(x) have the same period if and only if (per(f), k) = 1.
3. If (per(f), k) = 1, then f(x) is irreducible over F if and only if f_k(x) is irreducible over F.

Proof. (i). It follows from Newton's formula of equation (3). (ii). If f(x) is irreducible over F , then the minimal polynomial of over F is f_k(x) and per(f_k(x)) = per(f)/(per(f), k). So, per(f_k(x)) = per(f) if and only if (per(f), k) = 1. (iii). It follows from (ii).

Remark. Let . Then is the reciprocal polynomial of f(x) and {s_-k(a,b)} is the characteristic sequence over F generated by . We also call {s_-k(a,b)} the reciprocal sequence of {s_k(a,b)}.

Lemma 2. Let be a polynomial over F, and let s be the characteristic sequence generated by f(x). Then for all positive integers k and e,

. (5)

Proof. From Lemma 1,

= . (6)

Thus

= = = .

Q.E.D.

Note. If we consider a and b as variables in F and k as a fixed integer, then s_k(a,b) and s_-k(a,b) are Waring polynomials. From Theorem 7.46 in [12] , we have the following fact.

Fact 1. Let k be a fixed positive integer. If k satisfies (k, pⁱ – 1) = 1, i = 1, 2, 3, then for any u, v Î F, the system of equations:

and

has a unique solution (a, b) Î F´ F. In other words, s_k(a,b) and s_-k(a,b) are orthogonal in F in variables a and b.

We denote that Q = . A positive integer r is called a coset leader modulo Q if r is the smallest integer in the set {tpⁱ mod Q | i = 0, 1, 2}, where t is a positive integer.

Theorem 1. Let be an irreducible polynomial over F of the period Q = and be the characteristic sequence generated by f(x). Let k and k’ be different coset leaders modulo Q, and both k and k’ are relatively prime to Q. Then

.

Proof. If , then

= .

Thus f_k(x) also has , , as its roots. From Lemma 1, f_k(x) is irreducible over F. Therefore, and are conjugate of each other. In other word, there exists an integer t, 0 £ t £ 2, such that

(mod Q).

This contradicts with the fact that k and k¢ are different coset leaders modulo Q.

Q.E.D.

Remark. Lemma 2 and Theorem 1 will play as key roles in constructing a public-key distribution scheme, since the former guarantees the commutative property and the later provides one-to-one correspondence between the private key space and the public key space. Fact 1, together with Lemma 2, will be used to construct a RSA-type encryption scheme.

In reference [7], there is an algorithm to calculate the k^th term of any linear recurring sequences. Here we will provide a much more efficient algorithm to calculate the k^th term of a 3^rd-order characteristic sequence.

Lemma 3. Let be the 3^rd-order reciprocal characteristic sequence over F with the characteristic polynomial f(x), defined by (1), and , its reciprocal sequence. Then for any positive integers n and m,

1. , and
2. ,

Proof. From (2), we have

, and

.

Notice that . Then

= =

which gives (i). The same argument can be applied to (ii).

Q.E.D.

Let be the binary representation of k, and , . So, . From Lemma 3, the recurrence can be described by the following formulae:

For = 0,

, (7)

, and (8)

. (9)

For = 1,

Since and are symmetric in (7) - (12) and the probability that k_j equals 0 or 1 is 1 / 2, therefore we obtain the following result.

Theorem 2. With the same f(x), and as in Lemma 3. Using (7) - (12) to calculate a pair of the kth terms s_k and s_-k needs 9logk modulo p multiplications on average.

Note. This method is much more efficient than the algorithm using modulo polynomial [7]. The algorithm provided in [7] requires O(m (n)logk) arithmetic operations to calculate the k^th term of a LFSR sequence of order n over F where m (n) is the total number of arithmetic operations required to multiply two polynomials of degree n - 1. In case of n = 3, m (3) is the total number of multiplications modulo p required to multiply two polynomials of degree 2 over F (=GF(p)) and reduce it by modulo f(x). Notice that multiplying two polynomials of degree 2 over F without reduction by modulo f(x) already requires 9 multiplications modulo p. So, by using the algorithm in [7] to calculate the k^th term s_k requires at least 9logk multiplications modulo p. Consequently, the total computational cost for calculating a pair of the k^th term s_k and s_-k needs at least 18logk multiplications modulo p.

In this section, we will present a public-key distribution (GH-PKD) scheme that is constructed by a pair of 3^rd-order characteristic sequences and discuss its security.

• System public parameters: p is a prime number, and is an irreducible polynomial over GF(p) with the period Q = .
• User Alice ¾ selects e that satisfies and gcd(e, Q)=1 as her private key. She then computes as her public key from the system public key p and .
• User Bob ¾ selects r that satisfies that and gcd(r, Q) = 1 as his private key. He then computes as his public key from the system public key p and

Alice Bob

computing: computing:

and and

According to Lemma 2,

= = , and = = .

Namely, their common key is (,).

Example. Let p = 11, and is an irreducible polynomial over GF(11) of period 133 = 7´ 19.

Alice: Selects e = 9 as her private key. Her public key is = (10, 6).

Bob: Selects r = 13 as private key. His public key is = (7, 1).

Key Distribution Phase:

Remark.

1. In each key exchange session, the computational cost for each user is 9logp modulo p multiplications on average.

The security for GH key distribution scheme is based on the difficulty of solving the discrete logarithm in GF(p³). If an attacker tries to compute Alice’s private key e from her public key , a polynomial can be formed. Since is irreducible over F, according to Lemma 1, is also irreducible over F. Assume that a and b are the roots of f(x) and in the extension GF(p³) of F, respectively. They then can be derived by solving roots of and in GF(p³). Then b = a ^e. As a result, once a and b are known, solving the exponent e is equivalent to solving the discrete logarithm in GF(p³). According to [1, 2, 6, 9, 11], solving the discrete logarithm in GF(p³) is much harder than solving discrete logarithm in the GF(p) for the same p.

In this section, we will propose a RSA-type public-key cryptosystem by using a pair of 3^rd-order characteristic sequences over Z_n, which is an integer ring modulo n.

A. A RSA-type Encryption Algrithm

1. Public keys: e and n, where n = pq, p and q are primes, and gcd(e, pⁱ – 1) = 1, i = 2, 3.
2. Private keys d_i, 1 £ i £ 9, where d_i’s are given by Table 3.
3. Enciphering: For a message m = (m₁, m₂) where 0 < m₁, m₂ < n, the sender computes c₁ = s_e(m₁, m₂) and c₂ = s_-e(m₁, m₂). The ciphertext c = (c₁, c₂).
4. Deciphering: First, the receiver computes three functions (15)-(17) of the ciphers c₁, c₂ in order to choose a proper decryption key d, in the set { d_i,1 £ i £ 9 } in Table. Then he computes m₁ = s_d(c₁, c₂) and m₂ = s_-d(c₁, c₂) using the selected key d.

is a bijective map from the message space to the ciphertext space.

Next we will show how to construct decryption keys. For a 3^rd-order characteristic sequence s over F = GF(p) generated by , its period, per(s), may be one of three cases as listed below:

Case 1. f(x) is reducible over F Û per(s) | p – 1.

Case 3. f(x) is irreduclible over F Û per(s) | p² + p + 1.

According to the method for solving a cubic equation in a finite field in [17], substituting into f(x), then

, (13)

where

and . (14)

The discriminate of the cubic (13) is defined as

. (15)

Let x Î {p, q},

(16)

where , and

, the Legendre symbol of an integer i with respect to the prime x. (17)

Now we are in a position to give a definition for a logic function , which is related to the ciphertext ( c₁, c₂), where j Î {1, 2, 3} and x Î {p, q}.

G (3, x) is true Û D ( c₁, c₂) (mod x) ¹ 0, = 1 and (mod x) ¹ 1.

Û Case 3

We denote , and . From Lemma 1, two polynomials and have the same period. So the receiver can select a proper deciphering key based on the polynomial constructed by the ciphertext (c₁, c₂). The following Table gives the construction of these deciphering keys.

It is clear that the security of the scheme is based on the difficulty of factoring a large composite integer.

As the RSA public-key system, we can choose a small e such that the computational cost for computing the e^th terms of the 3^rd-order characteristic sequence with f(x) = and its reciprocal polynomial is low. For example, by taking e = 5, we compute

So, c₁ = s₅ . Similarly,

We get c₂ = s_-5 . Totally, we only need 10 modulo n multiplications for enciphering a 2logn-bit message. For deciphering process, first we need to decide a proper deciphering key d, i.e., we need to compute three functions. D ( c₁, c₂) (mod x) requires 8 modulo n multiplications. For and (mod x), each of the last two functions requires 1.5logp modulo p multiplications and 1.5logq modulo q multiplications, respectively. Second, we need to compute the d^th terms the 3^rd-order characteristic sequence with and its reciprocal polynomial, which needs 9logn modulo n multiplications on average. Therefore, the total computational cost in the deciphering process is 12logn modulo n multiplications on average.

As we have shown, we can conclude that the proposed public-key distribution scheme (GH-PKD) and the RSA-type encryption scheme are practical efficient public-key cryptosystems. Especially, GH-PKD is successful in reducing the size of the modulus while speeding up the computation. Note that from current literatures [19, 22, 23], only a few of public-key cryptosystems have been put into practical use.

The method presented here can be leading to construct public-key cryptosystems by using n^th-order characteristic sequences over GF(p) of any degree n > 3.

The authors wish to thank the referees for their valuable comments and suggestions.

1. L.M. Adleman and J. DeMarrais, "A subexponential algorithm for descrete logarithms over all finite fields," Proceedings Crypto'93, Lecture Notes in Computer Science, No. 773, 1994, pp.147-158.
2. L.M. Adleman and M.A. Huang, "Function field sieve method for discrete logarithms over finite fields, " preprint, December 1997.
1. W. Diffie and M.E. Hellman, "New directions in cryptography," IEEE Trans. on Inform. Theory, vol. IT-22, November 1976, pp.644-654.
1. P. Donnelly and G. Grimmett, "On the asymptotic distribution of large prime factors," J. London Math. Soc. (2), 47 (1993), pp. 395-404.
1. T. ElGamal, "A public key cryptosystem and a signature scheme based on discrete logarithms," IEEE Trans. on Inform. Theory, vol. IT- 31, no. 4, July 1985, pp.469-472.
1. T. ElGamal, "A subexponential-time algorithm for computing discrete logarithms over GF(p²), IEEE Trans. on Inform. Theory, vol. IT-32, 1985.
1. C.M. Fiduccia, " An efficient formula for linear recurrences," SIAM J. Comput. 14, 1985, pp. 106-112.
1. S.W. Golomb, Shift Register Sequences, Laguna Hills, CA: Aegean Park Press, 1982.
1. D. Gordon, "Discrete logarithms in GF(p) suing the number field sieve," SIAM J. Disc. Math. 6(1993), pp. 124-138.
1. D.E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, Addison-Wesley Publishing Co., MA, 1969.
1. A.K. Lenstra and H.W. Lenstra, Jr. (eds), The Development of the Number Field Sieve, Lecture Notes in Math. 1554, Springer-Verlag, Berlin, 1993.
1. R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, Volume 20, Addison-Wesley, 1983.
2. R. Lidl, G.L. Mullen and G. Turnwald, Dickson Polynomials, Pitman Monographs and Surveys in Pure and Applied Mathematics 65, John Wiley & Sons, Inc., 1993.
3. W.B. MŸ ller and W. Nš bauer, "Cryptanalysis of the Dickson-scheme, " Proceedings of Eurocrypt'85, Springer-Verlag, pp. 71-76.
4. W. Nš bauer, "Cryptanalysis of a public-key cryptosystem based on Dickson polynomials, " Mathematica Slovaca 38 (1989), pp. 309-323.
1. NIST, "A proposed federal information processing standard for digital signature standard (DSS)," Federal Register 56 (1991), 42980-42982.
1. L. Rédei, Algebra, Geest & Portig, Leipzig, 1959; Pergamon Press, London 1967.
1. R.L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public key cryptosystems," ACM, vol. 21, no. 2, Feb. 1978, pp.120-126.
1. B. Schneier, Applied Cryptography, John Wiley & Sons, Inc., Second edition, 1996.
2. P. Smith, "LUC public-key encryption, " Dr. Dobb's Journal, pp. 44-49, January 1993.
3. P. Smith and C. Skinner, "A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms," Proceedings of Asiacrypt'94, pp. 298-306, Nov. 1994.
1. D.R. Stison, Cryptography, Theory and Practice, CRC Press, Inc., 1995.
1. W. Stallings, Network and Internetwork Security Principles and Practice, IEEE Press, Inc., New York, 1995.