Software data protection mechanism5276738Abstract A protection mechanism includes means for taking an input binary value and generating a unique key value as well as performing the reverse operation of taking a key value and generating an input binary value. The mechanism includes a scrambler which includes an array having a number of multibit container locations for storing a unique sequence of random numbers. The scrambler forms another binary value by rearranging the bits of the input binary value as a function of the random number values in addition to altering the states of such bits as a function of the random number values and the numeric bit position values of sources of the input binary bits. The resulting binary value is applied to an alphanumeric encoder which converts the binary value into a series of alphanumeric characters containing a valid key value. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
TABLE
__________________________________________________________________________
Scrambler Array
Input
Output
Input
Output
Input
Output
Input
Output
__________________________________________________________________________
00 NOT
30 01 NOT
11
02 27
03 NOT
23
04 NOT
14 05 08
06 NOT
04
07 28
08 NOT
22 09 26
10 NOT
24
11 NOT
17
12 01 13 20
14 15
15 NOT
03
16 31 17 NOT
19
18 NOT
18
19 02
20 NOT
12 21 NOT
09
22 NOT
06
23 NOT
21
24 13 25 NOT
25
26 NOT
16
27 00
28 07 29 NOT
29
30 05
31 10
__________________________________________________________________________
As shown in FIG. 1A, the binary contents of the output register 18 are applied as inputs to an alphanumeric encoder 20. The encoder 20 includes four sets of overlapping 5-bit registers 200-1a,1b through 200-4a,4b. Each of the sets of registers receive as inputs, a different 8-bit character or byte from output register 18. The 5-bit output of each register is applied as an input to a table 204. The table 204 contains 32 different alphanumeric characters. The contents of each set of registers 200-1a, 1b through 200-4a, 4b are used as indexes into the table 204 for obtaining eight alphanumeric characters which are stored in a user key register 24. In the preferred embodiment of the present invention, table 204 includes the key characters shown below and discussed relative to in FIG. 1C:
______________________________________
Alphanumeric Encode/Decode Table
Index Character
______________________________________
0 A
1 B
2 C
3 E
4 D
5 F
6 G
7 H
8 I
9 J
10 K
11 L
12 M
13 N
14 P
15 Q
16 R
17 S
18 T
19 U
20 V
21 W
22 X
23 Y
24 Z
25 2
26 3
27 4
28 5
29 6
30 7
31 8
______________________________________
The characters "O" and "1" were excluded to avoid problems in distinguishing between ZEROS and the letter "0," ONES and the letter I or L. FIG. 1C illustrates the manner in which an input binary value (0001 . . . 1001) contained in input register 12 is transformed into the string of alphanumeric characters AGFPH3XS. Also, FIG. 1C illustrates the reverse operation of transforming the string of alphanumeric characters AGFPH3XS into the input binary value 0001 . . . 1001. These operations are illustrated for the unique sequence of random number values indicated in scrambler array table. The sequence corresponds to the random number values 30, 11, 27, 23, 14, 08, 04, 28, 22, 26 . . . through 10. In the preferred embodiment, the scrambler and alphanumeric encoder functions are implemented by the use of different program routines. More specifically, the scrambler array operation is carried out by a mix function of FIG. 4A. The routine takes a 32-bit value and randomly rearranges the bits to form another 32-bit value. This is accomplished by generating a list of the numbers from 0 to 31 in random order and moving each bit position to a new bit position indicated by that list. As shown in FIG. 4A, the value of encode flag parameter is used to control the direction of movement through the scrambler. The mix function makes use of a conventional pseudo random number generator. As shown in FIG. 4A, the seed value is applied as an input to the pseudo random number generator. As indicated, this type of generator is normally included as part of a standard C runtime library (SRAND routine which receives the seed value and the RAND function which returns a pseudo random number value). Such runtime libraries are normally provided in operating system which utilize the C programming language. Equivalent generators are available for use with other programming languages. Additionally, a start number value is also applied which results in skipping a designated number of random number sequences. Since both the seed and start values are arbitrary values, they can be selected in a way to ensure security. As seen from FIG. 4A, a switch counter is set to zero, and the number of scrambler switches is checked to determine if all 32 switches have been processed. Next, the mix function checks if the random number to be loaded is new (unique). There must be 32 unique numbers stored in containers 140-0 through 140-31. If it is not unique, the function skips to another random number of the sequence. Next, the mix function checks if the mechanism is performing an encoding function or a decoding function. As shown, in either case, the mix function compare the least significant bit of the numeric value of each source bit position and each destination bit position (i.e., the random number value stored in the associated container) to determine if they are equal. This is carried out by exclusively oring of these bits. When they are not equal, the bit being moved is moved to the non-inverting input bit position. When they are equal, the bit being moved is moved to the inverting or complementing bit position. This is followed by incrementing the switch counter by one. The above sequence is repeated until all 32 switches are done. As shown, the mix function returns the result which corresponds to the 32-bit value stored in output register 18 or the 32-bit input binary value stored in input register 12. The source code for the mix function is shown in Appendix I. The alphanumeric encoder function is carried out by a make key function routine and a make value function routine. The make key function routine takes a 32-bit value and converts it into a series of alphanumeric characters. This is accomplished by extracting groups of 5 bits and using that as an index into the table of 32 alphanumeric characters. Each byte is used to form two characters, one from the high order five bits and the other from the low order five bits. A null character is placed at the end of the string of eight characters. A pointer is returned to this static string and copy would normally be made of the string before the make key function is called again. FIG. 4B is a flow diagram illustrating the operation of the make key function. The input binary value is viewed as consisting of four bytes designed as bytes 0 through 3. As shown, this function first terminates the stored result string with a null or zero character. Next, the function establishes a counter for storing a byte numerical index value of (i). This value identifies the index for the byte to be converted. Since this is the first pass, the make key function converts the five high order bits of byte (i) into the character obtained from the alphanumeric table and stores the character in result location at index (i*2). Next, the make key function converts five low order bits of byte (i) into the character obtained from the alphanumeric table and stores the character in result location at index (i*2+1). When all four of the bytes have been processed, the function eliminates all trailing zero value characters and then returns a pointer designating the location of the result. The source code of this function is shown in Appendix II. The make value function takes a series of alphanumeric characters and converts them into a 32-bit value. This is accomplished by forming a 5-bit value from the alphanumeric character and combining them to form the 32-bit value. Each character is searched for in the table 204 and its position is used as the value. FIG. 4C is a flow diagram illustrating the operation of the make value function. As shown, the make value function first sets the result field to zero and sets a character counter (i) equal to zero. Next, it determines if there is a key character left. Next, it looks up the key character in the "keychars" table. If the key character is found, then the position or index (j) of the located key character is stored in the result field. If the character count is less than 8, the character counter is incremented by one. Also, the key pointer is incremented by one for processing the next key character. When all of the key characters have been processed, the make value function then returns the result. It will be noted that any extraneous characters included as key characters are ignored since they will not be found in the table. The source code of this routine is shown in Appendix III. DESCRIPTION OF OPERATION With reference to FIGS. 1A through 1C and 2, the utilization of the protection mechanism 10 will now be described relative to the flow diagrams of FIGS. 3A and 3B. FIG. 2 depicts both developer and user environments which utilize the teachings of the present invention. The protection mechanism 10 when utilized in the application developer system environment 40 includes the encoding routines to compute a valid key. It also may include the decoding routines also utilized in the user environment 50 for verifying that the application is correctly processing the key values using valid and invalid keys. As indicated in FIG. 2, all of these routines are stored in a library 400 linked to the applications 1 and 2 being run. Also, the system environment 40 includes storage for the scrambler switching array memory 402 equivalent to array 14 of FIG. 2 and an alias table 404 which is equivalent to table 204 of FIG. 2. Application 2 is run by the developer for the purpose of generating a valid key. More specifically, the application provides seed and start values generated as a function of certain identification information provided by the developer. For example, the start value is determined by CPU serial number while the seed is selected for a particular product and its value is hidden to the extent possible. The seed and start values are applied as inputs to the pseudo random number generator program included as part of the developer environment 40. Additionally, the application supplies a 32-bit binary value. In accordance with the invention, the application calls mix function routine stored in library 400 and provides as inputs, the seed, start and the 32-bit binary value. The routine produces as an output, another 32-bit value whose bits have been randomly rearranged utilizing scrambler array 402 in the manner previously described. Next, the make key function routine is called as shown in FIG. 3A. This routine takes the 32-bit value provided by the mix function routine and converts it to a string or series of alphanumeric characters utilizing alias table 404 in the manner previously described. The routine puts a null character at the end of the string and stores it in a key storage memory 406. As indicated in FIG. 2, a key pointer to this static string is returned by the routine to application 2. This completes the encoding sequence. The developer then verifies that the application is correctly processing key values by running application 1. This sequence is shown in FIG. 3B. The application first reads the user supplied key which in this case corresponds to a previously generated key or a test value. The key is referenced via the key pointer. Next, the application calls the make value function. This function takes the string of alphanumeric characters and converts them into a 32-bit value by searching alias table 404 in the manner previously described. As described in FIG. 3B, next a call is made to the mix function routine of library 400. This routine takes the 32-bit value and rearranges its bits utilizing scrambler array 402 to form another 32-bit value which corresponds to the input binary value. As shown in FIG. 2, this number is returned to the application. The values are compared by the application of FIG. 3B and if the appropriate parts match identically, the key is deemed valid. From the valid value derived from the user supplied key, certain information can be extracted as explained herein. Such computed valid key value can include the serial number of the system machine, a product code and an encoded value representing the maximum number of users allowed in the system. More specifically, the 32-bit valid key value may contain the following information:
______________________________________
01 . . . 19 20 . . . 27 28 . . . 31
CPU Serial No.
PRODUCT CODE MAX USERS.
______________________________________
Also, the 32-bit valid key value could contain duplicate data as follows:
______________________________________
0 . . . 6
8 . . . 15 16 . . . 22
23 . . . 31
YEAR- DAY OF YEAR YEAR-1990 DAY OF YEAR.
1990
______________________________________
In the case where the valid key value contains the CPU serial number and product code, the application, by accessing such information, can compare these values and, if they match, the application can extract the maximum user field and use that value. In the case where the valid key value contains duplicate data, the key value is validated by comparing the duplicated data. As indicated, FIG. 2 also shows user system environment 50. This environment only contains the routines for verifying the key. As shown, the developer normally provides the valid key along with the user environment application packaged in a shrink-wrapped container as is standard in the software industry. The user enters the user key which is furnished to the application. The application performs the sequence of operations of FIG. 3B. As previously explained, this involves calling the make value function routine which converts the key to a 32-bit value. This is followed by calling the mix function which rearranges the 32 bits to form the real 32-bit binary value. The information used for validation is extracted from the key value and compared with known values by the application for establishing that the key is valid. If it is, the application can extract additional information such as maximum number of users. Appendices IV and V provide the source code for the functions of FIGS. 3A and 3B. From the above, it is seen how the protection mechanism of the present invention is able to provide key values associated with software packages that cannot be easily duplicated and which contain information useful in license verification. The protection mechanism details as well as source code need not be protected. Therefore, only a minimal amount of information needs to be hidden or concealed thereby reducing the extent of security measures normally required. Further, since the protection mechanism does not depend upon the formatting or ordering of bits, bytes, etc., it can be used to generate valid keys on any type of machine. It is only required that such machine provide a pseudo random number generator. Another advantage of the protection mechanism is that it requires a minimal amount of code to implement the required functions. It will be obvious to those skilled in the art that many changes may be made to the protection mechanism of the present invention. For example, different user identification information may be used in conjunction with the mechanism. Also, only portions of the protection mechanism may be used. For example, the mix function may be used separately to encrypt an input binary value. Similarly, the alphanumeric encoder/decoder or make key/make value function may be used separately to encode/decode an input binary value into an alphanumeric string of characters. ##SPC1## While in accordance with the provisions and statutes there has been illustrated and described the best form of the invention, certain changes may be made without departing from the spirit of the invention as set forth in the appended claims and that in some cases, certain features of the invention may be used to advantage without a corresponding use of other features.
|
Same subclass Same class Consider this |
||||||||||