Inverse calculation device, reverse the original calculation method, RSA key pair generation device, RSA key pair generation method

摘要

PROBLEM TO BE SOLVED: To provide an inverse element calculation unit in which the division of many precisions is not used, of which memory capacity is reduced, and which determines an inverse element on a residue class ring in which the value of a divisor is even.;SOLUTION: The inverse element calculation unit consists of: the divisor unit which acquires M and t which satisfies N=M×2^t (M is the odd number), and a first inverse element calculation unit which calculates the inverse element on the residue class ring which makes the divisor as the acquired value M, for the value of the divisor whose number is even; and a second inverse element calculation unit which calculates the inverse element on the residue class ring which makes 2^t as the divisor, and a synthetic calculation unit which calculates the inverse element on the residue class ring which makes N as the divisor from a value acquired with each inverse element calculation unit, for the acquired t. Thus, the inverse element calculation is calculated by controlling every calculation units.;COPYRIGHT: (C)2004,JPO