Abstract:
A multi-stage technique of establishing a plurality of secure strings of symbols is disclosed. In the first stage, the illustrative embodiment establishes a first-stage string of symbols with each other node. The first-stage strings are chosen from a first, small, key space, which means that they can be established more quickly than a highly secure key from a large key space. The advantage of the first-stage strings is that it enables the user to transmit secure messages more quickly than messages secured with highly secure strings. The disadvantage of the illustrative embodiment is that the first-stage strings are not as secure as strings from a larger key space. This disadvantage is mitigated, however, by the fact that the first-stage strings are only used for a short amount of time—until the second-stage strings are established in the second stage.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to telecommunications in general, and, more particularly, to cryptography. 
       BACKGROUND OF THE INVENTION 
       [0002]    When two parties communicate via a telecommunications network, it is common for the parties:
       i. to encrypt their messages so that they remain secret from eavesdroppers, and   ii. to authenticate the messages so that the receiver is confident who really sent the message.
 
It is well known in the prior art how to encrypt and authenticate messages using one or more secure strings of symbols. There are many well-known ways of establishing secure strings, but the process of establishing secure strings in the prior art has disadvantages.
       
 
       SUMMARY OF THE INVENTION 
       [0005]    The present invention provides a technique for establishing secure strings of symbols between pairs or groups of nodes in a telecommunications network without some of the costs and disadvantages for doing so in the prior art. These secure strings can then be used to create and transmit a “secure message,” which for the purposes of this specification, is defined as a message that is:
       i. authenticated, or   ii. encrypted, or   iii. authenticated and encrypted.       
 
         [0009]    When a node in a telecommunications network is turned on, comes on-line, or is re-booted, the node might be required to establish a secure string of symbols with one or more other nodes. Because the process to establish even one highly secure string of symbols is computationally intense, the amount of time required for one node to establish a highly secure string with each of several other nodes can be substantial. The consequence is that a user of the node might be prevented from transmitting a secure message for a long time. 
         [0010]    To address this, the illustrative embodiment stages the process of establishing secure strings. In the first stage, the illustrative embodiment establishes a first-stage string of symbols with each other node. The first-stage strings are chosen from a first, small, key space, which means that they can be established more quickly than a highly secure key from a large key space. The advantage of the first-stage strings is that it enables the user to transmit secure messages more quickly than messages secured with highly secure strings. The disadvantage of the illustrative embodiment is that the first-stage strings are not as secure as strings from a larger key space. This disadvantage is mitigated, however, by the fact that the first-stage strings are only used for a short amount of time—until the second-stage strings are established in the second stage. 
         [0011]    In the second stage, the illustrative embodiment establishes a second-stage string of symbols with each other node. The second-stage strings are chosen from a second, medium-sized, key space. The advantage of the second-stage strings is that they are more secure than the first-stage strings, albeit not as secure as the third-stage strings established in the third stage. Once the second-stage strings are established, they can be used in place of the first-stage strings. 
         [0012]    In the third stage, the illustrative embodiment establishes a third-stage string of symbols with each other node. The third-stage strings are chosen from a third, large-sized, key space. The advantage of the third-stage strings is that they are more secure than the second-stage strings. Once the third-stage strings are established, they can be used in place of the second-stage strings. 
         [0013]    The illustrative embodiment comprises: transmitting secure messages at a telecommunications node with a first string of symbols for a first interval from instant b 1  to instant x 1 , wherein the first string of symbols is selected from a first key space having K 1  members, where K 1  is a natural number; and transmitting secure messages at the telecommunications node with a second string of symbols for a second interval from instant b 2  to instant x 2 , wherein the second string of symbols is selected from a second key space having K 2  members, where K 2  is a natural number; wherein b 2 &lt;x 1 ; and wherein 
         [0000]    
       
         
           
             
               
                 ln 
                  
                 
                   ( 
                   
                     K 
                     2 
                   
                   ) 
                 
               
               
                 ( 
                 
                   
                     x 
                     2 
                   
                   - 
                   
                     b 
                     2 
                   
                 
                 ) 
               
             
             &gt; 
             
               
                 
                   ln 
                    
                   
                     ( 
                     
                       K 
                       1 
                     
                     ) 
                   
                 
                 
                   ( 
                   
                     
                       x 
                       1 
                     
                     - 
                     
                       b 
                       1 
                     
                   
                   ) 
                 
               
               . 
             
           
         
       
     
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]      FIG. 1  depicts a schematic diagram of a portion of a typical wireless telecommunications system. 
           [0015]      FIG. 2  depicts a flowchart of the salient tasks associated with the operation of the illustrative embodiment of the present invention. 
           [0016]      FIG. 3  depicts a flowchart of the salient tasks associated with the operation of task  201 - i.    
       
    
    
     DETAILED DESCRIPTION 
       [0017]      FIG. 1  is a schematic diagram of the salient components of cryptographic telecommunications system  100  in accordance with the illustrated embodiment of the present invention. Cryptographic telecommunications system  100  comprises: telecommunications nodes  101 - 1  through  101 - 4  and telecommunications network  102 , interconnected as shown. 
         [0018]    In accordance with the illustrative embodiment, node  101 - 4  is a communications hub, and messages between nodes  101 - 1 ,  101 - 2 , and  101 - 3  pass through node  101 - 4 , but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which any node communicates directly with any other hub (i.e., the nodes communicate on a peer-to-peer basis). 
         [0019]    In accordance with the illustrative embodiment, each of nodes  101 - 1  through  101 - 3  establishes a series of progressively-more-secure string of symbols with node  101 - 4  for the purposes of exchanging secure messages with node  101 - 4 . 
         [0020]    Although the illustrative embodiment depicts three nodes that establish a series of string of symbols with one other node, it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which any number of nodes establish a series of string of symbols with any number of other nodes. 
         [0021]    In accordance with the illustrative embodiment, each of nodes  101 - 1  through  101 - 4  uses one series of strings of symbols to exchange secure messages, but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which one node uses one series of strings of symbols to transmit secure messages to a second node, but the second node uses a second series of strings of symbols to transmit secure messages to the first node. 
         [0022]    Node  101 - j , where jε{1, 2, 3, 4}, is hardware and software that provides voice, video, and data capabilities to a user, and that is capable of performing the functionality described below and in the accompanying figures. In accordance with the illustrative embodiment, node  101 - j  is a wireless terminal that is connected to network  102  via wireline, but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which node  101 - j  is connected to network  102  via wireless. 
         [0023]    Network  102  is the Internet, but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which telecommunications network  102  is any network (e.g., the Public Switched Telephone Network, an intranet, an 802.11 network, etc.), or combination of networks, using the same or dissimilar networks and in one or more address spaces. 
         [0024]      FIG. 2  is a flowchart of the salient tasks associated with the operation of the illustrative embodiment of the present invention. In accordance with the illustrative embodiment, tasks  201 - 1 ,  201 - 2  and  201 - 3  are performed concurrently, but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which some or all of the tasks are performed serially or simultaneously. Furthermore, in accordance with the illustrative embodiments, the subtasks within tasks  201 - 1 ,  201 - 2 , and  201 - 3  are performed serially so as to not overwhelm the computing capabilities of node  101 - 4 , but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which some or all of the subtasks are performed concurrently or simultaneously. 
         [0025]    At task  201 - 1 , node  101 - 1  and node  101 - 4  establish a series of three progressively-more-secure strings of symbols and exchange secret and authenticated messages using those strings of symbols. This is described in detail below and in  FIG. 3 . Although node  101 - 1  and  101 - 4  establish a series of three secure strings of symbols, it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which the series comprises any plurality of secure strings of symbols. 
         [0026]    At task  201 - 2 , node  101 - 2  and node  101 - 4  establish a series of three progressively-more-secure strings of symbols and exchange secret and authenticated messages using those strings of symbols. This is described in detail below and in  FIG. 3 . Although node  101 - 2  and  101 - 4  establish a series of three secure strings of symbols, it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which the series comprises any plurality of secure strings of symbols. 
         [0027]    At task  201 - 3 , node  101 - 3  and node  101 - 4  establish a series of three progressively-more-secure strings of symbols and exchange secret and authenticated messages using those strings of symbols. This is described in detail below and in  FIG. 3 . Although node  101 - 3  and  101 - 4  establish a series of three secure strings of symbols, it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which the series comprises any plurality of secure strings of symbols. 
         [0028]      FIG. 3  is a flowchart of the salient tasks associated with the operation of task  201 - i , where iε{1, 2, 3}, involving node  101 - i  and node  101 - 4 . Task  201 - i  begins, by definition, when node  101 - i  is turned on, is re-booted, or for whatever reason is required to renew its secure strings. The beginning of task  201 - i  is defined as instant t 0 -i. 
         [0029]    At task  301 - i —which occurs at instant b 1 -i—node  101 - i  and node  101 - 4  establish a first-stage secure string of symbols S 1 -i. 
         [0030]    In accordance with the illustrative embodiment, the first-stage string S 1 -i is chosen from a key space having K 1 -i members, where K 1  is a natural number, using the well-known Diffie-Hellman key exchange protocol. It will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which another protocol is used to establish the first-stage string S 1 -i (e.g., physically secure key exchanges, protocols based on the computational difficulty inherent in solving large numbers of puzzles, of factoring large numbers, of inverting large matrices, etc.). 
         [0031]    In accordance with the illustrative embodiment, task  301 - i  occurs at a different instant than all of the other tasks so as to not overwhelm the computing capabilities of node  101 - 4 , but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which task  301 - i  does, in fact occur concurrently with one or more other tasks. In any case, it will be clear to those skilled in the art how to make and use embodiments of the present invention that accomplish task  301 - i.    
         [0032]    At task  302 - i —which occurs at instant m 1 -i:
       i. node  101 - i  transmits a first secure message to node  101 - 4  and uses the first-stage string S 1 -i to secure the first message, and   ii. node  101 - 4  transmits a second secure message to node  101 - i  and uses the first-stage string S 1 -i to secure the second message.
 
Although the illustrative embodiment uses symmetric-key or “classical” cryptography for encryption and authentication, it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which asymmetric key or “public-key” techniques are used.
       
 
         [0035]    At task  303 - i —which occurs at instant b 2 -i—node  101 - i  and node  101 - 4  establish a second-stage secure string of symbols S 2 -i. In all cases, the second-stage string S 2 -i is established before the first-stage string S 1 -i expires (i.e., b 2 -i&lt;x 1 -i). 
         [0036]    In accordance with the illustrative embodiment, the second-stage string S 2 -i is chosen from a key space having K 2 -i members, where K 2  is a natural number that is larger than the key space of the first-stage string (i.e., K 2 -i&gt;K 1 -i). 
         [0037]    All other things being equal, the fact that the second-stage string S 2 -i is chosen from a larger key space than the first-stage string S 1 -i suggests that the second-stage string S 2 -i is more secure than the first-stage string and can be used for a longer interval before it is likely to be broken. In accordance with the illustrative embodiment, the key spaces and the length of the intervals during which they are comparably secure are related by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ln 
                        
                       
                         ( 
                         
                           K 
                           2 
                         
                         ) 
                       
                     
                     
                       ( 
                       
                         
                           x 
                           2 
                         
                         - 
                         
                           b 
                           2 
                         
                       
                       ) 
                     
                   
                   &gt; 
                   
                     
                       ln 
                        
                       
                         ( 
                         
                           K 
                           1 
                         
                         ) 
                       
                     
                     
                       ( 
                       
                         
                           x 
                           1 
                         
                         - 
                         
                           b 
                           1 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     1 
                   
                   ) 
                 
               
             
           
         
       
     
         [0038]    It will be clear to those skilled in the art, however, after reading this disclosure, how to make and use alternative embodiments of the present invention in which the key space of the second-stage string is smaller than the key space of the first-stage string (i.e., K 2 -i&lt;K 1 -i) or in which they are identical (i.e., K 2 -i=K 1 -i). 
         [0039]    In accordance with the illustrative embodiment, node  101 - i  and node  101 - 4  use the well-known Diffie-Hellman key exchange protocol to establish the second-stage string S 2 -i, but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which the nodes use another protocol to establish the second-stage string S 2 -i (e.g., physically secure key exchanges, protocols based on the computational difficulty inherent in solving large numbers of puzzles, of factoring large numbers, of inverting large matrices, etc.). 
         [0040]    In accordance with the illustrative embodiment, task  303 - i  occurs at a different instant than all of the other tasks so as to not overwhelm the computing capabilities of node  101 - 4 , but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which task  303 - i  does, in fact occur concurrently with one or more other tasks. In any case, it will be clear to those skilled in the art how to make and use embodiments of the present invention that accomplish task  303 - i.    
         [0041]    At instant x 1 -i first-stage string S 1 -i expires because sufficient time has elapsed since instant b 1 -i for a reasonably-skilled cryptanalyst could discover it. It will be clear to those skilled in the art how to determine when instant x 1 -i occurs given K 1  and the technique used for generating the first-stage string S 1 -i. In all cases, instant b 1 -i occurs before instant m 1 -i which occurs before instant x 1 -i (i.e., b 1 -i&lt;m 1 -i&lt;x 1 -i). 
         [0042]    At task  304 - i —which occurs at instant m 2 -i:
       i. node  101 - i  transmits a third secure message to node  101 - 4  and uses the second-stage string S 2 -i to secure the third message, and   ii. node  101 - 4  transmits a fourth secure message to node  101 - i  and uses the second-stage string S 2 -i to secure the fourth message.
 
Although the illustrative embodiment uses symmetric-key or “classical” cryptography for encryption and authentication, it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which asymmetric key or “public-key” techniques are used.
       
 
         [0045]    At task  305 - i —which occurs at instant b 3 -i—node  101 - i  and node  101 - 4  establish a third-stage secure string of symbols S 3 -i. In all cases, the third-stage string S 3 -i is established before the second-stage string S 2 -i expires (i.e., b 3 -i&lt;x 2 -i). 
         [0046]    In accordance with the illustrative embodiment, the third-stage string S 3 -i is chosen from a key space having K 3 -i members, where K 3  is a natural number that is larger than the key space of the second-stage string (i.e., K 3 -i&gt;K 2 -i). 
         [0047]    All other things being equal, the fact that the third-stage string S 3 -i is chosen from a larger key space than the second-stage string S 2 -i suggests that the third-stage string S 3 -i is more secure than the second-stage string and can be used for a longer interval before it is likely to be broken. In accordance with the illustrative embodiment, the key spaces and the length of the intervals during which they are comparably secure are related by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ln 
                        
                       
                         ( 
                         
                           K 
                           3 
                         
                         ) 
                       
                     
                     
                       ( 
                       
                         
                           x 
                           3 
                         
                         - 
                         
                           b 
                           3 
                         
                       
                       ) 
                     
                   
                   &gt; 
                   
                     
                       ln 
                        
                       
                         ( 
                         
                           K 
                           2 
                         
                         ) 
                       
                     
                     
                       ( 
                       
                         
                           x 
                           2 
                         
                         - 
                         
                           b 
                           2 
                         
                       
                       ) 
                     
                   
                   &gt; 
                   
                     
                       ln 
                        
                       
                         ( 
                         
                           K 
                           1 
                         
                         ) 
                       
                     
                     
                       ( 
                       
                         
                           x 
                           1 
                         
                         - 
                         
                           b 
                           1 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                      
                     2 
                   
                   ) 
                 
               
             
           
         
       
     
         [0048]    It will be clear to those skilled in the art, however, after reading this disclosure, how to make and use alternative embodiments of the present invention in which the key space of the third-stage string is smaller than the key space of the second-stage string (i.e., K 3 -i&lt;K 2 -i) or in which they are identical (i.e., K 3 -i=K 2 -i). 
         [0049]    In accordance with the illustrative embodiment, node  101 - i  and node  101 - 4  use the well-known Diffie-Hellman key exchange protocol to establish the third-stage string S 3 -i, but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which the nodes use another protocol to establish the third-stage string S 3 -i (e.g., physically secure key exchanges, protocols based on the computational difficulty inherent in solving large numbers of puzzles, of factoring large numbers, of inverting large matrices, etc.). 
         [0050]    In accordance with the illustrative embodiment, task  305 - i  occurs at a different instant than all of the other tasks so as to not overwhelm the computing capabilities of node  101 - 4 , but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which task  305 - i  does, in fact occur concurrently with one or more other tasks. In any case, it will be clear to those skilled in the art how to make and use embodiments of the present invention that accomplish task  305 - i.    
         [0051]    At instant x 2 -i the second-stage string S 2 -i expires because sufficient time has elapsed since instant b 2 -i for a reasonably-skilled cryptanalyst could discover it. It will be clear to those skilled in the art how to determine when instant x 2 -i occurs given K 2  and the technique used for generating the second-stage string S 2 -i. In all cases, instant b 2 -i occurs before instant m 2 -i which occurs before instant x 2 -i (i.e., b 2 -i&lt;m 2 -i&lt;x 2 -i). 
         [0052]    At task  306 - i —which occurs at instant m 3 -i:
       i. node  101 - i  transmits a fifth secure message to node  101 - 4  and uses the third-stage string S 3 -i to secure the fifth message, and   ii. node  101 - 4  transmits a sixth secure message to node  101 - i  and uses the third-stage string S 3 -i to secure the sixth message.
 
Although the illustrative embodiment uses symmetric-key or “classical” cryptography for encryption and authentication, it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which asymmetric key or “public-key” techniques are used.
       
 
         [0055]    At instant x 3 -i the third-stage string S 3 -i expires because sufficient time has elapsed since instant b 3 -i for a reasonably-skilled cryptanalyst could discover it. It will be clear to those skilled in the art how to determine when instant x 3 -i occurs given K 3  and the technique used for generating the third-stage string S 3 -i. In all cases, instant b 3 -i occurs before instant m 3 -i which occurs before instant x 3 -i (i.e., b 3 -i&lt;m 3 -i&lt;x 3 -i). 
         [0056]    It is to be understood that the disclosure teaches just one example of the illustrative embodiment and that many variations of the invention can easily be devised by those skilled in the art after reading this disclosure and that the scope of the present invention is to be determined by the following claims.