Elliptic Curve Cryptoprocessor with Hierarchical Security

摘要

This paper describes an elliptic curve scalar multiplication method which is resistant to power analysis attacks. The proposed method confuses both the private key bit values and positions. Even with correct leaked information on the type of operations performed, associating that with a particular key bit value or position is almost impossible. Resistance to side channel attacks is provided at several levels. At the top level, the secret key is segmented into a number of randomly sized segments processed in random order. At the segment level, each segment is encoded randomly using NAF or binary encodings. Further, at the segment level, the inspection direction of segment bits for binary-encoded segments is randomly assigned either in MSB-to-LSB or LSB-to-MSB. Furthermore, at the individual segment bit level, zero bits can randomly trigger a dummy PADD operation. In addition to improved security, this results in an average saving of 50% over the number of dummy PADDs in the Double-and-Add-Always algorithm. Such hierarchical multi-level scheme causes the relation between the private key and possible leaked information to be quite confused resulting in a higher system security with minimal overhead for both speed and area.