Digital Signal Processing

This invention relates to a method and apparatus for carrying out the modulo reduction of large binary numbers and to cryptographic apparatus, more particularly but not exclusively cryptographic apparatus which executes the Rivest, Shamir and Adleman (RSA) public key cryptosystem proposed by R. L. Rivest, A. Shamir, and L. Adleman in "On Digital Signatures and Public Key Cryptosystems", (Comms. ACM Vol 21 Number 2, February 1978, pages 120-126).

The RSA cryptosystem involves modular exponentiations of the form y=x.sup.k modulo m where y is the ciphertext and x is the plain text to be enciphered, or alternatively where x is the received ciphertext and y is the deciphered text, while k and m form the cipher key (k being different for enciphering and deciphering). For best security, x, k, and m need to be of the order of 256 bits long or more.

As shown by D. E. Knuth in "The Art Of Computer Programming" (Volume 2: "Seminumerical Algorithms", 2nd Edition, Addison-Wesley 1981), an exponentiation operation can be broken down into a series of repeated squarings of and multiplications by the original number depending upon the bits of the exponent, omitting the most significant and taking the remainder in sequence from the most significant end. Squaring is carried out for every one of these less significant bit positions while multiplication is carried out only for bits which are set. Thus the operation of raising x to a power 13 (1101 binary) becomes a sequence of squaring x, multiplying the result by x, squaring and then squaring again the result of that multiplication, and then multiplying by x again, i.e.

Meanwhile the modulus operation is associative so a modulo m reduction of an exponentiation is equivalent to a modulo m reduction after each squaring and each multiplication, i.e.

Thus, the basic arithmetic operation to be performed by RSA cryptographic apparatus is modulo multiplication of the form AB mod m.

At least at present, it would be quite difficult to incorporate into an integrated circuit the means for carrying out parallel multiplication of numbers which are 256 bits long. Thus, a more attractive possibility is bit-serial multipliers such as those proposed by I. Ngo-Chen and R. Willoner in "An O(n) Parallel Multiplier with Bit-Sequential Input and Output" (IEEE Trans. Comp. Vol C28 Num 10 October 1979 pp 721-727) and N. R. Strader and V. T. Rhynne in "A Canonical Bit Sequential Multiplier" (IEEE Trans. Comp. Vol C31 Num 8 August 1982 pp 791-795). Such multipliers take the multiplicand and multiplier in one bit at a time, least significant first, and produce a result one bit at a time least significant first.

To match the bit serial multiplier, there is then required a serial (or at least pseudo-serial) modular reduction unit.

For this, the operation of modular reduction can be converted to a summing operation. The binary notation P of AB can be expressed as: ##EQU1##

Where p.sub.i is the i th bit of P. Thus: ##EQU2## and, since the modulus operation is associative, ##EQU3##

Each bit p.sub.i of P can only take one of the values 0 and 1 so the summation becomes equivalent to conditionally summing the modular reductions of a power series of 2 (called the `residues` of that series) depending on the value of each corresponding bit of P and then making a modulo m reduction of the sum. This is therefore known as the sum-of-residues method of modular reduction. For the sum-of-residues method to work in conjunction with a serial multiplier, the residues of ascending powers of 2 have to be made available in correct sequence as the successive bits of P are produced by the multiplier. It has been proposed to do this by having the residues pre-stored in a look-up table and called out of that table in sequence--I. Ngo-Chen and R. Willoner, "An Algorithm For Modular Exponentiation" (Proc. 5th Symp. Comp. Arithmetic pp 135-137, IEEE 1981). A problem with this proposal is that the residues have to be pre-computed and stored as words up to n-bits long. This implies very wide data bus paths which, just like the use of parallel multipliers, would render the design of an integrated circuit for performing the method difficult to say the least. A further problem is the need to carry out a modulo m reduction on the result of each sum of the residues operation which adds complexity to the algorithm and the apparatus for carrying it out.

Thus, one object of the invention is to provide a method and means for providing the residues of a power series of 2 without pre-calculating and storing them. A further object is to provide a modulo m reduction method and means which uses the sum of residues approach but which is simplified compared with the above mentioned prior proposal. Yet further objects are to provide a `serial` arrangement for generating the residues, to provide a modulo m reduction unit incorporating such a `serial` residue generator, and to provide an encryption/decryption device incorporating both a serial multiplier and a serial modulo m reduction device.

According to one aspect of the invention, there is provided a method of performing a modulo m reduction of a binary number, in which method the modulo m reductions of ascending powers of two are calculated in sequence, each being calculated from the value of the next preceding calculation in a recursive process, and said modulo m reductions are conditionally summed in dependence upon the bit values of said binary number.

According to a second aspect of the invention there is provided apparatus for performing encryption and decryption comprising:

means for supplying in sequence the bits of a digital signal to be encrypted or decrypted;

serial multiplier means for squaring said signal and conditionally multitplying the result by the original signal in dependence upon the bits of a held exponent;

serial means for implementing the modulo m reduction method described above in respect of the output of said multiplier means.

For a better understanding of the invention and to show how the same may be carried into effect, reference will be made, by way of example, to the accompanying drawings, in which:

FIG. 1 is a block diagram of RSA cryptographic apparatus incorporating a serial multiplier according to the present invention;

FIG. 2 is a plot of bit lengths overhead h against modulo bit length m;

FIG. 3 is a block diagram of a `parallel` modulo m reduction device;

FIG. 4 is a table of sign-bit values;

FIG. 5 is a block diagram showing the general form of a serial array of one-bit processing elements;

FIG. 6 is a simplified circuit diagram of one of the elements of FIG. 5, and

FIG. 7 is a block diagram of a serial modulo m reduction device using the array of FIG. 5.

In the FIG. 1 apparatus, a block of text to be encrypted is fed into a shift register 1 via input 2 and circulated through the register so that the bits of the text appear in sequence at one input of a logic circuit 3. Meanwhile, circulating within shift register 4 so that they appear in sequence at a second input of the logic circuit 3 are the bits of the chosen exponent, i.e. the number k of the earlier discussion. The two inputs of a serial multiplier 5 are connected to circuit 3 while its output is connected via modulo reduction unit 6 to a third input of the logic circuit. Circuit 3 acts so as to carry out the function illustrated by expression (1) above, namely the circuit 3 takes in the text from register 1 and applies it bit by bit to both inputs of the multiplier 5 to become squared, the binary result being modulo m reduced by unit 6 (which is a means for performing modulo m reduction of a binary number) and fed back into circuit 3. Depending upon the bit value then being read from register 4, the modulo m reduced squared value is passed to both inputs of the multiplier so as to be squared again, or is passed to only one input of the multiplier while the other input thereof is again fed with the content of register 1 so as to achieve a multiplication of the squared value by the original value.

Eventually a fully encrypted version of the text in register 1 will appear at the output of reduction unit 6 and this version is fed out of logic circuit 3 at output 7, a new block of text is fed into register 1 and the encryption process is carried out for that block and so on.

The modulo reduction unit 6 of FIG. 1 works by the sum-of-residues method described earlier but, instead of calling the residues from memory as in the described prior art proposal, they are calculated as and when needed by a conditional recursion process, i.e.

where r.sub.i is the residue required and r.sub.i-1 is the preceding residue which would already have been calculated (note that r.sub.0 =1 of course).

As noted earlier, the value of AB Mod m equals the modulo m reduced result of the sum of residues operation. In the method and apparatus being described herein however, other than for the result of the final such operation, the modulo m reduction of each sum of residues is not carried out. This is allowable because the result, i.e. before the aforementioned reduction, is always congruent to, if larger than, the true value of AB Mod m. Thus, provided that a simple modulo m reduction is carried out on the final sum of residues result, i.e. the encrypted (or decrypted) text appearing at output 7 in FIG. 1, the performances of a reduction on each intermediate result produced by unit 6 is of no account except insofar as the system, particularly the multiplier 5, has to be sized to allow for the larger values, i.e. the system has to have an (n+h) bit capacity where n is the bit length of the modulo m and h is an overhead. If the overhead is not provided then of course the multiplier would overflow when the result is fed back to it. The question of course is how big should the overhead h be. We have determined by way of a computer simulation that for bit length n, a realistic value of h is of the order .vertline.log.sub.2 n+2.vertline.. Herein, ".vertline.x.vertline." means "the next integer greater than x" so that for example .vertline.log.sub.2 n+2.vertline. above means the next integer greater than log.sub.2 n+2. Support for the simulation is given by a derivation of an upper boundary value of h as follows:

Let P be the result of a squaring or multiplying operation as defined earlier, i.e. P=X.sup.2 or A.X where A is less than 2.sup.n.

Let the expression ##EQU4## define p.sub.i where I equals the bit length of P.

Let r.sub.j =2.sup.j-1 mod m where m is less than 2.sup.n (residues of power series of 2).

Hence ##EQU5## where p.sub.i and I are defined by the previous P.

Now let Y be the maximum value (less than 2.sup.n+h) of X that can ever occur. This maximum is not yet known but is to be found by induction.

Now r.sub.i <m<2.sup.n

so r.sub.i <=2.sup.n -2

therefore ##EQU6## where p.sub.i and I are for the previous p.

But ##EQU7## so Y<=(2.sup.n -2). .vertline.log.sub.2 (P).vertline.

Now P=X.sup.2 or AX as stated earlier where X is the previous sum of residues result. The sum of residues result could be greater than 2.sup.n (in general) while A<2.sup.n so the largest Y will be produced by a squaring operation. Therefore, Y<=(2.sup.n -2). .vertline.log.sub.2 (X.sup.2)+1.vertline.

However, the maximum for X=Y so:

Using the above analysis, h can be calculated for a series of values n (for example, by use of a comparatively simple iterative computer program of which the design will be clear to those skilled in the art) and h can then be plotted against n as shown in FIG. 2. The stepped line in FIG. 2 shows the value of h rounded up to the nearest integer value and thus shows the actual bit length overhead needed in terms of hardware for the given range of n, n being the required bit length of the modulus m.

As can be seen from FIG. 2, for large values of n, h does indeed approximate to a maximum of .vertline.log.sub.2 n+2.vertline..

It will be seen also that where n is the aforementioned typical value of 256 bits, the system has to be sized to handle 267 bit numbers, i.e. the overhead h is 11 bits and the ratio h/n is only about 4%.

As noted earlier, a final modulo m reduction on the final sum of residues still has to be carried out--this however is a comparatively simple operation e.g. by way of software on a host micro-computer (not shown).

The reduction unit 6 could be a `parallel` device as shown in FIG. 3. By reference to the FIG. 3 and to the table of FIG. 4, it will be shown how a simplification of the sum of residues algorithm can be made with a view to achieving easier implementation of the algorithm not only by the parallel device but also by the preferred serial arrangement to be described later. In FIG. 3, two n bit registers 8 and 9 hold the 2's complement of the modulus -m, and the current residue r respectively. The residue r is initially 1. As the system is clocked, the residue register 9 is reloaded with either (2r) or (2r-m), depending on the sign bit of (2r-m). An (n+h) bit accumulator 10 sums those residues which are gated into it by the incoming serial product P.

For practical sizes of n, the time taken for the sign bit to appear will be prohibitive, because of the long carry-propagate path. However, for a given modulus, the sequence of the sign bits will always be the same. Therefore they can be pre-computed by a host machine each time the modulus is changed, and stored as a sequence of bits in a shift register. This allows the carry chain to be pipelined. For example, if the modulus is ll, the sign bits are as shown in FIG. 4.

Suppose m is q bits long (q<=n), then

so for i=0 . . . (q-1), r.sub.o =1

because 2.r.sub.i-1 <m, hence the sign bits are all 1.

This means that, for the lowest (q-1) bits of P, the sign bits are all 1. To make the most of this fact, a "working modulus", m' can be used, being the actual modulus multiplied by an appropriate power of 2 to make an n bit number, i.e.

The sum of residues derived using this modulus will be congruent to that of the real modulus, and the bit length of the result will still not exceed the figure used in the maximum complexity calculations above. However, the length of the sign bit shift register now need only be (n+2h). The first n bits of the product P may be loaded directly into the accumulator, and the residue register R may be pre-loaded with (-m') in 2's complement form, as this is the residue of 2.sup.(n+1) modulo m'.

Note that if the lower n bits of P represent a number >=m', then the pre-loading of the accumulator results in m' being added to the accumulation. However, this still yields a final sum congruent to the true residue, and within the maximum bit length defined above. It does however mean that the sign bit register is (n+2h) bits, as opposed to (n+2h+1).

The modified parallel architecture may now be transformed into a bit serial array format. Physically, it consists of a regular array of simple synchronously clocked processing elements or `cells` 40 requiring near neighbor connection only as shown in FIG. 5.

Referring now to FIG. 6, in each cell 40 of the array, a shift register formed by the cascading of FFSEL at each cell propagates a select pulse SELIN to each cell in turn. The arrival of this pulse at a cell causes the current P bit on the common product input line PRODIN to be "held" at that cell in latch LP. A value (-m') circulates in a shift register formed by the cascaded FFMOD flip flops. ADR1 corresponds to the top adder in FIG. 3, subtracting m' from 2r. FFC1 stores the carry for the next cycle. The sign bit for the cell is stored in a flip flop FFSIGN, and gates either 2r or (2r-m) via multiplexer MX. The result is propagated to the next cell to the right via two flip flops FFR1 and FFR2. The extra clock cycle delay achieves the doubling of the residue presented to the next cell. The output of FFR1 is also gated by the stored product bit into the carry save accumulator formed by ADR2, FFC2 and FFSUM. Using the output of FFR1 further pipelines the design-- the critical timing path then includes only one adder delay.

A scheme for interconnecting a practical array of cells is shown in FIG. 7. This also shows part of the accumulator being used as a shift register to buffer the first n bits of the product input. The feedback paths for the "shifting" modulus and the select pulse are also included.

The array computes the sum-of-residues as follows:

Consider time step i, 1<=i<=2(n+h), and Processing Element j, 1<=j<=(n+2h).

Bit i of the product P is assumed to be available at time step i. During time steps i=1 . . . n, the array stores the least n bits of the product P. During time steps i=n . . . 2(n+h)-1, element j calculates the (i-j-n+2)th bit of the residue modulo m' of 2.sup.(j+n). During time steps i=(n+1) . . . 2(n+h), element j also holds the (j+n)th bit of the product, which gates the accumulation of the (i-j-n)th bit of the residue of 2.sup.(j+n), for all j<=(i-n). The "accumulator" is effectively preloaded by bits 1 . . . n of the product. In practice this is achieved by adding bit (i-n) of the product to the accumulating adder in PE No. 1, during time steps i=(n+1) . . . 2n.

Array operation is illustrated for the time steps i=n, (n+1), (n+2) . . . and processing elements 1, 2, 3 . . . in Table 1 below. Note that P is the product to be reduced, and that the carry terms for the accumulator are not shown.

The sum-of-residues appears serially, least significant bit first, at element (n+2h). The latency between the final bit of the product, and the first bit of the sum-of-residues is just one clock cycle, and hence the output can be fed directly back into the multiplier during exponentiation.

The logic shown in FIG. 6 is not inherently self-clearing during continuous operation, as the residue section attempts to generate (2r-m) for ever increasing powers of 2 as the modulus re-circulates. Therefore, some logic is needed to purge the residue section on arrival of the select pulse at the cell, signifying a cycle of order 2.degree..

As will be appreciated, on the basis of the description above, there can be designed a high-speed hardware efficient VLSI architecture for performing RSA encryption and decryption, using serial data and one-dimensional systolic arrays. The system consists of a serial multiplier array coupled with a serial sum of residues reduction array. No look up tables are required, and the operation is fully synchronous. Based on this architecture, it is possible to build an easily expandable RSA engine for performing n bit encryption/decryption with a hardware complexity proportional to n and speed proportional to (1/n.sup.2). The system needs minimal host support for loading the modulus etc. and performing a final reduction: these tasks could be performed by a dedicated single chip microcomputer.