Cryptosystem for data security

• US 20040223608A1
• Filed: 03/24/2004
• Published: 11/11/2004
• Est. Priority Date: 09/25/2001
• Status: Active Grant

• Current Assignee: Stealth Encoder Inc.
• Original Assignee: Compusoft ASA
• Inventors: Rueda, Luis G., Oommen, B. John
• Granted Patent: US 7,508,935 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: H04L 9/0656 Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure

Abstract

A method and device for creating ciphertext from plaintext, and for decoding ciphertext, utilizing a tree structure for both encoding and decoding, the tree having leaves which are associated with plaintext symbols and the branches having assigned thereto a member of the ciphertext alphabet so that when encoding, a traversal is made between the root and the leaf corresponding to the plaintext and recording the ciphertext associated with each branch traversed, and when decoding, using the ciphertext to determine the branches to be traversed until a leaf is reached and recording the plaintext associated with that leaf.

Claims

1. A method for creating ciphertext from plaintext comprising the steps of:

(a) receiving a character of plaintext;

(b) traversing an Oommen-Rueda Tree between the root and that leaf corresponding to that character of plaintext and recording the Assignment Value of each branch so traversed;

(c) receiving a next character of plaintext; and

(d) repeating steps b and c until the plaintext has been processed.

6. A method for creating ciphertext from plaintext according to claims 1, 2, 3, 4 or 5, wherein the Assignment Value for at least one branch traversed is determined in accordance with a Branch Assignment Rule.

7. A method for creating ciphertext from plaintext according to claim 6 wherein when a member of the ciphertext alphabet is under-represented in the ciphertext generated thus far, the Branch Assignment Rule assigns that member of the ciphertext alphabet to at least one of the branches being traversed between the root and the leaf so that that member of the ciphertext alphabet is no longer as under-represented as before the assignment.

8. A method for creating ciphertext from plaintext according to claim 6 wherein when a member of the ciphertext alphabet is under-represented in the ciphertext generated thus far, the Branch Assignment Rule assigns that member of the ciphertext alphabet more frequently than other members of the ciphertext alphabet to the branches being traversed between the root and the leaf so that that member of the ciphertext alphabet is no longer as under-represented as before the assignment.

9. A method for creating ciphertext from plaintext according to claim 6 wherein when the ciphertext alphabet is binary, the Branch Assignment Rule assigns a zero to the majority of branches being traversed between the root and the leaf when zero is under-represented in the ciphertext generated thus far, and assigns a one to the majority of branches being traversed between the root and the leaf when one is under-represented in the ciphertext generated thus far.

10. A method for creating ciphertext from plaintext according to claim 6 wherein, when the conditional frequency of one member of the ciphertext alphabet given a particular sequence of members of the ciphertext alphabet in the ciphertext generated thus far, is under-represented in the ciphertext generated thus far, the Branch Assignment Rule assigns that member of the ciphertext alphabet to at least one of the branches being traversed between the root and the leaf so that the said conditional frequency of that member of the ciphertext alphabet is no longer as under-represented as before the assignment.

11. A method for creating ciphertext from plaintext according to claim 6 wherein, when the conditional frequency of one member of the ciphertext alphabet given a particular sequence of members of the ciphertext alphabet in the ciphertext generated thus far, is under-represented in the ciphertext generated thus far, the Branch Assignment Rule assigns that member of the ciphertext alphabet more frequently than other members of the ciphertext alphabet to the branches being traversed between the root and the leaf so that the said conditional frequency of that member of the ciphertext alphabet is no longer as under-represented as before the assignment.

12. A method for creating ciphertext from plaintext according to claim 6 wherein the Branch Assignment Rule assigns a member of the ciphertext alphabet to at least one of the branches being traversed between the root and the leaf, such assignment being determined by comparing a number associated with the frequency of at least one member of the ciphertext alphabet in the ciphertext generated thus far, with a number associated with the output of a pseudo-random number generator.

13. A method for creating ciphertext from plaintext according to claim 6 wherein when the ciphertext alphabet is binary, the Branch Assignment Rule assigns a member of the binary alphabet to at least one of the branches being traversed between the root and the leaf, such assignment being determined by comparing a number associated with the frequency of a member of the binary alphabet in the ciphertext generated thus far, with a number associated with the output of a pseudo-random number generator.

14. A method for creating ciphertext from plaintext according to claim 6 wherein the Branch Assignment Rule assigns a member of the ciphertext alphabet to at least one branch being traversed between the root and the leaf, such assignment being determined by a number associated with the output of a pseudo-random number generator.

15. A method for creating ciphertext from plaintext according to claim 6 wherein when the ciphertext alphabet is binary, the Branch Assignment Rule assigns a member of the binary alphabet to at least one branch being traversed between the root and the leaf, such assignment being determined by comparing a number associated with the a pseudo-random number with a range equal to half the domain of the generator generating the pseudo-random number.

16. A method for creating ciphertext from plaintext according to claim 6 wherein the Branch Assignment Rule assigns a member of the ciphertext alphabet of cardinality R to at least one branch being traversed between the root and the leaf, such assignment being determined by invoking at least two times (R minus 1) pseudo-random numbers, the domains of at least one of the pseudo-random numbers being related to the frequencies of the occurrences of the ciphertext characters generated thus far, and the domain of at least one of the other of the pseudo-random numbers having a mean of i/R for the ith branch of each node encountered in the traversal, where i is the relative position of the branch quantified by a pre-specified ordering of the branches, and the Branch Assignment Rule being such that where the ciphertext character associated with the ith branch in the said ordering is under-represented in the ciphertext generated thus far, it is no longer as under-represented.

17. A method for creating ciphertext from plaintext according to claim 6 wherein when the ciphertext alphabet is binary;

the Branch Assignment Rule assigns a member of the binary ciphertext alphabet to at least one branch being traversed between the root and the leaf, such assignment being determined by invoking at least two pseudo-random numbers, the domain of the first of these pseudo-random numbers being related to the frequency of the occurrence of zero in the ciphertext, and the domain of a second of these pseudo-random numbers having a mean of 0.5, and the Branch Assignment Rule being such that when any character of the ciphertext alphabet is under-represented in the ciphertext generated thus far, it is no longer as under-represented.

18. A method for creating ciphertext from plaintext according to claim 6 wherein when the ciphertext alphabet is binary, the Branch Assignment Rule assigns a member of the binary ciphertext alphabet to at least one branch being traversed between the root and the leaf, such assignment being determined by comparing at least the output of two invoked pseudo-random numbers, the first of which has a domain having a mean between a number associated with the frequency of zeros and the quantity 0.5, and the second of which is a pseudo-random number having a domain whose mean is 0.5, and the Branch Assignment Rule being such that where any member of the ciphertext alphabet is under-represented in the binary ciphertext generated thus far, it is no longer as under-represented.

19. A method for creating ciphertext from plaintext according to claim 6 wherein when the ciphertext alphabet is binary, the Branch Assignment Rule assigns a member of the binary alphabet to at least one branch being traversed between the root and the leaf by utilizing at least two pseudo-random numbers, zero being assigned when a first pseudo-random number is less than a second pseudo-random number, where the generation of the second pseudo-random number is bounded between a number associated with the frequency of zeros in the ciphertext generated thus far and the quantity of one minus the said number associated with the frequency of zeros in the ciphertext generated thus far.

20. A method for creating ciphertext from plaintext according to claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 or 19 comprising the further steps of, after at least one traversal of the Oommen-Rueda Tree, recalculating a number associated with the frequency weight of at least one of the nodes of the Oommen-Rueda Tee including the internal nodes and the leaves depending therefrom, and thereafter restructuring the Oommen-Rueda Tree in accordance with a Tee Restructuring Rule.

21. A method for creating ciphertext from plaintext according to claims 12, 13, 14, 15, 16, 17, 18, 19 or 20, comprising the further step of receiving first key data associated with an initial seed for at least one of the generators of the pseudo-random numbers utilized by the Branch Assignment Rule.

22. A method for creating ciphertext from plaintext according to claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 or 21, comprising the further step of receiving second key data associated with the structure and labeling of the Oommen-Rueda Tree.

23. A method for creating ciphertext from plaintext according to claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 or 22, wherein the plaintext is modified prior to processing by the addition of a pre-specified prefix data stream.

24. A method for creating ciphertext from plaintext according to claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22 or 23;

wherein at least one of the steps is preformed by a suitably programmed processor.

25. A method for creating ciphertext from plaintext according to claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22 or 23, wherein at least one of the steps is a process executed in software.

26. A method for creating ciphertext from plaintext according to claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22 or 23, wherein at least one of the steps is a process executed in firmware.

30. A method for decoding ciphertext according to claims 27, 28 or 29, wherein when the Encoder has utilized a Tree Restructuring Rule according to claim 20, after at least one traversal of the Oommen-Rueda Dee to a leaf, recalculating a number associated with the frequency weight of at least one of the nodes of the Oommen-Rueda Tree including the nodes and the leaves depending therefrom, the Oommen-Rueda Tree thereafter being structured in accordance with the same Tree Restructuring Rule utilized by the Encoder.

41. A secure communication method comprising the steps of:

(a) encoding the communication in accordance with a method described in claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 or 26 herein;

(b) transmitting the encoded communication;

(c) receiving the encoded communication;

(d) decoding the encoded communication in accordance with a method described in claims 27, 28, 29, 30, 31, 32, 33, 34, 35 or 36 herein.

42. A secure data storage and retrieval method comprising the steps of:

(a) encoding the data in accordance with a method described in claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 or 26 herein;

(b) storing the encoded data;

(c) retrieving the encoded data;

(d) decoding the encoded data in accordance with a method described in claims 27, 28, 29, 30, 31, 32, 33, 34, 35 or 36 herein.

43. A method of creating ciphertext from plaintext according to claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 or 26, further comprising the step of subsequently encrypting the ciphertext generated in accordance with the process of claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 or 26 by any standard encryption process.

45. A method for embedding a plaintext message into carrier data comprising the steps of converting the plaintext into ciphertext in accordance with claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 or 26, and thereafter steganographically inserting the ciphertext into the carrier data.

47. A method for generating pseudo-random numbers comprising the steps of receiving an arbitrary data stream, and processing the data stream in accordance with the process of claims 12, 13, 14, 15, 16, 17, 18, or 19.

2. A method for creating ciphertext from plaintext comprising the steps of:

(a) creating an Oommen-Rueda Tee;

(b) receiving a character of plaintext;

(c) traversing the Oommen-Rueda Tree between the root and that leaf corresponding to that character of plaintext and recording the Assignment Value of each branch so traversed;

(d) receiving a next character of plaintext; and

(e) repeating steps c and d until the plaintext has been processed.

3. A method for creating ciphertext from plaintext comprising the steps of:

(a) receiving an Oommen-Rueda Tree;

(b) receiving a character of plaintext;

(c) traversing the Oommen-Rueda Tee between the root and that leaf corresponding to that character of plaintext and recording the Assignment Value of each branch so traversed;

(d) receiving a next character of plaintext; and

(e) repeating steps c and d until the plaintext has been processed.

4. A method for creating ciphertext from plaintext comprising the steps of:

(a) creating an Oommen-Rueda Tree, which Oommen-Rueda Tree has leaves associated with the members of the alphabet of the plaintext, each member of the alphabet of the plaintext being associated with at least one leaf, which Oommen-Rueda Tree'"'"'s internal nodes each have at least one branch depending therefrom, which Oommen-Rueda Tree branches have associated therewith an Assignment Value, which Assignment Value is associated with a member of the alphabet of the ciphertext, which Oommen-Rueda Tree'"'"'s nodes each have associated therewith a quantity related to the frequency weight of each of the nodes and leaves dependant therefrom;

(b) receiving a character of plaintext;

(c) traversing the Oommen-Rueda Tee between the root and that leaf corresponding to that character of plaintext and recording the Assignment Value of each branch so traversed;

(d) receiving the next character of plaintext; and

(e) repeating steps c and d until the plaintext has been processed.

5. A method for creating ciphertext from plaintext comprising the steps of:

(a) receiving an Oommen-Rueda Tee, which Oommen-Rueda Tree has leaves associated with the members of the alphabet of the plaintext, each member of the alphabet of the plaintext being associated with at least one leaf, which Oommen-Rueda Tree'"'"'s internal nodes each have at least one branch depending therefrom, which Oommen-Rueda Tree branches have associated therewith an Assignment Value, which Assignment Value is associated with a member of the alphabet of the ciphertext, which Oommen-Rueda Tree'"'"'s nodes each have associated therewith a quantity related to the frequency weight of each of the nodes and leaves dependant therefrom;

(b) receiving a character of plaintext;

(c) traversing the Oommen-Rueda Tree between the root and that leaf corresponding to that character of plaintext and recording the Assignment Value of each branch so traversed;

(d) receiving the next character of plaintext; and

(e) repeating steps c and d until the plaintext has been processed.

27. A method for decoding ciphertext, comprising the steps of:

(a) receiving a first character of ciphertext;

(b) utilizing an Oommen-Rueda Tree having a structure corresponding to the Oommen-Rueda Tree initially utilized by the Encoder and utilizing the same Branch Assignment Rule as utilized by the Encoder to provide the Assignment Values for the branches depending from the root, traversing such Oommen-Rueda Tree from the root towards a leaf, the first character of ciphertext determining the branch to then be traversed;

(c) if a leaf has not been reached, utilizing the same Branch Assignment Rule as utilized by the Encoder to provide Assignment Values for the branches depending from the node that has been reached, receiving the next character of ciphertext, and continuing to traverse the Oommen-Rueda Tree from the node that has been reached towards a leaf, the current symbol of ciphertext determining the branch to then be traversed;

(d) when a leaf is reached, recording the plaintext character associated with the label of the leaf, the root becoming the node that has been reached for the purpose of further processing;

(e) repeating steps c and d until all symbols of ciphertext have been processed.

31. A method for decoding ciphertext according to claims 27, 28, 29 or 30, comprising the further step of receiving first key data associated with the initial seed for at least one of the generators of the pseudo-random numbers utilized by the Branch Assignment Rule, where first key data is associated with the first key data utilized by the Encoder.

32. A method for decoding ciphertext according to claims 27, 28, 29, 30 or 31, comprising the further step of receiving second key data associated with the structure and labeling of the Oommen-Rueda Tree, where second key data is associated with the second key data utilized by the Encoder.

33. A method for decoding ciphertext according to claims 27, 28, 29, 30, 31 or 32 wherein when the plaintext has been modified prior to processing by the addition of a pre-specified prefix data stream, the ciphertext is modified prior to processing by the addition of an encoded pre-specified data stream in a prefix manner, and where this encoded pre-specified data stream is related to the pre-specified data stream utilized by the Encoder.

34. A method for decoding ciphertext according to claims 27, 28, 29, 30, 31, 32 or 33, wherein at least one of the steps is preformed by a suitably programmed processor.

35. A method for decoding ciphertext according to claims 27, 28, 29, 30, 31, 32 or 33, wherein at least one of the steps is a process executed in software.

36. A method for decoding ciphertext according to claims 27, 28, 29, 30, 31, 32 or 33, wherein at least one of the steps is a process executed in firmware.

44. A method of decoding ciphertext according to claims 27, 28, 29, 30, 31, 32, 33, 34, 35 or 36, comprising the further steps of initially decrypting the ciphertext data stream using the standard decryption process associated with the encryption process utilized in claim 43, and thereafter decoding in accordance with the process of claims 27, 28, 29, 30, 31, 32, 33, 34, 35 or 36.

46. A method for extracting a plaintext message from carrier data which carrier data contains embedded ciphertext steganographically inserted into carrier data in accordance with claim 45, comprising the steps of steganographically extracting the ciphertext from the carrier data, and further decoding the ciphertext utilizing a process in accordance with claims 27, 28, 29, 30, 31, 32, 33, 34, 35 or 36.

28. A method for decoding ciphertext, comprising the steps of:

(a) creating an Oommen-Rueda Tee structure corresponding to the Oommen-Rueda Tree initially utilized by the Encoder;

(b) receiving a first character of ciphertext;

(c) utilizing the Oommen-Rueda Tee structure, and utilizing the same Branch Assignment Rule as utilized by the Encoder to provide the Assignment Values for the branches depending from the root, traversing such Oommen-Rueda Tree from the root towards a leaf, the first character of ciphertext determining the branch to then be traversed;

(d) if a leaf has not been reached, utilizing the same Branch Assignment Rule as utilized by the Encoder to provide Assignment Values for the branches depending from the node that has been reached, receiving the next character of ciphertext, and continuing to traverse the Oommen-Rueda Tree from the node that has been reached towards a leaf, the current symbol of ciphertext determining the branch to then be traversed;

(e) when a leaf is reached, recording the plaintext character associated with the label of the leaf, the root becoming the node that has been reached for the purpose of further processing;

(f) repeating steps d and e until all symbols of ciphertext have been processed.

29. A method for decoding ciphertext, comprising the steps of:

(a) receiving data corresponding to the Oommen-Rueda Tree structure initially utilized by the Encoder, to create an Oommen-Rueda Tree having a structure corresponding- to the Oommen-Rueda Tee initially utilized by the Encoder;

(b) receiving a first character of ciphertext;

(c) utilizing the Oommen-Rueda Tree having a structure corresponding to the Oommen-Rueda Tree initially utilized by the Encoder and utilizing the same Branch Assignment Rule as utilized by the Encoder to provide the Assignment Values for the branches depending from the root, traversing such Oommen-Rueda Tree from the root towards a leaf, the first character of ciphertext determining the branch to then be traversed;

(d) if a leaf has not been reached, utilizing the same Branch Assignment Rule as utilized by the Encoder to provide Assignment Values for the branches depending from the node that has been reached, receiving the next character of ciphertext, and continuing to traverse the Oommen-Rueda Tree from the node that has been reached towards a leaf, the current symbol of ciphertext determining the branch to then be traversed;

(e) when a leaf is reached, recording the plaintext character associated with the label of the leaf, the root becoming the node that has been reached for the purpose of further processing;

(f) repeating steps d and e until all symbols of ciphertext have been processed.

37. A device for creating ciphertext from plaintext comprising:

(a) receiving means for receiving a plaintext data stream;

(b) storing means for storing data representative of an Oommen-Rueda Tree;

(c) processing means for processing the plaintext data stream on a character by character basis, and for repeatedly traversing the stored Oommen-Rueda Tree for each character of plaintext to be processed, each such traversal being between the root and that leaf corresponding to that symbol of plaintext then being processed;

(d) recording means for recording the Assignment Values of the branches of the Oommen-Rueda Tree traversed during the processing of the plaintext data stream;

the receiving means, the storing means and the recording means being in communication with the processing means.

38. A device for creating ciphertext from plaintext according to claim 37, further comprising a second storing means in communication with the processing means for storing a Branch Assignment Rule, and wherein the processing means additionally calculates a number associated with the frequency of at least one member of the ciphertext alphabet in the ciphertext generated thus far, and calculates the Assignment Value of at least one branch depending from at least one node reached in processing.

39. A device for decoding ciphertext comprising:

(a) receiving means for receiving a ciphertext data stream;

(b) storing means for storing data representative of the Oommen-Rueda Tree utilized by the Encoder;

(c) processing means for;

1. processing the ciphertext data stream on a character by character basis,

2. repeatedly traversing the stored Oommen-Rueda Tree between the root and leaves of the Oommen-Rueda Tree, the choice of branch to traverse being determined by the comparison of the character of ciphertext then being processed and the Assignment Value of such branch;

3. selecting the next character of ciphertext for processing to determine the next branch to be traversed, until a leaf is reached, whereupon the plaintext character associated with the leaf is recorded, and the processing continues from the root; and

4. repeating the above steps (1), (2) and (3) until all ciphertext to be processed has been processed;

(d) recording means for recording the plaintext associated with each of the leaves reached during processing;

the receiving means, the storing means and the recording means being in communication with the processing means.

40. A device for decoding ciphertext according to claim 39 further comprising a second storing means in communication with the processing means, for storing a Branch Assignment Rule, and wherein the processing means additionally calculates a number associated with the frequency of at least one member of the ciphertext alphabet in the ciphertext processed thus far, and calculates the Assignment Value of at least one branch depending from at least one node reached in processing.