Cryptography Without Exponentiation

While not a full-fledged public-key cryptosystem, the 1976 Diffie-Hellman key-negotiation technique featured the first cryptographic use of modulus exponentiation. Diffie and Hellman's method, which is used to establish a secret key over an insecure channel, is still in use because the mathematical problem on which it is based remains as difficult today as it was in 1976. In this, Diffie and Hellman were also the first to base cryptosystems on problems that mathematicians have been unable to solve.

In the January 1993 issue of DDJ, I presented an alternative to the RSA encryption algorithm called LUC (see "LUC Public-Key Encryption," DDJ, January 1993). As that article suggests, many ciphers, including the Hellman-Diffie-Merkle key-exchange system and the El Gamal digital signature, can be reinforced by replacing the process of exponentiation with the process of calculating Lucas functions. This article extends LUC with three new cryptosystems: the Lucas-function El Gamal public-key encryption, the Lucas-function El Gamal digital signature, and a Lucas-function-based key-negotiation method called LUCDIF.

The exponentiation ciphers here are all based on the mathematical problem known as the Discrete Logarithm (DL). Basically, this problem reduces to solving for x in the equation a^x=b mod c; where a, b, and c are integers and their values are known. The cipher known as El Gamal and its variants were introduced over the course of the 1980s and are based on the DL problem. One of these, Schnorr's variant of the El Gamal digital signature, was chosen by the National Institute of Standards and Technology as the basis of the Digital Signature Standard.

As suggested in my previous article, ciphers based on the DL problem can be implemented using Lucas functions instead of exponentiation. Such implementations are sometimes not without their complications in terms of storage and timing overheads, but they can be shown to be asymptotically as fast. More importantly, they are cryptographically stronger than their exponentiation-based ancestors. It is an open question how much stronger the Lucas-function ciphers are. The fastest known subexponential-time algorithms for attacking the DL can't be used against them, making them vulnerable only to exponential-time attacks.

The mathematical problem on which the Lucas-function ciphers are based is analogous to the DL problem, except that here the problem is to solve for x in the equation V_x(a,1)=b mod c. This problem has the advantage that the subexponential algorithms do not appear to generalize to it, so breaking these ciphers is much more expensive.

The Diffie-Hellman key-negotiation process allows two correspondents, Alice and Bob, to establish a common cryptographic key between them, even if an eavesdropper is listening in on their connection. They both agree on a prime p and a primitive root (or generator) . Using a secret number A, Alice publishes her part of the key, as given by ^A mod p. Similarly, Bob publishes his part of the key using his secret number B, using the formula ^B mod p. In Alice's case, she takes Bob's key and forms (^B)^A mod p, while Bob takes Alice's published key, and forms (^A)^B mod p. Since (^B)^A mod p equals ^AB mod p equals (^A)^B mod p equals some value K, say, then both Alice and Bob now have the same key. This method, the first successful, though partial, implementation of public-key ideas, lets part of the key be made public.

The DL problem seems to guarantee that an eavesdropper, who has only public knowledge and not the secret values A and B, cannot find K. If p, A, and B are large enough (say, over 500 bits in length), there is only a small chance of guessing the secret values. If the key were to be used as a DES key, Alice and Bob could agree to take only the first 56 bits to K.

We have called our Lucas-function-based key-negotiation method LUCDIF, combining LUCas and DIFfie. As with LUC, the known multiplicative attacks on Diffie-Hellman do not carry over to LUCDIF, since it is not multiplicative.

The El Gamal cipher comes in two parts. There is a procedure for encrypting and decrypting and a second procedure for signing and verifying a digital signature. For encryption, assume Alice wants to send a message M to Bob using his public key y which is equal to ^x mod p (x is Bob's private key). Alice first finds a secret number k, which is greater than zero and less than p, and calculates L using Ly^k mod p. Two other values are then worked out: c₁^k mod p, and c₂LM mod p. These two values, c₁ and c₂, make up the cryptogram which Alice sends to Bob.

For decryption, Bob first calculates L using the fact that L(^k)^x=(c₁)^x, since only he knows the value of his secret key x. Having found L, Bob calculates its multiplicative inverse (L^-1), and multiplies this by c₂, recovering M; Mc₂(L^-1) mod p.

The Lucas-function version of El Gamal public-key encryption and decryption follows a path similar to that of El Gamal public-key encryption/

decryption. Bob's public key, in this case, is V_x(,1) mod p. A secret value k is also necessary here, and we first calculate G. When encrypting, GV_k(y,1) mod p. The two halves of the cryptogram are then computed: d₁V_k(,1) mod p, and d₂GM mod p.

In the decryption case, Bob deciphers the cryptogram by solving for G; G

The El Gamal digital signature is more cumbersome to convert from exponentiation to Lucas functions than is El Gamal public-key encryption/decryption. However, observing that Lucas functions have formulas for multiplying and adding subscripts--see Figure 1(b)--we can construct an El Gamal-like cipher, since El Gamal's manipulation of exponents can be converted to the manipulation of Lucas-function subscripts. The formula for the addition of subscripts (Relation 2) involves the Lucas {U_i} "sister" series. Subsequently, our Lucas-function alternative to El Gamal involves the doubling of the public-key size (two Lucas function values, U and V, must be given), as well as increasing the size of the signature, because two "r" (U and V) values are necessary.

The variant of El Gamal chosen as the Digital Signature Standard can be converted in a similar manner. In both cases, we produce ciphers apparently based on a problem for which there is no known subexponential-time attack; hence, they are stronger than their prototypes.

The calculation of the nth Lucas function can be done in O(logn) operations, which is the same order as the computation of similar exponentials. Heuristics to speed up modular exponentiation can be brought over to the calculation of Lucas functions, if in more complicated form (witness the formula for adding subscripts). These new ciphers can be assured of having performance characteristics similar to those of their progenitors.

For the same level of security, these Lucas-function-based ciphers can be used with a shorter modulus than the exponentiation ciphers. For a 512-bit modulus, the reduction is about one fifth, down to 420 bits, for equivalent cryptographic strength. This reduction increases in size as the modulus grows longer. That only exponential-time attacks are possible on the Lucas-function version of the DL problem ensures attempts to solve it are increasingly more expensive than the subexponential-time attacks possible on the DL itself. We have applied for patents on these algorithms.

Finally, LUC Encryption Technology Ltd. (LUCENT), has been incorporated to license and support cryptographic systems based on Lucas functions. For more information, contact Horace R. Moore, 101 E. Bonita, Sierra Madre, CA 91024.

Carey, M.R. and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: W.H. Freeman, 1979.

Diffie, W. and M.E. Hellman. "New Directions in Cryptography." IEEE Transactions on Information Theory (November 1976).

El Gamal, T. "A Public-key Cryptosystem and a Signature Scheme Based on Discrete Logarithms." IEEE Transactions on Information Theory (July 1985).

Knuth, D.E. The Art of Computer Programming: Volume II: Semi-Numerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1981.

Smith, Peter. "LUC Public-Key Encryption." Dr. Dobb's Journal (January 1993).

<b>(a)</b>
     V<sub>(p+1)/t</sub>(<img src="http://twimgs.com/ddj/ddj/images/ddj9404b/lambda.gif" alt="[lambda]">,1) [does not equal] 2 mod p, for all t>1 dividing (p+1)

<b>(b)</b>
     V<sub>nm</sub>(P,Q)=V<sub>n</sub>(V<sub>m</sub>(P,Q),Q<sup>m</sup>)     Relation 1
     2V<sub>n+m</sub>=V<sub>n</sub>V<sub>m</sub>+DU<sub>n</sub>U<sub>m</sub>            Relation 2

Let the prime p be 908797. Choose k=1949, <img src="http://twimgs.com/ddj/ddj/images/ddj9404b/gamma14.gif" alt="[gamma]">=19, x=2089, y=894501 and M=1111.

G<img src="http://twimgs.com/ddj/ddj/images/ddj9404b/equiv12.gif" alt="[equivalent to]">V<sub>k</sub>(y,1) mod p=V<sub>1949</sub>(894501,1) mod 908797=788038.
d<sub>1</sub><img src="http://twimgs.com/ddj/ddj/images/ddj9404b/equiv12.gif" alt="[equivalent to]">V<sub>k</sub>(<img src="http://twimgs.com/ddj/ddj/images/ddj9404b/gamma14.gif" alt="[gamma]">,1) mod p=V<sub>1949</sub>(19,1) mod 908797=307718.
d<sub>2</sub><img src="http://twimgs.com/ddj/ddj/images/ddj9404b/equiv12.gif" alt="[equivalent to]">GM mod p=788038.1111 mod 908797=338707.

The cryptogram is the pair (d<sub>1</sub>,d<sub>2</sub>)=(307718, 338707).
The receiver, who knows that the secret key is 2089, first calculates:

G<img src="http://twimgs.com/ddj/ddj/images/ddj9404b/equiv12.gif" alt="[equivalent to]">V<sub>x</sub>(d<sub>1</sub>,1) mod p=V<sub>2089</sub>(307718,1)=788038     The inverse of this is 518288.
M<img src="http://twimgs.com/ddj/ddj/images/ddj9404b/equiv12.gif" alt="[equivalent to]">d<sub>2</sub>(G<sup>-1</sup>)=338707.518288=1111     The original message.

Copyright © 1994, Dr. Dobb's Journal