Data mapping method and apparatus with multi-party capability6438230Abstract Mapping or encryption of a message made up of characters from a character set is provided. Each character in the character set is associated with one or more disjoint real number intervals. Each character in the message is represented by a real number randomly selected from one of the intervals with which the character of the character set is associated. In some aspects, the resulting set of real numbers is translated to another set of real numbers by the application of a translation function or successive application of two or more translation functions. The translation functions never result in two different real numbers being translated to a single number. Claims What is claimed is: Description The present invention relates to encryption or other data mapping and in particular to mappings from discrete characters to value ranges preferably permitting multiple parties to contribute to the encryption.
{
Select at random an element i of C for which:
C[i].Count <C [i].IntervalCount
Set [j].Index = i
Set C[i].Count + = 1
Set S[j].I.sub.L = LowerBound
ifC[i].Count = C[i].IntervalCount
Set S[j].I.sub.U = S[i].I.sub.L + (C[j].Proportion * (Y-X) -
C[i].Sum)
otherwise
Select a value .alpha. such that:
S[j].I.sub.L .alpha. < S[j].I.sub.L + (c[i].Proportion * (Y - X)
- C[i].Sum)
Set S[j].I.sub.U = .alpha.
(Ideally .alpha. should be a random value; but it would be
best to prevent situations in which any subinterval length is
too close to zero.)
Set C[i].Sum + = S[j].I.sub.U - S[j].I.sub.L
Set LowerBound = S[j].I.sub.U
}
As an illustration of the first interval-generation example, suppose the character set consists of the characters: A, B, C, D, E and that we wish to assign the following values for the number of subintervals and the relative frequency of each:
Character Number of subintervals Relative Frequency
A 2 0.20
B 1 0.18
C 3 0.16
D 1 0.21
E 5 0.25
Step 1: The 5 element array C will be as follows: C[1]={A, 2, 0.20, 0, 0} C[2]={B, 1, 0.18, 0, 0} C[3]={C, 3, 0.16, 0, 0} C[4]={D, 1, 0.21, 0, 0} C[5]={E, 5, 0.25, 0, 0} Step 2: Set [X,Y]=[2.0, 10.0] Step 3: The array S will have 12 elements. Set LowerBound=2.0 Setj=1 Randomly pick an index i of the array C for which: C[i].Count C[i].IntervalCount Say that it is 3. Then: S[1].Index=3 C[3].Count=1 S[1].I.sub.L =2.0 Select a value .alpha. such that: 2.0<.alpha.<2.0+0.16*(8.0)-0.0)=3.28 Say that the value of .alpha.=2.44 S[1]..I.sub.U =2.44 C[3].Sum=0.44 LowerBound=2.44 S[1]={3, 2.0, 2.44} C[3]={C, 3, 0.16, 1, 0.44} Setj=2 Randomly pick an index i of the array C for which: C[i].Count<C[i].IntervalCount Say that it is 2. Then: S[2].Index=2 C[2].Count=1 S[2].I.sub.L =2.44 Because there is only to be 1 interval for B, S[2]..I.sub.U =2.44+0.18*8=3.88 C[2].Sum=1.44 LowerBound-3.88 S[2]={2, 2.44, 3.88} C[2]={B, 1, 0.18, 1, 1.44} Continue as above for the remaining 10 elements of the array S. In a second example of a procedure for selecting intervals, as depicted in FIG. 3, the procedure can begin with selection of a real number range, within which the intervals will lie. The range which is selected can theoretically be any real number range. Any real number range (no matter how small) will contain an infinite number of real number points within the range and thus there will always be sufficient numbers to achieve the goals of the present invention. However, because present computing systems represent real numbers using a finite number of bits or digits, for any given interval, there are a finite number of real numbers that can be distinguishably represented in computers and the intervals should be selected such that the number of real numbers that can be distinguishably represented by the computer in the interval is sufficiently large, such as being at least equal to (preferably at least twice) the character-length of the plaintext to be encrypted. This will make it possible for most, preferably all, characters in the plaintext to be represented by a unique real number in the cyphertext. Moreover, a real number range which is excessively large will require relatively long numbers to represent points within the range and accordingly the range should not be so large that truncation and/or rounding errors (introduced in the representation of large numbers) introduces errors which are sufficiently large as to make it difficult to identify the intervals within which certain real numbers lie. As will be understood by those of skill in the art, the size of truncation or rounding errors would be affected by such choices as whether to perform all calculations in binary representation or to convert between digital and binary representations (which can introduce another level of rounding error) and by the choice of whether to use single precision, double precision, triple precision calculations and the like. FIG. 5A is a graphic depiction of the result of one example of an interval selection and mapping scheme. In the example of FIG. 5A, a plaintext (e.g. as illustrated in Table I), is made up of pattern of four "unique characters" or tokens "A", "B", "C" and "D". In the example of FIG. 5A, the real number range which is selected 312 has a lower bound 512 of 0.0491 and an upper bound 514 of 0.9936 providing a total length (L) of the range 516 equal to 0.9445 (see Table II). For purposes described below, a constant "H" is defined which is equal to one half the length 516 (H=L/2+L =0.47225).
TABLE I
Plaintext
B A C C C A D B C A C
A C B C A C C B A A C
A C A B C C B A C B D
A A C B C A C C A C B
There are numerous ways in which the range 516 can be partitioned or subdivided into intervals. The total number of intervals needed will be at least equal to the number of unique characters which occur in the plaintext (i.e. 4, in the example of Table I). Thus, the present invention could be implemented by partitioning the real number range into four intervals, in this example. In other embodiments, any or all of the four unique characters in the plaintext can be mapped onto two or more intervals. Thus embodiments of the present invention can be implemented, in the context of the example of Table I, using five or more intervals. Since decryption (described below) will require that an interval be associated with no more than one of the four unique characters, the intervals must be disjoint (non-overlapping). The intervals need not be, but some or all may be, spaced-apart (such that the lower bound of one interval is greater than the upper bound of the next-lower interval). One advantage of providing non-spaced-apart intervals ("contiguous") is that the definition of the intervals in the real number range can be communicated using only a single real number to define each interval, such as using the lower bound of each interval, since (except for the highest interval) the upper bound of any interval will equal the lower bound of the next-higher interval). Thus, in this system, a partition into R intervals can be communicated using R+1 real numbers. However, if the intervals are spaced-apart, the lower bound of each interval must be separately defined and thus communication of R spaced-apart intervals would require 2 R real numbers. Because decryption also involves determining within which interval a particular real number lies, the real numbers that will make up the cyphertext (as described below) should not be so close to an interval endpoint that rounding error could cause the decryption procedure to erroneously consider that point to lie outside the interval. If all intervals are spaced-apart sufficiently far (such as at least equal to the rounding error, preferably after considering the effect of any monotonic function transforms as described below) real numbers would never be mis-assigned to an incorrect mapped interval as a result of rounding. However, a real number which is within an interval, but near an endpoint, could, through rounding error, be erroneously considered to be not a part of any mapped interval. Another manner of handling rounding error in this regard is to assure that no random numbers are used as part of the mapped numbers in the cyphertext which are within one (or two) rounding error distances of an interval end point. This procedure, besides introducing additional computational test steps, and requiring a computation or estimate of rounding error (preferably including the effect of any transforms) also could provide the astute code-breaker with information about where interval boundaries may lie (since this procedure would result in a cyphertext which had no real numbers in areas of the number line near the interval endpoints). Accordingly, to disguise the location of the interval end points, embodiments of the present invention can also include inserting, into the cyphertext (preferably randomly) "red herring" real numbers which lie in the spaces between the mapped intervals (or within a predefined distance of the interval end points) and wherein such "red herring" real numbers will be ignored when they occur in the cyphertext. By providing a partition of the real number range in which a relatively large portion of the range, such as a total of 50% or, preferably more, is made up of inter-intervals spaces, i.e. non-mapped intervals, the cyphertext can preferably include a sufficient number of (and preferably a proper distribution of) "red herring" real numbers that the resulting cyphertext will have the appearance of real numbers which are randomly distributed over the real number range, thus providing little information regarding interval definitions, letter frequencies and the like. Regardless of whether a given unique-character is assigned to one interval or many intervals, for each unique character there will be a total real number length equal to the sum of all the lengths of all intervals to which the unique character is mapped. It would be possible to partition the range 516 into, e.g. four (or more) equally sized intervals. However, this approach would have the disadvantage that the interval associated with the most frequently-occurring character in the plaintext would have a relatively dense population of real numbers in the cyphertext. A would-be code-breaker might be able to discern the correspondence of, e.g. the most densely populated interval to the most frequent character. In order to prevent a would-be code-breaker from successfully identifying the interval associated with, e.g. the most-frequent letter or character in the cyphertext as the interval having the most dense distribution of real numbers in the cyphertext, in one embodiment the total length of all intervals associated with a given unique-character, relative to the length of the real number range L, should be substantially equal to the relative frequency with which that letter occurs in the cyphertext. In the embodiment of FIG. 3, the total length of all intervals to which a character is mapped is roughly proportional to the relative frequency of that character in the plaintext. Accordingly, the relative frequency of a character is determined by dividing the actual number of occurrences of a given character by the actual number of occurrences of the least frequent character 314. Table III provides an illustration of performing this calculation with respect to the plaintext of Table I. For example, since the plaintext of Table I contains two "D's" (which is the least frequent character), its relative frequency P.sub.D is 1.0. Since the plaintext of Table I contains 14 A's, the relative frequency of A's is P.sub.A =14/2=7.0 and so forth. The total of all the frequencies, as shown in Table III is 22 and (for purposes described below) one greater than this number (i.e. 23, in the example of Table III) is assigned to the symbol "t" 316.
TABLE III
NO. OF RELATIVE
CHARACTERS FREQUENCY P.sub.K P.sub.K /t
Total 44
Characters
A's 14 7.0 0.309
B's 9 4.5 0.195
C's 19 9.5 0.413
D's 2 1.0 0.043
Total 22
The number of potential interval endpoints selected within the real number range 516, in the example of Table III, is twice the integer portion of t (i.e. 46 in the present example 318). This will define a "pool" of real numbers as potential interval endpoints from which selections will be made during the mapping step as described below. When it is desired to insert "red herring" real numbers in the cyphertext (to give the appearance of a random distribution of numbers, as described above), selecting twice the integer value of t (rather than the integer value of t) provides a partition of the real number range 516 which will have about twice as many intervals as will be used for the mapping, thus assuring that about 50% of the intervals in the range 516 will represent unmapped real numbers which can be used for "red herring" numbers. As will be clear to those of skill in the art, the integer portion of t may be multiplied by numbers other than 2 in order to provide any desired proportion of unmapped intervals to mapped intervals within the real number range 516 on average. Other schemes for selecting intervals from a real number range will be apparent to those of skill in the art after understanding the present disclosure. FIG. 5A illustrates an example of a random selection of 46 points (represented by long or short vertical marks) within the real number range 516. As depicted in FIG. 4, after the real number range has been partitioned, each of the unique characters in the cyphertext (in this example, "A", "B", "C", "D") are mapped to intervals. Although it is possible to map the characters in a particular order, such as alphabetical order, letter frequency order or the like, in the embodiment of FIG. 4, the characters are mapped in random order. Thus, the first step is selecting one of the unique characters (which has not already been mapped) for mapping 412. For purposes of illustration, the selected character will be called the j.sup.th character. With reference to the illustration of Table I, in one example the randomly selected character may be "B". A counter variable N.sub.B is initialized to zero 414 and then incremented 416. One of the previously-determined 46 real numbers from the "pool" 318 (other than the highest number in the pool) is randomly selected and this is assigned 418 to the selected letter j.sup.th unique character (in this case "B") to act as the lower bound of one of the intervals. In the example of FIG. 5A, the randomly selected interval lower bound is 517 is 0.6437. The letter B is thus mapped to an interval .sup.M.sub.1.sub..sub.B whose lower bound is the randomly-selected point 517 and whose upper bound is another randomly selected point in the pool which is higher than the first randomly selected point, 518, in this example equal to 0.6988, to provide an interval .sup.M.sub.1.sub..sub.B having a length .sup.L.sub.1.sub..sub.B in this case equal to 0.0551. The end points for intervals selected in step 422 are illustrated, in FIG. 5A, by long vertical lines. The total accumulated length for the mapping of "B" characters is thus, at this point, equal to 0.0551 (since only a singular interval has thus far been mapped 424). This value is divided by the value of H (which in this case is equal to 0.47225, as noted above). The result, which is equal to, at this iteration of the present example, 0.1167 is compared to the ratio of P.sub.B /t (see Table III) 426. The comparison indicates that the total interval accumulated, thus far, for "B" characters is not yet equal to the relative probability of occurrence of "B" characters in the plaintext and thus the system loops 428 to repeat the procedure for mapping "B" to an additional interval 524, having a length .sup.L.sub.2.sub..sub.B (see Table II). After this iteration, (.sup.L.sub.1.sub..sub.B +.sup.L.sub.2.sub..sub.B )/H is still less than (P.sub.B)/t so the system once again returns 428 to map B 526 to yet a third interval. If it is assumed that this third interval to which B is mapped 526 has a length 528 of 0.535, than the value of (.sup.L.sub.1.sub..sub.B +.sup.L.sub.2.sub..sub.B +.sup.L.sub.3.sub..sub.B )/H is now 0.132 and thus exceeds P.sub.B /t 426. Thus, at this point in the procedure, the unique character "B" has been mapped to three intervals 522, 524, 526. As noted above, it is preferred that the length of the intervals, for each unique character (as a proportion of the length of all intervals for all characters), should be at least roughly proportional to the frequency of occurrence of that character in the plain text (e.g. in order to disguise such characteristics as letter frequency). In addition, in some embodiments, the number of intervals for each unique character (as a proportion of the total number of intervals mapped) should be roughly proportional to the frequency of occurrence of that character in the plaintext (in order to make it difficult to discern the intervals). However, there will always be an integral number of mappings while the relative frequency of a character in the plaintext will typically be non-integral. Thus, the number of mappings for a character will typically be the next larger or next smaller integer compared to the non-integral ratio. If it is desired to disguise mapped intervals from non-mapped intervals, it would be useful for the number of mappings for each unique character to be randomly selected between the next greater integer and the next smaller integer (compared to the character-frequency ratio). However, step 426 is constructed so that the loop 428 is not escaped until the number of mappings has reached the next-larger integer. Accordingly, in the embodiment of FIG. 4, after the loop 428 has been escaped 432, the procedure will randomly choose whether to unmap the most recent mapping (in this case, indicated by a phantom arrow 526 in FIG. 5A) and to return the bounds of the most-recently-mapped interval to the pool 434 (provided the mapping which is to be unmapped is not the only mapping for the character 433). In the present example, it is assumed that the random choice 432 results in removal of the most recent mapping for "B" 526 resulting in only two remaining mappings for "B", resulting in mappings: B.fwdarw..sup.M.sub.1.sub..sub.B , B.fwdarw..sup.M.sub.2.sub..sub.B as depicted in Table II. Unless all characters in the character set have been mapped 432 (causing a termination of the mapping procedure 436), the system loops back 448 to select the next character in the character set for a mapping procedure. FIG. 5A illustrates one example of the result of applying the procedure of FIG. 4 to the four-unique-character set of the characters in the plaintext of Table I and the intervals and lengths illustrated in the example of FIG. 5A are shown in Table II. Once the intervals and mappings have been defined, encryption 116 can be performed e.g. using a procedure as shown in FIG. 5B. In the procedure of FIG. 5B, for each character in the plaintext (Table I) one of the intervals to which that character is mapped is randomly selected 512. For example, in the plaintext of Table I, the first character is "B". As noted above, B is mapped to two intervals 522, 524. Thus, the first step 512 is selecting which of these two mappings are to be used for the first "B" in the plaintext. For purposes of illustration, it is assumed that the selected mapping is .sup.M.sub.2.sub..sub.B 524. The lower and upper bounds of this interval are 0.6437 and 0.6988. A real number within the selected interval is then chosen to represent the character of the plaintext 516. For example, the first B of the plaintext might be represented by the number 0.6673. The same procedure 512, 514, 516 is used for selecting a real number to represent each character in the plaintext (Table I). Thus, at this point, the 44 characters of the plaintext in Table I will have been replaced by 44 real numbers lying within the various intervals shown in Table II). However, a would-be code-breaker who examined such a series of real numbers (particularly one which corresponds to a relatively longer plaintext) might discern that all of the real numbers lie in only certain intervals and thus may be able to determine at least the boundaries of the intervals, as part of the process of code-breaking. Accordingly, in the embodiment of FIG. 5B, a number of "red herring" real numbers selected from portions of the real number range 516 which are outside the mapped intervals and are inserted 538 preferably at random locations in the cyphertext, preferably with insertion of "red herring" numbers being interspersed with selection of mapped numbers 534. The red herring numbers may be randomly selected or may be chosen so as to, in combination with the mapped real numbers, provide an appearance of a random distribution of real numbers within the real number range 516. Returning to FIG. 1, following the encryption 116 of FIG. 5B, the resulting cyphertext is communicated 118 over a communication link 216 to a destination computer 214. The mapping and interval information 122 is also communicated to the destination computer 214, as described above. Various systems can be used for communicating the mapping and interval information. In one simple example, the mapping and interval information can consist of each letter of the character set followed by one or more pairs of real numbers representing the upper and lower bounds of the one or more intervals to which that character was mapped. Of course, it would be relatively straightforward for a would-be code-breaker to use such interval/mapping communications to assist in decrypting the cyphertext. Accordingly, various procedures can be used for further protecting the communication of the mapping/interval information. As noted above, the mapping/interval information can be, itself, encrypted. The definition of the intervals can be transmitted separately (at different time or using a different communication channel) from the information regarding mapping such as using a prior day's transmission as a key for a current day's transmission. For example, a first communication can be used to transmit pairs of real numbers representing upper and lower bounds of intervals (or, for contiguous intervals, all lower bounds, plus the upper bound of the largest interval) and a second communication can be used to transmit a string of characters indicating (e.g. in the same order) which characters are mapped to which intervals. Alternatively, interval definitions can be communicated by sending a center point and width rather than end points. Those that are skilled in the art will understand how to devise other ways of communicating mapping and interval information after understanding the present disclosure. After the cyphertext and mapping/interval information have been communicated to the destination, the destination computer can decrypt the cyphertext to recover the original plaintext. In the procedure of FIG. 5C, the destination computer will receive a series of real numbers as the cyphertext. For each discrete real number, the computer will determine whether that real number lies within one of the intervals to which one of the characters is mapped 542. If the number does not lie within one of the mapped-to intervals 544, it can be assumed that the number was one of the red herring numbers selected from the non-mapped intervals and these numbers can be ignored 546. Otherwise, the real number will be replaced with the character which is mapped to that interval 548. In the example above, the first character of the plaintext of Table I was represented by the real number 0.6673. Thus, during decryption, the destination computer will determine that 0.6673 lies within one of the mapped-to intervals, namely interval .sup.M.sub.2.sub..sub.B . The computer will know that this interval is one of the intervals to which the letter "B" is mapped and accordingly will replace the number 0.6673 with the letter "B" thus recovering the first character of the plaintext of Table I. The description above is generally related to communications between two computers, a source computer and a destination computer as illustrated in FIG. 2. However, as noted above, there are situations in which it is desirable for other parties to be involved in the communication process, e.g. to communicate such third-party's approval or verification of the transaction or communication. One procedure for involving additional parties can involve dividing the character set into two or more subsets and permitting different parties to define the mappings and/or intervals for the different subsets of characters. Thus (in the example of Table I) a first party might define the intervals and mapping for characters A and B and a second party might define the intervals and mapping for characters C and D. In this way, a receiving party who was able to successfully decrypt the cyphertext could be assured that both of the parties who contributed to the encryption of the plaintext (and had communicated the mapping/interval information to the receiving party) had done so in order to indicate their verification or approval of the communication or transaction. While this procedure may be useful in many situations, in other situations it may be desired to provide for multiple-party contribution to encryption but without all of the contributing parties (or, in some cases, any of the contributing parties) having the ability to decrypt the cyphertext (or, preferably, any portion thereof) using only their own contributions to the encryption process. Thus, when two parties each define intervals and mappings for some of the character set, that party would be able to recover the portion of the plaintext which uses characters for which that party had defined the mapping. Thus, in the example above, the first contributing party, if they intercepted the cyphertext, would be able to recover all of the A's and B's of the plaintext. Accordingly, another procedure, illustrated in FIGS. 6 and 7 can be used to achieve multi-party encryption without contributing-party decryption. In the embodiment of FIG. 6, initial steps of selecting intervals 612, selecting mappings 614 and performing a first stage of encryption 616 can be performed in a fashion similar to that described above for corresponding steps 112, 114, 116 of FIG. 1. Alternatively, the selection of intervals and mapping can be shared among two or more parties, as described above. As described above in connection with FIG. 1, the result of the first stage of encryption 616 will be a series of real numbers. The mapping of letters ABCD to intervals is illustrated in FIG. 7, by arrows 712. As is well known to those of skill in the art, there are numerous mathematical functions which can be used to transform one set of real numbers into another set of real numbers. Moreover, functions are known which can be multiplied such that a second function can be applied to the real number set resulting from a first function, in order to yield a third real number set. For purposes of at least some embodiments of the present invention, the transformation function(s) that may be used should be configured such that one or more reverse functions or inverse functions are available (or can be derived) so as to permit unambiguous recovery of the original set of real numbers. Finally, for at least some embodiments the functions should operate so that, at least for the various real numbers sets, and preferably for all real numbers in the mapped intervals, and even more preferably for all real numbers in the real number region, a transformation function will never result in two different real numbers being transformed to the same real number. Conveniently, this can be assured by using transformation functions which are continuous and monotonic in the mapped intervals (preferably in the selected real number range). As will be understood by those of skill in the art, for any selected real number range, there are numerous polynomial equations that are continuous and monotonic in such range. Other suitable transformation functions can be selected as will be understood by those of skill in the art after understanding the present disclosure. FIG. 7 illustrates intervals position on a portioned of the X axis of a Cartesian coordinate system with a graph of a suitable cubic equation Y=(X-A).sup.3 +B. The illustrated cubic equation is continuous and monotonic increasing in the illustrated interval. As shown in FIG. 7, endpoints of each selected interval can be transformed to endpoints of a corresponding "Y" interval by application of the cubic equation to define a series of corresponding intervals 714 on the Y axis. If desired, the interval 714 resulting from the first transformation function 713 can be further transformed by another function which is preferably continuous and monotonic over the length 716 of the Y-axis intervals to provide yet another series of intervals (not shown) and so forth. In one embodiment, each of one or more verifying parties can define a transformation function for use in the procedure of FIG. 6. As illustrated in FIG. 6, a first transformation function 618 (devised by a first verification party) is applied to the set of real numbers output by the first state encryption 616 to yield a second set of real numbers, to which a second transformation function 622 (devised by a second verification party 234) is applied in order to arrive at the cyphertext which is communicated 624 e.g. over communication link 216 to the destination computer 214. Although it would be possible for the source computer 212 to send the first stage-encrypted text to the first verifying party 232 for transformation by the first verifying party 232 and for transmission on to the second verifying party 234 for the performance of the second transmission and, thence, transmission to the destination computer 216, FIG. 2 illustrates a somewhat different procedure. In the procedure of FIG. 2, each of the first and second verification party computers 232, 234 sends the information defining the transformation functions (e.g. such as the parameters of a cubic equation in the example of function 713) to the source computer 212 via communication links 3 and 4236, 238. The source computer 212 then sends the cyphertext 624 via the first communication link 216 and the mapping and interval information 630 by a second communication link 218. The first verifying party 232 sends the first transformation information 626 by a fifth communication link 242 to the destination computer 214 and the second verifying party sends the second transformation information 628 by a sixth communication link 244 to the destination computer 214. If desired, the verifying parties, rather than sending the values of the transformation functions (which were sent to the source computer 212) can send inverse function information. This procedure can be useful when the transformed functions have different levels of difficulty of operation and inverse operation. The destination computer 214 performs second and first inverse transform operations 632, 634 (using inverse transform information communicated from the verifying parties or calculated from the transform information sent from the verifying parties). Many real number functions are commutative so that the reverse inverse transformations can be performed in either order. Many real number functions can be multiplied so that, as an alternative, the inverse functions can be multiplied to form a single composite inverse fiction which is then applied 636 to the cyphertext. The resulting "original" set of real numbers can then be decrypted 638a, b, e.g. using procedures similar to that described above in connection with FIG. 5C. Accordingly, although the destination party can be assured that the first and second verification parties 232, 234 contributed to the encryption process, to indicate their authorization or verification, neither of the verifying parties 232, 234 is able, using only their transformation function contribution, to recover the plaintext. FIG. 7 depicts an embodiment in which the second transformation function is a continuous monotonic function. However, it is also possible to provide a workable encryption system in which the second function is discontinuous and/or non-monotonic. For example, as illustrated in FIG. 8, the second function can be a step function (i.e. a function in which each of a plurality of intervals in the range may map to a single value in the domain) 812a through 812g. As can be seen from FIG. 8, in this embodiment, the function is not necessarily monotonic nor continuous. As illustrated in the example depicted in FIG. 8, there may be two or more intervals (e.g. 812a,e) which map onto the same domain value. Although, in decrypting the cyphertext, there may be ambiguity which arises from the non-monotonic nature of the second transformation function, if the characters of the document, as they are encrypted, are kept in order, it becomes feasible to decrypt the cyphertext (because the cyphertext retains not only the numbering or functional relationship between the cyphertext and the plain text but also the relative position information). In light of the above description, a number of advantages of the present invention can be seen. The present invention allows encryption of a plaintext in such a manner that different instances (preferably all different instances) of the same character within the plaintext are represented by different cyphertext components, such as different real numbers. Nevertheless, a single decryption procedure applied to such different numbers correctly decrypts the different numbers to the same plaintext character. In this way, information that might be of use to a code-breaker, such as letter frequency information, word size information and the like, can be reduced or eliminated from the cyphertext. Preferably, the cyphertext appears to be a series of numbers randomly distributed over a range of real numbers. By avoiding a one-to-one system of encryption, the disadvantages associated with such encryption systems are avoided. The present invention allows the participation of two or more parties in the encryption process e.g. for purposes of indicating verification or approval of various parties to the communication or transaction. In some embodiments of invention, such participation of multiple parties can be achieved without providing such verifying parties with the ability to recover all, or preferably any portion of, the plaintext from the cyphertext, using only that party's contribution to the encryption process. A number of variations and modifications can be used. It is possible to use some aspects of the invention without using others. For example, it is possible to use the described one-to-many "encryption" without using transformation functions or other multi-party participation processes. It is possible to use multiple transformation functions or other multiple party encryption procedures without using the described mapping of characters to intervals. Many of the steps in the procedures described herein can be performed in an order different from that illustrated. For example, with regard to the procedure of FIG. 6, rather than performing the encryption first stage and then applying the transforms 618622 to the resultant set of real numbers, the transform 618612 can be applied to the interval boundaries before characters of plaintext are mapped to real numbers within the intervals. Although one example was provided illustrating two different parties defining the intervals and mappings for two different portions of the character set, it is also possible for one party to define the interval bounds and another party to define the mapping (for all or some portion of the character set). The above-described one-to-many mapping can result in a cyphertext which includes a series of real numbers if desired, the real numbers in the cyphertext can be concatinated and, if the numbers have a known or a determinable number of digits or bits, can be transmitted simply as a stream of such digits or bits, with the decryption party having the ability to break the stream into real numbers having the known number of bits or digits. In some embodiments, it may be desirable to translate real numbers from one number system to another such as decimal to octal, hexadecimal, binary and the like either before or after any given stage of the encryption. If number system changes are performed, rounding errors that may occur during number system transformations should be accounted for, e.g. using techniques that will be understood by those of skill in the art after understanding the present disclosure. As described above, the intervals and mappings can be selected such that the resultant series of real numbers appears to be randomly distributed over an interval of the number line. Typically, applications of one or more transformation functions will distort the apparent random distribution so that the resultant cyphertext may no longer appear to be a randomly distributed series of real numbers. However, the distortion that results is dependent on the nature of the transformation functions and is independent of the plaintext. Accordingly, even if the final cyphertext contains numbers that do not appear to be randomly distributed, the departure from randomness will not contain information about the letter frequency or similar characteristics of the plaintext. However, if it is known that the "original" series of random numbers (on which the transformation function(s) operated) was random, the nature of the departures from randomness might be useful in determining the transformation functions. If this is a concern, in one embodiment the original intervals and mapping may be selected (or extra-interval "red herring" numbers may be inserted) so that the "original" series of random numbers is not apparently randomly distributed. Thus any departures from randomness in the transformed real number series will be of little use in determining the nature of the transformations. EXAMPLE The following provides one example of a use of the procedure as described herein. The example involves a source "branch" bank, the source's "parent" bank, a destination bank, and a verifying federal reserve bank. The source branch bank initiates communication with its parent by defining a set of intervals for a character set. In this example, the character set is chiefly numbers and includes 15 characters (including decimal point, minus sign, currency symbol, space and the like). Five intervals are assigned to each character. The intervals in this example are contiguous. Accordingly, the intervals can be communicated by transmitting a set of 76 numbers, in this case, double precision numbers. This can be communicated using a total of 608 bytes. In one embodiment, the branch bank and its parent bank establish such a set of intervals on a periodic basis, such as hourly. The source branch calls its parent bank which assigns a unique transaction identification number to the source bank's transaction. The source bank then calls the destination bank to obtain an authentication code. This code consists of the coefficients of a simple polynomial such as a cubic polynomial. The polynomial is chosen to be monotone increasing over the range of intervals defined in the first step. The coefficients of the cubic polynomial can be transmitted using four double precision numbers or 32 bytes. The source bank then contacts the verifying Federal Reserve Bank and obtains another set of authentication codes (corresponding to coefficients of a polynomial which is monotone over the range of intervals), thus obtaining another 32 bytes. The source (branch) bank then encrypts the document which it wishes to transmit using the 3 pieces of authentication data: the interval/mapping information, the first polynomial coefficients and the second polynomial coefficients. The encrypted document is then sent to the destination bank as cyphertext, along with the transaction identification number in plaintext. The destination bank calls each of the parent bank and the Federal Reserve Bank and provides them with the transaction identification number and their own bank identification number. In response, the parent bank and the Federal Reserve Bank transmit to the destination bank, the respective authentication/encryption information. Using this information, the destination bank decrypts the transmission and is thus assured that the transmission has been authorized by both the parent bank and the Federal Reserve Bank. The present invention, in various embodiments, includes components, methods, processes, systems and/or apparatus substantially as depicted and described herein, including various embodiments, subcombinations, and subsets thereof. Those of skill in the art will understand how to make and use the present invention after understanding the present disclosure. The present invention, in various embodiments, includes providing devices and processes in the absence of items not depicted and/or described herein or in various embodiments hereof, including in the absence of such items as may have been used in previous devices or processes, e.g. for improving performance, achieving ease and.backslash.or reducing cost of implementation. The foregoing discussion of the invention has been presented for purposes of illustration and description. The foregoing is not intended to limit the invention to the form or forms disclosed herein. Although the description of the invention has included description of one or more embodiments and certain variations and modifications, other variations and modifications are within the scope of the invention, e.g. as may be within the skill and knowledge of those in the art, after understanding the present disclosure. It is intended to obtain rights which include alternative embodiments to the extent permitted, including alternate, interchangeable and/or equivalent structures, functions, ranges or steps to those claimed, whether or not such alternate, interchangable and/or equivalent structures , functions, ranges or steps are disclosed herein, and without intending to publicly dedicate any patentable subject matter.
|
Same subclass Same class Consider this |
||||||||||