Cryptography using Chebyshev polynomials

G. J. Fee and M. B. Monagan Centre for Experimental and Constructive Mathematics, Simon Fraser University, Burnaby, Canada, V5A 1S6

         gjfee@cecm.sfu.ca and monagan@cecm.sfu.ca

Abstract

We consider replacing the monomial x^{n} with the Chebyshev polynomial T_{n}(x), in the Diffie-Hellman and RSA cryptography algorithms. We show that we can generalize the binary powering algorithm, to compute Chebyshev polynomials, and that the inverse problem of computing the degree n, the discrete log problem for T_{n}(x) mod p, is as hard as that for x^{n} mod p.

1 Introduction

If Alice wants to send a secret message to Bob, using a conventional secret key cryptographic algorithm, such as the DES, (Data Encryption Standard) [1], then Alice and Bob must first agree on a common secret key. If Alice emails Bob the secret key, then a wiretapper could copy the key and decrypt the secret message that Alice sent to Bob. How can Alice and Bob agree on their common secret key? The Diffie-Hellman [1] key agreement protocol solves this problem.

The Diffie-Hellman Key Agreement Algorithm

1. Alice creates positive integers g and p such that g < p.

2. Alice chooses a secret integer exponent m such that 0 < m < p.

3. Alice calculates a = g^{m} mod p.

4. Alice emails p, g, and a to Bob.

5. After Bob receives Alice’s email he chooses a secret integer exponent n such that 0 < n < p.

6. Bob calculates b = g^{n} mod p.

7. Bob emails b to Alice.

8. Alice computes the secret key k = c where c = b^{m} mod p.

9. Bob computes the secret key k = d where d = a^{n} mod p.

The common secret key k is c for Alice and d for Bob. Now c = d since (g^{n})^{m} = g^{nm} = (g^{m})^{n} mod p . In the above algorithm, one uses binary powering modulo p to quickly compute the powers g^{m}, g^{n}, b^{m}, and a^{n} modulo p. Since the base and exponent are bounded by p, one can compute the powers in O(log p) multiplications and divisions, with numbers that contain at most O(log p) bits in their binary representation. Using classical algorithms we can multiply or divide in O(log(p)^{2}) bit operations. This yields a time complexity of O(log(p)^{3}) bit operations to compute g^{m} mod p. This is polynomial time in the length of the input.

We may assume that an eavesdropper knows p, g, a, and b, and needs to compute the secret key k which is either c or d in the above protocol. One method for doing this is to solve the discrete log problem a = g^{m} mod p for the secret exponent m, and then compute c = b^{m} mod p, just as Alice would do in step 8. Since known methods for solving the discrete log problem have a much larger time complexity it is computationally infeasible to solve the discrete log problem for the secret exponent. For example, the Pollard ρ algorithm, see [1], the time complexity is O(\sqrt{p}) = O(exp(\frac{1}{2} log p)), which is of exponential time in the length of the inputs, This is the reason the above algorithm hinders eavesdroppers from discovering the secret key.

For maximum security it is recommended in [1] that p should be a safeprime, that is (p − 1)/2 should also be a prime, and secondly, g should be a primitive root of p so that the period of the sequence of powers of g is maximal. In current practice p is chosen to be 100 decimal digits or more in length.

The generalized Diffie-Hellman Key Agreement Algorithm

The above algorithm has been generalized from the multiplicative group of the integers modulo p, a prime, to any finite group, such as the group of points on an elliptic curve under addition [1]. Alice just chooses a group G and a random element g from the group. Since the binary powering algorithm may be used in any group, both Alice and Bob can quickly compute a common secret group element. For this to be useful, we would also require that the known algorithms for the discrete log problem be exponential time in the length of the inputs. One simple example where this is not true, is in the additive group of integers modulo p, where binary powering becomes multiplication modulo p, and the discrete log problem is solved by doing one division modulo p.

In this paper we replace the polynomial x^{n} that appears in the Diffie-Hellman key agreement protocol with the Chebyshev polynomial T_{n}(x) and show also how to use this in the RSA algorithm. In section 3 we show how to compute T_{n}(g) mod p rapidly. In section 4 we study properties of the sequence of values of T_{n}(x) mod p and in section 5 we show that the discrete log problem for Chebyshev polynomials can be mapped into the classical discrete log problem. Finally, in section 6, we give an RSA encryption algorithm based on Chebyshev polynomials.

2 Diffie-Hellman Key Agreement with Chebyshev polynomials

We generalize the Diffie-Hellman key agreement protocol as follows. Instead of generalizing the basic rule of exponents (g^{m})^{n} = g^{mn} = (g^{n})^{n} to an arbitrary group, we consider it as a polynomial identity (x^{m})^{n} = x^{mn} = (x^{n})^{m}, where x is an indeterminate. We ask the question if any other classes of polynomials could satisfy such a commutative composition identity, besides the pure monomial x^{n}. A similar identity holds for the Chebyshev polynomials:

T_{m}(T_{n}(x)) = T_{mn}(x) = T_{n}(T_{m}(x)).

We see that this holds by using the classical formula [2] 22.3.15 on page 776, which may be rewritten as T_{n}(x) = cos(n arccos(n)) which is valid for all real x in the interval [−1, 1] . Using this formula we have

T_{m}(T_{n}(x)) = cos(m arccos(cos(n arccos x)))
= cos(mn arccos x)
= cos(nm arccos x)
= cos(n arccos(cos(m arccos x)))
= T_{n}(T_{m}(x))

For x > 1 we can use the formula T_{n}(x) = cosh(n cosh^{−1} x) to verify the identity. Up to a linear transformation the pure monomial x^{n} and the Chebyshev polynomials are the only classes of polynomials satisfying the commutative composition relation P_{n}(P_{m}(x)) = P_{m}(P_{n}(x)) where P_{n}(x) is a polynomial of degree n. See pages 33-34 exercise E.5 in reference [3] for a proof. Now we present the Diffie-Hellman Key Agreement algorithm using Chebyshev polynomials:

1. Alice creates positive integers g and p such that g < p.

2. Alice chooses a secret integer degree m such that 0 < m < p.

3. Alice calculates a = T_{m}(g) mod p.

4. Alice emails p,g, and a to Bob.

5. After Bob receives Alice’s email he chooses a secret integer degree n such that 0 < n < p.

6. Bob calculates b = T_{n}(g) mod p.

7. Bob emails b to Alice.

8. Alice computes the secret key k = c where c = T_{m}(b) mod p.

9. Bob computes the secret key k = d where d = T_{n}(a) mod p.

The integer c for Alice and the integer d for Bob is the common secret key k since both of them have computed T_{mn}(g) mod p.

Example 1: Here is a simple example of the above algorithm where m = 2 and n = 3 are chosen hence we need to evaluate T_{2}(x) = 2x^{2} − 1, T_{3}(x) = 4x^{3} − 3x, and T_{6}(x) = 32x^{6} − 48x^{4} + 18x^{2} − 1.

1. Alice chooses p = 89 and g = 7.

2. Alice chooses m = 2.

3. Alice computes a = T_{2}(7) = 2(7^{2}) − 1 mod 89 = 97 mod 89 = 8.

4. Alice emails Bob p = 89, g = 7, and a = 8.

5. Bob chooses n = 3.

6. Bob computes b = T_{3}(7) = 4(7^{3}) − 3(7) mod 89 = 1351 mod 89 = 16.

7. Bob emails b = 16 to Alice.

8. Alice computes c = T_{2}(16) = 2(16^{2}) − 1 mod 89 = 511 mod 89 = 66.

9. Bob computes d = T_{3}(8) = 4(8^{3}) − 3(8) mod 89 = 2024 mod 89 = 66.

Now both Alice and Bob have generated the same secret key k = 66 which is also T_{6}(7) mod 89 = 3650401 mod 89 = 66. To make the above algorithm practical we require a fast algorithm for computing T_{n}(x) mod p, where both n and p are large. We look at methods for doing this in the next section. For maximum security p should be a safeprime and g should be such that the period is large. We study this in the following section. Note that for p a prime greater than three, five known cases where the period is small are when g is one of 0, 1, (p − 1)/2, (p + 1)/2 and p − 1, with periods of length 4, 1, 3, 6 and 2 respectively.

3 Binary powering for Chebyshev polynomials

We would like to generalize the binary powering algorithm, so that we could quickly compute the values of the Chebyshev polynomials modulo p. First we rewrite the recurrence relation [2] formula 22.7.4 from page 782, for the Chebyshev polynomials T_{n+1}(x) = 2xT_{n}(x) − T_{n−1}(x) as the matrix equation:

[ \begin{matrix}T_{n}(x) \\ T_{n+1}(x) \end{matrix} ] = [ \begin{matrix}0 & 1 \\ −1 & 2 x \end{matrix} ] [ \begin{matrix}T_{n−1}(x) \\ T_{n}(x) \end{matrix} ]

The above equation with n diminished by 1 becomes:

[ \begin{matrix}T_{n−1}(x) \\ T_{n}(x) \end{matrix} ] = [ \begin{matrix}0 & 1 \\ −1 & 2 x \end{matrix} ] [ \begin{matrix}T_{n−2}(x) \\ T_{n−1}(x) \end{matrix} ]

Combining the above equations yields:

[ \begin{matrix}T_{n}(x) \\ T_{n+1}(x) \end{matrix} ] = [ \begin{matrix}0 & 1 \\ −1 & 2 x \end{matrix} ]^{2} [ \begin{matrix}T_{n−1}(x) \\ T_{n}(x) \end{matrix} ]

We continue to replace the vector on the right side until the index is 0. This yields:

[ \begin{matrix}T_{n}(x) \\ T_{n+1}(x) \end{matrix} ] = [ \begin{matrix}0 & 1 \\ −1 & 2 x \end{matrix} ]^{n} [ \begin{matrix}T_{0}(x) \\ T_{1}(x) \end{matrix} ]

Since T_{0}(x) = 1 and T_{1}(x) = x the vector on the right is just the transpose of the row vector [1, x]. Now we just need to compute the above using matrix binary powering, and then perform one matrix-vector product, and then extract the first element of the resulting vector and we obtain T_{n}(x). By using the classical matrix-matrix multiplication algorithm, we can do one matrix multiplication with the individual elements reduced modulo p using 8 integer multiplications, 4 integer additions, and 4 integer remainder operations. Since the exponent n < p we would use O(log(p)) matrix multiplications modulo p to compute the value of the n^{th} Chebyshev polynomial modulo p . This would be about 4 to 8 times slower than the usual Diffie-Hellman algorithm, depending on the relative cost of a large integer division compared to a large integer multiplication.

We can improve the above binary matrix powering algorithm by computing λ^{n} modulo the characteristic polynomial of the above recurrence relation matrix. Since the determinant is 1 and the trace is 2x the characteristic polynomial is λ^{2} − 2xλ + 1. The Cayley-Hamilton theorem says that a matrix satisfies its own characteristic polynomial, so instead of powering a matrix, we just compute the indeterminate λ^{n} modulo the characteristic polynomial using binary powering. A basic step in the above algorithm would be multiplying 2 linear polynomials and finding the remainder from the division by the characteristic polynomial and then reducing the coefficients modulo p. We can multiply 2 linear polynomials using 4 integer multiplications of single length numbers and 1 integer addition of double length numbers, where a single length number is one that is less than p and a double length number is one that is less than p^{2}. Then the remainder can be calculated by doing a substitution for λ^{2} , which would cost another multiplication and 2 additions. This other multiplication would be a product of a double length number times a single length number, so we may want to reduce the double length number, by performing a division by p before doing this other multiplication. Whether we should do this reduction modulo p would depend on the relative cost of our division algorithm versus our multiplication algorithm. In practice we would implement both versions, and time them, then pick the faster version. Then we would reduce the 2 coefficients modulo p at a cost of 2 integer divisions. If we did not do the intermediate reduction, then one of our divisions, would be a triple length number, divided by a single length number. We have found the above algorithm to be slightly faster than the other matrix powering algorithm.

Timings

We implemented the classical binary powering algorithm, computing g^{n} mod p, the Chebyshev matrix powering algorithm, computing T_{n}(g) mod p, and the Chebyshev characteristic polynomial algorithm, computing T_{n}(g) mod p, where g = 7^{233}, n = 13^{178} and p = 97^{100} + 528. The calculations were performed in Maple 6 [4], on a 180 Mhz Silicon Graphics computer.

algorithm time in seconds
binary powering  .686
matrix powering  4.527
characteristic polynomial  3.197

The Chebyshev matrix powering algorithm was 6.60 times slower than the classical binary powering algorithm, and the other Chebyshev algorithm was 4.66 times slower.

4 Properties of Chebyshev polynomial sequences modulo a prime

To understand the difficulty of inverting x = T_{n}(g) mod p, where n is unknown, we generate some experimental data. By choosing a small p, we could compute the sequence T_{n}(x) mod p for n = 0, 1, 2, ... until we discovered the period of the sequence. When we try this we discover that the period is at most p + 1 for any given input argument x = 0, 1, 2, ..., p − 1. For example when x = 3 and p = 11 we find that the sequence T_{n}(3) mod 11 for n = 0, 1, 2, ..., 23 is:

1, 3, 6, 0, 5, 8, 10, 8, 5, 0, 6, 3, 1, 3, 6, 0, 5, 8, 10, 8, 5, 0, 6, 3

which is of period 12. By doing this for each x = 0, 1, 2, ..., 10 we find the following sequences:

x sequence
0 1, 0, 10, 0, 1, 0, 10, 0, 1, 0, 10, 0
1 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
2 1, 2, 7, 4, 9, 10, 9, 4, 7, 2, 1, 2
3 1, 3, 6, 0, 5, 8, 10, 8, 5, 0, 6, 3
4 1, 4, 9, 2, 7, 10, 7, 2, 9, 4, 1, 4
5 1, 5, 5, 1, 5, 5, 1, 5, 5, 1, 5, 5
6 1, 6, 5, 10, 5, 6, 1, 6, 5, 10, 5, 6
7 1, 7, 9, 9, 7, 1, 7, 9, 9, 7, 1, 7
8 1, 8, 6, 0, 5, 3, 10, 3, 5, 0, 6, 8
9 1, 9, 7, 7, 9, 1, 9, 7, 7, 9, 1, 9
10 1, 10, 1, 10, 1, 10, 1, 10, 1, 10, 1, 10

Table 1: Example 2

with periods 2, 1, 10, 12, 10, 3, 6, 5, 12, 5, 2 respectively.

Theorem 1 Let p be an odd prime and g ∈ ℤ such that 0 ≤ g < p. Let k be the period of the sequence T_{n}(g) mod p for n = 0, 1, 2, . . .. Let λ^{2} − 2gλ + 1 have roots λ = α_{1}, α_{2}. Then (i) k|p − 1 if the roots are in GF(p), otherwise, (ii) k|p + 1 when the roots are in GF(p^{2}).

Proof: We have already shown that we may compute T_{n}(g) mod p by computing the n^{th} power of the recurrence relation matrix which has characteristic polynomial f(λ) = λ^{2} − 2gλ + 1, then performing one matrix-vector product modulo p and selecting the first element in the resulting vector. The determinant of this matrix is also equal to the coefficient of λ^{0} of f(λ), which is 1, so the matrix is non-singular. The 0^{th} power of the matrix is the identity matrix, so the period k will be the smallest positive integer such that the k^{th} power of the matrix is the identity matrix. We may compute powers of a matrix by finding its Jordan canonical form, then compute powers of the Jordan canonical form, then transform back. Recall that the Jordan canonical form is a diagonal matrix with the distinct eigenvalues on the diagonal, or it is an upper triangular matrix with repeated eigenvalues on the diagonal. Recall that the eigenvalues are also roots of the characteristic polynomial. In the case when the characteristic polynomial has repeated roots then they both must be ±1 mod p because the only least residue solutions of x^{2} − 1 = 0 mod p are x = ±1. In the case when 1 is a double root then g = 1 and our sequence is 1, 1, 1, ... which has period 1. In the other case, the repeated root is −1 with g = −1 and our sequence is 1, p − 1, 1, p − 1, ... which has period 2 and this is a divisor of p − 1, since p is odd. Now we consider the case when the distinct roots lie in GF(p). ¿From Fermat’s theorem a^{(p−1)} = 1 mod p for any non-zero a < p. So the (p − 1)^{st} power of the Jordan canonical form matrix will be the identity matrix, so our sequence will have period at most p − 1. If a smaller exponent k < p − 1 exists such that the k^{th} power of our Jordan canonical form matrix is the identity, then k must be a divisor of p − 1, because by Lagrange’s theorem for the order of a subgroup of a finite group the period must be a divisor of p − 1. The final case, case (ii), is when the roots only exist in a quadratic extension of GF(p). We may still diagonalize our matrix as long as we do our arithmetic in that quadratic extension field. First we raise our diagonal Jordan canonical form matrix to the power p. We recall that raising a number to the power p is an automorphism in the quadratic extension field. This means that the 2 roots just swap position on the diagonal, since we only have one non-identity automorphism in a quadratic extension field. Then we multiply by our original Jordan canonical form matrix to complete the calculation of the (p + 1)^{st} power. This will just multiply 2 pairs of conjugate roots. Since the product of the conjugate roots is also the coefficient of λ^{0} in the characteristic polynomial, which is 1, the (p + 1)^{st} power is the identity matrix. This means that the period is at most p + 1. Again, by Lagrange’s theorem, the period must be a divisor of p + 1. ■

We also noticed a mirror symmetry about the midpoint in each of the sequences in example 2. This is also explained by the roots being reciprocals of each other. Because of this mirror symmetry only about one half the elements could occur in any given sequence. Since our sequences contain some duplicates before the period is complete, our sequence cannot be explained as being obtained from the powers of an element from a group. It is because of this fact that we have a different generalization of the Diffie-Hellman algorithm than the group generalization, in spite of the fact that a matrix group occurs in our algorithm.

5 The discrete log problem for Chebyshev polynomials

How does an eavesdropper try to break our algorithm? We may assume that the eavesdropper knows p, g, a, b but does not know the secret degrees m and n . One way that the eavesdropper could break our algorithm would be to first solve the equation a = T_{m}(g) mod p for the unknown degree m. We call this the Chebyshev discrete log problem. Then the eavesdropper would just compute c = T_{m}(b) mod p the same way that Alice would. We will map the Chebyshev discrete log problem onto the conventional discrete log problem by recalling the hyperbolic definition of Chebyshev polynomials and solving it for m . We have the following theorem.

Theorem 2 Let a and g be integers and p a prime. If a = T_{m}(g) mod p then m is one of the values log_{g+\sqrt{g^{2}−1}}(a + \sqrt{a^{2} − 1}) where the square roots

may lie in the quadratic extension field GF (p^{2}) and the logarithm is the discrete log in the field GF (p) or its quadratic extension field.

Proof: a = T_{m}(g) = cosh(m cosh^{−1}(g)) so m = \frac{cosh^{−1}(a)}{cosh^{−1}(g)}. We convert this to

log’s to find m = \frac{log(a+\sqrt{a^{2}−1})}{log(g+\sqrt{g^{2}−1})}. We recall the change of base formula for log’s

to write this as: m = log_{g+\sqrt{g^{2}−1}}(a + \sqrt{a^{2} − 1}). In the case where both the

square roots \sqrt{g^{2} − 1} and \sqrt{a^{2} − 1} exist in GF(p) we have a conventional discrete log problem. Otherwise at least one of the square roots exists in the quadratic extension field GF(p^{2}) and this leads to a quadratic extension field generalization of the discrete log problem. Note, to compute a square root in GF(p) or in GF(p^{2}) we may use the O(log^{3} p) probabilistic polynomial time method of Rabin which is also described in [1].

Example 3 Alice chooses p = 9973, g = 65 and m = 1871. Alice computes a = T_{m}(g) mod p = 1063. Now the eavesdropper has seen p, g, a but not m and needs to determine m. The eavesdropper computes

h = \sqrt{g^{2} − 1} = ±923, and s = \sqrt{a^{2} − 1} = ±3296.

The eavesdropper then computes the discrete logarithms

log_{g±h}(a ± s) = ±1871 mod 9972.

Now the eavesdropper has also seen b = T_{n}(g) mod p which was sent from Bob to Alice. He now computes k = T_{m}(b) mod p and obtains the secret key. Note both values of m yield the same key k.

Example 4 Alice chooses p = 9973, g = 73 and m = 1259. Alice computes a = T_{m}(g) mod p = 1659. Now the eavesdropper has seen p, g, a but not m and needs to determine m. The eavesdropper attempts to compute h = \sqrt{(}g^{2} − 1) mod p, but this only exists in the quadratric extension field Z_{p}(\sqrt{5328}). Next the eavesdropper attempts to compute s = \sqrt{a^{2} − 1} mod p, but this may be expressed as s = 5200\sqrt{5328}. The eavesdropper then computes the discrete logarithms

log_{g±h}(a ± s) = ±1259 mod 9974.

6 The Chebyshev polynomial RSA algorithm

Recall that the RSA cryptographic algorithm is as follows [1]:

1. Alice chooses two large primes p and q which are kept secret.

2. Alice creates the public modulus M = pq.

3. Alice chooses a random encryption exponent 0 < e < M, and makes e public.

4. Alice computes a secret decryption exponent d = 1/e mod ((p−1)(q− 1)).

5. Alice emails Bob M and e.

6. Bob encodes his secret message as a number x.

7. Bob computes y = x^{e} mod M and sends y to Alice.

8. Alice decrypts Bob’s y by computing z = y^{d} mod M.

Now Alice has z = x and then decodes z to read Bob’s message. We modify the above algorithm to use Chebyshev polynomials instead of monomials. The Chebyshev polynomial RSA algorithm is as follows:

1. Alice chooses two large primes p and q which are kept secret.

2. Alice creates the public modulus M = pq.

3. Alice chooses a random encryption degree 0 < e < M, and makes e public.

4. Alice computes a secret decryption degree d = 1/e mod ((p^{2} − 1)(q^{2} − 1)).

5. Alice emails Bob M and e.

6. Bob encodes his secret message as a number x.

7. Bob computes y = T_{e}(x) mod M and sends y to Alice.

8. Alice decrypts Bob’s y by computing z = T_{d}(y) mod M.

Now Alice has z = x and then decodes z to read Bob’s message. This works because the period in the sequence of Chebyshev polynomials was shown to be a divisor of p − 1 or a divisor p + 1, so it is always a divisor of the product p^{2} − 1 for an odd prime modulus p. Since our modulus is M = pq we may use the Chinese remainder theorem to show that if a message is recovered modulo each of the primes p and q then it can be recoved modulo M. First working modulo p we find that z = T_{d}(y) = T_{d}(T_{e}(x)) = T_{de}(x) = T_{k(p^{2}−1)(q^{2}−1)+1}(x) = T_{1}(x) = x mod p. The same equation holds modulo q so Alice can recover Bob’s encoded message x. In our case the decryption degree d, is about twice the length of the decryption exponent in the classical RSA algorithm. This will cost us another factor of 2 in decryption time as compared to RSA, so the total time should be about 8 to 16 times slower than the conventional RSA algorithm. Our Maple 6 timings show that encrypting is 4.01 times slower than RSA, and decrypting is 8.39 times slower than RSA, when p is a random 100 digit prime, q is a random 101 digit prime, and e a random 100 digit integer.

References

[1] Randall K. Nichols, ICSA guide to Cryptography, McGraw-Hill, New York.

[2] M. Abramowitz and A. Stegun, Handbook of Mathematical Functions, Dover Publications, New York.

[3] Peter Borwein and Tamas Erdelyi, Polynomials and Polynomial Inequalities, Springer, New York, 1995.

[4] M.B. Monagan, K.O. Geddes, K.M. Heal, G. Labahn, S.M. Vorkoetter, J. MacCarron Maple 6 Programming Guide Waterloo Maple, Waterloo, Canada

[5] Arto Salomaa Public-Key Cryptography Springer, New York.