Patent ID: 7177423

Claim:
A method of computing an exponent of a message m in an RSA cryptosystem having a private key d, a public key e and system parameters p, q where p and q are primes and ed=1 mod (p−1) (q−1), said method comprising the steps of obtaining a value r, and exponentiating said value r to the power e to obtain an exponent r e mod p, combining said exponent r e with said message m to obtain a combined value r e m and mod p; selecting a value s and obtaining a difference (d−s), exponentiating said combined value with said difference to obtain an intermediate exponent (r e m) d−s , multiplying said intermediate exponent by a value m s to obtain a resultant value equivalent to r 1−es m d and multiplying said resultant value by a value corresponding to r 1−es to obtain an exponent corresponding to m d mod p.