A Small Modular Exponentiation Circuit

A Small Modular Exponentiation Circuit

   Disclosed is a small modular exponentiation circuit.  The
modular exponentiation (M**E mod N) is achieved by repeated number
of modular multiplications (A*B mod N).  As shown in Fig. 1, one
modular multiplication is in turn executed by repeated addition of
partial product (A), followed by an adjustment operation (N),
shift operation (*2), and another adjustment.  When a bit '1' is
found in the multiplicator B by checking each bit in B sequentially
from the MSB-side, addition and adjustment are executed.  When the
bit is '0', only adjustment is done.  After that, *2 operation and
adjustment are executed.  To reduce the number of additions, binary
redundant form is used for the multiplicator B.  The consecutive '1'
bits in B are transformed such that 1111=10000-1.  To keep the
intermediate value X in the range -n <= X < n, -N operation is
executed if X becomes a positive number after addition (A) or *2
operation.  On the other hand, if X becomes negative,  operation is
done.  An adjustment after the addition can be skipped when the sign
of X is changed by the addition.  An adjustment after the *2
operation also can be skipped when the 3 MSBs of X are '000' or
'111'.  Fig. 2 shows the block diagram of the modular exponentiation
circuit.  M**E mod N can be calculated by repeating an alternating
multiplication (X*M) and squaring (X*X), depending on the bit pattern
of the exponent E.  Registers M and N are used for additio...