Secure data encoder and decoder

• US 6,275,587 B1
• Filed: 06/30/1998
• Issued: 08/14/2001
• Est. Priority Date: 06/30/1998
• Status: Expired due to Term

• Current Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Amerige, Stephen Kelley
• Primary Examiner(s): Peeso, Thomas R.
• Assistant Examiner(s): JACK, TODD M
• Application Number:
  US09/108,090
• Time in Patent Office: 1,141 Days
• Field of Search: 380/28, 380/36, 380/37, 380/255
• US Class Current: 380/255
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/00 Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
• CPC Class Codes: H04L 9/065 Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3
• CPC Class Codes: H04L 9/34 Bits, or blocks of bits, of the telegraphic message being interchanged in time for speech signals H04K1/06

Abstract

A computer system includes a processor and a computer readable medium storing a computer program product for encoding a serial bit stream of digital data. The product includes instructions for causing the processor to place a first number of bits from the input bit stream into bit positions of an encoded output unit in accordance with a first value, the first number of bits aligned to a bit position in the encoded output unit in accordance with a second value and insert bits of arbitrary value into remaining, bit positions of the unit of the encoded output unit. In addition, the computer program product includes instructions that cause a processor to select significant bits from a unit of the encoded bit stream in accordance with the first value and the second value to place the selected bits in a decoded bit stream.

Claims

1. A method of encoding a serial bit stream of digital data, the method comprises:

placing a first portion of bits from the input bit stream into bit positions of an encoded output unit in accordance with a first value, said first number of bits aligned to a bit position in the encoded output unit in accordance with a second value and inserting bits of arbitrary value into remaining bit positions of the unit of the encoded output unit;

placing a remaining portion of bits from the input bit stream into bit positions of a second encoded output unit in accordance with a different, first value, said remaining portion of bits aligned to a bit position in the second encoded output unit in accordance with a different, second value and inserting bits of arbitrary value into remaining bit positions of the second unit of the encoded output unit; and

wherein the bits of arbitrary value are noise bits.

2. A method of encoding a serial bit stream of digital data, the method comprises:

placing a first portion of bits from the input bit stream into bit positions of an encoded output unit in accordance with a first value, said first number of bits aligned to a bit position in the encoded output unit in accordance with a second value and inserting bits of arbitrary value into remaining bit positions of the unit of the encoded output unit;

placing a remaining portion of bits from the input bit stream into bit positions of a second encoded output unit in accordance with a different, first value, said remaining portion of bits aligned to a bit position in the second encoded output unit in accordance with a different, second value and inserting bits of arbitrary value into remaining bit positions of the second unit of the encoded output unit; and

iteratively generating subsequent first values and subsequent second values for the actions of placing, and for each subsequent action of placing, placing a variable number of bits, as determined by the subsequent first values from the input bit stream into subsequent encoded output units.

3. The method of claim 2 wherein generating the first value and the second value uses a deterministic non-trivial algorithm to select the first value and second value.

4. The method of claim 3 wherein the deterministic non-trivial algorithm comprises

determining pairs of generated values from a first prime number and a second prime number, where the first prime number is a primitive root of the second prime number.

5. The method of claim 4 wherein pairs of generated values based on the first and second prime numbers are used to determine the first and second values.

6. The method of claim 2 wherein the unit of encoded data is a byte, word, long word or quad word.

7. The method of claim 2 wherein the unit of data is a byte.

8. The method of claim 2 wherein placing further comprises modifying the selected input bits in the encoded bit stream in accordance with whether a third value corresponds to a logic 0 or a logic 1.

9. The method of claim 2 further comprising supplying the encoded bit stream with a header that identifies values of the two prime numbers to produce the generated values.

10. The method of claim 9 wherein the header is encrypted.

11. The method of claim 5 wherein the values of the two prime numbers to produce the generated values are in a software application that uses the encoding method.

12. The method of claim 5 wherein values of the two prime numbers to produce the generated values are user supplied.

13. The method of claim 2 wherein placing further comprises applying a transformation to the selected bits and noise.

14. The method of claim 2 wherein the first value is defined as b(k) and the second value is defined as r(k) and are given by:

15. The method of claim 2 wherein the first value is defined as b(k) and the second value is defined as r(k) and are given by:

16. The method of claim 2 wherein placing bits into the encoded output unit further comprises inverting a unit of the encoded bit stream in accordance with whether a third value corresponds to a logic 0 or a logic 1.

17. A method of decoding an encoded serial bit stream, the method comprising:

selecting significant bits from a unit of the encoded bit stream in accordance with a number of bits value and a bit alignment value to place the selected bits in a decoded bit streams;

gathering values of two prime numbers to produce generated values;

generating the generated values based on the gathered values of the two prime numbers; and

producing the number of bits value and the bit alignment value from the generated values.

18. The method of claim 17 further comprising iteratively repeating the generating, producing and selecting actions until all bits of the encoded bit stream have been placed in the decoded bit stream.

19. The method of claim 17 wherein the encoded unit is a byte, word, long word or quad word.

20. The method of claim 17 wherein the encoded unit is a byte.

21. The method of claim 20 wherein generating provides said generated values in accordance with a primitive root algorithm.

22. The method of claim 17 wherein selecting identifies the number of bits in the encoded bit stream and the bit position in the encoded bit stream.

23. The method of claim 20 further comprising:

gathering a third value and wherein said third value determines a filter function to apply to the selected bits.

24. The method of claim 23 wherein said third value determines whether or not the selected bits in the encoded bit stream unit are inverted to provided the decoded bit stream.

25. The method of claim 20 wherein gathering further comprises decrypting values to find the two prime numbers.

26. The method of claim 20 wherein gathering further comprises retrieving the values of the two prime numbers from an application program.

27. The method of claim 20 wherein gathering further comprises retrieving user supplied values of the two prime numbers.

28. The method of claim 20 wherein gathering further comprises retrieving the values of the two prime numbers from a header that accompanies the encoded bit stream.

29. A computer program product residing on a computer readable medium for encoding a serial bit stream of digital data, the product comprising instructions for causing a processor to:

place a first portion of bits from the input bit stream into bit positions of an encoded output unit in accordance with a first value, said first number of bits aligned to a bit position in the encoded output unit in accordance with a second value and insert bits of arbitrary value into remaining, bit positions of the unit of the encoded output unit; and

place a remaining portion of bits from the input bit stream into bit positions of a second encoded output unit in accordance with a different, first value, said remaining portion of bits aligned to a bit position in the second encoded output unit in accordance with a different, second value and insert bits of arbitrary value into remaining bit positions of the second unit of the encoded output unit; and

iteratively generate subsequent first values and subsequent second values to place a variable number of bits determined by the subsequent first values from the input bit stream into subsequent encoded output units.

30. The computer program product of claim 29 wherein instructions that cause the processor to generate the first value and the second value use a deterministic non-trivial algorithm to select the first value and second value.

31. The computer program product of claim 30 wherein the deterministic non-trivial algorithm comprises instructions that cause the processor to

determine pairs of generated values from a first prime number and a second prime number, where the first prime number is a primitive root of the second prime number.

32. The computer program product of claim 31 wherein pairs of generated values based on the first and second prime numbers are used to determine the first and second values.

33. The computer program product of claim 29 wherein the unit of encoded data is a byte, word, long word or quad word.

34. The computer program product of claim 29 wherein the unit of data is a byte.

35. The computer program product of claim 29 wherein instructions that cause the processor to place further comprise instructions that cause the processor to modify the selected input bits in the encoded bit stream in accordance with whether a third value corresponds to a logic 0 or a logic 1.

36. The computer program product of claim 31 further comprising a header that identifies values of the two prime numbers to produce the generated values.

37. The computer program product of claim 36 wherein the header is encrypted.

38. The computer program product of claim 31 wherein the values of the two prime numbers to produce the generated values are in a software application that uses the encoding computer program product.

39. The computer program product of claim 31 wherein values of the two prime numbers to produce the generated values are user supplied.

40. The computer program product of claim 29 wherein instructions that cause the processor to place bits further comprise instructions that cause the processor to apply a transformation to the selected bits and noise.

41. The computer program product of claim 29 wherein the first value is defined as b(k) and the second value is defined as r(k) and are given by:

42. The computer program product of claim 29 wherein the first value is defined as b(k) and the second value is defined as r(k) and are given by:

43. A computer program product residing on a computer readable medium for decoding an encoded serial bit stream, the computer program product comprising instructions that cause a processor to:

select significant bits from a unit of the encoded bit stream in accordance with a number of bits value and a bit alignment value to place the selected bits in a decoded bit stream;

gather values of two prime numbers to produce generated values;

generate the generated values based on the gathered values of the two prime numbers; and

produce the number of bits value and the bit alignment value from the generated values.

44. The computer program product of claim 43 further comprising instructions that cause a processor to:

iteratively repeat the generate, produce and select instructions until all bits of the encoded bit stream have been placed in the decoded bit stream.

45. The computer program product of claim 43 wherein the encoded unit is a byte, word, long word or quad word.

46. The computer program product of claim 43 wherein the encoded unit is a byte.

47. The computer program product of claim 43 wherein instructions that cause a processor to generate generated values provides said generated values in accordance with a primitive root algorithm.

48. The computer program product of claim 47 wherein instructions that cause a processor to select significant bits further comprises instructions that cause the processor to identify the number of bits in the encoded bit stream and the bit position in the encoded bit stream.

49. The computer program product of claim 43 further comprising instructions that cause a processor to gather a third value and wherein said third value determines a filter function to apply to the selected bits.

50. The computer program product of claim 49 wherein said third value determines whether or not the selected bits in the encoded bit stream unit are inverted to provided the decoded bit stream.

51. The computer program product of claim 43 wherein instructions that cause a processor to gather further comprises instructions that cause a processor to de-encrypt values to find the two prime numbers.

52. The computer program product of claim 43 wherein instructions that cause a processor to gather further comprises instructions that cause a processor to retrieve the values of the two prime numbers from an application program.

53. The computer program product of claim 43 wherein instructions that cause a processor to gather further comprises instructions that cause a processor to retrieve user supplied values of the two prime numbers.

54. The computer program product of claim 43 wherein instructions that cause a processor to gather further comprise instructions that cause a processor to retrieve the values of the two prime numbers from a header that accompanies the encoded bit stream.