Method for the implementation of an elementary modular operation according to the Montgomery method
AssigneeSTMicroelectronics S.r.l.
InventorBernard Plessier
Life of this patent
Estimating the term…
Abstract
A Pfield operation defined according to the Montgomery method by Pfield(A, B)N=A*B*I mod N, where I is a determinable error, is implemented in a processor. The least significant word of the data elements A and N which are stored in elementary sub-registers are shifted twice. This eliminates delay cells in a processor used for executing the Pfield operation.
Claims4
A method for implementing a Pfield operation defined according to the Montgomery method by Pfield(A, B)N=A*B*I mod N, with A, B and N being integers encoded respectively on α, b and n words of k bits, with N being an odd-parity number, with b and n being non-zero integers smaller than or equal to an integer m, and with α and m being non-zero integers, the method comprising the steps of:
- successively receiving words Ai−1 of k bits of A in a first k bit register;
- storing B in a second m*k bit shift register;
- storing an updated data element S(i) in a third m*k bit shift register;
- storing N in a fourth m*k bit shift register, the second to fourth registers being organized in banks of m sub-registers for enabling shifts by k bit words;
- performing a first k bit shifting of least significant words in the second to fourth registers for serial production of an intermediate data element Y0=((−N0−1mod 2k)*(B*Ai−1+S(i−1)) mod 2k for storing in a fifth k bit register;
- and
- performing a second n*k bit shifting of the words B, S(i−1) and N stored in the second to fourth registers for serial production of the updated data element S(i).
An integrated circuit for implementing a Pfield operation defined according to the Montgomery method by Pfield(A, B)N=A*B*I mod N, with A, B and N being integers encoded respectively on a, b and n words of k bits, with N being an odd-parity number, with b and n being non-zero integers smaller than or equal to an integer m, and with α and m being non-zero integers, the integrated circuit comprising:
- a processor including a plurality of registers, said processor comprising means for performing the following steps
- successively receiving words Ai−1 of k bits of A in a first k bit register,
- storing B in a second m*k bit shift register,
- storing an updated data element S(i) in a third m*k bit shift register,
- storing N in a fourth m*k bit shift register, the second to fourth registers being organized in banks of m sub-registers for enabling shifts by k bit words,
- performing a first k bit shifting of least significant words in the second to fourth registers for serial production of an intermediate data element Y0+((−N0−1mod 2k)*(B*Ai−1+S(i−1)) mod 2k for storing in a fifth k bit register, and
- performing a second n*k bit shifting of the words B, S(i−1) and N stored in the second to fourth registers for serial production of the updated data element S(i).
Dependencies are inferred from the claim text.