Pad encryption method and software

[0002] This is a Division, of application Ser. No. 08/533,314 filed on Sep. 25, 1995 now U.S. Pat. No. 5,799,090.

[0003] This invention relates generally to encryption methods and software, and more particularly to stream ciphers and one time pad encryption methods and software.

[0004] One time pad encryption methods are well known. The first such method was invented in 1917 by Major Joseph Mauborgne and AT&T's Gilbert Vernam. Classically, a one time pad is a key of random letters, written on sheets of paper bound together in a pad. The pad is used to encrypt plain text and to decrypt the encrypted ciphertext. The pad is kept secret, and can be referred to as a private key. For security, the pad has the same or more letters than the message being encrypted. Accordingly, the pad is cumbersome, because it requires a large number of letters.

[0005] A one time pad provides perfect encryption, provided the letters of the pad are truly random. However, the burden of using a pad which is the same or a greater size than the text being encrypted makes one time pad methods generally non-applicable to consumer uses.

[0006] Encryption becomes less than perfect, if the key is less than perfectly random.

[0007] It would be beneficial to have a one time pad method which employs less random letters than the size of the message being encrypted.

[0008] It would be beneficial to enhance the security of one time pad methods which rely upon less than perfectly random, i.e., pseudo random, pads.

[0009] According to the present invention, characters for a pad are generated by selecting a seed file, extracting a first value from the seed file, generating a random number, and logically combining the first value with the random number to generate a first random character of the pad. To generate a next random character of the pad, a next value is extracted from the selected seed file, a next random number is generated, and the next random number is combined logically with the next value from the selected seed file to generate a next random character of the pad. This process repeats itself until a desired number of pad characters have been developed.

[0010] According to an embodiment of the present invention, logical combination by exclusive OR, i.e., XOR, is performed to generate a first random character. According to an embodiment of the present invention, a pad is produced having on the order of approximately 20,000 random characters.

[0011] According to the present invention, a user selects plain text to be encrypted and XORs the plain text with a pad at determined offset, to produce output cipher text. If the plain text is larger in number of characters than the pad, the pad is reused at a redetermined offset for XORing the not yet enciphered portions of the plain text. According to one embodiment of the present invention, the offset is a function of a user selected password. According to one embodiment of the present invention. The pad includes the user selected password or a derivative thereof.

[0012] According to the present invention, a pad is created with a software program stored on a selected memory medium a which space is reserved for storage of the pad created. Once the pad is created, it is stored at the reserved space. According to one embodiment of the present invention, the pad is additionally stored at another location for security. According to one embodiment of the present invention, the pad is stored on a flash card. According to one embodiment of the present invention, the software program is stored on a floppy disk. According to one embodiment of the present invention, the pad is stored at a reserved space on the floppy disk. According to one embodiment of the present invention, the software program is installed on a hard disk. According to one embodiment of the present invention, the pad is created by the software program with a seed file located on a hard disk drive, i.e., a hard drive.

[0013] FIG. 1 is a flow diagram of a method according to the present invention, showing creation of a pad with a seed file and storage of the pad created on a flash card and at a blank space on a floppy disk carrying a software program creating the pad;

[0014] FIG. 2 is a flow diagram of a method according to the present invention, showing creation of a random character by XORing pseudo random numbers with corresponding characters of a selected seed file;

[0015] FIG. 3 is a flow diagram of a method according to the present invention, showing the determination of an offset applied to the pad before XORing with a corresponding character of plain text to be encrypted;

[0016] FIG. 4 is a flow diagram of a method according to the present invention, showing user selection of plain text and a password for encryption, and calculation of a pad offset for establishing character correspondence between plain text and pad prior to XORing to determine ciphertext; and

[0017] FIG. 5 is a flow diagram of a method according to the present invention, showing creation of ciphertext by XQRing with the result of a pad XORed at an offset location with a selected password, the offset itself being a function of the selected password.

[0018] FIG. 1 is a flow diagram of a method according to the present invention, showing installation 10 of a software pad and encryption program having blank spaces for storage of a pad sequence to be generated by running the pad & encryption program, as will be discussed in detail below. In particular, the program is operated from an external storage source such as for example a floppy, a PCMCIA card, or a PC card. Utilities such as compression and help programs can be installed from the external storage source to a hard disk for operation with the external storage source. An example of one such utility program according to the present invention is shown in the appendixes attached hereto.

[0019] According to one embodiment of the present invention, operation of the pad & encryption program according to the invention is done on a personal computer (PC). The pad & encryption program according to an embodiment of the present invention, is originally stored on a floppy disk. Space is reserved on the floppy disk for storage of the pad which is generated. A seed file is identified 12 on the hard drive.

[0020] A random pad is created 13 by XORing pseudo random numbers with the seed file located on the hard drive on which the pad & encryption program is installed, according to one embodiment of the present invention. A seed file can be an arbitrary or selected text or non-text file on the hard drive of a personal computer which is randomly or purposefully selected for XOR processing with the pad. A purely random pad is typically not feasibly obtained from computer operation, in view of the regularity of computer operation. However, a computer can generate pseudo random numbers, as is well known. Accordingly, random pad can feasibly be established by computer operation in conjunction with an external source—in this case the user supplied seed file.

[0021] Exclusive OR operation can be performed as follows, with the following first and second bytes:

[0022] In short, any bit match between the two bytes yields FALSE, any bit mismatch yields TRUE.

[0023] The XOR operation can be undone in two ways, to regenerate BYTE ONE, or BYTE TWO, as desired. In particular, BYTE ONE is regenerated by XORing the first XOR result with BYTE TWO, as follows:

[0024] Similarly, BYTE TWO is regenerated by XORing the first XOR result with BYTE ONE, as follows:

[0025] The random pad created is stored 14 at the blank space on the floppy disk or other storage location selected, according to an embodiment of the present invention. The random pad which has been created can additionally be stored 14 on a flash card which has been prepared by burning a PCMCIA program onto it, according to an embodiment of the present invention. According to the present invention, once encryption has been completed and the encrypted text has been stored on a hard disk on a computer or elsewhere, the pad number or sequence must be separated from the encrypted number. If the pad number or sequence is stored proximally to the encrypted text, there is no security for the encrypted text, because a third party having access to the encrypted text also can use the pad to decrypt the encrypted text. Having the pad on a PCMCIA card, a medium which is non-volatile and more robust than the typical floppy disk, permit the encrypting user to separately maintain the encrypted text and the key, i.e., the pad. which can be used to access the encrypted text. Typically, it is desired to have a back-up for the pad stored on the PCMCIA card. Accordingly, it is one embodiment of the present invention to store the pad at a predetermined location within the pad & encryption program, preferably on the installation disk used to install the pad & encryption program on the PC hard drive for operation, including generation of a pad. According to one embodiment of the present invention, the pad & encryption program is mounted on a selected memory medium, which may be magnetic or optical. According to one embodiment, the pad & encryption program is stored on a magnetic floppy disk and is installable on a magnetic hard drive. According to one embodiment, the pad & encryption program includes software modules including but not limited to a pad creation module, an encryption module, an installation module, and an initially blank or zeroed pad sequence storage module or region.

[0026] FIG. 2 is a flow diagram of a method according to the present invention, showing creation of successive random characters by XORing pseudo random numbers with corresponding characters of a selected seed file. In particular according to the present invention, characters for a pad are generated by selecting a seed file and entering 20 the seed file at a first byte thereof. A seed file is any selected file containing elements, bits, values, or characters. It is called the “seed file” for convenience herein, because it is the file from which bits for example are obtained which after a particular logical operation give birth to the desired pad which is used for encryption purposes according to the present invention. The first byte is stored 21 in a memory (e.g., RAM memory) momentarily, serving as a first value from the seed file. Further, a pseudo random number is generated 23, and the pseudo random number is logically combined, by exclusive OR, i.e., XOR, operation, with the first value extracted from the seed file, to generate a first random character of the pad. To generate a next random character of the pad, the process of FIG. 2 is repeated, and successive values, e.g., bytes, are extracted from the selected seed file for logical combination with successively generated pseudo random numbers. Each pseudo random number is generated in succession, and each next pseudo random number is combined logically with the next value from the selected seed file to generate a next random character of the pad. This process repeats itself until a desired number of pad characters have been developed or produced. For purposes of this invention, created, produced and generated have the same meaning. According to an embodiment of the present invention, logical combination by exclusive OR, i.e., XOR, is performed to generate the random characters of the pad. According to an embodiment of the present invention, the pad produced can have on the order of approximately 20,000 random characters. According to an embodiment of the present invention, random number generation produces pseudo random numbers by pseudo random number generation.

[0027] FIG. 3 is a flow diagram of a method according to the present invention, showing the determination of an offset or setoff applied to the pad before XORing with a corresponding character of plain text to be encrypted. According to one embodiment of the present invention, the offset determines which character of a pad string will correspond with a counterpart character of plain text during XOR operation, to raise the security level of encryption. Thus, for a zero offset, the first character of a pad string will be XORed with the first character of plain text to be encrypted. A second character of a pad string will be XORed with the second character of plain text to be encrypted and so on.

[0028] With an initial setoff of two, on the other hand, the third character of a pad string will be XORed with the first character of plain text to be encrypted. A fourth character of a pad string will be XORed with the second character of plain text to be encrypted and so on.

[0029] The beneficial use in enhancing security of plain text to be encrypted with the use of a changed pad setoff arises from the fact that to avoid susceptibility of the encrypted text to undesired decryption, the pad must be as long as the plain text to be decrypted. If the plain text is longer than the pad, security requires that a new pad be used, otherwise the encryption can be broken, by relying upon the establishment of a pattern with reuse of the same pad for the remainder of the plain text left over after the first portion has been encrypted with the pad. According to the present invention, this disadvantage is avoided by using a first pad setoff for encryption of a first portion of the plain text being encrypted and a second, independent pad setoff for another portion of the plain text, which is left over after the first portion has been encrypted.

[0030] According to the present invention, XOR logical conversion of a particular pad generated and plain text selected for a first encryption level is performed 30 with a first offset. A new offset can be determined 31 by adding the value of an older offset with a selected non-negative integer value derived from the pad 32 relative to the older offset valve, and applying the offset to determine the pad characters to be XORed with further plain text characters. Accordingly, in order to continue first level encryption with the remainder of the plain text, one enters the pad at the location specified by the new offset valve. For subsequent offsets in further cycles, the process is repeated.

[0031] Thus, according to one embodiment of the present invention, the offset can be redetermined for each cycle in accordance with the flow chart of FIG. 3. A cycle is defined as the point when a pad string has been completely used in XOR operation to perform a first order encryption of a portion of a plain text file. For example, if the pad string contains n characters or bytes, and the offset is 5, then the first character of the plain text is logically combined with a character from the pad defined by the offset 5. The characters initially skipped can be eliminated entirely from use, according to one embodiment, or they can be used at the end of a particular cycle.

[0032] FIG. 4 is a flow diagram of a method according to the present invention, showing user selection 40 of plain text and a password for encryption. FIG. 4 further shows calculation of an offset from the selected password for establishing character correspondence between plain text and pad prior to XORing 42 (byte-sized, according to one embodiment of the present invention) plain text characters, to generate desired output ciphertext. The offset is significant, because the plain text is a file of sequential characters. Similarly, the pad is a sequential grouping of bits or characters. According to the present invention, an initial offset is established by establishing a correspondence at an initial offset value of the pad sequence which will be XORed with the first character of the plain text. According to the present invention, a user selects 40 plain text to be encrypted 41 and selects 44 a password of desired length. According to one embodiment of the present invention, a five character password is selected.

[0033] According to one embodiment of the present invention, selecting 41 plain text to be encrypted includes or is followed by compressing the plain text by a selected compression technique. Many compression techniques are well-known. Some of these are commercially available. Any one of these may be used in connection with the present invention. Alternatively, compression can be applied to the output ciphertext, within the meaning of the present invention.

[0034] Next in FIG. 4, the user XORs 42 particular characters, i.e., bytes, of the selected plain text with corresponding pad characters or pad derivative (e.g., the pad XORed with a password) characters. The pad characters XORed are taken from a pad of selected relative size (compared to the size of the plain text being XORed) at a determined pad character offset. The result of XORing the offset pad characters with corresponding plain text characters is to produce output cipher text.

[0035] According to one embodiment of the invention, the offset at which pad characters are taken for XORing with corresponding plain text, can be determined by selecting a password which may have five characters, for example, and programming 44 the selected password by combination with a randomly determined pad. The offset is determined 45 with reference to the selected password.

[0036] An example of how to determine the offset from a selected password is according to the following code:

[0037] char code;

[0038] int offset;

[0039] int y;

[0040] for (y=0; y<5; y++) do

[0041] offset+=*(code+y);

[0042] The character of the pad to be selected in accordance with the offset is identified by moving 46 a pointer for example to the location of the next character in the pad. Next, the character of the pad identified with reference to the offset is extracted 47 and then XORed with the password 43. Finally, the result of XOR logical combination 43 is XORed with corresponding plain text 42 to produce output ciphertext.

[0043] If the plain text is larger in number of characters than the pad, the pad is reused at a redetermined offset for XORing the not yet enciphered portions of the plain text. According to one embodiment of the present invention, the offset is a function of a user selected password. According to one embodiment of the present invention, the pad includes the user selected password or a derivative thereof.

[0044] According to the present invention, a pad is created with a software program stored on a selected memory medium on which space is reserved for storage of the pad created. Once the pad is created, it is stored at the reserved space. According to one embodiment of the present invention, the pad is additionally stored at another location for security. According to one embodiment of the present invention, the pad is stored on a flash card. According to one embodiment of the present invention, the software program is stored on a floppy disk. According to one embodiment of the present invention, the pad is stored at a reserved space on the floppy disk. According to one embodiment of the present invention, the software program is installed on a hard disk. According to one embodiment of the present invention, the pad is created by the software program with a seed file located on a hard disk drive, i.e., a hard drive.

[0045] FIG. 5 is a flow diagram of a method according to the present invention, showing creation of ciphertext by XORing with the result of a pad XORed at an offset location with a selected password, the offset itself being a function of the selected password. In particular, a password is selected 50. Next, an offset is calculated 51 or otherwise determined. A move is then made 52 to the offset determined location. Then, the character of the pad at the offset location is extracted 53. The particular pad character is XORed 54 with the first character of the password, to produce a result, which in turn is XORed 55 with corresponding characters of plain text to produce ciphertext.

[0046] For purposes of the present invention, random is defined as an unpatterned, probabilistically unbiased sequence greater than or equal to one of elements (preferably bits, but for example also characters or numbers). Pseudo random means substantially but notcompletely random, for example but not limited to 99 percent random. By definition, a computer generated number is considered to be pseudo random.

[0047] Appendix A. below provides an example of C++ code according to an embodiment of the present invention.

[0048] PROGRAM CODE:

[0049] THE SWAPCRYPT INITIALIZATION PROGRAM FOLLOWS.

[0050] This program prompts the user to supply a seed file located on their computer. according to one embodiment of the present invention. This seed file is used in con)unction with a pseudo-random enerator to produce a pad key that is written into the data segment of a SwapCrypt program file, according to an embodiment of the present invention. Pseudo-random generators may typically not produce an adequate level of randomness for use in cryptography; therefore this program combines the output of a pseudo-random generator with a user supplied or selected seed file. The result is an output pad that exhibits superior randomness adequate to anchor a cryptographic stream cipher. Secondarily, this program allows the user to set a multi-character sign-on password for the SwapCrypt program. The sign-on password is encrypted into the data segment of the SwapCrypt program file, according to an embodiment of the present invention. A pseudo-random generator supplies material that is used to encrypt the sign-on password into a specific version of the SwapCrypt program.

[0051] The following function reads the information in the user supplied seed file and combines that information with the output of a pseudo-random number generator writing the result to the pad key in the data segment of the SwapCrypt program file. This function also writes a random test string to the SwapCrypt program file. This test string is used to check the validity of the password for the encrypted document.

[0052] The following line of code sets the position in the SwapCrypt program file for writing the file password test string.

[0053] fseek(fp, NOWAY, SEEK_SET); // file offset for faulty passwrd chk

[0054] The following for loop reads data from the user supplied seed file and combines that data with the output of a pseudo-random number generator to produce the 50 character file password test string. The file password test string is written to the SwapCrypt program file in this loop.

[0055] randomizes;

[0056] for (x=1; x<50; x++)

[0057] {

[0058] The variable crypt is used to retrieve characters (one at a time) from the user supplied seed file. The following do loop checks each character selected with the preceding character selected. A character match aborts the current selection and another is made until the preceding character and the present selection are different.

[0059] The following line of code sets the position in the SwapCrypt program file for writing the pad key encryption array.

[0060] fseek(fp, MUTATE, SEEK_SET); // file offset for encrypt array

[0061] The following for loop reads data from the user supplied seed file and combines that data with the output of a pseudo-random number generator to produce the 20000 character pad key encryption array. The pad key encryption array is written to the SwapCrypt program file in this loop.

[0062] for (x=1; x<20000; x++)

[0063] {

[0064] The variable crypt is used to retrieve characters (one at a time) from the user supplied seed file. The following do loop checks each character selected against the preceding character selected. A character match aborts the current selection and another is made until the preceding character and the present selection are different.

[0065] The following cascade of ifs re-seeds the pseudo-random generator from the system clock. This action produces a new sequence of pseudo-random numbers every 1500 characters.

[0066] THE SWAPCRYPT PROGRAM FOLLOWS.

[0067] The SwapCrypt program file is a Microsoft C++ MFC program broken into an SDI module set, according to one embodiment of the present invention. The modules are stdafx.cpp, mainfrm.cpp, swapcdoc.cpp, swapcvw.cpp, and swapcrpt.cpp. Modules other than swapcrpt.cpp contain text common to generic Windows programs. The module swapcrpt.cpp contains the code that performs encryption tasks according to the present invention.

[0068] Through the initialization process documented above, a 20,000 character array located in the data segment of the SwapCrypt program is filled with random data, according to an embodiment of the present invention. This array becomes the encryption pad key used by the program. The invention in the initialization program above was the method of the pad key creation that incorporates a seed file supplied by the user. Here in the SwapCrypt program the invention includes a method by which the utility of the pad key is expanded to more than a single use by way of a password that is used to both encrypt the pad key itself before use and to determine an offset position into the pad key that varies with each new password and/or with each new iteration of the pad key. This is particularly useful should the document being encrypted exceed the 20000 byte length of the pad key.

[0069] SwapCrypt is relies upon a stream cipher whereby each successive byte from the plain text document is XORed with each byte from the pad key. The pad key retains its original utility over time and through multiple uses. This is achieved by the use of a multi-character user supplied document password which may be unique to each document encrypted. Before the plain text document is XORed with the pad key, the pad key is XORed with the password. Furthermore, the password can be used to calculate an offset into the pad key where encryption begins. This offset will differ with different passwords. In the event that the plain text document is larger than the 20,000 byte pad key, a new offset is calculated with each iteration through the pad key. This use of the document password ensures that the security of the pad key will withstand a cryptanalysis attack should multiple documents be captured that were encrypted with the same version of the program.

[0070] THE STDAFX.CPP MODULE FOLLOWS

[0071] // stdafx.cpp: source file that includes just the standard includes #include “stdafx.h”

[0072] THE MAINFRM.CPP MODULE FOLLOWS

[0073] THE SWAPCDOC.CPP MODULE FOLLOWS

[0074] THE SWAPCVW.CPP MODULE FOLLOWS

[0075] THE SWAPCRPT.CPP MODULE FOLLOWS

[0076] The following global variables create a data segment space for the faulty password check, the pad key array, and the sign-on password and password encryption string.

[0077] The following code fragment reads in the 50 bytes of the file header that contains the faulty password check string. Decryption is aborted if the password supplied cannot decrypt the check string.

[0078] The following is the actual encryption decryption routine. Since the XOR operation reverses itself, the same process with slight modification will either encrypt or decrypt a file.

[0079] The variable flag (below) was previously given a value to identify which operation is indicated. If flag is TRUE the file will be encrypted.

[0080] In the following for loop the variable rollover is XORed with the user supplied five character document password. Rollover is a 16 byte character array that originally contains the sign-on password and the sign-on password encryption string, both of which are unique to the initialized version of the program. This for loop creates a 16 byte character array that is uniquely derived from initialized data in the program and the five character document password.

[0081] In the following for loop the five character document password is used to calculate a numeric offset that will be used to determine the starting position in the pad key where encryption will begin.

[0082] The following while loop reads in the plain text documented encrypts it.

[0083] The following conditional (if y equals offset) routine will execute if encryption has proceeded through the entire length of the pad key back to the offset position. This will occur if the plain text document is larger than 20000 bytes. In this event a new offset position is calculated and encryption continues after a jump to that new position. The current offset value is increased by the value of the byte in the pad key at the offset position. Should this create a new offset value greater than 20000 then the new offset becomes the value of the byte in the pad key located at the position in the pad equal to the current offset value divided by three.

[0084] The following line of code does the actual data encryption. The character in the pad key (mutate) at position y is XORed with the character in the array (rollover) at position x. That result is then XORed with the character in the plain text file (text buf) at position j to produce the cypher character. The subscript counters y, x and j are incremented and the loop proceeds to the next iteration until the entire file is processed.

[0085] The following line of code writes the cypher character to the output file on disk.

[0086] Appendix B. below provides an example of C++ code according to the present invention.

[0087] Appendix C. below provides an example of C++ code according to the present invention.

[0088] Appendix D. below provides an example of C++ code according to the present invention.