Error Detection in Arithmetic Operations over Elliptic Curves
Elliptic Curve Cryptography (ECC) is a class of cryptography which is based on the discrete logarithm problem (DLP). At the heart of ECC is an elliptic curve which is defined over an elliptic field consisting of a finite set of points with a set of arithmetic rules. Differences between standard arithmetic and elliptic curve arithmetic also lead to changes in fault detection schemes in ECC. In this simulator we explain a novel method of fault detection in elliptic curves known as the Point on Curve Method.
Fault detection is important in cryptography because in addition to random errors which may produce garbled results, intentionally induced errors (fault injection) can compromise the system. A simple example of an effective fault injection attack can be illustrated using RSA encryption. RSA is a well known algorithm which is based on the assumption that factoring a composite of two large primes is difficult. Encryption of message m using key e and public modulus n is the following arithmetic operation over real numbers:
me mod n
Since n is recommended to be at least 2048 bits, this operation is computationally expensive. A significant speed up can be achieved using the Chinese remainder theorem (CRT) because n is composed of two primes p and q. Typically p and q are roughly √n and computing me mod p and me mod q in parallel and then combining them using the CRT results in significant speedup. If a designer uses this common trick without adequate fault detection then an attacker can extract p and q, breaking the system.
To extract p and q (and thus break the system) the attacker tries to induce a fault in the register that holds either p or q. If a fault is successfully induced, the result of the CRT will be mod n' where n' is no longer composed of two large primes and the system can be broken. While this example is specific to RSA with CRT, other fault injection techniques are more general and apply to ECC algorithms.