Method for simultaneous modular exponentiations

An article comprising a computer readable, non-transitory storage medium having stored thereon instructions that when executed by a machine result in the following:

• generating a first remainder (Xp) based on an encrypted message (X) modulo a first prime number (p);
• generating a second remainder (Xq) based on the encrypted message (X) modulo a second prime number (q);
• generating 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 simultaneously generating a fourth remainder (v2) based on the second remainder (Xq) raised to a second private key number (d2) modulo the second prime number (q);
• subtracting the fourth remainder (v2) from the third remainder (v1) to yield a result (v1−v2);
• multiplying the result (v1−v2) by a constant (c) to produce a second result;
• generating a sixth remainder (h) by taking the second result modulo the first prime number (p);
• multiplying the sixth remainder (h) by the second prime number (q) to produce a third result;
• adding the third result and the fourth remainder (v2) to yield a final result (Y);
• and
• generating, at least in part, a public key based on the final result (Y).

A system comprising:

• a plurality of line cards and a switch fabric interconnecting said plurality of line cards, at least one line card comprising:
• at least one physical layer component (PHY);
• and
• 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 on the final result (Y).