Left-to-Right Recoded NAF* for RFID Tags

摘要

Efficient implementations of cryptosystems are important for resource-limited devices, e.g. RFID tags, to compute necessary cryptographic operations. To reduce the number of cryptographic operations, a signed digit representation for a scalar is the most useful method. A signed digit representation can reduce the nonzero density of the representation. King introduced a left-to-right representation called NAF* (non-adjacent form*) which nonzero density is the same as NAF and MOF (mutual opposite form). In this paper, we will propose a modified NAF*, and demonstrate that it is more efficient than the original NAF*. The recoding time of modified NAF* achieves at least 64.5% time reduction supported by simulation results.