Remote Key Manipulations for Over-the-Air Re-Keying

This invention relates generally to digitally encrypted voice signals and more particularly to a method for providing a secure trunked communications system by changing a key used to encrypt and decrypt the voice signal.

Secure communications systems are known in the art. Such systems typically render a voice message unintelligible to prevent unauthorized reception. To accomplish this the voice message can be digitized and processed through an encryption device to produce a resulting signal that appears to be random (or pseudo-random) in nature. Such a signal appears like noise to unauthorized receivers and discourages intelligible reception. The particular encryption algorithm used by the encryption device maybe a proprietary algorithm or may be based on a standard such as the Data Encryption Standard (DES) promulgated by the United States National Bureau of Standards. In a typical encryption device a secret key is utilized in conjunction with a cipher algorithm to encrypt and decrypt messages. The keys may be changed or rekeyed as frequently as desired in order to enhance security.

It is sometimes however desirable in such voice protection or secure systems to maintain different levels of security. A supervisor for example may wish to deliver a scrambled message to one user or a set of users without communicating with another set of users on the same channel. One method of accomplishing this is to call a remote unit in the clear (without encryption) and identify a particular key that is to be used to unscramble an ensuing message. Key identification is used to identify which one of a multiplicity of keys was used to encrypt the message and also to keep the access time down to a minimum. This however requires vast memory storage of the keys in the subscriber unit especially if the keys are to be unique and are to be changed frequently.

Such secure communication is a feature mainly available on conventional communications systems that make use of dedicated channels. This has occurred in part because the encrypted signal itself comprises a 12 kilo bits per second (KBS) data string that requires substantially all of the available spectrum of the assigned channel. Currently conventional communications systems use a secure communication method which is performed by sending encrypted information about the key to be used via signalling data. This key information includes the transmission of the actual key having multiple (64) bits for DES.

Conventional channel allocation systems however do not represent optimum usage of the increasingly crowded communications spectrum. Trunked systems are well recognized to make more efficient usage of available channel allocations. Such systems typically include at least one central controller or fixed end that controls channel allocation between various subscriber units (as used herein subscriber units includes all remote transceiving devices such as mobile units installed in vehicles, other controlled stations, portable devices, and radio frequency (RF) linked telephones).

However, far too much information is sent using the conventional remote key information method for it to be possible to use the control channel of a trunked system. Especially when a fleet of subscriber units or radios have to be rekeyed, a lot of air time would be consumed on the control channel in a trunked system, rendering it effectively immobilized for quite some time. Such a signal thus presents compatibility problems when compared to the trunked channel maintenance protocol which includes control signals such as connect tones, handshake signals, acknowledge tones, and disconnect tones.

Accordingly there exists a strongly felt need for a combined secure trunked communication system that is remotely rekeyable without taking up too much system access time or subscriber memory space.

Accordingly, it is an advantage of the present invention to provide an efficient method for securing a trunked communications system by remotely varying the key to decrypt a voice signal.

Briefly, according to the invention, a method of remotely changing an original voice encryption key in a secure radio comprises transmission by a central controller to the secure radio of a digital word representing a selective operation to be performed on the original voice encryption key stored in the radio. In response to the digital word, the radio performs the operation on the original voice encryption key to generate a current voice encryption key.

FIG. 1 is a flowchart depicting a method for changing a key by a subscriber unit in accordance with the present invention.

FIG. 2 a flowchart depicting a method for generating a key change command by a central controller in accordance with the present invention.

FIG. 3 a schematic diagram depicting a method for generating a varying key in accordance with the present invention.

Referring to FIGS. 1 and 2, a flowchart depicting the steps taken in a central controller 20 and in each one of a plurality of remote subscriber units or radios 10 communicating over the air via a trunking channel or any other secure radio frequency channel with the central controller 20. As in the prior art, the subscriber unit 10 has already been loaded, hard wired or programmed over-the-air by the central controller 20 with an initial binary key, K.sub..phi.. In this invention, the major difference is that the sequence of bits loaded into the radio originally will not necessarily be the actual key used to encrypt and decrypt voice or data information. The working, current, or new key would be the result of some operation on the initial key sequence. This operation could be as simple as a rotation of the sequence through some specified number of positions. The exact number would be sent by the controller in a "key-switch outbound signal word (OSW)" or key change command, which is a control signal sent by the controller in a trunking system.

The subscriber unit 10 in a decision block 2 determines whether the central controller 20 has transmitted a key change command for rekeying. If not, the subscriber unit 10 determines in another decision block 4 whether the user or operator of the subscriber unit wishes to request a key change to obtain better security. If rekeying is not desired at this time, the subscriber unit 10 returns to the initial decision block 2 awaiting further action.

If yes, the subscriber unit 10 transmits a key change request. The key request includes data identifying the subscriber unit to the central controller 20. On receipt of the key change request from the subscriber unit 10, the central controller 20 answers "yes" in a decision block 14 to the question as to whether the subscriber units or radios need to be rekeyed. If it is determined by the central controller 20 that a new key need not be generated, the central controller taking the no branch of the decision block 14 returns to the initial accessing point of the same block to await the next key change request from the subscriber unit 10.

Assuming rekeying was desired, in step 21, a key change command with an operational code (OP code) along with data (including X) is transmitted to the subscriber unit 10 by the central controller 20. The subscriber unit 10 will now return to the decision block 2 to determine whether the central controller 20 has transmitted the key change command. If it has, in step 24, the subscriber unit 10 will decode the OP code and look up the operation in its memory, which may be a mere rotation or a more involved function, F(X), required to change the original key, K.sub..phi., in accordance with a method to be described later. The new encryption key is then formed at step 26 by the subscriber unit 10 performing the operation specified by the OP code on the old or original key K.sub..phi..

After rekeying in step 26, the subscriber unit 10 will use the new encryption key for encryption of data/voice or decryption of data/voice according to an encryption algorithm such as the National Bureau of Standards encryption/decryption algorithm (DES) which is the Federal Information processing standard approved by the U.S. Department of Commerce. This standard National Bureau of Standards algorithm may later be used to decrypt the encrypted data or voice to retrieve the voice or data in its original form. Using the function specified by the OP code that was transmitted by the central controller 20, the subscriber unit 10 is thus able to form a new or current encryption or decryption key. An acknowledgement that the new or current key has been formed according to the method proscribed is then sent in step 28 to the central controller 20 by the subscriber unit 10. Finally, the subscriber unit 10 will return to the original decision block 2 to start the sequence anew if a new key is requested or more iteration of functions is desired on the original key to form a new key from the current key. This new key is then stored for use in encryption and decryption of subsequent voice communications with the central controller 20 or with other subscriber units using the same key.

In decision block 32, the central controller 20 determines whether the subscriber unit or radio 10 had acknowledged the key change. If yes, the sequence of operations returns to the original decision block 14 to await new key change requests. If no, a decision block 34 determines whether a predetermined number of allowances to retry the key change has been exhausted. If not, the retry sequence is tried again by returning to step 21 to transmit a key change command with the same operational code. However, if the allowable retries have been exhausted, the central controller 20 places the radio's identification (ID) in a list of radios that need to be rekeyed with the same or previous key command when the radio requests a key change after coming back in-range or being re-activated (assuming the radio is now out-of-range or turned off to be unable to acknowledge). Finally, the central controller 20 returns to the original decision block 14 to await for new key change requests.

Referring to FIG. 3, a schematic diagram detailing the generation of the new key K.sub.NEW from the information which was transmitted to the subscriber unit 10 by the central controller 20 is shown. The key change command sent by the central controller 20 includes a digital word or key switch OSW 42. The digital word 42 comprises an OP code 44 and some data 46 (which may include a variable number X). This digital word 42 determines the radio's actions to form the new key. As described previously, the method of generating the new key includes the use of functions or operations associated with a particular operational code to be performed on the original key. A list 52 of what the different OP codes could represent is shown in FIG. 3 as an example.

The new key may be simply formed by manipulating the original key through a rotation of the original key sequence through some specific number of positions, X, sent by the controller 20 in the data field 46 of the key change command digital word 42. For simplicity, assume that the following 8 bit key has been originally loaded into the radio or subscriber unit 10 as the original key:

If the decoded OP code 44 is translated to a 1 on the list 52 (which contains the command to rotate right X=3 positions as defined by the OP code 44 and the X=3 in the data field 46), then the following becomes the current or new key:

An 8 bit key was chosen for simplicity but an actual key is usually much larger, often containing 64 bits. With 64 bits, it is appreciated that the number of possible keys obtainable through a single series of rotation commands is extremely large to enable changing keys frequently for better security. However, other methods for generating the new key with various operations or functions are also contemplated by the present invention. Certainly other arithmetic or logical operations individually or in combination can be used as well such as rotating left x-number of positions, shifting in data right or left, or ones or twos complimenting. One operation can be continued with another function or with multiple iteration of the same function to generate the new key from a current key.

If more variety or complexity is desired, then an operations table 54 can be used. In this case the data contained in the key change command digital word or key switch OSW 42 is simply an index into a table contained in the subscriber unit's memory which will access the function and/or data to be chosen. Each entry into the table will specify a different operation to be performed on the radio's key. For example, the following operations may be used on the original key: and-ing, or-ing, or exclusive or-ing with the previous key or with data that was previously stored or transmitted in the data field 46 of the OSW digital word; and/or adding to or substracting from the previous key. Any unknowns or variables listed necessary for the decoded OSW OP code functions are supplied by the data field 46 of the OSW digital word 42. On the other hand, the data mentioned in the table entries is contained within the table itself which can be stored in the radio.

For example, the OP code may be a table entry to specify the exclusive or-ring of data with the original key. In this case, a translated OP code representing 7 with an index of 6 may specify a table entry that is already stored in a memory in the subscriber unit 10. On the other hand, the address of the table entry X and data can be transmitted by the central controller 20 in the key change command as data 46.

It is to be appreciated that the actual decoding scheme of the decrypting algorithm is not affected. No major hardware changes are needed and only moderate software changes are required to modify the decrypting key. By varying the keys, this effectively increases the capability of a secure trunking system.

This modification scheme is adaptable to a wide variety of radios. For instance while a higher tier radio having more memory may make use of every Op code function including the table entries, a lower tier radio or radio with tighter memory constraints may wish to utilize only the transmitted operations and not implement any table operations at all. Finally, to increase the variety of possible operations occurring in the field, different subscriber units could have completely unrelated operations tables. Those tables could even be programmable so that they could be changed at regular intervals if desired.

To provide for the case where one or more members of the group whose key was switched was out-of-range or powered off at the time of the key switch, a refresh OSW or digital word will need to be sent. This could simply be the same previous key switch OSW digital word 42 sent out by the central 20 according to some predetermined schedule. To avoid the problem of one subscriber unit missing one key switch or key change command in a series of key switch commands to arrive at the final or new key, all key switch operations may operate on the original key sequence of bits rather than on the last working sequence or previous key. For example, a second command specifying a right rotation of 2 positions would be performed on the original key.

In this manner, the radio will always be rekeyable no matter how long it has been out-of-range or off, as long as the subscriber unit has retained its original base key or original key and the table entries using the previous key as an operator are not used.

In summary, after being loaded with an original key, K.sub..phi., the subscriber unit 10 can generate a new key through a pre-defined series of steps transmitted via one or more key change commands (based on the decoded OP code) that was sent by the central controller 20. Any Boolean algebraic function or other mathematical methods recognized in the art may operate on the original key to form the new key. Because the present invention of remote key manipulation requires much less transmission time in order to perform the key switch or change then the conventional method giving full key information, the present invention can use the existing control channel rather than a new data channel in a trunking system. Hence, this remote key manipulation can be implemented at the central controller with only a moderate amount of central and console software effort.