## 2 Related Works
### Eight-Bit AVR Microcontrollers and Notations  
Currently, devices using 8-bit AVR are broadly used for diverse applications, like RFIDs, smartcards, embedded controllers, wireless sensor nodes, and so on. Typically, 8-bit AVR MCUs, including our target platform ATmega128, contain 32 general-purpose registers (\(R_{31},\ldots,R_{1},R_{0}\)). Among 32 registers, six registers are utilized as memory address pointers. Each set of (\(R_{26}\),\(R_{27}\)), (\(R_{28}\),\(R_{29}\)), and (\(R_{30}\),\(R_{31}\)) are aliased as \(X\), \(Y\), and \(Z\) pointer registers, respectively [13]. Typically, AVR MCUs have not only individual memory spaces but also buses for data and program instructions in a simple single-issued pipeline manner, since their architecture is based on the Harvard architecture. There are 133 instructions in total, and typically, each instruction executes in constant latency. For instance, logical/arithmetic instructions (e.g., ROR (rotate right through carry), LSL (logical shift left), EOR (bit-wise XOR), ADD (arithmetic add), and so forth) are executed within a single clock cycle, while instructions related to memory accesses (e.g., ST (store from register to memory), LD (load from memory to register), and so on) consume two clock cycles [13]. In the case of conditional branch instructions, their clock cycles depend on whether the tested condition is true or not. For instance, in the case of SBRS (skip next instruction if bit in register is set), if the condition is true, it takes up two or three cycles depending on the skipped instruction's word size. Otherwise, it consumes one cycle. The memory and computation capabilities of 8-bit AVR MCUs are limited. For example, an 8-bit ATmega128 MCU has 4 Kbytes of RAM and 128 Kbytes of ROM memory, and its running clock speed is 7.3728 MHz. Contrary to the state-the-of-art ARM MCUs and Intel CPUs providing a carryless multiplier and generic binary field hardware multiplier, AVR MCUs still do not embed the dedicated hardware multiplier. All through our paper, the following notations are used. The general purpose registers are represented as \(R\). \(R_{i}\) means to the \(i\)-th general-purpose register in which \(0\leq i\leq 31\). The operators \(\gg\), \(\ll\) and \(\oplus\) mean logical right shifts, logical left shifts, and XOR operation. \(A[i]\) refers to the \(A\)'s \(i\)-th byte and it consists of 8 bits like \((a_{8i+7},\ldots,a_{8i})\). Finally, \(A[n,\ldots,m]\) corresponds to the bytes from \(A[m]\) to \(A[n]\), respectively. Multiplication over Binary Field  
Binary Field (\(BF\)) multiplication is a core operation of several cryptographic algorithms, such as the GHASH function of GCM and NIST-compliant binary elliptic curve operations. For example, in the GHASH function of GCM, \(BF\) multiplications are executed with input operands as associated data blocks or ciphertext blocks, and a secret constant hash key \(H\). In the case of binary ECC, scalar multiplication is the most performance-critical part of the entire ECC-based protocols and its almost 80% running time comes from \(BF\) multiplications. Thus, the performance of \(BF\) multiplication needs to be optimized as much as possible. \(BF\) multiplication computes \(A\cdot B\) where \(A=\sum_{i=0}^{m-1}a_{i}z^{i}\), \(B=\sum_{i=0}^{m-1}b_{i}z^{i}\in GF(2^{m})\) where \(m\) is the degree of the underlying binary extension field. In the above notation, each multiplicand and multiplier are represented as \(A\) an \(B\), respectively. The result of the multiplication can be represented as \(C=\sum_{i=0}^{m-1}A\cdot b_{i}z^{i}\). The most basic algorithm for a multiplication over a binary field is the Shift-and-Add method. It scans the multiplier from LSB (Least Significant Bit, the 0-th bit) to MSB (Most Significant Bit, the \((m-1)\)-th bit).