Abstract:
The present invention provides methods and apparatuses for implementing communications privacy on a class of two-way wireless control communications. The methods and apparatuses of the present invention are cryptographic in nature and are built on a symmetric cryptographic algorithm structure. The cryptographic algorithm structure generates keytext on a frame-by-frame basis and both directions of the communications control link are served by the same keytext frames. The methods and apparatuses of the present invention utilize a single outbound/inbound cryptographic generator, such as a shrinking generator or the like designed using six-sigma tools in order to ensure, within a predetermined probability, that the non-fixed encryption time does not cause operational problems.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates generally to instrumentation privacy methods and apparatuses. More specifically, the present invention relates to methods and apparatuses for implementing communications privacy on a class of two-way wireless control communications. The methods and apparatuses of the present invention are cryptographic in nature and are built on a symmetric cryptographic algorithm structure. The cryptographic algorithm structure generates keytext on a frame-by-frame basis and both directions of the communications control link are served by the same keytext frames.  
         BACKGROUND OF THE INVENTION  
         [0002]    Communications privacy has become increasingly important to the protection of business interests in a competitive global economy. This is made difficult by the widespread use of wireless communications and the like. Such wireless communications are often interceptible and exploitable beyond any existing communications control mechanisms. Therefore, it is prudent for businesses and others to seek and institute new, cost-effective electronic protective measures that allow the efficiency of the host processes to be maintained.  
           [0003]    One relatively straightforward communications control mechanism is the use of encryption technology to protect vital, competitively valuable data and information from successful interception and subsequent exploitation. One significant problem faced by communications engineers and the like in attempting to provide such protection, however, is the relatively high speed that such encryption technology requires. This problem is compounded by the labor overhead required to institute and maintain the proper operation of such communications control mechanisms.  
           [0004]    Expanding upon this problem, short-range wireless equipment control links and the like are becoming increasingly prevalent. Such control links, and the associated applications, require high-speed two-way communications with low latency. Many of these control links utilize star-like communications flows, wherein a central module broadcasts messages to outlying modules and the outlying modules respond to the central module in a pre-ordered fashion. These messages often contain vital, competitively valuable data and information related to products, services, installations, and the like. Typically, this sort of problem has been approached using cryptographic architectures wherein there is a separate encryption unit for outbound messages and a separate encryption unit for inbound messages.  
           [0005]    What is needed are instrumentation privacy methods and apparatuses that protect these control links and the data and information transmitted on them from interception and subsequent exploitation. What is also needed are instrumentation privacy methods and apparatuses that are relatively simple to install, set up, and maintain, requiring only minimal labor overhead and not significantly impacting communications latency. Accordingly, what is needed are instrumentation privacy methods and apparatuses that utilize a single outbound/inbound cryptographic generator, such as a shrinking generator or the like designed using six-sigma tools in order to ensure, within a predetermined probability, that the non-fixed encryption time does not cause operational problems.  
         BRIEF SUMMARY OF THE INVENTION  
         [0006]    As described above, the present invention provides methods and apparatuses for implementing communications privacy on a class of two-way wireless control communications. The methods and apparatuses of the present invention are cryptographic in nature and are built on a symmetric cryptographic algorithm structure. The cryptographic algorithm structure generates keytext on a frame-by-frame basis and both directions of the communications control link are served by the same keytext frames. The methods and apparatuses of the present invention utilize a single outbound/inbound cryptographic generator, such as a shrinking generator or the like designed using six-sigma tools in order to ensure, within a predetermined probability, that the non-fixed encryption time does not cause operational problems.  
           [0007]    In one embodiment of the present invention, an instrumentation privacy apparatus includes a central module and an outlying module. The central module is operable for transmitting a first synchronous packet of data to the outlying module and the outlying module is operable for receiving the first synchronous packet of data from the central module. The outlying module is operable for transmitting a second synchronous packet of data to the central module and the central module is operable for receiving the second synchronous packet of data from the outlying module. The instrumentation privacy apparatus also includes a common keytext generator operable for according privacy to both the first synchronous packet of data and the second synchronous packet of data.  
           [0008]    In another embodiment of the present invention, an instrumentation privacy method includes providing a central module and providing an outlying module. The instrumentation privacy method also includes transmitting a first synchronous packet of data to the outlying module and receiving the first synchronous packet of data from the central module. The instrumentation privacy method further includes transmitting a second synchronous packet of data to the central module and receiving the second synchronous packet of data from the outlying module. The instrumentation privacy method still further includes providing a common keytext generator operable for according privacy to both the first synchronous packet of data and the second synchronous packet of data.  
           [0009]    In a further embodiment of the present invention, an instrumentation privacy method includes providing an m-bit shift register having a first clock and providing an n-bit shift register having a second clock. The instrumentation privacy method also includes setting the first clock and the second clock to a primary clock. The instrumentation privacy method further includes providing a bit selection module operable for receiving a first bit from a first modulo-two combiner and a second bit from a second modulo-two combiner. If the first bit is equal to zero, the bit selection module is operable for discarding the second bit and, if the first bit is equal to one, the bit selection module is operable for passing the second bit into a keytext frame and issuing a frame block clock pulse to the keytext frame. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0010]    [0010]FIG. 1 is a schematic diagram illustrating a typical synchronous star network associated with the methods and apparatuses of the present invention;  
         [0011]    [0011]FIG. 2 is a schematic diagram illustrating a typical synchronous packet framing sequence associated with the methods and apparatuses of the present invention;  
         [0012]    [0012]FIG. 3 is a schematic diagram illustrating one embodiment of a keytext generator operable for providing keytext for the encryption/decryption of a data frame;  
         [0013]    [0013]FIG. 4 is a schematic diagram illustrating one preferred embodiment of a cryptographic instrumentation privacy apparatus of the present invention;  
         [0014]    [0014]FIG. 5 is a schematic diagram illustrating the components of the cryptographic instrumentation privacy apparatus of the present invention involved in a pre-operation mode;  
         [0015]    [0015]FIG. 6 is a plot of a clock ratio associated with the instrumentation privacy methods and apparatuses of the present invention for three values of a parameter S (standard deviations or sigmas);  
         [0016]    [0016]FIG. 7 is a plot illustrating a distribution of ones produced by an m-sequence according to x 41 +x 3 +1 for intervals of 2,000 clock times (100,000 trials each starting a recursion at a randomly chosen setting);  
         [0017]    [0017]FIG. 8 is a plot illustrating a distribution of ones produced by an m-sequence according to x 2,281 +x 715 +1 in successive intervals of 2,000 clock times (100,000 trials, but starting a recursion only once at a randomly chosen point);  
         [0018]    [0018]FIG. 9 is a schematic diagram illustrating the components of the cryptographic instrumentation privacy apparatus of the present invention involved in an additional pre-operation mode;  
         [0019]    [0019]FIG. 10 is a plot of {max(n)} (upper curve) and {min(n)} (lower curve) versus P for m=2,281 and c=30;  
         [0020]    [0020]FIG. 11 is a plot of {Δ(n)}; and  
         [0021]    [0021]FIG. 12 is a plot illustrating the distribution of the number of bits different between two initial shift register contents. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0022]    An important class of problems associated with conventional instrumentation privacy methods and apparatuses is illustrated with reference to the synchronous star network  10  of FIG. 1. A central module  12  periodically transmits a synchronous packet of data to outlying module  1   14 , outlying module  2   16 , . . . , and outlying module R  18 . The outlying modules  14 , 16 , 18  use the time boundaries of the central module&#39;s synchronous packets to determine the time boundaries for their transmissions to the central module  12 . The time boundaries for the R outlying modules&#39; synchronous packets are specified by, for example, a network installer prior to the commencement of communications. The time boundaries are assigned such that no two outlying modules  14 , 16 , 18  are transmitting at the same time, which would lead to a collision between outlying module synchronous packets. A typical synchronous packet framing sequence is illustrated in FIG. 2.  
         [0023]    Referring to FIG. 2, two sequential frames of data, frame i  20  and frame i+1 22, are illustrated. Transmissions from the central module  12  (FIG. 1) to the outlying modules  14 , 16 , 18  (FIG. 1) are labeled OUT and transmissions from the outlying modules  14 ,  16 ,  18  to the central module  12  are labeled IN 1 , IN 2 , . . . , and IN R, respectively. In this example, the i-th OUT synchronous packet precedes the i+1 st  outlying module R synchronous packet response.  
         [0024]    Both the transmissions from the central module  12  to the outlying modules  14 , 16 , 18  and the transmissions from the outlying modules  14 , 16 , 18  to the central module  12  are accorded privacy by the same keytext generator. FIG. 3 illustrates the frame keytext block  30  that is produced by the keytext generator  32 . The keytext supplied by the keytext generator  32  has previously been extracted from the keytext generator&#39;s keytext frame  40  (FIG. 4) and buffered, depending upon the status of the associated module (i.e., whether the associated module is the central module  12  (FIG. 1) or an outlying module  14 , 16 , 18  (FIG. 1)). The same keytext generator  32  is provided at the central module  12  and all outlying modules  14 , 16 , 18 . The keytext for the encryption/decryption of frame i  20  is bit-by-bit modulo two added to the appropriate contents of frame i  20  by the exclusive-or logic gate  34 . The exclusive-or logic gate  34  performs the following function:  
                                       INPUT LINE 1   INPUT LINE 2   EXCLUSIVE-OR OUTPUT                   0   0   0       0   1   1       1   0   1       1   1   0                  
 
         [0025]    For a transmission from the central module  12  to all of the outlying modules  14 , 16 , 18 , the keytext  36  is used to encrypt the OUT portion of the data frame and decrypt the IN portions of the data frame. For a transmission from the i-th outlying module, the keytext  36  is used to encrypt the i-th IN portion of the data frame and decrypt the OUT portion of the data frame.  
         [0026]    The components of the keytext generator  32  are illustrated in FIG. 4. In one preferred embodiment of the present invention, the keytext generator  32  is a shrinking generator, well known to those of ordinary skill in the art. It should be noted, however, that other suitable types of keytext generators may be utilized, as appropriate. The keytext generator  32  includes two shift registers  42 , 50  of m-bits length and n-bits length, respectively, with modulo-two feedback from stages whose contents are summed together and reduced by two modulo-two combiners  44 , 52 , respectively. The stages of a register whose contents are summed together are chosen such that a register with feedback will generate an m-sequence of length two to the number of stages in the register minus one. Appropriate stages for extracting content in order to create an m-sequence are specified by a primitive polynomial of a degree equal to the number of stages in the register, as is well known to those of ordinary skill in the art.  
         [0027]    The outputs of the two modulo-two combiners  44 , 52  are input into two multiplier logic gates  46 , 54 , respectively. A multiplier logic gate performs the following function:  
                                       INPUT LINE 1   INPUT LINE 2   MULTIPLIER OUTPUT                   0   0   0       0   1   0       1   0   0       1   1   1                  
 
         [0028]    The outputs of the two multiplier logic gates  46 , 54  are input into two exclusive-or logic gates  48 , 56 , respectively. The outputs of the two exclusive-or logic gates  48 , 56  are input into the two shift registers  42 , 50 , respectively.  
         [0029]    The keying variables for the shrinking generator consist of a secret m-bit binary vector denoted by KV 1  and a secret n-bit binary vector denoted by KV 2 . These keying variables are entered into and stored in two registers  60 , 62 , as illustrated in FIG. 5. Referring to FIGS. 4 and 5, there are two modes of the keytext generator  32 : (i) a pre-operation mode and (ii) a keytext generation mode. Each mode specifies the various control signals, C S , I S , C G , I G , and their respective settings.  
         [0030]    In the pre-operation mode, the central control module control signals C G =0 and C G =0. The input I S  is connected to the output  68  of an exclusive-or logic gate  66  (see FIG. 5). The two inputs to the exclusive-or logic gate  66  consist of the outputs of the keytext storage register KV 1   60  and a binary noise generator  64 . In the pre-operation mode, CLOCK 1  is clocked m-times, with the result that KV 1  is rotated end-around for m-steps and the keytext storage register KV 1   60  returns to its original setting. The binary noise from the binary noise generator  64  is broadcast to the outlying modules  14 , 16 , 18  (FIG. 1) via an output  70 , each of which adds the m-binary noise bits modulo-two to KV 1  and places the bit-by-bit mod 2 sum in the m-bit shift register  42 . The input IG is also connected to the output  76  of an exclusive-or logic gate  74  (see FIG. 5). The two inputs to the exclusive-or logic gate  74  consist of the outputs of the keytext storage register KV 2   62  and a binary noise generator  72 . In the pre-operation mode, CLOCK 2  is clocked n-times, with the result that KV 2  is rotated end-around for n-steps and the keytext storage register KV 2   62  returns to its original setting. The binary noise from the binary noise generator  72  is broadcast to the outlying modules  14 , 16 , 18  via an output  78 , each of which adds the n-binary noise bits modulo-two to KV 2  and places the bit-by-bit mod 2 sum in the n-bit shift register  50 .  
         [0031]    In the keytext generation mode, the clocks of both shift registers  42 , 50 , CLOCK 1  and CLOCK 2 , respectively, are set to a primary clock (PC). The control signals, C S , I S , C G , I G , are set according to: C S =1, I S =0, C G =1, and I G =0. The two shift registers  42 , 50  are clocked by the PC with feedback according to their respective primitive polynomials. The bits produced by the modulo-two combiners  44 , 52  are input to a bit selection module  58 . The bit selection module  58  operates as follows:  
         [0032]    If the bit from the output of the modulo-two combiner  44  is a zero, the bit selection module  58  discards the bit input from the modulo-two combiner  52  and the bit selection module  58  does not issue a frame block clock (FBC) pulse to the keytext frame  40 ;  
         [0033]    If the bit from the output of the modulo-two combiner  44  is a one, the bit selection module  58  passes the bit from the output of the modulo-two combiner  52  into the keytext frame  40  and issues an FBC pulse to the keytext frame  40 .  
         [0034]    This process continues until the keytext frame  40  has been filled from the bit selection module  58 . This will be the case after B-pulses from the FBC. When the keytext frame  40  has been filled, the contents of the keytext frame  40  are transferred to the register  30  (FIG. 3) and are ready to serve as the keytext for a encryption/decryption frame.  
         [0035]    Because the shrinking generator is not a fixed-time algorithm, the keytext for a given frame will not be ready unless there have been B-pulses from the FBC. On the average, the FBC pulse rate will be one-half the PC pulse rate. By increasing the PC pulse rate, B-pulses from the FBC may be assured and the keytext will be ready when it is needed.  
         [0036]    It should be noted that the shrinking generator utilized by the instrumentation privacy methods and apparatuses of the present invention does not incorporate a default mode but, rather, utilizes a statistical design technique to reduce the probability that the problems described above arise to below a predetermined probability threshold. This is done by recognizing that the output of the FBC is well modeled as a Bernoulli process with probability one-half, that is, the FBC emits a pulse at any given clock time with probability one-half and its output is independent of prior outputs. Therefore, the number of FBC pulses in C PC pulses is well modeled as a binomial distribution wherein the probability of the number of FBC pulses, x, associated with C PC pulses is 2 −C (x C ). For moderately large values of C, such as C=100 or more, this probability is well modeled by a normal distribution.  
         [0037]    What is needed is for C to be large enough so that the probability that x is greater than or equal to B is at least some predetermined probability P S . This probability may be achieved via the following process:  
         [0038]    1. Model x as a normal distribution with mean μ=C/2 and variance σ 2 =C/4;  
         [0039]    2. Determine the number of times, T, that the keytext frame  40  will be filled;  
         [0040]    3. Let p be the probability that the keytext frame  40  will be fully filled each of the T times;  
         [0041]    4. Determine the number of standard deviations or sigmas, S, required so that p is greater than or equal to P S ; and  
         [0042]    5. Given S and B, solve for C.  
         [0043]    Step (5) above is performed by first noting that:  
             S   =           C   2     -   B         C     2       .             (   1   )                               
 
         [0044]    This equation is solved to yield:  
             C   =         (       S   +         S   2     +     8      B           2     )     2     .             (   2   )                               
 
         [0045]    The ratio C/B is the number of PC clock pulses allocated per required keytext frame bit required to meet equations (1) and (2). This ratio is referred to as the clock ratio and is plotted in FIG. 6.  
         [0046]    An added refinement to the implementation described above includes filling the keytext frame  40  with randomly generated bits prior to developing keytext. As the keytext is developed and the register  40  is shifted, the random bits are shifted out. In the event that the register  40  has not been filled with keytext before that is required, the register contents are used as they are in a time of need. Such an event would result in errors in those messages using randomly generated bits.  
         [0047]    As described above, one problem associated with the shrinking generator is that it does not have a fixed time algorithm and it is unclear what measures should be taken to compensate for this. Thus, a frame of keytext data may not be ready when needed. As described above, the shrinking generator&#39;s operation may be cast in statistical terms and the shrinking generator&#39;s time may be modeled to finish as a Gaussian variable. The shrinking generator may also be initialized in a pre-operation mode, generating and transmitting a binary noise sequence before starting or restarting. Additionally, various parameters of the shrinking generator may be specified in order that it&#39;s behavior may be further modeled and it&#39;s non-fixed time behavior compensated for, as described below. A further pre-operation mode may be utilized that does not require the generation and transmission of binary random noise. Advantageously, this pre-operation mode allows explicit message sequencing information to be incorporated in the message header and used for pre-operation setup.  
         [0048]    As described above, the shrinking generator is built using m-sequences. An m-sequence is a binary sequence produced according to a primitive polynomial. Typically, an m-sequence has been used to simulate, and, conversely, may be modeled by, a balanced binary Bernoulli source—a source of ones and zeros with equal probability and no memory. Up to a point, such a simulation is appropriate and useful. However, when the sequence of bits generated by an m-sequence greatly exceeds the degree of the m-sequence&#39;s primitive polynomial, the correspondence to a balanced binary Bernoulli source is severely strained.  
         [0049]    This issue is important to the operation of the shrinking generator, especially in the mode wherein the shrinking generator is required to periodically produce a B-bit frame of keytext. If the frame is not ready when required, the system may fail. This will occur if:  
               S   =         ∑     n   =     n   1         n   =     n   2                s   1          (   n   )         &lt;   B       ,           (   3   )                               
 
         [0050]    where n 2 −n 1 +1 is the number of clock pulses per frame time and {s 1 (n)} is the sequence of bits, the m-sequence, produced by the m-bit shift register controlling the bit selection module.  
         [0051]    In the case of the shrinking generator, the problem arises if n 2 −n 1 +1 is greater than the degree of the primitive polynomial producing {s 1 (n)}. To illustrate this, FIG. 7 shows the distribution of ones produced by the m-sequence according to x 41 +x 3 +1 for intervals of 2,000 clock times (100,000 trials each starting the recursion at a randomly chosen setting). The distribution shown in FIG. 7 is not normal. The minimum value is 858, the maximum value is 1,073, and the mean is 1,000. The shape is leptokurtic with a kurtosis of 3.933.  
         [0052]    If, however, an m-sequence of a very high degree is used (such as x 2,281 +x 715 +1), normal statistics may be obtained. FIG. 8 illustrates the distribution of ones produced by the m-sequence according to x 2,281 +x 715 +1 in successive intervals of 2,000 clock times ( 100 , 000  trials, but starting the recursion only once at a randomly chosen point). The distribution shown in FIG. 8 is an excellent candidate for a normal distribution. The minimum value is 905, the maximum value is 1,095, and the mean is 1,000. The kurtosis is 3.005.  
         [0053]    By using an m-sequence whose degree is greater than the keytext frame length, it is possible to make the statistics that of a normal distribution. Advantageously, one may then accurately estimate the probability of the system&#39;s failure to fill a keytext frame.  
         [0054]    In some operational situations, it may be advantageous to send packets of data with unencrypted headers that list the number of the packet such that the receiver(s) may decrypt the packets even if they did not receive previous packets due to a communications blockage or the like. In order to accommodate these cases, an additional pre-operation mode may be utilized that uses the number of the packet as the seed for initializing the shrinking generator. The number of the packet is not reused as this may precipitate a cryptographic depth issue (wherein two or more messages in a machine or similar cipher have been enciphered on the same machine-setting or on the same key, allowing a cryptanalyst to recover both plaintext messages without knowing the cryptographic machine&#39;s keying variable).  
         [0055]    As described above, m=2281, n=41, and N=1,000. In the additional pre-operation mode, only the m-stage shift register is utilized and there is no generation of binary noise. FIG. 9 illustrates the configuration of this additional pre-operation mode. Referring to FIG. 9, a c-bit binary counter  80  is loaded with the message number in the additional pre-operation mode. The shift register  42  is loaded with the secret m-bit binary vector KV 1  and C S =1 and I S  is connected to the least significant bit (LSB) end of the message number counter  80 . Additional pre-operation mode clocking is via CLOCK 1 . The procedure involves running CLOCK 1  for P pulses in the additional pre-operation mode. P must be large enough for the shift register  42  to start the keytext generation mode at a substantially different setting for each message.  
         [0056]    Because the shift register  42  is a linear machine, the effects of the contents of the message number counter  80  on the message-to-message changes of the contents of the shift register  42  at the start of keytext generation may be, to some extent, characterized.  
         [0057]    As the central encryption unit increments the c-bit binary counter  80 , the LSB toggles for each new message, the next bit toggles at half the rate that the LSB toggles, and so on through the c bits of the c-bit binary counter  80 . Using this understanding of the behavior of the c-bit binary counter  80 , a two-step procedure may be used to select P. Given m and c, the number of bits changed in the contents of the shift register  42  may be assessed as the c-bit binary counter  80  is incremented. The contents of all of the stages of the shift register  42  are set to zero and the first i bits of the c-bit binary counter  80  are set to one. CLOCK 1  pulses are then applied and the number of one bits in the shift register  42  are noted. {max(n)} is defined as the largest number of ones in the shift register  42  at clock pulse n for the range 0≦i≦c−1 and, likewise, {min(n)} is defined as the smallest number. A is computed and is defined as:  
               Δ                   (   n   )       =              max        (   n   )       -     m   2            +              m   2     -     min        (   n   )              .               (   4   )                               
 
         [0058]    Referring to FIGS. 10 and 11, {max(n)} (upper curve) and {min(n)} (lower curve) are plotted versus P for m=2,281 and c=30, and {Δ(n)} is plotted. This first portion of the test measures the decorrelation between the initial contents of the shift register  42  between two sequential messages, i.e., messages M and M+1.  
         [0059]    From these results, it may be seen that, given a value of P less than 20,000, a randomization of the contents of the shift register  42  may be approximated prior to each message&#39;s encryption. Specifically, when P=17,523, there is a local minimum value of Δ and that is Δ(17,523)=248.  
         [0060]    The second step of the procedure involves checking to see that Δ(17,523) remains suitably small for random togglings of message counter bits. This latter part of the procedure considers the correlation between initial shift register contents for two non-sequential messages. Random contents are selected for the message number counter  80  and P is set to 17,523, as determined in the formed part of the procedure. The distribution of the number of bits different between the two initial shift register contents is illustrated in FIG. 12. The histogram of FIG. 12 is highly leptokurtic. The kurtosis is almost 31 and the maximum deviation below m/2 is 277.5 and the maximum deviation above m/2 is 258.5. Therefore, this procedure is expected to have arrived at a value for P that may reasonably be expected to decorrelate the initial shift register contents between messages.  
         [0061]    It is apparent that there have been provided, in accordance with the methods and apparatuses of the present invention, instrumentation privacy methods and apparatuses for implementing communications privacy on a class of two-way wireless control communications. Although the methods and apparatuses of the present invention have been described with reference to preferred embodiments and examples thereof, other embodiments and examples may perform similar functions and/or achieve similar results. All such equivalent embodiments and examples are within the spirit and scope of the present invention and are intended to be covered by the following claims.