COMBINATIONAL COMBINER CRYPTOGRAPHIC METHOD AND APPARATUS

• US 20100034385A1
• Filed: 12/15/2006
• Published: 02/11/2010
• Est. Priority Date: 12/15/2006
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Noerenberg, John W. II, Gantman, Alexander, Rose, Gregory G., Choi, Jae-Hee
• Granted Patent: US 8,290,162 B2
• Time in Patent Office: Days
• US Class Current: 380/268
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• 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

Abstract

Another feature provides an efficient encryption method that safeguards the security of encrypted symbols. Each plaintext symbol is encrypted by using a separate pseudorandomly selected translation table. Rather than pre-storing every possible permutation of symbols as translation tables, the translation tables may be efficiently generated on-the-fly based on a pseudorandom number arid a symbol shuffling algorithm. A receiving device may similarly generate reverse translation tables on-the-fly to decrypt received encrypted symbols.

Claims

1. A method operational on an encrypting device, comprising:

obtaining a plurality of input symbols;

obtaining a pseudorandomly selected translation table, from a plurality of translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be encrypted; and

translating the input symbols into corresponding output symbols using their corresponding translation table for each of the input symbols to individually encrypt each input symbol.

2. The method of claim 1 wherein obtaining the pseudorandomly selected translation table for each of the input symbols to be encrypted includes

obtaining a pseudorandomly selected first translation table for a first input symbol;

and

obtaining a pseudorandomly selected second translation table for a second input symbol;

and wherein translating the input symbols into corresponding output symbols using their corresponding translation table for each of the input symbols includes

translating the first input symbol into a first output symbol using the first translation table; and

translating the second input symbol into a second output symbol using the second translation table.

3. The method of claim 1 wherein the plurality of input symbols is defined by a set of N symbols, where N is a positive integer and a translation table is a permutation of the N symbols.

4. The method of claim 3 wherein obtaining the pseudorandomly selected translation table for each of the input symbols to be encrypted includes

obtaining a first pseudorandom number for a first input symbol to be encrypted;

and

shuffling the set of N symbols to obtain a different permutation of the set of N symbols and using that permutation as the translation table for the first input symbol.

5. The method of claim 4 wherein the first pseudorandom number is obtained by

generating a pseudorandom number for the first input symbol, where the pseudorandom number is k bits long and k is a positive integer;

determining whether the pseudorandom number is within a maximum number Pmax, where Pmax is the largest multiple of N factorial that is less than a maximum threshold 2^k;

discarding the pseudorandom number if it is greater than the maximum number Pmax;

obtaining different pseudorandom numbers for the first input symbol until an acceptable pseudorandom number is obtained that is less than or equal to the maximum number Pmax; and

dividing the acceptable pseudorandom number modulo N factorial to obtain the first pseudorandom number.

6. The method of claim 4 wherein shuffling the set of N symbols includes

initializing a permutation vector P with all symbols of the set of N symbols;

and

shuffling the symbols in the permutation vector based on the first pseudorandom number.

7. The method of claim 1 further comprising:

transmitting the output symbols to a decrypting device.

8. The method of claim 1 further comprising:

obtaining a second pseudorandomly selected translation table, from the plurality of translation tables defining different symbol-to-symbol permutations, for each of the input;

symbols to be encrypted; and

translating the output symbols into corresponding second output symbols using their corresponding second translation table for each of the output symbols to further individually encrypt each input symbol.

9. An encryption device, comprising:

means for obtaining a plurality of input symbols;

means for obtaining a pseudorandomly selected translation table, from a plurality of translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be encrypted; and

means for translating the input symbols into corresponding output symbols using their corresponding translation table for each of the input symbols to individually encrypt each input symbol.

10. The device of claim 9 further comprising:

means for obtaining a pseudorandomly selected first translation table for a first input symbol;

means for obtaining a pseudorandomly selected second translation table for a second input symbol;

means for translating the first input symbol into a first output symbol using the first translation table; and

means for translating the second input symbol into a second output symbol using the second translation table.

11. The device of claim 9 further comprising;

means for obtaining a first pseudorandom number for a first input symbol to be encrypted; and

means for shuffling the set of N symbols to obtain a different permutation of the set of N symbols and using that permutation as the translation table for the first input symbol.

12. The device of claim 11 further comprising:

means for generating a pseudorandom number for the first input symbol, where the pseudorandom number is k bits long and k is a positive integer;

means for determining whether the pseudorandom number is within a maximum number Pmax, where Pmax is the largest multiple of N factorial that is less than a maximum threshold 2^k;

means for discarding the pseudorandom number if it is greater than the maximum number Pmax;

means for obtaining different pseudorandom numbers for the first input symbol until an acceptable pseudorandom number is obtained that is less than or equal to the maximum number Pmax; and

means for dividing the acceptable pseudorandom number modulo N factorial to obtain the first pseudorandom number.

13. The device of claim 9 further comprising:

means for transmitting the output symbols to a decrypting device.

14. The device of claim 9 further comprising:

means for obtaining a second pseudorandomly selected translation table, from the plurality of translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be encrypted; and

means for translating the output symbols into corresponding second output symbols using their corresponding second translation table for each of the output symbols to further individually encrypt each input symbol.

15. An encryption device comprising:

an input interface for receiving an input symbol stream; and

a processing circuit coupled to the input interface, the processing circuit configured to

obtain a plurality of input symbols from the input interface;

obtain a pseudorandomly selected translation table, from a plurality of translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be encrypted; and

translate the input symbols into corresponding output symbols using their corresponding translation table for each of the;

input symbols to individually encrypt each input symbol.

16. The device of claim 15 further comprising:

an output interface coupled to the processing circuit for transmitting the output symbols.

17. The device of claim 15 wherein the plurality of input symbols is defined by a set of N symbols, where N is a positive integer and a translation table is a permutation of the N symbols.

18. The device of claim 17 further comprising:

a keystream generator coupled to the processing circuit, the keystream generator configured obtain a first pseudorandom number from the keystream generator for a first input symbol to be encrypted; and

a translation table generator coupled to the processing circuit, the translation table generator configured to shuffle the set of N symbols to obtain a different permutation of the set of N symbols and using that permutation as the translation table for the first input symbol.

19. The device of claim 17 wherein the processing circuit is further configured to

generate a pseudorandom number for the first input symbol, wherein the pseudorandom number is k bits long and k is a positive integer;

determine whether the pseudorandom number is within a maximum number Pmax, where Pmax is the largest multiple of N factorial that is less than a maximum threshold 2^k;

discard the pseudorandom number if it is greater than the maximum number Pmax;

obtain different pseudorandom numbers for the first input symbol until an acceptable pseudorandom number is obtained that is less than or equal to the maximum number Pmax; and

divide the acceptable pseudorandom number modulo N factorial to obtain the first pseudorandom number.

20. The device of claim 17 wherein the processing circuit is further configured to

obtain a second pseudorandomly selected translation table, from the plurality of translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be encrypted;

and

translate the output symbols into corresponding second output symbols using their corresponding second translation table for each of the output symbols to further individually encrypt each input symbol.

21. A machine-readable medium having one or more instructions operational for encrypting symbols, which when executed by a processor causes the processor to:

obtain a plurality of input symbols;

obtain a pseudorandomly selected translation table, from a plurality of translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be encrypted; and

translate the input symbols into corresponding output symbols using their corresponding translation table for each of the input symbols to individually encrypt each input symbol.

22. The machine-readable medium of claim 21 wherein the plurality of input symbols is defined by a set of N symbols, where N is a positive integer and a translation table is a permutation of the N symbols.

23. The machine-readable medium of claim 22 having one or more instructions which when executed by a processor causes the processor to further;

obtain a first pseudorandom number for a first input symbol to be encrypted; and

shuffle the set of N symbols to obtain a different permutation of the set of N symbols and using that permutation as the translation table for the first input symbol.

24. The machine-readable medium of claim 22 having one or more instructions which when executed by a processor causes the processor to further:

generate a pseudorandom number for the first input symbol, wherein the pseudorandom number is k bits long and k is a positive integer,

determine whether the pseudorandom number is within a maximum number Pmax, where Pmax is the largest multiple of N factorial that is less than a maximum threshold 2^k;

discard the pseudorandom number if it is greater than the maximum number Pmax;

obtain different pseudorandom numbers for the first input symbol until an acceptable pseudorandom number is obtained that is less than or equal to the maximum number Pmax; and

divide the acceptable pseudorandom number modulo N factorial to obtain the first pseudorandom number.

25. The machine-readable medium of claim 21 having one or more instructions which when executed by a processor causes the processor to further;

obtain a second pseudorandomly selected translation table, from the plurality of translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be encrypted; and

translate the output symbols into corresponding second output symbols using their corresponding second translation table for each of the output symbols to further individually encrypt each input symbol.

26. A method for decrypting symbols, comprising:

obtaining a plurality of input symbols defined within a set of n symbols;

obtaining a pseudorandomly selected reverse translation table, from a plurality of reverse translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be decrypted; and

translating the input symbols into corresponding output symbols using their corresponding reverse translation table for each of the input symbols to individually decrypt each input symbol.

27. The method of claim 26 wherein the plurality of input symbols is defined by a set of N symbols, where N is a positive integer and a reverse translation table is a permutation of the N symbols and further comprising:

obtaining a first pseudorandom number for a first input symbol to be decrypted; and

shuffling the set of N symbols to obtain a different permutation of the set of N symbols and using that permutation as the reverse translation table for the first input symbol.

28. The method of claim 27 wherein the first pseudorandom number is obtained by

generating a pseudorandom number for the first input symbol, wherein the pseudorandom number is k bits long and k is a positive-integer;

determining whether the pseudorandom number is within a maximum number Pmax, where Pmax is the largest multiple of N factorial that is less than a maximum threshold 2^k;

discarding the pseudorandom number if it is greater titan the maximum number Pmax;

obtaining different pseudorandom numbers for the first input symbol until an acceptable pseudorandom number is obtained that is less than or equal to the maximum number Pmax; and

dividing the acceptable pseudorandom number modulo H factorial to obtain the first pseudorandom number.

29. The method of claim 26 further comprising:

obtaining a second pseudorandomly selected reverse translation table, from the plurality of reverse translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be decrypted; and

translating the output symbols into corresponding second output symbols using their corresponding second reverse translation table for each of the output symbols to further individually decrypt each input symbol.

30. A decryption device, comprising:

means for obtaining a plurality of input symbols defined within a set of n symbols;

means for obtaining a pseudorandomly selected reverse translation table, from a plurality of reverse translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be decrypted; and

means for translating the input symbols into corresponding output symbols using their corresponding reverse translation table for each of the input symbols to individually decrypt each input symbol.

31. The device of claim 30 wherein the plurality of input symbols is defined by a set of N symbols, where N is a positive integer and a reverse translation table is a permutation of the N symbols and further comprising:

means for obtaining a first pseudorandom number for a first input symbol to be decrypted; and

means for shuffling the set of N symbols to obtain a different permutation of the set of N symbols and using that permutation as the reverse translation table for the first input symbol.

32. The device of claim 31 wherein the first pseudorandom number is obtained by

means for generating a pseudorandom number for the first input symbol, wherein the pseudorandom number is k bits long and k is a positive integer;

means for determining whether the pseudorandom number is within a maximum number Pmax, where Pmax is the largest multiple of N factorial that is less than a maximum threshold 2^k;

means for discarding the pseudorandom number if it is greater than the maximum number Pmax;

means for obtaining different pseudorandom numbers for the first input symbol until an acceptable pseudorandom number is obtained that is less than or equal to the maximum number Pmax; and

means for dividing the acceptable pseudorandom number modulo N factorial to obtain the first pseudorandom number.

33. The device of claim 30 further comprising:

means for obtaining a second pseudorandomly selected reverse translation table, from the plurality of reverse translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be decrypted; and

means for translating the output symbols into corresponding second output symbols using their corresponding second reverse translation table for each of the output symbols to further individually decrypt each input symbol.

34. A decryption device, comprising:

an input interface for receiving an input symbol stream; and

a processing circuit coupled to the input interface, the processing circuit configured to

obtain a plurality of input symbols defined within a set of n symbols;

obtain a pseudorandomly selected reverse translation table, from a plurality of reverse translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be decrypted; and

translate the input symbols into corresponding output symbols using their corresponding reverse translation table for each of the input symbols to individually decrypt each input symbol.

35. The device of claim 34 wherein the plurality of input symbols is defined by a set of N symbols, where N is a positive integer and a reverse translation table is a permutation of the N symbols and further comprising:

a keystream generator coupled to the processing circuit, the keystream generator configured obtain a first pseudorandom number from the keystream generator for a first input symbol to be decrypted; and

a reverse translation table generator coupled to the processing circuit, the reverse translation table generator configured to shuffle the set of N symbols to obtain a different permutation of the set of N symbols and using that permutation as the reverse translation table for the first input symbol.

36. The device of claim 34 wherein the plurality of input symbols is defined by a set of N symbols, where N is a positive integer and a reverse translation table is a permutation of the N symbols and the processing circuit is further configured to

generate a pseudorandom number for the first input symbol, wherein the pseudorandom number is k bits long and k is a positive integer;

determine whether the pseudorandom number is within a maximum number Pmax, where Pmax is the largest multiple of N factorial that is less than a maximum threshold 2^k;

discard the pseudorandom number if it is greater than the maximum number Pmax;

obtain different pseudorandom numbers for the first input symbol until an acceptable pseudorandom number is obtained that is less than or equal to the maximum number Pmax; and

divide the acceptable pseudorandom number modulo N factorial to obtain the first pseudorandom number.

37. The device of claim 34 wherein the processing circuit is further configured to

obtain a second pseudorandomly selected reverse translation table, from the plurality of reverse translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be decrypted;

and

translate the output symbols into corresponding second output symbols using their corresponding second reverse translation table for each of the output symbols to further individually decrypt each input symbol.

38. A machine-readable medium having one or more instructions for decrypting symbols, which when executed by a processor causes the processor to:

obtain a plurality of input symbols defined within a set of n symbols;

obtain a pseudorandomly selected reverse translation table, from a plurality of reverse translation tables defining different symbol-to-symbol permutations, for each of the input symbols, to be decrypted; and

translate the input symbols into corresponding output symbols using their corresponding reverse translation table for each of the input symbols to individually decrypt each input symbol.

39. The machine-readable medium of claim 38 wherein the plurality of input symbols is defined by a set of N symbols, where N is a positive integer and a reverse translation table is a permutation of the N symbols, and further comprising one or more instructions which when executed by a processor causes the processor to further:

obtain a first pseudorandom number for a first input symbol to be decrypted; and

shuffle the set of N symbols to obtain a different permutation of the set of N symbols and using that permutation as the reverse translation table for the first input symbol.

40. The machine-readable medium of claim 38 having one or more instructions which when executed by a processor causes the processor to further:

obtain a second pseudorandomly selected reverse translation table, from the plurality of reverse translation tables defining different symbol-to-symbol permutations, for each of the input symbols to be decrypted; and

translate the output symbols into corresponding second output symbols using their corresponding second reverse translation table for each of the output symbols to further individually decrypt each input symbol.