Processes, circuits, devices, and systems for encryption and decryption and other purposes, and processes of making

• US 20060056620A1
• Filed: 09/01/2004
• Published: 03/16/2006
• Est. Priority Date: 09/01/2004
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Karantha, Shankaranarayana, Shingal, Tonmoy, Srinivasan, Chakravarthy
• Granted Patent: US 7,602,905 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• 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 wireless communications device (110) has a digital section (800) and a radio frequency section (840). The digital section (800) does setup and execution on a set of data in at least first and second threads concurrently in a series of overlapping iterations by dividing the set of data into at least two different subsets and concurrently reading and writing in both subsets. A state machine (1010, 1100) is shared by the setup and execution iterations. Two or more memory units (930, 940) segregate the set of data, the predetermined size of the set of data in the memories (930, 940) combined comprehending the total number of addresses occupied by the set of data utilized in operation of circuitry (910). Dirty bits (1430) are accessible at addresses corresponding to addresses in the memory. A selector circuit (1412) has a selector output selectively coupled to an address line, and to a data line. The selector circuit (1412) responds to a state on a dirty bit line (db) to couple data bits related to the address bits themselves from the address line (1421) to the selector output (1412). Other circuits and methods of manufacture and operation are also disclosed.

Claims

1. An integrated circuit comprising:

execute circuitry operable to execute at least part of an encryption process involving a set of data having numerousness N, the circuitry arranged to update at least first and second data concurrently in the set in a series of overlapping iterations followed by subsequent overlapping iterations in the series wherein at least one of the second data depends on the uncompleted processing of the first data; and

an assemblage of memory elements coupled to the execute circuitry having at least two read ports and at least two write ports operable for concurrent read and write, the elements having addresses, the number of memory elements being bounded in numerousness by the number N and sufficient to be utilized by the execute circuitry for updating the set of data for a subsequent iteration in the series.

2. The integrated circuit of claim 1 wherein the memory elements provide storage for an S-Box.

3. The integrated circuit of claim 1 wherein the execute circuitry is arranged to process the first and second data concurrently in iterations of variable length in the series.

4. The integrated circuit of claim 1 wherein the execute circuitry has an output and the integrated circuit further comprises a FIFO (first-in first-out) buffer coupled to the output of the execute circuitry.

5. The integrated circuit of claim 1 the execute circuitry has an output and the integrated circuit further comprises a cryptological logic circuit coupled to the output of the execute circuitry.

6. The integrated circuit of claim 5 wherein the execute circuitry is operable to supply at least some of the set of data from the memory elements to the cryptological logic circuit.

7. The integrated circuit of claim 5 wherein the cryptological logic circuit has a first input for a data stream and a second input coupled to the output of the execute circuit.

8. The integrated circuit of claim 7 wherein the cryptological logic circuit is responsive to the series of iterations by the execute circuit to supply the data stream cryptologically altered as an output.

9. An integrated circuit comprising:

execute circuitry operable to execute at least part of an encryption process involving a set of data of a predetermined size, the circuitry arranged to process at least first and second threads concurrently in the set in a series of overlapping variable-length iterations; and

at least two memory units segregating the set of data, each of the memories coupled to the execute circuitry and having at least one read port and at least one write port operable for concurrent read and write, the locations having addresses, the predetermined size comprehending the total number of addresses occupied by the set of data utilized in operation of the execute circuitry in the memory units combined.

10. The integrated circuit of claim 9 wherein the execute circuitry includes at least two state machines providing the variable length iterations.

11. The integrated circuit of claim 9 wherein the memory elements provide storage for an S-Box.

12. The integrated circuit of claim 9 wherein the execute circuitry has an output and the integrated circuit further comprises a FIFO (first-in first-out) buffer coupled to the output of the execute circuitry.

13. The integrated circuit of claim 12 further comprising a cryptological logic circuit coupled by said FIFO buffer to the output of the execute circuitry.

14. The integrated circuit of claim 13 wherein the execute circuitry is operable to supply at least some of the set of data from the memory elements to the cryptological logic circuit.

15. The integrated circuit of claim 13 wherein the cryptological logic circuit has a first input for a data stream and a second input coupled to the FIFO buffer.

16. The integrated circuit of claim 15 wherein the cryptological logic circuit has a second FIFO buffer for a data stream at the first input.

17. The integrated circuit of claim 9 further comprising a cryptological logic circuit responsive to a data stream and to the series of iterations by the execute circuit to supply the data stream cryptologically altered as an output.

18. Circuitry for use with a storage having storage locations for data and dirty bits accessible at addresses corresponding to addresses in the storage, the circuitry comprising:

an address line for carrying address bits;

a data line for carrying data bits;

a dirty bit line for conveying a dirty bit set/reset state;

a selector circuit having a selector output selectively coupled to the address line, and to the data line, the selector circuit responsive to a state on the dirty bit line to couple data bits related to the address bits themselves from the address line to the selector output.

19. The circuitry claimed in claim 18 herein the selector circuit is further responsive to a different state on the dirty bit line to couple the data line to the selector output instead.

20. The circuitry claimed in claim 18 further comprising a read line coupled to said selector circuit, wherein the selector circuit is further responsive to a read signal on said read line and to a different state on the dirty bit line to couple the data line to the selector output.

21. The circuitry claimed in claim 18 further comprising a control line for carrying a write signal, and a dirty bit control circuit responsive to the write signal on said control line to put a set state on a dirty bit.

22. The circuitry claimed in claim 18 further comprising an address generator coupled to said address line.

23. The circuitry claimed in claim 22 further comprising a sequential control circuit having an output coupled to said address generator.

24. The circuitry claimed in claim 18 further comprising a sequential control circuit having at least one output coupled to enable data reads through said selector circuit.

25. The circuitry claimed in claim 18 further comprising a dirty bit reset line and a sequential control circuit having an output coupled to said dirty bit reset line.

26. The circuitry claimed in claim 18 further comprising a write line coupled to the storage and coupled to the dirty bits to set the dirty bit corresponding to each storage location written to, whereby each storage location not written to has its corresponding dirty bit still reset and each storage location written to has its corresponding dirty bit element set.

27. The integrated circuit of claim 18 further comprising a reset circuit coupled to said dirty bits and operable in a manner to reset said dirty bits, without initializing the at least some storage locations.

28. The circuitry claimed in claim 18 further comprising a reset circuit coupled to to reset the dirty bits concurrently.

29. The circuitry claimed in claim 18 further comprising a reset circuit coupled to reset all the dirty bits in one clock cycle.

30. The circuitry claimed in claim 18 wherein the data bits related to the address bits themselves include at least some of the address bits themselves.

31. The circuitry claimed in claim 18 further comprising a read line coupled to said selector circuit, but the read line isolated from set/reset of the dirty bits, whereby a read leaves the dirty bits unchanged.

32. The circuitry claimed in claim 18 further comprising a control circuit coupled to the address line, and responsive to a cryptological key.

33. The circuitry claimed in claim 18 further comprising a sequential control circuit operable to produce a series of reads and writes of data constituting a data swap between addresses.

34. The circuitry claimed in claim 18 further comprising a cryptological logic circuit having a first input for a stream of bits and a second input coupled to the selector output, and an output for supplying a cryptologically altered stream of bits.

35. The circuitry claimed in claim 18 wherein the selector circuit is responsive to a dirty bit corresponding to the storage location addressed, to convey at least some of the address bits to the selector output as data bits when that dirty bit is in reset state.

36. The circuitry claimed in claim 18 further comprising control circuitry coupled to the selector output to generate second address bits as a function of at least the data bits from the selector output.

37. A method of operating circuitry for use with a storage having storage locations for data at a set of at least some addresses in the storage and for use with addressable dirty bits corresponding to the data, wherein each dirty bit has a dirty bit state being a set state or a reset state, wherein the method comprises

asserting a first address to retrieve the dirty bit state at that first address;

and

in response to a reset state as the dirty bit state retrieved, delivering to an output first data related to the first address instead of storage data at the first address.

38. The method claimed in claim 37 further comprising delivering second data to the output instead of the first data, in response to a set state as the dirty bit state retrieved, wherein the second data is related to data at the first address in the storage instead of to the first address itself.

39. The method claimed in claim 38 wherein the first data is the first address and the second data is the storage data at the first address.

40. The method claimed in claim 37 further comprising asserting a read signal with the first address, and delivering the first data provided the read signal is asserted.

41. The method claimed in claim 37 further comprising

asserting a second address to retrieve the dirty bit state at that second address;

and

in response to a set state as the dirty bit state retrieved from that second address, delivering second data to the output as a function of the data in the storage location at the second address.

42. The method claimed in claim 37 further comprising

asserting a second address to store write data to the storage at the second address;

and

storing a set state in a dirty bit corresponding to the second address.

43. The method claimed in claim 37 further comprising

asserting a write signal with a second address to store write data to the storage at the second address;

and

storing a set state in a dirty bit corresponding to the second address when the write signal is asserted.

44. The method claimed in claim 37 further comprising operating a sequential control circuit to sequentially perform a series of the asserting and delivering operations.

45. The method claimed in claim 37 further comprising reading and writing data to execute a data swap between addresses.

46. The method claimed in claim 37 further comprising initializing by resetting at least some of the dirty bits concurrently.

47. The method claimed in claim 37 further comprising initializing by resetting at least some of the dirty bits concurrently, instead of writing any initialization data to the storage.

48. The method of claim 37 further comprising initializing by resetting the set of dirty bits in response to one reset signal.

49. The method of claim 37 further comprising reading from a storage location and, upon such reading, leaving the state of the corresponding dirty bit unchanged.

50. The method of claim 37 further comprising generating a second address as a function of at least the first data thus delivered.

51. The method of claim 50 wherein the generating of the second address is further as a function of cryptological key bits.

52. The method of claim 50 further comprising asserting a read to the storage with the second address whereby second data are returned.

53. The method of claim 50 further comprising swapping data between the storage locations having the first address and the second address.

54. The method claimed in claim 37 wherein asserting the first address includes generating the first address as a function of a cryptological key.

55. The method claimed in claim 37 further comprising executing on a stream of bits a cryptological logic function in response to said output delivered as above, whereby a cryptologically altered stream of bits is supplied.

56. An integrated circuit comprising:

a first memory having a first read port and a first write port for concurrent read and write, the first memory having memory locations for data accessible by asserting respective addresses to the first memory through the first read port and the first write port;

a second memory having a second read port and a second write port for concurrent read and write, the second memory having memory locations for data accessible by asserting respective addresses to the second memory through the second read port and the second write port; and

address generation circuitry respectively coupled by address lines to said first memory and to said second memory and operable to generate address bits representative of odd and even addresses, said first memory responsive only to the even addresses and said second memory responsive only to the odd addresses.

57. The integrated circuit of claim 56 wherein the address generation circuitry is operable sequentially for encryption.

58. The integrated circuit of claim 56 wherein the address generation circuitry is operable to generate address bits representative of at least one odd address and at least one even address concurrently.

59. The integrated circuit of claim 56 further comprising data write circuitry and data read circuitry each coupled to said first and second memories.

60. The integrated circuit of claim 56 further comprising a sequential control circuit coupled to said address generation circuitry and having a storage for a cryptological key.

61. The integrated circuit of claim 56 further comprising a sequential control circuit operable to produce a series of reads and writes of data from said first and second memories thereby as a result to generate addresses for at least some of the reads and writes in the series.

62. The integrated circuit of claim 56 further comprising a sequential control circuit having a encryption control output coupled to the address generation circuitry.

63. The integrated circuit of claim 56 further comprising a cryptological logic circuit responsive to data from said first and second memories.

64. The integrated circuit of claim 56 further comprising a cryptological logic circuit including:

a first input for a stream of bits, a second input coupled to the first and second memories; and

an output for supplying a cryptologically altered stream of bits.

65. A method of operating an integrated circuit comprising:

concurrently reading and writing data in a first memory, the first memory having memory locations for data accessible by asserting respective addresses to the first memory through a first read port and a first write port;

concurrently reading and writing data in a second memory, the second memory having memory locations for data accessible by asserting respective addresses to the second memory through a second read port and a second write port; and

generating address bits representative of odd and even addresses, the first memory responsive only to the even addresses and the second memory responsive only to the odd addresses.

66. The method of claim 65 wherein the generating address bits provides an encryption-related operation.

67. The method of claim 65 wherein the generating address bits provides at least one odd address and at least one even address concurrently.

68. The method of claim 65 further comprising sequentially controlling the generating address bits based on a cryptological key.

69. The method of claim 65 further comprising sequentially producing a series of reads and writes of data from the first and second memories thereby as a result to generate addresses for at least some of the reads and writes in the series.

70. The method of claim 65 further comprising a sequentially controlling the generating address bits to provide a setup operation followed by an encryption operation.

71. The method of claim 65 further comprising a cryptologically altering a stream data in response to bits from said first and second memories and said address bits.

72. A process of making integrated circuits having operations of at least a portion of the integrated circuit definable by Case/Subcase tables, the process comprising

making at least a first state machine and a second state machine corresponding to a partition of the Case/SubCase tables into at least a first part and a second part.

73. The process of claim 72 further comprising fabricating integrated circuits with at least the first and second state machines therein.

74. The process of claim 72 further comprising arranging the Case/Subcase tables to have increased regularity prior to the making.

75. The process of claim 72 wherein the first state machine has logic related to the Cases.

76. The process of claim 72 wherein the second state machine has logic related to the Subcases.

77. The process of claim 72 wherein the first state machine has logic related to the Cases and the second state machine has logic related to the Subcases, whereby logic for each Case/Subcase is obviated.

78. The process of claim 72 further comprising optimizing the state machines for number of gates to implement the operations and data throughput of the operations.

79. The process of claim 72 wherein the state machines provide an encryption feature.

80. The process of claim 72 wherein further setup operations are definable by Setup Case tables and the making includes structuring the first state machine for operations that the Setup Case tables have in common with the first part of the Case/SubCase tables.

81. An integrated circuit comprising:

a memory having memory locations for data accessible by asserting respective addresses to the memory;

a first register;

a second register;

read circuitry operable to read to the first register a first datum stored at a location in the memory represented by a first address;

an address circuit operable to generate a second address at which the first datum will be stored in said memory and a third address at which a second datum can be read from memory;

a comparison circuitry responsive to said address circuit when the third address is different from the second address to read the second datum to said second register from the third address in said memory, and when the third address is same as the second address then to copy the first datum to said second register as the second datum.

82. The integrated circuit of claim 81 further comprising a storing circuit operable to store the first datum at the second address after the reading or copying of the second datum to said second register by said comparison circuitry.

83. The integrated circuit of claim 81 further comprising control circuitry coupled to the comparison circuitry to perform operations plural times concurrently on plural bytes in an iteration of overlapping dependent calculations.

84. A process of resolving a dependency in an integrated circuit including a memory having memory locations for data accessible by asserting respective addresses to the memory, the process comprising:

reading to a first register a first datum stored at a location in the memory represented by a first address;

generating a second address at which the first datum will be stored in the memory;

providing a third address at which a second datum can be read;

comparing the second address with the third address, and if different then reading the second datum to a second register from the third address in the memory, and if same then copying the first datum to the second register as the second datum.

85. The process of claim 84 further comprising storing the first datum at the second address after the reading or copying of the second datum to the second register.

86. The process of claim 84 performed plural times concurrently on plural bytes in an iteration of overlapping dependent calculations.

87. An integrated circuit comprising:

execute circuitry operable to execute at least part of a process involving a set of data, the circuitry arranged to process operations of setup and execution, each of the setup and execution including at least first and second threads concurrently in the set in a series of overlapping iterations; and

a state machine coupled to the execute circuitry, the state machine shared by the setup and execution iterations.

88. The integrated circuit of claim 87 further comprising a control state machine coupled to the execute circuit and generally operable to provide at least one control signal distinguishing the setup from the execution.

89. The integrated circuit of claim 87 wherein the execute circuitry includes a secondary state machine generally operable for executing a portion of the execution iterations other than shared by the setup iterations and execution operations.

90. The integrated circuit of claim 87 further comprising at least two memory units segregating the set of data, each of the memories coupled to the execute circuitry and having at least one read port and at least one write port operable for concurrent read and write, the locations having addresses, the set of data having a size comprehending the total number of addresses occupied by the set of data utilized in operation of the execute circuitry in the memory units combined.

91. The integrated circuit of claim 87 wherein the setup is an S-Box setup.

92. The integrated circuit of claim 87 wherein the execution is an RC4 encryption.

93. The integrated circuit of claim 87 further comprising a data stream logic circuit coupled to the execute circuitry.

94. The integrated circuit of claim 87 further comprising a data stream logic circuit and a FIFO circuit coupling the data stream logic circuit to the execute circuitry.

95. The integrated circuit of claim 87 further comprising a data stream logic circuit coupled to the execute circuitry so that data stream logic operations occur in the execution and are prevented in the setup.

96. The integrated circuit of claim 87 wherein the state machine produces iterations of variable length.

97. The integrated circuit of claim 87 wherein the state machine comprises a primary state machine and a secondary state machine, each responsive to the other.

98. A method of operating an integrated circuit comprising:

executing at least part of a process including operations of setup and execution on a set of data in at least first and second threads concurrently in a series of overlapping iterations by sharing a state machine for operations common to the setup and execution iterations.

99. The method of claim 98 further comprising providing at least one control signal distinguishing the setup from the execution.

100. The method of claim 98 wherein the executing includes running a secondary state machine for operations other than shared by the setup iterations and execution operations.

101. The method of claim 98 further comprising segregating the set of data into two different subsets and concurrently reading and writing in both subsets.

102. The method of claim 98 further comprising performing a logic operation on a data stream to produce a result stream depending on the execution iterations.

103. The method of claim 98 further comprising buffering the execution and performing a logic operation on a data stream to produce a result stream depending on the execution thus buffered.

104. The method of claim 98 further comprising performing a logic operation on a data stream to produce a result stream depending on the execution iterations but preventing the result stream in the setup.

105. The method of claim 98 including operating the state machine in iterations of variable length.

106. The method of claim 98 including operating the state machine in first and second parts starting and stopping each other.

107. An article of manufacture comprising a substantially planar medium having physically established therein structures corresponding to operations of a process including operations of setup and execution on a set of data in at least first and second threads concurrently in a series of overlapping iterations by dividing the set of data into at least two different subsets and concurrently reading and writing in both subsets.

108. The article of claim 107 further including structures corresponding to a logic operation on a data stream to produce a result stream depending on the execution iterations.

109. The article of claim 107 wherein the structures further establish operations on a data stream to produce a result stream depending on the execution iterations but preventing the result stream in the setup.

110. The article of claim 107 wherein the structures correspond to operations producing iterations of variable length.

111. The article of claim 107 wherein the structures correspond to operations in first and second parts starting and stopping each other to produce the iterations.

112. The article of claim 107 wherein the structures correspond to operations resolving at least one dependency between the overlapping iterations.

113. The article of claim 107 wherein the structures correspond to dirty bit operations compressing setup by selectively delivering addresses as representations of setup data depending on at least one dirty bit state.

114. The article of claim 107 wherein the structures correspond to dirty bit operations bypassing initialization of the set of data by simultaneously resetting dirty bits.

115. The article of claim 107 wherein the structures correspond to dirty bit operations setting a dirty bit when data is written.

116. The article of claim 107 wherein the structures correspond to encryption operations.

117. The article of claim 107 wherein the structures correspond to RC4 encryption operations on streaming data.

118. The article of claim 107 wherein the structures correspond to operations including at least one operation selected from the communications group consisting of WLAN, 802.11, GSM, GPRS, EDGE, UMTS, CDMA, WCDMA, HSDPA, 1xEV-DV, 3xEV-DV, 1xEV-DO.

119. The article of claim 107 wherein the structures correspond to operations including at least one operation selected from the encryption group consisting of SHA-1, MD2, MD5, DES, 3DES, RC4, ARC4, TKIP, AES, RSA, DSA, DH, NTRU, ECC.

120. A process of manufacturing a wireless communications device comprising establishing in the device operational features resulting from use of an article of manufacture comprising a substantially planar medium having physically established therein structures corresponding to operations of a process including operations of setup and execution on a set of data in at least first and second threads concurrently in a series of overlapping iterations by dividing the set of data into at least two different subsets and concurrently reading and writing in both subsets.

121. The process of claim 120 wherein the operations further include a logic operation on a data stream to produce a result stream depending on the execution iterations.

122. The process of claim 120 wherein the operations produce iterations of variable length.

123. The process of claim 120 wherein the operations resolve at least one dependency between the overlapping iterations.

124. The process of claim 120 wherein the operations include dirty bit operations compressing setup by selectively delivering addresses as representations of setup data depending on at least one dirty bit state.

125. The process of claim 120 wherein the operations include encryption operations.

126. The process of claim 120 wherein the operations include at least one operation selected from the communications group consisting of WLAN, 802.11, GSM, GPRS, EDGE, UMTS, CDMA, WCDMA, HSDPA, 1xEV-DV, 3xEV-DV, 1xEV-DO.

127. The process of claim 120 wherein the operations include at least one operation selected from the encryption group consisting of SHA-1, MD2, MD5, DES, 3DES, RC4, ARC4, TKIP, AES, RSA, DSA, DH, NTRU, ECC.

128. A wireless communications device comprising a digital section and a radio frequency section, the digital section including circuitry having physically established therein structures implementing operations of setup and execution on a set of data in at least first and second threads concurrently in a series of overlapping iterations by dividing the set of data into at least two different subsets and concurrently reading and writing in both subsets.

129. The wireless communications device of claim 128 wherein the structures implement a logic operation on a data stream to produce a result stream depending on the execution iterations.

130. The wireless communications device of claim 128 wherein the structures correspond to operations producing iterations of variable length.

131. The wireless communications device of claim 128 wherein the structures correspond to operations in first and second parts starting and stopping each other to produce the iterations.

132. The wireless communications device of claim 128 wherein the structures correspond to operations resolving at least one dependency between the overlapping iterations.

133. The wireless communications device of claim 128 wherein the structures correspond to dirty bit operations compressing setup by selectively delivering addresses as representations of setup data depending on at least one dirty bit state.

134. The wireless communications device of claim 128 wherein the structures correspond to dirty bit operations bypassing initialization of the set of data by simultaneously resetting dirty bits.

135. The wireless communications device of claim 128 wherein the structures correspond to dirty bit operations setting a dirty bit when data is written.

136. The wireless communications device of claim 128 wherein the structures correspond to encryption operations.

137. The wireless communications device of claim 128 wherein the structures correspond to RC4 encryption operations on streaming data.

138. The wireless communications device of claim 128 wherein the circuitry implements a wireless local area network (WLAN) device function.

139. The wireless communications device of claim 128 wherein the digital section implements one or more functions selected from the group consisting of WLAN, 802.11, GSM, GPRS, EDGE, UMTS, CDMA, WCDMA, HSDPA, 1xEV-DV, 3xEV-DV, 1xEV-DO.

140. The wireless communications device of claim 128 wherein the circuitry implements one or more functions selected from the group consisting of SHA-1, MD2, MD5, DES, 3DES, RC4, ARC4, TKIP, AES, RSA, DSA, DH, NTRU, ECC.

141. A digital circuit comprising

a memory;

a dirty bit array; and

an execution unit establishing maximum 256 (two hundred fifty six) bytes of S-Box in the memory and maximum 256 (two hundred fifty six) dirty bits in the dirty bit array corresponding to the S-Box, the execution unit having throughput exceeding 0.40 Bytes per cycle,

the memory, dirty bit array, and execution unit together implemented in less than 20,000 (twenty thousand) gates.

142. The digital circuit of claim 141 having single-cycle initialization of S-Box in the dirty bit array.

143. The digital circuit of claim 141 having 385 cycles-or-less setup of S-Box.

144. The digital circuit of claim 141 having the memory, dirty bit array, and execution unit together implemented in less than 15,000 (fifteen thousand) gates.