Resource Library

Download PDF version of this paper

Alternatives to RSA: Using Diffie-Hellman with DSS

By Dr. Jim Omura

Many vendors who need security for their networking applications often assume that RSA is the only public-key technique available. Just as secure and easier to use than RSA are the techniques based on the original public-key paper by Diffie and Hellman [1]. In this note, we describe the important applications of public-key cryptography and show how these Diffie-Hellman (DH) based techniques perform the same functions as RSA.

The Stanford patent on the Diffie-Hellman technique had expired in 1997 and it is now in the public domain while the MIT patent on RSA will not expire until the year 2000. New information security standards in both banking and the Internet are now based on these royalty free Diffie-Hellman public-key techniques.

Introduction:
In 1976, Diffie and Hellman [1] started an explosion of open research in cryptology when they first introduced the notion of public-key cryptography, which allows for new electronic means to handle key distribution in conventional cryptographic systems and for digital signatures in electronic messages. In this original paper, Diffie and Hellman gave a limited example of a public-key system which is known today as the Diffie-Hellman key exchange. Later, in 1978, Rivest, Shamir, and Adleman [2] gave a complete example of a public-key system that is popularly known as RSA. This RSA system can perform both key distribution and digital signature functions. RSA can also be used for encryption, but here it has no practical advantages over conventional encryption techniques which are generally much faster.

It turns out that the original example given by Diffie and Hellman had the elements of a complete public-key system. This was discovered by El Gamal [3] who added the digital signature feature to the original Diffie-Hellman key exchange ideas. In 1994, the National Institute of Standards and Technology (NIST) adopted the Digital Signature Standard (DSS) based on a variation of this El Gamal digital signature [4]. Thus, the Diffie-Hellman key exchange, together with its extension to digital signatures in the form of DSS, can do the same public-key functions that RSA can perform.

In 1995, the Financial Institution Standards body of the American National Standards Institute (ANSI) established the NIST's DSS as its own digital signature standard [5]. This banking standard has been established together with the NIST Secure Hashing algorithm (SHA) [6]. In addition, ANSI will adopt a certificate management standard for DSS [7].

For key exchange there is now an ANSI standard, X9.42, that is based on Diffie-Hellman. The Internet Engineering Task Force (IETF) key exchange standard called IPsec, is also based on Diffie-Hellman. Thus this royalty free Diffie-Hellman public-key technique is now the standard in both the Internet and banking.

We first present a general discussion of the public-key method for creating digital signatures and the use of certificates, followed by a general discussion of the key distribution problem in conventional cryptographic systems. The remaining sections describe how the Diffie-Hellman key exchange with DSS can accomplish all the same functions as RSA in all the important applications of public-key cryptography.

Digital Signatures and Certificates:
With both RSA and DSS, a person's digital signature is based on a unique pair of numbers, one private, the other public. Although mathematically related, knowing a person's public number does not reveal the corresponding private number. Alice, for example, can use her private number to create a digital signature attached to her electronic message. Later, another person, say Bob, can easily authenticate Alice's digital signature by using only Alice's public number. Bob can also verify the integrity of the message that Alice signed. As long as Alice keeps her private number secret, nobody can counterfeit her digital signatures, while anyone can both authenticate her digital signatures and verify the integrity of her signed messages by using only her public number.

To make practical use of public-key digital signatures, there needs to be established a trusted certification authority which also has a private number and public number. It is assumed that everyone in the system has knowledge of the public number of the certification authority. Thus, everyone can verify the digital signatures and the integrity of any signed message of the certification authority.

Alice must first identify herself to the certification authority and submit her public number to be certified. Once the certification authority is satisfied it has properly identified Alice, it can create a message that consists of Alice's data (which may include, for example, her name, address, social security number, unique privileges, time of expiration, etc.) and her public number, which is then digitally signed by the certification authority using its private number. This electronic message that is signed by the certification authority is Alice's certificate. It is assumed that everyone in the system obtains such a unique personal certificate from the certification authority. It is also assumed that everyone in the system can verify the integrity of the data in any certificate issued by the certification authority.

A complete network of such trusted certification authorities will be needed for widespread use of digital signatures. The United States government's planned system of certification authorities is called the Public-Key Infrastructure (PKI).

Once Alice has her certificate, she can attach it to her signed messages. To authenticate Alice's signature, Bob can first authenticate her certificate and recover Alice's public number. He then uses what he knows is Alice's public number to authenticate her digital signature and verify the integrity of the message she signed.

Cryptographic Strengths of RSA and Diffie-Hellman Based Systems:
The cryptographic strength of these public-key systems depends on how difficult it is for anyone to compute a person's private number given only the person's corresponding public number. For RSA this is based on the difficulty of finding the prime factors of a large integer, while the Diffie-Hellman based systems depend on the difficulty of computing discrete logarithms in a finite field generated by a large prime number. Both of these are well known "hard to solve" mathematical problems. Although the discrete logarithm problem is believed to be more difficult to solve than the factoring problem, in practical terms the differences are not important [8,9,10].

In terms of ease of computations, there is also not much of a difference between the Diffie-Hellman based systems and RSA. Depending on the circumstances, there may be a computational advantage with one method over the other, but with today's high speed processors and custom chips, these differences are not significant for numbers from 512 bits to 1024 bits in length.

Debates have been going on for some time comparing various properties of the RSA and DSS public-key digital signature schemes. Although there are some differences, the bottom line is that, from a practical point of view, these two public-key digital signature schemes are roughly the same in strength and computational requirements.

In a recent study, Odlyzko [11] concludes that the 512 bit numbers are considered marginally safe today, while 1024 bit numbers are expected to be safe for a decade in both RSA and Diffie-Hellman based systems. Because the numbers may eventually exceed 1024 bits in length, there is now interest in elliptic curve public-key cryptosystems that were first proposed independently by N. Koblitz [12] and V.S. Miller [13]. These are not new public-key systems, but are basically the Diffie-Hellman based systems using elliptic curves over finite fields. Elliptic curves over the finite field GF(2[ⁿ]) are the most interesting and specific implementations proposed that provide a high degree of security with small numbers, where n is less than 200 bits [14,15]. The RSA system does not extend to these elliptic curve cryptosystems.

There is still some reluctance to use elliptic curve cryptosystems since they have not been scrutinized as carefully as integer factorization (attack on RSA) and ordinary discrete logarithms for GF(p), where "p" is a prime number (attack on conventional Diffie-Hellman and DSS systems).

Conventional Encryption and Key Distribution:
Because public-key algorithms are computationally intensive, they are generally used in practice for creating digital signatures in electronic messages and for handling key distribution in systems using conventional (also called symmetric key) encryption algorithms. Conventional encryption algorithms are used primarily for maintaining the privacy of information. The best known conventional encryption algorithm is the Data Encryption Algorithm, which was established by NIST as the 1976 Data Encryption Standard (DES) [16]. DES has been around for over 20 years and now a replacement is being discussed by several organizations.

The banking standards group, ANSI, has approved as a standard encryption algorithm the extension of DES to Triple-DES. IDEA (International Data Encryption Algorithm), an algorithm invented by Professor James Massey and his students at the ETH in Zurich, has been used by Phil Zimmermann in his Pretty Good Privacy (PGP) security software package that was distributed on the Internet [17]. IDEA, however, is patented by ASCOM, a Swiss company that funded the work by Massey and his students. Massey has recently developed a new conventional encryption algorithm called SAFER which is not patented and is available license free [18].

Meanwhile NIST has asked for submissions for the next conventional encryption algorithm standard which is referred to as the Advanced Encryption Standard (AES). This NIST replacement for DES is expected to be established in 1999.

All of these conventional encryption algorithms require a single secret key for both encryption and decryption of messages. Before the invention of public-key cryptography, key distribution required a trusted secure channel. Traditionally, this channel was a trusted person who installed secret keys into the various encryption algorithms in a secure network.

With the use of public-key cryptography, key distribution can be done electronically at much less cost and risk than using trusted couriers. This requires the use of digital signatures and a certification authority. In the following sections, we describe how this public-key approach for key distribution can be handled just as easily with the Diffie-Hellman based systems as with RSA.

Notations:
The following are the notations we will use throughout this note.

{ }
Braces indicate the Secure Hash Algorithm (SHA) which is required by the NIST Digital Signature Standard (DSS) as input to the Digital Signature Algorithm (DSA). Here, {a, b} is the result when the SHA is applied to "a" concatenated with "b".

[ ]
Brackets are for any function of the Diffie-Hellman shared secret number, Z, which is used to create a conventional L bit secret key for a symmetric encryption algorithm. Here, [Z] may be, for example, the L least significant bits of Z or perhaps some hash of Z which is L bits long.

I_A
This is Alice's identification which is typically attached to any message sent by Alice. It is generally a short identifier with no cryptographic elements in it.

C_A
This is a random number generated by Alice to be used in a challenge response protocol.

S_A{ }
This is Alice's DSS signature on the hashed version of the message which is "a" concatenated with "b". There will be several protocols presented here where the DSS signature is sent without the message for which the signature is applied. Here, Alice uses her permanent private number X[_A] to create her DSS signatures.

S_A( )
This is the concatenation of "a" and "b" followed by Alice's DSS signature on message "a, b". Here again, Alice uses her permanent private number X_A to create her DSS signatures. Note that S_A(a, b) = a, b, S_A{a, b}.

Cert_A
This is Alice's certificate which contains Alice's name, Alice's privileges (and possibly other information), her permanent public number Y[_A], and the trusted Certification Authority's DSS signature for this personal data.

E_K( )
This is encryption using a symmetric cryptosystem (such as DES) with key K.

a+b
This is the bit-by-bit modulo-2 addition of two equal length binary sequences "a" and "b".

The Diffie-Hellman Key Exchange with DSS:
For the Digital Signature Standard (DSS) we have common system parameters "g", "q", and "p" where "p" is the modulus prime number. For this DSS system, Alice has a permanent private number X_A and the corresponding permanent public number Y_A given by

Y_A = g^XA mod p .

Bob also has his own permanent private number X_B and corresponding permanent public number Y_B given by

Y_B = g^XB mod p .

We assume that both Alice and Bob have certificates issued by a certification authority that includes their public numbers. Denote these certificates as Cert_A and Cert_B where Y_A and Y_B are Alice and Bob's permanent public numbers that are included in their certificates. Thus, when Alice receives Bob's certificate, Cert_B, she knows with certainty that Y_B is Bob's public number. These do not change as long as the certificates are valid.

Assume throughout this note that Alice and Bob have each other's certificates. Thus Alice knows with certainty Bob's permanent public number Y[_B] and Bob similarly knows Alice's permanent public number Y_A. Certificates could be exchanged prior to a protocol or obtained from a directory service. If certificates are not distributed prior to the protocols given here then they must be included in the initial exchanges of these protocols.

The Standard Diffie-Hellman Key Exchange:
In the conventional Diffie-Hellman key exchange, Alice and Bob can generate a shared secret key by conducting the following transaction:

1. Alice randomly generates a secret private number R[_A] and computes the corresponding public number W_A given by

while Bob randomly generates his own secret private number R_B and computes his corresponding public number W[_B] by

W_B = g^RB mod p .

2. When Alice and Bob want to establish a key exchange, they first exchange their public numbers, where Alice sends WA to Bob and Bob sends WB to Alice.

3. Alice computes the common shared secret number Z by using only Bob's public number W_B and her secret number R_A by

Bob is able to compute the same shared secret number Z by using Alice's public number W_A and his own secret number R_B by

Note that in each new transaction between Alice and Bob, new private and public numbers can be used with the resulting newly computed common shared secret number Z. This type of conventional Diffie-Hellman key exchange works well in many end-to-end secure communication applications. Its weakness is that there is no authentication of the public numbers that are exchanged. For example, how does Alice know that W[_B] is truly Bob's public number?

Challenge Response Authentication:
Before continuing with authenticated Diffie-Hellman key exchanges, we first examine how Alice and Bob can authenticate each other. For mutual authentication, the obvious challenge response protocol using DSS is as follows:

1. Alice generates a random number C_A and sends this to Bob.

2. Bob generates a random number C_B and sends to Alice the DSS signed message C_B, S_B{C_A, C_B}.

3. Alice sends back to Bob the DSS signature S_A{C_A, C_B}.

Note that Eve could intercept Alice's second transmission to Bob and replace it with her DSS signed message S_E{C_A, C_B}. Bob would then believe that it is Eve that is at the other end of the link instead of Alice. Alice, on the other hand, knows that she is linked to Bob and conducts the session without knowing that Bob thinks she is Eve.

This problem can be avoided by linking some identification to each transmission in the protocol. For example, in Step 1 Alice sends I_A along with C_A. In Step 2 Bob can send the DSS signed message I_B, C_B, S_B{I_A, C_A, I_B, C_B} to Alice and in Step 3 Alice can send the DSS signed message I_A, S_A{I_A, C_A, I_B, C_B} to Bob. In this case, Eve could replace IE for IA in both of Alice's transmissions to Bob and also use her own DSS signature on the second transmission to Bob. Although Bob would be deceived into believing he is in communication with Eve, Alice would know that Eve is doing this and terminate this session.

This modified mutual authentication protocol with the normal practice of sending an identification with each transmission is as follows:

1. Alice generates a random number C_A and sends this to Bob.

2. Bob generates a random number C_B and sends to Alice the DSS signed message I_B, C_B, S_B{I_A, C_A, I_B, C_B}.

3. Alice sends back to Bob the DSS signature S_A{I_A, C_A, I_B, C_B}.

In the remainder of this note, we will always assume that an identification of the sender is attached to any message.

Authenticated Diffie-Hellman Key Exchanges:
If Alice and Bob have permanent public numbers that are certified then they can conduct the Diffie-Hellman scheme with authenticated public numbers. The problem here is that the computed shared secret number would always be the same as long as the permanent public numbers are unchanged. In general it is not a good idea to use the same secret numbers too long.

Method #1:
One way to get around this is to generate new secret and public numbers for this conventional Diffie-Hellman key exchange but send the public numbers signed with DSS signatures. This problem of authenticated key exchange has been examined by Diffie, Van Oorschot, and Wiener [19] who recommends the following authenticated key exchange protocol:

1. Alice randomly generates a secret private number R_A and computes the corresponding public number W_A which she sends to Bob.

2. Bob randomly generates a secret private number R_B and computes the corresponding public number W_B . He computes the shared secret number Z from Alice's public number W_A and his private number R_B. He then sends to Alice W_B together with E_K(S_B{I_A, W_A, I_B, W_B}) where K = [Z].

3. Alice computes Z from Bob's public number W_B and her secret private number R_A. She then obtains the key K = [Z] and next decrypts and verifies Bob's signature on the hashed versions of the certificates and public numbers W_A and W_B. She also sends to Bob E_K(S_A{I_A, W_A, I_B, W_B}).

4. Bob then uses the key K and decrypts this message and verifies Alice's signature on the hashed certificates and public numbers.

The use of the shared secret number in this protocol is necessary to prevent a person in the middle, say Eve, causing Bob to believe he is conducting the DH key exchange with her rather than Alice [19]. There are many other ways to securely bind the shared secret number Z to the signed public numbers W_A and W_B. We consider another approach next.

Method #2:
1. Alice randomly generates a secret private number R_A and computes the corresponding public number W_A which she sends to Bob.

2. Bob randomly generates a secret private number R_B and computes the corresponding public number W_B. He also computes the shared secret number Z from W_A and R_B . Next, he randomly generates a random L bit sequence C_B and computes [Z] + C_B . He then sends to Alice W_B, [Z] + C_B, S_B{I_A, W_A, I_B, W_B, C_B}.

3. Alice computes the shared secret number Z from Bob's public number W_B and her secret private number R_A. She can then obtain C_B and verify the signature on the SHA of I_A, W_A, I_B, W_B, C_B.

Next, she then randomly generates a random bit sequence C_A and computes [Z] + C_A and sends to Bob [Z] + C_A, S_A{I_A, W_A, I_B, W_B, C_A}.

4. Bob uses Z to find C_A and can then verify Alice's signature on the SHA of I_A, W_A, I_B, W_B, C_A.

Note that since C_B is a random bit sequence, [Z] + C_B is a bit level "one time pad" encryption of [Z], which is known to be absolutely secure. The key issue here is the amount of information about CB that is revealed in S_B{I_A, W_A, I_B, W_B, C_B}. This also applies to how much S_A{I_A, W_A, I_B, W_B, C_A} reveals about C_A which is used to encrypt Z in [Z] + C_A.

This second method has the advantage that it does not use a particular symmetric key encryption algorithm in the protocol except for the bit level one time pad which is very simple and secure.

A Store and Forward Version of Diffie-Hellman
In the conventional Diffie-Hellman key exchange, we assume that Alice and Bob are engaged in a two way protocol. Suppose Alice wants to send an encrypted message by e-mail when Bob is not available to conduct an authenticated Diffie-Hellman key exchange. We describe a store and forward Diffie-Hellman scheme which is a natural extension of the original scheme for key agreement.

Assume that Alice has Bob's certificate, Cert_B, and therefore has his authenticated permanent public number Y_B. Alice can generate a random secret number R_A and the corresponding public number W_A and also generate a shared secret key Z by

She can then use the shared secret number Z to make an encryption key K = [Z] and encrypt (using DES for example) her DSS signed message M to get the encrypted message E_K(M, S_A{M, I_A, W_A}). She can then send to Bob, together with this encrypted message, her session public number W_A. This can be sent in a store and forward manner system.

Later, when Bob picks up this message, he can compute the shared secret number by

where X_B is Bob's permanent secret number. K = [Z] is the message encryption key that is then used to decrypt Alice's signed message from E_K(M, S_A{M, I_A, W_A}). Here, the encryption of S_A{M, I_A, W_A} binds W_A to Alice and the shared secret key.

Summary:
The important practical applications of public-key cryptography are for digital signatures in electronic messages and for key distribution in conventional encryption systems that maintain privacy in secure networks. For these applications, we have shown that the public-key example introduced by Diffie and Hellman and the extension of this to the Digital Signature Standard can perform the same functions as the RSA public-key system. Although there are some detail differences, there is little practical difference in performance between the two systems. The Diffie-Hellman based systems can be used in place of RSA in any application requiring public-key cryptography.

Download PDF version of this paper

References:
[1] W. Diffie and M.E. Hellman, New Directions in Cryptography, IEEE Trans. on Info. Theory, vol. IT-22, pp. 644-654, Nov. 1976.

[2] R. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Commun. of the Assoc. of Comp. Mach., vol. 21, pp. 120-126, Feb. 1978.

[3] T. El Gamal, A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. on Info. Theory, vol. IT-31, pp. 469-472, July 1985.

[4] Federal Information Processing Standards Publication (FIPS PUB) 186, Digital Signature Standard (DSS), National Institute of Standards and Technology, May 1994.

[5] ANSI X9.30 - 1995: Public Key Cryptography Using Irreversible Algorithms for the Financial Services Industry, Part 1: The Digital Signature Algorithm (DSA).

[6] ANSI X9.30 - 1995: Public Key Cryptography Using Irreversible Algorithms for the Financial Services Industry, Part 2: The Secure Hash Algorithm (SHA).

[7] ANSI X9.30 - Pending: Public Key Cryptography Using Irreversible Algorithms for the Financial Services Industry, Part 3: Certificate Management for DSA.

[8] S.C. Pohlig and M. Hellman, A Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance, IEEE Transactions On Information Theory, IT-24, pp. 106-110.

[9] B.A. LaMacchia and A.M. Odlyzko, Computation of Discrete Logarithms in Prime Fields, Designs, Codes and Cryptography, Kluwer Academic Publishers, 1991, pp. 47-62.

[10] G.J. Simmons, Contemporary Cryptology: The Science of Information Integrity, IEEE Press, New York, NY, 1992. See Chapter 10, Cryptanalysis: A Survey of Recent Results, by E.F. Brickell and A.M. Odlyzko.

[11] A.M. Odlyzko, The Future of Integer Factorization and Discrete Logarithms, preliminary draft paper, AT&T Bell Laboratories, Murray Hill, New Jersey, May 10, 1995.

[12] N. Koblitz, Elliptic Curve Cryptosystems, Mathematics of Computation, vol. 48, 1987, pp.203-209.

[13] V.S. Miller, Use of Elliptic Curves in Cryptography, Advances in Cryptology - CRYPTO '85 Proceedings, Berlin: Springer-Verlag, 1986, pp. 417-426.

[14] A.J. Menezes and S. Vanstone, The Implementation of Elliptic Curve Cryptosystems, Advances in Cryptology - AUSCRYPT '90 Proceedings, Berlin: Springer-Verlag, 1990, pp. 2-13.

[15] A.J. Menezes, Elliptic Curve Public-key Cryptosystems, Kluwer, 1993.

[16] Federal Information Processing Standards Publication (FIPS PUB) 46-2, Data Encryption Standard (Reaffirmed until 1998), National Institute of Standards and Technology, December 1993.

[17] S. Garfinkel, PGP: Pretty Good Privacy, O'Reilly & Associates, Sebastopol, CA, 1995.

[18] J.L. Massey, SAFER K-64: A Byte-Oriented Block Ciphering Algorithm, pp. 1-17 in Fast Software Encryption (Ed. R. Anderson), Proceedings of the Cambridge Security Workshop, Cambridge, U.K., December 1993.

[19] W. Diffie, P.C. Van Oorschot, and M.J. Wiener, Authentication and Authenticated Key Exchanges,in Designs, Codes and Cryptography, Kluwer Academic Publishers, 1992, pp. 107.