Format-preserving cipher

Abstract

A format-preserving cipher including an encryption and a decryption scheme supporting non-linear access to input data by allowing the selection of portions of data from a potentially larger dataset to be encrypted, thus avoiding a necessarily sequential access into the input plaintext data. The cipher first defines a forward mapping from the allowable ciphertext values to an integer set of the number of such allowable ciphertext values, and a corresponding reverse mapping. It also supports exclusion of a certain set of characters from the ciphering process. An encryption algorithm is provided that encrypts the input plaintext data while preserving its original format and length, and a corresponding decryption algorithm is provided. The cipher advantageously embodies the encryption and decryption of multi-byte values, composite datasets, and credit card numbers, thus fitting a variety of industrial needs.

Claims

1. A method of format-preserving ciphering, comprising the steps of: (a) providing predetermined criteria for selecting a portion of data to be ciphered; (b) providing a forward mapping from N allowable ciphertext values to an integer set {0 . . . N1}, and a corresponding reverse mapping from said integer set {0 . . . N1} to corresponding said N allowable ciphertext values, said allowable ciphertext values being non-contiguous; (c) iteratively accessing said portion in increments of size S bits, where S is set according to a downstream business process utilizing said format-preserving ciphering; (d) providing a key-stream and iteratively accessing it in increments of said size S bits; (e) determining a limiter value L as the difference of 2.sup.S and (2.sup.S modulo N); (f) ignoring in said ciphering any said accessed key-stream value in said size S bits, if said key-stream value is greater than or equal to said limiter value L; (g) allowing zero or more combinations of said S bits in said portion to be skipped from said ciphering; (h) encrypting said portion in an encryption module by taking the sum of said forward mapping of said accessed portion in (c) above and modulo N of said accessed key-stream value in (d) above, taking modulo N of said sum to produce a final sum, and taking said reverse mapping of said final sum; and (i) decrypting said portion in a decryption module by taking the difference of said forward mapping of said accessed portion in (c) above and modulo N of said accessed key-stream value in (d) above, taking modulo N of said difference, if said difference is less than 0 then adding N to said difference to produce a final difference, and taking said reverse mapping of said final difference.

2. The method of claim 1, where said format-preserving ciphering preserves an alpha-numeric format of said data.

3. The method of claim 1, where S=8, representing said increments of said size S to be bytes.

4. The method of claim 1, where said combinations of said S bits in step 1(g) represent characters selected from the group consisting of binary characters, unprintable characters, dashes and delimiting characters.

5. The method of claim 1, where said integer set {0 . . . N1} in said forward mapping and said reverse mapping is in no particular order.

6. The method of claim 1, where said key-stream is generated by utilizing a block cipher operating in CTR stream mode.

7. The method of claim 1, where said forward mapping maps said allowable ciphertext values as multi-byte values to said integer set {0 . . . N1}, and said corresponding reverse mapping maps said integer set {0 . . . N1} to corresponding said multi-byte allowable ciphertext values, and said size S divided by 8 equals to the number of bytes in each said multi-byte value.

8. The method of claim 1, where said format-preserving ciphering is used to implement a stream-cipher.

9. A system of format-preserving ciphering, comprising: (a) at least one portion of data to be ciphered; (b) a forward mapping from N allowable ciphertext values to an integer set {0 . . . N1}, and a corresponding reverse mapping from said integer set {0 . . . N1} to corresponding said N allowable ciphertext values, said allowable ciphertext values being non-contiguous; (c) said at least one portion iteratively accessed in increments of size S bits, where S is set according to a downstream business process utilizing said format-preserving ciphering; (d) a key-stream iteratively accessed in increments of said size S bits; (e) a limiter value L determined as the difference of 2.sup.S and (2.sup.S modulo N); (f) an encryption module for encrypting said at least one portion by taking the sum of said forward mapping of said accessed portion in (c) above and modulo N of said accessed key-stream value in (d) above, taking modulo N of said sum to produce a final sum, and taking said reverse mapping of said final sum; (g) said encryption module ignoring any said accessed key-stream value from said encrypting if said key-stream value is greater than or equal to said limiter value L; (h) said encryption module skipping zero or more combinations of said S bits in said at least one portion, from said encrypting; (i) a decryption module for decrypting said at least one portion by taking the difference of said forward mapping of said accessed portion in (c) above and modulo N of said accessed key-stream value in (d) above, taking modulo N of said difference, if said difference is less than 0 then adding N to said difference to produce a final difference, and taking said reverse mapping of said final difference; (j) said decryption module ignoring any said accessed key-stream value from said decrypting if said key-stream value is greater than or equal to said limiter value L; and (k) said decryption module skipping zero or more combinations of said S bits in said at least one portion, from said decrypting.

10. The system of claim 9, wherein said format-preserving ciphering preserves an alpha-numeric format of said at least one portion.

11. The system of claim 9, wherein said at least one portion is a composite dataset comprising a plurality of components.

12. The system of claim 11, wherein each of said plurality of components is selected from the group consisting of alpha characters, numeric characters, special characters and binary characters, and wherein said forward mapping and said reverse mapping is uniquely defined for each of said plurality of components.

13. The system of claim 9, wherein said integer set {0 . . . N1} in said forward mapping and said reverse mapping has no particular order.

14. The system of claim 9, wherein said forward mapping maps said allowable ciphertext values as multi-byte values to said integer set {0 . . . N1}, and said corresponding reverse mapping maps said integer set {0 . . . N1} to corresponding said multi-byte allowable ciphertext values, and said size S divided by 8 equals to the number of bytes in each said multi-byte value.

15. The system of claim 14, wherein said format-preserving ciphering is utilized to cipher a credit card number.

16. The system of claim 15, wherein a check-digit from said credit card number is skipped from said format-preserving ciphering, then said check-digit is computed based on the ciphered characters of said credit card number.

17. A system of format-preserving ciphering, comprising: (a) a credit card number iteratively accessed by each digit and processed by downstream business processes; (b) a forward mapping from N allowable ciphertext values to an integer set {0 . . . N1}; (c) a reverse mapping from said integer set (0 . . . N1) to corresponding said N allowable ciphertext values, said allowable ciphertext values being non-contiguous; (d) a key-stream iteratively accessed in increments of bytes; (e) a limiter value L determined as the difference of 256 and (256 modulo N); (f) an encryption module used for encrypting said credit card number by taking the sum of said forward mapping of said each digit and modulo N of said accessed key-stream value, taking modulo N of said sum to produce a final sum, and taking said reverse mapping of said final sum; wherein said encryption module ignores any said accessed key-stream value from said format-preserving ciphering, if said key-stream value is greater than or equal to said limiter value L.

18. The system of format-preserving ciphering of claim 17, wherein a check-digit of said credit card number is skipped from said encrypting and then calculated based on the encrypted digits of said credit card number.

19. A system of format-preserving ciphering, comprising: (a) an encrypted credit card number iteratively accessed by each digit and processed by downstream business processes; (b) a forward mapping from N allowable ciphertext values to an integer set {0 . . . N1}; (c) a reverse mapping from said integer set {0 . . . N1} to corresponding said N allowable ciphertext values, said allowable ciphertext values being non-contiguous; (d) a key-stream iteratively accessed in increments of bytes; (e) a limiter value L determined as the difference of 256 and (256 modulo N); (f) a decryption module for decrypting said each digit by taking the difference of said forward mapping of said each digit and modulo N of said accessed key-stream value, taking modulo N of said difference, if said difference is less than 0 then adding N to said difference to produce a final difference, and taking said reverse mapping of said final difference; wherein said decryption module ignores any said accessed key-stream value from said format-preserving ciphering, if said key-stream value is greater than or equal to said limiter value L.

20. The system of format-preserving ciphering of claim 19, wherein a check-digit of said encrypted credit card number is skipped from said decrypting and then calculated based on the decrypted digits of said encrypted credit card number.

Description

BRIEF DESCRIPTION OF THE DRAWING FIGURES

(1) FIG. 1 is a functional view of encryption performed by a block-cipher in Counter (CTR) mode in the prior art.

(2) FIG. 2 is a functional view of decryption performed by a block-cipher in Counter (CTR) mode in the prior art.

(3) FIG. 3 is a functional view of encryption performed by the format-preserving cipher according to the present invention.

(4) FIG. 4 is a functional view of decryption performed by the format-preserving cipher according to the present invention.

(5) FIG. 5 shows in a flowchart form the steps required to perform encryption according to the format-preserving encryption mechanism taught by the present invention.

(6) FIG. 6 shows in a flowchart form the steps required to perform decryption according to the format-preserving cipher mechanism taught by the present invention.

DETAILED DESCRIPTION

(7) The figures and the following description relate to preferred embodiments of the present invention by way of illustration only. It should be noted that from the following discussion, alternative embodiments of the structures and methods disclosed herein will be readily recognized as viable alternatives that may be employed without departing from the principles of the claimed invention.

(8) Reference will now be made in detail to several embodiments of the present invention(s), examples of which are illustrated in the accompanying figures. It is noted that wherever practicable, similar or like reference numbers may be used in the figures and may indicate similar or like functionality. The figures depict embodiments of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein.

(9) The present invention will be best understood by first reviewing the format-preserving cipher 100 according to the teachings of the current invention as illustrated in FIG. 3 and FIG. 4. The invention teaches how to build a cipher that will encrypt a dataset while preserving the format of the original data. FIG. 3 shows an encryption scheme that uses as input plaintext data 106 and key-stream 102 to produce ciphertext 114. According to the teachings of the current invention, input key-stream 102 can be produced by any existing popular methods, such as, a block-cipher using Counter (CTR) mode, that uses a cryptographic key 104 to encrypt a nonce (not shown) combined with a counter (not shown). Those familiar with the art will recognize that there are many alternative ways of producing a key-stream. For example, Rivest Cipher 4 (RC4), also known as Alleged RC4 or ARCFOUR, is another popular stream cipher that can be easily used by cipher mechanism 100 shown in FIG. 3. Preferably, the key-stream is generated using a block cipher operating in stream mode such as AES in CTR mode, which is the case in a preferred embodiment.

(10) Throughout the following explanation, reference to the input unencrypted data will be made as input plaintext data, original input data or simply plaintext data as is commonly understood in the industry. Similarly reference to encrypted data will be made as encrypted or ciphertext data as is known in the art. It should be noted, that although the term plaintext may seemingly imply that the input data can only be in textual form, the present invention and its teachings are not restricted to ciphering only textual data, but also any other type of data, such as, binary or non-printable data. Because the cryptographic industry refers to the input or unencrypted data as plaintext data, this convention will be adopted in the following teachings to be consistent with the skills and terminology of the art, and as mentioned, the instant invention does not impose any restriction on the format of the original input data.

(11) Furthermore, and as will be understood by those skilled in the art of cryptography, a cipher (or cypher) is referred to a mechanism/method/system/scheme/algorithm for performing encryption or decryption. This will be the meaning attributed to the term cipher or in verb form cipher/ciphering in this disclosure. Therefore, ciphering may refer to either encryption or decryption as will be apparent from the context.

(12) As disclosed by the present invention, cipher mechanism 100 of FIG. 3, first allows the selection of specific portions of data 108 from the overall plaintext dataset 106. In FIG. 3 and FIG. 4 the reference number 106 represents individual data bits or bytes of the entire dataset as squares, while the squares that are filled with circular wheels with cross bars, as denoted by reference number 108, represent bits or bytes of the actual fields or portions of input data that have been selected for the ciphering process.

(13) This initial selection of parts of data to be encrypted is made on predetermined criteria which could be defined based on the requirements of the particular application requiring the format-preserving cipher of the present invention. This pre-selection is important because it lends the ability to the cipher to only encrypt or decrypt certain pieces of data that need to be secured, and not necessarily the entire plaintext dataset. For example, there may be Personally Identifiable Information (PII) or privacy data, such as a social security number (SSN), or Payment Card Industry (PCI) data such as a credit card number (CCN) embedded in the original plaintext dataset. It may not be efficient or possible to encrypt this entire dataset, only a small portion of which is in fact really needed to be secured, in order to meet either external industry compliance requirements, e.g. that of PCI compliance, or an internal company dictate.

(14) Therefore, the predetermined criteria for this initial selection can be based on data security requirements at hand. For example, the criteria could include searching for strings in the input plaintext data that match the format: nnn-nn-nnnn, where each n denotes a numeric digit. In other words, the criteria searches for any strings of digits that has 3 digits before a dash -, two digits after that, then another dash and then 4 digits after that. This search string or format represents a social security number. Similarly, the criteria could include searching for patterns like nnnn nnnn nnnn nnnn, which would represent a search for strings of 16 digits, representing a Visa or Mastercard number and Exp: mm/yyyy, which would represent a search for the expiration date of the credit card, and so on. People skilled in the art will recognize that one can construct a variety of regular expression searches that would search for a variety of PII, PCI, Healthcare, or other private data in the input plaintext dataset, as the predetermined criteria for selecting the exact portions of input data that need to be secured.

(15) The present invention allows such a non-linear access to data so as to only encrypt or decrypt the specific pieces of data 108 that may indeed need to be protected. Once the pre-selected portions of data 108 are obtained from the overall plaintext dataset 106, the algorithm of the present invention iterates over the plaintext data 108 that needs to be encrypted and feeds this data, along with a keystream 102 to an encryption module 110. It will be understood by those skilled in the art that there are a variety of tools and techniques available to implement such a data access scheme to access portions of data 108 that need to be encrypted from the entire dataset 106 to encryption module 110. For example, one could have an array that is populated with portions 108 of data that are to be encrypted, along with pointers to where those portions 108 of data are located in the entire dataset 106, and then feed those entries of that array to encryption module 110. Such data access techniques are commonplace in the art and will not be discussed in detail in this specification, and are merely represented by process box 112 in FIG. 3.

(16) Subsequently, as illustrated in FIG. 3, encryption module 110 encrypts input data 108 with a value from keystream 102 according to the teachings of the invention as will be explained below, to produce ciphertext 118. The ciphertext 118 is embedded into the original larger dataset 106, where unencrypted data 108 used to be, to produce protected dataset 114. Using our example above, one will take individual portions 118 of ciphertext and use the pointers stored in the above array to embed format-preserved ciphertext according to the current invention, into the original dataset 106, to produce protected dataset 114 as illustrated in FIG. 3. Again, there are a number of tools and techniques available to those skilled in the art for such data insertion schemes to embedded ciphertext portions of data 118 into original dataset 106 and are merely represented by process box 116 in FIG. 3.

(17) Conversely, as illustrated in FIG. 4, cipher mechanism 100 of the current invention has a corresponding decryption mechanism that takes encrypted or ciphertext data 118 from the overall protected dataset 114 obtained above, again using some familiar data access scheme as represented by 112, to access and feed portions of ciphertext data 118 that need to be decrypted along with keystream 102 to a decryption module 120. It then traverses over ciphertext data 118 and keystream 102 to produce plaintext data 108 that after reinsertion, again using a familiar data insertion scheme 116, into input dataset 106 at the original locations, results in the original plaintext dataset 106. In the following explanation, we will take a closer look at the abovementioned encryption and decryption schemes as taught by the current invention.

(18) First to restate, a key advantage of the format-preserving encryption mechanism taught by the present invention is that it allows for non-linear access to input data to be encrypted. That is, the algorithm of the instant invention allows a selection of portions of data from a potentially much larger input plaintext dataset to be encrypted (and decrypted) by the downstream cipher based on a variety of predetermined criteria that may be suitable for a given application. Since there are generally small portions or strings of data that need to be protected in a typically large dataset, such a scheme would result in substantial performance improvements since the whole dataset does not need to be encrypted or decrypted. Specifically referring to FIG. 3 and FIG. 4, selected portions 108 may be a small subset of the overall dataset 106. Moreover, as stated above and will be obvious, the format preserving cipher of the present invention will produce encrypted portions of ciphertext 118 that have the same format and length as the corresponding input plaintext portions 108.

(19) Let us turn our attention to the encryption and decryption cipher scheme taught by the present invention. The parts of the scheme that are invoked each time an encryption or decryption operation of the present invention is performed are depicted by encryption module 110 in FIG. 3 and decryption module 120 in FIG. 4. Note that the below explanation teaches the various steps of the algorithm of the cipher of the instant invention. Skilled artisans will recognize that there will be several ways to implement the below algorithm. As such alternative arrangements of the below steps are possible in the light of a given implementation without deviating from the principles of the invention. For example, as disclosed by the invention, steps of the algorithm that need to happen only once, do not need to be repeated in encryption module 110 or decryption module 120 for each encryption and decryption operation. These initialization steps will be explained in the below teachings. Similarly, other optimizations of the algorithm are possible within the scope of the invention.

(20) According to the format-preserving cipher taught by the present invention, a determination of the N allowable values permitted in the output or ciphertext is first made. Typically this determination stays static during the course of the operation of an encryption/decryption regime. For example, if the format-preserving cipher of the present invention requires the preservation of alpha-numeric format, then these allowable values will be the characters 0 through 9, a through z, A though Z and any other special characters such as dashes, etc. Such a requirement might exist to encrypt residential or commercial addresses as an example.

(21) Alternatively if the intent is to keep the ciphertext in numeric form, as is the case for Social Security Numbers (SSN) or Credit Card Numbers (CCN), then these allowable values will be 0 through 9 and N will be 10. It is these allowable ciphertext values that enable the preservation of the format of the original data in the output ciphertext. After the determination of these N allowable values, the cipher then creates a forward mapping M of these allowable ciphertext values into a corresponding set of N integer values {0 . . . N1}, and also the creation of a reverse mapping R from the given set of integer values {0 . . . N1} to the corresponding N allowable ciphertext values. Of course, the encryption and decryption engines of the cipher being taught by the present invention need to agree on this forward mapping M and reverse mapping R a priori before the commencement of ciphering operations.

(22) Taking the numeric format-preserving encryption example above, the forward mapping M and reverse mapping R are represented in Table 1 and Table 2 below.

(23) TABLE-US-00001 TABLE 1 Value Mapping M 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

(24) TABLE-US-00002 TABLE 2 Value Mapping R 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

(25) This example assumes that data is being encrypted in character sized chunks as will be the case of typical byte-oriented architectures of most computer systems. However the teachings of the present invention are agnostic to the size of such chunks and can be implemented in increments of any given number of bits, let us say S bits. The cipher algorithm then determines a limiter value L as the difference of the maximum number representable in S bits, and the maximum number representable in S bits modulo operation the number N of allowable values in the ciphertext. Mathematically, the limiter value L can be represented by the following equation:
L=2.sup.S(2.sup.S modulo N)Eq. (1)
For byte-oriented systems with S=8, obviously:
L=256(256 modulo N)Eq. (2)

(26) The encryption mechanism taught by the current invention then iterates over the portions of input plaintext data that need to be encrypted as identified by reference number 108 in FIG. 3 according to above explanation. Similarly, the decryption mechanism taught by the current invention iterates over the portions of encrypted ciphertext data that need to be decrypted as identified by reference number 118 in FIG. 4 according to above explanation. Let us denote each accessed chuck of S bits of input plaintext data by PT.sub.j and each accessed chunk of encrypted ciphertext data as CT.sub.j where j is a traversal iterator or index over portion PT of plaintext data for encryption or corresponding portion CT of ciphertext data for decryption. The cipher also iterates over key-stream 102 in chunks of S bits. Let us denote each accessed chunk of S bits of key-stream 102 by KS.sub.i where i is a traversal iterator or index over key-stream KS.

(27) In other words, KS.sub.i and PT.sub.j respectively represent the ith key-stream value, and jth plaintext value during the encryption operation of input plaintext, and KS.sub.i and CT.sub.j respectively represent the ith key-stream value, and jth ciphertext value during the decryption operation of encrypted ciphertext. As taught above, preferably, the key-stream is chosen to be the familiar block cipher in CTR mode or an RC4 key-stream. It should be noted that any secure key stream can be used within the scope of the present invention.

(28) The format-preserving encryption and decryption mechanisms of the present invention further allow defining a set of values represented by the S bits in which input data and the key-stream are accessed, to be skipped during the encryption and decryption operations. In other words, if certain characters from the input data are to bypass the encryption or decryption operations altogether, the cipher algorithm of the present invention allows such excluded values to be specified. An example use-case of such an exclusion-list would be dashes - of a social security number, thus ensuring that the format-preserving cipher of the present invention will produce encrypted social security numbers that are also in the format nnn-nn-nnnn. Other examples could include the . in the domain name of an email address. However doing so will leak the formatting information of the input plaintext into the ciphertext and should be done only if the advantages outweigh this lessening of security.

(29) As input data and key-stream values are iterated over as PT.sub.j and KS.sub.i respectively, the algorithm ignores the values of the key-stream that are greater than or equal to the limiter value L calculated above. This is required to ensure that the ciphertext values will be within the bounds of the allowable of ciphertext values as specified prior to the initiation of the cipher. Similarly, as input ciphertext data and key-stream values are iterated over as CT.sub.j and KS.sub.i respectively, the algorithm ignores the values of the key-stream that are greater than or equal to the limiter value L calculated above. Note, as convenient, we will use the terms input plaintext to represent data being fed to encryption module 110 of FIG. 3, and input ciphertext for encrypted ciphertext being fed to decryption module 120 of FIG. 4.

(30) Let us now turn our attention to the implementation of encryption module 110 and decryption module 120 illustrated in FIG. 3 and FIG. 4 respectively. For encryption module 110 of FIG. 3, as input data 108 and key-stream 102 are iterated over as PT.sub.j and KS.sub.i respectively according to above explanation, encryption of input PT.sub.j is accomplished by taking the sum of the forward mapping M of the currently accessed chunk PT.sub.j of input data and the current key-stream value KS.sub.i modulo N, then taking modulo N of this sum thereby producing a final sum, and finally taking the reverse mapping M of this final sum to produce the format-preserved encrypted value corresponding to the current chunk of input or plaintext data PT.sub.j.

(31) Conversely, for decryption module 120 of FIG. 4, decryption of ciphertext data 114 in a given chunk represented by CT.sub.j is accomplished by taking the difference of the forward mapping M of ciphertext value CT.sub.j and the currently accessed value of key-stream 102 represented by KS.sub.i modulo N, then taking modulo N of this difference. If this difference is less than 0, adding the number N of allowable ciphertext values to this difference to produce a resultant value, and finally taking the reverse mapping R of this resultant value to produce the original plaintext value PT.sub.j for the corresponding ciphertext value CT.sub.j.

(32) The following pseudo-code represents one implementation of the above algorithm. As stated earlier, it is entirely conceivable to arrive at equivalent and alternative code for the implementation of the above taught cipher within the scope of the instant invention.

(33) Encryption:

(34) TABLE-US-00003 if KS.sub.i >= L then i++ // ignore this key-stream value else if PT.sub.j != any value defined in the exclusion-list then // do not encrypt values to be skipped p = M(PT.sub.j) e = (p + (KS.sub.i mod N)) mod N // encrypt output R(e) i++ // advance to next key-stream byte else output PT.sub.j // do not encrypt values to be skipped fi j++ // iterate to the next data value to be encrypted fi.
Decryption:

(35) TABLE-US-00004 if KS.sub.i >= L then i++ // ignore this key-stream value else if CT.sub.j != any value defined in in the exclusion-list then // do not decrypt values to be skipped p = M(CT.sub.j) d = (p (KS.sub.i mod N)) mod N // decrypt if d < 0 d = N + d // subtract abs(d) from N output R(d) i++ // advance to next key-stream byte else output CT.sub.j // do not decrypt values to be skipped fi j++ // iterate to the next data value to be decrypted fi.

(36) FIG. 5 and FIG. 6 show in a flowchart form the encryption and decryption algorithms respectively, of the format-preserving cipher taught by the current invention. Note that in FIG. 5 and FIG. 6, the initialization steps required to set up the initial parameters, including computing the value of limiter L and setting up the exclusion-list are performed first, and then encryption and decryption loops are executed. These loops containing the repeating steps of the cipher will indeed be encapsulated in the respective encryption module 110 of FIG. 3 and decryption module 120 of FIG. 4. It should be further noted, that in a given implementation the common initialization steps required for encryption and decryption may be merged into a common routine, let us say cipher, that can perform both encryption and decryption.

(37) It will be understood by skilled artisans that if key-stream KS is exhausted prior to completion of encryption or decryption of the entire input plaintext or ciphertext datasets respectively, additional key-stream values can be generated depending on the specific algorithm used for key-stream cipher KS. For example, for the block-cipher CTR mode implementation of key-stream cipher, this will be accomplished by incrementing the counter for the CTR mode, and encrypting another block of the required chunk's size worth of nonce and counter combination with the cryptographic key used for the CTR mode.

(38) The methods of the invention teach many preferred embodiments well suited for a number of applications in the data security industry. In a preferred embodiment the ciphertext 114 in FIG. 3 produced by the present invention is alphanumeric. This will be a familiar requirement for a lot of database applications requiring the preservation of alphanumeric format for the tables predefined in the database(s). Preferably, the number of bits S in which chunks of data and key-stream is accessed is 8, thereby conforming to the specifications of the commonly used byte-oriented architectures of the present day IT industry.

(39) As taught above, the invention allows for the specification of an exclusion-list of certain combination of input bits from the ciphering process. In a character-oriented or byte-oriented architecture, such an exclusion-list preferably includes binary characters, unprintable characters, dashes, delimiting characters, etc. Preferably, the allowable ciphertext characters as taught above are non-contiguous. This allows for the specification of an encryption regime that can preserve a non-standard format that may have characters segmented in various chunks of non-consecutive allowable and unallowable values. An example of such non-contiguous ciphertext characters would be an allowable ciphertext of the set of ASCII characters 0123456789ABCDEF as commonly used to represent hexadecimal values. 0-9 respectively correspond to ASCII values 48-57 and A-F respectively correspond to ASCII values 65-70. Obviously, these value ranges are not contiguous.

(40) In a highly preferred embodiment, the invention allows for the specification of multi-byte values, or a string of allowable characters in the ciphertext. This feature is important because in certain encryption regimes only a certain combination or string of allowable characters or values are permitted to keep the integrity of the downstream business processes. For example, in a credit card number the first six digits, usually referred to as Issuer Identification Number (IIN) contain a valid banking institution code that needs to have certain values in order to pass the validation checks of business systems downstream from the cipher. It would be desirable to produce ciphertext values so that those downstream validation checks will not be violated, and the present invention allows for such a capability.

(41) Taking the above example, the forward mapping M of multi-byte IIN values to the corresponding set of N allowable ciphertext values, according to the teachings of the present invention, is shown in Table 3 below, where values in the first column are exemplary values for valid IIN codes.

(42) TABLE-US-00005 TABLE 3 Value Mapping M 400610 0 400936 1 400937 2 400938 3 400941 4 400942 5 400844 6 401171 7 401106 8 . . . . . . 409311 N 1

(43) Encryption and decryption proceed in the same manner as the previous embodiments except that size S of bits, as taught above, needs to be chosen such that when input plaintext data is accessed as PT.sub.k or ciphertext data is accessed as CT.sub.j according to the above algorithm, enough bits are accessed to ensure that the entire input multi-byte value can be encrypted or decrypted. Further, when key-stream KS is accessed as KS.sub.i, enough bits of the key-stream are accessed so that they can be used to encrypt or decrypt the entire multi-byte value. This is accomplished by ensuring that S divided by 8 is equal to the number of bytes in each of the input multi-byte plaintext value. Of course, the assumption here is that these multi-byte values that need to be encrypted or decrypted are of fixed and equal lengths.

(44) Given this scheme, in the example shown in Table 3 above, the multi-byte values are of 6 bytes in length, that means that S should be chosen to be 48 bits, so that 48 divided by 8 equals 6 bytes, and N is the number of allowed values. The same method for calculating limiter value L of Eq. (1) is used as in earlier embodiments, that is:
L=2.sup.S(2.sup.S modulo N)

(45) A single encryption would consume the 6 bytes of plaintext IIN and produce a 6 byte encrypted IIN. After the initial IIN has been encrypted, normal encryption process as explained for the earlier embodiments can resume, where S is selected to be of normal size e.g. 8.

(46) Additionally, as is known to the skilled artisans, that the last character of a CCN is a checksum of the previous digits, and is also known as the check-digit. The skilled artisans will also recognize that such a legitimate check-digit as obtained using the below described scheme would be required to ensure that the sanctity of downstream financial processes and systems is not violated. The check-digit is usually calculated using the Luhn algorithm. To make a fully legitimate format-preserved encrypted CCN, the checksum needs to be recalculated on the encrypted value of the remainder digits of the CCN, using the checksum algorithm for that card which can be determined using the original IIN.

(47) Therefore, during encryption, the check-digit will be left out of the encryption process, or skipped. Once the rest of the CCN has been encrypted, the check-digit will be calculated based on the remainder encrypted digits of the CCN using an appropriate algorithm, which may be the Luhn algorithm. During decryption, and conversely, the check-digit will be skipped. After the rest of the CCN has been decrypted, then the check-digit will be recalculated based on the remainder original digits of the CCN, again using the appropriate algorithm for the application and the banking institution.

(48) It will be obvious to those skilled in the art, that the multi-byte ciphering embodiment presented above can be used for encrypting any multi-byte values and not just credit card numbers. The techniques of the embodiment can be invoked as and when desired during the course of normal character-based or byte-sized encryption regimes implemented by earlier embodiments, and once the desired multi-byte values have been encrypted, normal character-based or byte-sized cipher operations can resume. Of course, the converse is true for the decryption process.

(49) In another preferred embodiment the forward mapping from the allowable ciphertext values to the corresponding set of integers {0 . . . N1} as taught above, does not pre-ordain a certain ordering of that set of integers. That means, that as long as there is a unique forward mapping M from input ciphertext values to the set {0 . . . N1} where the values of set {0 . . . N1} can be in any order, and a corresponding reverse mapping R that uniquely maps values of the set {0 . . . N1} in any order to the corresponding ciphertext values, the format-preserving cipher taught by the current invention will function properly. This further reduces complexity of implementation in the practice of the instant invention.

(50) In yet another highly preferred variation of the format-preserving cipher according to the invention, two different forward mappings and correspondingly two different reverse mappings are used for two different components of a composite plaintext dataset. An exemplary use of such a variation would be when the plaintext comprises an initial set of T alpha characters, followed by numbers. Then a first forward mapping M.sub.1 is defined that maps a first set of N.sub.1 allowable ciphertext values to the integer set {0 . . . N.sub.11}. A second forward mapping M.sub.2 is also defined that maps a second set of N.sub.2 allowable ciphertext values to integer set {0 . . . N.sub.21}. Similarly, two reverse mappings R.sub.1 and R.sub.2 are defined that map the given sets of integer values {0 . . . N.sub.11} and {0 . . . N.sub.21} to the corresponding N.sub.1 and N.sub.2 allowable ciphertext values respectively.

(51) The two forward mappings M.sub.1 and M.sub.2 and the two reverse mappings R.sub.1 and R.sub.2 are then used to encrypt the alpha component and the numeric component respectively of the plaintext using the above presented encryption algorithm. Similarly, a converse process is used for decryption using the decryption algorithm presented above. Therefore unsurprisingly, in the decryption algorithm, the two forward mappings M.sub.1 and M.sub.2 and the two reverse mappings R.sub.1 and R.sub.2 are used to decrypt the alpha component and the numeric component of the plaintext respectively using the above presented decryption algorithm.

(52) As with earlier embodiments, the encryption and decryption engines of the cipher variation being taught will need to agree on the forward mappings M.sub.1 and M.sub.2, and the corresponding reverse mapping R.sub.1 and R.sub.2, a priori before the commencement of ciphering operations. Note that the sets of integer values {0 . . . N.sub.11} and {0 . . . N.sub.21} will always be overlapping as they would both start with 0 and progress onwards, however the corresponding sets of allowable ciphertext values must not overlap in order for encryption and decryption regimes to work properly.

(53) Note further that the same keystream is used for encrypting and decrypting both the alpha and numeric components of the composite plaintext in the above example. Obviously, the invention admits of any other combination of various types of input characters as part of the composite plaintext using the above described scheme. In extensions of the above scheme, three, four or even more sets or pairs of forward/reverse mappings may be employed to encrypt/decrypt multiple components of the composite plaintext.

(54) The encryption and decryption algorithms in pseudo-code for the present variation applied to the above example of using two forward and reverse mappings M.sub.1, M.sub.2 and R.sub.1, R.sub.2 for ciphering a composite dataset of an initial T bytes of alpha characters, and the reminder bytes of numeric characters, are now presented below. As will be apparent, subscript 1 in the forward and reverse mappings M.sub.1 and R.sub.1 is used to represent the mappings used in the ciphering of the alpha component of the composite dataset, and subscript 2 is used to represent the mappings M.sub.2 and R.sub.2 used in the ciphering of the numeric component of the composite dataset.

(55) As before with earlier embodiments, it is entirely conceivable to produce alternative implementations of the present composite dataset ciphering scheme within the scope of the invention, than the one represented by the below algorithms.

(56) First the two limiter values L.sub.1 and L.sub.2 are computed using Eq. (1) for integer sets {0 . . . N.sub.11} and {0 . . . N.sub.21}, i.e.
L.sub.1=2.sup.S(2.sup.S modulo N.sub.1).fwdarw.L.sub.1=(256 modulo N.sub.1)//S=8 for byte-sized operation, and
L.sub.2=2.sup.S(2.sup.S modulo N.sub.2).fwdarw.L.sub.2=(256 modulo N.sub.2)//S=8 for byte-sized operation
Encryption:

(57) TABLE-US-00006 Loop if more PT.sub.j values to be encrypted If j <= T // alpha component first if KS.sub.i >= L.sub.1 then i++ // ignore this key-stream value else if PT.sub.j != any value defined in the exclusion-list then // do not encrypt values to be skipped p = M.sub.1(PT.sub.j) e = (p + (KS.sub.i mod N.sub.1)) mod N.sub.1 // encrypt output R.sub.1(e) i++ // advance to next key-stream byte else output PT.sub.j // do not encrypt values to be skipped fi j++ // iterate to the next data value to be encrypted fi else then // now numeric component if KS.sub.i >= L.sub.2 then // alpha component first i++ // ignore this key-stream value else if PT.sub.j != any value defined in the exclusion-list then // do not encrypt values to be skipped p = M.sub.2(PT.sub.j) e = (p + (KS.sub.i mod N.sub.2)) mod N.sub.2 // encrypt output R.sub.2(e) i++ // advance to next key-stream byte else output PT.sub.j // do not encrypt values to be skipped fi j++ // iterate to the next data value to be encrypted fi fi End Loop.
Decryption:

(58) TABLE-US-00007 Loop if more CT.sub.j values to be decrypted If j <= T // alpha component first if KS.sub.i >= L.sub.1 then i++ // ignore this key-stream value else if CT.sub.j != any value defined in in the exclusion-list then // do not decrypt values to be skipped p = M.sub.1(CT.sub.j) d = (p (KS.sub.i mod N.sub.1)) mod N.sub.1 // decrypt if d < 0 d = N.sub.1 + d // subtract abs(d) from N.sub.1 output R.sub.1(d) i++ // advance to next key-stream byte else output CT.sub.j // do not decrypt values to be skipped fi j++ // iterate to the next data value to be decrypted fi else // now numeric component if KS.sub.i >= L.sub.2 then i++ // ignore this key-stream value else if CT.sub.j != any value defined in in the exclusion-list then // do not decrypt values to be skipped p = M.sub.2(CT.sub.j) d = (p (KS.sub.i mod N.sub.2)) mod N.sub.2 // decrypt if d < 0 d = N.sub.2 + d // subtract abs(d) from N.sub.2 output R.sub.2(d) i++ // advance to next key-stream byte else output CT.sub.j // do not decrypt values to be skipped fi j++ // iterate to the next data value to be decrypted fi fi End Loop.

(59) As already stated above, it is conceivable to have alternative ways of implementing the encryption and decryption algorithms of the composite dataset ciphering scheme of the present variation within the scope of the invention, than represented by the above provided pseudo-code.

(60) In view of the above teaching, a person skilled in the art will recognize that the methods of present invention can be embodied in many different ways in addition to those described without departing from the principles of the invention. Therefore, the scope of the invention should be judged in view of the appended claims and their legal equivalents.