Chinese remainder theorem-based computation method for cryptosystems

摘要

A computer hardware implemented cryptography method computes a modular exponentiation, M :=Cd (mod p·q), upon a message data value C using a Chinese Remainder Theorem (CRT) based technique. To secure against cryptanalysis, the private key moduli p and q are transformed by multiplication with a generated random value s, so that p′: =p·s and q′:=q·s, as shown in an exemplary embodiment in FIG. 2. The CRT steps of the modular exponentiation are applied using the transformed moduli p′and q′to obtain a random intermediate message data value M′. A final reduction of M′modulo p·q yields the final message data value M. Values needed for the computation are loaded into data storage and accessed as needed by electronic processing hardware.