# Using the Elliptic Curve Digital Signature Algorithm (ECDSA) with the DeepCover Secure Microcontroller's (MAXQ1103) Modular Arithmetic Accelerator (MAA)

Abstract: This application note describes the use and implementation of elliptic curve digital signature algorithm (ECDSA) on the DeepCover

^{®}Secure Microcontroller's (MAXQ1103) modular arithmetic accelerator (MAA) module. Performance figures are given for a standard 160-bit curve specified in

__Standards for Efficient Cryptography__published by Certicom

^{®}.

## Overview

## Introduction

## Terminology

- Ғ
_{p}is the finite field of order p - G(x,y) is the function G, taking two variables x and y
- * means scalar multiplication carried out by repeated addition
- [ and ] function as normal arithmetical grouping operators

## The Inner Workings of ECDSA

*Online Elliptic Curve Cryptography Tutorial*.² This tutorial will guide the reader on elliptic curve point multiplication and addition.

_{p}, obtaining a public key Q(x,y). Equation 1 represents the generation of Bob's public key.

Q(x,y) = [G(x,y) * d] mod p | (Eq. 1) |

_{p}. The result is an affine coordinate point (x

_{1},y

_{1}). The nonmessage portion of the signature is r = x

_{1}mod n, and y

_{1}is discarded. For ECDSA, Ғ

_{n}is a superset of Ғ

_{p}. Thus, Bob does not actually need to run the modulo operation over x

_{1}to obtain r. Equation 2 shows the generation of r.

(x_{1},y_{1}) = [G(x,y) * k] mod pr = x _{1} mod n |
(Eq. 2) |

^{-1}. Then, he multiplies his secret key (d) by the r value found in the previous equation, adds the result to the message hash value H(m), and multiplies the entire result by k

^{-1}. All operations for s are performed in the field Ғ

_{n}. Equation 3 shows the generation of s.

s = [k^{-1} * (H(m) + d * r)] mod n |
(Eq. 3) |

_{n}, excluding the element 0 (i.e., [1 ... n-1]). Should this check fail, the signature is immediately declared invalid. Next, several intermediate products are computed in Equations 4, 5, and 6 for signature verification.

w = s^{-1} mod n |
(Eq. 4) |

u1 = [H(m) * w] mod n | (Eq. 5) |

u2 = [r * w] mod n | (Eq. 6) |

(x_{2},y_{2}) = [u1 * G(x,y) + u2 * Q(x,y)] mod n |
(Eq. 7) |

_{2}as a scalar against the r coordinate of Bob's signature. If they match exactly, then the signature is authentic. Otherwise, the signature is invalid.

## Theory into Practice: DeepCover Secure Microcontroller (MAXQ1103) ECDSA Performance

^{®}Secure Microcontroller (MAXQ1103), the ECDSA signature and verify routines are very efficient for a microcontroller of its class. The implementation utilizes the MAXQ1103's integrated MAA running at approximately 55MHz. As the MAA is clocked from a free-running ring oscillator, the exact speed and timing cannot be known precisely, which adds a layer of defense against differential power-analysis cryptographic attacks.

Table 1. Timing for ECDSA Operations over the p160r1 Curve | ||

Operation | 160-Bit Normal | 160-Bit Accelerated |

Key Generation | 77ms | 18ms |

Sign | 75ms | 19ms |

Verify | 148ms | 79ms |

**Table 1**shows the nominal timings for ECDSA routines for a 55MHz MAA clock. The 160-bit elliptic curve p160r1 was selected from Certicom Research's

*Recommended elliptic curve domain parameters*.¹ Of course, some of the nonmodular computational work is done by the MAXQ1103 CPU, which will affect the timings to a small degree, depending on the core frequency selected.

## Conclusion

#### References

*SEC 2: Recommended elliptic curve domain parameters*, September, 2000 (www.secg.org/secg_docs.htm).

² www.certicom.com/index.php?action=ecc_tutorial,home.

³ A. Menezes, et al.,

*Handbook of Applied Cryptography*, 1st ed. (CRC Press, 2001).