Patent ID: 6795553
Filing Date: 2004-09-21
Classification: G06F

Abstract:
A method of calculating modular inversion R of an input value X over a residue class ring Z/NZ or finite field GF(p) for information security service, comprising the steps of:(a) calculating Y for input values X and N given as pieces of security information, by the following equation using a predetermined value t Y=X2âˆ’t mod N; where said N is a part of cryptographic key information employed in the security service, the input value X is calculated from an encrypted message, a digital signature, a random number or a message to be encrypted and the bit size of each of said X and N is n and said X is equal to or greater than 0 and less than said N, n being an integer equal to or greater than 1; (b) calculating S and k for said Y and N by an extended GCD method expressed by bgcd (Y,N) defined as follows: S=bgcd(Y, N)=Yâˆ’12k mod N; and(c) performing the following calculation using said S, k and t R=S2âˆ’(k+tâˆ’m) mod N where m=0, n, or 2n and outputting said R as the result of said modular inversion of said input value X to be used for calculation of an encrypted message, a decrypted message or a digital signature in the information security service.