Patent ID: 7925011

Claim:
An apparatus, comprising: an integrated circuit (IC) configured to calculate a first remainder (Xp) based on an encrypted message (X) modulo a first prime number (p); the IC further configured to calculate a second remainder (Xq) based on the encrypted message (X) modulo a second prime number (q); the IC further configured to calculate a third remainder (v1) based on the first remainder (Xp) raised to a first private key number (d1) modulo the first prime number (p) and to simultaneously calculate a fourth remainder (v2) based on the second remainder (Xq) raised to a second private key number (d2) modulo the second prime number (q); the IC further configured to subtract the fourth remainder (v2) from the third remainder (v1) to yield a result (v1−v2) and to multiply the result (v1−v2) by a constant (c) to produce a second result; the IC further configured to calculate a sixth remainder (h) by taking the second result modulo the first prime number (p) and to multiply the sixth remainder (h) by the second prime number (q) to produce a third result; the IC further configured to add the third result and the fourth remainder (v2) to yield a final result (Y) and to generate, at least in part, a public key based upon the final result (Y).