High speed modular exponentiator

A method for computing a cryptographic key with improved computational efficiency, based on a modular exponentiation of the form be mod n comprises the steps of:

• dividing said modular exponentiation into at least first and second portions respectively having reduced modulus values p and q, and a reduced base value bI, than an original modulus value n and base value b of said modular exponentiation;
• factoring each portion of said modular exponentiation into respective pluralities of smaller modular exponentiations having precalculated exponent values;
• multiplying said respective pluralities of smaller modular exponentiations together to provide respective first level intermediate products, said multiplying step further comprising selectively reducing a total number of operations of said multiplying step for squaring of said respective pluralities of smaller modular exponentiations;
• subtracting said respective intermediate products from each other and adding one of said reduced modulus values to provide an intermediate sum value;
• multiplying said intermediate sum value with a precalculated inverse value to provide a second level intermediate product;
• calculating a modular reduction of said second level intermediate product with respect to one of said reduced modulus values;
• multiplying said modular reduction of said second level intermediate product with the other one of said reduced modulus values;
• adding one of said first and second modular exponentiation portions to said second level intermediate product to provide a final modular exponentiation product;
• and
• employing the final modular exponentiation product to define said cryptographic key.

A method of decrypting data encrypted with an encryption key, wherein a decryption key is provided by computation of a modular exponentiation of the form be mod n based on the encryption key, comprising:

• dividing said modular exponentiation into at least first and second portions respectively having reduced modulus values p and q, and a reduced base value bI, than an original modulus value n and base value b of said modular exponentiation;
• factoring each portion of said modular exponentiation into respective pluralities of smaller modular exponentiations having precalculated exponent values;
• multiplying said respective pluralities of smaller modular exponentiations together to provide respective first level intermediate products, said multiplying step further comprising selectively reducing a total number of operations of said multiplying step for squaring of said respective pluralities of smaller modular exponentiations;
• subtracting said respective intermediate products from each other and adding one of said reduced modulus values to provide an intermediate sum value;
• multiplying said intermediate sum value with a precalculated inverse value to provide a second level intermediate product;
• calculating a modular reduction of said second level intermediate product with respect to one of said reduced modulus values;
• multiplying said modular reduction of said second level intermediate product with the other one of said reduced modulus values;
• and
• adding one of said first and second modular exponentiation portions to said second level intermediate product to provide a final modular exponentiation product;
• and
• employing the final modular exponentiation product to define said cryptographic key.

A system for decrypting data encrypted with an encryption key, wherein a decryption key is provided by computation of a modular exponentiation of the form be mod n based on the encryption key, comprising:

• means for dividing said modular exponentiation into at least first and second portions respectively having respective reduced modulus values p and q which are each smaller than an original modulus value n of said modular exponentiation, and a respective reduced base value bi which is smaller than an original vase value b;
• means for factoring each said portion of said modular exponentiation into respective pluralities of smaller modular exponentiations using precalculated exponent values;
• means for multiplying said respective pluralities of smaller modular exponentiations together to provide respective first level intermediate products, said multiplying means being optimized for squaring operations;
• means for combining said intermediate products into a final modular exponentiation product, and
• a processor unit coupled to receive said final modular exponentiation product and define said decryption key based on the final modular exponentiation product, said processing unit including means for decrypting said encrypted data using said decryption key.