Document Type Master's Dissertation Author Abu-Mahfouz, Adnan Mohammed I Ami.Mahfouz@gmail.com URN etd-06082005-144557 Document Title Elliptic curve cryptosystem over optimal extension fields for computationally constrained devices Degree MEng (Computer Engineering) Department Electrical, Electronic and Computer Engineering Supervisor
Advisor Name Title Prof G P Hancke Committee Chair Keywords
- Elliptic Curve
- Discrete Logarithm Problem
- Itoh Tsujii Inversion
- Karatsuba algorithm
- Extended Euclidean algorithm
- Schoolbook method
- Addition Chain algorithm
- Non-Adjacent Form
- Quadratic Residue
- Legendre Symbol
- Embedded System
- Finite field
- Optimal Extension Field
Date 2004-12-03 Availability unrestricted AbstractData security will play a central role in the design of future IT systems. The PC has been a major driver of the digital economy. Recently, there has been a shift towards IT applications realized as embedded systems, because they have proved to be good solutions for many applications, especially those which require data processing in real time. Examples include security for wireless phones, wireless computing, pay-TV, and copy protection schemes for audio/video consumer products and digital cinemas. Most of these embedded applications will be wireless, which makes the communication channel vulnerable.
The implementation of cryptographic systems presents several requirements and challenges. For example, the performance of algorithms is often crucial, and guaranteeing security is a formidable challenge. One needs encryption algorithms to run at the transmission rates of the communication links at speeds that are achieved through custom hardware devices.
Public-key cryptosystems such as RSA, DSA and DSS have traditionally been used to accomplish secure communication via insecure channels. Elliptic curves are the basis for a relatively new class of public-key schemes. It is predicted that elliptic curve cryptosystems (ECCs) will replace many existing schemes in the near future. The main reason for the attractiveness of ECC is the fact that significantly smaller parameters can be used in ECC than in other competitive system, but with equivalent levels of security. The benefits of having smaller key size include faster computations, and reduction in processing power, storage space and bandwidth. This makes ECC ideal for constrained environments where resources such as power, processing time and memory are limited.
The implementation of ECC requires several choices, such as the type of the underlying finite field, algorithms for implementing the finite field arithmetic, the type of the elliptic curve, algorithms for implementing the elliptic curve group operation, and elliptic curve protocols. Many of these selections may have a major impact on overall performance. In this dissertation a finite field from a special class called the Optimal Extension Field (OEF) is chosen as the underlying finite field of implementing ECC. OEFs utilize the fast integer arithmetic available on modern microcontrollers to produce very efficient results without resorting to multiprecision operations or arithmetic using polynomials of large degree. This dissertation discusses the theoretical and implementation issues associated with the development of this finite field in a low end embedded system. It also presents various improvement techniques for OEF arithmetic.
The main objectives of this dissertation are to
--Implement the functions required to perform the finite field arithmetic operations.
-- Implement the functions required to generate an elliptic curve and to embed data on that elliptic curve.
-- Implement the functions required to perform the elliptic curve group operation.
All of these functions constitute a library that could be used to implement any elliptic curve cryptosystem. In this dissertation this library is implemented in an 8-bit AVR Atmel microcontroller.
© 2004, University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria
Please cite as follows:
Abu-Mahfouz, AM 2004, Elliptic curve cryptosystem over optimal extension fields for computationally constrained devices, MEng(Computer Engineering) dissertation, University of Pretoria, Pretoria, viewed yymmdd < http://upetd.up.ac.za/thesis/available/etd-06082005-144557 / >
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access 00dissertation.pdf 846.12 Kb 00:03:55 00:02:00 00:01:45 00:00:52 00:00:04