Patent ID: 7227947

Claim:
A cryptographic method in which computation time to perform modular exponentiation is reduced when carrying out an encryption and signature scheme by means of an electronic apparatus, and in which recovery of information on prime factorization based on a faulty result of a disturbed modular exponentiation is prevented, comprising the steps of: a) using said electronic apparatus to perform at least one computing step containing a modular exponentiation E E =x d (mod p·q ) with a first prime factor p, a second prime factor q, an exponent d and a base x, wherein b) for carrying out the modular exponentiation two natural numbers r and s are chosen with the condition that d is relatively prime to φ(kgV(r,s)), and wherein the following computing steps are performed: x 1 =x (mod p·r ) x 2 =x (mod q·s ) d — 1 =d (mod φ( p·r )) d — 2 =d (mod φ( q·s )) z 1 =x 1 d — 1 (mod p·r ) z 2 =x 2 d — 2 (mod q·s ) and wherein φ(.) is the Eulerian function and kgV(r,s) is the smallest common multiple of r and s, c) then a number z is calculated according to the Chinese Remainder Theorem from z 1 and z 2 with z=z 1 (mod p·r); z=z 2 (mod q·s); d) the result E of the exponentiation is calculated by reduction of z modulo p·q, e) the previously calculated number z and thus the result E is checked for computing errors in a checking step, f) the checking step comprises the following computing operations: f1) calculating the smallest possible natural number e with the property e·d=1(mod φ(kgV(r,s))) with the aid of the Extended Euclidean Algorithm, f2) calculating the value C=z e (mod kgV(r,s)), f3) comparing the values x and C modulo kgV(r,s), and rejecting the result of the modular exponentiation E as faulty if x≠C (mod kgV(r,s)), and f4) if x=C (mod kgV(r,s)), using the modular exponentiation to complete said encryption and signature scheme.