RSA signature authentication with reduced computational burden

摘要

Methods and apparatuses enable quick authentication of a Rivest, Shamir, and Adleman (RSA) compliant signature by performing non-modular arithmetic operations on one or more pre-computed constants in place of at least one modular arithmetic operation. In one embodiment, the signature is authenticated by computing S^E (mod N) by performing k non-modular arithmetic squaring operations, k+1 non-modular arithmetic subtraction operations, k+2 non-modular arithmetic multiplication operations, and no modular arithmetic, where S is the RSA compliant signature, E is the exponent of a public key, N is the modulus of the public key, and k is a positive integer where E=2^k+1.