# PAGE--Practical AES-GCM Encryption for Low-End Microcontrollers
## 3 Face-Light: Fast AES-CTR Mode Encryption for Low-End Microcontrollers
### Karatsuba Algorithm for GHASH  
Karatsuba algorithm is well known asymptotically fast multiplication method and the proposed implementation also utilizes the Karatsuba algorithm for high performance. First, the multiplication is performed with lower 32-bit of 64-bit operands (\(A[3\sim 0],B[3\sim 0]\)) and 64-bit result (\(L\)) is obtained. Second, the multiplication is performed with lower 32-bit of 64-bit operands (\(A[7\sim 4],B[7\sim 4]\)) and 64-bit result (\(H\)) is obtained. Third, XOR operation is performed between the upper part and the lower part of the \(A\) and \(B\), respectively. Values are multiplied and output the final result (\(M\)). The \(L\), \(H\), and \(M\) are XORed together and stored in \(M\), again. Lastly, shifted \(H\) (\(H\ll 64\)), shifted \(M\) (\(M\ll 32\)) and \(L\) are XORed and the final 128-bit result (\(C\)) is obtained. Karatsuba algorithm needs a buffer to store intermediate results of each operation. In the Block Comb method proposed by [PERSON] and [PERSON], the size of intermediate results is over than given size of general purpose registers. For this reason, the part of intermediate result should be stored in STACK. However, accessing to STACK memory (i.e., 2 clock cycles) requires high-overheads than register accesses (i.e., 1 clock cycle). The proposed method uses eight more registers to maintain the intermediate result. For the register optimized version, the intermediate result is stored in STACK memory. In Algorithm 2, the proposed implementation does not reserve the intermediate result of the Karatsuba calculation, such as \(L\), \(H\), and \(M\), in the STACK. Instead, only values needed for the following operation are stored using the \(K0\) to \(K7\) registers. ```
1:ROUND32
2:STD 2+0,
3:STD 2+1,
4:STD 2+1,
5:STD 2+3,
6:EDR 50,
7:EDR 51,
8:EDR 52,
9:EDR 53,
10:ROUND32
11:MOVW 50,



### Fast Reduction for GHASH

In order to optimize the modular operation, the fast reduction modulo algorithm by [PERSON] and [PERSON] [16] was applied to the proposed implementation. The algorithm optimizes the reduction operation with an irreducible polynomial (\(x^{128}+x^{7}+x^{2}+x+1\)) in a 64-bit environment. The algorithm is optimized for 8-bit AVR platforms. In Algorithm 3, input values (\(K[0]\sim K[31]\)) were reflected in advance. This is the reason why all of operations are reversed to the existing original algorithm. The algorithm requires a number of bit-wise shift operation. The 8-bit wise shift operation is optimized away. ```
0: : 256-bit data \(K[0],...,K[31]\), where \(K[0\sim 31]\) are 8-bit long each. 0: : \(K[16],...,K[31]\) (reduced result). 1: \(A\leftarrow(K[31]\) & \(0\)\(\pm 0\)\(\pm 6\)
2: \(B\leftarrow(K[31]\) & \(0\)\(\pm 0\)\(\pm 5\)
3: \(C\leftarrow(K[31]\) & \(0\)\(\pm 111\)\(\pm 111\))
4: \(K[16]\gets K[16]\oplus((A\bigoplus B\oplus C)\ll 1)\)
5: \(K[8]\gets K[8]\oplus K[24]\oplus((K[23]\ll 7)\mid(K[24]\gg 1))\oplus((K[2 3]\ll 6)\mid((K[24]\gg 2)))\oplus((K[23]\ll 1)\mid(K[24]\gg 7))\)
6: \(K[0]\gets K[0]\oplus K[16]\oplus(K[16]\oplus 2)\oplus(K[16]\gg 7)\)
7:for\(l=1\) to 7 do
8: \(K[i+8]\leftarrow K[i+8]\oplus K[i+24]\oplus((K[i+23]\ll 7)\mid(K[i+24] \gg 1))\oplus((K[i+23]\ll 6)\mid(K[i+24]\gg 2))\oplus((K[i+23]\ll 1)\mid(K[i+24]\gg 7))\)
9: \(K[i]\gets K[i]\oplus K[i+16]\oplus((K[i+15]\ll 7)\mid(K[i+16]\gg 1))\oplus((K[i +15]\ll 6)\mid(K[i+16]\gg 2))\oplus((K[i+15]\ll 1)\mid(K[i+16]\gg 7))\)
10:endfor
```

**Algorithm 3** Proposed method for fast modular reduction. ## 5 Evaluation

Low-end 8-bit AVR microcontrollers were used to run the proposed method. Arduino UNO board equipped with the ATmega328 microcontroller working at 16 MHz is used. The size of FLASH, EEPROM, and internal SRAM is 32 KB, 1 KB, and 2 KB, respectively. 32 8-bit general purpose registers and 131 instructions are supported. The code is complied in -OS option and the executiong timing is measured in clock cycles. The software is implemented over Arduino IDE and Atmel Studio 7. Majority of implementation is written in assembly language.