Patent ID: 6836784
Filing Date: 2004-12-28
Classification: G06F

Abstract:
A method for identifying an encryption value in a Finite field, FP, where P is a prime number, based on a private key PV and a received public key PB, comprising the steps of:determining a mathematical inverse of PB modulo P by performing the steps of: a) assigning P to a temporary variable U and assigning PB to a temporary variable V and assigning a value of zero to a temporary variable U2 and assigning a value of one to a temporary variable V2; b) selecting 2M most significant bits of U as a first value U2M and selecting 2M most significant bits of V as a second value V2M, dividing U2M by V2M and storing an integer portion of the result as a value Q; c) determining a value T as U minus the quantity Q times V; d) if T is less than zero, applying a correction term to Q to obtain a corrected value Qâ€² and assigning the new value for T as U minus the quantity Qâ€² times V; e) determining a value T2 as U2 minus Q times V2, assigning the value in V2 to U2, assigning the value T2 to U2, assigning V to U and T to V; and f) repeating steps a) through e) until V equals zero, whereby the value remaining in U2 is the mathematical inverse of PB; and dividing PV by PB modulo P by multiplying PV times the mathematical inverse of PB, wherein the result is the encryption value.