Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-08-28
2001-04-03
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06212538
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to methods for performing certain mathematical operations, and, more particularly, to a method for the performing of an integer division with a modular arithmetic coprocessor.
BACKGROUND OF THE INVENTION
Modular arithmetic coprocessors are typically used in encryption and/or decryption circuits. The use of these coprocessors enables a considerable acceleration of encryption and/or decryption operations using the Montgomery method. Such systems are commonly used in chip cards employing, in particular, the RSA code.
The RSA code is a form of mathematical encoding where a binary message M encoded on N bits is processed as an integer of n bits. The encryption and decryption are done by operations of modular exponentiation:
encryption: M′=M
e
mod N,
decryption: M=M′
d
mod N.
Where M′ is the encrypted message encoded on n bits, N is an integer encoded on n bits such that N=p*q, and p and q are two integers. The exponents e and d are two integers such that (e*d) mod &PHgr;(N)=1, with &PHgr;(N)=(p−1)*(q−1). A code of this kind therefore has two keys, one encryption key called a public key (e and N) and the other a decryption key called a secret key (d and N).
To find the secret key from the public key, it is enough to carry out the following operation: d=(1+K*&PHgr;(N))/e, with K being an integer coefficient that is not zero. The security of a code of this kind lies in the complexity of the operations to be performed. To find the secret key, it is necessary to split up N into prime numbers. This requires a period of time that becomes greater as the numbers p and q are increased (p and q are encoded on several hundreds of bits). Indeed, it is necessary to test, successively, the divisibility of N by all the integers encoded on 2 to n/2 bits.
It is quite possible to find out the secret key from the public key, provided that several hundreds of years are spent for this purpose. However, certain uses of RSA codes may require changes of keys that make use of a computation of keys. Such computations may make use of divisions on large numbers.
In chip cards, the encryption circuits make use of a microprocessor-coprocessor type architecture. The microprocessor is a standard 8-bit or 16-bit microprocessor. The coprocessor is a modular arithmetic coprocessor especially designed to carry out computations on large numbers. The document EP-A 601,907 discloses a modular arithmetic coprocessor using a serial architecture that is particularly well suited to chip cards. This particularly well suited coprocessor has been used as a basis for several improvements, and especially for the patent application PCT/FR 97/00035.
The patent application PCT/FR 97/00035 discloses a possible performance of an integer division using the modular arithmetic coprocessor. However, the division made requires a reversal of bits on large-sized words for the dividend and the quotient. The reversal is done at present by a processor which works jointly with the coprocessor and requires, firstly, substantial memory space and, secondly, substantial computation time.
SUMMARY OF THE INVENTION
The invention proposes to resolve the problems raised by the prior art. The invention proposes a new division circuit that can be integrated into the modular arithmetic coprocessor disclosed in the document EP-A 601,907 for which it is planned to have a data reversal that is achieved internally.
An object of the invention is a method for the implementation of an integer division in a modular arithmetic coprocessor. The division relates to a dividend A, encoded on &agr; words of Bt bits, divided by a divider N, encoded on n words of Bt bits, to obtain a quotient S, encoded on &agr;−n+1 words of Bt bits. At least one word of Bt bits of the dividend A is entered bit-by-bit into a Bt bit dividend shift register in a first order, and is output from the dividend register bit-by-bit in an order that is the reverse of the first order; and/or in which at least one Bt word of the quotient S is entered bit-by-bit into a quotient register in a defined order, and is output bit-by-bit in an order that is the reverse of the defined order.
Preferably, the dividend register performs a Bt−1 bit shift Bt times by having its input connected to its output. Thus, the contents of the dividend register are output bit-by-bit after each of the shifts by Bt−1 bits. The quotient register performs a shift of Bt−1 bits Bt times, the first shift bringing about the entry of one bit of the quotient S and the output of the quotient register being connected to the input of the quotient register during the Bt−2 following shifts.
In one variant, the dividend and quotient registers receive, successively and respectively, Bt bit words of the dividend A and the &agr;−n+1 Bt bit words of the quotient S. Each of the words has a lower place value than the previously received word. In another variant, several Bt bit dividend and quotient registers each receive, respectively, a Bt bit word of the dividend A and of the quotient S.
An object of the invention is also a modular arithmetic coprocessor comprising a division circuit to carry out an integer division of a dividend A, encoded on &agr; words of Bt bits, by a divider N, encoded on n words of Bt bits, to obtain a quotient S, encoded on &agr;−n+1 words of Bt bits. The coprocessor comprises at least one Bt bit dividend shift register to contain at least one word of the dividend A to be able to enter the word of a dividend A in a first order, and to output the word of the dividend A in an order that is the reverse of the first order; and/or wherein it comprises at least one Bt bit quotient shift register to contain at least one word of the quotient S to be able to enter the word of the quotient S in a defined order, and output the word of the quotient S in an order that is the reverse of the defined order.
Preferably, the coprocessor has a dividend multiplexer and/or a quotient multiplexer to connect the output of the dividend register and/or the quotient register, respectively, to the input of the dividend register and/or the input of the quotient register to reverse the order of output of the bits contained in the dividend register and/or in the quotient register by rotation of the contents of the dividend register and/or the quotient register.
REFERENCES:
patent: 5751620 (1998-05-01), Monier
patent: 5999953 (1999-12-01), Monier
patent: 97/25668 (1997-07-01), None
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Galanthay Theodore E.
Mai Tan V.
STMicroelectronics S.A.
LandOfFree
Method for the performance of an integer division with a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for the performance of an integer division with a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the performance of an integer division with a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2529036