## 4 Proposed Binary Field Multiplication
### Enhanced Secure Block-Comb Method  
[PERSON] et al. 's utilized \(n\) garbage registers equal to the number of real accumulator registers (namely, eight registers were used as the garbage register set). Our method makes use of a single garbage register rather than using \(n\) garbage register. The security analysis of using a single garbage register is described in Section 4.4. The saved registers can be used for extending the block size of the Block-Comb method. If the Block-Comb method with a garbage register uses block size \(s\), the number of total registers is \((4s+2)\): 1, \(s\), \(s+1\), 2\(s\) are for the garbage register, the multiplier, the multiplicand, and the accumulator. Since on 8-bit AVR MCUs 26 registers are available except for address registers, the block size \(s\) can be 6 (48-bit). Since [PERSON] et al. utilized the 32-bit secure Block-Comb technique for calculating 128-bit \(BF\) multiplication, 9 partial products were required (actually, they integrate their secure Block-Comb method into the Karatsuba technique. Thus, 16 partial products are reduced into 9 partial products). With the 48-bit wise Block-Comb method, 128-bit operands are divided into three terms. Thus, the 128-bit \(BF\) multiplication can be computed with 6 partial products by integration with the Karatsuba technique. Even though by using a garbage register the block size of the secure Block-Comb method has been extended from 4 to 6, it still does not reach the maximum block size 8, which was presented from the work of the non-constant Enhanced Karatsuba Block-Comb method [9]. In order to expand the block size of the Block-Comb multiplication method from 6 to 8, it is required to reserve more registers. However, since on 8-bit AVR MCUs the available registers are only 26 except for address registers, one of register sets for maintaining each of multiplier, multiplicand, or accumulator needs to be reduced. Common Block-Comb methods load \(s\) bytes of the multiplier into \(s\) registers (at Step 4\(\sim\)7 of Algorithm 1 in Appendix A) and sequentially access \(l\)-th bit of \(s\) registers where \(l\) is from 0 to 7 (at Step 11 of Algorithm 1 in Appendix A). Figure 1 shows the multiplier accessing pattern of Algorithm 1 in Appendix A. Since the bits being accessed are distributed in \(s\) registers, they require \(s\) registers for accessing the multiplier. Thus, we encode the multiplier so that the bits being accessed are in one register [9]. In other words, by rearranging \(l\)-th bit of \(s\) registers into one register, steps 10\(\sim\)16 of Algorithm 1, the main inner loop of the Block-Comb method, requires only one register at a time. Algorithm 2 depicts a 128-bit wise multiplier encoding process. The algorithm makes use of AVR bit handling instructions as LSR (logical shift right), ROR (rotate right through carry). Figure 2 shows the encoded multiplier from bit reordering-based multiplier encoding process when the multiplier is 128-bit, which can be used for \(BF\) multiplication in the GHASH function of GCM. The encoding process operates on 64-bit wise so that \(i\)-_th_ encoded byte \(EB[i]\) contains 0-th bit of original multiplier \(B[0]\sim B[7]\). With the application of multiplier encoding, our method loads \(l\)-th bit of original multiplier's \(s\) bytes into one register. Thus, our method requires (35+3) registers for computing a Block-Comb method (namely, 1, 1, \(s+1\), and 2\(s\) registers are for the multiplier, the garbage register, the multiplicand, and real accumulator, respectively). Even though \(s\) value is 7, satisfying \(3s+3\leq 26\), we can extend the block size from 7 to 8 by using exploiting the address registers (\(r_{31},\ldots,r_{26}\)). Actually, address registers can be used as arithmetic registers. In other words, the memory address for the final result is needed only when storing the final multiplication result in the accumulators into the memory at the end of the \(BF\) multiplication.