Co-processor for performing modular multiplication

Details Co-processor for performing modular multiplication Co-processor for performing modular multiplication

1999-06-03

2001-03-27

Ngo, Chuong Dinh (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06209016

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to a co-processor for performing modular multiplication and particularly, though not exclusively, for implementing the Montgomery Reduction Algorithm.
BACKGROUND OF THE INVENTION
Modular multiplication is extensively used in implementing cryptographic methods such as RSA cryptography.
The Montgomery algorithm is one of the most efficient techniques for performing modular multiplication. Its use is particularly effective where high performance is required so as to minimise the computation time.
The Montgomery proof is given in Appendix 1 and the Montgomery Reduction Algorithm is outlined below:
Montaomery Algorithm To enact the P operator on A.B we follow the process outlined below:
(1) X=A.B+S {S initially zero}
(2) Y=(X.J) mod2
n
(where J is a pre-calculated constant)
(3) Z=X+Y.N
(4) S=Z/2
n
(5) P=S (modN) (N is subtracted from S, if S≧N)
Thus P P(A.B)
N
(the result in the Montgomery Field of numbers)
In financial applications where smartcards are used as a means of ensuring a high level of security during the transaction, Public Key Cryptography is becoming increasingly popular. Public Key Cryptography offers a higher level of protection than the traditional symmetric or private key methods but until recently has been expensive to implement. Advances in technology have now made the implementation of such methods cost effective. RSA Public Key capability has been designed into smartcard microcontrollers which also include an on-chip co-processor which has been specifically designed to perform modular multiplications for operands each of 512 bit length. The co-processor is directly driven by the microcontroller's CPU under software control by a program stored either in ROM or in EEPROM. Such a co-processor which implements the Montgomery algorithm for modular reduction without the division process and is known from European Patent Publication EP-0601907-A.
As will be discussed in detail hereafter, such a known co-processor suffers from a number of disadvantages.


REFERENCES:
patent: 5742530 (1998-04-01), Gressel et al.

Affiliated with

Also associated with

Rating

Co-processor for performing modular 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 Co-processor for performing modular multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Co-processor for performing modular multiplication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2514245