Back to search

University of Waterloo

Issues in Implementation of Public Key Cryptosystems

Abstract

dc:description.abstract

A new class of moduli called the low-weight polynomial form integers (LWPFIs) is introduced. LWPFIs are expressed in a low-weight, monic polynomial form, <em>p</em> = <em>f</em>(<em>t</em>). While the generalized Mersenne numbers (GMNs) proposed by Solinas allow only powers of two for <em>t</em>, LWPFIs allow any positive integers. In our first proposal of LWPFIs, we limit the coefficients of <em>f</em>(<em>t</em>) to be 0 and ±1, but later we extend LWPFIs to allow any integer of less than <em>t</em> for the coefficients of <em>f</em>(<em>t</em>). Modular multiplication using LWPFIs is performed in two phases: 1) polynomial multiplication in Z[<em>t</em>]/<em>f</em>(<em>t</em>) and 2) coefficient reduction. We present an efficient coefficient reduction algorithm based on a division algorithm derived from the Barrett reduction algorithm. We also show a coefficient reduction algorithm based on the Montgomery reduction algorithm. We give analysis and experimental results on modular multiplication using LWPFIs. <br /><br /> New three, four and five-way squaring formulae based on the Toom-Cook multiplication algorithm are presented. All previously known squaring algorithms are symmetric in the sense that the point-wise multiplication step involves only squarings. However, our squaring algorithms are asymmetric and use at least one multiplication in the point-wise multiplication step. Since squaring can be performed faster than multiplication, our asymmetric squaring algorithms are not expected to be faster than other symmetric squaring algorithms for large operand sizes. However, our algorithms have much less overhead and do not require any nontrivial divisions. Hence, for moderately small and medium size operands, our algorithms can potentially be faster than other squaring algorithms. Experimental results confirm that one of our three-way squaring algorithms outperforms the squaring function in GNU multiprecision library (GMP) v4. 2. 1 for certain range of input size. Moreover, for degree-two squaring in Z[<em>x</em>], our algorithms are much faster than any other squaring algorithms for small operands. <br /><br /> We present a side channel attack on XTR cryptosystems. We analyze the statistical behavior of simultaneous XTR double exponentiation algorithm and determine what information to gather to reconstruct the two input exponents. Our analysis and experimental results show that it takes <em>U</em><sup>1. 25</sup> tries, where <em>U</em> = max(<em>a</em>,<em>b</em>) on average to find the correct exponent pair (<em>a</em>,<em>b</em>). Using this result, we conclude that an adversary is expected to make <em>U</em><sup>0. 625</sup> tries on average until he/she finds the correct secret key used in XTR single exponentiation algorithm, which is based on the simultaneous XTR double exponentiation algorithm.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chung, Jaewook

Subjects

dc:subject × 7

Rights

dc:rights
Statement dc:rights
  • Copyright: 2006, Chung, Jaewook. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/2853

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chung, Jaewook. Issues in Implementation of Public Key Cryptosystems. University of Waterloo, 2006. http://hdl.handle.net/10012/2853