A Small Modular Exponentiation Circuit
Original Publication Date: 1998-Jun-01
Included in the Prior Art Database: 2005-Apr-04
Publishing Venue
IBM
Related People
Abstract
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.
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...