Document Type Master's Dissertation Author Joseph, George 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 Supervisor

Advisor Name Title Prof W T Penzhorn Keywords

- 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 AbstractThe 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 formA=gmod^{e}mwheregis the base,eis the exponent andmis 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

pandq. The resulting reduction of the decryption exponent improves the decryption speed by approximately 45%.Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access 00dissertation.pdf926.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.