Modular multiplication in GF(p) for public-key cryptography

Distributed measurement systems (DMS) and wireless sensor networks (WSN) are becoming main applications for modern applied metrology. These systems are severely resource constrained, usually we have to deal with tiny autonomous nodes with very limited computational resources and very limited energy source. Integration into existing infrastructure (i.e. the Internet) and usage of unsecure transmission channels (wireless) make information security of the system a crucial problem. Cryptography provides tools for solving this problem, however, resource constraints influence methods of securing such systems (algorithms, protocols, circuits).

Use of Public Key Cryptography (PKC) simplifies the implementation of many typical security services in WSN and improves scalability of the entire system. In addition PKC potentially reduces transmission power due to less protocol overhead and increases physical security (since no globally shared secrets are stored). Modular multiplication forms the basis of modular exponentiation which is the core operation of the RSA cryptosystem. It is also present in many other cryptographic algorithms including those based on ECC and HECC. Hence, an efficient implementation of PKC relies on efficient modular multiplication.

The paper presents a survey of most common algorithms for modular multiplication along with hardware architectures especially suitable for cryptographic applications in sensor networks. Analysis of the most popular types of modular multiplication algorithms is presented and serial architectures for prime fields GF(p) are discussed. Finally solutions which are suitable to DMS specific requirements according to cryptographic security, computational efficiency (throughput) and complexity of implementation (VHDL targeted at FPGA and ASIC devices) are selected. Strong asymmetry of computing power and memory capacity is taken into account in both software and hardware solutions.