Cryptographic key distribution method and system

Claims

We claim:

1. A cryptographic communications system for use with a first terminal, a second terminal, a communications channel, and a network center, comprising:

first generator means located at said first terminal for generating a first key-encryption-key signal;

first structure means located at said first terminal for generating a first structured-data signal;

first encoding means located at said first terminal and coupled to said first generator means, said first structure means and said communications channel, for transforming, using a public-key-encryption algorithm, the first key-encryption-key signal and the first structured-data signal to a first ciphertext signal, and for transmitting the first ciphertext signal over said communications channel;

means located at said network center and responsive to receiving the first ciphertext signal for generating a request signal and transmitting the request signal over said communications channel;

second generator means located at said second terminal and responsive to the request signal for generating a second key-encryption-key signal;

second structure means located at said second terminal for generating a second structured-data signal;

second encoding means located at said second terminal and coupled to said second generator means, said second structure means and said communications channel, for transforming, using the public-key-encryption algorithm, the second key-encryption-key signal and the second structured-data signal to a second ciphertext signal, and for transmitting the second ciphertext signal over said communications channel;

first decoding means located at said network center and coupled to said communications channel for decoding, using a public-key-decryption algorithm, the first ciphertext signal and the second ciphertext signal, thereby generating the first key-encryption-key signal, the first structured-data signal, the second key-encryption-key signal and the second structured-data signal;

means located at said network center and coupled to said first decoding means for verifying the first structured-data signal and the second structured-data signal and for generating a verification signal;

third encoding means located at said network center, coupled to said decoding means, said verifying means, and said communications channel, and responsive to the verification signal, for transforming, using a classical-key-encryption algorithm, the first key-encryption-key signal and the second key-encryption-key signal to a third ciphertext signal and for transmitting the third ciphertext signal over said communications channel; and

second decoding means located at said first terminal and coupled to said communications channel for decoding, using a classical-key-decryption algorithm and the first key-encryption-key signal, the third ciphertext signal thereby generating the second key-encryption-key signal.

2. The cryptographic system as set forth in claim 1 wherein:

said first structure means generates the first structured-data signal with a first time-stamp signal; and

said verifying means verifies the first time-stamp signal.

3. The cryptographic system as set forth in claim 1 wherein:

said first structure means generates the first structured-data signal with a first identification signal; and

said verifying means verifies the first identification signal.

4. The cryptographic system as set forth in claim 1 wherein:

said second structure means generates the second structured-data signal with a second time-stamp signal; and

said verifying means verifies the second time-stamp signal.

5. The cryptographic system as set forth in claim 1 wherein:

said second structure means generates the second structured-data signal with a second identification signal; and

said verifying means verifies the second identification signal.

6. The cryptographic system as set forth in claim 1 wherein said first encoding means includes means for exponentiating the first key-encryption-key signal and the first structured-data signal modulo a modulus number, for generating the first ciphertext signal.

7. The cryptographic system as set forth in claim 1 wherein said second encoding means includes means for exponentiating the second key-encryption-key signal and the second structured-data signal modulo a modulus number, for generating the second ciphertext signal.

8. A cryptographic communications system for use with a first terminal, a second terminal, a communications channel, and a network center, comprising:

first generator means located at said first terminal for generating a first key-encryption-key signal;

first encoding means located at said first terminal and coupled to said first generator means and said communications channel, for transforming, using a public-key-encryption algorithm, the first key-encryption-key signal to a first ciphertext signal, and for transmitting the first ciphertext signal over said communications channel;

second generator means located at said second terminal for generating a second key-encryption-key signal;

second encoding means located at said second terminal and coupled to said second generator means and said communications channel, for transforming, using the public-key-encryption algorithm, the second key-encryption-key signal to a second ciphertext signal, and for transmitting the second ciphertext signal over said communications channel;

first decoding means located at said network center and coupled to said communications channel for decoding, using a public-key-decryption algorithm, the first ciphertext signal and the second ciphertext signal, thereby generating the first key-encryption-key signal and the second key-encryption-key signal;

third encoding means located at said network center and coupled to said decoding means and said communications channel for transforming, using a classical-key-encryption algorithm, the first key-encryption-key signal and the second key-encryption-key signal to a third ciphertext signal and for transmitting the third ciphertext signal over said communications channel; and

second decoding means located at said first terminal and coupled to said communications channel for decoding, using a classical-key-decryption algorithm and the first key-encryption-key signal, the third ciphertext signal thereby generating the second key-encryption-key signal.

9. The cryptographic communications system as set forth in claim 8 further including:

first structure means located at said first terminal for generating a first structured-data signal; and

wherein said first encoding means is coupled to said first structure means for transforming, using the public-key-encryption algorithm, the first key-encryption-key signal and the first structured-data signal to the first ciphertext signal.

10. The cryptographic system as set forth in claim 9 further including means located at said network center and coupled to said first decoding means for verifying the first structured-data signal and for generating a verification signal; and

wherein said third encoding means is coupled to said verifying means and is responsive to the verification signal for transforming, using a classical-key-encryption algorithm, the first key-encryption-key signal and the second key-encryption-key signal to the third ciphertext signal and for transmitting the third ciphertext signal over said communications channel.

11. The cryptographic system as set forth in claim 8 further including:

second structure means located at said second terminal for generating a second structured-data signal; and

wherein said second encoding means is coupled to said second structure means for transforming, using the public-key-encryption algorithm, the second key-encryption-key signal and the second structured-data signal to the second ciphertext signal.

12. The cryptographic system as set forth in claim 11 further including means located at said network center and coupled to said first decoding means for verifying the second structured-data signal and for generating a verification signal; and

wherein said third encoding means is coupled to said verifying means and is responsive to the verification signal for transforming, using the classical-key-encryption algorithm, the first key-encryption-key signal and the second key-encryption-key signal to the third ciphertext signal and for transmitting the third ciphertext signal over said communications channel.

13. The cryptographic system as set forth in claim 8 further including:

means located at said network center and responsive to receiving the first ciphertext signal for generating a request signal and for transmitting the request signal over said communications channel; and

wherein said second generator means is responsive to said request signal for generating the second key-encryption-key signal.

14. The cryptographic system as set forth in claim 8 wherein said first encoding means includes means for exponentiating the key-encryption-key signal modulo a modulus number, for generating the first ciphertext signal.

15. The cryptographic system as set forth in claim 8 wherein said second encoding means includes means for exponentiating the key-encryption-key signal modulo a modulus number, for generating the second ciphertext signal.

16. A method for establishing cryptographic communications using a first terminal, a second terminal, a communications channel, and a network center, comprising the steps of:

generating at said first terminal a first key-encryption-key signal and a first structured-data signal;

transforming, using a public-key-encryption algorithm, at said first terminal, the first key-encryption-key signal and the first structured-data signal to a first ciphertext signal;

transmitting the first ciphertext signal over said communications channel;

generating at said network center, in response to receiving the first ciphertext signal, a request signal;

transmitting from said network center the request signal over said communications channel;

generating at said second terminal in response to receiving the request signal a second key-encryption-key signal;

generating at said second terminal a second structured-data signal;

transforming at said second terminal, using the public-key-encryption algorithm, the second key-encryption-key signal and the second structured-data signal to a second ciphertext signal;

transmitting the second ciphertext signal over said communications channel;

decoding at said network center, using a public-key-decryption algorithm, the first ciphertext signal and the second ciphertext signal, thereby generating the first key-encryption-key signal, the first structured-data signal, the second key-encryption-key signal and the second structured-data signal;

verifying at said network center the first structured-data signal and the second structured-data signal and generating a verification signal;

transforming at said network center in response to the verification signal, using a classical-key-encryption algorithm, the first key-encryption-key signal and the second key-encryption-key signal to a third ciphertext signal;

transmitting the third ciphertext signal over said communications channel; and

decoding at said first terminal, using a classical-key-decryption algorithm and the first key-encryption-key signal, the third ciphertext signal, thereby generating the second key-encryption-key signal.

17. The method as set forth in claim 16 wherein:

said generating step of said first terminal generates the first structured-data signal with a first time-stamp signal; and

said verifying step verifies the first time-stamp signal.

18. The method as set forth in claim 16 wherein:

said generating step at said first terminal generates the first structured-data signal with a first identification signal; and

said verifying step verifies the first identification signal.

19. The method as set forth in claim 16 wherein:

said generating step at said second terminal generates the second structured-data signal with a second time-stamp signal; and

said verifying step verifies the second time-stamp signal.

20. The method as set forth in claim 16 wherein:

generating step at said second terminal generates the second structured-data signal with a second identification signal; and

said verifying step verifies the second identification signal.

21. The method as set forth in claim 16 wherein said transforming step at said first terminal includes an exponentiation of the first key-encryption-key signal and the structured-data signal modulo a modulus number, for generating the first ciphertext signal.

22. The method as set forth in claim 16 wherein said transforming step at said second terminal includes an exponentiation of the second key-encryption-key signal and the structured-data signal modulo a modulus number, for generating the second ciphertext signal.

23. The method as set forth on claim 16 further comprising the steps of:

generating at a third terminal in response to receiving the request signal a third key-encryption-key signal and a third structured-data signal;

transforming at said third terminal, using the public-key-encryption algorithm, the third key-encryption-key signal and the third structured-data signal to a fourth ciphertext signal;

transmitting the fourth ciphertext signal over a communications channel;

decoding at said network center, using a public-key-decryption algorithm, the fourth ciphertext signal, thereby generating the third key-encryption-key signal and the third structured-data signal;

verifying at said network center the third structured-data signal and generating a verification signal;

transforming at said network center using the classical-key-encryption algorithm, the third key-encryption-key signal and the second key-encryption-key signal to a fifth ciphertext signal;

transmitting the fifth ciphertext signal over said communications channel; and

decoding at said third terminal, using a classical-key-decryption algorithm and the third key-encryption-key signal, the fifth ciphertext signal, thereby generating the second key-encryption-key signal.

24. A method for establishing cryptographic communications comprising the steps of:

generating a first key-encryption-key signal;

transforming, using a public-key-encryption algorithm, the first key-encryption-key signal to a first ciphertext signal;

generating a second key-encryption-key signal;

transforming, using the public-key-encryption algorithm, the second key-encryption-key signal to a second ciphertext signal;

decoding, using the public-key-decryption algorithm, the first ciphertext signal and the second ciphertext signal, thereby generating the first key-encryption-key signal and the second key-encryption-key signal;

transforming, using a classical-key-encryption algorithm, the first key-encryption-key signal and the second key-encryption-key signal to a third ciphertext signal; and

decoding, using a classical-key-decryption algorithm and the first key-encryption-key signal, the third ciphertext signal thereby generating the second key-encryption-key signal.

25. The method for establishing cryptographic communications as set forth in claim 24 further comprising the steps of:

generating a first structured-data signal; and

transforming the first key-encryption-key signal and the first structured-data signal to the first ciphertext signal.

26. The method for establishing cryptographic communications as set forth in claim 25 further comprising the steps of:

verifying the first structured-data signal and generating a verification signal; and

transforming in response to the verification signal, using the classical-key-encryption algorithm, the first key-encryption-key signal and the second key-encryption-key signal to the third ciphertext signal.

27. The method for establishing cryptographic communications as set forth in claim 24 further comprising the steps of:

generating a second structured-data signal; and

transforming the second key-encryption-key signal and the second structured-data signal to the second ciphertext signal.

28. The method for establishing cryptographic communications as set forth in claim 27 further comprising the steps of:

verifying the second structured-data signal and generating a verification signal; and

transforming in response to the verification signal, using the classical-key-encryption algorithm, the first key-encryption-key signal and the second key-encryption-key signal to the third ciphertext signal.

29. The method for establishing cryptographic communications as set forth in claim 24 further comprising the steps of:

generating a request signal; and

generating, in response to the request signal, the second key-encryption-key signal.

30. The method for establishing cryptographic communications as set forth in claim 24 wherein said step of transforming using the public-key-encryption algorithm includes:

an exponentiation of the first key-encryption-key signal modulo a modulus number.

31. The method for establishing cryptographic communications as set forth in claim 24 wherein said step of transforming using the public-key-encryption algorithm includes:

an exponentiation of the ciphertext signal modulo a modulus number.

32. A method for establishing cryptographic communications with a first terminal and a second terminal and using a network center, comprising the steps of:

encoding a first key-encryption-key signal, r.sub.1, by transforming said first key-encryption-key signal to a first ciphertext signal by computing r.sub.1.sup.e (mod n), wherein e is a public key of said network center and n is a modulus number;

decoding the first ciphertext signal by computing (r.sub.1.sup.e (mod n)).sup.d (mod n) wherein d is a secret key of said network center;

encoding a second key-encryption-key signal, r.sub.2, by transforming said second key-encryption-key signal to a second ciphertext signal by computing r.sub.2.sup.e (mod n);

decoding the second ciphertext signal by computing (r.sub.2.sup.e (mod n)).sup.d (mod n) wherein d is the secret key of said network center;

encoding the second key-encryption-key signal and the first key-encryption-key signal to generate a third ciphertext signal; and

decoding the third ciphertext signal with the first key-encryption-key signal.

33. The method as set forth in claim 32 further comprising the steps of:

generating a third key-encryption-key signal;

transforming, using the public-key-encryption algorithm, the third key-encryption-key signal to a fourth ciphertext signal;

decoding, using the public-key-decryption algorithm, the fourth ciphertext signal, thereby generating the third key-encryption-key signal;

transforming, using a classical-key-encryption algorithm, the first key-encryption-key signal and the third key-encryption-key signal to a fifth ciphertext signal; and

decoding, using a classical-key-decryption algorithm and the first key-encryption-key signal, the fifth ciphertext signal thereby generating the third key-encryption-key signal.

34. A method for establishing cryptographic communications comprising the steps of:

generating a first key-encryption-key signal;

transforming, using a public-key-encryption algorithm, the first key-encryption-key signal to a first ciphertext signal;

generating a second key-encryption-key signal;

transforming, using the public-key-encryption algorithm, the second key-encryption-key signal to a second ciphertext signal;

decoding, using the public-key-decryption algorithm, the first ciphertext signal and the second ciphertext signal, thereby generating the first key-encryption-key signal and the second key-encryption-key signal;

transforming, using a classical-key-encryption algorithm, the first key-encryption-key signal and the second key-encryption-key signal to a third ciphertext signal; and

decoding, using a classical-key-decryption algorithm and the second key-encryption-key signal, the third ciphertext signal thereby generating the first key-encryption-key signal.

35. A method for establishing cryptographic communications with a first terminal and a second terminal and using a network center, comprising the steps of:

encoding a first key-encryption-key signal, r.sub.1, by transforming said first key-encryption-key signal to a first ciphertext signal by computing r.sub.1.sup.e (mod n), wherein e is a public key of said network center and n is a modulus number;

decoding the first ciphertext signal by computing (r.sub.1.sup.e (mod n)).sup.d (mod n) wherein d is a secret key of said network center;

encoding a second key-encryption-key signal, r.sub.2, by transforming said second key-encryption-key signal to a second ciphertext signal by computing r.sub.2.sup.e (mod n);

decoding the second ciphertext signal by computing (r.sub.2.sup.e (mod n)).sup.d (mod n) wherein d is the secret key of said network center;

encoding the second key-encryption-key signal and the first key-encryption-key signal to generate a third ciphertext signal; and

decoding the third ciphertext signal with the second key-encryption-key signal.

BACKGROUND OF THE INVENTION

This invention relates to digital mobile communications systems and more particularly, to a method and system employing a protocol for establishing a secure secret key between two or more terminals through a network center.

1. Related Patents

This invention employs public-key-encryption concepts as disclosed in U.S. Pat. No. 4,200,770 entitled "Cryptographic Apparatus and Method", to W. Diffie and M. E. Hellman Apr. 29, 1980; U.S. Pat. No. 4,405,829 entitled "Cryptographic Communications System and Method", to R. Rivest, A. Shamir and L. Adleman, Sep. 20, 1983; and, U.S. Pat. No. 4,424,414, entitled "Exponentiation Cryptographic Apparatus and Method", to S. C. Pohlig and M. E. Hellman, which are all expressly incorporated herein by reference.

2. Description of the Prior Art

Awareness of the value of information together with advances in modern state-of-the-art telecommunications technologies including personal computers, local area networks, distributed data bases, packet radio, satellite teleconferencing, electronic mail, and electronic funds transfer, has stimulated and increased awareness of the vulnerability of communications links to intercept and of the susceptibility of databases to exploitation and tamper. This same telecommunications revolution has made the wide spread availability of technology for implementing techniques which can provide authenticated communications that also can be made secure against eavesdropping or tampering.

Prime users of a secure network of communicators include the banking community who has a need for ensuring that funds, electronically transferred, are sent correctly: a message authentication problem. Similarly, the stocks and securities community which operates on a computer network, has a requirement that the buy and sell of stocks are authentically sent to and from the correct person.

In response to this revolution and awareness, communicators increasingly have become aware of communications privacy and security. A technical solution for providing security against both eavesdropping and the injection of illegitimate messages, includes cryptography. Two generic approaches to key distribution are classical cryptographic techniques and public key cryptographic techniques. Classical cryptography requires that for ensuring secure communications, communicators must have keys that are identical. The encryption key is used to "lock" or secure the messages and a receiver must have an identical key to "unlock" or decrypt the messages. A problem arises with key distribution in a large network of communicators who wish to communicate with each other securely.

A major problem with classical cryptographic techniques is key distribution in a large network which requires n(n-1)/2 keys for n nodes. As shown in FIG. 1, a message, M, which is encrypted with an encryption key E.sub.A, into a cipher text, C, requires having the key distributed over a private channel to the receiver. This requirement includes generating, storing, distributing, destructing and archiving of key variables which are essential elements of encipherment. Typically, a courier is responsible for distributing the keys over the private channel. For a large network of communicators, this requires a courier to distribute the key to many users. Further, if all communicators in the network are using the same key, and if the key is compromised by any one communicator, then the whole network is compromised.

The advent of inexpensive electronics hardware has facilitated means for providing the security of communications. In computer communications networks in particular, public key cryptography, which may be viewed as a multiple access cryptographic technique, provides a relatively inexpensive means for distributing keys among communicators and ensuring communications privacy and message authentication in comparison to conventional cryptographic techniques.

Public Key Cryptographic Concepts

Public key cryptographic systems are based on the trapdoor one-way function. Consider first, the concept of a one-way function. A one-way function is an easily computed function whose inverse is computationally infeasible to find. That is, for a Y=f(X), given an X, Y is easy to compute. However, given a Y, X is difficult to compute.

The Diffie-Hellman public key cryptographic systems are based on exponentiation of a number p, in a Galois field, GF(p).

The basic computations for the Diffie-Hellman public key encryption are as follows: ##EQU1## where X is the plain-text, Y is the ciphertext, E is the secret encryption exponent and D is the secret decryption exponent.

A key management system based on the work of Diffie-Hellman and Hellman-Pohlig, and independently on the work of Merkle, is two pronged: first, a common secret number is established between two communicators, without either communicator having exchanged any secret information. Second, this common secret number is then used as a key in conventional cryptographic systems, for example, employing the Data Encryption Standard (DES), for enciphering messages. The security of the Diffie-Hellman system rests on the difficulty of performing discrete logarithms in the finite field of integers modulo a very large prime number, p, denoted GF(p). A basic conjecture is that exponentiation in GF(p) is a one-way function for a large prime number p. Given X is an integer, and an X and N, it is easy to compute the equation Y=X.sup.N modulo p, where 0.ltoreq.X.ltoreq.p. Given Y and X it is hard to compute N in the above equation, because it is computationally hard to take a discrete logarithm, N=log.sub.X (Y), in GF(p). Indeed, for the best known algorithm for finding discrete logarithms, GF(p), it is believed to be impractical to compute the discrete logarithm on a Cray machine when p is a 1000-bit prime number. In contrast, it takes a fraction of a second to compute the exponentiation, GF(p). Encryption and decryption are both done with exponentiation.

For example, an encryption exponent E and decryption exponent D can be derived using Euler's Theorem from number theory to satisfy

D.multidot.E=1 modulo (p-1)

This is a necessary relationship for D to be the exponential inverse of E; that is, (X.sup.E).sup.D =1 modulo p. This relationship can be used to encrypt a message X, an integer less than p, by the exponentiation operation

Y=X.sup.E modulo p

and to decrypt this message by another exponentiation operation,

X=Y.sup.D modulo p.

Here E and D are kept secret and E can be obtained easily from D and vice versa. Given p, X, and Y satisfying the above two equations it is computationally difficult to find the secret encryption exponent E for a large prime number p, due to the difficult problem of taking discrete logarithms in GF(p). For a prime number p of 512 bits it is estimated to be many times more difficult to perform a discrete logarithm than a brute force attack on the DES algorithm.

An important property of the encryption and decryption function based on exponentiation in GF(p) is the commutative property where

(X.sup.E.sbsp.1 modulo p).sup.E.sbsp.2 modulo p=(X.sup.E.sbsp.2 modulo p).sup.E.sbsp.1

modulo p.

This property allows two communicators in a network, hypothetically terminal A and terminal B, to share a secret number by only exchanging non-secret numbers.

Assume the entire network has fixed known constants (not necessarily secret):

p=prime number

and a is any integer between 0 and p-1.

For terminal A and terminal B to obtain a shared secret number, terminal A randomly generates a secret number,

X.sub.A =terminal A's secret number,

and computes a corresponding public number,

Y.sub.A =a.sup.X.sbsp.A modulo p.

Terminal B also randomly generates a secret number,

X.sub.B =terminal B's secret number,

and computes a corresponding public number,

Y.sub.B =a.sup.X.sbsp.B modulo p.

For a large prime number, it practically is impossible to obtain the secret numbers from the public numbers.

Terminal A and terminal B can share a secret number that is unique to them while only exchanging non-secret public numbers. Specifically, suppose terminal A sends his public number, Y.sub.A, to terminal B while terminal B sends his public number, Y.sub.B, to terminal A. By the commutative property, terminal A can compute

Z=Y.sub.B.sup.X.sbsp.A modulo p

while terminal B can compute the same number by

Z=Y.sub.A.sup.X.sbsp.B modulo p.

Next terminal A and terminal B compute Z*, the reciprocal of Z, such that

Z.multidot.Z*=1 modulo (p=1).

In a particular Diffie-Hellman system the prime number p is chosen to satisfy

p=2q+1

where q is a prime number. Then if Z is an odd integer,

Z*=Z.sup.q-2 modulo (p-1)

which is another exponentiation. If Z is not an odd number then terminal A and terminal B first can convert Z to an odd number and then compute Z*.

The shared secret numbers Z and Z* are used by terminal A and terminal B to encrypt and decrypt messages where E=Z is the encryption exponent and D=Z* is the decryption exponent. For most encrypted network applications terminal A and terminal B would exchange encryption keys for conventional encryptors using Z and Z*. This is because encryption with exponentiation may be too slow for most data networks.

The basic Diffie-Hellman technique is illustrated in FIG. 2, with secret numbers shown enclosed inside boxes. For this illustration, the secret numbers are never transmitted in the clear or delivered by couriers. A message M sent by terminal A and terminal B can be keys for conventional encryptors.

It may be desirable for both terminal A and terminal B to contribute independent random bits to the generation of keys. For example, terminal A and terminal B can independently generate random bits to form messages which they exchange securely using Z and Z* as shown above. The final encryption keys can then be some function of these independently and randomly generated bit sequences such as taking bit by bit modulo 2 addition of the two bit sequences. Another possibility is for terminal A and terminal B to independently generate new secret and public numbers, exchange these public numbers, compute a new shared secret number S, and combine this with the original shared secret number Z to form secret encryption keys. For example, keys might be of the form M=Z.multidot.S modulo p.

RSA System

RSA is a public key encryption technique invented by Rivest, Shamir, and Adleman, supra. The security of the RSA system rests on the difficulty of factoring integers into their prime components. As with the Diffie-Hellman system, encryption and decryption are both done with exponentiation. In the RSA system, however, the modulus is not a prime number as in the Diffie-Hellman technique. Instead, the modulus is a product of two secret prime numbers and for security the modulus must be unique to each user in the network.

Using the RSA system, terminal A and terminal B can exchange secret messages by first exchanging non-secret public numbers. Terminal B first randomly generates two large secret prime numbers,

(p.sub.B,q.sub.B)=terminal B's secret prime numbers,

a secret decryption exponent,

D.sub.B =terminal B's secret decryption exponent,

and a non-secret public encryption exponent,

E.sub.B =terminal B's public encryption exponent

which satisfies

E.sub.B .multidot.D.sub.B =1 modulo [(p.sub.B -1)(q.sub.B -1)].

In general, to obtain D.sub.B from E.sub.B, one would have to know the prime numbers p.sub.B and q.sub.B. Hence without knowledge of terminal B's secret prime numbers, knowing the public encryption exponent E.sub.B does not reveal the decryption exponent D.sub.B. In order for the RSA system to be "strong", each of the numbers p-1 and q-1 should have large prime factors.

For terminal A to send a secret message to terminal B, terminal B must send to terminal A his public numbers

E.sub.B and N.sub.B =p.sub.B q.sub.B.

Then terminal A can send the message X by exponentiation,

Y=X.sup.E.sbsp.B modulo N.sub.B

Only terminal B can decrypt this message by similar exponentiation with his secret decryption exponent,

X=Y.sup.D.sbsp.B modulo N.sub.B

In addition, terminal B can send a certified non-secret message M to terminal A by sending his,

C=M.sup.D.sbsp.B modulo N.sub.B

terminal A can obtain M from

M=C.sup.E.sbsp.B modulo N.sub.B

since she knows terminal B's public numbers. In fact, anyone that has terminal B's public numbers can obtain the message M from C. Only terminal B, however, could have computed C from M. Upon converting C to M, terminal A or anyone else who has terminal B's public numbers knows that the message M came from terminal B. Thus, the message M has been signed (authenticated or certified) by terminal B in this procedure. Terminal A also can randomly generate secret prime numbers,

(p.sub.A,q.sub.A)=terminal A's secret prime numbers,

a secret decryption exponent,

D.sub.A =terminal A's secret decryption exponent,

and a non-secret public encryption exponent,

E.sub.A =terminal A's public encryption exponent,

which satisfies (using Euler's Theorem)

E.sub.A .multidot.D.sub.A =1 modulo [(p.sub.A -1)(q.sub.A -1)].

If terminal A and terminal B were to exchange their public numbers then they can exchange secret signed messages in both directions. For a network of encryptors these secret messages are typically keys for conventional encryptors. FIG. 3 illustrates the RSA technique.

Note that in the RSA technique, every user in the system must have a distinct composite number made up of two large prime numbers; whereas, in the Diffie-Hellman technique a single prime number suffices for the entire network. This latter technique simplifies the computations for encryption and decryption since all the users in the network perform their computations modulo a single number, p.

OBJECTS AND SUMMARY OF THE INVENTION

An object of the present invention is to provide a protocol for establishing secure secret keys between two or more terminals communicating through a network center.

Another object of the present invention is to remove key management at the network center.

A further object of the present invention is to enable hardware-limited user terminals to obtain a common secret key in a reasonable time.

An additional object of the present invention is to provide a common secret key for a plurality of users in a network.

A still further object of the present invention is to provide secret keys for users in a mobile radio cellular network.

According to th