Abstract:
Computer related method and apparatus to transmit a logical value (e.g., 1 or 0) between two entities, such as an operating system and application program, in a secure way in an insecure environment. The logical status is sent by in effect encrypting it using two random numbers, one from each entity, before sending it to the other entity. However the encrypting is much “lighter” (requiring much less computer or circuit resources) than any conventional secure cipher and has a built-in verification feature.

Description:
FIELD OF THE INVENTION 
     This invention relates to computers, computing devices, and data security. 
     BACKGROUND 
     For a large set of software applications (program) it is necessary to answer a logic statement Yes or No. Yes and No are typically expressed in the computer field by respectively a binary 0 or a 1. This type of answer (“return”) is for instance the case when a digital signature is verified to answer if the signature has been determined to be valid or not. 
     For inside a secure computing environment it is possible simply to transmit this logic Yes/No status as a Boolean value of 1 or 0. In a non-secure computing environment, a block cipher can for instance be used to encrypt the Boolean value for transmission. This is often done with the addition of a random number, to avoid the well known replay type attacks. 
     However, for some applications use of a block cipher is impossible due to the length of execution time and software code size required for a block cipher or equivalent. For instance, many consumer electronic devices do not have adequate processing ability to handle a block cipher (which is complex), but do require data security. 
     SUMMARY 
     This disclosure describes a solution to transmit a Boolean status in a secure way using a “light” but secure method related to encryption but not using a cipher. This is intended for a “light” (small code size or few logic gates) implementation. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows the present method diagrammatically. 
         FIG. 2  shows how to determine ST 1  for use in the  FIG. 1  method. 
         FIG. 3  shows an apparatus for the  FIG. 1  method. 
     
    
    
     DETAILED DESCRIPTION 
     The Boolean logic status exchange (transmission) in accordance with the invention is done as follows. In one example the Boolean status is transmitted between a computer operation system referred here to as “Part 1 ” and a software application referred here to as “Part 2 ” running on that operating system in a computer or computing device environment. But, that is not limiting; in another example the Boolean status is transmitted between two different computers or other types of computing devices. Suppose Part 1  (the operating system) needs to obtain a Boolean response from Part 2  (the application). The method is shown in  FIG. 1  where time is the vertical axis and each column shows the activity at respectively Part 1  and Part 2 . 
     The functions of  FIG. 1  are as follows: 
     ST 2  (State  2 ) is obtained as being, for example: 
     a) ((r 1  II r 2 ) 2  modulus 2 128 +51) modulus 2 128 , or 
     b) (a·(r 1  II r 2 )+b) modulo 2 128  XOR K 1 , where “II” designates concatenation and “XOR” is the Boolean (logic) exclusive OR operation. a, b and K 1  are constants, see below. The random numbers r 1 , r 2  may be generated by a true random number generator or a pseudo-random number generator. Values r 1 , r 2  are for example 64 bits long expressed in binary form. 
     ST 1  (State  1 ) is obtained by the method and apparatus depicted in  FIG. 2 . This generates a value having 256 binary bits. If the bit status of the Boolean logic value to be returned from Part 2  to Part 1  is 0, then only the even bits of ST 1  are taken to generate Alpha of  FIG. 1 . If the bit status of the Boolean logic value to be sent is 1, then only the odd bits of ST 1  are taken to generate Alpha. Note that this example uses bits, but can easily be extended to bytes or words. 
     In  FIG. 2 , one starts with two random numbers (from e.g. a pseudo or true random number generator) r 1 , r 2  stored in respective storage elements (e.g., registers)  40 ,  42 . These are then in effect “flipped” as shown (r 1  for r 2 , r 2  for r 1 ) and restored in storage elements  46 ,  48 . S-boxes s 1 , s 2  (which are stored in respective storage elements  50 ,  52 ) are then applied to r 2 , r 1  by a calculation element  56 . S-box s- 1  is applied then s-box s- 2 , then again s- 1  then s- 2  to the nibble of the constructed values to achieve a value 128 bits long. There are additional s-boxes in other embodiments. A cryptographic key K (not the same as constant K 1  above) is stored in its storage element  56  and logically XOR&#39;d (exclusive OR operation) at element  60  with the result of the S-box application. The result of the XOR operator  60  is stored in the first output storage element  64 , as output 1  and also partitioned into two and stored in storage elements  68 ,  70 . 
     The contents of storage elements  68 ,  70  are flipped as shown and stored in elements  74 ,  76 . The contents of  74 ,  76  have the same S-box operations of s 1 , s 2  applied at  80 . A 64 bit-shift rotated version of key K is stored at  84 , and logically XOR&#39;d at  88  with the result of operation  80 . The result is the second half of the output (output 2 ) stored at  92 .  FIG. 2  shows (right hand column) in this example how many bits are being stored in each storage element or set of storage elements, which here is 128 bits. 
     The s-box st (first substitution box—which implements a substitution operation of the type well known for use in block ciphers) of  FIG. 2  (working on 4 input bits) can be expressed in hexadecimal in one embodiment as {0x3, 0x5, 0xf, 0xd, 0x0, 0xe, 0xi, 0xa, 0x6, 0x2, 0xc, 0x4, 0x7, 0x9, 0xb, 0x8}; the s-box s 2  (second substitution box) can be expressed as {0x5, 0xe, Ox1, 0x2, 0x4, 0x9, 0xb, 0xc, 0x0, 0xf, 0x3, 0x8, 0xa, 0x6, 0xd, 0x7}. These s-boxes are merely exemplary. 
     Values A, B, a, b. K 1  and the key of  FIG. 2  can be fixed and secret and are integers. The only other restriction is that A and a are odd integers. Suitable exemplary values are: A=3 or A=5 and a=5 or a=7. B, b, k 1  and the key for ST 1  of  FIG. 2  in one embodiment are built (“hardwired”) into the software/hardware executing the process of  FIGS. 1 and 2  and are each, e.g., 128 bits long when expressed as binary numbers. 
     If A=3 then the inverse of A is expressed in hexadecimal as A −1 =Oxaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab 
     If A=5 then A −1 =Oxcccccccccccccccccccccccccccccccd where A −1  is the inverse of A modulo 2 128 . 
     At the end of the second XOR operation of  FIG. 2  (where the XOR operation is expressed there by the “+” operator) the two blocs of 128 bits (output 1  and output 2 ) are concatenated which yields a 256 bit bloc output. 
     The process of  FIG. 1  can be summarized as: 
     The transmitted messages in  FIG. 1  are: 
     1. From Part 1  to Part 2 : send number r 1   
     2. From Part 2  to Part 1 : send numbers r 2  and C 
     The Boolean status of Part 2  is extracted on the Part 1  side of  FIG. 1  from C, by recovering Alpha′ from C as follows: 
     1. Recover Beta from r 2   
     2. (C XOR Beta)−B=A·Alpha 
     3. Alpha′=A·Alpha·A −1 , where · is the multiplication operation. This operation may be done modulo any other value. 
     4. At this point Alpha′ is determined from expression 3. 
     Part 1  can then compute ST 1  from r 1 , r 2  as in  FIG. 2  and then compares the ST 1  even bytes or odd bytes to value Alpha&#39;. If neither of the full sets of 16 bytes (128 bits) match, then there has been a transmission error of r 1 , r 2 , or C between Part 1  and Part 2  in  FIG. 1 . This can be an indication of corruption. Otherwise (if no transmission error is found by the comparison), Part 1  is able to know securely what is the Boolean logic status of Part 2 . 
     The present method thereby provides transmission of a Boolean status in a secure way and has the advantage of being implementable in a constrained (“light”) environment in terms of available computing resources. This approach is more compact in terms of software code length (or logic gates in a hardware implementation) than most the block ciphers. The method is less secure than a classical block cipher but is intended primarily for purposes as described here which are different than that of block ciphers. One useful feature is the possibility of error detection as indicated above since the two possible answers are both recovered on the Part 1  side and a set of comparisons is performed for verification. The present method may be embodied in computer code coded in, e.g., the C++ computer language, to be executed on a processor. Coding such code or embodying it in logical gates would be routine in light of this disclosure. Also contemplated is a computer or computing device programmed to execute the code, and a computer readable medium storing such code. In other embodiments the method is embodied entirely or in part as logic circuitry. 
       FIG. 3  shows an apparatus  100  in a block diagram for carrying out the  FIG. 1  method in hardware or software. Apparatus  100  includes (as in  FIG. 1 ) Part 1  and Part 2  (partitioned as indicated by the broken line), with respective sources  104 ,  106  of r 1 , r 2 , such as a memory (storage) element or random number generator. Source  104  of r 1  is coupled to Part 2  via a suitable communications channel. Part 2  also has memory element  108  storing its logical state to be returned to Part 1 . Cryptographic element  114  computes C from r 1 , r 2 , the logical state at  108 , and the various constants shown above in  FIGS. 1 and 2 , and outputs value C to its output storage element  118 . Storage element  118  and source  106  of r 2  are coupled via the communications channel to the extractor  120  in Part 1 , which as shown above extracts the logical state of Part 2  from C using r 2  and stores the extracted logical state in storage element  124 , and if need be performs the verification as described above. 
     This disclosure is illustrative but not limiting; further modifications will be apparent to those skilled in the art in light of this disclosure, and are intended to fall within the appended claims.