Channels ▼
RSS

Cryptography Without Exponentiation


APR94: Cryptography Without Exponentiation

Peter has worked in the computer industry for 16 years, and served as deputy editor of Asian Computer Monthly. He invented LUC in 1991 and founded LUCENT to commercialize Lucas-function-based cryptography. He can be reached at 25 Lawrence Street, Herne Bay, Auckland, New Zealand.


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 Algorithms

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 ax=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 Vx(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.

Key Negotiation

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) [alpha]. Using a secret number A, Alice publishes her part of the key, as given by [alpha]A mod p. Similarly, Bob publishes his part of the key using his secret number B, using the formula [alpha]B mod p. In Alice's case, she takes Bob's key and forms ([alpha]B)A mod p, while Bob takes Alice's published key, and forms ([alpha]A)B mod p. Since ([alpha]B)A mod p equals [alpha]AB mod p equals ([alpha]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.

LUCDIF is quite analogous to Diffie-Hellman. Choose the prime p in the same way. A value [lambda] must be chosen so that the condition in Figure 1(a) is true. Finding such a value is easy. Every value tried has a 50 percent chance of satisfying the condition. Now the values given by VA([lambda],1) mod p and VB([lambda],1) mod p are published by Alice and Bob, respectively. Bob takes Alice's number and calculates VB(VA([lambda],1)) mod p. Similarly, Alice calculates VA(VB([lambda],1)) mod p.

Relation 1 in Figure 1(b) shows that these two values are the same and that Alice and Bob have obtained the same key, K'. If p is a prime of over 512 bits, then this method of key negotiation is very secure. Once again, for a DES key, Alice and Bob may decide to select only the first 56 bits of K'.

El Gamal and LUCELG

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 [alpha]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 L[equivalent to]yk mod p. Two other values are then worked out: c1[equivalent to][alpha]k mod p, and c2[equivalent to]LM mod p. These two values, c1 and c2, make up the cryptogram which Alice sends to Bob.

For decryption, Bob first calculates L using the fact that L[equivalent to]([alpha]k)x=(c1)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 c2, recovering M; M[equivalent to]c2(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 Vx([gamma],1) mod p. A secret value k is also necessary here, and we first calculate G. When encrypting, G[equivalent to]Vk(y,1) mod p. The two halves of the cryptogram are then computed: d1[equivalent to]Vk([gamma],1) mod p, and d2[equivalent to]GM mod p.

In the decryption case, Bob deciphers the cryptogram by solving for G; G[equivalent to]

Vx(d1,1) mod p. The multiplicative inverse of G can be calculated, modulo p, using the extended Euclidean algorithm (see Knuth), and the message is recovered by M[equivalent to]d2(G-1) mod p. Figure 2 provides an example.

Note that the LUCELG cryptogram is twice the size it would be in LUC. Both d1 and d2 almost always have the same number of digits as the modulus, so the combined cryptogram will have a length of about twice that of p. This is also the case with the exponentiation version.

Digital Signature

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 {Ui} "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.

Conclusion

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.

References

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

Secure alternatives

to RSA

Figure 1: (a) Choosing a value [lambda]; (b) Lucas-function relations which let us transform exponentiation to Lucas-function calculation.

<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


Figure 2: Example of LUCELG.

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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.