Date of Award

5-1-2014

Degree Type

Thesis

Degree Name

Master of Science

Department

Computer Science

First Advisor

Guangwu Xu

Committee Members

Christine Cheng, Adrian Dumitrescu

Keywords

Cryptography, Elliptic Curve, Koblitz, Tau NAF, TNAF, Window Tau NAF

Abstract

This paper examines scalar multiplication on Koblitz curves employing the Frobenius endomorphism. We examine simple binary scalar multiplication, binary Non Adjacent Formats or NAF's, followed by τ-NAF methods. We pay particular attention to width-τ-NAF where we focus on pre-computation. We present alternative pre-computation arrangements for αu for width sizes of 5 and 6 which are better than any previously published results since they: involve a single power of τ are based on least norms; and have a maximum of 2w - 2 - 1 elliptic curve operations. We then study widths of 7 and 8 producing efficient arrangements. Arrangements for width sizes of 7 and 8 have never before appeared in the literature.

Furthermore, we introduce a simplified rounding technique for reduction modulo (τm - 1)/(τ - 1) relaxing the requirement of least norms. Lastly, we discuss an O(n) technique for finding arbitrary powers of &tau in software.

Download

Share

COinS