Encryption processor with shared memory interconnect

Abstract

An encryption chip is programmable to process a variety of secret key and public key encryption algorithms. The chip includes a pipeline of processing elements, each of which can process a round within a secret key algorithm. Data is transferred between the processing elements through dual port memories. A central processing unit allows for processing of very wide data words from global memory in single cycle operations. An adder circuit is simplified by using plural relatively small adder circuits with sums and carries looped back in plural cycles. Multiplier circuitry can be shared between the processing elements and the central processor by adapting the smaller processing element multipliers for concatenation as a very wide central processor multiplier.

What is claimed is: 
     
       1. An electronic encryption device comprising, on a single chip, an array of processing elements, each processing element comprising:
 an instruction memory for storing a round of an encryption algorithm, the round comprising a sequence of instructions; 
 a processor for implementing the round from the instruction memory; 
 data storage for storing encryption data operands and encrypted data resulting from implementing the round; 
 processing elements of the array each implementing one of the rounds and transferring results to successive processing elements such that the array of processing elements implements successive rounds of the encryption algorithm in a processing element pipeline. 
 
     
     
       2. An electronic encryption device as claimed in  claim 1  wherein the data storage has a portion thereof which is shared between adjacent processing elements of the linear array for transfer of data between adjacent processing elements of the linear array. 
     
     
       3. An electronic encryption device as claimed in  claim 2  wherein each processing element comprises a control unit and an ALU, the control unit, instruction memory and data storage being connected to a local processing element data bus, the local data bus being segmented into two independent portions by a switch; the control unit and instruction memory being connected to one of the segments, and the ALU and data storage being connected to the other of the segments. 
     
     
       4. An electronic encryption device as claimed in  claim 2  wherein each processing element comprises a control unit and an ALU, the control unit, instruction memory, local data memory and shared data storage connected to a local processing element bus, the local bus being segmented by a switch into a local instruction bus segment connecting the instruction memory and the control unit, and a local data bus segment connecting the ALU, local data memory and shared data storage, the switch permitting either independent simultaneous operation on the two local bus segments, or a communication between the two bus segments. 
     
     
       5. An electronic encryption device as claimed in  claim 4  wherein each processing element further comprises a multiplier for performing multiplication operations within the processing element. 
     
     
       6. An electronic encryption device as claimed in  claim 2  wherein, during the implementation of the encryption algorithm, each processing element in the pipeline writes resulting data into the data storage shared with the subsequent processing element for direct access by the subsequent processing element. 
     
     
       7. An electronic encryption device as claimed in  claim 2  wherein the shared data storage of the processing elements are comprised of dual port memories shared between adjacent processing elements of the linear array for transfer of data between adjacent processing elements of the linear array. 
     
     
       8. An electronic encryption device as claimed in  claim 7  wherein each processor comprises a control unit and an ALU, the control unit, ALU, instruction memory, local data memory and shared data storage being connected to a local processing element data bus, the local data bus being segmented into two independent segments by a switch; the control unit and instruction memory being connected to one of the segments and the ALU, local data memory and shared data storage being connected to the other of the segments. 
     
     
       9. An electronic encryption device as claimed in  claim 1  wherein each processing element further comprises a multiplier for performing multiplication operations within the processing element. 
     
     
       10. An electronic encryption device as claimed in  claim 9  wherein the multipliers of plural processing elements are adapted for concatenation as segments of a wider multiplier. 
     
     
       11. An electronic encryption device as claimed in  claim 10  wherein each multiplier comprises partial product adders having input selection circuitry for selecting a first set of inputs when operating as an individual multiplier, and a second set of inputs, including inputs from adjacent processing elements, when concatenated. 
     
     
       12. An electronic encryption device as claimed in  claim 1  wherein each processor comprises a control unit and an ALU, the control unit, ALU, instruction memory, local data memory and shared data storage being connected to a local processing element data bus, the local data bus being segmented into two independent segments by a switch; the control unit and instruction memory being connected to one of the segments and the ALU, local data memory and shared data storage being connected to the other of the segments. 
     
     
       13. An electronic encryption device as claimed in  claim 1  further comprising a global random access memory and a global bus through which data is transferred between the global random access memory and the processing element data storage. 
     
     
       14. An electronic encryption device as claimed in  claim 13  further comprising a central processor coupled to the global bus for processing data words which are wider than data words processed by the processing elements. 
     
     
       15. An electronic encryption device as claimed in  claim 14  wherein each processing element further comprises a multiplier for performing multiplication operations within the processing element. 
     
     
       16. An electronic encryption device as claimed in  claim 15  wherein the multipliers of plural processing elements are adapted for concatenation as segments of a wider multiplier. 
     
     
       17. An electronic encryption device as claimed in  claim 16  wherein each multiplier comprises partial product adders having input selection circuitry for selecting a first set of inputs when operating as an individual multiplier, and a second set of inputs, including inputs from adjacent processing elements, when concatenated. 
     
     
       18. An electronic encryption device as claimed in  claim 13  wherein the central processor comprises an adder comprising:
 plural adder segments, each of the plural adder segments having a carry output and a sum output, each of the plural adder segments processing a segment of each of two operands; 
 carry selectors to select the carry outputs as carry inputs to successive adder segments and for successive clock cycles so long as any carry results in an adder cycle; and 
 operand selectors to select each sum output as an operand input to the same adder segment for successive clock cycles so long as any carry results in an adder cycle. 
 
     
     
       19. An electronic encryption device as claimed in  claim 1  wherein each processor of each processing element performs a modulo adjust operation to compute M mod N. 
     
     
       20. An electronic encryption device as claimed in  claim 1  wherein each processor of each processing element performs a modulo add or subtract operation to compute A±B mod N. 
     
     
       21. An electronic encryption device as claimed in  claim 1  wherein each processor of each processing element performs a modulo multiply operation to compute A×B mod N. 
     
     
       22. An electronic encryption device as claimed in  claim 1  wherein the encryption device further comprises an adder comprising:
 plural adders segments, each of the plural adder segments having a carry output and a sum output, each of the plural adder segments processing a segment of each of two operands; and 
 carry selectors to select the carry outputs as carry inputs to successive adder segments for successive clock cycles so long as any carry results in an adder cycle; 
 operand selectors to select each sum output as an operand input to the same adder segment for successive clock cycles so long as any carry results in an adder cycle. 
 
     
     
       23. An electronic encryption device comprising, on a single chip, a linear array of processing elements, each processing element comprising:
 an instruction memory for storing code required to implement at least a round of an encryption algorithm; 
 a processor for processing the round from the instruction memory; 
 local data memory; 
 shared data storage between two adjacent processing elements; 
 processing elements of the linear array each implementing one of the rounds and transferring results to successive processing elements such that the linear array of processing elements processes successive rounds of the encryption algorithm in a processing element pipeline. 
 
     
     
       24. An electronic encryption device as claimed in  claim 23  wherein, during the implementation of the encryption algorithm, each processing element in the pipeline writes resulting data into the data memory shared with the subsequent processing element for direct access by the subsequent processing element. 
     
     
       25. An encryption data processing system comprising a linear array of processing elements, each processing element comprising:
 an instruction memory; 
 a processor for processing instructions from the instruction memory; 
 data memory; 
 data memories of the processing elements of the linear array comprising dual port memories shared between adjacent processing elements for transfer of data between adjacent processing elements of the linear array. 
 
     
     
       26. An electronic encryption system as claimed in  claim 25  wherein each processor comprises a control unit and an ALU, the control unit, ALU, instruction memory, data memories of the processing elements being connected to a local processing element data bus, the local data bus being segmented into two independent portions by a switch; the control unit and instruction memory being connected to one of the segments and the ALU and local and shared data memories being connected to the other of the segments. 
     
     
       27. An electronic encryption system as claimed in  claim 25  wherein each processing element further comprises a multiplier for performing multiplication operations within the processing element. 
     
     
       28. An electronic encryption system as claimed in  claim 27  wherein the multipliers of plural processing elements are adapted for concatenation as segments of a wider multiplier. 
     
     
       29. An electronic encryption system as claimed in  claim 28  wherein each multiplier comprises partial product adders having input selection circuitry for selecting a first set of inputs when operating as an individual multiplier, and a second set of inputs, including inputs from adjacent processing elements, when concatenated. 
     
     
       30. An electronic encryption system as claimed in  claim 25  further comprising a global random access memory and a global bus through which data is transferred between the global random access memory and the processing element data memories. 
     
     
       31. An electronic encryption system as claimed in  claim 30  further comprising a central processor coupled to the global bus for processing data words which are wider than data words processed by the processing elements. 
     
     
       32. An electronic encryption system as claimed in  claim 31  further comprising a multiplier for performing multiplication operations within the processing element. 
     
     
       33. An electronic encryption system as claimed in  claim 32  wherein the multipliers of plural processing elements are adapted for concatenation as segments of a wider multiplier. 
     
     
       34. An electronic encryption system as claimed in  claim 33  wherein each multiplier comprises partial product adders having input selection circuitry for selecting a first set of inputs when operating as an individual multiplier, and a second set of inputs, including inputs from adjacent processing elements, when concatenated. 
     
     
       35. An electronic encryption system as claimed in  claim 31  wherein the central processor comprises an adder comprising:
 plural adder segments, each of the plural adder segments having a carry output and a sum output, each of the plural adder segments processing a segment of each of two operands; 
 carry selectors to select the carry outputs as carry inputs to successive adder segments for successive clock cycles so long as any carry results in an adder cycle; and 
 operand selectors to select each sum output as an operand input to the same adder segment for successive clock cycles so long as any carry results in an adder cycle. 
 
     
     
       36. An electronic encryption system as claimed in  claim 25  wherein each processor of each processing element performs a modulo adjust operation to compute M mod N. 
     
     
       37. An electronic encryption system as claimed in  claim 25  wherein each processor of each processing element performs a modulo add or subtract operation to compute A±B mod N. 
     
     
       38. An electronic encryption system as claimed in  claim 25  wherein each processor of each processing element performs a modulo multiply operation to compute A×B mod N. 
     
     
       39. An electronic encryption system as claimed in  claim 25  wherein the encryption device further comprises an adder comprising:
 plural adder segments, each of the plural adder segments having a carry output and a sum output, each of the plural adder segments processing a segment of each of two operands; 
 carry selectors to select the carry outputs as carry inputs to successive adder segments for successive clock cycles so long as any carry results in an adder cycle; and 
 operand selectors to select each sum output as an operand input to the same adder segment for successive clock cycles so long as any carry results in an adder cycle. 
 
     
     
       40. An electronic encryption device as claimed in  claim 25  wherein, during the implementation of the encryption algorithm, each processing element in the pipeline writes resulting data into the data memory shared with the subsequent processing element for direct access by the subsequent processing element. 
     
     
       41. A multiplier circuit comprising:
 a plurality of multiplier segments, each receiving operand words of a first length; and 
 input selectors which select a first set of inputs when the multiplier segments operate as individual multipliers and a second set of inputs to concatenate the multiplier segments as a wider multiplier operating on operands of a second word length, 
 wherein the first word length is 32 bits and the second word length is 512 bits. 
 
     
     
       42. A multiplier as claimed in  claim 41  wherein each multiplier segment comprises partial product adders. 
     
     
       43. An adder comprising:
 plural adder segments, each having a carry output and a sum output, each of the adder segments processing a segment of each of two operands;   carry selectors to select the carry outputs as carry input to successive adder segments for successive clock cycles so long as any carry results in an adder cycle; and   operand selectors to select each carry output as an operand input to the same adder segment for successive clock cycles so long as any carry results in an adder cycle.   
     
     
       44. An electronic encryption device comprising, on a single chip:
 a linear array of processing elements, each comprising an instruction store, data storage, and a processor which processes a sequence of instructions from the instruction store to operate on data words of a first length, the data storage of the processing elements including dual port memories shared between adjacent processing elements for transfer of data between adjacent processing elements of the array, the processing elements of the linear array having stored in their instruction stores respective rounds of an encryption algorithm and transferring results of the rounds to successive processing elements such that the linear array of processing elements processes successive rounds of the encryption algorithm in a processing element pipeline; 
 a global random access memory; 
 a global bus to which data is transferred between the global random access memory and the processing element data memories; and 
 a public key encryption processor operating on data words of a second length at least an order of magnitude longer than the first length, the public key processor accessing global random access memory in word lengths of the second length. 
 
     
     
       45. An electronic encryption device comprising, on a single chip, an array of processing elements, each processing element comprising:
 instruction memory means for storing a round of an encryption algorithm; 
 processor means for implementing the round from the instruction memory; and 
 data storage means for storing encryption data operands and encrypted data resulting from implementing the round. 
 
     
     
       46. An electronic encryption device as claimed in  claim 45  wherein the data storage means has a portion thereof which is shared between adjacent processing elements of the linear array for transfer of data between adjacent processing elements of the linear array. 
     
     
       47. An electronic encryption device as claimed in  claim 46  further comprising global random access memory means and a global bus means through which data is transferred between the global random access memory means and the processing element data storage means. 
     
     
       48. An electronic encryption device as claimed in  claim 47  further comprising central processing means coupled to the global bus means for processing data words which are wider than the data words processed by the processing elements. 
     
     
       49. A method of encryption comprising:
 in an electronic circuit on a single chip, receiving data to be encrypted; 
 applying the data to a pipeline of data processing elements on the chip, each processing element processing an encryption round from a block cipher algorithm and transferring results to successive processing elements such that the processing elements implement successive rounds of the encryption algorithm in a processing element pipeline. 
 
     
     
       50. A method as claimed in  claim 49  wherein results are transferred to successive processing elements through shared memory. 
     
     
       51. A method as claimed in  claim 50  further comprising processing encryption algorithms on the chip in a central processor coupled to the processing elements through a global bus, the central processor processing data words which are wider than data words processed by the processing elements. 
     
     
       52. A method as claimed in  claim 49  further comprising processing encryption algorithms on the chip in a central processor coupled to the processing elements through a global bus, the central processor processing data words which are wider than data words processed by the processing elements. 
     
     
       53. The multiplier as claimed in claim 41 wherein providing the multiplier segments operate as individual multipliers each individual multiplier is configured to operate as a first length by first length multiplier. 
     
     
       54. The multiplier as claimed in claim 41 wherein the wider multiplier is configured to operate as a first length by first length times a number of the plurality of multiplier segments multiplier. 
     
     
       55. The multiplier as claimed in claim 41 wherein the second word length is equal to the first length times a number of the plurality of multiplier segments. 
     
     
       56. The multiplier as claimed in claim 55 wherein the wider multiplier provides an output having a length equal to the first length plus the second length. 
     
     
       57. The multiplier as claimed in claim 41 wherein each of the multiplier segments is configured to receive a first operand word of the first length and a second operand word of the first length. 
     
     
       58. The multiplier as claimed in claim 57 wherein each of the multiplier segments comprises:
 a plurality of AND gates,   each AND gate configured to:
 receive a first bit from the first operand word, 
 receive a second bit from the second operand word, and 
 provide one of a set of partial products. 
   
     
     
       59. The multiplier as claimed in claim 58 wherein each of the multiplier segments comprises:
 a plurality of partial product adders, and   input selection circuitry configured to select the set of partial products as inputs to the partial product adders when operating as an individual multiplier, or a second set of inputs including partial products from an adjacent multiplier segment when concatenated.   
     
     
       60. The multiplier as claimed in claim 59 wherein each of the plurality of partial product adders comprises three stages, wherein the first and second stages comprise full adders and the third stage comprises a carry look-ahead adder. 
     
     
       61. The multiplier as claimed in claim 41 wherein each of the plurality of multiplier segments is configurable to operate as a 4 by 4 multiplier. 
     
     
       62. A multiplier circuit comprising:
 a plurality of multiplier segments, each receiving operand words of a first length; and   input selectors which select a first set of inputs when the multiplier segments operate as individual multipliers and a second set of inputs to concatenate the multiplier segments as a wider multiplier operating on operands of a second word length,   wherein at least one multiplier segment includes a gate configured to receive a select signal and a partial product signal from a neighboring multiplier segment, the select signal enabling the gate when the multiplier segments are concatenated to pass the partial product signal to a summation logic circuit, the select signal disabling the gate when the multiplier segments operate as individual multipliers to disable the passing of the partial product signal.   
     
     
       63. A multiplier as claimed in claim 62 wherein the gate is an AND gate, the select signal is logic 1 when the multiplier segments are concatenated, and the select signal is logic 0 when the multiplier segments operate as individual multipliers. 
     
     
       64. A multiplier circuit comprising:
 a plurality of multiplier segments, each receiving operand words of a first length; and   input selectors which select a first set of inputs when the multiplier segments operate as individual multipliers and a second set of inputs to concatenate the multiplier segments as a wider multiplier operating on operands of a second word length,   wherein at least one multiplier segment includes a plurality of gates each receiving a select signal and a respective one of a plurality of partial product signals from a neighboring multiplier segment, the select signal enabling the gates when the multiplier segments are concatenated to pass the partial product signals to a summation logic circuit, the select signal disabling the gates when the multiplier segments operate as individual multipliers to disable the passing of the partial product signals.   
     
     
       65. A multiplier as claimed in claim 64 wherein the plurality of gates are AND gates, the select signal is logic 1 when the multiplier segments are concatenated, and the select signal is logic 0 when the multiplier segments operate as individual multipliers. 
     
     
       66. A multiplier circuit comprising:
 a plurality of multiplier segments, each receiving operand words of a first length; and   input selectors which select a first set of inputs when the multiplier segments operate as individual multipliers and a second set of inputs to concatenate the multiplier segments as a wider multiplier operating on operands of a second word length,   wherein at least one multiplier segment includes a multiplexer receiving a select signal, a sum signal from a neighboring multiplier segment, and a partial product signal, the select signal enabling the multiplexer when the multiplier segments are concatenated to pass the sum signal to a summation logic circuit, the select signal enabling the multiplexer when the multiplier segments operate as individual multipliers to pass the partial product signal to the summation logic circuit.   
     
     
       67. A multiplier circuit comprising:
 a plurality of multiplier segments, each receiving operand words of a first length; and   input selectors which select a first set of inputs when the multiplier segments operate as individual multipliers and a second set of inputs to concatenate the multiplier segments as a wider multiplier operating on operands of a second word length,   wherein at least one multiplier segment includes a plurality of multiplexers each receiving a select signal, a respective one of a plurality of sum signals from a neighboring multiplier segment, and a respective one of a plurality of partial product signals, the select signal enabling the multiplexers when the multiplier segments are concatenated to pass the sum signals to a summation logic circuit, the select signal enabling the multiplexers when the multiplier segments operate as individual multipliers to pass the partial product signals to the summation logic circuit.   
     
     
       68. An electronic encryption device as claimed in claim 45, in which said processor means comprises a memory which is shared between adjacent processing elements of the array of processing elements for transfer of data between adjacent processing elements of the array.