Cryptographic system configured for extending a repetition period of a random sequence

• US 7,995,749 B2
• Filed: 10/30/2007
• Issued: 08/09/2011
• Est. Priority Date: 10/30/2007
• Status: Active Grant

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Michaels, Alan J.
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): KAPLAN, BENJAMIN A
• Application Number:
  US11/928,013
• Publication Number:
  US 20090110197A1
• Time in Patent Office: 1,379 Days
• Field of Search: 380/28, 380/268
• US Class Current: 380/28
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: G06F 7/729 using representation by a residue number system
• CPC Class Codes: G06F 7/766 Generation of all possible permutations
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• 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

A cryptographic system (CS) is provided. The CS (500) is comprised of a data stream receiving means (DSRM), a ring generator (RG) and an encryptor. The DSRM (602) provides a data stream (DS). The RG (400) includes a computing (404-408), converting (404-408) and permutation (410) means. The computing means is configured to perform RNS arithmetic operations to express a random number in a random number sequence as RNS residue values (RNSRV). The converting means is configured to convert each RNSRV to a relatively prime number system so that each RNSRV includes at least one digit. The permutation means is configured to generate an arbitrary permutation ordering of output sequence numbers (OSNs) using a select combination of digits associated with each RNSRV. The arbitrary permutation ordering is determined using a cyclic structure. The encryptor is configured to generate a modified data stream by combining the OSNs and DS.

Claims

1. A cryptographic system, comprising:

a data stream receiving circuit configured to receive a data stream;

a ring generator circuit including

(a) a computing module configured to

perform a plurality of RNS arithmetic operations to express a random number in a random number sequence as a plurality of RNS residue values, said plurality of RNS residue values computed during said plurality of RNS arithmetic operations using a plurality of different modulus raised to different powers, and

convert each of said plurality of RNS residue values to a relatively prime number system so that each of said plurality of RNS residue values includes at least one digit, and

(b) a permutation module coupled to said computing module and configured to generate an arbitrary permutation ordering of a plurality of output sequence numbers using a select combination of digits associated with each of said plurality of RNS residue values, wherein said arbitrary permutation ordering is determined using a cyclic structure having n elements each having assigned thereto an output sequence number of said plurality of output sequence numbers and using a value of said select combination of digits to select an available unselected element in said cyclic structure, and wherein said arbitrary permutation ordering of said plurality of output sequence numbers is defined by an order of a selection of said n elements of said cyclic structure; and

an encryptor circuit coupled to said data stream receiving circuit and said ring generator circuit, said encryptor circuit configured to generate a modified data stream by incorporating or combining said plurality of output sequence numbers with said data stream.

2. The cryptographic system according to claim 1, wherein said random number has a value within a range of zero to n!−

1.

3. The cryptographic system according to claim 1, wherein said computing module is further configured to calculate said plurality of RNS residue values using relatively prime numbers as moduli, wherein said relatively prime numbers are selected to have a product equal to a decimal number defined by n!.

4. The cryptographic system according to claim 1, wherein said converting module is further configured to convert each of said plurality of RNS residue values to a different relatively prime number system.

5. The cryptographic system according to claim 1, wherein said select combination of digits are chosen so that a range of values which can be determined by said digits is equal to a number of available unselected elements in said cyclic structure.

6. The cryptographic system according to claim 1, wherein said permutation module is further configured to use a Chinese Remainder Theorem to combine at least two digits associated with at least two RNS residue values to obtain a digit having a different number base than said at least two digits.

7. The cryptographic system according to claim 1, wherein said permutation module is further configured to use a Chinese Remainder Theorem to combine with one or more additional cyclic ring generators.

8. The cryptographic system according to claim 7, wherein said permutation module is further configured to use said digit having a different number base to select said available unselected element in said cyclic structure.

9. The cryptographic system according to claim 1, wherein said encryptor circuit includes at least one of a multiplier, an adder, a digital logic device and a feedback mechanism.

10. The cryptographic system according to claim 1, wherein said encryptor circuit is configured to perform at least one of a standard multiplication operation, a multiplication in a Galois extension field operation, an addition modulo q operation, a subtraction modulo q operation and a bitwise logic operation.

11. The cryptographic system according to claim 1, further comprising a second ring generator circuit configured to generate a decryption sequence.

12. The cryptographic system according to claim 11, further comprising a decryptor circuit electronically connected to said second ring generator circuit, said decryptor circuit configured to generate decrypted data by performing a decryption method utilizing said modified data stream and said decryption sequence.

13. A cryptographic system, comprising:

a data stream receiving circuit configured to receive a data stream;

a first ring generator circuit including

(a) a computing module configured to

perform a plurality of RNS arithmetic operations to express a random number in a random number sequence as a plurality of RNS residue values, said plurality of RNS residue values computed during said plurality of RNS arithmetic operations using a plurality of different modulus raised to different powers, and

convert each of said plurality of RNS residue values to a relatively prime number system so that each of said plurality of RNS residue values includes at least one digit, and

(b)a permutation module configured to generate an arbitrary permutation ordering of a plurality of output sequence numbers using a select combination of digits associated with each of said plurality of RNS residue values, wherein said arbitrary permutation ordering is determined using a cyclic structure having n elements each having assigned thereto an output sequence number of said plurality of output sequence numbers and using a value of said select combination of digits to select an available unselected element in said cyclic structure, and wherein said arbitrary permutation ordering of said plurality of output sequence numbers is defined by an order of a selection of said n elements of said cyclic structure; and

a diffusion operator circuit coupled to said data stream receiving circuit and said first ring generator circuit, said diffusion operator circuit configured to generate a diffused data stream by permuting said data stream using said arbitrary permutation ordering of a plurality of output sequence numbers.

14. The cryptographic system according to claim 13, wherein said random number has a value within a range of zero to n!−

1.

15. The cryptographic system according to claim 13, wherein said computing module is further configured to calculate said plurality of RNS residue values using relatively prime numbers as moduli, wherein said relatively prime numbers are selected to have a product equal to a decimal number defined by n!.

16. The cryptographic system according to claim 13, wherein said converting module is further configured to convert each of said plurality of RNS residue values to a different relatively prime number system.

17. The cryptographic system according to claim 13, wherein said select combination of digits are chosen so that a range of values which can be determined by said digits is equal to a number of available unselected elements in said cyclic structure.

18. The cryptographic system according to claim 13, wherein said permutation module is further configured to use a Chinese Remainder Theorem to combine at least two digits associated with at least two RNS residue values to obtain a digit having a different number base than said at least two digits.

19. The cryptographic system according to claim 18, wherein said permutation module is further configured to use said digit having a different number base to select said available unselected element in said cyclic structure.

20. The cryptographic system according to claim 13, further comprising a second ring generator circuit configured to generate a reverse diffusion sequence comprised of pseudo-random numbers or pseudo-chaotic random numbers.

21. The cryptographic system according to claim 20, further comprising a reverse diffusion operator circuit coupled to said second ring generator circuit, said diffusion operator circuit configured to undiffused said diffused data stream by performing reverse diffusion operations utilizing said reverse diffusion sequence.

22. A method for generating a modified data stream, comprising:

receiving a data stream by an electronic circuit;

performing, by said electronic circuit, a plurality of RNS arithmetic operations to express a random number in a random number sequence as a plurality of RNS residue values, said plurality of RNS residue values computed during said plurality of RNS arithmetic operations using a plurality of different modulus raised to different powers;

converting, by said electronic circuit, each of said plurality of RNS residue values to a relatively prime number system so that each of said plurality of RNS residue values includes at least one digit;

generating, by said electronic circuit, an arbitrary permutation ordering of a plurality of output sequence numbers using a select combination of digits associated with each of said plurality of RNS residue values; and

generating, by said electronic circuit, said modified data stream by incorporating or combining said plurality of output sequence numbers with said data stream;

wherein said arbitrary permutation ordering is determined using a cyclic structure having n elements each having assigned thereto an output sequence number of said plurality of output sequence numbers and using a value of said select combination of digits to select an available unselected element in said cyclic structure; and

wherein said arbitrary permutation ordering of said plurality of output sequence numbers is defined by an order of a selection of said n elements of said cyclic structure.

23. A method for generating a diffused data stream, comprising:

receiving, by an electronic circuit, a data stream;

performing, by said electronic circuit, a plurality of RNS arithmetic operations to express a random number in a random number sequence as a plurality of RNS residue values, said plurality of RNS residue values computed during said plurality of RNS arithmetic operations using a plurality of different modulus raised to different powers;

converting, by said electronic circuit, each of said plurality of RNS residue values to a relatively prime number system so that each of said plurality of RNS residue values includes at least one digit;

generating, by said electronic circuit, an arbitrary permutation ordering of a plurality of output sequence numbers using a select combination of digits associated with each of said plurality of RNS residue values; and

generating, by said electronic circuit, said diffused data stream by permuting said data stream using said arbitrary permutation ordering of a plurality of output sequence numbers;

wherein said arbitrary permutation ordering is determined using a cyclic structure having n elements each having assigned thereto an output sequence number of said plurality of output sequence numbers and using a value of said select combination of digits to select an available unselected element in said cyclic structure; and

wherein said arbitrary permutation ordering of said plurality of output sequence numbers is defined by an order of a selection of said n elements of said cyclic structure.