CMU 15-418/618 (Spring 2013) Final Project:
CUDA RSA
AJ Kaufman & David Matlack
Project Code: github
Reports

Project Proposal

Checkpoint Report

Final Report

Working Schedule

Week What We Plan To Do What We Actually Did
Apr 1-7  Decide on a project.  Chose to work on a CUDA based integer factorizor, with a possible goal of breaking RSA encryptions
Apr 8-14  Create proposal, choose algorithm, choose/implement multiple precision library  Wrote proposal, investigated Pollard's p - 1 algorithm as well as the elliptic curve method for factorization. Decided, based on promising results as well as our ability to understand it, to start with Pollard's algorithm.
Apr 15-21  Finalize multiple precision implementation, begin GPU based implementation  Began CPU implementation of Pollard's algorithm using longs. Began working on Multiple Precision library.
Apr 22-28  Continue work on GPU implementation
  Finish GPU based implementation of Pollard's algorithm, using longs
 Finished CPU implementation of Pollard's algorithm, and began GPU implementation (again using longs), near completion of GPU implementation. Completed most of Multiple Precision library.
Apr 29-May 5  Finish work on MP library and adapt GPU factor code to use MP library.
 Profile code, create test suite and begin comparing to standards
 Major refactor of MP library, addition of factorization specific operations.
 Port of GPU code to our MP library lots of debugging... trying to figure out why it runs so slow.
May 6-11  Consider optimizations, reworks for specific GPU architecture
 Implement RSA cracking, using factorization algorithm, evaluate viability of stretch goals
 Restructuring of GPU algorithm, lots of tweaking, and testing.  Writing of final report and presentation.

Working Log

A more detailed worklog with more ranting can be found in the commit history of our github repo for this project here.