Packet-parallel high performance cryptography systems and methods

• US 7,512,780 B1
• Filed: 06/10/2002
• Issued: 03/31/2009
• Est. Priority Date: 08/31/2001
• Status: Expired due to Fees

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: BBN Technologies (Rtx Corporation), Verizon Corporate Services Group Incorporated (Verizon Communications Inc.)
• Inventors: Milliken, Walter Clark
• Primary Examiner(s): Simitoski; Michael J
• Application Number:
  US10/166,547
• Time in Patent Office: 2,486 Days
• Field of Search: 713/153, 713/189, 714/4, 710/57, 708/256
• US Class Current: 713/153
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 9/06 the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators

Abstract

A cryptographic system (500) includes cryptographic sub-units (510) and associated input buffers (520) connected to a scheduler (530) and a reassembler (540). The scheduler (530) receives packets, where each of the packets includes one or more data blocks, and assigns each of the packets to one of the sub-units (510). The input buffers (520) temporarily store the packets from the scheduler (530). Each of the sub-units (510) performs a cryptographic operation on the data blocks from the associated input buffer (520) to form transformed blocks. The reassembler (540) receives the transformed blocks from the sub-units (510), reassembles the packets from the transformed blocks, and outputs the reassembled packets in a same order in which the packets were received by the scheduler (530).

Claims

1. A cryptographic system, comprising:

a plurality of input buffers configured to temporarily store a plurality of packets, each of the packets including one or more data blocks;

a plurality of cryptographic sub-units associated with the input buffers, each of the sub-units being configured to perform a cryptographic operation on the data blocks from the associated input buffer to form transformed blocks;

a scheduler configured to assign each of the packets to one of the sub-units, as an assigned sub-unit, based on an amount of data stored in the associated input buffer; and

a reassembler configured to;

receive the transformed blocks from the assigned sub-units;

reassemble the packets from the transformed blocks to form reassembled packets, and

output the reassembled packets in a same order in which the packets arrived at the scheduler.

2. The system of claim 1, wherein the cryptographic operation includes one of an encryption operation and a decryption operation.

3. The system of claim 1, wherein the scheduler is further configured to:

determine whether the packet will fit in the associated input buffer of the assigned sub-unit, and

delay storing of the packet in the associated input buffer until the packet is determined to fit in the associated input buffer.

4. The system of claim 1, wherein each of the sub-units has a same constant throughput and latency.

5. The system of claim 4, wherein the scheduler is configured to:

identify one of the input buffers, as an identified input buffer, with a least amount of stored data, and

assign a next one of the packets to the sub-unit associated with the identified input buffer.

6. The system of claim 1, wherein the reassembler is configured to:

receive one of the transformed blocks for one of the packets from the assigned sub-unit,

determine whether the transformed block is a first data block in the packet, and

store the transformed block at an end of an output queue when the transformed block is the first data block in the packet.

7. The system of claim 6, wherein the reassembler is further configured to:

determine whether the transformed block is also a last data block in the packet when the transformed block is the first data block in the packet, and

mark the packet as complete when the transformed block is the last data block in the packet.

8. The system of claim 6, wherein the reassembler is further configured to:

determine whether the transformed block is a last data block in the packet when the transformed block is not the first data block in the packet, and

attach the transformed block to an end of the packet when the transformed block is not the last data block in the packet.

9. The system of claim 6, wherein the reassembler is further configured to:

determine whether the transformed block is a last data block in the packet when the transformed block is not the first data block in the packet,

attach the transformed block to an end of the packet when the transformed block is the last data block in the packet, and

mark the packet as complete.

10. The system of claim 1, wherein the scheduler is further configured to perform an arbitration if more than one of the sub-units qualifies for assignment of a packet.

11. A cryptographic system, comprising:

means for receiving a plurality of packets, each of the packets including one or more data blocks;

means for assigning each of the packets to one of a plurality of input buffers based on an amount of data stored in the input buffer;

means for performing a cryptographic operation on the data blocks from each of the input buffers to form transformed blocks;

means for reassembling the packets from the transformed blocks to form reassembled packets; and

means for outputting the reassembled packets in a same order in which the packets were received.

12. A cryptographic method, comprising:

receiving a plurality of packets, each of the packets including one or more data blocks;

assigning each of the packets to one of a plurality of input buffers, as an assigned input buffer, based on an amount of data stored in the input buffer;

storing the data blocks in the assigned input buffers;

performing a cryptographic operation on the data blocks from each of the input buffers to form transformed blocks;

reassembling the packets from the transformed blocks to form reassembled packets; and

outputting the reassembled packets in a same order in which the packets were received.

13. The method of claim 12, wherein the performing a cryptographic operation includes:

performing one of an encryption operation and a decryption operation.

14. The method of claim 12, wherein the storing the data blocks includes:

determining whether all the data blocks of a packet will fit in the assigned input buffer, and

delaying the storing of the data blocks in the assigned input buffer until all the data blocks of the packet are determined to fit in the assigned input buffer.

15. The method of claim 12, wherein the assigning each of the packets includes:

identifying one of the liquid buffers, as an identified input buffer, with a least amount of stored data, and

assigning a next one of the packets to the identified input buffer.

16. The method of claim 12, wherein the outputting the reassembled packets includes:

outputting the reassembled packets in a single packet stream.

17. The method of claim 12, wherein the reassembling the packets includes:

receiving one of the transformed blocks for one of the packets,

determining whether the transformed block is a first data block in the packet, and

storing the transformed block at an end of an output queue when the transformed block is the first data block in the packet.

18. The method of claim 17, wherein the reassembling the packets further includes:

determining whether the transformed block is also a last data block in the packet when the transformed block is the first data block in the packet, and

marking the packet as complete when the transformed block is the last data block in the packet.

19. The method of claim 17, wherein the reassembling the packets further includes:

determining whether the transformed block is a last data block in the packet when the transformed block is not the first data block in the packet, and

attaching the transformed block to an end of the packet when the transformed block is not the last data block in the packet.

20. The method of claim 17, wherein the reassembling the packets further includes:

determining whether the transformed block is a last data block in the packet when the transformed block is not the first data block in the packet,

attaching the transformed block to an end of the packet when the transformed block is the last data block in the packet, and

marking the packet as complete.

21. The method of claim 12, wherein assigning each of the packets to one of the input buffers further comprises performing an arbitration if more than one of the sub-units qualifies for assignment of a packet.

22. A network device, comprising:

a plurality of input ports configured to receive a plurality of packets;

a plurality of output ports configured to transmit the packets; and

a packet processing system configured to transmit the packets from the input ports to the output ports, the packet processing system comprising;

a plurality of input buffers configured to temporarily store the packets, each of the packets including one or more data blocks,

a plurality of cryptographic sub-units associated with the input buffers, each of the sub-units being configured to perform a cryptographic operation on the data blocks from the associated input buffer to form transformed blocks,

a scheduler configured to assign each of the packets to one of the sub-units based on an amount of data stored in the associated input buffer, and

a reassembler configured to;

receive the transformed blocks from the sub-units,

reassemble the packets from the transformed blocks, and

output the reassembled packets in a same order in which the packets arrived at the scheduler.