Circuit and method of modulo multiplication

Details Circuit and method of modulo multiplication Circuit and method of modulo multiplication

1998-07-22

2001-01-30

Swann, Tod R. (Department: 2132)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C380S028000, C708S505000, C708S523000

Reexamination Certificate

active

06182104

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates, in general, to multipliers and, more particularly, to a cryptographic multiplier.
Rivest-Shamir-Adleman (RSA) is a widely used cryptographic algorithm that provides high security for digital data transfers between electronic devices. The modular exponentiation mathematics of the RSA algorithm can be efficiently computed using Montgomery's method for modular reduction based on a hardware multiplier. Modular exponentiation of large integers can be efficiently computed with repeated modular multiplications and the efficiency of the overall RSA computation is directly related to the speed of the multiplier. Hardware multiplier architectures use pipelining techniques for the massive parallel computations of the Montgomery algorithm. A pipelined hardware multiplier computing the Montgomery algorithm can provide speed and silicon area tradeoffs that provide both a high performance and a cost effective solution. In addition, the pipelined integer modular multiplier offers lower power which is required for many applications.
The cryptosystem facilitated by the RSA algorithm offers a high level of security but is expensive to implement. Although the mathematics of the RSA algorithm with modular exponentiation are straight forward, efficient hardware implementation is not straight forward. With increasing demand for faster cryptographic operations and higher performance, hardware modular multiplier architecture improvements are needed to ensure high levels of security.
Accordingly, it would be advantageous to have a modular exponentiation and multiplication system that achieves high performance, low cost, and low-power for implementation in an integrated circuit. A need exists for a multiplication system that achieves high performance by computing the Montgomery algorithm in fewer clock cycles than in prior art systems. A further need exists for a multiplication system that is adaptable to operands having an increased number of bits.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1
is a block diagram of a smartcard that includes a Foster-Montgomery Hardware Accelerator (FMHA) block;
FIG. 2
is a diagram illustrating data being transferred over the internet from an integrated circuit that includes the FMHA block;
FIG. 3
is a block diagram that illustrates the functional blocks included in the FMHA block of
FIG. 1
;
FIG. 4
is a block diagram of a portion of a modulo reducer;
FIG. 5
is a block diagram of a portion of the modulo reducer combined with a multiplier for use in the FMHA block of
FIG. 1
;
FIG. 6
is a flow diagram
230
that illustrates a method for generating the value (R
2
mod N) that is used in the Foster-Montgomery Reduction Algorithm; and
FIG. 7
is a block diagram that illustrates the generation of the value (R
2
mod N) as described in FIG.
6
.


REFERENCES:
patent: 4658094 (1987-04-01), Clark
patent: 5513133 (1996-04-01), Cressel et al.
patent: 5675527 (1997-10-01), Yano
patent: 5764554 (1998-06-01), Monier
patent: 5784305 (1998-07-01), Nadehara
patent: 5870478 (1999-02-01), Kawamura

Affiliated with

Also associated with

Rating

Circuit and method of modulo multiplication does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Circuit and method of modulo multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit and method of modulo multiplication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2470161