Title page for ETD etd-06092005-122043

Document Type Master's Dissertation
Author Joseph, George
Email josephg1@telkom.co.za
URN etd-06092005-122043
Document Title Design and implementation of high-speed algorithms for public-key cryptosystems
Degree MEng (Electronics)
Department Electrical, Electronic and Computer Engineering
Advisor Name Title
Prof W T Penzhorn
  • modular multiplication
  • modular reduction
  • RSA decryption
  • Montgomery reduction
  • Karatsuba-Ofman multiplication
  • addition chains
  • Chinese remainder theorem
  • public-key cryptosystems
  • RSA
  • modular exponentiation
Date 2005-03-15
Availability unrestricted
The aim of this dissertation is to improve computational efficiency of modular exponentiation-based public-key cryptosystems. The operational speed of these public-key cryptosystems is largely determined by the modular exponentiation operation of the form A = ge mod m where g is the base, e is the exponent and m is the modulus. The required modular exponentiation is computed by a series of modular multiplications.

Optimized algorithms are required for various platforms, especially for lower-end platforms. These require the algorithms to be efficient and consume as little resources as possible. In these dissertation algorithms for integer multiplication, modular reduction and modular exponentiation, was developed and implemented in software, as required for public-key cryptography. A detailed analysis of these algorithms is given, as well as exact measurement of the computational speed achieved by each algorithm.

This research shows that a total speed improvement of 13% can be achieved on existing modular exponentiation based public-key cryptosystems, in particular for the RSA cryptosystem. Three novel approaches are also presented for improving the decryption speed efficiency of the RSA algorithm. These methods focus on the selection of the decryption exponent by careful consideration of the difference between the two primes p and q. The resulting reduction of the decryption exponent improves the decryption speed by approximately 45%.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  00dissertation.pdf 926.29 Kb 00:04:17 00:02:12 00:01:55 00:00:57 00:00:04

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact UPeTD.