Encryption processor with shared memory interconnect

BACKGROUND OF THE INVENTION

0001Before the advent of the Internet, corporate data networks typically consisted of dedicated telecommunications lines leased from a public telephone company. Since the hardware implementation of the data networks was the exclusive property of the telephone company, a regulated utility having an absolute monopoly on the medium, security was not much of a problem; the single provider was contractually obligated to be secure, and the lack of access to the switching network from outside made it more or less resistant to external hacking and tampering.

0002Today, more and more enterprises are discovering the value of the Internet which is currently more widely deployed than any other single computer network in the world and is therefore readily available for use by a multi-national corporate network. Since it is also a consumer-level product, Internet access can usually be provided at much lower cost than the same service provided by dedicated telephone company network. Finally, the availability of the Internet to the end user makes it possible for individuals to easily access the corporate network from home, or other remote locations.

0003The Internet however, is run by public companies, using open protocols, and in-band routing and control that is open to scrutiny. This environment makes it a fertile proving ground for hackers. Industrial espionage is a lucrative business today, and companies that do business on the Internet leave themselves open to attack unless they take precautions.

0004Several standards exist today for privacy and strong authentication on the Internet. Privacy is accomplished through encryption/decryption. Typically, encryption/decryption is performed based on algorithms which are intended to allow data transfer over an open channel between parties while maintaining the privacy of the message contents. This is accomplished by encrypting the data using an encryption key by the sender and decrypting it using a decryption key by the receiver (sometimes, the encryption and decryption keys are the same).

0000Types of Encryption Algorithms

0005Encryption algorithms can be classified into public-key and secret key algorithms. In secret-key algorithms, both keys are secret whereas in public-key algorithms, one of the keys is known to the general public. Block ciphers are representative of the secret-key cryptosystems in use today. Usually, for block ciphers, the encryption key is the same as the decryption key. A block cipher takes a block of data, typically 32-128 bits, as input and produces the same number of bits as output. The encryption and decryption are performed using a key, anywhere from 56-128 bits in length. The encryption algorithm is designed such that it is very difficult to decrypt a message without knowing the key.

0006In addition to block ciphers, Internet security protocols also make heavy use of public-key algorithms. A public key cryptosystem such as the Rivest, Shamir, Adelman (RSA) cryptosystem described in U.S. Pat. No. 5,144,667 issued to Pogue and Rivest uses two keys, only one of which is made public. Once someone publishes a key, anyone may send that person a secret message using that key. However, decryption of the message can only be accomplished by use of the secret key. The advantage of such public-key encryption is secret keys do not need to be distributed to all parties of a conversation beforehand. In contrast, if only secret-key encryption were used, multiple secret keys would have to be generated, one for each party intended to receive the message, and each secret key would have to be privately communicated. Attempting to communicate the secret key privately results in the same problem as in sending the message itself using only secret-key encryption; this is called the key distribution problem.

0007Key exchange is another application of public-key techniques. In a key exchange protocol, two parties can agree on a secret key even if their conversation is intercepted by a third party. The Diffie-Hellman exponential key exchange, described in U.S. Pat. No. 4,200,770, is an example of such a protocol.

0008Most public-key algorithms, such as RSA and Diffie-Hellman key exchange, are based on modular exponentiation, which is the computation of α^xmod p. This expression means “multiply α by itself x times, divide the answer by p, and take the remainder.” This computation is very expensive to perform, for the following reason. In order to perform this operation, many repeated multiplications and divisions are required, although techniques such as Montgomery's method, described in “Modular Multiplication Without Trial Division,” from Mathematics of Computation, Vol. 44, No. 170 of April 1985, can reduce the number of divisions required. In addition, the numbers used are very large (typically 1024 bits or more), so the multiply and divide instructions found in common CPUs cannot be used directly. Instead, special algorithms that break down the large multiplications and divisions into operations small enough to be performed on a CPU must be used. These algorithms usually have a run time proportional to the square of the number of machine words involved. These factors result in multiplication of large numbers being a very slow operation. For example, a Pentium® can perform a 32×32-bit multiply in 10 clock cycles. A 2048-bit number can be represented in 64 32-bit words. A 2048×2048-bit multiply requires 64×64 separate 32×32-bit multiplications, which takes 40960 clocks on the Pentium. An exponentiation with a 2048-bit exponent requires up to 4096 multiplications if done in the normal way, which requires about 167 million clock cycles. If the Pentium is running at 166 MHZ, the entire operation requires roughly one second. This example does not consider the time required to perform the divisions, either! Clearly, a common CPU such as a Pentium cannot expect to do key generation and exchange at any great rate.

0009Because public-key algorithms are so computationally intensive, they are typically not used to encrypt entire messages. Instead, private-key cryptosystems are used for message transfer. The private key used to encrypt the message, called the session key, is chosen at random and encrypted using a public key. The encrypted session key, as well as the encrypted message, are then sent to the other party. The other party uses its secret key to decrypt the session key, at which point the message may be decrypted using the session key. A different session key is used for each communication, so that if one session key is ever broken, only the one message encrypted with it may be read. This public-key/private-key method can also be used to protect continuous communications, such as interactive terminal sessions that never terminate in normal operation. In this case, the session key is periodically changed (e.g. once an hour) by repeating the public-key generation technique. Again, frequent changing of the session key limits the amount of data compromised if the encryption is broken.

0000Prior Art

0010Network-level encryption devices, allowing access to corporate networks using a software-based solution are experiencing widespread usage. Products such as Raptor Eagle Remote and others perform encryption entirely in software. The software limits the encryptor's throughput. Session key generation using public-key techniques may take several minutes. For this reason, session keys are not re-generated as often as some people would like. However, software does have the advantage that the encryption algorithms are easily changed in response to advances in the field.

0011Other devices use a combination of hardware and software. For example, the Northern Telecom (now Entrust) Sentinel X.25 encryption product uses a DES chip produced by AMD to perform the DES secret-key encryption. Hardware implementations of DES are much faster, since DES was designed for efficient implementation in hardware. A transposition that takes many CPU instructions in software can be done using parallel special-purpose lookup tables and wiring.

0012The Sentinel also makes use of a Motorola DSP56000 processor to perform the public-key operations. At the time, the single-cycle multiplication ability of the DSP made this approach significantly faster than implementing the public-key algorithms on regular CISC microprocessors.

0013Most hardware encryption devices are severely limited in the number of algorithms that they can implement. For example, the AMD chip used in the Sentinel performs only DES. More recent devices, from Hi/Fn can perform DES and RC4. However, if you need to implement either RC5 or IDEA, then you would need to use another product.

SUMMARY OF THE INVENTION

0014A preferred high-performance programmable network encryption device, integrated into a single chip, is a parallel-pipelined processor system whose instruction set is optimized for common encryption algorithms. The present invention realizes the advantages of both hardware and software approaches. Since the processor is a programmable processor, any encryption algorithm may be implemented, contrary to a hardware implemented encryption processor which is dedicated to executing only one algorithm. However, the processor's architecture permits parallel computations of a nature useful for encryption, so its performance more closely approximates that of a dedicated hardware device.

0015In accordance with a preferred implementation of the invention, an electronic encryption device comprises an array of processing elements. Each processing element comprises an instruction memory for storing a round of an encryption algorithm, the round comprising a sequence of instructions. The processing element also includes a processor for implementing the round from the instruction memory and data storage for storing encryption data operands and encrypted data resulting from implementing the round. Each processing element of the array implements one of the rounds and transfers results to successive processing elements such that the array of processing elements implements successive rounds of the encryption algorithm in a processing element pipeline.

0016In a preferred embodiment, 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. The shared data storage is preferably comprised of dual port memories but may also comprise shared registers.

0017The preferred processing element comprises a control unit and an ALU. The control unit, ALU, instruction memory and data storage, including local data memory and shared data memory, are connected to a local processing element bus. The local bus is 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 memory. The switch permits either independent simultaneous operation on the two local bus segments or a communication between the two bus segments. Each processing element further comprises a multiplier for performing multiplication operations within the processing element.

0018The preferred encryption device further comprises 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. A central processor is coupled to the global bus for processing data words which are wider than data words processed by the processing elements. The multipliers of the plural processing elements may be adapted for concatenation as segments of a wider multiplier used by the central processor. Preferably, 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.

0019Preferably, the central processor comprises a novel adder. In the adder, each of plural adder segments has a carry output and a sum output and each of the adder segments processes a segment of each of two operands. Selectors 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. Selectors also select each sum output as an operand input to the same adder segment. Accordingly, so long as any carry results in an adder cycle, the sum output of an adder is fed back to its input, and the adder segment receives a carry input generated as a carry output from a preceding segment in a preceding cycle.

0020Preferably, each processing element performs a modular adjust operation to compute M mod N without using a divide circuit. Each processing element also performs a modulo add/subtract operation to compute A±B mod N. Further, each processing element performs a modulo multiply operation to compute A×B mod N.

BRIEF DESCRIPTION OF THE DRAWINGS

0021The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

0022<figref idref="DRAWINGS">FIGS. 1A and 1B</figref> are block diagrams of potential applications of the present invention.

0023<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram of an encryption chip embodying the present invention.

0024<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram of a processing element in the encryption chip of <figref idref="DRAWINGS">FIG. 2</figref>.

0025<figref idref="DRAWINGS">FIG. 4</figref> illustrates a preferred chip layout of the circuitry of <figref idref="DRAWINGS">FIGS. 2 and 3</figref>.

0026<figref idref="DRAWINGS">FIG. 5</figref> illustrates the processing element of <figref idref="DRAWINGS">FIG. 3</figref> redrawn to correspond to the layout of <figref idref="DRAWINGS">FIGS. 4</figref> and to illustrate the PE local bus and global bus connections.

0027<figref idref="DRAWINGS">FIG. 6</figref> illustrates an adder circuit used in the PK ALU of <figref idref="DRAWINGS">FIG. 2</figref>.

0028<figref idref="DRAWINGS">FIG. 7</figref> illustrates a full adder symbol used in a multiplier of the PK ALU.

0029<figref idref="DRAWINGS">FIG. 8</figref> illustrates processing in the first stage of a 4×4 multiplier using full adders.

0030<figref idref="DRAWINGS">FIG. 9</figref> illustrates three stages of the 4×4 multiplier.

0031<figref idref="DRAWINGS">FIG. 10</figref> illustrates the adders of a wide multiplier with the adders of the 4×4 multiplier overlaid thereon.

0032<figref idref="DRAWINGS">FIG. 11</figref> is a block diagram of a 4×4 multiplier adapted to be concatenated with like multipliers in a wide word length multiplier of <figref idref="DRAWINGS">FIG. 10</figref>.

0033<figref idref="DRAWINGS">FIG. 12</figref> illustrates a conventional implementation of an 8-bit adder using full adders.

0034<figref idref="DRAWINGS">FIG. 13</figref> is a conventional implementation of a carry lookahead adder.

0035<figref idref="DRAWINGS">FIG. 14</figref> is a block diagram illustration of a DES encryption round.

0036<figref idref="DRAWINGS">FIGS. 15A-D</figref> are functional diagrams illustrating modular add, subtract, adjust and combination of all three operations according to embodiments of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

0037The encryption chip of the present invention may be programmed to perform common data encryption and decryption algorithms on one or more data streams in any application. The principal purpose of the encryption chip is to perform high speed data encryption using algorithms that are expected to be in use on the Internet, at data rates of 100-2000 Mbps.

0038Example applications are illustrated in <figref idref="DRAWINGS">FIGS. 1A and 12</figref>. In <figref idref="DRAWINGS">FIG. 1A</figref>, data from a source <b>22</b> is encrypted in an encryption chip <b>24</b> before the data is passed into a public network <b>26</b>. The data is then decrypted in encryption chip <b>28</b> before being forwarded to a destination <b>30</b>. In one embodiment, the source and the destination are themselves networks such as local area networks. In that case, the encryption chips provide a secure path between the local area networks and the public network <b>26</b>.

0039In a link encryption application illustrated in <figref idref="DRAWINGS">FIG. 1B</figref>, data transferred within each link between routers is encrypted. In that case, encrypted data received at a router <b>32</b> between links must first be decrypted in an encryption chip <b>34</b>, and the data is re-encrypted in accordance with the encryption algorithm of the next link in an encryption chip <b>36</b>.

0040Three main secret-key block encryption algorithms are in common use today: DES, RC5 and IDEA. The first two algorithms are standard Internet Protocol SECurity IPSEC standard algorithms. IDEA is the algorithm used by PGP, a popular email encryption program.

0041Typically, block algorithms consist of a number of rounds; each round is a sequence of operations in an encryption algorithm. Anywhere from 8-32 rounds are required to completely implement an encryption algorithm. The operations performed by each round are often the same, although they need not be. In software, each round is implemented with a few machine instructions. In hardware, each round is implemented with dedicated circuitry. The hardware is typically pipelined, with each round being implemented in its own pipeline stage.

0042<figref idref="DRAWINGS">FIG. 2</figref> illustrates an integrated chip solution, henceforth referred to as the encryption chip, according to an embodiment of the present invention. Although the encryption chip implies the chip can perform encryption, it should be noted that the chip is also designed to perform decryption and message digest functions as well.

0043Data enters the encryption chip through an input stage <b>40</b>, which receives network data, typically as a serial bit stream. Ethernet, ATM or any other serialized format may be used. The input stage converts the serial data stream to block-aligned data suitable for processing as an input to an encryption/decryption pipeline. The size of the input blocks is programmable. In the preferred embodiment illustrated in <figref idref="DRAWINGS">FIG. 2</figref>, the pipeline is made up of a plurality of processing elements <b>37</b> arranged in a linear array, each containing an instruction memory, a register file, an ALU, local and shared data memory, and control circuitry. Each of the processing elements is designed to process 32-bit wide data words. The encrypted data is taken from the last processing element in the pipeline into an output stage <b>42</b>, which converts the block data back into a serial stream format and forwards the data over the network or to a local destination.

0044Data can be transferred among non-adjacent processing elements and/or other elements within the encryption ship via a global data bus <b>38</b>. Also connected to the global data bus <b>38</b> is I/O communication logic <b>54</b>, which allows communication with a host CPU (not shown). Host CPU communication is required to program the encryption chip prior to use. Global random access memory (RAM) <b>44</b> is also connected to the global data bus <b>38</b>, allowing global communication among the processing elements. A control CPU <b>52</b> synchronizes the operations of the encryption pipeline processors. This CPU may be implemented using any available embedded CPU core such as MIPS, ARM or ARC. Furthermore, to allow processing of algorithms which utilize very wide operands such as public-key encryption algorithms, a public-key (PK) core processor <b>46</b> is connected to the control CPU <b>52</b>. The PK core includes a register file <b>48</b> consisting of 8-16 512-bit wide registers as well as a PK ALU <b>50</b>. The PK core processor can make data transfers to and from the global RAM <b>44</b> over a 512-bit bus in one system clock cycle. 512-bit operands are processed in the ALU <b>50</b>, typically in 2-32 clock cycles. The PK core ALU <b>50</b> is a coprocessor controlled by the control CPU <b>52</b>, performing only arithmetic and logic operations along with loads and stores. Other instructions necessary for implementing PK algorithms can be executed within the control CPU <b>52</b>.

0045The encryption chip implements the code for each round of a secret key algorithm in a separate processing element of the pipeline. Once computed upon, data from one PE is transferred to the next PE where the next round is implemented. The first PE is then free to process an encryption round for the next block of data coming in. The pipeline process continues for the remaining PE's. The time required to encrypt a block using this architecture is therefore equal to the time required to encrypt one round.

0046Many block algorithms use one set of operations to encrypt the data, and a separate set of operations to expand the key. Key expansion is the process of transforming a relatively small key (56-128 bits) into a larger number (512 bits or more) with statistically random properties. This expanded key is distributed into smaller subkeys, where a different portion of the expanded key is used for each round. It is important to note that the expanded key does not change with the data. Therefore, since it is not in the critical path, it can be pre-computed and stored in memory. The sample code discussed later assumes that key information has been pre-computed and stored in the local data memories of each PE.

0047The basic application of a block algorithm transforms a block of plaintext (unencrypted information) into a similar-sized block of ciphertext (encrypted information) and vice-versa. This operating mode is known as electronic codebook (ECB) mode. Due to its many inherent security weaknesses, methods of introducing feedback into the encryption by cycling some of the basic output back into the input are commonly used. The encryption chip uses the global data bus <b>38</b> to perform cipher feedback (CFB). In ECB mode, a new block of data can be encrypted once per pipeline cycle, which can be 10-100 instructions. However, in CFB mode, each datum must pass through the pipeline multiple times. This mode substantially reduces throughput on a single channel. However, peak performance can be achieved by encrypting multiple data channels, interleaved in the pipeline.

0048A block diagram of one individual processing element PE according to an embodiment of the present invention is shown in <figref idref="DRAWINGS">FIG. 3</figref>. The processing element <b>37</b>, consists of an ALU <b>56</b> operating on 32-bit words from a register file <b>58</b> made up of 8-16 32-bit registers. The register file <b>58</b> and ALU <b>56</b> are controlled by a control unit <b>60</b> which decodes instructions from a processing element instruction memory <b>62</b>. Each processing element instruction memory stores at least one round of an encryption algorithm, where a round is defined as a sequence of instructions in an encryption algorithm. The PE data memory space accessible by each processing element is divided into four areas: a local PE memory <b>64</b> (in <figref idref="DRAWINGS">FIG. 3</figref>, designated as PE_nlocal memory), a shared memory <b>66</b> (in <figref idref="DRAWINGS">FIG. 3</figref>, designated as PE_n,n−1shared memory shared between the n-th and n−1-th processing element), and a second shared memory <b>68</b> (in <figref idref="DRAWINGS">FIG. 3</figref>, designated as PE_n+1,nshared memory shared between the n+1-st and n-th processing element), and the global memory <b>44</b> as described with reference to <figref idref="DRAWINGS">FIG. 2</figref>, which is accessible to all PEs. All of these memories are mapped into the address space of a processing element, say the n-th processing element. No special instructions are required to access any type of memory; all memories are accessible by all memory access instructions.

0049The memories <b>66</b> and <b>68</b> of a processing element are dual port SRAMs and are shared with the PE of the previous and next pipe stage, respectively. Note that a PE's next-neighbor memory is the same as the next PE's previous-neighbor memory.

0050These dual ported SRAMs are used to propagate data through the pipeline stages. One processing element writes data to be transferred into its associated next-neighbor shared memory. Then the next-neighbor processing element reads the stored data from its previous-neighbor shared memory, which as described before, is one and the same as the previous processing element's next-neighbor shared memory. Since the memories are dual-ported, there are no timing restrictions on accesses. Synchronization of accesses is performed using static scheduling of machine instructions by the software author or compiler. Furthermore, since the global bus is not used for communication between adjacent PEs, the PEs may all communicate concurrently.

0051The global memory <b>44</b> is connected to the global communication bus. Only one processing element is allowed to access the global memory <b>44</b> at any one time. This memory is used to pass data between non-adjacent processing elements, for example, during feedback encryption algorithms and can serve as supplemental storage for individual processing elements.

0052The PE instruction memory <b>62</b> has an instruction set resembling that of a modern RISC processor integer unit. The instruction set is more or less orthogonal in that any register can be used as an operand to any instruction. No floating-point or memory management support need be provided, since neither are useful in encryption. However, the instruction set contains the following useful enhancements: a modular addition/subtraction instruction, a modular multiplication instruction and a modulo adjust instruction.

0053The modular addition/subtraction instruction computes A±B mod N (the number “M mod N” is the remainder when M is divided by N). <figref idref="DRAWINGS">FIGS. 15A through 15D</figref> illustrate the combination of the modular add, subtract and adjust into one 3-in-1 modulo arithmetic unit.

0054<figref idref="DRAWINGS">FIG. 15A</figref> illustrates the modular add operation. If the two numbers to be added, A and B, are both less than N, then their sum from adder <b>120</b> can be reduced modulo N by subtracting N in subtractor <b>122</b>, and then selecting through the multiplexer <b>124</b> either the output of the subtractor or the original number, depending on the sign of the difference. Similarly, in the case of a modular subtract operation as shown in <figref idref="DRAWINGS">FIG. 15B</figref>, if the two numbers A and B are less than N, then their difference modulo N can be computed by adding N in adder <b>126</b> if the difference from subtractor <b>128</b> is negative or by selecting the difference through multiplexor <b>130</b> if the difference is positive. Note that both the modulo add and modulo subtract do not require division. However, they do require two additions in series (one to compute the sum/difference, and one to reduce modulo N). If the double-addition impacts the critical path, then the reduction modulo N can be encoded as a separate instruction, which is called the “modulo adjust” instruction.

0055The modulo adjust instruction, illustrated in <figref idref="DRAWINGS">FIG. 15C</figref>, computes M mod N, given that M is either a sum or a difference of A and B, both already reduced to mod N. If M is negative, the logic <b>132</b> causes adder/subtractor <b>134</b> to add N to M to produce the result through multiplexor <b>136</b>. If M is positive, then logic <b>132</b> causes subtraction of N, and returns the difference if it is positive or M if the difference is negative. This instruction may be used in conjunction with sum and difference instructions to render the modular addition/subtraction instruction unnecessary.

0056In <figref idref="DRAWINGS">FIG. 15D</figref>, the 3-in-1 arithmetic unit combines the modulo add, modulo subtract and modulo adjust into a single unit which is implemented within each processing element. Under control of logic <b>144</b> responding to an instruction (modular add, subtract or adjust) and most significant bit (MSB) sign inputs, adder/subtractor <b>138</b> serves the function of either of devices <b>120</b> and <b>128</b>, and adder/subtractor <b>140</b> serves the function of any of devices <b>122</b>, <b>126</b> and <b>134</b>. Multiplexor <b>142</b> corresponds to devices <b>124</b>, <b>130</b> and <b>136</b>. In the modulo adjust operation, M is applied to the A input and the B input is set at zero. This combined unit is most efficient in area at the cost of speed. This combined unit is also useful in implementing Montgomery's method for modular multiplication without trial division, “Modular Multiplication Without Trial Division,” by Peter L. Montgomery, Mathematics of Computation, Vol. 44, No. 170, April 1985, pages 519-521.

0057Although modular addition and subtraction can be performed on conventional processors using only 2-3 instructions, the inclusion of these instructions as special functions of the encryption chip instruction set offers a minor speedup for the specific case of encryption algorithms.

0058The modular multiplication instruction computes A*B mod N. The multiplier used for this instruction will be described in more detail below. The encryption chip provides a full modular multiply instruction, for reasons which will become clear below.

0059Table 1 gives a representative sample of the instruction set of the PEs to be used in subsequent examples. Other conventional RISC instructions may also be implemented.

0060<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 1</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Sample Instruction Set</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="147pt" align="left" /><tbody valign="top"><row><entry /><entry>Instruction</entry><entry>Description</entry></row><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row><row><entry /><entry>load rn,addr</entry><entry>Load register n with memory</entry></row><row><entry /><entry>store rn,addr</entry><entry>Store register n in memory</entry></row><row><entry /><entry>xor r1, r2, r3</entry><entry>r1 = r2 xor r3</entry></row><row><entry /><entry>add r1, r2, r3</entry><entry>r1 = r2 + r3</entry></row><row><entry /><entry>rol r1, r2, r3</entry><entry>r1 = r2 <<< r3 (<<< is the Java operator for a </entry></row><row><entry /><entry /><entry>rotate instruction. For a 32-bit operand, </entry></row><row><entry /><entry /><entry>bit 31 rotates to bit position 0)</entry></row><row><entry /><entry>xor r1, addr</entry><entry>r1 = r1 xor memory[addr]r1 = r1</entry></row><row><entry /><entry>add r1, addr</entry><entry>+ memory[addr]</entry></row><row><entry /><entry>rol r1, addr</entry><entry>r1 = r1 <<< memory[addr]</entry></row><row><entry /><entry>moda r1, r2</entry><entry>Modulo adjust: r1 = r1 mod r2, where r1</entry></row><row><entry /><entry /><entry>is result of modular add or multiply</entry></row><row><entry /><entry>moda r1, addr</entry><entry>r1 = r1 mod memory[addr</entry></row><row><entry /><entry>mul r1, r2, r3</entry><entry>Multiply: r1 = r2 × r3, performed in 32 bits.</entry></row><row><entry /><entry>mulm</entry><entry>Modular multiply: r1 = r2 × r3 mod r4.</entry></row><row><entry /><entry>r1, r2, r3, r4</entry><entry /></row><row><entry /><entry>Jump label</entry><entry>Transfer control unconditionally to label</entry></row><row><entry /><entry>sync label</entry><entry>Pipeline sync: wait until all PEs have arrived</entry></row><row><entry /><entry /><entry>at a “sync” instruction, then branch to label</entry></row><row><entry /><entry>Dbra rn, label</entry><entry>rn = rn − 1; if rn ! = 0 then jump to label</entry></row><row><entry /><entry>cbra r1 cond</entry><entry>Compare and branch: compare r1 and r2,</entry></row><row><entry /><entry>r2, label</entry><entry>and branch to label if condition is true.</entry></row><row><entry /><entry /><entry>“Cond” is one of ==, !=, <, >, <= or >=.</entry></row><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Layout Issues

0061A general layout of the encryption chip is illustrated in <figref idref="DRAWINGS">FIG. 4</figref>, assuming 16 processing elements and a 512-bit wide public key PK core unit. The PK core word width of 512 bits was chosen due to its layout convenience. A width of 1024 bits for example, would require more silicon area but would also double performance.

0062The individual elements can be compared to the elements of <figref idref="DRAWINGS">FIGS. 2 and 3</figref>. Sixteen of the processing elements are linearly arranged in a column in the large region of the layout to the lower left, one being shown in detail. The shared multiplier element <b>70</b> is shown associated with the illustrated processing element. As previously described, a 32×32 multiplier segment <b>70</b> is associated with each processing element for performing 32-bit multiplications within the respective processing elements. Alternatively, the multiplier elements <b>70</b> can be concatenated to serve as a wide 512×32 bit multiplier for the public-key ALU <b>50</b>. The public-key PK ALU <b>50</b> is located to the right of the secret-key SK elements, made up of the processing elements as described above. Next to the PK ALU is the PK register file <b>48</b>. Together, the PK ALU <b>50</b> and the PK register file <b>48</b> make up the PK processing core, identified in <figref idref="DRAWINGS">FIG. 2</figref> as <b>46</b>. To the right of the PK core is located the global memory (RAM) <b>44</b>. Along the top of the chip are the control CPU <b>52</b>, the communication logic <b>54</b> and the input and output processing blocks <b>40</b> and <b>42</b>. The global data bus <b>38</b> links the SK elements, the PK core <b>46</b>, the global RAM <b>44</b>, the communication logic <b>54</b> and the control CPU <b>52</b>.

0063The layout of a typical processing element with the local bus connections is shown in <figref idref="DRAWINGS">FIG. 5</figref>. All components of a processing element may communicate via a local processing element data bus <b>72</b>, which handles all the memory—register transfers. Note that the next-neighbor shared PE memory <b>68</b> is laid out in line with the other elements of the illustrated processing element, whereas, the previous-neighbor shared PE memory <b>66</b> is laid out in line with the elements of the previous-neighbor processing element. For programming and testing purposes, all PE memories are accessible from the global bus <b>38</b>. A switch <b>74</b> normally disconnects the local bus <b>72</b> from the global bus <b>38</b> but may be selectively closed to enable data transfer between the local RAM <b>64</b> and the global RAM <b>44</b>. Another switch <b>76</b> allows the local bus <b>72</b> to be segmented into independent segments such that the control unit <b>60</b> can read instructions from the RAM <b>62</b> simultaneously with transfer of data on the bus <b>72</b>. As such, operations within the processing element may be pipelined with one instruction being processed in the control unit while a prior instruction is executed in the PE ALU <b>56</b>. During execution of encryption code, switches <b>74</b> and <b>76</b> are normally open, so that instruction fetches from the instruction RAM may proceed concurrently with data fetches from the data memories and register file.

0064Many multiprocessor architectures have been proposed. Most of them are designed for general-purpose multiprocessing, so communication between processing elements is usually done using a switching matrix that can be dynamically configured to switch data from any one PE to any other. These switch designs are extremely complex. Since they are not required for encryption, an embodiment of the present invention uses a simpler linear arrangement of the PEs with much less switching circuitry.

0065In addition, the use of shared memory as the interconnect technique rather than I/O ports as documented in the literature produces a much simpler and more powerful programming model. Consider two PEs, A and B, connected with a single 32-bit I/O port. In order for A to transfer multiple words of data to B, A must write each word to the I/O port and wait for B to read it. In contrast, if A and B are connected by a shared memory large enough to hold all words of the communication, then A may write out its data without waiting for B to read any. Furthermore, PE B has the freedom to read the words out in any order, or to pick and choose from the data as required by the job at hand. Finally, it should be noted that if some of the shared memory is not required for communication, then it may be used as an extension of the local memory to provide additional local work space.

0000Public Key Support

0066Efficient public-key encryption requires efficient modular exponentiation, provided by the public-key co-processor. This unit comprises the following items: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0067">PK register file <b>48</b>, consisting of 16 512-bit wide registers</li><li id="ul0002-0002" num="0068">PK 512×32-bit multiplier <b>70</b> made up of concatenated SK multiplier elements (this unit can perform a 512×512 multiply in only 32 clock cycles)</li><li id="ul0002-0003" num="0069">PK 512-bit adder ALU <b>50</b> which can perform addition in 2-16 cycles, typically no more than 2</li><li id="ul0002-0004" num="0070">global memory <b>44</b> organized for 512-bit parallel access from the PK coprocessor for loading and storing 512-bit words in a single clock cycle</li></ul></li></ul>

0071The PK core processor accelerates modular multiplication by performing it using 512-bit words. A 512×512 multiply operation using the PK unit of the invention would be implemented by performing 16 512×32 multiplies using the concatenated multiplier elements of the 16 processing elements described below. Assuming each multiply requires 2 clock cycles and 16 such multiplies are required, a 512×512 multiply would require 32 clock cycles and a 2048×2048 multiply would require only 512 clock cycles. The full modular exponentiation operation, requiring 4096 multiplies, would take a total of 2 million clock cycles. This represents an 80 fold improvement to the Pentium example discussed earlier. The performance improvement of PK algorithms is expected to be similar. This represents a significant performance gain compared to the prior art, and will enable more frequent changing of session keys, thereby increasing security.

0000512-bit Adder

0072Adders are not shared between the public key PK and secret key SK units. Rather, since addition and logic operations are common for both PK and SK, each unit has its own adder, so that operations may proceed concurrently.

0073Within the public-key PK ALU <b>50</b>, a 512-bit single cycle adder would be extremely complex and would add substantially to the critical path time of the ALU. Accordingly, the 512-bit adder in the ALU <b>50</b> is formed of 16 32-bit adders as illustrated in <figref idref="DRAWINGS">FIG. 6</figref>. In operation, the AND-gate <b>78</b> and multiplexer <b>80</b> initially apply two 32-bit operand segments to each of the 32-bit adders A0-A15. Note that the AND-gate <b>78</b> represents a 32-bit wide operation. Each 32-bit adder computes a 32-bit sum along with a carry output. The carry output of one adder is connected through a D flip-flop <b>79</b> to the carry input of the next. If a carry is generated in the first cycle, then it is clocked into the flip-flop where it is available as a carry input for the next clock cycle. Each sum is returned to one input of the same adder through a D flip-flop <b>81</b> and multiplexer <b>80</b>; the other input of the adder is held at zero using the AND gate <b>78</b> during successive clock cycles. The step of adding back the sum as a carry input for each adder is repeated as long as any carry results at the output of any of the 32-bit adders.

0074The operation of the 512-bit adder can be better understood with reference to the following example using four 4-bit binary words instead of the 16 32-bit words of the actual implementation.

0075<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="6"><colspec colname="1" colwidth="35pt" align="left" /><colspec colname="2" colwidth="21pt" align="char" /><colspec colname="3" colwidth="35pt" align="char" /><colspec colname="4" colwidth="21pt" align="char" /><colspec colname="5" colwidth="35pt" align="char" /><colspec colname="6" colwidth="70pt" align="left" /><thead><row><entry namest="1" nameend="6" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>Add:</entry><entry>1101</entry><entry>0110</entry><entry>1001</entry><entry>1011</entry><entry /></row><row><entry /><entry>0001</entry><entry>0101</entry><entry>1100</entry><entry>1011</entry><entry /></row><row><entry /><entry>01110</entry><entry>01011</entry><entry>10101</entry><entry>10110</entry><entry>carry-outs are 0,0,1,1</entry></row><row><entry /><entry>1110</entry><entry>1011</entry><entry>0101</entry><entry>0110</entry><entry /></row><row><entry /><entry>0</entry><entry>1</entry><entry>1</entry><entry>0</entry><entry>previous carries</entry></row><row><entry /><entry>1110</entry><entry>1100</entry><entry>0110</entry><entry>0110</entry><entry>final sum</entry></row><row><entry namest="1" nameend="6" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0076Note that two additions were required to arrive at the final sum where no further carries resulted. This is a typical case. Since the adder is being used for encryption operations, it is safe to assume that the numbers being added are more or less randomly distributed. The probability of a carry-out after the first add is quite high. However, the probability that a carry, added back in as a least significant bit, will result in another carry from the most significant bit is quite low. For this reason, most add operations are expected to take only two clock cycles.

0077Returning to the original problem of constructing a 512-bit adder, if a standard carry lookahead or carry bypass adder design were used, the critical path through the adder would be quite long, since the carry must propagate through some optimized circuitry that operates on 512 bits. This adder would be quite large and slow. In contrast, in one embodiment of the present invention, a 512-bit adder is composed of 32-bit adders, whose design is well-known today and has been well optimized. The maximum clock speed of an individual 32-bit adder is expected to be more than twice that of a 512-bit carry lookahead design. Thus, the two-or-more cycle adder according to the invention, would on average operate faster than a large 512-bit adder, while consuming less chip area.

0078In a worst case, as illustrated below, it is possible that 16 cycles would be required to completely compute the final sum without carries, for 16 32-bit adders implementation. Using the 4-bit binary word example once again for illustrative purposes:

0079<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="6"><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="21pt" align="char" /><colspec colname="3" colwidth="35pt" align="char" /><colspec colname="4" colwidth="21pt" align="char" /><colspec colname="5" colwidth="35pt" align="char" /><colspec colname="6" colwidth="77pt" align="left" /><thead><row><entry namest="1" nameend="6" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>Add:</entry><entry>1111</entry><entry>1111</entry><entry>1111</entry><entry>1111</entry><entry /></row><row><entry /><entry>0000</entry><entry>0000</entry><entry>0000</entry><entry>0001</entry><entry /></row><row><entry /><entry>01111</entry><entry>01111</entry><entry>01111</entry><entry>10000</entry><entry>1st carry-outs are 0,0,0,1</entry></row><row><entry /><entry>1111</entry><entry>1111</entry><entry>1111</entry><entry>0000</entry><entry /></row><row><entry /><entry>0</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry /></row><row><entry /><entry>01111</entry><entry>01111</entry><entry>10000</entry><entry>00000</entry><entry>2nd carry-outs are 0,0,1,0</entry></row><row><entry /><entry>1111</entry><entry>1111</entry><entry>0000</entry><entry>0000</entry><entry /></row><row><entry /><entry>0</entry><entry>1</entry><entry>0</entry><entry>0</entry><entry /></row><row><entry /><entry>01111</entry><entry>10000</entry><entry>00000</entry><entry>00000</entry><entry>3rd carry-outs are 0,1,0,0</entry></row><row><entry /><entry>1111</entry><entry>0000</entry><entry>0000</entry><entry>0000</entry><entry /></row><row><entry /><entry>1</entry><entry>0</entry><entry>0</entry><entry>0</entry><entry /></row><row><entry /><entry>10000</entry><entry>0000</entry><entry>0000</entry><entry>0000</entry></row><row><entry namest="1" nameend="6" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0080Four additions were required. In general, for n groups of numbers, at most, n additions will be required.

0000512×32 Multiplier

0081Multipliers are large in area. Each secret-key processing element must contain its own multiplier in order to implement any secret key algorithm requiring multiplication, for example IDEA which will be discussed in more detail below. The area taken by each PE multiplier collectively is significant and as a result, use of this area is made in implementing the 512×32-bit public key multiplier. To save area, the large 512×32 multiplier is implemented by concatenating the 16 32×32 multipliers in each secret key processing element. In other words, the secret and public key units can share the multiplier elements, as is illustrated in the layout of the chip in <figref idref="DRAWINGS">FIG. 4</figref>. Use of the multiplier elements must therefore be coordinated between the secret key processing elements and the PK core processor since the PK core processor cannot perform a multiply operation when any one of the secret key processing elements is itself independently performing a multiply operation.

0082To illustrate the concatenation of the multipliers, a simple design of a combination 4×4/4×N multiplier is illustrated below. Note that more advanced techniques of multiplier design such as Booth encoding and 4:2 compressors are available. The following example provides a simple presentation:

0083<tables id="TABLE-US-00004" num="00004"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="8"><colspec colname="1" colwidth="28pt" align="center" /><colspec colname="2" colwidth="7pt" align="center" /><colspec colname="3" colwidth="42pt" align="center" /><colspec colname="4" colwidth="7pt" align="center" /><colspec colname="5" colwidth="35pt" align="center" /><colspec colname="6" colwidth="7pt" align="center" /><colspec colname="7" colwidth="35pt" align="center" /><colspec colname="8" colwidth="56pt" align="left" /><thead><row><entry namest="1" nameend="8" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry /><entry /><entry>1 </entry><entry>0 </entry><entry>1 </entry><entry>1</entry><entry /></row><row><entry /><entry /><entry>× </entry><entry>0 </entry><entry>1</entry><entry>0 </entry><entry>0</entry><entry /></row><row><entry /><entry /><entry /><entry>0 </entry><entry>0</entry><entry>0 </entry><entry>0</entry><entry /></row><row><entry /><entry /><entry>1</entry><entry>0</entry><entry>1</entry><entry>1</entry><entry /><entry>Partial Products</entry></row><row><entry /><entry>1</entry><entry>0</entry><entry>1</entry><entry>1</entry><entry /><entry /><entry /></row><row><entry>0</entry><entry>0</entry><entry>0</entry><entry>0</entry><entry /><entry /><entry /><entry /></row><row><entry>1</entry><entry>0</entry><entry>0</entry><entry>0</entry><entry>0</entry><entry>1</entry><entry>0</entry></row><row><entry namest="1" nameend="8" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Single-digit multiplication can be easily implemented by using an AND gate. The result, when using two 4-bit operands, consists of 16 bits of partial product. These partial products must be added together efficiently. The partial products could, for example, be added using two 4-bit and one 6-bit full adder, but they would take a substantial time to perform the addition of the partial products, since the carry may have to propagate through several adders. The overall result of such an adder implementation would be too slow. A better approach would consist of an adder whose carry has to go through fewer stages.

0084The basic component of the preferred multiplier is a full adder, a circuit that takes three inputs and outputs the two-bit sum of their inputs. A full adder is illustrated using the symbol in <figref idref="DRAWINGS">FIG. 7</figref>. The use of squares instead of binary numbers is for generality and convenience. The three squares at the top show the three inputs of the full adder. The two squares at the bottom show the sum and carry outputs. The carry is to the lower left to indicate its place value is twice that of the sum. The first stage of the addition of a 4×4 multiplier is illustrated in <figref idref="DRAWINGS">FIG. 8</figref>. Above the summing line, 16 squares, some shown in black, some as white boxes, represent the bits of a partial product which has to be added. The bits shown in black will be added in the first stage using four full adders <b>82</b>. The bits shown as white boxes are not to be added in the first stage, but simply transferred down as shown with the arrows in <figref idref="DRAWINGS">FIG. 8</figref>, in preparation for the next addition stage. The sum of the adders in the first stage is shown below the summing line. The second stage is shown in <figref idref="DRAWINGS">FIG. 9</figref>. Arrows once again indicate bits which are not operated on during this current stage and simply transferred down, while black boxes denote bits that are to be added in this current (second) stage. Once again, four full adders <b>84</b> are used to add the black box elements. At the output of the second stage produced by the full adders <b>84</b>, there are two numbers which now must be added with a regular 4-bit carrying adder <b>86</b>.

0085A comparison of the performance of various adder and multiplier architectures helps to illustrate the advantages of the multiplier according to the present invention. A naive implementation of a 4-bit adder consists of four full adders A0-A3 in series as shown in <figref idref="DRAWINGS">FIG. 12</figref>. In this design, the carry out C_outof the rightmost adder could potentially affect every one of the adder stages to the left of it. The critical path in this design is therefore four adder stages. Since the typical full adder consists of two or more logic stages, the total gate delay of an four-bit adder could exceed 8 stages.

0086An improved four-bit adder is a carry lookahead design. A three-bit carry lookahead adder is shown in <figref idref="DRAWINGS">FIG. 13</figref>. A four-bit design is only a little more complex. A detailed discussion of operation of the AND gates <b>102</b>, OR gates <b>104</b> and Exclusive-OR gates <b>106</b> is not presented since this is a well known circuit. The advantage of a carry lookahead adder is that carries propagate to final sum bits in only four logic gates. More complex designs for wider numbers have more stages of logic, but they are still faster than a carry chain design.

0087In the full 4×4 multiplier, the carry save design creates a critical path through two full adders, plus the final carry lookahead adder. An implementation using only full adders would have a longer critical path since a naive adder using chained carries is slower than the carry lookahead adder. Finally, if we used full carry lookahead adders in the first two stages of the partial product summation, then the resulting multiplier would again be slower, since carry lookahead adders are slower than individual full adders. Note that the multiplier design according to the present invention never propagates a carry from one adder to another at the same partial product level. In this manner, the critical path through the multiplier is sure to include no more than two full adders in the first two stages of partial product summation.

0088<figref idref="DRAWINGS">FIG. 10</figref> illustrates a much wider 4×N multiplier. The large black boxes <b>82</b>, <b>84</b>,<b>86</b> denote the same full adder hardware that was used in <figref idref="DRAWINGS">FIG. 9</figref>. Note that full adders are necessary in this case, since in each circumstance, three inputs are being added together. In <figref idref="DRAWINGS">FIG. 9</figref>, simpler circuitry could have been used since not all circumstances required the addition of three inputs. However, in order to create a system which can handle a 4×N case, full adders are preferably used for all stages with some additional circuitry to determine how to treat a case with fewer than three inputs. Dual mode adders are therefore created, some having a multiplexer feeding one of their inputs to select between the output of a previous stage or a single bit partial product.

0089<figref idref="DRAWINGS">FIG. 11</figref> illustrates the full adders A required to implement the boxed regions <b>82</b>,<b>84</b>,<b>86</b> of <figref idref="DRAWINGS">FIG. 10</figref> with respective carry outputs at the lower left. In the preferred implementation, each adder A is a full adder. Some of the adders have only two inputs in the 4×4 case (i.e. the secret key case), while other adders have three inputs in the 4×N case (i.e. the public key case). The two input adders must have their third input gated with an enable signal. Some adders also require a multiplexer to provide one of their inputs to select between the output of a previous stage or a single-bit partial product. The carry-lookahead adder <b>86</b> on the bottom requires a carry-out every four positions to generate the last bit of the product in the 4×4 case.

0090In <figref idref="DRAWINGS">FIG. 11</figref>, the partial products of a 4×4 multiplier have been labeled to correspond with the following partial product scenario:

0091<tables id="TABLE-US-00005" num="00005"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="8"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="28pt" align="left" /><colspec colname="3" colwidth="28pt" align="left" /><colspec colname="4" colwidth="28pt" align="left" /><colspec colname="5" colwidth="28pt" align="left" /><colspec colname="6" colwidth="28pt" align="left" /><colspec colname="7" colwidth="28pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="7" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry /><entry /><entry /><entry>A</entry><entry>B</entry><entry>C</entry><entry>D</entry></row><row><entry /><entry /><entry /><entry>E</entry><entry>F</entry><entry>G</entry><entry>H</entry><entry /></row><row><entry /><entry /><entry>I </entry><entry>J</entry><entry>K</entry><entry>L</entry><entry /><entry /></row><row><entry /><entry>M</entry><entry>N</entry><entry>O</entry><entry>P</entry></row><row><entry /><entry namest="offset" nameend="7" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0092For a 4×N multiplier, the neighboring partial products must also be considered. They are labeled in <figref idref="DRAWINGS">FIG. 11</figref> according to the following scenario:

0093<tables id="TABLE-US-00006" num="00006"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="8"><colspec colname="1" colwidth="14pt" align="center" /><colspec colname="2" colwidth="42pt" align="center" /><colspec colname="3" colwidth="14pt" align="center" /><colspec colname="4" colwidth="42pt" align="center" /><colspec colname="5" colwidth="14pt" align="center" /><colspec colname="6" colwidth="42pt" align="center" /><colspec colname="7" colwidth="14pt" align="center" /><colspec colname="8" colwidth="35pt" align="center" /><thead><row><entry namest="1" nameend="8" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry /><entry>D′</entry><entry /><entry>A</entry><entry>B</entry><entry>C</entry><entry>D</entry></row><row><entry /><entry /><entry>E</entry><entry>F</entry><entry>G</entry><entry>H</entry><entry /><entry /></row><row><entry /><entry>I </entry><entry>J </entry><entry>K</entry><entry>L</entry><entry>I′</entry><entry /><entry /></row><row><entry>M</entry><entry>N</entry><entry>O</entry><entry>P</entry><entry>M′</entry></row><row><entry namest="1" nameend="8" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0094Note that D′ is the neighboring (either to the left or to the right) equivalent of D. The 8-bit final sum is indicated as S7,S6,S5,S4,S3,S2,S1,S0 and the three lower-order bits of the left-hand neighbor's sum are S2′,S1′,S0′. The 2:1 multiplexer <b>88</b> has a selection signal Sel. In general, if Sel is logic 1, then the left input is passed to the output of the multiplexer; otherwise, if Sel is logic 0, the right input is passed to the output of the multiplexer. The Sel signal is also used to gate the AND gates <b>90</b>. When Sel is logic 1, the other input to the AND gate is passed to the output; otherwise, with Sel at logic 0, the AND gates <b>90</b> are disabled and pass a logic 0 regardless of the value of the other input. Thus, in the implementation of <figref idref="DRAWINGS">FIG. 11</figref>, if Sel is logic 1, a segment of a 4×N multiplier can be implemented, with product appearing on outputs S6-S3. If Sel is logic 0, a 4×4 multiplier is implemented, with the 8-bit product appearing on outputs S7-S0. As such, the implementation of <figref idref="DRAWINGS">FIG. 11</figref> illustrates a secret key multiplier element which can also be utilized as an multiplier element, which when concatenated with other like multiplier elements, will be used to implement the much wider width public key multiplier.

0000Example Implementations

0095Example implementations of common encryption algorithms will be now described with reference to the encryption chip preferred embodiment discussed above. RC5 is perhaps one of the simplest encryption algorithms to implement. It basically utilizes three types of operations: XOR, additions and rotations, all supportable by any one of the processing elements discussed above, as shown in Table 1. Although RC5 has a variable length block, most commonly, each round of the RC5 algorithm operates on a 64-bit data block plus a key value stored in Si1 and Si2 which are constants within each processing element, depending only on the round and the key. To encrypt data, a 64-bit input block is split into two 32-bit words which are then stored in locations A and B in the previous-neighbor memory, the output block is to be written to A_next and B_next in the next-neighbor memory. An example of a round of the RC5 encryption algorithm follows:

0096<tables id="TABLE-US-00007" num="00007"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="84pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>Loop:</entry></row><row><entry /><entry> load r1, A</entry></row><row><entry /><entry> xor r1, B</entry></row><row><entry /><entry> rol r1, B</entry></row><row><entry /><entry> add r1, Si1</entry></row><row><entry /><entry> store r1, A_next</entry></row><row><entry /><entry> load r2, B</entry></row><row><entry /><entry> xor r2, r2, r1</entry></row><row><entry /><entry> rol r2, r2, r1</entry></row><row><entry /><entry> add r2, Si2</entry></row><row><entry /><entry> store r2, B_next</entry></row><row><entry /><entry> sync Loop</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Each round requires 11 clock cycles. If the encryption chip is designed using a logic process that can run up to 400 MHZ, then 36 million blocks can be encrypted per second, or 288 MB/s in ECB mode. If we assume 12 rounds (a typical case for RC5), then compared to a conventional CPU running at the same clock speed, the concurrent execution of multiple PEs according to an embodiment of the present invention results in a 12-fold performance improvement over the conventional software implementation.

0097IDEA is one of the most secure block algorithms available and has a substantially more complex structure. It operates on 64-bit plaintext blocks. A 128-bit key is used. The same algorithm is used both for encryption and decryption. The main philosophy of the algorithm is to mix operations from different algebraic groups, operations such as XOR, addition modulo 2¹⁶, and multiplication modulo 2¹⁶+1. These operations are used to operate on 16-bit blocks.

0098IDEA therefore makes use of both modular multiplication and addition, which are expensive operations in software. The multiplication is complicated by IDEA's treatment of zero: in a multiply, a zero is interpreted as (−1) modulo 65537. Assuming that the value 65537 has been pre-loaded into register r8 of the processing element's register file, and that register r0 contains zero, the following multiplication macro is presented for illustrative purposes:

0099<tables id="TABLE-US-00008" num="00008"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="63pt" align="left" /><colspec colname="2" colwidth="154pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>MACRO MMULT (A,B,RESULT)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="35pt" align="left" /><colspec colname="3" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry /><entry>cbra A == r0, L1</entry></row><row><entry /><entry /><entry>load RESULT, #1</entry></row><row><entry /><entry /><entry>sub RESULT, B, RESULT</entry></row><row><entry /><entry /><entry>jump L2</entry></row><row><entry /><entry>L1:</entry><entry /></row><row><entry /><entry /><entry>cbra B == r0, L3</entry></row><row><entry /><entry /><entry>load RESULT, #1</entry></row><row><entry /><entry /><entry>sub RESULT, A, RESULT</entry></row><row><entry /><entry /><entry>jump L2</entry></row><row><entry /><entry>L3:</entry><entry /></row><row><entry /><entry /><entry>mulm A, B, RESULT, r8</entry></row><row><entry /><entry /><entry>andi #0xFFFF, RESULT</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="21pt" align="left" /><colspec colname="3" colwidth="154pt" align="left" /><tbody valign="top"><row><entry /><entry>L2:</entry><entry /></row><row><entry /><entry /><entry>ENDMACRO</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Each round of IDEA consists of modular multiplications, modular addition and exclusive-OR. The 128-bit key is broken down into subkeys. Each processing element's subkey is a function solely of the key and the processing element, and therefore can be computed in advance and stored in the PE. The plaintext input to IDEA consists of four 16-bit sub-blocks X1 through X4, as indicated earlier. Each round uses six subkeys K1 through K6, and can be coded as follows:

0100<tables id="TABLE-US-00009" num="00009"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="84pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>Loop:</entry></row><row><entry /><entry> load r1, X1</entry></row><row><entry /><entry> load r9, K1</entry></row><row><entry /><entry> MMULT r1, r9, r1</entry></row><row><entry /><entry> load r2, X2</entry></row><row><entry /><entry> load r9, K2</entry></row><row><entry /><entry> MMULT r2, r9, r2</entry></row><row><entry /><entry> load r3, X3</entry></row><row><entry /><entry> load r9, K3</entry></row><row><entry /><entry> MMULT r3, r9, r3</entry></row><row><entry /><entry> load r4, X4</entry></row><row><entry /><entry> load r9, K4</entry></row><row><entry /><entry> MMULT r4, r9, r4</entry></row><row><entry /><entry> xor r5, r1, r3</entry></row><row><entry /><entry> xor r6, r2, r4</entry></row><row><entry /><entry> load r9, K5</entry></row><row><entry /><entry> MMULT r5, r9, r5</entry></row><row><entry /><entry> add r6, r5</entry></row><row><entry /><entry> and r6, #0xFFFF</entry></row><row><entry /><entry> load r9, K6</entry></row><row><entry /><entry> MMULT r6, r9, r6</entry></row><row><entry /><entry> add r5, r6</entry></row><row><entry /><entry> and r5, #0xFFFF</entry></row><row><entry /><entry> xor r1, r6, r1</entry></row><row><entry /><entry> xor r3, r6, r3</entry></row><row><entry /><entry> xor r2, r5, r2</entry></row><row><entry /><entry> xor r4, r3, r4</entry></row><row><entry /><entry> store r1, X1_next</entry></row><row><entry /><entry> store r2, X3_next</entry></row><row><entry /><entry> store r3, X2_next</entry></row><row><entry /><entry> store r4, X4_next</entry></row><row><entry /><entry> sync Loop</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Since IDEA has eight rounds, the encryption chip hardware implementation according to an embodiment of the present invention accelerates the execution by a factor of eight or more. Additional acceleration is provided by the modular multiply instruction which is not available on most microprocessors. The above code requires roughly 50 clock cycles to perform one round. At 400 MHZ, the encryption chip can encrypt with IDEA at a rate of 64 MB/s, about three times faster than a 25 MHZ hardware implementation developed at ETH University in Zurich.

0101Data Encryption Standard, or DES, was originally designed for hardware implementation, and is therefore the most difficult to implement in software. Nevertheless, it can easily be coded in the encryption chip, according to an embodiment of the present invention.

0102Like the previous two algorithms, DES is also a block cipher encrypting data in 64-bit blocks. A 64-bit block of plaintext is the input and a 64-bit ciphertext is the output. Once again, both encryption and decryption use the same algorithm, making DES a symmetrical algorithm. DES creates subkeys from a single key, in this case 56 bits. The subkeys are a function of the PE and the 56-bit key, so they can be computed in advance.

0103The basic concept behind DES, as illustrated in <figref idref="DRAWINGS">FIG. 14</figref>, consists of a substitution followed by a permutation on the text based on the key. The following operations make up the core of DES: <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0104">Expansion: The 64-bit block is divided into two 32-bit pieces <b>108</b>,<b>110</b>. One piece is unaffected by the encryption. (The pieces are operated on every other round.) The piece that is affected is divided into eight groups of four bits. Each group is expanded by copying the two bits adjacent to it.</li><li id="ul0004-0002" num="0105">Each expanded group is XOR'ed at <b>112</b> with a subkey.</li><li id="ul0004-0003" num="0106">The six-bit result of the XOR is used to index a 64-entry×4-bit lookup table <b>114</b> called an S-box. Each of the eight groups uses its own S-box.</li><li id="ul0004-0004" num="0107">The output from the S-boxes is permuted at <b>116</b>: the bits are scrambled. Eight outputs yield 32 bits.</li><li id="ul0004-0005" num="0108">The 32-bit output is XOR'ed at <b>118</b> with the other 32-bit half of the block. <br /> The operations can be coded as follows: expansion is performed by copying the input word, and masking bits such that there are two words: one representing even-numbered S-box inputs and one representing odd-numbered S-box inputs. The two words are XOR'ed with key information. The result is used to index the S-box lookup table. The data in each S-box is pre-permuted, so that the output of the S-box is 32-bit data. The final value is the logical OR of all components. Sample code follows: </li></ul></li></ul>

0109<tables id="TABLE-US-00010" num="00010"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="84pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>Loop:</entry></row><row><entry /><entry> load r1,A</entry></row><row><entry /><entry> load r2,B</entry></row><row><entry /><entry> load r3,r2</entry></row><row><entry /><entry> store r2, A_next</entry></row><row><entry /><entry> and r2,#0xF9F9F9F9</entry></row><row><entry /><entry> and r3,#0x9F9F9F9F</entry></row><row><entry /><entry> xor r2,K1</entry></row><row><entry /><entry> xor r3,K2</entry></row><row><entry /><entry> load r5,r0</entry></row><row><entry /><entry> load r4,r3</entry></row><row><entry /><entry> rol r4,#1</entry></row><row><entry /><entry> and r4,#0x3f</entry></row><row><entry /><entry> or r5, [r4 + S1]</entry></row><row><entry /><entry> load r4,r2</entry></row><row><entry /><entry> ror r4,#3</entry></row><row><entry /><entry> and r4,#0x3f</entry></row><row><entry /><entry> or r5, [r4 + S2]</entry></row><row><entry /><entry> load r4,r3</entry></row><row><entry /><entry> rol r4,#7</entry></row><row><entry /><entry> and r4,#0x3f</entry></row><row><entry /><entry> or r5, [r4 + S3]</entry></row><row><entry /><entry> load r4,r2</entry></row><row><entry /><entry> ror r4,#11</entry></row><row><entry /><entry> and r4,#0x3f</entry></row><row><entry /><entry> or r5, [r4 + S4]</entry></row><row><entry /><entry> load r4,r3</entry></row><row><entry /><entry> rol r4,#15</entry></row><row><entry /><entry> and r4,#0x3f</entry></row><row><entry /><entry> or r5, [r4 + S5]</entry></row><row><entry /><entry> load r4,r2</entry></row><row><entry /><entry> ror r4,#19</entry></row><row><entry /><entry> and r4,#0x3f</entry></row><row><entry /><entry> or r5, [r4 + S6]</entry></row><row><entry /><entry> load r4,r3</entry></row><row><entry /><entry> rol r4,#23</entry></row><row><entry /><entry> and r4,#0x3f</entry></row><row><entry /><entry> or r5, [r4 + S7]</entry></row><row><entry /><entry> load r4,r2</entry></row><row><entry /><entry> ror r4,#27</entry></row><row><entry /><entry> and r4,#0x3f</entry></row><row><entry /><entry> or r5, [r4 + S8]</entry></row><row><entry /><entry> xor r5,r1,r5</entry></row><row><entry /><entry> store r5,B_next</entry></row><row><entry /><entry> sync Loop</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> This sample code requires 44 clock cycles to perform one round. At 400 MHZ, a data rate of 72 MB/s can be achieved. This rate compares favorably with hardware implementations of DES available in the mid-1990's, that encrypt at rates ranging from 1-35 MB/s. VLSI Technology's VM007 can encrypt up to 200 MB/s.

0110In each of the above cases, performance has been shown to be much faster than a software implementation on a conventional CPU, but slower than a dedicated hardware implementation. The advantage of this invention over the hardware implementations is that the encryption chip is programmable, so that it may implement any algorithm, including those that have yet to be conceived.

0111Although no specific public key algorithm examples have been given, it should be noted that similar improvements over existing approaches will result by employing the techniques as discussed in the preferred embodiment of the present invention.

EQUIVALENTS

0112While this invention has been particularly shown and described with references to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims. Those skilled in the art will recognize or be able to ascertain using no more than routine experimentation, many equivalents to the specific embodiments of the invention described specifically herein. Such equivalents are intended to be encompassed in the scope of the claims.