Reasonably Efficient RSA Encryption/Decryption with C++
Author: Samuel WilliamsWhen: Thursday, 19 August 2010
I have implemented RSA encryption and decryption using C++, along with support functions such as key generation. This implementation is purely academic and does not take into consideration many important real-world security issues. Several of the multiple precision integer algorithms were developed and implemented from the book Handbook of Applied Cryptography. I wrote some documentation for my implementation, which may be helpful if you are making your own implementation.
This implementation supports both single precision and multiple precision (a.k.a. big integer) mathematics. Several optimised functions are implemented including Barrett Modular Reduction.
This code is suitable for key size up to 1024 bits on modern computer.
Multiplication by Repeated Doubling
The multiple precision implementation contains a unique division algorithm by repeated doubling.
The main benefit of this approach is that it only uses additions and shifts to perform division. This algorithm can probably be extended to support multi-core implementation and is very robust.
This diagram shows the process going on inside the algorithm when computing 30/5.
I suspect that the ramping up happens in logaritmic time, but on the way down we zig-zag many times, possibly as bad as linear time. I wonder if its possible to improve this? It might be possible to cache the results on the way back to avoid oscilations.
The source code is available as an Xcode project. This project may not be reproduced except for personal use.