Patent ID: 6240436
Filing Date: 2001-05-29
Classification: G06F

Abstract:
A method of computing a modular exponentiation 2.sup.2k mod(n) for use in a cryptographic system using a processor accepting an m-bit operand, wherein n is a modulus value, and k is a number of bits used to represent n, comprising the steps of:configuring a first register such that there is a one in a 2.sup.(h*m)+1 bit position of the first register and a zero in all less significant bit positions in the first register, wherein h is the smallest integer such that the product (h*m) is not less than k;loading k bits representing the value of n into a second register, the second register comprising an integer multiple of m bit positions;shifting the k bits representing the value of n in the second register in a most significant bit direction until the most significant non-zero bit of n is at a bit position defined by an integer multiple of m;repeatedly subtracting the value of the second register from the first register until the value of the first register is less than the value of the modulus n;squaring the modularly reduced value in the first register log.sub.2 (k) times to produce the value 2.sup.2k mod(n), where log.sub.2 (k) is an integer;employing the value 2.sup.2k mod(n) for determining a cryptographic key.