Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Patent
1998-07-09
2000-12-19
Mai, Tan V.
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
G06F 738
Patent
active
061637904
DESCRIPTION:
BRIEF SUMMARY
The invention relates to a modular arithmetic coprocessor comprising an integer division circuit. Modular arithmetic coprocessors are used in encryption and/or decryption circuits. The use of these coprocessors enables the considerable acceleration of the operations of encryption and/or decryption using the Montgomery method. Systems of this kind are much used in chip cards using, in particular, the RSA code.
The RSA code is a mathematical encoding method where a binary message M encoded on n bits is processed as an integer of n bits. The encryption and decryption are achieved by modular exponentiation operations:
M' is the encrypted message encoded on n bits, N is an integer encoded on n bits such that N=p*q, p and q being two prime numbers. The exponents e and d are two whole numbers such that (e*d) mod .PHI.(N)*1, with .PHI.(N)=(p-1)*(q-1). A code of this kind therefore has two keys: one is an encryption key known as a public key (e and N) and the other is 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*.PHI.(N))/e, K being an integer coefficient that is not zero. The security of a code of this kind actually relates to the complexity of the operations to be performed. To find the secret key, it is necessary to factorize N into prime numbers. The greater the numbers p and q, the greater is the amount of time required for this operation (in practice p and q are encoded on a few hundreds of bits). Indeed, it is necessary to make successive tests on the divisibility cf N by all the integers encoded on 2 to n/2 bits.
It is quite possible to look for a secret key on the basis of the public key, provided that several hundreds of years are devoted to the task. However, certain uses of RSA codes may require changes of key that call for a computation of the keys. Computations of this kind use operations of division on big numbers.
In chip cards, the encryption circuits make use of a microprocessor-coprocessor type of architecture. The microprocessor is a standard 8-bit or 16-bit type of microprocessor. The coprocessor is a modular arithmetic coprocessor, for example of the same type as the one described in the European patent application referenced EP-A-0 601 907 (hereinafter called D1). The coprocessor is illustrated in FIG. 1 (this figure corresponds to FIG. 2 of the European patent application referred to).
To carry out the division operations, the coprocessor is of no use. Therefore, the division takes place in the microprocessor. The fact of carrying out the division in the microprocessor requires a considerable amount of time because the microprocessor is not capable of directly processing large-sized data elements (for example 512 bits). Furthermore, the program that enables this division to be carried out will take up a considerable amount of memory space (a code associated with the program) and will use working memory space to perform its computations. For a chip card, it is therefore very difficult to be able to recompute keys from different public keys (e and N).
The invention proposes the addition, in an modular arithmetic coprocessor, of a computation circuit specially designed to perform divisions on big numbers. Since the division circuit does not have to use a large amount of additional space, this circuit uses resources common to the modular operations performed according to the Montgomery method which are already present in a modular arithmetic coprocessor. Thus, the fact of making a computation circuit specific to the division on the modular arithmetic coprocessor enables a chip card to carry out a computation of keys without any noteworthy increase in the size of the integrated circuit. The invention also proposes a method for the making of a division using a circuit of this kind.
An object of the invention therefore is a modular arithmetic coprocessor designed to perform computations according to the Montgomery method comprising a division circuit wherein the division circuit comprises a test
REFERENCES:
patent: 3816733 (1974-06-01), Sather
patent: 3816773 (1974-06-01), Baldwin et al.
patent: 5261001 (1993-11-01), Dariel et al.
patent: 5448639 (1995-09-01), Arazi
patent: 5513133 (1996-04-01), Cressel et al.
patent: 5912904 (1999-06-01), Monier
patent: 5948051 (1999-09-01), Monier
patent: 5987489 (1999-11-01), Monier
patent: 5999953 (1999-12-01), Monier
K, Hwang, Computer Arithmetic, 1979, pp. 218-221, XP 002022160.
R. Richards, Arithmetic Operations in Digital Computers, 1955, pp. 152-155, XP002022159.
K. Murata et al., Very High Speed Serial and Serial-Parallel Computers Hitac 5020 and 5020E, 1964 pp. 187-203. XP002022162.
Galanthay Theodore E.
Mai Tan V.
Morris James H.
SGS-Thomson Microelectronics S.A.
LandOfFree
Modular arithmetic coprocessor comprising an integer division ci does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Modular arithmetic coprocessor comprising an integer division ci, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modular arithmetic coprocessor comprising an integer division ci will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-277760